pt::pegrammar(n)

💖 pt::pegrammar — Introduction to Parsing Expression Grammars 💖

okay bestie, so this is pt::pegrammar from the Parser Tools family, and it's basically the ✨lore drop✨ for Parsing Expression Grammars. pull up a chair, grab a boba, we're doing theory today 🧋

---

🌸 SYNOPSIS 🌸

package require Tcl 8.5 9

---

✨ DESCRIPTION ✨

Are you lost? 😭 Is this document giving you a headache? Do you have trouble understanding it? girl, same, but if that's you, pls go read the overview in the Introduction to Parser Tools first. This doc here is the entrypoint to the whole system that this package is part of. door = open 🚪✨

Welcome to the intro to Parsing Expression Grammars (short: PEG), the formalism the Parser Tools use. Now — heads up — this assumes you already know a lil something about parsing theory, i.e. Context-Free Grammars (short: CFG), languages, and the whole vocab squad: LL(k), LR(k), terminal and nonterminal symbols, etc. We are not recapping that. We're not re-explaining useful, reachable, (left/right) recursive, nullable, first/last/follow sets, none of it 🙈. If you need that background, scroll to the References at the end, they got you covered with places and books. 💅

PEGs are formally very similar to CFGs — terminal and nonterminal symbols, start symbol, and rules defining the structure of each nonterminal symbol. The main difference is in the choice (sic!) of choice operators. Where CFGs use an unordered choice to represent alternatives, PEGs use prioritized choice. Which is a fancy way of saying: the parser has to try the first alternative first, and can try the other alternatives only if it fails for the first, and so on. one at a time bestie, no skipping the line 🚦

On the CFG side this gives rise to LL(k) and LR(k) for making the choice deterministic with a bounded lookahead of k terminal symbols, where LL is in essence topdown aka recursive descent parsing, and LR is bottomup aka shift reduce parsing.

On the PEG side, we can parse input with recursive descent and backtracking of failed choices — and that backtracking thing amounts to unlimited lookahead 👀. By additionally recording the success or failure of nonterminals at the specific locations they were tried at, and reusing this info after backtracking, we can avoid the exponential blowup of running time that's usually associated with backtracking, and keep the parsing linear. The memory requirements are of course higher thanks to that cache, because we are literally trading space for time. 💀 no free lunch, periodt.

This is the basic concept behind packrat parsers. 🐀✨ iconic name, honestly.

A limitation pure PEGs share with LL(k) CFGs is that left-recursive grammars cannot be parsed, and the associated recursive descent parser just enters an infinite recursion 🌀😵💫. This limitation is usually overcome by extending pure PEGs with explicit operators to specify repetition — zero or more, and one or more — or, formally spoken, for the kleene closure and positive kleene closure. That is what the Parser Tools are doing. slay.

Another extension, specific to Parser Tools, is a set of operators which map more or less directly to various character classes built into Tcl, i.e. the classes reachable via string is. 👑

The rest of this document is: the formal definition of PEGs for the mathematically inclined, and an appendix listing references to places with more info on PEGs specifically, and parsing in general. 🦋

---

🎀 FORMAL DEFINITION 🎀

For the mathematically inclined 💜, a Parsing Expression Grammar is a 4-tuple (VN,VT,R,eS) where:

• VN is a set of nonterminal symbols,
• VT is a set of terminal symbols,
• R is a finite set of rules, where each rule is a pair (A,e), A in VN, and e a parsing expression.
• eS is a parsing expression, the start expression.

Further constraints are:

• The intersection of VN and VT is empty.
• For all A in VT exists exactly one pair (A,e) in R. In other words, R is a function from nonterminal symbols to parsing expressions.

Parsing expressions are inductively defined via:

• The empty string (epsilon) is a parsing expression.
• A terminal symbol a is a parsing expression.
• A nonterminal symbol A is a parsing expression.
• e1e2 is a parsing expression for parsing expressions e1 and 2. This is called sequence.
• e1/e2 is a parsing expression for parsing expressions e1 and 2. This is called ordered choice.
• e* is a parsing expression for parsing expression e. This is called zero-or-more repetitions, also known as kleene closure.
• e+ is a parsing expression for parsing expression e. This is called one-or-more repetitions, also known as positive kleene closure.
• !e is a parsing expression for parsing expression e1. This is called a not lookahead predicate.
• &e is a parsing expression for parsing expression e1. This is called an and lookahead predicate.

PEGs are used to define a grammatical structure for streams of symbols over VT. They are a modern phrasing of older formalisms invented by Alexander Birham. These formalisms were called TS (TMG recognition scheme), and gTS (generalized TS). Later they were renamed to TPDL (Top-Down Parsing Languages) and gTPDL (generalized TPDL). history lesson unlocked 🏛️✨

They can be easily implemented by recursive descent parsers with backtracking. This makes them relatives of LL(k) Context-Free Grammars. family reunion 🫶

---

📚 REFERENCES 📚

1. The Packrat Parsing and Parsing Expression Grammars Page [http://www.pdos.lcs.mit.edu/~baford/packrat/], by Bryan Ford, Massachusetts Institute of Technology. This is the main entry page to PEGs, and their realization through Packrat Parsers. 🌟
2. [http://en.wikipedia.org/wiki/Parsing_expression_grammar] — Wikipedia's entry about Parsing Expression Grammars.
3. Parsing Techniques - A Practical Guide [http://www.cs.vu.nl/~dick/PTAPG.html], an online book offering a clear, accessible, and thorough discussion of many different parsing techniques with their interrelations and applicabilities, including error recovery techniques. 📖
4. Compilers and Compiler Generators [http://scifac.ru.ac.za/compilers/], an online book using CoCo/R, a generator for recursive descent parsers.

---

🙈 BUGS, IDEAS, FEEDBACK 🙈

This document, and the package it describes, will undoubtedly contain bugs and other problems. 😭 not me admitting it but okay, honesty is hot. Please report such in the category pt of the Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist]. Please also report any ideas for enhancements you may have for either package and/or documentation. we want your thoughts bestie 💌

When proposing code changes, please provide unified diffs, i.e the output of diff -u.

Note further that attachments are strongly preferred over inlined patches. Attachments can be made by going to the Edit form of the ticket immediately after its creation, and then using the left-most button in the secondary navigation bar. 🖱️✨

---

👑 KEYWORDS 👑

EBNF, LL(k), PEG, TDPL, context-free languages, expression, grammar, matching, parser, parsing expression, parsing expression grammar, push down automaton, recursive descent, state, top-down parsing languages, transducer

---

🍓 CATEGORY 🍓

Parsing and Grammars

---

💜 COPYRIGHT 💜

Copyright (c) 2009 Andreas Kupries <andreas_kupries@users.sourceforge.net>

---

and that's the whole thing, bestie 🎀 this was pt::pegrammar(n) from tcllib 1.1 — go forth and parse, you absolute main character 🦋💅✨