pratt: Pratt parsing for C++

Pratt names the three answers of a token:

The engine’s whole algorithm is one function, expression(rbp). It reads a token and calls its nud; then, as long as the next token’s lbp is greater than rbp, it reads that token and calls its led with what it has parsed so far. A nud or a led that needs an operand calls expression again, with the binding power of its own operator, so the recursion stops at the first operator that binds less tightly. A * that asks for its right operand with its power, 20, stops before a + of power 10, which then takes the product as its left operand: precedence is that comparison of two numbers.

One token can have both denotations, as - has, and its nud and its led are two functions that never meet. That is what makes Pratt parsing fit the languages people write, where the same character is a sign, an operator, a grouping or a call, depending on where it stands.

This program parses integers of one digit with a unary minus and the binary +, - and *, and computes their values while it parses. It begins with the engine’s header and an alias for its namespace:

The engine reads tokens from a token stream: here, the characters of a text, each one a token, with '\0' once the text is spent. peek shows the next token, advance consumes it, and at_end says whether anything is left:

The grammar answers the three questions. Its node_type, what a parse builds, is int, since this grammar computes as it goes. lbp gives + and - the power 10 and * the power 20. The nud of a digit is its value, and the nud of - asks the parser for an operand with the power 30, above every binary operator, so that the minus takes only the next number. The led of a binary operator asks for the right operand with the operator’s own power, then combines the two:

pratt::parse parses a whole input with a grammar, and returns a pratt::result<int>, the value or the error:

It prints:

1+2*3 and 2*3+4 both multiply first, whatever their order, since * binds more tightly than +. 8-2-1 is 5, (8-2)-1, because the led of the first - asks for its right operand with the power 10, and the second -, of the same power, is not greater, so it ends that operand and takes 8-2 as its own left one: an operator that asks with its own power is left-associative. -2*3 negates only the 2, as the minus asks with 30. The last three fail, each with an error of pratt’s: the input ends where an operand was due, a * stands where no nud has a meaning for it, and the 2 of 12, a second number with no operator before it, is input left over after a whole expression.

<webcpp/pratt.hpp> includes the engine, <webcpp/pratt/errors.hpp> and <webcpp/pratt/parser.hpp>, whose names are in the namespace webcpp::pratt. The calculator, <webcpp/pratt/calculator.hpp>, is included by its own name, so that a program of the engine alone does not read Boost.Decimal; its names are in webcpp::pratt::calc. The code of this page writes them pratt::parse and calc::evaluate, as after namespace pratt = webcpp::pratt; and namespace calc = webcpp::pratt::calc;.

Writing a grammar takes the parts a program writes: the token stream, the grammar, the node, and the helpers that write the usual kinds of operator. The calculator shows the calculator, its number types and its environments, and The openui-lang micro-subset and the REPLs a grammar with calls, the seed of a parser of openui-lang, with the two programs that read lines and answer them. Errors lists every error, Limits the depth limit and the stack it protects, and Allocation what allocates and through which allocator. Testing shows how a program tests its grammar, and how pratt itself is tested. The reference closes the page.

A type models pratt::token_stream when it names its tokens token_type and has three functions:

The parser reads peek to decide whether the next token extends an expression, calls advance once for each token it hands a nud or a led, and asks at_end once a whole expression is parsed. peek must stay valid at the end of the input, and return there a token whose lbp is 0 and whose nud fails: '\0' in the first grammar, an end token in the calculator.

A stream may hold every token in advance, or lex each one as it is asked for. The characters of the first grammar is the simplest of them, and the calculator’s lexer, calc::stream, is lazy: it holds the source, its position and one token of lookahead, and no vector of tokens exists. The parser holds the stream by value, and moves it in.

A type G models pratt::grammar_for<G, S>, a grammar of the tokens of a stream S, when it names its node node_type and has three functions of a token t:

nud and led receive the parser, p, through which they parse their operands, and return a pratt::result<node_type>: the node, or an error. They are usually templates of the parser’s type, which names the grammar and the stream. The engine calls a led only for a token whose lbp is greater than the binding power the expression is parsed with, so a token of lbp 0 never reaches its led when the whole input is parsed with 0.

