Parsing Expression Grammar

*Parsing Expression Grammars* (PEGs) provide ordered choice. Unlike in parser combinators, the ordered choice of PEGs always follows the first matching alternative and ignores other alternatives. Valid input always results in exactly one parse-tree, the result of a parse is never ambiguous.

Also see wikipedia

> In computer science, a parsing expression grammar (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.

Parsing expression grammars (PEGs) developed by Ford [For04] are an alternative, recognition-based formal foundation for language syntax. PEGs are stylistically similar to CFGs with regular expression-like features, similarly to the Extended Backus-Naur Form (EBNF) notation [Wir77, ISO96]. The key difference is that in place of the unordered choice operator | used to indicate alternative expansions for a non-terminal in EBNF, PEGs use the prioritized choice operator / . This operator lists alternative patterns to be tested in order, unconditionally using the first successful match. The EBNF rules

A → ab | a A → a | ab

are equivalent in CFGs, but the PEG rules

A ← ab / a A ← a / ab

are different. The second alternative in the latter PEG rule will never succeed because the first choice is always taken if the input string to be recognized begins with ’a’ .

A PEG may be viewed as a formal description of a top-down parser.

[…] Table 3.1: PEG operators

~

Jan Kurs, „Parsing For Agile Modeling“, Wayback Machine, 20. Januar 2022. pdf , p. 24–25.