MINIPEG(1)
💅 NAME 💅
minipeg — parser generator ✨
(yeah that's the whole vibe of MINIPEG(1), and honestly? iconic.)
🌸 SYNOPSIS 🌸
minipeg [-hvVP -ooutput] [filename ...]✨ DESCRIPTION ✨
okay so minipeg is a tool for generating recursive-descent parsers — and those are just programs that perform pattern matching on text, bestie, no big deal 🫶
It processes a Parsing Expression Grammar (PEG) [Ford 2004] to produce a program that recognises legal sentences of that grammar. It processes PEGs written with syntax and conventions that are intended to make it an attractive replacement for parsers built with lex(1) and yacc(1). Like, genuinely an upgrade, iykyk.
Unlike lex and yacc, minipeg supports unlimited backtracking, provides ordered choice as a means for disambiguation, and can combine scanning (lexical analysis) and parsing (syntactic analysis) into a single activity 😭🔥 the way it just does both jobs at once? main character energy fr fr.
So here's the flow, step by step 👑
minipegreads the specified filenames, or standard input if no filenames are given, looking for a grammar that describes the parser to generate.- Then it generates a C source file that defines a function
yyparse(). - That C source file can be included in, or compiled and then linked with, a client program.
- Every single time the client program calls
yyparse(), the parser consumes input text according to the parsing rules, starting from the first rule in the grammar. yyparse()returns non-zero if the input could be parsed according to the grammar. It returns zero if the input could not be parsed. That's it, that's the whole duality 💀
The prefix 'yy' or 'YY' is prepended to all externally-visible symbols in the generated parser. Why? To reduce the risk of namespace pollution in client programs, of course — we're protecting your namespace's peace 🙈. (The choice of 'yy' is historical; see lex(1) and yacc(1), for example. you already knew that though, right? iykyk.)
🎀 OPTIONS 🎀
minipeg provides the following options, and yes you need to know all of them, don't scroll:
-h— prints a summary of available options and then exits. cute little help menu, slay 💖-ooutput— writes the generated parser to the file output instead of the standard output.-P— suppresses#linedirectives in the output. bye bye line directives 👋-v— writes verbose information to standard error while working. it's giving narrator mode 🗣️-V— writes version information to standard error then exits.
🧚 EXAMPLE: A CALCULATOR 🧚
here for the actual demonstration? periodt. 🍓
So we're showing a simple desk calculator supporting the four common arithmetic operators and named variables. The intermediate results of arithmetic evaluation will be accumulated on an implicit stack by returning them as semantic values from sub-rules. yes bestie, semantic values, we're doing this properly 💅
%{
#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;
}If the above grammar is placed in the file calc.peg, running this command
$ minipeg -o calc.c calc.pegwill save the corresponding parser in the file calc.c. Then the program can be compiled with a C compiler and run 🎉
$ cc -o calc calc.c
$ ./calc
a=5
5
a+5
10like look at that output. a+5 → 10. she's calculating. she's iconic. 👑🔥
✨ MINIPEG GRAMMARS ✨
okay so a grammar is literally just a set of named rules, and one rule looks like this:
name = patternThe pattern is built from one or more of these elements, and yes every single one matters:
name— this element stands for the entire pattern in the rule with that given name. like, the whole vibe of that rule."characters"— a character or string inside double quotes is matched literally. ANSI C escape sequences are recognized inside those characters. periodt.'characters'— same literal-match situation, but with single quotes. escape characters recognized as above too.[characters]— a set of characters inside square brackets matches any single character from the set, with escape characters recognized as above. If the set begins with an uparrow (^), the set is negated, meaning the element matches any character not in the set. Any pair of characters separated with a dash (-) represents the range from the first to the second, inclusive. A single alphabetic character or underscore is matched by this following set:
[a-zA-Z_]Similarly, this next one matches any single non-digit character:
[^0-9].— a dot matches any character. note that the only time this fails is at the end of file, where there is no character to match. rude but true.( pattern )— parentheses are for grouping, aka modifying the precedence of the operators described below. iconic behavior.{ action }— curly braces surround actions. The action is arbitrary C source code to be executed at the end of matching. Any braces within the action must be properly nested. Any input text that was matched before the action and delimited by angle brackets (see below) is made available within the action as the contents of the character arrayyytext. The length of (number of characters in)yytextis available in the variableyyleng. These variable names are historical; seelex(1).@{ action }— actions prefixed with an "at" symbol will be performed during parsing, at the time they are encountered while matching the input text with a rule. Because of back-tracking in the PEG parsing algorithm, actions prefixed with@might be performed multiple times for the same input text. The usual behavior of actions is that they are saved up until matching is complete, and then those that are part of the final derivation are performed in left-to-right order. The variableyytextis available within these actions.exp ~ { action }— a postfix operator~{ action }can be placed after any expression and will behave like a normal action (arbitrary C code) except that it is invoked only whenexpfails. It binds less tightly than any other operator except alternation and sequencing, and is intended to make error handling and recovery code easier to write. Note thatyytextandyylengare not available inside these actions, but the pointer variableyyis available to give the code access to any user-defined members of the parser state (see "CUSTOMISING THE PARSER" below). Note also thatexpis always a single expression; to invoke an error action for any failure within a sequence, parentheses must be used to group the 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"); }
| ...<— an opening angle bracket always matches (consuming no input) and causes the parser to begin accumulating matched text. This text will be made available to actions in the variableyytext.>— a closing angle bracket always matches (consuming no input) and causes the parser to stop accumulating text foryytext.
The above elements can be made optional and/or repeatable with these suffixes:
element ?— the element is optional. If present on the input, it is consumed and the match succeeds. If not present on the input, no text is consumed and the match succeeds anyway.element +— the element is repeatable. If present on the input, one or more occurrences ofelementare consumed and the match succeeds. If no occurrences ofelementare present on the input, the match fails.element *— the element is optional and repeatable. If present on the input, one or more occurrences ofelementare consumed and the match succeeds. If no occurrences ofelementare present on the input, the match succeeds anyway.
The above elements and suffixes can be converted into predicates (that match arbitrary input text and subsequently succeed or fail without consuming that input) with these prefixes:
& element— the predicate succeeds only ifelementcan be matched. Input text scanned while matchingelementis not consumed from the input and remains available for subsequent matching.! element— the predicate succeeds only ifelementcannot be matched. Input text scanned while matchingelementis not consumed from the input and remains available for subsequent matching. A popular idiom is:
!.which matches the end of file, after the last character of the input has already been consumed.
A special form of the & predicate is provided:
&{ expression }— in this predicate the simple C expression (not statement) is evaluated immediately when the parser reaches the predicate. If the expression yields non-zero (true) the "match" succeeds and the parser continues with the next element in the pattern. If the expression yields zero (false) the "match" fails and the parser backs up to look for an alternative parse of the input.
Several elements (with or without prefixes and suffixes) can be combined into a sequence by writing them one after the other. The entire sequence matches only if each individual element within it matches, from left to right.
Sequences can be separated into disjoint alternatives by the alternation operator |.
sequence-1 | sequence-2 | ... | sequence-N— each sequence is tried in turn until one of them matches, at which time matching for the overall pattern succeeds. If none of the sequences matches then the match of the overall pattern fails.
The following elements can appear in addition to rules:
%{ text... %}— a declaration section can appear anywhere that a rule definition is expected. The text between the delimiters%{and%}is copied verbatim to the generated C parser code before the code that implements the parser itself.#— the pound sign introduces a comment (discarded) that continues until the end of the line. yes bestie, comments are free.%% text...— a double percent%%terminates the rules (and declarations) section of the grammar. All text following%%is copied verbatim to the generated C parser code after the parser implementation code.
Some notes regarding rules and patterns follow:
rule-name— hyphens can appear as letters in the names of rules. Each hyphen is converted into an underscore in the generated C source code. A single hyphen-is a legal rule name.
Within actions you can access and manipulate named values.
$$ = 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 toint). This type can be changed by definingYYSTYPEin a declaration section.identifier:name— the semantic value returned (by assigning to$$) from the sub-rulenameis associated with the identifier and can be referred to in subsequent actions.
🌈 MINIPEG GRAMMAR FOR MINIPEG GRAMMARS 🌈
The grammar for minipeg grammars is shown below. This will both illustrate and formalise the above description. like, here's the actual formal grammar, no cap:
grammar = -
( declaration | definition )+
trailer? end-of-file
declaration = '%{' < ( !'%}' . )* > RPERCENT
trailer = '%%' < .* >
definition = identifier EQUAL expression
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 = ':' -
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 = !.that's the whole formal grammar in all its glory 👑
✨ CUSTOMISING THE PARSER ✨
okay so this is the part where minipeg lets you remix the generated parser code itself 💅 the following symbols can be redefined in declaration sections to modify the generated parser code. no cap, this is the customization menu bestie.
YYSTYPE — the semantic value type. 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. The default value is int. ✨
YYPARSE — the name of the main entry point to the parser. The default value is yyparse.
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. The default is yyparsefrom. Note that 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); \
}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 symbols 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. 😭 so much lore dumped to stderr.
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 (true) as the result of the predicate.
YY_END — this macros 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) Tleaves 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 TYY_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;
}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. Note also 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.
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 following variables can be referred to within actions. 🫶
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 (inyybuf) 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 inyytext.yycontext *yy— this variable points to the instance ofyycontextassociated 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().
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. 💖
🌸 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. Theses 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. 🦋
%{
#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;
}💀 DIAGNOSTICS 💀
ok so while minipeg is busy converting your grammar into an actual parser, it might throw these warnings at you — bestie, listen to them:
syntax error— your input grammar was malformed somehow 😭. The error message will include the text that was about to be matched (which is often backed up a huge amount from where the error actually is) plus the line number of the most recently considered character (which is often the real location of the problem). iykyk.rule 'foo' used but not defined— your grammar referred to a rule named'foo'but never gave a definition for it 🙈. If you try to use the generated parser anyway, you'll likely get errors from the linker about undefined symbols associated with that missing rule. not cute.rule 'foo' defined but not used— your grammar defined a rule named'foo'and then just... ignored it 💅. The code for that rule still gets included in the generated parser, which will be perfectly healthy in every other respect. no harm, just messy.possible infinite left recursion in rule 'foo'— there's at least one path through the grammar that leads from the rule'foo'back to a recursive invocation of that same rule without consuming any input 🔥. that's the danger zone.
Left recursion — especially the kind that shows up in standards documents — is often direct and basically just means "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? RPARENThe way to fix it is genuinely so easy: take the parts of the pattern that come after the recursion and turn them into a repeatable suffix ✨
# (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 😭
ok important one: a parser that accepts empty input will always succeed. always. forever. think about that. Consider this example, which is honestly not atypical of a first attempt to write a PEG-based parser:
Program = Expression*
Expression = "whatever"
%%
int main() {
while (yyparse())
puts("success!");
return 0;
}This program loops forever — no matter what (if any) input is provided on stdin 💀💀💀. So many fixes are possible; the easiest being to insist that the parser always consumes some non-empty input. Change the first line to
Program = Expression+and boom, fixed 🫶. If your parser is expected to consume the entire input, then explicitly requiring the end-of-file is also highly recommended:
Program = Expression+ !.The way this works: the parser will only fail to match (that's the ! predicate) any character at all (that's the . expression) when it attempts to read beyond the end of the input 👑.
🐛 BUGS 🐛
- The
'yy'and'YY'prefixes cannot be changed. locked in. not up for discussion. - Left recursion is detected in the input grammar but is not handled correctly in the generated parser 😬.
- Diagnostics for errors in the input grammar are obscure and not particularly helpful. (understatement of the century ngl)
- The operators
!and~should really be named the other way around 🙃. - Several commonly-used
lex(1)features (yywrap(),yyin, etc.) are completely absent. gone. not invited to the party. - 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. vintage icon behavior.
- 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. math girlies rise 🧚
- 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. literal main character of this whole thing. - The standard Unix utilities
lex(1)andyacc(1)which influenced the syntax and features ofminipeg. the elders 💜 - The source code for
minipegwhose grammar parsers are written using themselves. yes, it ate and left no crumbs. self-hosting queen. - The latest version of this software and documentation:
https://ach.srht.site/minipeg🎀 AUTHOR 🎀
minipeg and this manual were originally written by Ian Piumarta under the project name peg/leg. minipeg is a fork of peg/leg by Andrew Chambers. slay, thank you for your service 🫡💖
ok that's the whole page bestie, you're officially a minipeg scholar 🎓✨ the footer's just MINIPEG(1) with its date doing its little sign-off thing, so like... that's the version and the day you're reading this, periodt 💅🌸
📦 where this page comes from
- alpine 3.24: minipeg-doc 0.1.18_git20221008-r0 · MIT
- 💖 girlified by deepseek-ai/DeepSeek-V4.1-Flash-1017 on : a language model's rewrite of the original, under its terms