The parser’s expression(rbp) is what a nud or a led calls for an operand, and two more functions serve one that reads past its own token: p.peek() and p.advance(), the stream’s. The grammar of the openui-lang micro-subset reads the arguments of a call with them.

The node is whatever the grammar builds. The first grammar’s is an int, the value, computed while the parse goes; the grammar of the helpers below builds a string, the S-expression of the parse; the calculator’s node is a value and the name of a variable, so that = knows what it writes (The calculator). A program that keeps a tree makes the node a tree of its own. The engine moves nodes, and does nothing else with them.

Most operators come in a few kinds, and the engine writes each kind once, as a function a nud or a led returns. Each takes the parser and a binding power, parses its operands through expression, and calls a function of the grammar’s, make, which builds the node from the operands’ nodes:

This grammar is written with all six, and its node is the S-expression of the parse, (+ 1 (* 2 3)), so that its output shows how each line grouped. Its tokens are characters, as in the first grammar. Its binding powers put the sign below ^, and the postfix ! above everything; the grammar is shown here without its nud and its led, which follow:

Its nud makes a digit a literal, - a prefix operator and ( a grouping. unary and binary are two functions of the program that return the make of a node of one operand and of two:

Its led makes + - * / left-associative, ^ right-associative, and ! postfix. Only those tokens have an lbp above 0, so no other token reaches the led:

It prints:

-2^2 negates the power, since the sign asks for its operand with 30 and ^ binds with 40: the sign’s operand is 2^2. -3! takes the factorial first for the same reason, and 2*-3 shows the same - as a nud where a led stood before it. A grouping parses 1+2 with 0, so the + inside it binds whatever the power of what is outside, and a missing ) is expected_closing_token. A ) where an operand is due has no nud, and is an unexpected token.

Every helper recurses through expression alone, so a grammar written with them routes every token through its nud and its led, and the parser’s depth limit bounds its whole recursion (Limits).

pratt::parse(grammar, stream) parses the whole of a stream as one expression, with the power 0, and returns a pratt::result of the grammar’s node: the node, the first error a nud or a led returned, or trailing_input when tokens remain after a whole expression. A third argument, max_depth, bounds the recursion (Limits).

The class it uses is pratt::parser<Grammar, Stream>, which a program can construct itself, to call expression with another power, or to go on reading the stream after one expression. It holds a pointer to the grammar, so the grammar must outlive it, and a temporary grammar does not compile there; parse takes one, since its parser lives only for the call.

An error is whatever a nud or a led returned, passed on unchanged: one of pratt’s (Errors), or an error code of the program’s own category, which the engine never reads.

A number is digits, then optionally a point and more digits: 42, 0.5. A name is a letter or _, then letters, digits and _. Space, tab, carriage return and line feed separate tokens. The operators, from the loosest to the tightest, with the binding powers the grammar gives them:

A sign binds less tightly than ^, so -2 ^ 2 is -4, and ^ groups to the right, so 2 ^ 3 ^ 2 is 512, as the output above shows.

A variable keeps its value in the environment, from one line to the next:

It prints:

++ and -- behave as in C, and only on a variable: before it, they give the new value, and after it, the old one. A node of the calculator holds a value and, for a bare variable, its name, which is what =, ++ and -- write. A grouping keeps the name of what it holds, so (a) = 1 writes a and (a)++ increments it, while (1) = 2 has no name to write, and is an error. A variable that no line has written is an error only where it is read: a = 5 writes a name the environment does not hold yet.

The calculator computes in boost::decimal::decimal64_t by default, a decimal floating-point type of 16 significant digits, for exactness: a decimal fraction written in the input, 0.1 or 19.99, is exactly that number, so 0.1 + 0.2 == 0.3 holds and price * quantity is 59.97, not a binary approximation of it. The lexer builds each number in the number type’s own arithmetic, its digits as one integer divided once by ten to the number of its fraction digits, and never through a double.

A literal longer than the type’s precision keeps its first 17 significant digits in decimal64_t and in double (digits10 + 1, or max_digits10 where that is more): a later digit of the integer part multiplies the value by ten, and a later digit of the fraction is dropped. So 1. followed by any number of zeros is exactly 1, a literal up to the type’s largest value is finite, the largest double written out in full included, and 1 followed by 400 zeros is an infinity. A long literal is within one unit in the last place of the nearest decimal64_t, and within a few of the nearest double, whose digits round as they are read. A fraction keeps its value down to the type’s smallest subnormal, and is 0 below it.

