It's a little surprising to see new parser generators being written, long after the vast majority of compilers have already settled on recursive descent / precedence climbing (including https://news.ycombinator.com/item?id=49913192 , which is currently nearby on the front page.)
I recall reading in the past that the primary reason parser generators aren't used for production compilers is the difficulty of making them produce useful error messages on malformed code. (Of course, the need for fine tuned optimizations also plays a role). Is this still true, or have parser generators caught up in this regard?
Mostly still true, yeah. A few tools have made real progress on error tolerance, continuing past a mistake rather than just stopping, tree-sitter is probably the best example, it's explicitly built to produce a best-effort tree from broken input, which is why it's good for editors. ANTLR also has configurable recovery strategies, single-token insertion/deletion heuristics and the like.
But "tolerant" isn't the same as "as good as hand-written." A hand-rolled recursive descent parser can say something like "missing semicolon after return statement" because the code knows exactly what construct it's in.
A generated parser's error is usually derived mechanically from the state machine, "expected one of: X, Y, Z, got W", which is correct but generic. This is what Yantra does at the moment. Closing that specific gap would mostly require hand-authored, context-specific messages layered on top. But its a good problem to solve.
For yantra specifically, it doesn't have error recovery at all yet. A syntax or lexer error just stops parsing at that point, no resynchronization, no continuing to find more errors in one pass. It's a known, documented gap, not something I'd claim is solved. For the kind of smaller or evolving DSLs this is aimed at, that's probably an acceptable tradeoff, but it does exist as a limitation.
> A hand-rolled recursive descent parser can say something like "missing semicolon after return statement" because the code knows exactly what construct it's in.
> A generated parser's error is usually derived mechanically from the state machine, "expected one of: X, Y, Z, got W", which is correct but generic.
You are not describing the difference between hand-written and generated but rather top down vs. bottom up.
There may be some confusion here because hand-written parsers are almost always recursive decent (a form of top down), while the most popular parser generators (yacc, bison) are bottom up. However hand-written bottom up parsers do exist (Pratt parsing, recursive ascent), as do top down parser generators (ANTLR, Coco/R, Chumksy). Chumsky in particular gives pretty decent error messages out of the box.
Bottom up parsers can parse a larger set of languages than top down parsers, but the tradeoff is you don't know what you are parsing until you successfully reduce the rule (unlike top down parsers). This is why errors in bottom up parsers often lack comments on structure/context like "after return statement" and can only give a list of which alternative symbols would have been valid.
People who write a language simply don't like bringing in another one, and that's all it is.
If we have a compiler for language X in language X, and don't use any tools such as a parser or lexer generator, then there is nothing but code in X in the project, and that makes the developer of language X feel like they have earned major brownie points ... err, I mean, ... that they have kept their project free of cumbersome dependencies.
If language X is a one-implementation invention, then the tooling won't exist which hits these checkboxes: (1) is written in X; (2) generates code for X. By the time language X is mature enough that its ecosystem has something like that, it is long past the point where it would make sense to introduce it into its one and only implementation. There would have to be interest in writing another implementation.
E.g. the first C compilers would never have used Yacc.
Among languages that have one implementation, and that use parser generators, we will almost always see that another language is used for bootstrapping and the generator is for that language.
For some designers, that is a bruise to the ego, or else an unappetizing dependency. Even if they are boostrapping with another language, they are thinking forward to a future release where they will ditch that: they will rewrite parts that are in the boostrapping language in the new language to make it self-hosting.
If you use tooling like parser generation, which is in the ecosystem of, and oriented toward, the to-be-jettisoned-one-day boostrapping language, that throws a barrier in the path toward self-hosting. So you tend not to do it.
Like if you are boostrapping with C, and have it in the back of your mind to get rid of it, do you want to be bringing in a complicated tool with its own input language, which generates C? You think twice and are more likely to go ahead if you've resigned yourself to sticking with the C dependency.
Fair and true. Most production compilers (Clang, rustc, Go) have moved to hand-written recursive descent, largely for error messages and debuggability: a hand-rolled parser can say exactly what went wrong and try to recover, a generated one is working from a state table.
One thing worth separating out though: recursive descent is already top-down, so it gets "build the tree, then decide what to do with it" for free, the same way ANTLR's LL(*) does. The intresting part of what I built is that it's getting that capability while keeping LALR's bottom-up table-driven parsing.
Where a grammar-first tool like this is more useful is smaller or evolving DSLs, where you want the grammar as a readable, declarative spec with automatic conflict detection instead of hand-tuned lookahead logic, and cases like generating multiple outputs (e.g. C++ and Java) from one grammar, which is awkward to bolt onto a hand-rolled parser after the fact.
Yacc has mid-rule actions which can be used to propagate information from left siblings to right siblings, as well as to children (embedded nonterminal symbols).
Of course, it's not the same as having the parse tree all done from a previous pass and just walking it to do semantics.
For people interested on this topic I strongly recommend to also look at Ben Hanson https://github.com/BenHanson/parsertl17 and based on it I've created an online LALR(1) playground here https://mingodad.github.io/parsertl-playground/playground/ where you have around 350 non trivial. grammars to experiment (select one from the `Examples` dropdown and then click `Parse` to see a parse tree for the input in `Input`, it also generates EBNF to generate nice navigable railroad diagrams on https://www.bottlecaps.de/rr/ui .
Sorry, but the explanation in your README of the example given here is wrong. This is right associative, not left associative as you claim. Looking at your docs, I think you need a %left PLUS; somewhere in there.
At least I think that's the case. Clarification appreciated.
Good luck.
I once knew how to fix shift/reduce reduce/reduce errors, but that was a long time ago.
With recursive descent parser you need to check for left recursion, which is somewhat less tricky.
Thanks, I really appreciate that.
The README's Quick Start should get you to a working parser in a couple minutes, and I'm around if you need any assistance.
It's a little surprising to see new parser generators being written, long after the vast majority of compilers have already settled on recursive descent / precedence climbing (including https://news.ycombinator.com/item?id=49913192 , which is currently nearby on the front page.)
I recall reading in the past that the primary reason parser generators aren't used for production compilers is the difficulty of making them produce useful error messages on malformed code. (Of course, the need for fine tuned optimizations also plays a role). Is this still true, or have parser generators caught up in this regard?
Mostly still true, yeah. A few tools have made real progress on error tolerance, continuing past a mistake rather than just stopping, tree-sitter is probably the best example, it's explicitly built to produce a best-effort tree from broken input, which is why it's good for editors. ANTLR also has configurable recovery strategies, single-token insertion/deletion heuristics and the like.
But "tolerant" isn't the same as "as good as hand-written." A hand-rolled recursive descent parser can say something like "missing semicolon after return statement" because the code knows exactly what construct it's in.
A generated parser's error is usually derived mechanically from the state machine, "expected one of: X, Y, Z, got W", which is correct but generic. This is what Yantra does at the moment. Closing that specific gap would mostly require hand-authored, context-specific messages layered on top. But its a good problem to solve.
For yantra specifically, it doesn't have error recovery at all yet. A syntax or lexer error just stops parsing at that point, no resynchronization, no continuing to find more errors in one pass. It's a known, documented gap, not something I'd claim is solved. For the kind of smaller or evolving DSLs this is aimed at, that's probably an acceptable tradeoff, but it does exist as a limitation.
> A hand-rolled recursive descent parser can say something like "missing semicolon after return statement" because the code knows exactly what construct it's in.
> A generated parser's error is usually derived mechanically from the state machine, "expected one of: X, Y, Z, got W", which is correct but generic.
You are not describing the difference between hand-written and generated but rather top down vs. bottom up.
There may be some confusion here because hand-written parsers are almost always recursive decent (a form of top down), while the most popular parser generators (yacc, bison) are bottom up. However hand-written bottom up parsers do exist (Pratt parsing, recursive ascent), as do top down parser generators (ANTLR, Coco/R, Chumksy). Chumsky in particular gives pretty decent error messages out of the box.
Bottom up parsers can parse a larger set of languages than top down parsers, but the tradeoff is you don't know what you are parsing until you successfully reduce the rule (unlike top down parsers). This is why errors in bottom up parsers often lack comments on structure/context like "after return statement" and can only give a list of which alternative symbols would have been valid.
People who write a language simply don't like bringing in another one, and that's all it is.
If we have a compiler for language X in language X, and don't use any tools such as a parser or lexer generator, then there is nothing but code in X in the project, and that makes the developer of language X feel like they have earned major brownie points ... err, I mean, ... that they have kept their project free of cumbersome dependencies.
If language X is a one-implementation invention, then the tooling won't exist which hits these checkboxes: (1) is written in X; (2) generates code for X. By the time language X is mature enough that its ecosystem has something like that, it is long past the point where it would make sense to introduce it into its one and only implementation. There would have to be interest in writing another implementation.
E.g. the first C compilers would never have used Yacc.
Among languages that have one implementation, and that use parser generators, we will almost always see that another language is used for bootstrapping and the generator is for that language.
For some designers, that is a bruise to the ego, or else an unappetizing dependency. Even if they are boostrapping with another language, they are thinking forward to a future release where they will ditch that: they will rewrite parts that are in the boostrapping language in the new language to make it self-hosting.
If you use tooling like parser generation, which is in the ecosystem of, and oriented toward, the to-be-jettisoned-one-day boostrapping language, that throws a barrier in the path toward self-hosting. So you tend not to do it.
Like if you are boostrapping with C, and have it in the back of your mind to get rid of it, do you want to be bringing in a complicated tool with its own input language, which generates C? You think twice and are more likely to go ahead if you've resigned yourself to sticking with the C dependency.
this would be narrowing parsers down to programming languages. however parser generators are great to real quick parse structured data, too.
this is extra helpful if the parser generator also generates intuitive language bindings to, e.g. python or TS.
Fair and true. Most production compilers (Clang, rustc, Go) have moved to hand-written recursive descent, largely for error messages and debuggability: a hand-rolled parser can say exactly what went wrong and try to recover, a generated one is working from a state table.
One thing worth separating out though: recursive descent is already top-down, so it gets "build the tree, then decide what to do with it" for free, the same way ANTLR's LL(*) does. The intresting part of what I built is that it's getting that capability while keeping LALR's bottom-up table-driven parsing.
Where a grammar-first tool like this is more useful is smaller or evolving DSLs, where you want the grammar as a readable, declarative spec with automatic conflict detection instead of hand-tuned lookahead logic, and cases like generating multiple outputs (e.g. C++ and Java) from one grammar, which is awkward to bolt onto a hand-rolled parser after the fact.
Yacc has mid-rule actions which can be used to propagate information from left siblings to right siblings, as well as to children (embedded nonterminal symbols).
Of course, it's not the same as having the parse tree all done from a previous pass and just walking it to do semantics.
Right, mid-rule actions genuinely let you shuttle state into a child before it's parsed, so it's not nothing.
But as you said, it's still one linear left-to-right pass. Appreciate you drawing the line precisely.
For people interested on this topic I strongly recommend to also look at Ben Hanson https://github.com/BenHanson/parsertl17 and based on it I've created an online LALR(1) playground here https://mingodad.github.io/parsertl-playground/playground/ where you have around 350 non trivial. grammars to experiment (select one from the `Examples` dropdown and then click `Parse` to see a parse tree for the input in `Input`, it also generates EBNF to generate nice navigable railroad diagrams on https://www.bottlecaps.de/rr/ui .
do you intend to add sth like python bindings, especially for the AST and walker classes?
then Yantra would become great to parse well-known structured data from python at low-level speed.
Sorry, but the explanation in your README of the example given here is wrong. This is right associative, not left associative as you claim. Looking at your docs, I think you need a %left PLUS; somewhere in there.
At least I think that's the case. Clarification appreciated.
isn't this close to what ragel does ?
Good luck. I once knew how to fix shift/reduce reduce/reduce errors, but that was a long time ago. With recursive descent parser you need to check for left recursion, which is somewhat less tricky.
Congratulations. We need more of these tools. I'll give it a try.
Thanks, I really appreciate that. The README's Quick Start should get you to a working parser in a couple minutes, and I'm around if you need any assistance.