đź“ťPratt parser
A generalized parsing technique for hand-crafted parsers.
build a table of operators (both infix and postfix)
for each operator: its precedence, associativity, a prefix parser function, an infix parser function
parse_precedencefunction takes minimum precedence to parse as inputget first token
call prefix parser for the given token (if there is no infix parser → syntax error)
then, while the next token precedence is ≥ input precedence
call infix parser for the next token, passing previously parsed expression as parameter
if there is not infix parser → return previously parsed expression
Pros
short and generic parser implementation
operators table can be dynamic, which allows easy implementation of user-defined operators
See also
Common Lisp: readtable—CL readtable also maintains a list of prefix parser. Although it is char-based, not token-based.
References
Compiling Expressions · Crafting Interpreters—Pratt parser tutorial. Pay attention that it does not build AST but compiles expressions to byte-code in one pass—therefore, it does not pass AST to the infix parser. It also does not seem to handle associativity.
implemented in Alpha (3891bf5)