Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Just Write the Parser

tiarkrompf.github.io

Post reply on HN
Print view View original

61–70 of 85 posts

Re: Just Write the Parser

#61

Post by ltratt »

hardwaregeek wrote: post #28
ben509 wrote: post #13

> Why simpler is better and why you don't need a parser generator. As far as I can see, this isn't fully answered, unless the claim is strictly limited to the question of need. In my case, I certainly want a parser generator. I'm working on a language, and I did a very early version using a hand-rolled recursive descent parser. Then I realized I wanted a syntax that was human friendly, so I graduated to megaparsec. T…

How do you handle good error messages or error recovery? I've played around with parser generators but I never figured out how to do either in a satisfactory fashion. Granted, my hand written parser doesn't do error recovery very well either.

Alas, most parser generators don't have very good error recovery (and some have such terrible error recovery that I think it's worse than not having any!).

It turns out that this isn't inevitable: there's been a long strand of research on decent error recovery for LR parsers, at least, but it needed a bit of a refresh to be practical. If you'll forgive the blatant self promotion, we tackled this problem in https://soft-dev.org/pubs/html/diekmann_tratt__dont_panic/ which is implemented in our Rust parsing system https://github.com/softdevteam/grmtools/. It won't beat the very best hand-written error recovery routines, but it's often not far behind.

Re: Just Write the Parser

#62

Post by ThePhysicist »

I'd recommend reading the "Elkhound" paper [1], which introduces a GLR parser that's really easy to implement and very powerful, they use it in the paper to parse a large subset of C++. GLR parsers are so much more powerful and intuitive than recursive descent parser (I find), and they often make grammars easier to read and understand.

That said if you're building a real programming language it makes sense to build the parser by hand as it often runs faster. For example, my GLR Python parsers clocked in at around 100.000-300.000 lines of Python code per second, while the regular Python parser could do 5-10 times as much per second (including tokenizing, parsing and AST generation). Looking at the amount of Python code that is parsed every day, this is a significant difference.

[1] https://people.eecs.berkeley.edu/~necula/Papers/elkhound_cc0...

Re: Just Write the Parser

#63

Post by chrisseaton »

wrs wrote: post #16

One reason to use a parser generator for a new language is that it will tell you that your language is inherently ambiguous or otherwise broken in a way you didn’t realize. A hand-coded parser tends to just codify your bad assumptions. It can actually be a good idea to maintain a YACC (or other) grammar for your language just to run the tool as a kind of “grammar linter”, even if you’re going to write the parser by h…

If you define your language using a recursive descent parser then it can’t be ambiguous.

Re: Just Write the Parser

#64

Post by Cloudef »

Cloudef wrote: post #59

Whenever someone mentions parsers or parser combinators, the only thing that comes to my mind is ragel that's really suited for generating any sort of parsers http://www.colm.net/open-source/ragel/

https://git.cloudef.pw/escpos2raster.git/tree/src/escpos/par... here is example, where I use ragel to parse ESC/POS printer protocol. Software that allows raster printers to print ESC/POS stuff.

Re: Just Write the Parser

#65

Post by kenoph »

How about no? Parsers are one of the main sources of bugs in software. You should write parsers manually only when you have a very good reason to. Go ask any of your system security friends.

Re: Just Write the Parser

#66

Post by swyx »

jtolmar wrote: post #17

I'd highly recommend looking at a few toy parser projects, like this and Crafting Interpreters (which are both recursive decent, with very different styles), writing however much of a typical parser you think makes sense "for fun," and then saving that somewhere you can get at it. Writing a parser from scratch is kind of an obnoxious hurdle, but if you have some code you're already familiar with that you can copy-pas…

what is "recursive decent"?

Re: Just Write the Parser

#67

Post by UK-Al05 »

thequux wrote: post #38
pklausler wrote: post #36

Earlier quoted context omitted.

If you construct your parser in some kind of declarative fashion (e.g., a parser combinator DSL), you can do that kind of error checking directly on the same spec that you compile to produce your parser.

Most parser combinator DSLs use PEGs to parse, which don't actually prevent ambiguity, but instead hide it. I strongly recommend using something that compiles your declarative grammar into LL(k) or LALR(k)

Do they hide or do they just apply order to choices. Making it impossible to be ambiguous compared to the CFG definition?

It's only sweeping under the rug, if you look at PEG under CFG rules. PEG is not CFG.

I think practice of writing industrial software that is better.

Re: Just Write the Parser

#68

Post by Terr_ »

It may be worth distinguishing between:

1. Having a formal grammar definition as the authoritative spec

2. Using the formal grammar definition to generate your parser

#1 is quite valuable on its own, even if you don't want to do #2. It can be analyzed for ambiguities and inconsistencies, and you avoid the tar-pit of "the original implementation is the spec".

Re: Just Write the Parser

#69

Post by chrisseaton »

thequux wrote: post #38
pklausler wrote: post #36

Earlier quoted context omitted.

If you construct your parser in some kind of declarative fashion (e.g., a parser combinator DSL), you can do that kind of error checking directly on the same spec that you compile to produce your parser.

Most parser combinator DSLs use PEGs to parse, which don't actually prevent ambiguity, but instead hide it. I strongly recommend using something that compiles your declarative grammar into LL(k) or LALR(k)

PEGs absolutely do prevent ambiguity - they don't 'hide' it - I don't even know what that would mean?

There is exactly one way a PEG can parse - there is no ambiguity at all.

Re: Just Write the Parser

#70

Post by newlikeice »

swyx wrote: post #66
jtolmar wrote: post #17

I'd highly recommend looking at a few toy parser projects, like this and Crafting Interpreters (which are both recursive decent, with very different styles), writing however much of a typical parser you think makes sense "for fun," and then saving that somewhere you can get at it. Writing a parser from scratch is kind of an obnoxious hurdle, but if you have some code you're already familiar with that you can copy-pas…

what is "recursive decent"?

man can dig hole. while digging one hole he finds two holes. he Diggs the one hole till he finds the bottom. climbs up to where he found the two the proceeds down the other hole. till he finds two more holes and then digs to the bottom of the first hole he finds until he hits bottom there. he descends until he hits bottom or digs through the earth. one hole at a time.

the digging is just the way your language constructs itself into different elements spread out like directories and sub-directories.

Post reply on HN