grammar::peg(3tcl)

📦
version 2.0 · 2 versions
, in debian trixie, ubuntu questing, ubuntu resolute, ubuntu stonking

💖 NAME 💖

grammar::peg — literally the command for creating and manipulating parsing expression grammars, no cap 💅 (this is the grammar::peg(3tcl) page, bestie, and it's filed under Grammar operations and usage ✨)

✨ SYNOPSIS ✨

package require Tcl 8.5 9

package require snit

package require grammar::peg ?0.3?

::grammar::peg pegName ?=|:=|<--|as|deserialize src?

pegName destroy

pegName clear

pegName = srcPEG

pegName --> dstPEG

pegName serialize

pegName deserialize serialization

pegName is valid

pegName start ?pe?

pegName nonterminals

pegName nonterminal add nt pe

pegName nonterminal delete nt1 ?nt2 ...?

pegName nonterminal exists nt

pegName nonterminal rename nt ntnew

pegName nonterminal mode nt ?mode?

pegName nonterminal rule nt

pegName unknown nonterminals

🌸 DESCRIPTION 🌸

So this package hands you a container class for parsing expression grammars — PEGs for short, iykyk 🦋. What it lets you do is incrementally build up a grammar, poke at its definition, and ask it questions about itself. That's the whole vibe.

What it does NOT do: it doesn't do the fancy complex operations on your grammar, and it 100% cannot take a grammar definition and run it against a stream of symbols. Not its job, bestie. 🙅‍♀️

Two packages that do pick up that slack are grammar::mengine and grammar::peg::interpreter. The first one defines a general-purpose virtual machine for matching a character stream, and the second one implements an interpreter for parsing expression grammars sitting right on top of that virtual machine. Teamwork, honestly. 🫶

🦋 TERMS & CONCEPTS 🦋

PEGs are like context-free grammars but not equivalent — and in some cases PEGs are strictly more powerful than context-free grammars (there are PEGs for some languages that aren't even context-free, iconic 👑). If you want the formal mathematical definition of parsing expressions and parsing expression grammars, it's chilling down in the section PARSING EXPRESSION GRAMMARS.

Short version: we've got terminal symbols, which are the most basic building blocks for sentences, and nonterminal symbols, which come with associated parsing expressions that define the grammatical structure of the sentences. These two symbol sets are distinctive and they do not overlap, periodt. When people talk about symbols they usually drop the word "symbol" entirely (we're all guilty). The union of the terminal and nonterminal symbol sets is called the set of symbols.

Here's a cute little twist: the set of terminal symbols isn't explicitly managed. It's implicitly defined as the set of all characters 🌈. Which means we inherit from Tcl the ability to handle all of Unicode. Slay.

A pair of a nonterminal and a parsing expression is also called a grammatical rule, or just a rule if you're being casual. Inside a rule, the nonterminal is often called the left-hand-side (LHS) and the parsing expression is the right-hand-side (RHS). Standard.

The start expression of a grammar is a parsing expression from which all the sentences contained in the language specified by the grammar are derived. Okay so to make this click, let's pretend for a sec that the RHS of every rule (and the start expression too) is either a sequence of symbols or a series of alternate parsing expressions. In that second case you can read the rule as a whole set of rules, each one providing one alternative for the nonterminal. Now: a parsing expression A' is a derivation of a parsing expression A if we pick one of the nonterminals N in the expression, pick one of the alternative rules R for N, and then replace that nonterminal in A with the RHS of the chosen rule. And this is why terminal symbols are called terminal — they cannot be expanded any further, so they terminate the whole deriving-new-expressions process. So satisfying tbh.

An example, because examples ate:

                  Rules
                    (1)  A <- a B c
                    (2a) B <- d B
                    (2b) B <- e

                  Some derivations, using starting expression A.

                    A -/1/-> a B c -/2a/-> a d B c -/2b/-> a d e c

A derived expression that contains only terminal symbols is a sentence. And the set of all sentences that can be derived from the start expression is the language of the grammar. That's the whole point of the exercise 💖.

Some definitions for nonterminals and expressions, bestie, take notes:

  1. A nonterminal A is called reachable if it is possible to derive a parsing expression from the start expression which contains A.
  2. A nonterminal A is called useful if it is possible to derive a sentence from it.
  3. A nonterminal A is called recursive if it is possible to derive a parsing expression from it which contains A, again.
  4. The FIRST set of a nonterminal A contains all the symbols which can occur of as the leftmost symbol in a parsing expression derived from A. If the FIRST set contains A itself then that nonterminal is called left-recursive.
  5. The LAST set of a nonterminal A contains all the symbols which can occur of as the rightmost symbol in a parsing expression derived from A. If the LAST set contains A itself then that nonterminal is called right-recursive.
  6. The FOLLOW set of a nonterminal A contains all the symbols which can occur after A in a parsing expression derived from the start expression.
  7. A nonterminal (or parsing expression) is called nullable if the empty sentence can be derived from it.

And now, based on all of the above, definitions for grammars:

  1. A grammar G is recursive if and only if it contains a nonterminal A which is recursive. The terms left- and right-recursive, and useful, are analogously defined.
  2. A grammar is minimal if it contains only reachable and useful nonterminals.
  3. A grammar is wellformed if it is not left-recursive. Such grammars are also complete, which means they always succeed or fail on all input sentences. For an incomplete grammar on the other hand, input sentences exist for which an attempt to match them against the grammar will not terminate. 😭 Not the infinite loop.
  4. Since we want to allow ourselves to build a grammar incrementally inside a container object, we will encounter stages where the RHS of one or more rules reference symbols that the container doesn't know about yet. Such a grammar we call invalid. And no, we cannot call it incomplete — that word is already taken, see the last item. Sorry, the vocabulary is booked solid 💀.

💅 CONTAINER CLASS API 💅

The package exports the API described right here. Enjoy.

  • ::grammar::peg pegName ?=|:=|<--|as|deserialize src? — This command creates a brand new container object for a parsing expression grammar and returns the fully qualified name of the object command as its result. The API that the returned command follows is described down in the section CONTAINER OBJECT API, and you use it to invoke all kinds of operations on the container and the grammar living inside it.

If you don't specify src, your new container — i.e. your grammar — will be empty. Otherwise it will hold a copy of the grammar contained in src. For every operator except deserialize, src has to be a container object reference. The deserialize operator instead requires src to be the serialization of a parsing expression grammar. Different flavor of src, same energy.

An empty grammar has no nonterminal symbols, and its start expression is the empty expression, i.e. epsilon. It is valid, but it is not useful. (A mood, honestly, but for grammars it's just a technical fact 🙈.)

🎀 CONTAINER OBJECT API 🎀

All grammar container objects provide the following methods for manipulating their contents. Every single one, no skipping 💖:

  • pegName destroy — Destroys the grammar, including its storage space and its associated command. Gone, reduced to atoms ✨.
  • pegName clear — Clears out the definition of the grammar contained in pegName, but does not destroy the object. It stays, just empty. A fresh start, main character energy 🌸.
  • pegName = srcPEG — Assigns the contents of the grammar contained in srcPEG to pegName, overwriting whatever definition was there. This is the assignment operator for grammars. It copies the grammar contained in the grammar object srcPEG over the grammar definition in pegName. The old contents of pegName are deleted by this operation. 💀

This operation is in effect equivalent to

    pegName deserialize [srcPEG serialize]
  • pegName --> dstPEG — This is the reverse assignment operator for grammars. It copies the automation contained in the object pegName over the grammar definition in the object dstPEG. The old contents of dstPEG are deleted by this operation.

This operation is in effect equivalent to

    dstPEG deserialize [pegName serialize]
  • pegName serialize — This method serializes the grammar stored in pegName. In other words it returns a tcl value that completely describes that grammar. Which means you can, for example, transfer grammars over arbitrary channels, do persistence, all that good stuff 🦋. This method is also the basis for both the copy constructor and the assignment operator. Look at it carrying the whole team.

The result of this method has to be semantically identical across all implementations of the grammar::peg interface. That's literally what enables us to copy grammars between different implementations of the same interface. Iconic interoperability behavior 👑.

The result is a list of four elements with this structure:

  1. The constant string grammar::peg.
  2. A dictionary. Its keys are the names of all known nonterminal symbols, and their associated values are the parsing expressions describing their sentennial structure.
  3. A dictionary. Its keys are the names of all known nonterminal symbols, and their associated values are hints to a matcher regarding the semantic values produced by the symbol.
  4. The last item is a parsing expression, the start expression of the grammar.

Assuming the following PEG for simple mathematical expressions

                  Digit      <- '0'/'1'/'2'/'3'/'4'/'5'/'6'/'7'/'8'/'9'
                  Sign       <- '+' / '-'
                  Number     <- Sign? Digit+
                  Expression <- '(' Expression ')' / (Factor (MulOp Factor)*)
                  MulOp      <- '*' / '/'
                  Factor     <- Term (AddOp Term)*
                  AddOp      <- '+'/'-'
                  Term       <- Number

a possible serialization is 👀 (bestie, hold that thought — it's literally coming in the next bit, don't go anywhere ✨)

                  grammar::peg \
                  {Expression {/ {x ( Expression )} {x Factor {* {x MulOp Factor}}}} \
                   Factor     {x Term {* {x AddOp Term}}} \
                   Term       Number \
                   MulOp      {/ * /} \
                   AddOp      {/ + -} \
                   Number     {x {? Sign} {+ Digit}} \
                   Sign       {/ + -} \
                   Digit      {/ 0 1 2 3 4 5 6 7 8 9} \
                  } \
                  {Expression value     Factor     value \
                   Term       value     MulOp      value \
                   AddOp     value     Number     value \
                   Sign       value     Digit      value \
                  }
                  Expression

okay so that's a possible one, because the order of the nonterminals in the dictionary is not relevant. like, the dict is a dict, bestie, it does not care about your ordering opinions. 💅

  • pegName deserialize serialization — this is the complement to serialize. It swaps the grammar definition inside pegName for the grammar that serialization describes. and yes — the old contents of pegName get deleted by this operation. gone. bye. 👋
  • pegName is valid — a predicate, bestie. It tests whether the PEG in pegName is valid. (see the TERMS & CONCEPTS section for what that property even means.) The result is a boolean: true if the PEG has the tested property, false otherwise. no cap. ✨
  • pegName start ?pe? — this method defines the start expression of the grammar. It replaces the previously defined start expression with the parsing expression pe. The method fails and throws an error if pe does not contain a valid parsing expression as specified in the section PARSING EXPRESSIONS. and in that case, the existing start expression is not changed. The method returns the empty string as its result. If you call it with no argument at all, it just hands you back the currently defined start expression. cute, right? 🎀
  • pegName nonterminals — returns the set of all nonterminal symbols known to the grammar. that's it. that's the whole method. iconic behaviour honestly. 🌸
  • pegName nonterminal add nt pe — adds the nonterminal nt and its associated parsing expression pe to the set of nonterminal symbols and rules of the PEG living inside pegName. The method fails and throws an error if either the string nt is already known as a symbol of the grammar, or if pe does not contain a valid parsing expression as specified in the section PARSING EXPRESSIONS. In that case the current set of nonterminal symbols and rules is not changed. The method returns the empty string as its result. 🫶
  • pegName nonterminal delete nt1 ?nt2 ...? — removes the named symbols nt1, nt2 … from the set of nonterminal symbols of the PEG contained in pegName. The method fails and throws an error if <em>any</em> of the strings is not known as a nonterminal symbol. In that case the current set of nonterminal symbols is not changed. The method returns the empty string as its result.
⚠️ lowkey important: the stored grammar becomes invalid if the deleted nonterminals are still referenced by the RHS of rules that are still known. so like… be careful. 💀
  • pegName nonterminal exists nt — a predicate. It tests whether the nonterminal symbol nt is known to the PEG in pegName. The result is a boolean: true if the symbol nt is known, false otherwise. vibe check, but for symbols. ✅
  • pegName nonterminal rename nt ntnew — renames the nonterminal symbol nt to ntnew. The method fails and throws an error if either nt is not known as a nonterminal, or if ntnew is a known symbol. The method returns the empty string as its result. glow-up, but make it a symbol. 💅✨
  • pegName nonterminal mode nt ?mode? — this mode returns or sets the semantic mode associated with the nonterminal symbol nt. If no mode is specified, the current mode of the nonterminal is returned. Otherwise the current mode is set to mode. The method fails and throws an error if nt is not known as a nonterminal. The grammar interpreter implemented by the package grammar::peg::interpreter recognizes the following modes:
    • value — the semantic value of the nonterminal is the abstract syntax tree created from the ASTs of the RHS and a node for the nonterminal itself. 🦋
    • match — the semantic value of the nonterminal is an the abstract syntax tree consisting of single a node for the string matched by the RHS. The ASTs generated by the RHS are discarded. 🗑️
    • leaf — the semantic value of the nonterminal is an the abstract syntax tree consisting of single a node for the nonterminal itself. The ASTs generated by the RHS are discarded. 🍓
    • discard — the nonterminal has no semantic value. The ASTs generated by the RHS are discarded (as well). 💀
  • pegName nonterminal rule nt — returns the parsing expression associated with the nonterminal nt. The method fails and throws an error if nt is not known as a nonterminal. 🔍
  • pegName unknown nonterminals — returns a list containing the names of all nonterminal symbols which are referenced on the RHS of a grammatical rule, but have no rule definining their structure. In other words: a list of the nonterminal symbols which make the grammar invalid. The grammar is valid if this list is empty. so if it's empty? you ate. periodt. 👑

✨ PARSING EXPRESSIONS ✨

Various methods of PEG container objects expect a parsing expression as their argument, or will return such. This section specifies the format such parsing expressions are in. buckle up bestie, here's the list 🧚

  1. The string epsilon is an atomic parsing expression. It matches the empty string.
  2. The string alnum is an atomic parsing expression. It matches any alphanumeric character.
  3. The string alpha is an atomic parsing expression. It matches any alphabetical character.
  4. The string dot is an atomic parsing expression. It matches any character.
  5. The expression [list t x] is an atomic parsing expression. It matches the terminal string x.
  6. The expression [list n A] is an atomic parsing expression. It matches the nonterminal A.
  7. For parsing expressions e1, e2, … the result of [list / e1 e2 ... ] is a parsing expression as well. This is the ordered choice, aka prioritized choice. 🔀
  8. For parsing expressions e1, e2, … the result of [list x e1 e2 ... ] is a parsing expression as well. This is the sequence. ➡️
  9. For a parsing expression e the result of [list * e] is a parsing expression as well. This is the kleene closure, describing zero or more repetitions. 🔁
  10. For a parsing expression e the result of [list + e] is a parsing expression as well. This is the positive kleene closure, describing one or more repetitions. ➕
  11. For a parsing expression e the result of [list & e] is a parsing expression as well. This is the and lookahead predicate. 👀
  12. For a parsing expression e the result of [list ! e] is a parsing expression as well. This is the not lookahead predicate. 🙅
  13. For a parsing expression e the result of [list ? e] is a parsing expression as well. This is the optional input. 🎀

Examples of parsing expressions where already shown, in the description of the method serialize. (go scroll back up, they're right there, i promise 💖)

🦋 PARSING EXPRESSION GRAMMARS 🦋

For the mathematically inclined, a PEG 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 expression 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, bestie, take notes 📝

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

📚 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. 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. 📖
  3. 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 🐛

okay bestie, real talk: this doc and the package it describes are absolutely gonna have bugs and other problems. it's giving "software, but make it human". not a vibe, but it's the truth 💀

so if you find one, please report it in the category grammar_peg of the Tcllib Trackers at http://core.tcl.tk/tcllib/reportlist. also, if you've got ideas for enhancements — for either the package and/or the documentation — slide those in too, we want them 🫶

📝 a lil note on proposing code changes

when you propose code changes, please provide unified diffs, i.e. the output of diff -u. no cap, that's the format that makes everyone's life easier ✨

also note further that attachments are strongly preferred over inlined patches. how do you attach? go to the Edit form of the ticket immediately after creating it, then use the left-most button in the secondary navigation bar. iconic behavior, do it that way 💅

🔑 KEYWORDS 🔑

these are the lil searchable tags, so here's the full set, no skips:

  • LL(k)
  • TDPL
  • context-free languages
  • expression
  • grammar
  • parsing
  • parsing expression
  • parsing expression grammar
  • push down automaton
  • recursive descent
  • state
  • top-down parsing languages
  • transducer

🗂️ CATEGORY 🗂️

Grammars and finite automata — that's the whole category, bestie. short, sweet, extremely on brand 🌸

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

that's the whole copyright line, character for character, don't @ me 💜

and that's a wrap on grammar::peg(3tcl) 💖 this page is part of tcllib, version 0.3, and it's dated 0.3 in the footer — go forth and parse, bestie, you absolutely ate 👑✨ mwah 💅
📦 where this page comes from