An integral power is computed by repeated squaring, in the number type’s own multiplications, for exactness and determinism: every product is exact while it fits the type’s precision, so 43 + 12 + 2 * (44 - 12) ^ 4 is exactly 2097207, and the result is the same bits on every platform, where a library’s pow may round differently from one to the next. Past the precision, each product rounds, and the relative error grows with the exponent, where a correctly rounded pow would not: in double, 1.000000001 ^ 1000000000 differs from the result of std::pow in its ninth significant digit. That is the price of the same bits on every platform.

The same bits assume each compiler’s default for fusing a multiplication and an addition, which every operation of the calculator keeps apart in statements of their own. Built with -ffp-contract=fast or -ffast-math, a compiler may fuse them anyway, and a double result may then differ in its last place from one platform to another.

The power’s sign is the base’s when the exponent is odd. A negative integral exponent is one divided by the positive power, so 2 ^ -3 is 0.125, and 0 ^ 0 is 1. When the positive power overflows, or underflows to 0, pow computes the result instead, so 2 ^ -1074 is the smallest positive double and 0.1 ^ -400 is an infinity. Otherwise only an exponent that is not an integer calls pow.

Division by zero is an error, division_by_zero, for / and for %, and for 0 ^ -1, which divides by zero too. A floating-point type would answer an infinity or a NaN, and the line after would compute on with it; the calculator stops at the line that asked.

Any type that models calc::number serves. It is copyable and constructible from int, has the binary + - / *, the unary - and the six comparisons, and pow, fmod and trunc, found as using std::pow; pow(a, b) finds them, each returning the type itself. Boost.Decimal’s types model it, and so do float, double and long double. The number type is the environment’s: calc::environment<double> computes in double.

It prints, in the shortest form of std::to_chars:

The integral powers are still exact, 2 ^ 60 included, since repeated squaring multiplies powers of two, which double holds exactly. The decimal fractions are not: 0.1 and 0.2 are the nearest binary fractions, whose sum is not the nearest one to 0.3. 2.25 ^ 0.5 is not an integral power, and is the result of std::pow. Its exact value, 1.5, is a double, so any pow that errs by less than an ulp returns it exactly, on every standard library.

The environment is where the variables live, and its type is the program’s choice. A type E models calc::environment_for when its number_type models calc::number and it has two functions:

The name is a std::string_view into the line, so an environment that keeps a name copies it. calc::environment<Number, Allocator> is the calculator’s own, a std::map whose nodes and keys allocate through the program’s allocator (Allocation). This one is a program’s own, two variables in fixed storage, in double:

It refuses a third name with errc::not_enough_memory, an error of Boost.System’s generic category, which the calculator returns unchanged:

It prints:

Replacing width is no new name, so it succeeds when the storage is full; depth is refused, and stays unset, so reading it is undefined_variable. Nothing in this environment allocates, and so nothing in these evaluations does.

Every error of the calculator is a value of pratt::result, one of pratt’s errors (Errors) or the environment’s own:

It prints:

The lexer is lazy: it reads one token ahead, and the parse reads the tokens in order, so the first error in reading order is the one returned. A token’s error is found when the token is read, and an operator’s own error, an undefined operand or a zero divisor, once the operator has its operands. A character that is no token, such as $, is a token of its own, of the highest binding power, whose nud and led are invalid_character, so the engine reaches it wherever it stands, even after a whole expression, and 1 $ 2 is invalid_character rather than trailing_input.

A write made before the error stays made: nothing is undone.

It prints:

i++ $ increments i before it reads the $, so the line fails and i is 2. x + 1 $ is invalid_character although x is undefined: + finds that its left operand has no value only once it has its right one, and reading the right one reads the $ first. 5 = 3 $ is invalid_assignment_target, since = checks its target before it reads its right operand. A program that needs a line to write all or nothing evaluates it in a copy of the environment, and keeps the copy when the line succeeds.

