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

Other articles related to "parsing expression grammar, grammars":

Parsing Expression Grammar - Disadvantages - Expressive Power
... Packrat parsers cannot recognize some unambiguous grammars, such as the following (example taken from ) S ← 'x' S 'x'

Famous quotes containing the words grammar and/or expression:

    Hence, a generative grammar must be a system of rules that can iterate to generate an indefinitely large number of structures. This system of rules can be analyzed into the three major components of a generative grammar: the syntactic, phonological, and semantic components.
    Noam Chomsky (b. 1928)

    I have always looked upon decay as being just as wonderful and rich an expression of life as growth.
    Henry Miller (1891–1980)