cpp-peglib

C++17 header-only PEG (Parsing Expression Grammars) library. You can start using it right away just by including peglib.h in your project.

Since this library only supports C++17 compilers, please make sure that the compiler option -std=c++17 is enabled. (/std:c++17 /Zc:__cplusplus for MSVC)

You can also try the online version, PEG Playground at https://yhirose.github.io/cpp-peglib.

The PEG syntax is well described on page 2 in the document by Bryan Ford. cpp-peglib also supports the following additional syntax for now:

'...'i (Case-insensitive literal operator, ASCII letters)
[...]i (Case-insensitive character class operator, ASCII letters)
[^...] (Negated character class operator)
[^...]i (Case-insensitive negated character class operator, ASCII letters)
{2,5}, {2,}, {,5}, {2} (Regex-like repetition operator)
< ... > (Token boundary operator)
~ (Ignore operator)
\x20 (Hex number char: a byte in a literal, a code point in a character class)
\u10FFFF (Unicode char)
[\d\w\s], [\D\W\S] (Predefined character classes in a character class, ASCII semantics)
[[:alpha:]], [[:^alpha:]] (POSIX character classes in a character class, ASCII semantics: alnum, alpha, ascii, blank, cntrl, digit, graph, lower, print, punct, space, upper, word, xdigit)
%whitespace (Automatic whitespace skipping)
%word (Word expression)
$( ... ) (Capture scope operator)
$name< ... > (Named capture operator)
$name (Backreference operator)
| (Dictionary operator)
↑ (Cut operator)
MACRO_NAME( ... ) (Parameterized rule or Macro)
{ precedence L - + L / * } (Parsing infix expression)
Left recursive rules (direct, indirect, and mutual left recursion)
%recover( ... ) (Error recovery operator)
exp⇑label or exp^label (Syntax sugar for (exp / %recover(label)))
label { error_message "..." } (Error message instruction)
{ no_ast_opt } (No AST node optimization instruction)
{ no_whitespace } (Disable %whitespace skipping inside the rule)
{ ast_name: NodeTag } (AST node name override instruction)
← (Same as <-)

'End of Input' check will be done as default. To disable the check, please call disable_eoi_check.

This library supports Packrat parsing, which keeps backtracking from making the parse take time exponential in the input. It also supports left recursive grammars (direct, indirect, and mutual) via a seed-growing algorithm, allowing natural expression of left-associative operators.

Packrat parsing is turned on with enable_packrat_parsing. It remembers the result of a rule at a position and reuses it when the rule is tried there again, which takes memory that grows with the input, more so when the parse builds values or an AST. It remembers the rules that alternatives are likely to try again at one position, and one rule on every cycle of rules that call one another, which is what keeps backtracking from multiplying the time. It pays where a grammar often tries a rule again at one position, and can cost more than it saves where it seldom does, so measure with your own grammar and input. What it does not remember can be parsed again and again, which recursion can make exponential. It remembers nothing in the whitespace, and no rule at all if the whitespace may record or read a capture, or cut. It breaks no cycle on which every rule is a macro, or may record or read a capture, or cut the choice around it (with ↑ or a ^ label), itself or through the rules it calls. The operator of a precedence expression is parsed anew for its token. In the operand of ! and in a recovery's expression, where no error is reported, packrat parsing reuses what it remembered elsewhere but remembers nothing of a rule that is also parsed elsewhere.

A parser can be used from several threads at once, and parses on different threads may share one peg::parser. The callbacks the library calls, such as the ones set by set_logger, set_error_reporter and enable_trace, are called one at a time, so they may keep state of their own. The library does not protect what your code does: semantic actions run on the threads that parse, so any state they share between parses needs its own synchronization. Changing the parser while parses are running, such as its rules, options, callbacks or set_max_depth, is not safe. Set it up before the parses start.

IMPORTANT NOTE for some Linux distributions such as Ubuntu and CentOS: Need -pthread option when linking. See #23, #46 and #62.

I am sure that you will enjoy this excellent "Practical parsing with PEG and cpp-peglib" article by bert hubert!

How to use

This is a simple calculator sample. It shows how to define grammar, associate semantic actions to the grammar, and handle semantic values.

// (1) Include the header file
#include <peglib.h>
#include <assert.h>
#include <iostream>

using namespace peg;
using namespace std;

int main(void) {
  // (2) Make a parser
  parser parser(R"(
    # Grammar for Calculator...
    Additive    <- Multiplicative '+' Additive / Multiplicative
    Multiplicative   <- Primary '*' Multiplicative / Primary
    Primary     <- '(' Additive ')' / Number
    Number      <- < [0-9]+ >
    %whitespace <- [ \t]*
  )");

  assert(static_cast<bool>(parser) == true);

  // (3) Setup actions
  parser["Additive"] = [](const SemanticValues &vs) {
    switch (vs.choice()) {
    case 0: // "Multiplicative '+' Additive"
      return any_cast<int>(vs[0]) + any_cast<int>(vs[1]);
    default: // "Multiplicative"
      return any_cast<int>(vs[0]);
    }
  };

  parser["Multiplicative"] = [](const SemanticValues &vs) {
    switch (vs.choice()) {
    case 0: // "Primary '*' Multiplicative"
      return any_cast<int>(vs[0]) * any_cast<int>(vs[1]);
    default: // "Primary"
      return any_cast<int>(vs[0]);
    }
  };

  parser["Number"] = [](const SemanticValues &vs) {
    return vs.token_to_number<int>();
  };

  // (4) Parse
  parser.enable_packrat_parsing(); // Enable packrat parsing.

  int val;
  parser.parse(" (1 + 2) * 3 ", val);

  assert(val == 9);
}

To show syntax errors in grammar text:

auto grammar = R"(
  # Grammar for Calculator...
  Additive    <- Multiplicative '+' Additive / Multiplicative
  Multiplicative   <- Primary '*' Multiplicative / Primary
  Primary     <- '(' Additive ')' / Number
  Number      <- < [0-9]+ >
  %whitespace <- [ \t]*
)";

peg::parser parser;

parser.set_logger([](size_t line, size_t col, const string& msg, const string &rule) {
  cerr << line << ":" << col << ": " << msg << "\n";
});

auto ok = parser.load_grammar(grammar);
assert(ok);

A semantic action takes one of these forms, and can take vs as SemanticValues& instead, to move values out of it:

[](const SemanticValues& vs)
[](const SemanticValues& vs, any& dt)
[](const SemanticValues& vs, any& dt, const any& predicate_data)

SemanticValues value contains the following information:

Semantic values
Matched string information
Token information if the rule is literal or uses a token boundary operator
Choice number when the rule is 'prioritized choice'

any& dt is a 'read-write' context data which can be used for whatever purposes. The initial context data is set in peg::parser::parse method. It is the same in every callback, except in those of the rules under %word (see Word expression). predicate_data is what the rule's predicate passed on (see below).

A semantic action can return a value of arbitrary data type, which will be wrapped by std::any. An action that returns nothing gives an empty value. A rule without an action gives the first semantic value in vs. (Yacc parser has the same behavior.)

Here shows the SemanticValues structure:

struct SemanticValues : protected std::vector<any>
{
  // Input text
  const char* path;
  const char* ss;

  // Matched string
  std::string_view sv() const;

  // Name of the rule
  const std::string &name() const;

  // Tags (str2tag) of the rules the semantic values came from
  std::vector<unsigned int> tags;

  // Line number and column (in bytes) at which the matched string is
  std::pair<size_t, size_t> line_info() const;

  // Tokens
  std::vector<std::string_view> tokens;
  std::string_view token(size_t id = 0) const;

  // Token conversion
  std::string token_to_string(size_t id = 0) const;
  template <typename T> T token_to_number() const;

  // Number of alternatives and choice number (0 based index)
  size_t choice_count() const;
  size_t choice() const;

  // Transform the semantic value vector to another vector
  template <typename T> vector<T> transform(size_t beg = 0, size_t end = -1) const;
}

The following example uses < ... > operator, which is token boundary operator.

peg::parser parser(R"(
  ROOT  <- _ TOKEN (',' _ TOKEN)*
  TOKEN <- < [a-z0-9]+ > _
  _     <- [ \t\r\n]*
)");

parser["TOKEN"] = [](const SemanticValues& vs) {
  // 'token' doesn't include trailing whitespaces
  auto token = vs.token();
};

auto ret = parser.parse(" token1, token2 ");

We can ignore unnecessary semantic values from the list by using ~ operator.

peg::parser parser(R"(
  ROOT  <-  _ ITEM (',' _ ITEM _)*
  ITEM  <-  ([a-z0-9])+
  ~_    <-  [ \t]*
)");

parser["ROOT"] = [&](const SemanticValues& vs) {
  assert(vs.size() == 2); // should be 2 instead of 5.
};

auto ret = parser.parse(" item1, item2 ");

The following grammar is the same as the above.

peg::parser parser(R"(
  ROOT  <-  ~_ ITEM (',' ~_ ITEM ~_)*
  ITEM  <-  ([a-z0-9])+
  _     <-  [ \t]*
)");

Semantic predicate support is available with a predicate action.

peg::parser parser("NUMBER  <-  [0-9]+");

parser["NUMBER"] = [](const SemanticValues &vs) {
  return vs.token_to_number<long>();
};

parser["NUMBER"].predicate = [](const SemanticValues &vs,
                                const std::any & /*dt*/, std::string &msg) {
  if (vs.token_to_number<long>() != 100) {
    msg = "value error!!";
    return false;
  }
  return true;
};

long val;
auto ret = parser.parse("100", val);
assert(ret == true);
assert(val == 100);

ret = parser.parse("200", val);
assert(ret == false);

The message a predicate gives is reported where the rejected match starts, unless the parse fails further on (see Custom error message for definitions).

The predicate can pass data to the action via predicate_data to avoid redundant computation:

peg::parser parser("NUMBER  <-  < [0-9]+ >");

parser["NUMBER"].predicate = [](const SemanticValues &vs,
                                const std::any & /*dt*/, std::string &msg,
                                std::any &predicate_data) {
  int value;
  auto [ptr, err] = std::from_chars(
      vs.token().data(), vs.token().data() + vs.token().size(), value);
  if (err != std::errc()) {
    msg = "Number out of range.";
    return false;
  }
  predicate_data = value;
  return true;
};

parser["NUMBER"] = [](const SemanticValues & /*vs*/, std::any & /*dt*/,
                      const std::any &predicate_data) {
  return std::any_cast<int>(predicate_data);
};

enter and leave actions are also available.

parser["RULE"].enter = [](const Context &c, const char* s, size_t n, any& dt) {
  std::cout << "enter" << std::endl;
};

parser["RULE"] = [](const SemanticValues& vs, any& dt) {
  std::cout << "action!" << std::endl;
};

parser["RULE"].leave = [](const Context &c, const char* s, size_t n, size_t matchlen, any& value, any& dt) {
  std::cout << "leave" << std::endl;
};

Where the next byte cannot start a match of an alternative of a choice, the parser can skip the alternative instead of trying it, and then the enter and leave actions of the rules it would try there do not run, and nothing inside it does.

More generally, whether and how many times callbacks run in an attempt that is later abandoned is not fixed. This skipping leaves them out; packrat parsing can reuse a rule's earlier result at the same position, a match or a failure, instead of trying the rule again, so none of its callbacks run; and a left-recursive rule reuses its results even without packrat parsing, and tries its body once more after its match stops growing. So do not rely on what callbacks do in attempts that may be abandoned: undo in leave what enter did (such as opening a scope), or build the state from the value or the AST that the parse returns.

When an exception thrown by one of your callbacks leaves the parser, the leave actions of the rules it passes through do not run.

You can receive error information via a logger:

parser.set_logger([](size_t line, size_t col, const string& msg) {
  // ...
});

parser.set_logger([](size_t line, size_t col, const string& msg, const string &rule) {
  // ...
});

Ignoring Whitespaces

As you can see in the first example, we can ignore whitespaces between tokens automatically with %whitespace rule.

%whitespace rule skips leading spaces on text, and trailing spaces on tokens and on literal strings in rules (see the exact points below).

These are valid tokens:

KEYWORD   <- 'keyword'
KEYWORDI  <- 'case_insensitive_keyword'i
WORD      <-  < [a-zA-Z0-9] [a-zA-Z0-9-_]* >    # token boundary operator is used.
IDENT     <-  < IDENT_START_CHAR IDENT_CHAR* >  # token boundary operator is used.

The following grammar accepts one, "two three", four.

