News for hackers. Stuff that matters.
Re:Pratt parsing is a black box by throwup238 on Tuesday November 03, 2026 @03:29PM (#50357733)
> Traditional parsing techniques register semantic actions to production rules.

Are there any professional slop interpreters who can explain what this means?

Re:Pratt parsing is a black box by vkazanov on Tuesday November 03, 2026 @03:41PM (#50357879)
The article doesnt read like slop. And this is a very clear sentence to anybody who knows any amount of parser theory.

"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.

Re:Pratt parsing is a black box by jiggawatts on Tuesday November 03, 2026 @03:43PM (#50357904)
The blog reads like organic human text, not mechanical slop.

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 ride 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.

Re:Pratt parsing is a black box by adrian_b on Tuesday November 03, 2026 @04:07PM (#50358202)
I assume that they refer to what you do when you write a Yacc or Bison file or any other input file for a similar parser generator.

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.

Re:Pratt parsing is a black box by direwolf20 on Tuesday November 03, 2026 @06:48PM (#50359835)
Executing the operation inside the semantic action only works for simple calculators. Otherwise you have the problem that the line of code may run multiple times even though it's only parsed once. Usually you make the semantic actions build an AST (a data structure holding the structure of the program, e.g. new BinaryExpression(left_ast, '+', right_ast)
Re:Pratt parsing is a black box by vinipsmaker on Tuesday November 03, 2026 @04:19PM (#50358347)
Others here already answered your question. In the blogpost, the text that immediately follows already demonstrates the concept, then it contrasts to what's done in Pratt parsing (semantic actions to to terminals instead of non-terminals). Non-terminals is another way to refer to production rules. This difference is a pretty big deal so it's important to mention. The rest of the section goes on to explain the consequences of this difference. None of this is mentioned in other Pratt tutorials that I read before so I doubt a slop machine would write articles of Pratt parsing even mentioning this trait at all.
Re:Pratt parsing is a black box by stschaef on Tuesday November 03, 2026 @04:23PM (#50358394)
That is not slop btw
Re:Pratt parsing is a black box by nostrademons on Tuesday November 03, 2026 @04:35PM (#50358520)
This is standard CS terminology - if you take a compiler course it'll be explained in the first couple lectures.

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.

Re:Pratt parsing is a black box by thaumasiotes on Tuesday November 03, 2026 @11:13PM (#50361433)
I would usually think of a 'parser' as simply something that tells you how to produce the input given a set of production rules. There are no actions involved.

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 "[Add 1 [Mul 2 3]]", or "1 2 3 Mul Add". 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.

Re:Pratt parsing is a black box by Jtsummers on Tuesday November 03, 2026 @11:38PM (#50361555)
[delayed]
Re:Pratt parsing is a black box by thaumasiotes on Wednesday November 04, 2026 @12:10AM (#50361703)
Well, quoting from the Dragon Book, page 8:

---

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
are to be performed.

---

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:

---

The subsequent phases of the compiler use the grammatical structure to help analyze the source program and generate the target program.

---

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.

Re:Pratt parsing is a black box by Jtsummers on Wednesday November 04, 2026 @12:29AM (#50361790)
[delayed]
Re:Pratt parsing is a black box by thaumasiotes on Wednesday November 04, 2026 @01:29AM (#50362094)
> [I was] pointing out that even the Dragon Book talks about associating actions with parsing by attaching them to production rules for the parser.

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"), 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.

Re:Pratt parsing is a black box by nagaiaida on Wednesday November 04, 2026 @03:12AM (#50362668)
for another perspective, raku lets you carry around reusable grammars, but each time you parse something with them you have the option to specify an actions class, the methods of which are invoked and passed the corresponding matches from the grammar (this lets you reuse the actual grammar matched against; sometimes you just want to typecheck cli arguments to main against a grammar and aren't actually going to use the match as anything other than an ornate boolean, but you might as well keep the actual grammar in sync between that nop/bool parser and another parser that actually builds something useful later).

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.

Re:Pratt parsing is a black box by nostrademons on Wednesday November 04, 2026 @11:55AM (#50368344)
At least in imperative languages, a parser generator can execute arbitrary code, including side effects. There's nothing stopping that code from simply returning a data structure; indeed, most productions will have semantic actions that just say "return new Mul($1, $2)". However, the ability to add imperative side effects is what allows things like keeping a comment counter for nested comments; keeping a symbol table in case the same token might be a keyword or variable; handling indent levels in newline-sensitive languages; and so on.

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.

Re:Pratt parsing is a black box by supersimpleguy on Tuesday November 03, 2026 @05:03PM (#50358874)
> I don't understand what was said, so instead of trying to look it up myself I'll just toss my hands in the air, call it "slop". Aren't I the smartest?
Re:Pratt parsing is a black box by vinipsmaker on Tuesday November 03, 2026 @04:01PM (#50358134)
Author here.

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.

Re:Pratt parsing is a black box by p1necone on Tuesday November 03, 2026 @05:03PM (#50358883)
Tangential - on the 'use [] instead of <>' advice that you referenced in the post, I wish more languages would experiment with making types first class values that just get passed in regular () braces instead.

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.

Re:Pratt parsing is a black box by convolvatron on Tuesday November 03, 2026 @05:45PM (#50359313)
in logic programming you can just use normal predicates for arbitrary types also.

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.

Re:Pratt parsing is a black box by p1necone on Tuesday November 03, 2026 @05:54PM (#50359385)
> 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 Typescript had types as first class values and wasn't permanently tied to the unsound foundation of Javascript", but I've been finding various other rabbit holes to fall into along the way.

Re:Pratt parsing is a black box by tyromaniac on Tuesday November 03, 2026 @08:11PM (#50360388)
I believe zig does this
Re:Pratt parsing is a black box by p1necone on Wednesday November 04, 2026 @04:23PM (#50371757)
Yeah zig was definitely a big inspiration - implementing type system stuff as comptime code execution gives you a bunch for free that would otherwise be pretty tricky to implement.
Re:Pratt parsing is a black box by vinipsmaker on Tuesday November 03, 2026 @09:51PM (#50360992)
My own language doesn't try to unify both worlds (values from "type" world and values elsewhere), but my macros can be configured to happen in the type world. From a macro for the type world, you can run normal code to return whatever type you want. It's not the same thing you're talking about, but it's another interesting thing you can do.
Re:Pratt parsing is a black box by ogogmad on Wednesday November 04, 2026 @01:08PM (#50369308)
Wondering how that compares to dependent types.
Re:Pratt parsing is a black box by p1necone on Wednesday November 04, 2026 @04:21PM (#50371734)
I think they are essentially dependent types, I'm just coming at it from the "idiot with a laptop who hasn't read up on type theory" direction, and trying to fit everything into the "but what if it was just another place the user can write regular code" hole.
Re:Pratt parsing is a black box by e12e on Tuesday November 03, 2026 @04:48PM (#50358673)
I'd like to see a bit more about how compares to peg or something like ohm/ometa - am I correct assuming you pretty much give up the benefits of a readable grammar as documentation?

Maybe I just need to see something super simple like a calculator with expressions side by side to grasp the trade-off?

https://ohmjs.org/

Re:Pratt parsing is a black box by vinipsmaker on Tuesday November 03, 2026 @09:36PM (#50360904)
> am I correct assuming you pretty much give up the benefits of a readable grammar as documentation?

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.

Re:Pratt parsing is a black box by e12e on Tuesday November 03, 2026 @10:36PM (#50361246)
> You can use Pratt to parse languages that have grammars

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?

Re:Pratt parsing is a black box by vinipsmaker on Wednesday November 04, 2026 @09:11AM (#50365774)
I'm not familiar with ohm/ometa, but yes, if your language is "simple" it's possible to design a framework that generates both the Pratt parsers + a grammar so you don't need to manually keep them in sync. The complexity toll will be spent on this framework though. Plus it's unlikely that you're gonna explore traits that are exclusive to Pratt parsing so Pratt parsing would be just an implementation detail that you don't need to even bother to learn. The only upside of adopting Pratt parsing here is that Pratt parsing is fast.
Re:Pratt parsing is a black box by e12e on Wednesday November 04, 2026 @03:26PM (#50371034)
I recommend having a quick look at https://ohmjs.org/ just because it's such a joyful project that present parsing in such a simple fashion.

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.

Re:Pratt parsing is a black box by teleforce on Tuesday November 03, 2026 @11:49PM (#50361597)
> Packrat isn't really a parsing algorithm - the PEG is the parsing algorithm. Packrat is instead an optimisation that can be transparently applied to a PEG [1]

[1] https://news.ycombinator.com/item?id=20502974

Re:Pratt parsing is a black box by ghusbands on Tuesday November 03, 2026 @06:20PM (#50359584)
I've written a few Pratt parsers in my time. You don't need a lexer and you can have more parser states than are implied by 'nud' and 'led'. They can be incredibly extensible. For example, if you can parse the expression "{a:1, b:2}" then you might naturally have an Expr state (nud), a Between state (led) and a DictKey state; that might initially accept just an identifier and a colon before recursing into Expr state, but you could later add dynamic expressions, perhaps via a macro, to support [expr] as a key.
Re:Pratt parsing is a black box by direwolf20 on Tuesday November 03, 2026 @06:43PM (#50359789)
Is this the same algorithm commonly known as "recursive descent" parsing? The array index example is just recursive descent and the expression parsing is recursive descent with abstracted operators instead of a parsing function per precedence level.
Re:Pratt parsing is a black box by YuechenLi on Tuesday November 03, 2026 @06:53PM (#50359873)
Recursive descent and Pratt are two different but related parsing methods. Pratt is simpler and recursive descent is more explicit, but it's not an "either/or" thing since a parser can use both methods.
Re:Pratt parsing is a black box by ogogmad on Wednesday November 04, 2026 @12:34PM (#50368849)
Pratt is a combination of recursive descent and precedence-climbing. Maybe even the combination? Those ideas are individually older than Pratt.
Re:Pratt parsing is a black box by ogogmad on Wednesday November 04, 2026 @12:31PM (#50368797)
"Pratt can't parse statements" - can't you treat ';' as an operator whose meaning is "then"? You can then read "DOTHIS(); DOTHAT()" as an expression.
Re:Pratt parsing is a black box by vinipsmaker on Wednesday November 04, 2026 @12:52PM (#50369110)
You need to forbid stuff such as:

  return return 1;
return itself isn't an expression (it's a statement) so it can't be used in places that expect expressions (such as the "argument" to return itself).

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).