> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/programming_language_theory/parsers/peg.md).

# Parsing Expression Grammer (PEG) parser

## Basic idea

Grammar formalism where each rule is a *deterministic*, prioritised, ordered choice (`/`) rather than the unordered `|` of CFGs. Always unambiguous: the first alternative that matches wins. With memoisation ("Packrat"), parses in linear time.

## Key formulas

* Time (Packrat): $O(n)$, space $O(n)$
* Choice is ordered: $A / B$ tries $A$ first; on success, $B$ is never tried.
* Strictly different power than CFGs — can express $a^n b^n c^n$.