📝Pratt parser

tags

§ Programming language implementation

A generalized parsing technique for hand-crafted parsers.

1. build a table of operators (both infix and postfix)

   • for each operator: its precedence, associativity, a prefix parser function, an infix parser function

2. parse_precedence function 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.

• [2021-10-31 Sun] implemented in Alpha (3891bf5)

Backlinks

• 📝 § Programming language implementation