Pratt parsing is a black box
This article argues that understanding Pratt parsing isn't about memorizing its nine lines of code, but about adopting a fundamental shift in how one approaches language parsing. It champions treating Pratt as a 'black box' to embrace its paradigm of applying semantic actions to tokens rather than production rules. The piece details how this unlocks powerful features like simplified grammar extension, macro systems, and advanced lexer composability for compiler writers.
The Lowdown
The author contends that most Pratt parsing tutorials miss the forest for the trees, focusing too much on the algorithm's implementation details instead of the crucial mindset shift it represents. The core idea is to treat Pratt parsing as a black box and focus on its properties and the changed approach to parsing problems.
- Semantic Action Shift: Unlike traditional parsers that map semantic actions to production rules (non-terminals), Pratt parsing maps them directly to terminal symbols via 'nuds' (null denotation, for tokens with no left context) and 'leds' (left denotation, for tokens with left context).
- Key Advantages: This shift eliminates left-recursion issues, prevents backtracking, ensures semantic actions run exactly once (allowing side-effects), enables arbitrary lookahead within actions, simplifies grammar ambiguity resolution, and provides trivial extension points for macros and evolving grammars.
- Algorithmic and Grammar Constraints: Pratt requires a separate lexer, is inherently fast (only 1-token lookahead), cannot parse statements independently (needs combination with other techniques), and operates as a form of recursive descent that can support context-sensitive parsing.
- Practical Guidelines: Offers tips for binding power tables (e.g., never zero for leds, use increments of 10) and demonstrates how to implement right-to-left associative operators with a simple binding power adjustment.
- Powerful Macros: Pratt parsing allows for macros that can seamlessly interleave between lexing and parsing, enabling highly flexible, unconstrained embedded DSLs by exposing lexer and parser APIs to the macros themselves.
- Lexer's Renewed Importance: The article stresses that the lexer becomes a critical component in Pratt parsing, especially through 'modal lexing' (where the lexer state changes based on parsing context) and designing lexers with cheap copy semantics for lookahead and rollbacks.
In conclusion, the article advocates for internalizing the 'Pratt mindset' – breaking grammatical structures into nuds and leds – rather than just understanding the algorithm, as this is key to unlocking its full power for robust language design.
The Gossip
Clarifying Compiler Concepts
The discussion delved into fundamental compiler terminology, specifically what 'semantic actions' and 'production rules' mean in traditional parsing. Commenters provided clear explanations, often referencing tools like Yacc and Bison, where C functions are attached to grammar rules. The author also weighed in, clarifying that the article immediately contrasts these traditional concepts with Pratt's approach of attaching actions to terminals, a significant differentiator often overlooked.
Parsing Paradigms Compared
Users questioned how Pratt parsing compares to other techniques like PEG (Parsing Expression Grammars) or Ohm/Ometa, particularly regarding the readability of the grammar as documentation. One commenter suggested that Pratt can be even more extensible than implied, allowing for more states beyond just 'nud' and 'led' to handle complex constructs like dictionary keys with dynamic expressions.
Type Syntax & System Speculation
A tangential but engaging conversation emerged about language design choices for generics and types, moving away from special delimiters like `<>` (angle brackets). Commenters explored using regular parentheses `()` or curly braces `{}` to treat types as first-class values that can be passed like any other parameter, even discussing implications for static type erasure and potential undecidability in type systems. The aim was to simplify the interaction with types by unifying type-world syntax with value-world syntax.