📝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

Want to receive my 🖋 posts as I publish them?