Parsing expression grammar

<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a parsing expression grammar (PEG) is a type of <a href="/facts/Formal_grammar/QLxaQNAz">analytic</a> <a href="/facts/Formal_grammar/QLxaQNAz">formal grammar</a>, i.e. it describes a <a href="/facts/Formal_language/crDTyP8q">formal language</a> in terms of a set of rules for recognizing <a href="/facts/String_(computer_science)/4ChJu5WS">strings</a> in the language. The formalism was introduced by Bryan Ford in 2004 and is closely related to the family of <a href="/facts/Top-down_parsing_language/aYFundzW">top-down parsing languages</a> introduced in the early 1970s.
Syntactically, PEGs also look similar to <a href="/facts/Context-free_grammar/yu1FFdK4">context-free grammars</a> (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 <a href="/facts/Recursive_descent_parser/ARhcuAv1">recursive descent parser</a>.
</p><p>Unlike CFGs, PEGs cannot be <a href="/facts/Ambiguous_grammar/elcVDDL4">ambiguous</a>; a string has exactly one valid <a href="/facts/Parse_tree/FeBEtXcz">parse tree</a> or none. It is conjectured that there exist context-free languages that cannot be recognized by a PEG, but this is not yet proven. PEGs are well-suited to parsing computer languages (and artificial human languages such as <a href="/facts/Lojban/JSza3con">Lojban</a>) where multiple interpretation alternatives can be disambiguated locally, but are less likely to be useful for parsing <a href="/facts/Natural_language/B4gLS7Kd">natural languages</a> where disambiguation may have to be global.
</p>

Parsing expression grammar open-in-new

Parsing expression grammar