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:

    They are not callow like the young of most birds, but more perfectly developed and precocious even than chickens. The remarkably adult yet innocent expression of their open and serene eyes is very memorable. All intelligence seems reflected in them. They suggest not merely the purity of infancy, but a wisdom clarified by experience. Such an eye was not born when the bird was, but is coeval with the sky it reflects. The woods do not yield another such a gem.
    Henry David Thoreau (1817–1862)

    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)