Thread

Show HN: Yantra – an LALR(1) parser generator for C++

32 points · 17 comments · renjipanicker

Loading the complete thread in the background. This saved snapshot is available now. Refresh

kazinator · 1790826919 · focus · HN ↗
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.
1. renjipanicker · 1790828306 · focus · HN ↗
  [dead]
userbinator · 1790828071 · focus · HN ↗
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 <a href="https://news.ycombinator.com/item?id=49913192">https://news.ycombinator.com/item?id=49913192 , which is currently nearby on the front page.)
1. renjipanicker · 1790828715 · focus · HN ↗
  [dead]
2. traes · 1790830561 · focus · HN ↗
  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?
  1. renjipanicker · 1790831373 · focus · HN ↗
    [dead]
    Calavar · 1790834944 · focus · HN ↗
    > 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 rolled and generated but top down (LL) vs. bottom up (LR).
    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 additional context like "after return statement" and can only give a list of which alternative symbols would have been valid.
    There may be a some confusion here because hand-written recursive decent parsers are generally top down while the most popular parser generators (yacc, bison) are bottom up. However top down parser generators do also exists (ANTLR, Coco/R). ANTLR in particular gives pretty decent error messages out of the box.
    renjipanicker · 1790956422 · focus · HN ↗
    [dead]
    ahmedezat_katte · 1790835794 · focus · HN ↗
    [dead]
3. kazinator · 1790832309 · focus · HN ↗
  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.
4. froh · 1790838405 · focus · HN ↗
  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.
fithisux · 1790829401 · focus · HN ↗
Congratulations. We need more of these tools. I'll give it a try.
1. renjipanicker · 1790830957 · focus · HN ↗
  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.
mingodad · 1790834518 · focus · HN ↗
For people interested on this topic I strongly recommend to also look at Ben Hanson <a href="https://github.com/BenHanson/parsertl17" rel="nofollow">https://github.com/BenHanson/parsertl17 and based on it I've created an online LALR(1) playground here <a href="https://mingodad.github.io/parsertl-playground/playground/" rel="nofollow">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 <a href="https://www.bottlecaps.de/rr/ui" rel="nofollow">https://www.bottlecaps.de/rr/ui .
1. renjipanicker · 1790956361 · focus · HN ↗
  [dead]
signa11 · 1790834916 · focus · HN ↗
isn't this close to what ragel does ?
froh · 1790838594 · focus · HN ↗
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.
1. renjipanicker · 1790956318 · focus · HN ↗
  [dead]
MichaelMoser123 · 1790845284 · focus · HN ↗
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.
1. renjipanicker · 1790956226 · focus · HN ↗
  [dead]
sxzygz · 1790897601 · focus · HN ↗
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.
1. renjipanicker · 1790956261 · focus · HN ↗
  [dead]

Open on Hacker News to reply ↗

Unofficial Hacker News client; not affiliated with Y Combinator.