Hacker News Reader

Comment by marktangotango | Hacker News Reader

Yacc may not be dead, but parser generation should be, in my opinion. If one is designing a language today one should, and indeed most new lanvuages in the last 5-10 years have, avoided the pathological ambiguities of C++. Hence implementing parsing via recursive descent is sufficient, and i say trivial as opposed to learning and using any particular parser generator (error handling being the lrimary culprit in my view). Even for C++, i don't know of a major project that does not use a handcrafted rec descent parser.

Can anyone convince me of the value of parser genaration, othr than an interesting academic exercise?

View on HN

Parser generators allow you to work on a higher level. The reason why you may want to use one is the same as the reason why you'd want to use a higher level language rather than assembly. Instead of repeating the same pattern to implement every rule in the grammar you simply write down the grammar and the parser generator expands that so that you don't have to. Unfortunately most parser generators are limited in the class of languages they parse, or they are limited in the languages that they can express conveniently. Even parser generators that support full context free grammars are not enough. You need some method to abstract common patterns. For example if you want to express operator parsing in a context free grammar you end up with a separate rule for each level of precedence. Parser combinator libraries do allow you to use the full abstraction facilities of the programming language, but they usually are weak in terms of which grammars they allow you to parse in polynomial time (usually LL), whereas ideally you would be able to parse regular languages in O(n), deterministic languages in O(n) and context free languages in O(n^3). Also parser combinators often do not support streaming & incrementality because their reliance on backtracking forces them to keep the entire input in memory.

I don't know of any parser generator or parser combinator library that simultaneously supports abstraction and supports efficient streaming parsing. Does anybody know one?

There are parser generators based on PEG and Pratt, which are very flexible and efficient.

PEG parsers are not streaming. They have to keep the entire input in memory in case backtracking happens. I'll look into Pratt parsing. I've actually implemented a Pratt parser in the past but I thought it was just for parsing operators with precedence?

> PEG parsers are not streaming.

PEG is a superset of recursive descent. You can structure you grammar in a way that backtracking is not required at all or minimised.

> They have to keep the entire input in memory in case backtracking happens.

Not necessarily. You only need to keep something like around a current statement (or other small syntax entity), discarding everything you've already streamed.

> I've actually implemented a Pratt parser in the past but I thought it was just for parsing operators with precedence?

Exactly. And it's really easy to mix it into an otherwise PEG-based parser, eliminating the need to backtrack for the worst backtracking case (binary expressions).

For example, there is a very efficient implementation of such an approach (pure PEG+Pratt, no memoisation and no backtracking) in Nemerle.

There is also a Packrat+Pratt parser used in https://github.com/combinatorylogic/mbase

I'm making a language that is equivalent to (and compatible with) C++, but has a regular grammar, bison is quite pleasant to work with, and the lalr grammar is potentially reusable elsewhere (in javascript, with jison, in haskell, with happy, in go, with go-yacc and so on). It also allows me to change the language structure very quickly which is very important when designing the language. In the future I'll write a recdes parser as well, because I also want pretty error messages, but the parser generator saved me a ton of time so far and will continue to for a while.

Parser generation saves development time when it comes to small or maybe even middle sized languages. Also, it is easier to see bigger picture on how language works when you have single file with rules.

Major project will necessary end up handcrafted, because major project usually need to be fast and optimized. Most projects are not that sensitive - they need to be developed reasonably fast and then need to be easy to be maintained.

It has its value for "quick and dirty" parser generation for experimentation, or for use in DSLs/ small tools where throwing something together is sufficient. But I agree with you overall - much more sophisticated parser generators than Yacc have still not gotten us to a point where using a parser generator for a full scale compiler for example is particularly viable as a long term strategy.

If the target is security sensitive, there's whole classes of errors that are avoided by parser generators.

They are also useful to use while shaping or discovering a syntax. Parser generators will quickly show you where the irregularities are because they will become harder (or impossible) to implement.

For simple languages they are easier to maintain than a custom parser.

You may still want to write the BNF for your language for documentation purposes. Also, you could use yacc to see if it contains ambiguities.

We certainly don't want languages with hidden ambiguities, which are resolved in different ways in different implementations.

As the original article points out multiple times, recursive descent can take exponential time, even for an unambiguous grammar.

> Hence implementing parsing via recursive descent is sufficient

And why exactly do you want an overbloated parser implementation full of leaky abstractions, while you can nicely generate it out of a BNF-like dense description?

> Can anyone convince me of the value of parser genaration

https://en.wikipedia.org/wiki/Parsing_expression_grammar

Reply on news.ycombinator.com