ROOT         <- ITEM (',' ITEM)*
ITEM         <- WORD / PHRASE
WORD         <- < [a-z]+ >
PHRASE       <- < '"' (!'"' .)* '"' >

%whitespace  <-  [ \t\r\n]*

How `%whitespace` works exactly

Whitespace is skipped at exactly these points, and nowhere else:

once at the beginning of the input text
right after every matched literal string ('...', "..."), dictionary ('...' | '...') and back reference ($name)
right after every closed token boundary (< ... >) and every match of a { no_whitespace } rule

Inside a token boundary, whitespace skipping is completely disabled. A rule used where no whitespace is skipped, in a token boundary, a { no_whitespace } rule or the whitespace itself, is parsed there apart from its uses elsewhere. Character classes ([...]) and . never skip whitespace by themselves. Knowing these rules explains most surprises with %whitespace:

A rule made only of character classes doesn't skip trailing whitespace. (#327) With the grammar below, main() parses but main () doesn't, because NAME is not a token, so nothing skips the space after it. Wrap lexical rules in a token boundary.

DECL    <- NAME ARGS?    # `main ()` fails: whitespace after NAME is not skipped
NAME    <- [a-zA-Z_][a-zA-Z0-9_]*
ARGS    <- '(' ')'

NAME    <- < [a-zA-Z_][a-zA-Z0-9_]* >   # OK: token boundary skips trailing whitespace

