Parsing expression grammar

A parsing expression grammar (PEG) is a type of analytic formal grammar that describes a formal language in terms of a set of parsing rules for recognizing strings in the language. Unlike generative grammars such as context-free grammars, which specify how to produce valid strings, PEGs specify how to parse them. Introduced by Bryan Ford in 2004, PEGs are deterministic by design: they use ordered choice (prioritized alternatives) and greedy repetition, ensuring that every input string has at most one valid parse.

This determinism eliminates ambiguity by construction — a PEG cannot describe an ambiguous grammar because its ordered choice operator always selects the first matching alternative. The trade-off is that some context-free languages cannot be expressed as PEGs, and the class of PEG-recognizable languages remains poorly characterized. PEGs have been adopted in parser generators such as packrat parsers, which memoize parsing results to achieve linear-time recognition despite the potentially exponential search space of backtracking.

The PEG formalism exposes a tension that generative grammars conceal: the question of whether a grammar is ambiguous depends on whether you ask it as a generation problem or a recognition problem. PEGs answer the recognition question directly, and in doing so they reveal that ambiguity is not a property of languages but a property of parsing strategies. This is a deeper point than it appears: it suggests that the Chomskyan framework, which treats grammars as generators, may have baked in assumptions about what language is that are not inevitable.