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.
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.
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).
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.
> 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", 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.
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?
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.
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.
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.
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.
> 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?
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 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.
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.
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.
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).
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.
> 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", 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.
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/
> Traditional parsing techniques register semantic actions to production rules.
Are there any professional slop interpreters who can explain what this means?
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.
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.
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.
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.
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.
> 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?
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 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.
That is not slop btw