Formal Properties of PEGs

• Express all deterministic languages - LR(k)

• Closed under union, intersection, complement

• Some non-context free languages, e.g., anbncn

• Undecidable whether L(G) = ∅

• Predicate operators can be eliminated

  • ...but the process is non-trivial!