Parsing Expression Grammar

In computer science, a parsing expression grammar, or PEG, is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language. The formalism was introduced by Bryan Ford in 2004 and is closely related to the family of top-down parsing languages introduced in the early 1970s. Syntactically, PEGs also look similar to context-free grammars (CFGs), but they have a different interpretation: the choice operator selects the first match in PEG, while it is ambiguous in CFG. This is closer to how string recognition tends to be done in practice, e.g. by a recursive descent parser.

Unlike CFGs, PEGs cannot be ambiguous; if a string parses, it has exactly one valid parse tree. This makes PEGs well-suited to parsing computer languages, but not natural languages.

Read more about Parsing Expression Grammar:  Implementing Parsers From Parsing Expression Grammars, Advantages

Famous quotes containing the words expression and/or grammar:

    Our minds can go no further. The human imagination is capable of no further expression of beauty than the carved owl of Athene, the archaic, marble serpent, the arrogant selfish head of the Acropolis Apollo.
    Hilda Doolittle (1886–1961)

    Grammar is a tricky, inconsistent thing. Being the backbone of speech and writing, it should, we think, be eminently logical, make perfect sense, like the human skeleton. But, of course, the skeleton is arbitrary, too. Why twelve pairs of ribs rather than eleven or thirteen? Why thirty-two teeth? It has something to do with evolution and functionalism—but only sometimes, not always. So there are aspects of grammar that make good, logical sense, and others that do not.
    John Simon (b. 1925)