The micro-subset has identifiers, integers, strings in double quotes without escapes, and ( ) , : =. Its node is the S-expression of the parse, a std::string: root = Stack(gap: 4) is (= root (call Stack (: gap 4))).

( holds both of Pratt’s denotations. At the start of an expression it is a grouping, the helper’s; after an expression, it calls what stands on its left, with the highest power, so Stack(1, 2)(3) calls the result of the first call. , and ) have the power 0, so each ends the expression of an argument, and the led reads them itself:

The call’s led reads its arguments in a loop, each one a whole expression of the engine’s, until the ):

A character that is no token, and a " that the line does not close, are tokens of their own with the highest power, as in the calculator, so the engine reaches them wherever they stand: the first is invalid_character, the second unexpected_end. The node allocates, since it is a string; it is the examples’ output format, and the parser of openui-lang to come defines a tree of its own, under the rule of Allocation.

Two programs read lines from their standard input and answer each one: openui_repl parses it with the micro-subset’s grammar and writes its S-expression, and calculator_repl evaluates it with the calculator, in one environment for the whole session. Both share one loop, in example/repl.hpp, which drops the carriage return of a line that ends in one, skips a line that is empty or holds only spaces or tabs, and ends at the line exit, exactly, or at the end of the input, with the status 0:

openui_repl hands the loop its grammar’s parse, and writes error:, a space and the error’s message when a line fails:

Its build feeds it openui_repl.input, a session whose tenth line ends in a carriage return and a line feed, whose eleventh holds only four spaces, whose twelfth only a tab, a space and a tab, and whose thirteenth is exit and a space, a name to parse rather than the end:

It prints, one line for each line it read, and stops at exit, before ignored:

openui_repl_eof is the same program on another input, whose lines end in a carriage return and a line feed, whose second line is empty, and whose last line, Stack(a), has no line feed after it and no exit:

It reads that last line, then ends at the end of its input:

calculator_repl keeps one calc::environment<> for the session, and writes each value in Boost.Decimal’s shortest form:

