Parsing expression grammar: Difference between revisions

Revision as of 19:13, 27 December 2023

Revision as of 10:05, 28 December 2023

Line 15:

Syntactically, PEGs also look similar to [[context-free grammar]]s (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 grammar|ambiguous]]; a string has exactly one valid [[parse tree]] or none. It is conjectured that there exist context-free languages that cannot be recognized by a PEG, but this is not yet proven.<ref name="For04" /> PEGs are well-suited to parsing computer languages (and artificial human languages such as [[Lojban]]), butwhere notmultiple [[naturalinterpretation language]]salternatives wherecan thebe performancedisambiguated oflocally, PEGbut algorithmsare isless comparablelikely to generalbe CFGuseful algorithmsfor such as theparsing [[Earleynatural algorithmlanguage]]s where disambiguation may have to be global.<ref name="pegs">

{{cite journal

| first= Bryan |last=Ford