pt::peg_language(n)
pt::peg_language(n) 💖
Parser Tools — okay bestie, welcome to the PEG Language Tutorial, and yes this is literally the whole vibe. 💅
✨ SYNOPSIS ✨
package require Tcl 8.5 9🌸 DESCRIPTION 🌸
Are you lost? Like, genuinely confused by this document? 🥺 No worries — go read the overview that the Introduction to Parser Tools hands you. That doc is the front door to the entire system this package lives in, so start there if you're feeling ✨ adrift ✨.
Hi again!! 👑 Welcome to the tutorial / introduction for the PEG Specification Language. If you already know this language and you're just here for a lil refresher, you can absolutely skip ahead to the section we mentioned and read the full formal specification. No judgement, go off. 🦋
🌈 WHAT IS IT? 🌈
peg — a language for specifying parsing expression grammars — is meant to be human readable and human writable, but still strict enough that a machine can process it. Y'know, like every computer language ever. 💀
It was defined to make writing a grammar specification easy, which is lowkey something the other formats floating around in Parser Tools do not lend themselves to. Not naming names but 👀
🎀 THE ELEMENTS OF THE LANGUAGE 🎀
⭐ BASIC STRUCTURE
The general outline of a textual PEG is:
PEG <<name>> (<<start-expression>>)
<<rules>>
END;Heads up bestie: we're using text in double angle-brackets as place-holders for things we haven't explained yet. iykyk. 🙈
💜 NAMES
Names are mostly there to identify the nonterminal symbols of the grammar — i.e. the thing that shows up on the left-hand side of a <rule>. The one exception? The name you drop right after the keyword PEG (see the previous section), which is the name of the whole grammar itself. Main character energy. 👑
The structure of a name is simple:
- It begins with a letter, underscore, or colon, followed by
- zero or more letters, digits, underscores, or colons.
Or, in formal textual notation:
([_:] / <alpha>) ([_:] / <alnum>)*Examples of names:
Hello
::world
_:submarine55_Examples of text which are not names:
12
.bogus
0wrong
@location🌸 RULES 🌸
The main body of a grammar specification's text is taken up by the rules. Each rule defines the sentence structure of one nonterminal symbol. Their basic structure is:
<<name>> <- <<expression>> ;The <name> specifies the nonterminal symbol being defined, and the <expression> after the arrow (<-) declares its structure. 🫶
Note that each rule ends in a single semicolon, even the last one. Like, the semicolon is a rule terminator, not a separator. Don't come for me, that's just how it is. 💅
We can have as many rules as we like, as long as we define each nonterminal symbol at most once, and have at least one rule for each nonterminal symbol which occurred in an expression — i.e. in either the start expression of the grammar, or the right-hand side of a rule.
🔥 EXPRESSIONS 🔥
The parsing expressions are the meat of any specification. 🍓 They declare the structure of the whole document (<<start-expression>>), and of all nonterminal symbols.
All expressions are made up out of atomic expressions plus operators combining them. We've got operators for choosing between alternatives, repetition of parts, and look-ahead constraints. There is no explicit operator for the sequencing (also known as concatenation) of parts, though — you specify that by simply placing the parts adjacent to each other. It's giving "just put them next to each other". ✨
Here are the operators, from highest to lowest priority (i.e. strength of binding):
# Binary operators.
<<expression-1>> <<expression-2>> # sequence. parse 1, then 2.
<<expression-1>> / <<expression-2>> # alternative. try to parse 1, and parse 2 if 1 failed to parse.
# Prefix operators. Lookahead constraints. Same priority.
& <<expression>> # Parse expression, ok on successful parse.
! <<expression>> # Ditto, except ok on failure to parse.
# Suffix operators. Repetition. Same priority.
<<expression>> ? # Parse expression none, or once (repeat 0 or 1).
<<expression>> * # Parse expression zero or more times.
<<expression>> + # Parse expression one or more times.
# Expression nesting
( <<expression>> ) # Put an expression in parens to change its priority.With this we can now deconstruct the formal expression for names given in section Names:
([_:] / <alpha>) ([_:] / <alnum>)*It's a sequence of two parts,
[_:] / <alpha>and
([_:] / <alnum>)*The parentheses around the parts kept their inner alternatives bound together against the normally higher priority of the sequence. Each of the two parts is an alternative, with the second part additionally repeated zero or more times, leaving us with the three atomic expressions:
[_:]
<alpha>
<alnum>And atomic expressions are our next topic, bestie. 📚 They fall into three classes:
- names, i.e. nonterminal symbols,
- string literals, and
- character classes.
Names we know about already — or see section Names for a refresher. 💖
String literals are simple. They're delimited by (i.e. start and end with) either a single or double-apostroph, and in between the delimiters we can have any character but the delimiter itself. They can be empty as well. Examples of strings are:
''
""
'hello'
"umbra"
"'"
'"'The last two examples show how to place any of the delimiters into a string. Iconic. 🎀
For the last, but definitely not least, of our atomic expressions — character classes — we have a bunch of predefined classes, shown below, plus the ability to construct our own. The predefined classes are:
<alnum> # Any unicode alphabet or digit character (string is alnum).
<alpha> # Any unicode alphabet character (string is alpha).
<ascii> # Any unicode character below codepoint 0x80 (string is ascii).
<control> # Any unicode control character (string is control).
<ddigit> # The digit characters [0-9].
<digit> # Any unicode digit character (string is digit).
<graph> # Any unicode printing character, except space (string is graph).
<lower> # Any unicode lower-case alphabet character (string is lower).
<print> # Any unicode printing character, incl. space (string is print).
<punct> # Any unicode punctuation character (string is punct).
<space> # Any unicode space character (string is space).
<upper> # Any unicode upper-case alphabet character (string is upper).
<wordchar> # Any unicode word character (string is wordchar).
<xdigit> # The hexadecimal digit characters [0-9a-fA-F].
. # Any character, except end of input.And the syntax of custom-defined character classes is:
[ <<range>>* ]where each range is either a single character, or of the form:
<<character>> - <character>>Examples for character classes we have already seen in the course of this introduction are:
[_:]
[0-9]
[0-9a-fA-F]We're nearly done with expressions, bestie, hang in there. 🫶 The only piece left is to tell you how the characters in character classes and string literals are specified.
Basically, characters in the input stand for themselves, and on top of that we have several types of escape syntax to represent control characters, or characters outside of the encoding the text is in.
All the escaped forms start with a backslash character ('\', unicode codepoint 0x5C). That's then followed by a series of octal digits, or 'u' and hexadecimal digits, or a regular character from a fixed set for various control characters. Some examples:
\n \r \t \' \" \[ \] \\ #
\000 up to \277 # octal escape, all ascii character, leading 0's can be removed.
\u2CA7 # hexadecimal escape, all unicode characters.
# # Here 2ca7 <=> Koptic Small Letter Tau💅 WHITESPACE AND COMMENTS 💅
One issue we haven't touched on so far is whitespace and comments. 😌
Whitespace is any unicode space character — i.e. anything in the character class <space> — plus comments. Comments are sequences of characters starting with a '#' (hash, unicode codepoint 0x23) and ending at the next end-of-line.
Whitespace can be freely used between all syntactical elements of a grammar specification. It cannot be used inside of syntactical elements — like names, string literals, predefined character classes, etc. Respect the boundaries bestie. 🙈
👑 NONTERMINAL ATTRIBUTES 👑
Lastly, a more advanced topic. In the section Rules we gave the structure of a rule as:
<<name>> <- <<expression>> ;This is not quite true. 👀 It's possible to associate a semantic mode with the nonterminal in the rule, by writing it before the name, separated from it by a colon, i.e. writing:
<<mode>> : <<name>> <- <<expression>> ;is also allowed. This mode is optional. The known modes and their meanings are:
value— The semantic value of the nonterminal symbol is an abstract syntax tree consisting of a single node node for the nonterminal itself, which has the ASTs of the symbol's right hand side as its children.leaf— The semantic value of the nonterminal symbol is an abstract syntax tree consisting of a single node node for the nonterminal, without any children. Any ASTs generated by the symbol's right hand side are discarded.void— The nonterminal has no semantic value. Any ASTs generated by the symbol's right hand side are discarded (as well).
Of these three modes only leaf and void can be specified directly. value is implicitly specified by the absence of a mode before the nonterminal.
Now, with all the above under our belt, it should be possible to not only read, but actually understand the formal specification of the text representation shown in the next section — written in itself. 🤯 Slay.
💅 PEG SPECIFICATION LANGUAGE 💅
okay so bestie, peg is a whole language for specifying parsing expression grammars. It's meant to be human readable and writable, but also strict enough that a machine can process it. Like any computer language, fr fr. It was defined to make writing a grammar spec easy — something the other formats in the Parser Tools do not lend themselves too. It's formally specified by the grammar below, written in itself. For a tutorial / intro, go read the PEG Language Tutorial. 💖
PEG pe_grammar_for_peg (Grammar)
# --------------------------------------------------------------------
# Syntactical constructs
Grammar <- WHITESPACE Header Definition* Final EOF ;
Header <- PEG Identifier StartExpr ;
Definition <- Attribute? Identifier IS Expression SEMICOLON ;
Attribute <- (VOID / LEAF) COLON ;
Expression <- Sequence (SLASH Sequence)* ;
Sequence <- Prefix+ ;
Prefix <- (AND / NOT)? Suffix ;
Suffix <- Primary (QUESTION / STAR / PLUS)? ;
Primary <- ALNUM / ALPHA / ASCII / CONTROL / DDIGIT / DIGIT
/ GRAPH / LOWER / PRINTABLE / PUNCT / SPACE / UPPER
/ WORDCHAR / XDIGIT
/ Identifier
/ OPEN Expression CLOSE
/ Literal
/ Class
/ DOT
;
Literal <- APOSTROPH (!APOSTROPH Char)* APOSTROPH WHITESPACE
/ DAPOSTROPH (!DAPOSTROPH Char)* DAPOSTROPH WHITESPACE ;
Class <- OPENB (!CLOSEB Range)* CLOSEB WHITESPACE ;
Range <- Char TO Char / Char ;
StartExpr <- OPEN Expression CLOSE ;
void: Final <- "END" WHITESPACE SEMICOLON WHITESPACE ;
# --------------------------------------------------------------------
# Lexing constructs
Identifier <- Ident WHITESPACE ;
leaf: Ident <- ([_:] / <alpha>) ([_:] / <alnum>)* ;
Char <- CharSpecial / CharOctalFull / CharOctalPart
/ CharUnicode / CharUnescaped
;
leaf: CharSpecial <- "\\" [nrt'"\[\]\\] ;
leaf: CharOctalFull <- "\\" [0-3][0-7][0-7] ;
leaf: CharOctalPart <- "\\" [0-7][0-7]? ;
leaf: CharUnicode <- "\\" 'u' HexDigit (HexDigit (HexDigit HexDigit?)?)? ;
leaf: CharUnescaped <- !"\\" . ;
void: HexDigit <- [0-9a-fA-F] ;
void: TO <- '-' ;
void: OPENB <- "[" ;
void: CLOSEB <- "]" ;
void: APOSTROPH <- "'" ;
void: DAPOSTROPH <- '"' ;
void: PEG <- "PEG" !([_:] / <alnum>) WHITESPACE ;
void: IS <- "<-" WHITESPACE ;
leaf: VOID <- "void" WHITESPACE ; # Implies that definition has no semantic value.
leaf: LEAF <- "leaf" WHITESPACE ; # Implies that definition has no terminals.
void: SEMICOLON <- ";" WHITESPACE ;
void: COLON <- ":" WHITESPACE ;
void: SLASH <- "/" WHITESPACE ;
leaf: AND <- "&" WHITESPACE ;
leaf: NOT <- "!" WHITESPACE ;
leaf: QUESTION <- "?" WHITESPACE ;
leaf: STAR <- "*" WHITESPACE ;
leaf: PLUS <- "+" WHITESPACE ;
void: OPEN <- "(" WHITESPACE ;
void: CLOSE <- ")" WHITESPACE ;
leaf: DOT <- "." WHITESPACE ;
leaf: ALNUM <- "<alnum>" WHITESPACE ;
leaf: ALPHA <- "<alpha>" WHITESPACE ;
leaf: ASCII <- "<ascii>" WHITESPACE ;
leaf: CONTROL <- "<control>" WHITESPACE ;
leaf: DDIGIT <- "<ddigit>" WHITESPACE ;
leaf: DIGIT <- "<digit>" WHITESPACE ;
leaf: GRAPH <- "<graph>" WHITESPACE ;
leaf: LOWER <- "<lower>" WHITESPACE ;
leaf: PRINTABLE <- "<print>" WHITESPACE ;
leaf: PUNCT <- "<punct>" WHITESPACE ;
leaf: SPACE <- "<space>" WHITESPACE ;
leaf: UPPER <- "<upper>" WHITESPACE ;
leaf: WORDCHAR <- "<wordchar>" WHITESPACE ;
leaf: XDIGIT <- "<xdigit>" WHITESPACE ;
void: WHITESPACE <- (" " / "\t" / EOL / COMMENT)* ;
void: COMMENT <- '#' (!EOL .)* EOL ;
void: EOL <- "\n\r" / "\n" / "\r" ;
void: EOF <- !. ;
# --------------------------------------------------------------------
END;✨ EXAMPLE ✨
Our example specifies the grammar for a basic 4-operation calculator. 🧮
PEG calculator (Expression)
Digit <- '0'/'1'/'2'/'3'/'4'/'5'/'6'/'7'/'8'/'9' ;
Sign <- '-' / '+' ;
Number <- Sign? Digit+ ;
Expression <- Term (AddOp Term)* ;
MulOp <- '*' / '/' ;
Term <- Factor (MulOp Factor)* ;
AddOp <- '+'/'-' ;
Factor <- '(' Expression ')' / Number ;
END;Using higher-level features of the notation, i.e. the character classes (predefined and custom), this example can be rewritten as:
PEG calculator (Expression)
Sign <- [-+] ;
Number <- Sign? <ddigit>+ ;
Expression <- Term (AddOp Term)* ;
MulOp <- [*/];
Term <- Factor (MulOp Factor)* ;
AddOp <- [-+];
Factor <- '(' Expression ')' / Number ;
END;🐛 BUGS, IDEAS, FEEDBACK 🐛
This document, and the package it describes, will undoubtedly contain bugs and other problems. 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. 🫶
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 🔑
EBNFLL(k)PEGTDPLcontext-free languagesexpressiongrammarmatchingparserparsing expressionparsing expression grammarpush down automatonrecursive descentstatetop-down parsing languagestransducer
📂 CATEGORY 📂
Parsing and Grammars
© COPYRIGHT ©
Copyright (c) 2009 Andreas Kupries <andreas_kupries@users.sourceforge.net>
That's a wrap, bestie! This page is from tcllib, version 1.1, and it's the pt::peg_language(n) page. No date on the footer, but we move. 💅✨
📦 where this page comes from
- fedora 43: tcllib 2.0-3.fc43 · TCL
- fedora 44: tcllib 2.0-4.fc44 · TCL
- nixos 26.05: tcllib 2.0
- nixpkgs unstable: tcllib 2.0
- Copyright (c) 2009 Andreas Kupries <andreas_kupries@users\&.sourceforge\&.net>
- 💖 girlified by deepseek-ai/DeepSeek-V4.1-Flash on : a language model's rewrite of the original, under its terms