A literal skips whitespace before a following predicate sees the input. (#319) In KEYWORD <- "create" !IDCHAR, the literal "create" eats the whitespace after it, so !IDCHAR tests the character of the next word and the keyword check misfires on input like create a. Put the whole thing in a token boundary, or mark the rule with { no_whitespace }, to keep the predicate right next to the literal (peglint warns about this pattern):

KEYWORD <- < "create" !IDCHAR >
KEYWORD <- "create" !IDCHAR  { no_whitespace }

To preserve whitespace locally (e.g. inside string literals), mark the rule with the { no_whitespace } instruction: whitespace skipping is disabled inside the rule and resumes after it, like a token boundary without the token capture. (#44)

StrQuot   <- '"' (StrEscape / StrChars)* '"'  { no_whitespace }
StrEscape <- '\\' .
StrChars  <- (!'"' !'\\' .)+

The same can be written with nested token boundaries: the outer < ... > disables whitespace skipping for everything inside, and the inner one selects the text for token():

StrQuot   <- < '"' < (StrEscape / StrChars)* > '"' >

Rules whose name starts with _ are hidden from error messages. If you skip whitespace with rules of your own instead of %whitespace (e.g. to support comments), name them with a leading _, otherwise syntax errors report expecting <SPACE> instead of what the user actually needs to fix. What %whitespace fails to match while it is skipped is not listed among the expected tokens. Nothing in the operand of ! is reported either: Ident <- !Keyword < [a-z]+ > does not list the keywords, and a message or a recovery in it gives no error. (#292)

~_       <- (_SPACE / _COMMENT)*
_SPACE   <- [ \t\r\n]
_COMMENT <- '#' (!'\n' .)*

Keyword-like operators need %word. In a scannerless parser, 'and' happily matches the first three letters of android. Declare %word so literals that look like words are checked against a word boundary. (#328) See the next section.

Operators in precedence instructions must be literal tokens. When using the infix-expression precedence feature, write the operators as plain literals (optionally wrapped in a token boundary in the OPERATOR rule) rather than as rules that manage whitespace themselves. (#325)

Word expression

peg::parser parser(R"(
  ROOT         <-  'hello' 'world'
  %whitespace  <-  [ \t\r\n]*
  %word        <-  [a-z]+
)");

parser.parse("hello world"); // OK
parser.parse("helloworld");  // NG

A %word that can match the empty string, such as [a-z]*, is rejected.

A %word of the form [A] [B]* tells which characters start a word (A) and which go on one (B). A literal is checked as a word only if it starts with a character of A, and it does not match where a character of B follows it. Any other %word, such as [a-z], [a-z]+ or a reference to a rule, says both. A literal that ignores case ('if'i) is checked as a word if either case of its first character starts a word.

%word  <-  [a-zA-Z_] [a-zA-Z0-9_$]*   # 'AS' does not match in AS$x, and '$' is not a word literal

The parser checks %word apart from the rule that uses it, so a callback of the rules under %word gets no user data (dt is empty) and what it returns is thrown away. Whether a character is part of a word must depend on the input alone.

Capture/Backreference

peg::parser parser(R"(
  ROOT      <- CONTENT
  CONTENT   <- (ELEMENT / TEXT)*
  ELEMENT   <- $(STAG CONTENT ETAG)
  STAG      <- '<' $tag< TAG_NAME > '>'
  ETAG      <- '</' $tag '>'
  TAG_NAME  <- 'b' / 'u'
  TEXT      <- TEXT_DATA
  TEXT_DATA <- ![<] .
)");

parser.parse("This is <b>a <u>test</u> text</b>."); // OK
parser.parse("This is <b>a <u>test</b> text</u>."); // NG
parser.parse("This is <b>a <u>test text</b>.");     // NG

Dictionary

| operator allows us to make a word dictionary for fast lookup by using Trie structure internally. We don't have to worry about the order of words.

START <- 'This month is ' MONTH '.'
MONTH <- 'Jan' | 'January' | 'Feb' | 'February' | '...'

We are able to find which item is matched with choice().

parser["MONTH"] = [](const SemanticValues &vs) {
  auto id = vs.choice();
};

It supports the case-insensitive mode, which folds ASCII letters.

START <- 'This month is ' MONTH '.'
MONTH <- 'Jan'i | 'January'i | 'Feb'i | 'February'i | '...'i

Cut operator

↑ operator could mitigate the backtrack performance problem, but has a risk to change the meaning of grammar.

S <- '(' ↑ P ')' / '"' ↑ P '"' / P
P <- 'a' / 'b' / 'c'

When we parse (z with the above grammar, we don't have to backtrack in S after ( is matched, because a cut operator is inserted there.

A cut in a lookahead (& or !) commits no choice outside it, and neither does a recovery there.

Parameterized Rule or Macro

# Syntax
Start      ← _ Expr
Expr       ← Sum
Sum        ← List(Product, SumOpe)
Product    ← List(Value, ProOpe)
Value      ← Number / T('(') Expr T(')')

# Token
SumOpe     ← T('+' / '-')
ProOpe     ← T('*' / '/')
Number     ← T([0-9]+)
~_         ← [ \t\r\n]*

# Macro
List(I, D) ← I (D I)*
T(x)       ← < x > _

Parsing infix expression by Precedence climbing

Regarding the precedence climbing algorithm, please see this article.

peg::parser parser(R"(
  EXPRESSION             <-  INFIX_EXPRESSION(ATOM, OPERATOR)
  ATOM                   <-  NUMBER / '(' EXPRESSION ')'
  OPERATOR               <-  < [-+/*] >
  NUMBER                 <-  < '-'? [0-9]+ >
  %whitespace            <-  [ \t]*

  # Declare order of precedence
  INFIX_EXPRESSION(A, O) <-  A (O A)* {
    precedence
      L + -
      L * /
  }
)");

parser["INFIX_EXPRESSION"] = [](const SemanticValues& vs) -> long {
  auto result = any_cast<long>(vs[0]);
  if (vs.size() > 1) {
    auto ope = any_cast<char>(vs[1]);
    auto num = any_cast<long>(vs[2]);
    switch (ope) {
      case '+': result += num; break;
      case '-': result -= num; break;
      case '*': result *= num; break;
      case '/': result /= num; break;
    }
  }
  return result;
};
parser["OPERATOR"] = [](const SemanticValues& vs) { return *vs.sv().data(); };
parser["NUMBER"] = [](const SemanticValues& vs) { return vs.token_to_number<long>(); };

long val;
parser.parse(" -1 + (1 + 2) * 3 - -1", val);
assert(val == 9);

precedence instruction can be applied only to the following 'list' style rule.

Rule <- Atom (Operator Atom)* {
  precedence
    L - +
    L / *
    R ^
}

precedence instruction contains precedence info entries. Each entry starts with associativity which is 'L' (left) or 'R' (right), then operator literal tokens follow. The first entry binds the loosest, and each entry after it binds more tightly. An operator that contains L, R or }, such as OR, is quoted as '...' or "...".

Left Recursive Grammars

cpp-peglib supports left recursive rules, which are commonly used in expression grammars to achieve left-associative operators naturally. Left recursion is automatically detected at grammar compile time and handled via a seed-growing algorithm at parse time.

peg::parser parser(R"(
  Expr   <- Expr '+' Term / Expr '-' Term / Term
  Term   <- Term '*' Factor / Term '/' Factor / Factor
  Factor <- '(' Expr ')' / Number
  Number <- < [0-9]+ >
  %whitespace <- [ \t]*
)");

parser["Expr"] = [](const SemanticValues &vs) {
  switch (vs.choice()) {
  case 0: return any_cast<long>(vs[0]) + any_cast<long>(vs[1]);
  case 1: return any_cast<long>(vs[0]) - any_cast<long>(vs[1]);
  default: return any_cast<long>(vs[0]);
  }
};

parser["Term"] = [](const SemanticValues &vs) {
  switch (vs.choice()) {
  case 0: return any_cast<long>(vs[0]) * any_cast<long>(vs[1]);
  case 1: return any_cast<long>(vs[0]) / any_cast<long>(vs[1]);
  default: return any_cast<long>(vs[0]);
  }
};

parser["Number"] = [](const SemanticValues &vs) {
  return vs.token_to_number<long>();
};

long val;
parser.parse("1 - 2 - 3", val);
assert(val == -4);  // Left-associative: (1-2)-3 = -4

parser.parse("8 / 4 / 2", val);
assert(val == 1);   // Left-associative: (8/4)/2 = 1

Direct, indirect, and mutual left recursion are all supported. For example, indirect left recursion works as expected:

A <- B 'a'
B <- A 'b' / 'b'

A macro may also take part in the cycle. Each instantiation grows its own seed, so the same macro used with different arguments stays independent:

S      <- Sum(Digit) / Sum(Letter)
Sum(A) <- Sum(A) '+' A / A
Digit  <- [0-9]
Letter <- [a-z]

A plain macro is transparent to semantic values, but a left-recursive one forms its own scope: an action attached to it fires and its node appears in the AST, exactly as for the equivalent non-macro rule.

Whether a macro is left recursive is decided from its body alone, taking its parameters to consume input. Left recursion that only its arguments bring, as E brings to Pair(E, T) with E <- Pair(E, T) / T and Pair(A, B) <- A '+' B, leaves it transparent. Such an instantiation, entered again where it is being parsed, fails there instead of growing a seed: S <- Pair(E, T) matches 1+2 but not 1+2+3, which the equivalent non-macro rules match. A result there depends on what is being parsed around it, so once a rule or an instantiation is entered again where it is being parsed, packrat parsing stops for the rest of that parse.

Detection follows a chain of macros whose bodies call the next one 32 levels deep. Macros nested in arguments, as in Sum(Sum(Digit)), do not count toward it. Past that depth a rule is silently taken to be not left recursive, and its left-recursive alternative then fails instead of growing a seed.

A left-recursive macro whose own recursive call wraps its parameter in a larger expression, as in Sum(A) <- Sum(A / 'x') '+' A / A, grows no seed: it builds a new argument at every level, so no two levels share an instantiation and the seed memo never recognises the recursion. Each level calls the macro again at the same position, so the parse goes deeper until an alternative before the call matches, and overflows the stack and crashes if none does, unless set_max_depth makes it fail with an error first (see Limit nesting depth). Pass the parameter through unchanged (Sum(A)) in the recursive call; wrapping it is fine for a call to some other, non-left-recursive macro.

With %whitespace, a rule that calls itself inside its own token boundary, as Q <- < Q '.' I / I > does, grows only inside it, apart from its match outside (see How %whitespace works exactly), so Q matches a single I. Put the recursion in a rule of its own: Q <- < QBody > with QBody <- QBody '.' I / I. The same holds for a { no_whitespace } rule.

Left recursion support is enabled by default and adds zero overhead to non-left-recursive grammars. To disable it (reverting to the traditional error on left-recursive rules), call enable_left_recursion(false) before loading the grammar:

peg::parser parser;
parser.enable_left_recursion(false);
parser.load_grammar(grammar);

AST generation

cpp-peglib is able to generate an AST (Abstract Syntax Tree) when parsing. enable_ast method on peg::parser class enables the feature.

NOTE: An AST node holds a corresponding token as std::string_view for performance and less memory usage. It is users' responsibility to keep the original source text along with the generated AST tree.

peg::parser parser(R"(
  ...
  definition1 <- ... { no_ast_opt }
  definition2 <- ... { no_ast_opt }
  ...
)");

parser.enable_ast();

shared_ptr<peg::Ast> ast;
if (parser.parse("...", ast)) {
  cout << peg::ast_to_s(ast);

  ast = parser.optimize_ast(ast);
  cout << peg::ast_to_s(ast);
}

optimize_ast removes redundant nodes to make an AST simpler. If you want to disable this behavior from particular rules, no_ast_opt instruction can be used. Passing false as the second argument, opt_mode, reverses this: only the nodes of the no_ast_opt rules are removed.

If you only need the optimized AST, enable_ast(true) removes those nodes while parsing instead. It returns the same tree that optimize_ast would, and it is faster and uses much less memory on large inputs because the unoptimized tree is never kept. The second argument has the same meaning as the opt_mode argument of optimize_ast. Nodes built by your own semantic actions are left as they are.

parser.enable_ast(true);  // same AST as enable_ast() followed by optimize_ast()

A third argument lists the rules to use in place of those marked no_ast_opt, for the tree that AstOptimizer(opt_mode, rules) would return:

parser.enable_ast(true, true, {"ARGUMENTS", "BLOCK"});

A parse that uses packrat parsing or left recursion records the matches of AST rules, and builds their nodes only for the tree it returns and where a callback reads them: a predicate, a leave handler or an action of your own gets nodes as they would have been built as the rules matched. So the nodes of the alternatives such a parse abandons are mostly never built, but a node that a callback got can then be kept until the parse ends, even where the match it belongs to is abandoned. And where packrat parsing or left recursion reuses a node, changing its children (nodes) in a callback can make the returned tree differ from one built as the rules matched: a rule that collapses over the node can copy it with the change, and a child taken out of it can be copied instead of being renamed in place. Any other parse builds the node of each match as its rule matches.

A node's parent is guaranteed only once parser::parse has returned: until then, a node that packrat parsing or left recursion reuses can still point to a parent built for an alternative that was abandoned. Where packrat parsing reuses a node of an empty match under two parents, each gets a copy of its own, so such a node in the returned tree can be another object than the one an action or a leave handler saw.

A left-associative precedence operator or left recursion turns a long chain such as 1+2+3+... into a tree as deep as the chain is long. Parsing it and building and releasing its tree take no recursion that deep, but optimize_ast and ast_to_s walk the tree recursively, as your own code may, and can overflow the stack on a deep enough tree, sooner in a thread with a smaller stack. For such input, use enable_ast(true) rather than optimize_ast, and set_max_depth to make a parse fail on a tree deeper than the code that walks it can take (see Limit nesting depth). ast_to_s indents each node by its depth, so on such a chain its output grows with the square of the chain's length.

With enable_ast, a parse fails with an error on an input of 4 GiB or more.

By default an AST node carries the name of the rule that produced it. A rule can override that tag with the { ast_name: NodeTag } instruction, so several rules can emit nodes under a shared tag.

Multiple instructions can be combined in a single { ... } block by separating them with ;, e.g. { no_ast_opt; ast_name: NodeTag }.

It internally calls peg::AstOptimizer to do the job. You can make your own AST optimizers to fit your needs.

Each AST node exposes the following fields:

const std::string      path;     // the path given to parse
const size_t           line, column; // column in bytes
size_t                 position, length; // in bytes
const std::string      name;     // rule (or ast_name) that produced the node
const unsigned int     tag;      // str2tag(name), for fast switch dispatch
const size_t           choice_count, choice; // which alternative of a prioritized choice matched
std::string            original_name; // the node's name before AST optimization
unsigned int           original_tag;
size_t                 original_choice_count, original_choice;
const bool             is_token;
const std::string_view token;    // matched text (valid when is_token is true)
std::vector<std::shared_ptr<Ast>> nodes;  // child nodes
std::weak_ptr<Ast>     parent;

std::string token_to_string() const;
template <typename T> T token_to_number() const;

To walk the tree, switching on tag avoids string comparison. The _ literal in peg::udl turns a node name into the same compile-time tag value:

using namespace peg::udl;

void traverse(const std::shared_ptr<peg::Ast> &ast) {
  switch (ast->tag) {
  case "Additive"_: /* ... */ break;
  case "Number"_:   /* ... */ break;
  default:
    for (auto &node : ast->nodes) { traverse(node); }
    break;
  }
}

See actual usages in the AST calculator example and PL/0 language example.

Make a parser with parser combinators

Instead of making a parser by parsing PEG syntax text, we can also construct a parser by hand with parser combinators. Here is an example:

using namespace peg;
using namespace std;

vector<string> tags;

Definition ROOT, TAG_NAME, _;
ROOT     <= seq(_, zom(seq(chr('['), TAG_NAME, chr(']'), _)));
TAG_NAME <= oom(seq(npd(chr(']')), dot())), [&](const SemanticValues& vs) {
              tags.push_back(vs.token_to_string());
            };
_        <= zom(cls(" \t"));

auto ret = ROOT.parse(" [tag1] [tag:2] [tag-3] ");

The following are available operators:

Operator	Description	Operator	Description
seq	Sequence	cho	Prioritized Choice
zom	Zero or More	oom	One or More
opt	Optional	apd	And predicate
npd	Not predicate	lit	Literal string
liti	Case-insensitive Literal string	cls	Character class
ncls	Negated Character class	chr	Character
dot	Any character	tok	Token boundary
ign	Ignore semantic value	csc	Capture scope
cap	Capture	bkr	Back reference
dic	Dictionary	pre	Infix expression
rec	Error recovery	usr	User defined parser
rep	Repetition	ref	Rule reference
wsp	Whitespace	cut	Cut

Adjust definitions

It's possible to add/override definitions.

auto syntax = R"(
  ROOT <- _ 'Hello' _ NAME '!' _
)";

Rules additional_rules = {
  {
    "NAME", usr([](const char* s, size_t n) -> size_t {
      static vector<string> names = { "PEG", "BNF" };
      for (const auto& name: names) {
        if (name.size() <= n && !name.compare(0, name.size(), s, name.size())) {
          return name.size(); // processed length
        }
      }
      return -1; // parse error
    })
  },
  {
    "~_", zom(cls(" \t\r\n"))
  }
};

peg::parser g(syntax, additional_rules);

assert(g.parse(" Hello BNF! "));

The function given to usr gets the input from the current position, s, and its length, n, and returns the length it matches, or -1 where it does not match, which a syntax error lists like any other failure. It can also take the user data given to parse, as (const char* s, size_t n, any& dt), or the semantic values of its rule as well, as (const char* s, size_t n, SemanticValues& vs, any& dt), to read the values parsed before it in the rule and to add values of its own. Taking vs costs time: a grammar with such a function builds every value as it parses, even those that nothing reads. The parser can reuse what the function returned at a position, or call it there again, so the result must depend only on the input and on user data that does not change during the parse. The parser cannot tell what the function's match starts with, so it tries the function wherever the rule is reached: a lookahead before it, such as &[PB] NAME, keeps it from being tried elsewhere.

Unicode support

cpp-peglib accepts UTF8 text. . matches a Unicode codepoint. Also, it supports \u followed by four to six hex digits, up to \u10FFFF. Bytes that are not well-formed UTF-8 match neither . nor a character class, negated or not, and errors count each such byte as one column.

Columns are counted in two ways. Errors, the ones passed to the logger and to the error reporter, count col in Unicode codepoints from the start of the line, as a text editor does. Matches count it in bytes: the column of SemanticValues::line_info() and the column of an AST node. The position of an ErrorReport and of an AST node is a byte offset in the input in both cases.

Error report and recovery

cpp-peglib supports the furthest failure error position report as described in the Bryan Ford original document.

The message lists what every failure at that position expected, each once, in the order the parser first tried them. What %whitespace fails to match while it is skipped, and what the operand of ! fails to match, count as failures for neither the position nor the list. A literal is listed as its text. Any other failure is listed under the name of the outermost token rule it is in, or else of its own rule. Where packrat parsing or left recursion reuses a rule's earlier match or failure at the same position instead of trying the rule again, the reused result lists what trying the rule there would. This does not hold across a recovery that reports a custom message (see below): a result reused after the recovery reported an error lists none of its failures from before the report.

For better error report and recovery, cpp-peglib supports 'recovery' operator with label which can be associated with a recovery expression and a custom error message. This idea comes from the fantastic "Syntax Error Recovery in Parsing Expression Grammars" paper by Sergio Medeiros and Fabio Mascarenhas.

The custom message supports %t which is a placeholder for the unexpected token, and %c for the unexpected Unicode char. It can also reference a named capture with %{name}, which expands to the text captured by $name<...> earlier in the parse (an unknown name expands to an empty string):

Enum       <- 'enum' $name<NAME> '{' NAME+^enum_count '}'
enum_count <- '' { error_message "enum '%{name}' must contain at least one member" }

Here is an example of Java-like grammar:

# java.peg
Prog        ← 'public' 'class' NAME '{' 'public' 'static' 'void' 'main' '(' 'String' '[' ']' NAME ')' BlockStmt '}'
BlockStmt   ← '{' (!'}' Stmt^stmtb)* '}' # Annotated with `stmtb`
Stmt        ← IfStmt / WhileStmt / PrintStmt / DecStmt / AssignStmt / BlockStmt
IfStmt      ← 'if' '(' Exp ')' Stmt ('else' Stmt)?
WhileStmt   ← 'while' '(' Exp^condw ')' Stmt # Annotated with `condw`
DecStmt     ← 'int' NAME ('=' Exp)? ';'^semid # Annotated with `semid`
AssignStmt  ← NAME '=' Exp ';'^semia # Annotated with `semia`
PrintStmt   ← 'System.out.println' '(' Exp ')' ';'
Exp         ← RelExp ('==' RelExp)*
RelExp      ← AddExp ('<' AddExp)*
AddExp      ← MulExp (('+' / '-') MulExp)*
MulExp      ← AtomExp (('*' / '/') AtomExp)*
AtomExp     ← '(' Exp ')' / NUMBER / NAME

NUMBER      ← < [0-9]+ >
NAME        ← < [a-zA-Z_][a-zA-Z_0-9]* >

%whitespace ← [ \t\n]*
%word       ← NAME

# Recovery operator labels
semia       ← StmtRest { error_message "missing semicolon in assignment." }
semid       ← StmtRest { error_message "missing semicolon in declaration." }
stmtb       ← (';' / Skip StmtRest) { error_message "invalid statement" }
condw       ← &'==' ('==' RelExp)* / &'<' ('<' AddExp)* / (!')' .)*

# Recovery expressions
StmtRest    ← (!(';' / StmtKey) Skip)* ';'?
StmtKey     ← 'if' / 'while' / 'System.out.println' / 'int' / 'else' / '}'
Skip        ← '{' (!'}' Skip)* '}'? / NAME / NUMBER / .

For instance, ';'^semia is a syntactic sugar for (';' / %recover(semia)). Where ';' fails, %recover reports the custom message of semia, "missing semicolon in assignment.", and then recovers by skipping input text with the recovery expression semia. semia and semid skip the rest of the statement, and stmtb an invalid one: StmtRest stops after ;, or before } or a keyword that starts a statement, and skips a block in braces as one piece, so that an unbalanced brace is still reported. A recovery expression that stops where a rule such as Stmt matches can stop in the middle of the statement it skips, and report the rest of it as another error; one that stops at the tokens that end or start a statement does not. Where backtracking parses a rule again at the same position, its recoveries skip the same text again but report nothing more. The callbacks of the rules a recovery expression uses run again with it, and get the user data of the parse.

Here is the result:

> cat sample.java
public class Example {
  public static void main(String[] args) {
    int n = 5;
    int f = 1;
    while( < n) {
      f = f * n;
      n = n - 1
    };
    System.out.println(f);
  }
}

> peglint java.peg sample.java
sample.java:5:12: syntax error, unexpected '<', expecting '(', <NUMBER>, <NAME>.
sample.java:8:5: missing semicolon in assignment.
sample.java:8:6: invalid statement

As you can see, it can now show more than one error, and provide more meaningful error messages than the default messages.

Custom error message for definitions

We can associate custom error messages to definitions.

# custom_message.peg
START       <- CODE (',' CODE)*
CODE        <- < '0x' [a-fA-F0-9]+ > { error_message 'code format error...' }
%whitespace <- [ \t]*

> cat custom_message.txt
0x1234,0x@@@@,0xABCD

> peglint custom_message.peg custom_message.txt
custom_message.txt:1:8: code format error...

A definition's message stands for its failure where that failure is the error: when the parse fails further on, or an alternative tried before it went further, the error there is reported instead. A rule tried wherever whitespace may be fails at nearly every position, so no definition in %whitespace gives a message. To report an unterminated comment, give the comment rule a recovery label instead, which reports wherever whitespace is skipped, in %whitespace or in a rule of your own:

Comment      <- '/*' (!'*/' .)* '*/'^unterminated
unterminated <- '' { error_message "unterminated comment" }

NOTE: If there is more than one element with an error message instruction in a prioritized choice, this feature may not work as you expect.

Structured error reports

set_logger receives errors as formatted strings. To build tooling on top of the parser (error codes, localized messages, IDE diagnostics), use set_error_reporter instead, which receives the same errors as structured data before they are flattened into a display string:

parser.set_error_reporter([](const peg::ErrorReport &r) {
  // r.line, r.col          : 1-based error position
  // r.position             : byte offset in the input
  // r.unexpected_token     : the token found at the error position
  // r.expected_literals    : e.g. {"}", ";"}
  // r.expected_rules       : e.g. {"NAME"} (rules starting with '_' excluded)
  // r.message              : custom error_message if any (placeholders resolved)
  // r.label                : rule name or recovery label the error belongs to
});

Both callbacks can be set at the same time; each error is delivered to both. With error recovery, the reporter is called once per recovered error, so a single parse can produce multiple reports. Mapping r.label to an application-defined error enum is the intended way to get typed errors. An error that a recovery reports is labeled with its recovery label, whether or not the label has an error_message.

Limit nesting depth

The parser descends one level of C++ recursion for each rule it enters, and for the right operand of each operator a precedence rule parses, so deeply nested input, such as a few thousand (s, can overflow the stack and crash. set_max_depth makes such a parse fail with an error instead:

parser.set_max_depth(1000);

std::string deeply_nested_input(5000, '(');
parser.parse(deeply_nested_input); // false
// exceeded the maximum nesting depth of 1000

The depth counts the rule matches in progress at once, including macros and the rules %whitespace refers to, and the right operands a precedence rule is parsing: a chain of right-associative operators, such as 1^2^3 with R ^, nests one level per operator. One level of nesting in the input usually passes through several rules, so the limit is in rules, not in brackets. Only the rules the parser enters count: an alternative or a rule skipped because the next byte cannot start it enters none, and the rules entered are the same whether or not errors are reported. A tracer, which enable_trace and enable_profiling set, enters those rules to show them, so with one the limit can be reached a few levels sooner. How deep is safe depends on the grammar and on the stack size of the thread that parses.

Reaching the limit abandons the whole parse. The parser does not backtrack to try another alternative, no more actions, predicates or leave handlers run, and the error is reported at the position where the limit was reached, with the rule entered there (or the precedence rule, for a right operand) as its label. There is no limit by default.

An AST can be deeper than the parse nested: a left-associative precedence operator and left recursion fold a chain such as 1+2+3 in a loop into a tree as deep as the chain is long, and packrat parsing reuses a subtree wherever it matches again. So when parse returns an AST, the tree is held to the limit too. A tree that goes past it is not returned: the parse fails with the same error, reported at the first node past the limit, with that node's name as its label. Checking the tree takes one more walk over it after the parse, whose cost grows with the number of nodes, so it costs more with enable_ast() than with enable_ast(true), which keeps fewer nodes.

Change the Start Definition Rule

We can change the start definition rule as below.

auto grammar = R"(
  Start       <- A
  A           <- B (',' B)*
  B           <- '[one]' / '[two]'
  %whitespace <- [ \t\n]*
)";

peg::parser parser(grammar, "A"); // Start Rule is "A"

or

peg::parser parser;
parser.load_grammar(grammar, "A"); // Start Rule is "A"

parser.parse(" [one] , [two] "); // OK

Tracing the parser

To see how the parser proceeds, peg::enable_tracing prints a trace of the rules and operators the parser tries to the given output stream.

peg::parser parser(grammar);

peg::enable_tracing(parser, std::cout);

parser.parse(" [one] , [two] ");

This is what peglint --trace uses internally. For full control over the trace output, call parser.enable_trace(enter, leave) with your own callbacks, and parser.set_verbose_trace(true) to also trace what is left out by default: skipping whitespace, the inside of a token boundary, %word checks and the rules defined with ~, such as ~_ <- ....

Similarly, peg::enable_profiling(parser, std::cout) reports how many times each rule that the trace shows succeeds and fails, and how long the parse takes, as peglint --profile does.

peglint - PEG syntax lint utility

Build peglint

> cd lint
> mkdir build
> cd build
> cmake ..
> make
> ./peglint
usage: grammar_file_path [source_file_path]

  options:
    --source: source text
    --packrat: enable packrat memoise
    --ast: show AST tree
    --opt, --opt-all: optimize all AST nodes except nodes selected with `no_ast_opt` instruction
    --opt-only: optimize only AST nodes selected with `no_ast_opt` instruction
    --trace: show concise trace messages
    --profile: show profile report
    --verbose: verbose output for trace and profile
    --hints: show hints to make parsing faster
    --blob: write a serialized grammar blob to stdout (load it later with
            peg::parser::load_blob to skip the meta-parse on startup)
    --external NAME: take NAME as a rule the application gives as a `usr`
            operator; --blob stores it by name only, and a parse of the
            source fails where it is reached
    --version: show version information

Grammar check

> cat a.peg
Additive    <- Multiplicative '+' Additive / Multiplicative
Multiplicative   <- Primary '*' Multiplicative / Primary
Primary     <- '(' Additive ')' / Number
%whitespace <- [ \t\r\n]*

> peglint a.peg
a.peg:3:35: 'Number' is not defined.

--hints also shows what can make parsing slow, such as alternatives that start with the same rule, which without packrat parsing can be parsed again at the same position.

Source check

> cat a.peg
Additive    <- Multiplicative '+' Additive / Multiplicative
Multiplicative   <- Primary '*' Multiplicative / Primary
Primary     <- '(' Additive ')' / Number
Number      <- < [0-9]+ >
%whitespace <- [ \t\r\n]*

> peglint --source "1 + a * 3" a.peg
[commandline]:1:5: syntax error, unexpected 'a', expecting '(', <Number>.

Serialize a grammar for fast startup

A compiled grammar can be serialized to a portable byte blob and later restored without re-running the meta-parse. Deserializing a blob is much faster than load_grammar, so an application can embed a prebuilt blob and skip the grammar parsing on startup.

peg::parser parser(R"(
  ROOT <- _ TOKEN (',' _ TOKEN)*
  ...
)");

// Serialize the loaded grammar to a byte blob.
std::vector<uint8_t> blob = parser.serialize_grammar();

// ...store/embed the blob, then later:

peg::parser parser2;
parser2.load_blob(blob); // skips the meta-parse

// Re-apply semantic actions / enable_ast() etc. as needed:
parser2["TOKEN"] = [](const SemanticValues& vs) { /* ... */ };

Notes:

Only the grammar structure is serialized. Semantic actions, enable_ast(), and other callbacks are not included and must be re-applied after load_blob.
First-sets are recomputed on load, and references are resolved by name.
A rule whose whole body is a usr operator, such as one given in Adjust definitions, is stored by name only, since its body is code. Give the same rules again to load_blob(blob, rules), as below.
Grammars that use a named capture ($name<...>) or a usr operator inside a rule body are not serializable (serialize_grammar() throws).
load_blob() returns false on a bad or incompatible blob, or when rules lacks a rule the blob stores by name or gives it as other than a usr operator, and passes the reason to the logger set with set_logger.

Rules rules = {
  {"NAME", usr([](const char* s, size_t n) -> size_t {
    return n >= 3 && !strncmp(s, "PEG", 3) ? 3 : -1;
  })},
};
peg::parser parser("ROOT <- 'Hello ' NAME", rules);
auto blob = parser.serialize_grammar(); // NAME is stored by name only

peg::parser parser2;
parser2.load_blob(blob, rules); // takes the body of NAME from rules

peglint can emit a blob with the --blob option:

> peglint --blob a.peg > a.blob

A rule that the application gives as a usr operator is named with --external, so that peglint loads the grammar without that rule's body:

# b.peg
ROOT <- 'Hello ' NAME

> peglint --blob b.peg > b.blob
b.peg:2:18: 'NAME' is not defined.
> peglint --blob --external NAME b.peg > b.blob

AST

> cat a.txt
1 + 2 * 3

> peglint --ast a.peg a.txt
+ Additive/0
  + Multiplicative/1
    + Primary/1
      - Number (1)
  + Additive/1
    + Multiplicative/0
      + Primary/1
        - Number (2)
      + Multiplicative/1
        + Primary/1
          - Number (3)

AST optimization

> peglint --ast --opt --source "1 + 2 * 3" a.peg
+ Additive/0
  - Multiplicative/1[Number] (1)
  + Additive/1[Multiplicative]
    - Primary/1[Number] (2)
    - Multiplicative/1[Number] (3)

Rule/1 tells which alternative of the rule's choice matched, counting from 0, and Rule[Other] that the optimization put a node of Other in place of the node of Rule.

Adjust AST optimization with `no_ast_opt` instruction

> cat a.peg
Additive    <- Multiplicative '+' Additive / Multiplicative
Multiplicative   <- Primary '*' Multiplicative / Primary
Primary     <- '(' Additive ')' / Number          { no_ast_opt }
Number      <- < [0-9]+ >
%whitespace <- [ \t\r\n]*

> peglint --ast --opt --source "1 + 2 * 3" a.peg
+ Additive/0
  + Multiplicative/1[Primary]
    - Number (1)
  + Additive/1[Multiplicative]
    + Primary/1
      - Number (2)
    + Multiplicative/1[Primary]
      - Number (3)

> peglint --ast --opt-only --source "1 + 2 * 3" a.peg
+ Additive/0
  + Multiplicative/1
    - Primary/1[Number] (1)
  + Additive/1
    + Multiplicative/0
      - Primary/1[Number] (2)
      + Multiplicative/1
        - Primary/1[Number] (3)

Override an AST node's tag with `ast_name` instruction

By default, an AST node carries the name of the rule that produced it. A rule annotated { ast_name: NodeTag } emits its node under NodeTag instead. This lets two parallel productions converge onto a single AST tag, so a tree-walker needs only one case per logical nonterminal:

> cat a.peg
Atom        <- Number / String
Number      <- < [0-9]+ >          { ast_name: Literal }
String      <- '"' < [^"]* > '"'   { ast_name: Literal }
%whitespace <- [ \t\r\n]*

> peglint --ast --source "123" a.peg
+ Atom/0
  - Literal (123)

> peglint --ast --source "\"hi\"" a.peg
+ Atom/1
  - Literal (hi)

The override also works on parameterized rules (macros): each instantiation emits the same tag. ast_name composes with no_ast_opt: the AST optimizer's keep-list honors the overridden name.

Name		Name	Last commit message	Last commit date
.github/workflows		.github/workflows
abi		abi
benchmark		benchmark
docs		docs
example		example
grammar		grammar
lint		lint
pl0		pl0
scripts		scripts
test		test
.clang-format		.clang-format
.gitignore		.gitignore
.pre-commit-config.yaml		.pre-commit-config.yaml
CMakeLists.txt		CMakeLists.txt
LICENSE		LICENSE
README.md		README.md
justfile		justfile
peg.vim		peg.vim
peglib.h		peglib.h

Latest commit

History

Folders and files

Repository files navigation

cpp-peglib

How to use

Ignoring Whitespaces

How %whitespace works exactly

Word expression

Capture/Backreference

Dictionary

Cut operator

Parameterized Rule or Macro

Parsing infix expression by Precedence climbing

Left Recursive Grammars

AST generation

Make a parser with parser combinators

Adjust definitions

Unicode support

Error report and recovery

Custom error message for definitions

Structured error reports

Limit nesting depth

Change the Start Definition Rule

Tracing the parser

peglint - PEG syntax lint utility

Build peglint

Grammar check

Source check

Serialize a grammar for fast startup

AST

AST optimization

Adjust AST optimization with no_ast_opt instruction

Override an AST node's tag with ast_name instruction

Sample codes

Programming languages using cpp-peglib

License

About

Topics

Resources

Stars

Watchers

Forks

Releases

Used by

Contributors

Languages

How `%whitespace` works exactly

Adjust AST optimization with `no_ast_opt` instruction

Override an AST node's tag with `ast_name` instruction