Pratt parsing is a black box
vinipsmaker.github.io
vinipsmaker.github.io
I was using Pratt parsing for almost a year in a macro-heavy language that I've been developing before finally sitting down on my chair to write my thoughts on Pratt parsing. Code is closed right now because I don't want LLMs training on my code before 0.1, but I'll open source it again later.
Happy to answer questions.
With erased static types, you can do arbitrary operations on types-as-values at compile time and just compile the static result into the runtime code, so it doesn't even cost anything at runtime to do this. Generic functions just turn into curried functions with the type params as their first param set.
My wip language uses '()' for 'always explicit params' and '{}' for 'can be implicit params', but both types and values can be passed into both (of course inference only makes sense for statically known types/values, so 'value' params in curly braces must be known at compile time and are treated like singleton types as well as their actual value in runtime code that uses them).
my understanding is that this makes certain typing decisions undecidable? I agree though the the special parallel type language is a huge amount of added complexity and source of pain.
This was exactly what initially motivated me to write my own language. I was spending a bunch of time writing complex types in Typescript (for SQL query builder type stuff - essentially data schema -> TS type transformation) as what was essentially just a bunch of regular boolean logic and iteration that would be simple, but because the 'type' world uses a completely different syntax to the 'value' world it gets unreadable really fast.
My language was originally basically "what if Typescripts type system treated types as first class values and let you use standard syntax for interacting with them", but I've been finding various other rabbit holes to fall into along the way.
I'd be curious as to what is undecidable as a consequence of this, that sounds like something that's going to bite me in the ass at some point.
Maybe I just need to see something super simple like a calculator with expressions side by side to grasp the trade-off?
This is more of a question language than a parser language. If you have a language that requires a Turing-complete parser than you gave up on grammar. You can use Pratt to parse languages that have grammars.
The language that I'm implementing has procedural macros (hence the parser is Turing-complete). However it has some "structure" that I can port to a tree-sitter parser. The tree-sitter parser for my language won't be 100% accurate, but it'll capture the most important structures.
Of course. I meant more that unlike with yacc or ohm - you won't have a grammar as an intrinsic artifact - you would have to maintain it and the Pratt code in sync manually?
From looking a bit more at ohm - it generates peg - and is apparently equivalent to Pratt - so I guess one can have the cake and parse it too?
As to benefits of Pratt, as best I can tell ohm is fast and lean - but handwriting a Pratt parser will be faster and leaner (esp lighter memory requirements).
Ohm does however handle left recursion, which could be considered a major feature of Pratt.
GCC used to use a type of parser generator but switched to recursive descent because the C language is just a little bit too dynamic to make it work well (EG typedefs). They specifically cited the advantage that because you are writing actual code to parse each production rule, you can break the conventions when needed.
return return 1;
However extending Pratt parsing to handle this case is trivial: https://vinipsmaker.github.io/blog/article/statements-in-pra...
It's still an extension so not really pure Pratt parsing IMO (other practitioners of Pratt parsing disagree with me).
Are there any professional slop interpreters who can explain what this means?
The ELI5 is that "semantic actions" are bits of code that a parser generator runs, and "production rules" are patterns that tell it when to run them.
For a simple ambiguous arithmetical grammar, the output of a parser fed "1 + 2 * 3" might be something like "[Mul [Add 1 2] 3]", or "AddExpr(1, MulExpr(2, 3))", or "1 2 3 Mul Add", or "1. Start with 1; 2. Add 2; 3. Multiply by 3", or (more likely in practice) in-memory data structures corresponding to one of those. The form of the representation doesn't matter; it's just an indication of the sequence of steps that gets you from 'nothing' to whatever input string was provided.
But there's not really a concept of 'actions' to go with parsing. Parsing tells you how some string was constructed, or how it might have been constructed. What you do with that information is up to you.
In the example above, the parser's interest in a MulExpr is that it can produce a string containing the token '*'. The fact that mathematically two times three equals six doesn't come up.
I'll appeal to authority here and quote from the Dragon Book:
>> Program fragments embedded within production bodies are called semantic actions.
In CS, particularly around compilers, it's an old concept.
--- begin quote ---
The second phase of the compiler is syntax analysis or parsing. The parser uses the first components of the tokens produced by the lexical analyzer to create a tree-like intermediate representation that depicts the grammatical structure of the token stream. A typical representation is a syntax tree in which each interior node represents an operation and the children of the node represent the arguments of the operation. A syntax tree for the token stream (1.2) is shown as the output of the syntactic analyzer in Fig. 1.7.
This tree shows the order in which the operations in the assignment
position = initial + rate * 60
--- end quote ---
For context, token stream 1.2 is the sequence of lexer output "ID1 = ID2 + ID3 * 60" (7 tokens long), and Figure 1.7 shows that sequence being transformed by a parser into the tree "[= ID1 [+ ID2 [* ID3 60]]]".
Back to the textbook:
--- resume quote ---
The subsequent phases of the compiler use the grammatical structure to help analyze the source program and generate the target program.
--- end quote ---
I'm struggling to see where this disagrees with my earlier comment in even the most minor detail.
I notice that the quote you provide comes from a later chapter, "A Simple Syntax-Directed Translator", and that there is no suggestion there that parsing involves semantic actions. Rather, semantic actions annotated on to a finished parse tree are presented as a tool for generating translations.
Had you moved on to the chapter section immediately following the one you quoted from -- the one titled "Parsing" (page 60) -- you might have seen that it opens by saying this:
Parsing is the process of determining how a string of terminals can be generated by a grammar.
I was specifically responding to your earlier statement:
>> But there's not really a concept of 'actions' to go with parsing.
And pointing out that even the Dragon Book talks about associating actions with parsing by attaching them to production rules for the parser. You don't seem to accept the literal text of the book, and that's not something I can understand. But that's your choice.
But that's just a false claim. The book does no such thing. The book, in the quote you pulled, talks about attaching semantic actions to finished parser output. At that point, the parser has already completed its work. It will never do anything again. The actions will neither affect it nor be seen by it. It's kind of like saying that illustration is part of writing a novel because an artist inserts their work into the finished manuscript.
Did you not notice that your quote doesn't contain any form of the word "parse"?
In the diagram displayed in section 1.2 ("The Structure of a Compiler"; the diagram is Figure 1.6 and also Figure 1.7), we see a statement processed in turn by a lexical analyzer, a syntax analyzer, a semantic analyzer, an intermediate code generator, a code optimizer, and finally a code generator.
The book informs us explicitly that a "syntax analyzer" and a "parser" are the same thing.
But those semantic actions are associated with the intermediate code generator two steps down the pipeline. They've got nothing to do with the parser.
Even in declarative languages like Haskell, your parser combinators will usually operate in a state monad so you can do things like this. True context-free grammars are rare; many real programmer convenience features have some level of context sensitivity, which is usually handled more easily by side effects in the semantic actions than by generalizing to a context-sensitive parser.
so that's another community's vote for actions as something belonging to The Parser over and above the strict grammar by which that parsing is done.
A Yacc file contains the grammar of the language to be parsed, but to each grammar rule you can attach a C function that will be invoked by the generated parser when matching that rule.
That C function is the "semantic action" registered for the corresponding grammar production rule.
For instance, by registering appropriate "semantic actions" the generated parser can become a language interpreter, e.g. when matching a multiplication expression a function that does multiplication is invoked, and so on.
If the parser is intended for a compiler, not for an interpreter, the "semantic actions" may generate some intermediate format of the compiled program, like that used by LLVM.
Older compilers with less memory may have compiled each function as it was parsed, but it's pretty typical these days for the parser to output a whole-file AST that you process separately.
The terminology is baroque, but pretty standard in parsing circles.
Essentially, different parsing algorithms "run side effects" at different stages of the parsing algorithm application, which can make certain things easy or difficult depending on the timing.
E.g.: If parsing runs side effects before it has 100% decided on what rules have been applied, it may need to "back track" and undo side-effects. This can be very painful to code around, so a common solution is to build (only) a temporary abstract syntax tree (AST) in a pure functional manner, and later come back and process that instead of trying to handle every "do and undo" scenario during initial parsing.
Parsers that only run side-effects when a decision is final allow very efficient compilers that directly "do the thing" instead of building temporary structures.
IIRC, Pascal was compiled this way, in a single pass.
"Production rules" are rules in grammar descriptions for tools like yacc. "Semantic actions" correspond to pieces of code/logic executed whenever a given rule is fully parsed from input.