đź“ť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 input- get 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)