PEG(1)

PEG(1) — the manual page bestie 💖

General Commands Manual ✨ (yes, this is a real section, we're keeping it, it's part of the vibe)

---

🌸 NAME 🌸

peg, leg — parser generators 🧚 (they make parsers, they're literally so talented)

---

✨ SYNOPSIS ✨

peg [-hvV -ooutput] [filename ...]
leg [-hvV -ooutput] [filename ...]

---

💜 DESCRIPTION 💜

okay so. peg and leg are tools for generating recursive-descent parsers: programs that perform pattern matching on text. They process a Parsing Expression Grammar (PEG) [Ford 2004] to produce a program that recognises legal sentences of that grammar. 🌈

peg processes PEGs written using the original syntax described by Ford. leg processes PEGs written using slightly different syntax and conventions — those ones are intended to make it an attractive replacement for parsers built with lex(1) and yacc(1). 💅

And here's the tea, bestie: unlike lex and yacc, peg and leg support unlimited backtracking, provide ordered choice as a means for disambiguation, and can combine scanning (lexical analysis) and parsing (syntactic analysis) into a single activity. 😭 iconic behaviour honestly

peg reads the specified filenames, or standard input if no filenames are given, for a grammar describing the parser to generate. Then peg generates a C source file that defines a function yyparse(). This C source file can be included in, or compiled and then linked with, a client program. 🫶

Every time the client program calls yyparse() the parser consumes input text according to the parsing rules, starting from the first rule in the grammar. And yyparse() returns non-zero if the input could be parsed according to the grammar; it returns zero if the input could not be parsed. no cap ✨

The prefix 'yy' or 'YY' is prepended to all externally-visible symbols in the generated parser. This is intended to reduce the risk of namespace pollution in client programs. 🌈 (The choice of 'yy' is historical; see lex(1) and yacc(1), for example.)

---

🎀 OPTIONS 🎀

peg and leg provide the following options, periodt:

• -h — prints a summary of available options and then exits. short king behaviour 💫
• -ooutput — writes the generated parser to the file output instead of the standard output. 🍓
• -P — suppresses #line directives in the output. (bye bye line info 🙈)
• -v — writes verbose information to standard error while working. she's chatty and we love that 💬
• -V — writes version information to standard error then exits. 👑

---

🌟 A SIMPLE EXAMPLE 🌟

okok so the following peg input specifies a grammar with a single rule (called 'start') that is satisfied when the input contains the string "username".

start <- "username"

(The quotation marks are not part of the matched text; they serve to indicate a literal string to be matched.) In other words, yyparse() in the generated C source will return non-zero only if the next eight characters read from the input spell the word "username". 💅

If the input contains anything else, yyparse() returns zero and no input will have been consumed. (Subsequent calls to yyparse() will also return zero, since the parser is effectively blocked looking for the string "username".) 😭 To ensure progress we can add an alternative clause to the 'start' rule that will match any single character if "username" is not found.

start <- "username"
       / .

yyparse() now always returns non-zero (except at the very end of the input). ✨ To do something useful we can add actions to the rules. These actions are performed after a complete match is found (starting from the first rule) and are chosen according to the 'path' taken through the grammar to match the input. (Linguists would call this path a 'phrase marker'.) 🤓

start <- "username"    { printf("%s\n", getlogin()); }
       / < . >         { putchar(yytext[0]); }

The first line instructs the parser to print the user's login name whenever it sees "username" in the input. If that match fails, the second line tells the parser to echo the next character on the input the standard output. 🫶 Our parser is now performing useful work: it will copy the input to the output, replacing all occurrences of "username" with the user's account name. main character energy fr fr 👑

Note the angle brackets ('<' and '>') that were added to the second alternative. These have no effect on the meaning of the rule, but serve to delimit the text made available to the following action in the variable yytext. 🦋

If the above grammar is placed in the file username.peg, running the command

peg -o username.c username.peg

will save the corresponding parser in the file username.c. To create a complete program this parser could be included by a C program as follows.

#include <stdio.h>      /* printf(), putchar() */
#include <unistd.h>     /* getlogin() */

#include "username.c"   /* yyparse() */

int main()
{
  while (yyparse())     /* repeat until EOF */
    ;
  return 0;
}

💖 PEG GRAMMARS 💖

okay bestie, so a grammar is literally just a bunch of named rules, and that's it. each one looks like this:

name <- pattern

and the pattern is made of one or more of these lil guys 👇

• name — this element stands in for the whole entire pattern of the rule that has that name. it's giving "hey go look over there" energy.
• "characters" — anything wrapped in double quotes gets matched literally, exactly as written. and yes, the ANSI C escape sequences are recognised inside. no cap.
• 'characters' — same deal but with single quotes, matched literally, exactly like above. twins fr.
• [characters] — a set of characters in square brackets matches any single character from that set, and escape characters are recognised here too. but here's the tea: if the set starts with an uparrow (^), the whole set gets negated — so it matches any character not in the set. also, any pair of characters separated by a dash (-) means the range from the first to the second, inclusive. and a single alphabetic character or underscore gets matched by this set right here:

[a-zA-Z_]

similarly, this next one matches any single non-digit character:

[^0-9]

• . — a dot matches any character. and note that the only time this fails is at the end of file, where there's literally no character left to match. 💀
• ( pattern ) — parentheses for grouping, which modifies the precedence of the operators we're about to talk about. slay.
• { action } — curly braces surround actions, and the action is arbitrary C source code that runs at the end of matching. any braces inside the action have to be properly nested, bestie. any input text that got matched before the action and was delimited by angle brackets (see below 👇) is made available inside the action as the contents of the character array yytext. and the length of it (how many characters are in yytext) lives in the variable yyleng. (these variable names are historical — go check lex(1) if you're curious.)
• < — an opening angle bracket always matches (and consumes no input) and makes the parser start accumulating matched text. that text then gets handed to actions in the variable yytext.
• > — a closing angle bracket always matches (consumes no input) and makes the parser stop accumulating text for yytext.

---

and now, the glow-up: all of the above can be made optional and/or repeatable with these suffixes ✨

• element ? — the element is optional. if it's there on the input, it gets consumed and the match succeeds. if it's not there, nothing gets consumed and the match succeeds anyway. win-win honestly.
• element + — the element is repeatable. if it's present on the input, one or more occurrences of element get consumed and the match succeeds. if there are no occurrences of element on the input, the match fails. sorry babe.
• element * — optional and repeatable, the full combo. if it's present on the input, one or more occurrences of element get consumed and the match succeeds. if there are none present, the match succeeds anyway. iconic behaviour.

---

and you can turn any of those elements + suffixes into predicates (which match arbitrary input text and then succeed or fail without consuming that input) using these prefixes:

• & element — the predicate succeeds only if element can be matched. and the input text scanned while matching element is not consumed from the input — it stays available for whatever matching happens next. 🫶
• ! element — the predicate succeeds only if element cannot be matched. same deal: text scanned while matching element is not consumed and remains available for subsequent matching. a super popular idiom for this one is

!.

which matches the end of file, after the last character of the input has already been consumed. chef's kiss.

and there's a special form of the & predicate too:

• &{ expression } — in this predicate, the simple C expression (not a statement, bestie, an expression) is evaluated immediately when the parser reaches the predicate. if the expression gives a non-zero (true) result, the match succeeds and the parser keeps going with the next element in the pattern. if the expression gives zero (false), the match fails and the parser backs up to hunt for an alternative parse of the input. no notes.

---

so you can smoosh several elements together (with or without prefixes and suffixes) into a sequence just by writing them one after the other. the entire sequence matches only if every individual element in it matches, going left to right.

and sequences can be split into disjoint alternatives by the alternation operator /.

• sequence-1 / sequence-2 / ... / sequence-N — each sequence gets tried in turn until one of them matches, and at that moment matching for the overall pattern succeeds. if none of the sequences match, then the overall pattern's match fails. periodt.

---

finally, the pound sign (#) starts a comment (which gets discarded) that runs until the end of the line.

---

to summarise all of that: the parser tries to match the input text against a pattern that contains literals, names (which represent other rules), and various operators (written as prefixes, suffixes, juxtaposition for sequencing, and an infix alternation operator) that modify how the elements inside the pattern get matched. matches happen from left to right, descending into named sub-rules as the parser bumps into them. if the matching process fails, the parser back tracks (rewinding the input appropriately while it does) to find the nearest alternative path through the grammar. in other words, the parser does a depth-first, left-to-right search for the first successfully-matching path through the rules. and if it finds one, the actions along that successful path get executed, in the order they were encountered.

lowkey important: predicates are evaluated immediately during the search for a successful match, since they contribute to whether the search succeeds or fails. actions, though? actions are evaluated only after a successful match has been found. don't mix those up bestie 😭

---

🌈 PEG GRAMMAR FOR PEG GRAMMARS 🌈

so the grammar for peg grammars is right here below. it both illustrates and formalises everything we just said. very meta of it. 💅

Grammar         <- Spacing Definition+ EndOfFile

Definition      <- Identifier LEFTARROW Expression
Expression      <- Sequence ( SLASH Sequence )*
Sequence        <- Prefix*
Prefix          <- AND Action
                 / ( AND | NOT )? Suffix
Suffix          <- Primary ( QUERY / STAR / PLUS )?
Primary         <- Identifier !LEFTARROW
                 / OPEN Expression CLOSE
                 / Literal
                 / Class
                 / DOT
                 / Action
                 / BEGIN
                 / END

Identifier      <- < IdentStart IdentCont* > Spacing
IdentStart      <- [a-zA-Z_]
IdentCont       <- IdentStart / [0-9]
Literal         <- ['] < ( !['] Char  )* > ['] Spacing
                 / ["] < ( !["] Char  )* > ["] Spacing
Class           <- '[' < ( !']' Range )* > ']' Spacing
Range           <- Char '-' Char / Char
Char            <- '\\' [abefnrtv'"\[\]\\]
                 / '\\' [0-3][0-7][0-7]
                 / '\\' [0-7][0-7]?
                 / '\\' '-'
                 / !'\\' .
LEFTARROW       <- '<-' Spacing
SLASH           <- '/' Spacing
AND             <- '&' Spacing
NOT             <- '!' Spacing
QUERY           <- '?' Spacing
STAR            <- '*' Spacing
PLUS            <- '+' Spacing
OPEN            <- '(' Spacing
CLOSE           <- ')' Spacing
DOT             <- '.' Spacing
Spacing         <- ( Space / Comment )*
Comment         <- '#' ( !EndOfLine . )* EndOfLine
Space           <- ' ' / '\t' / EndOfLine
EndOfLine       <- '\r\n' / '\n' / '\r'
EndOfFile       <- !.
Action          <- '{' < [^}]* > '}' Spacing
BEGIN           <- '<' Spacing
END             <- '>' Spacing

🌈 LEG GRAMMARS 🌈

okay bestie, so leg is basically peg's cooler cousin that stole some features from lex(1) and yacc(1). Here's exactly how it differs from peg. no cap 💅

✨ %{ text... %} ✨

A declaration section can show up anywhere you'd normally expect a rule definition. The text between %{ and %} gets copied verbatim into the generated C parser code, right before the code that implements the parser itself. 💖

✨ name = pattern ✨

The assignment operator = replaces the left arrow operator <-. slay 💅

✨ rule-name ✨

Hyphens can appear as letters in rule names. Every hyphen gets converted into an underscore in the generated C source code. And a single hyphen - is a totally legal rule name. 🎀

    -       = [ \t\n\r]*
    number  = [0-9]+                 -
    name    = [a-zA-Z_][a-zA_Z_0-9]* -
    l-paren = '('                    -
    r-paren = ')'                    -

This example shows how ignored whitespace can be obvious when you're reading the grammar, yet unobtrusive when you sprinkle it liberally at the end of every rule tied to a lexical element. iykyk 💜

✨ seq-1 | seq-2 ✨

The alternation operator is the vertical bar |, not the forward slash /. So the peg rule

                  name <- sequence-1
                        / sequence-2
                        / sequence-3

is written like this in leg:

                  name = sequence-1
                       | sequence-2
                       | sequence-3
                       ;

And the final semicolon? optional, as we're about to spill. 🍑

✨ @{ action } ✨

Actions prefixed with an @ symbol get performed during parsing, right when they're encountered while matching the input text with a rule. But because PEG parsing backtracks, those @ actions might be performed multiple times for the same input text. 😭 (The usual behaviour of actions is that they're saved up until matching is complete, and then only the ones that are part of the final derivation get performed in left-to-right order.) The variable yytext is available inside these actions. 💖

✨ exp ~ { action } ✨

A postfix operator ~{ action } can be placed after any expression. It behaves like a normal action (arbitrary C code) except it's invoked only when exp fails. It binds less tightly than any other operator except alternation and sequencing, and it's meant to make error handling and recovery code easier to write. ⚠️ Note that yytext and yyleng are not available inside these actions, but the pointer variable yy is available to give the code access to any user-defined members of the parser state (see "CUSTOMISING THE PARSER" below). Also note that exp is always a single expression; to invoke an error action for any failure within a sequence, you must use parentheses to group that sequence into a single expression. 🫶

                  rule = e1 e2 e3 ~{ error("e[12] ok; e3 has failed"); }
                       | ...

                  rule = (e1 e2 e3) ~{ error("one of e[123] has failed"); }
                       | ...

✨ pattern ; ✨

A semicolon punctuator can optionally terminate a pattern. cute 💅

✨ %% text... ✨

A double percent %% terminates the rules (and declarations) section of the grammar. All text following %% gets copied verbatim into the generated C parser code after the parser implementation code. 🌈

✨ $$ = value ✨

A sub-rule can return a semantic value from an action by assigning it to the pseudo-variable $$. All semantic values must have the same type (which defaults to int). Wanna change that type? Define YYSTYPE in a declaration section. 👑

✨ identifier:name ✨

The semantic value returned (by assigning to $$) from the sub-rule name is associated with the identifier, and you can refer to it in subsequent actions. 💜

The desk calculator example below illustrates the use of $$ and :. periodt 💅

🧮 LEG EXAMPLE: A DESK CALCULATOR 🧮

The extensions in leg described above let useful parsers and evaluators (including declarations, grammar rules, and supporting C functions such as main) be kept within a single source file. To illustrate this, here's a simple desk calculator supporting the four common arithmetic operators and named variables. The intermediate results of arithmetic evaluation get accumulated on an implicit stack by returning them as semantic values from sub-rules. slay ✨

           %{
           #include <stdio.h>     /* printf() */
           #include <stdlib.h>    /* atoi() */
           int vars[26];
           %}

           Stmt    = - e:Expr EOL                  { printf("%d\n", e); }
                   | ( !EOL . )* EOL               { printf("error\n"); }

           Expr    = i:ID ASSIGN s:Sum             { $$ = vars[i] = s; }
                   | s:Sum                         { $$ = s; }

           Sum     = l:Product
                           ( PLUS  r:Product       { l += r; }
                           | MINUS r:Product       { l -= r; }
                           )*                      { $$ = l; }

           Product = l:Value
                           ( TIMES  r:Value        { l *= r; }
                           | DIVIDE r:Value        { l /= r; }
                           )*                      { $$ = l; }

           Value   = i:NUMBER                      { $$ = atoi(yytext); }
                   | i:ID !ASSIGN                  { $$ = vars[i]; }
                   | OPEN i:Expr CLOSE             { $$ = i; }

           NUMBER  = < [0-9]+ >    -               { $$ = atoi(yytext); }
           ID      = < [a-z]  >    -               { $$ = yytext[0] - 'a'; }
           ASSIGN  = '='           -
           PLUS    = '+'           -
           MINUS   = '-'           -
           TIMES   = '*'           -
           DIVIDE  = '/'           -
           OPEN    = '('           -
           CLOSE   = ')'           -

           -       = [ \t]*
           EOL     = '\n' | '\r\n' | '\r' | ';'

           %%

           int main()
           {
             while (yyparse())
               ;
             return 0;
           }

📜 LEG GRAMMAR FOR LEG GRAMMARS 📜

The grammar for leg grammars is shown below. This will both illustrate and formalise the above description. iconic 💜

           grammar =       -
                           ( declaration | definition )+
                           trailer? end-of-file

           declaration =   '%{' < ( !'%}' . )* > RPERCENT

           trailer =       '%%' < .* >

           definition =    identifier EQUAL expression SEMICOLON?

           expression =    sequence ( BAR sequence )*

           sequence =      error+

           error =         prefix ( TILDE action )?

           prefix =        AND action
           |               ( AND | NOT )? suffix

           suffix =        primary ( QUERY | STAR | PLUS )?

           primary =       identifier COLON identifier !EQUAL
           |               identifier !EQUAL
           |               OPEN expression CLOSE
           |               literal
           |               class
           |               DOT
           |               action
           |               BEGIN
           |               END

           identifier =    < [-a-zA-Z_][-a-zA-Z_0-9]* > -

           literal =       ['] < ( !['] char )* > ['] -
           |               ["] < ( !["] char )* > ["] -

           class =         '[' < ( !']' range )* > ']' -

           range =         char '-' char | char

           char =          '\\' [abefnrtv'"\[\]\\]
           |               '\\' [0-3][0-7][0-7]
           |               '\\' [0-7][0-7]?
           |               !'\\' .

           action =        '{' < braces* > '}' -

           braces =        '{' braces* '}'
           |               !'}' .

           EQUAL =         '=' -
           COLON =         ':' -
           SEMICOLON =     ';' -
           BAR =           '|' -
           AND =           '&' -
           NOT =           '!' -
           QUERY =         '?' -
           STAR =          '*' -
           PLUS =          '+' -
           OPEN =          '(' -
           CLOSE =         ')' -
           DOT =           '.' -
           BEGIN =         '<' -
           END =           '>' -
           TILDE =         '~' -
           RPERCENT =      '%}' -

           - =             ( space | comment )*
           space =         ' ' | '\t' | end-of-line
           comment =       '#' ( !end-of-line . )* end-of-line
           end-of-line =   '\r\n' | '\n' | '\r'
           end-of-file =   !.

💖 CUSTOMISING THE PARSER 💖

okay bestie, so sometimes the default parser just isn't giving what you need and you want to customise it, right? Well these symbols can be redefined in declaration sections to modify the generated parser code. Obsessed.

• YYSTYPE — this is the semantic value type, the whole vibe of your values. The pseudo-variable $$ and the identifiers bound to rule results with the colon operator : should all be considered as being declared to have this type. Default? It's int. classic.
• YYPARSE — the name of the main entry point to the parser. Default is yyparse. she's the main character fr.
• YYPARSEFROM — the name of an alternative entry point to the parser. This function expects one argument: the function corresponding to the rule from which the search for a match should begin. Default is yyparsefrom. Just so you know, yyparse() is defined as

int yyparse() { return yyparsefrom(yy_foo); }

where foo is the name of the first rule in the grammar. ✨

• YY_INPUT(buf, result, max_size) — this macro is invoked by the parser to obtain more input text. buf points to an area of memory that can hold at most max_size characters. The macro should copy input text to buf and then assign the integer variable result to indicate the number of characters copied. If no more input is available, the macro should assign 0 to result. By default, the YY_INPUT macro is defined as follows.

#define YY_INPUT(buf, result, max_size)        \
{                                              \
  int yyc= getchar();                          \
  result= (EOF == yyc) ? 0 : (*(buf)= yyc, 1); \
}

heads up 💀 — note that if YY_CTX_LOCAL is defined (see below) then an additional first argument, containing the parser context, is passed to YY_INPUT.

• YY_DEBUG — if this symbol is defined then additional code will be included in the parser that prints vast quantities of arcane information to the standard error while the parser is running. it's giving chaos but make it diagnostic 🌀
• YY_BEGIN — this macro is invoked to mark the start of input text that will be made available in actions as yytext. This corresponds to occurrences of < in the grammar. These are converted into predicates that are expected to succeed. The default definition

#define YY_BEGIN (yybegin= yypos, 1)

therefore saves the current input position and returns 1 (which is true) as the result of the predicate. slay.

• YY_END — this macro corresponds to > in the grammar. Again, it is a predicate so the default definition saves the input position before 'succeeding'.

#define YY_END (yyend= yypos, 1)

• YY_PARSE(T) — this macro declares the parser entry points (yyparse and yyparsefrom) to be of type T. The default definition

#define YY_PARSE(T) T

leaves yyparse() and yyparsefrom() with global visibility. If they should not be externally visible in other source files, this macro can be redefined to declare them static.

#define YY_PARSE(T) static T

• YY_CTX_LOCAL — if this symbol is defined during compilation of a generated parser then global parser state will be kept in a structure of type yycontext which can be declared as a local variable. This allows multiple instances of parsers to coexist and to be thread-safe. The parsing function yyparse() will be declared to expect a first argument of type yycontext *, an instance of the structure holding the global state for the parser. This instance must be allocated and initialised to zero by the client. A trivial but complete example is as follows.

#include <stdio.h>

#define YY_CTX_LOCAL

#include "the-generated-parser.peg.c"

int main()
{
  yycontext ctx;
  memset(&ctx, 0, sizeof(yycontext));
  while (yyparse(&ctx));
  return 0;
}

okay so this part is IMPORTANT 🚨 — note that if this symbol is undefined then the compiled parser will statically allocate its global state and will be neither reentrant nor thread-safe. Also note that the parser yycontext structure is initialised automatically the first time yyparse() is called; this structure must therefore be properly initialised to zero before the first call to yyparse().

• YY_CTX_MEMBERS — if YY_CTX_LOCAL is defined (see above) then the macro YY_CTX_MEMBERS can be defined to expand to any additional member field declarations that the client would like included in the declaration of the yycontext structure type. These additional members are otherwise ignored by the generated parser. The instance of yycontext associated with the currently-active parser is available within actions as the pointer variable yy. 💅
• YY_BUFFER_SIZE — the initial size of the text buffer, in bytes. The default is 1024 and the buffer size is doubled whenever required to meet demand during parsing. An application that typically parses much longer strings could increase this to avoid unnecessary buffer reallocation. glow up your buffer ✨
• YY_STACK_SIZE — the initial size of the variable and action stacks. The default is 128, which is doubled whenever required to meet demand during parsing. Applications that have deep call stacks with many local variables, or that perform many actions after a single successful match, could increase this to avoid unnecessary buffer reallocation.
• YY_MALLOC(YY, SIZE) — the memory allocator for all parser-related storage. The parameters are the current yycontext structure and the number of bytes to allocate. The default definition is: malloc(SIZE)
• YY_REALLOC(YY, PTR, SIZE) — the memory reallocator for dynamically-grown storage (such as text buffers and variable stacks). The parameters are the current yycontext structure, the previously-allocated storage, and the number of bytes to which that storage should be grown. The default definition is: realloc(PTR, SIZE)
• YY_FREE(YY, PTR) — the memory deallocator. The parameters are the current yycontext structure and the storage to deallocate. The default definition is: free(PTR)
• YYRELEASE — the name of the function that releases all resources held by a yycontext structure. The default value is yyrelease.

---

🌸 the variables you can use in actions 🌸

The following variables can be referred to within actions. (yes, inside your actions, they're all just... there for you 🫶)

• char *yybuf — this variable points to the parser's input buffer used to store input text that has not yet been matched.
• int yypos — this is the offset (in yybuf) of the next character to be matched and consumed.
• char *yytext — the most recent matched text delimited by < and > is stored in this variable.
• int yyleng — this variable indicates the number of characters in yytext.
• yycontext *yy — this variable points to the instance of yycontext associated with the currently-active parser.

Programs that wish to release all the resources associated with a parser can use the following function.

• yyrelease(yycontext*yy) — returns all parser-allocated storage associated with yy to the system. The storage will be reallocated on the next call to yyparse().

ngl this bit matters 😭 — note that the storage for the yycontext structure itself is never allocated or reclaimed implicitly. The application must allocate these structures in automatic storage, or use calloc() and free() to manage them explicitly. The example in the following section demonstrates one approach to resource management.

---

🦋 LEG EXAMPLE: EXTENDING THE PARSER'S CONTEXT 🦋

The yy variable passed to actions contains the state of the parser plus any additional fields defined by YY_CTX_MEMBERS. These fields can be used to store application-specific information that is global to a particular call of yyparse(). A trivial but complete leg example follows in which the yycontext structure is extended with a count of the number of newline characters seen in the input so far (the grammar otherwise consumes and ignores the entire input). The caller of yyparse() uses count to print the number of lines of input that were read. it's giving ✨custom state✨

%{
#define YY_CTX_LOCAL 1
#define YY_CTX_MEMBERS \
  int count;
%}

Char    = ('\n' | '\r\n' | '\r')        { yy->count++ }
        | .

%%

#include <stdio.h>
#include <string.h>

int main()
{
    /* create a local parser context in automatic storage */
    yycontext yy;
    /* the context *must* be initialised to zero before first use*/
    memset(&yy, 0, sizeof(yy));

    while (yyparse(&yy))
        ;
    printf("%d newlines\n", yy.count);

    /* release all resources associated with the context */
    yyrelease(&yy);

    return 0;
}

lowkey the most satisfying little loop ever, bestie 🌈

💅 DIAGNOSTICS 💅

ok so peg and leg will yell at you about these things while they're turning your grammar into a parser. bestie they are not subtle about it, and honestly? good. 😤

• syntax error — your input grammar was malformed somehow 🫠. The error message shows you the text that was about to be matched (which is often backed up, like, a huge amount from where the actual error is), plus the line number of the most recently considered character — and that line number is usually the real location of the problem. iykyk.
• rule 'foo' used but not defined — the grammar was like "yeah we're using a rule called 'foo'" and then never defined it. not it. If you actually try to use the generated parser you'll probably get errors from the linker, because of undefined symbols that go with the missing rule. 💀
• rule 'foo' defined but not used — the grammar defined a rule named 'foo' and then just… ignored it 🙈. The code for that rule still gets included in the generated parser, which is otherwise totally healthy. no cap, it's fine, just messy.
• possible infinite left recursion in rule 'foo' — there's at least one path through the grammar that goes from rule 'foo' back to a recursive invocation of the same rule without consuming any input. that's a loop, bestie, and loops don't end. 😭

Left recursion — especially the kind you find in standards documents — is often 'direct', and that means it's lowkey just trivial repetition.

# (6.7.6)
direct-abstract-declarator =
    LPAREN abstract-declarator RPAREN
|   direct-abstract-declarator? LBRACKET assign-expr? RBRACKET
|   direct-abstract-declarator? LBRACKET STAR RBRACKET
|   direct-abstract-declarator? LPAREN param-type-list? RPAREN

And the way you fix that recursion? So easy. You take the parts of the pattern that come after the recursion and turn them into a repeatable suffix. slay. ✨

# (6.7.6)
direct-abstract-declarator =
    direct-abstract-declarator-head?
    direct-abstract-declarator-tail*

direct-abstract-declarator-head =
    LPAREN abstract-declarator RPAREN

direct-abstract-declarator-tail =
    LBRACKET assign-expr? RBRACKET
|   LBRACKET STAR RBRACKET
|   LPAREN param-type-list? RPAREN

---

😭 CAVEATS 😭

🚨 okay this one is important, listen up: a parser that accepts empty input will ALWAYS succeed.

Look at this example. It's, like, not atypical of a first attempt at writing a PEG-based parser. we've all been there bestie.

Program = Expression*
Expression = "whatever"
%%
int main() {
  while (yyparse())
    puts("success!");
  return 0;
}

This program loops forever. Every time. No matter what input you give it on stdin — or even if you give it no input at all. it's giving infinite. it's giving no. 😭

Many fixes are possible, and the easiest one is to insist that the parser always consumes some non-empty input. So change that first line to:

Program = Expression+

and boom, done. 💅

And if you want the parser to consume the entire input? Then explicitly requiring the end-of-file is also highly recommended:

Program = Expression+ !.

Why does that work? Because the parser will only fail to match the "!" predicate on any character at all (that's the "." expression) when it tries to read beyond the end of the input. 🌸

---

🙈 BUGS 🙈

• You have to type man peg to read the manual page for leg(1). yes. for real. the leg page is hiding inside the peg page. iconic behaviour, honestly. 🎀
• The 'yy' and 'YY' prefixes cannot be changed.
• Left recursion is detected in the input grammar, but it is not handled correctly in the generated parser. 💀
• Diagnostics for errors in the input grammar are obscure and not particularly helpful. (we know. we said.) 🫠
• The operators ! and ~ should really be named the other way around. not me pointing this out in the manual. 🙈
• Several commonly-used lex(1) features (yywrap(), yyin, etc.) are completely absent. like, fully missing. gone.
• The generated parser does not contain '#line' directives to direct C compiler errors back to the grammar description when appropriate.

---

🦋 SEE ALSO 🦋

• D. Val Schorre, META II, a syntax-oriented compiler writing language, 19th ACM National Conference, 1964, pp. 41.301--41.311. Describes a self-implementing parser generator for analytic grammars with no backtracking.
• Alexander Birman, The TMG Recognition Schema, Ph.D. dissertation, Princeton, 1970. A mathematical treatment of the power and complexity of recursive-descent parsing with backtracking.
• Bryan Ford, Parsing Expression Grammars: A Recognition-Based Syntactic Foundation, ACM SIGPLAN Symposium on Principles of Programming Languages, 2004. Defines PEGs and analyses them in relation to context-free and regular grammars. Introduces the syntax adopted in peg.
• The standard Unix utilities lex(1) and yacc(1), which influenced the syntax and features of leg.
• The source code for peg and leg, whose grammar parsers are written using themselves. (they're self-hosting. main character energy. 👑)
• The latest version of this software and documentation:

http://piumarta.com/software/peg

---

🫶 AUTHOR 🫶

peg, leg and this manual page were written by Ian Piumarta (first-name at last-name dot com) while investigating the viability of regular and parsing-expression grammars for efficiently extracting type and signature information from C header files. yes, this whole thing came out of one very focused side quest. obsessed. ✨

Please send bug reports and suggestions for improvements to the author at the above address. they literally asked. 💜

---

and that's a wrap bestie 🎀 this was Version 0.1, dated September 2013, and it's the PEG(1) page — go write something iconic with it. mwah 💅🦋