Its session, calculator_repl.input, holds the values and the errors of The calculator, a division by zero, and, just before exit, a line of ten thousand ( and a 1, left out here:

It prints, the line of ten thousand ( answering error: expression nested too deeply instead of overflowing the stack (Limits):

The parser counts its active expression calls, and refuses the call that would make them more than its limit, max_depth, with nesting_too_deep, before it reads a token. So the stack never grows past what the limit allows, and the input that would have overflowed it is an error like any other. max_depth is an argument of the parser’s constructor, of parse and of calc::evaluate, and its default is pratt::default_max_depth, which is 64. A negative max_depth behaves as 0, which refuses every parse.

A 1 inside a number of parentheses is that number plus one calls deep:

It prints:

The limit bounds the recursion through expression alone. That is the whole recursion of a grammar whose nuds and leds parse every operand through expression or the helpers, as the calculator’s and the micro-subset’s do, the micro-subset’s argument loop included. A nud or a led that recurses through functions of its own, without calling expression, is not bounded by it, and bounds that recursion itself.

The default is measured, not chosen. The measurement is the deepest nesting that the calculator evaluated without a trap, over calc::environment<>, with wasi-sdk 34 (clang 23.1.0) and wasmtime 47.0.3, and the stack divided by that depth, for three shapes of N operators or (. It was taken on wasm’s default stack of 64 KiB, in a debug build (-O0 -fno-inline) on wasip2 and wasip3, and in a build with -O2 on wasip2; natively in a debug build, on a stack of 8 MiB:

Of these three, the shape that costs the most is a grouping, by a few bytes a level. Over every shape of the calculator’s grammar and of openui-lang’s, the deepest debug parse that wasm’s default stack holds is at least 203 calls: openui-lang’s call shape, on wasip2. The calculator’s least is 214, a grouping with a pow inside. The default is the largest power of two at most half of that: half of 203 is 101, hence 64. A parse at the default depth uses at most half the stack, in the worst shape and the slowest build, on every target pratt is tested on; a build with -O2 and a native stack hold far more.

In a debug build on wasm, a level of grouping costs 272 bytes, a level of ^ 256 and a level of sign 240, plus at most about 7.5 KiB that a parse needs at any depth, its heaviest operand, a pow, included.

A program that raises the limit raises its stack with it, by the cost of a level times the levels it adds. On wasm, the stack is set when the program is linked, with the linker’s flag -Wl,-z,stack-size= and the size in bytes. A program that evaluates groupings 1024 deep in a debug build needs about 1024 times 272 bytes and 7.5 KiB, about 280 KiB, so it links with a stack of 1 MiB, which keeps the margin the default keeps:

and passes max_depth to every call: calc::evaluate(line, env, 1024). A b2 project adds the flag to its target’s requirements:

Natively, the stack is the thread’s. The main thread’s is the system’s, commonly 8 MiB on Linux and macOS (ulimit -s shows it), and a thread a program creates takes the size it is created with, through pthread_attr_setstacksize or Boost.Thread’s boost::thread::attributes::set_stack_size. The measurement above holds 12741 levels of ^ on 8 MiB in a debug build, so a native program has room for a limit far above the default without changing its stack.

The test below checks the grammar of the openui-lang micro-subset (The openui-lang micro-subset and the REPLs), with Boost.Core’s lightweight_test, the framework of one header that pratt’s own tests use. It includes the engine, the framework and the grammar:

A helper parses one line, with the default depth limit unless the test names another:

A test of trees compares the node of each line with the S-expression it should be: how = and calls group.

A test of errors compares the error of each wrong line with an enumerator of pratt::error, and checks the depth limit on both of its sides, with a limit small enough to write the input by hand:

main calls the cases and returns boost::report_errors(), the program’s status:

When every check holds, the program prints No errors detected. on its standard error, nothing on its standard output, and returns 0. A check that fails prints its expression, its values, its file and its line on the standard error, and main returns 1. .value() of a result that holds an error throws, or, built without exceptions, calls boost::throw_exception, which ends the program: the test stops there rather than compare a node that is not there.

pratt’s tests are lightweight_test programs, one per subject, under test/, each declared in test/Jamfile with webcpp’s webcpp.run:

Each case is a function named after the rule it checks, such as a_decimal_fraction_is_exact_in_decimal, and main calls them all and returns boost::report_errors(). Beside them, test/Jamfile compiles each public header alone, as the only include of its translation unit, so that a header that leans on an include it does not make fails, naming it. The lint checks the boundary that meta/include-boundaries.json declares: the engine’s headers include neither the calculator nor Boost.Decimal, since the engine knows no grammar and no number type. And example/Jamfile builds every program this page shows, runs it with the .input beside it as its standard input when there is one, and compares what it printed with the .expected beside it; a program that returns anything but 0 fails too.

test/Jamfile and example/Jamfile declare the targets they are built for, webcpp.targets native emscripten wasip2 wasip3, and b2 builds each program for those alone:

That pratt works without exceptions is checked by the lint, which compiles every public header, and every test and example, which instantiate its templates, with exception-handling=off; a template that none of them instantiates is not checked.

<webcpp/pratt/config.hpp>, which every public header of pratt includes first, defines WEBCPP_PRATT_NO_EXCEPTIONS when webcpp has no exceptions (WEBCPP_HAS_EXCEPTIONS is not defined: the compiler has none, or the program defined WEBCPP_NO_EXCEPTIONS), and a program may define it for pratt alone, to turn pratt’s exceptions off in a build that has them, as Boost.Asio’s BOOST_ASIO_NO_EXCEPTIONS does. pratt raises no exception of its own, so the macro changes nothing in it: it exists so that a program can set it for every webcpp library alike. The tests config, config_developer_defined and config_all_off check the three ways it is defined, and the lint refuses a throw in a public header, even in a template nothing instantiates: an exception goes through boost::throw_exception.

From the root of a webcpp checkout, each of these builds and runs, natively:

The WASI toolsets are b2’s clang, which a user-config.jam registers against wasi-sdk, as xactor’s page shows. The emscripten toolset is registered against emsdk, as trystero’s page shows, and runs a program with node itself, never with a testing.launcher. b2 compares timestamps, so a result that counts is built from scratch, with b2 -a. b2 libs/pratt/test//calculator builds and runs one test alone, while working on it.

The continuous integration runs pratt’s tests and examples in lanes, one toolset each: the native compilers, and wasip2 and wasip3. Each lane builds from scratch and records what b2 built and ran:

webcpp’s tools/report/report.py merges the files of every lane into a matrix: a page of the libraries by lanes, and a page of each library’s tests and examples by lanes, where each cell says whether that program passed in that lane, or how it failed, at compile time, at link time or when it ran. The matrix is published with the documentation, at https://webcpporg.github.io/report/.

The calculator’s own environment: a std::map from names to values, whose map and keys allocate through the user’s allocator.

The allocator the environment was given, which its map and its keys rebind.

The type of the values.

Constructors

Constructs an empty environment with a default-constructed allocator.

Constructs an empty environment that allocates through allocator.

Sets name to value, inserting the name or replacing its value.

The allocator the environment allocates through.

Finds the value of name.

The calculator’s grammar over an environment: numbers, variables, the arithmetic operators + - * / % ^, the comparisons, =, and ++ and -- before and after a variable.

What a parse builds.

The type the calculator computes in, the environment’s.

The tokens the grammar reads.

Constructs the grammar over env.

How tightly the token t binds the expression on its left.

The meaning of the token t after the expression left.

The meaning of the token t at the start of an expression.

The power of binary + and -.

The power of =, the weakest operator.

The power of the six comparisons.

The power of an invalid character, higher than every other, so that one after a complete operand is read as an operator, whose led gives error::invalid_character, rather than end the expression with error::trailing_input or error::unexpected_end.

The power of *, / and %.

The power of a postfix ++ or --, the tightest operator.

The power of ^.

The power a unary sign and a prefix ++ or -- parse their operand with, below ^.

A node of a calculator parse: a value, and the name of a bare variable.

Whether the node has a value: false for a name the environment does not hold.

The name of a bare variable, a view into the source; empty for every other node.

The value, when has_value says there is one.

The calculator’s lexer, a lazy webcpp::pratt::token_stream.

The tokens the stream yields.

Constructs the stream of source, and lexes the first token.

Consumes the next token and returns it; at the end, returns the end token again.

Whether the input is spent: the next token is the end token.

The next token, not consumed; the end token once the input is spent.

A token of the calculator’s input.

The token’s characters, a view into the source.

What the token is.

The value of a number token; 0 for every other kind.

What a token is.

A number literal, such as 42 or 0.5, whose value the token holds.

A variable’s name, such as x or _total2.

+, binary addition or a unary plus.

-, binary subtraction or a unary minus.

*, multiplication.

/, division.

%, the remainder of a division.

^, exponentiation.

(, which opens a grouping.

), which closes a grouping.

=, assignment.

==, equal.

!=, not equal.

<, less than.

<=, less than or equal.

>, greater than.

>=, greater than or equal.

++, a prefix or a postfix increment.

--, a prefix or a postfix decrement.

A character the lexer reads as no token, one character long.

The end of the input, which an empty text at the end of the source spells.

Evaluates source as one expression of the calculator, reading and writing its variables in env.

An environment the calculator reads and writes its variables in.

A type the calculator computes in.

What a parse that can fail returns: a T, or the error_code of the failure.

A Pratt parser of the tokens of a Stream, by a Grammar.

What the grammar builds.

The tokens the stream yields.

Constructors

Constructs a parser of stream by grammar.

Refused: the parser keeps a pointer to its grammar, which a temporary would leave dangling.

Consumes the next token and returns it: for a nud or a led that reads past its own token.

Parses the longest expression whose operators bind tighter than rbp.

Parses the whole input as one expression.

The next token, not consumed: for a nud or a led that reads past its own token.

The errors pratt reports, as boost::system::error_code values of the category error_category.

A token appears where the grammar’s nud or led has none for it.

The input ends where a token was still expected.

A closing token the grammar requires is missing.

Input remains after a complete expression.

The left side of an assignment or an increment is not a name.

A name is read before anything has written it.

A character the lexer reads as no token, such as $, or ! without =.

A parse recursed past the parser’s configured depth limit.

A division or a remainder was asked by zero.

The category of every error.

The nud of an opening token: a whole inner expression, then the closing token that is_close accepts.

The led of a left-associative infix operator of power bp.

The led of a right-associative infix operator of power bp.

The nud of an atom: the token is the whole expression.