6 ms·
Yacc is Not Dead (2010)
- marktangotango 12y agoYacc 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?
- hobo_mark 12y agoI'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.
- vidarh 12y agoIt 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.
- wslh 12y agoFor simple languages they are easier to maintain than a custom parser.
- amelius 12y agoYou 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.
- jules 12y agoParser 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?
- sklogic 12y agoThere are parser generators based on PEG and Pratt, which are very flexible and efficient.
- jules 12y agoPEG 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?
- sklogic 12y ago> 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 https://github.com/combinatorylogic/mbase
- watwut 12y agoParser 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.
- zimbatm 12y agoIf 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.
- sklogic 12y ago> 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 https://en.wikipedia.org/wiki/Parsing_expression_grammar
- BruceIV 12y agoAs the original article points out multiple times, recursive descent can take exponential time, even for an unambiguous grammar.
- bmn_ 12y agoLR parsers like yacc are obsoleted by Earley parsers, which Cox apparently didn't know about in 2010. Quoting <http://loup-vaillant.fr/tutorials/earley-parsing/what-and-why#Why> http://loup-vaillant.fr/tutorials/earley-parsing/what-and-wh...: The biggest advantage of Earley Parsing is its accessibility. Most other tools such as parser generators, parsing expression grammars, or combinator libraries feature restrictions that often make them hard to use. Use the wrong kind of grammar, and your PEG will enter an infinite loop. Use another wrong kind of grammar, and most parser generators will fail. To a beginner, these restrictions feel most arbitrary: it looks like it should work, but it doesn't. There are workarounds of course, but they make these tools more complex. Earley parsing Just Works™. On the flip side, to get this generality we must sacrifice some speed. Earley parsing cannot compete with speed demons such as Flex/Bison in terms of raw speed. It's not that bad, however: • Earley parsing is cubic in the worst cases, which is the state of the art (and possibly the best we can do). The speed demons often don't work at all for those worst cases. Other parsers are prone to exponential combinatorial explosion. • Most simple grammars can be parsed in linear time. • Even the worst unambiguous grammars can be parsed in quadratic time. My advice would be to use Earley parsing by default, and only revert to more specific methods if performance is an issue… In 2014, we now have Earley parsers in C, JavaScript, Lua, Perl and Python. Further discussion on killing yacc: http://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2010/12/killing-yacc-1-2-3.html http://jeffreykegler.github.io/Ocean-of-Awareness-blog/indiv... http://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2010/12/why-the-bovicidal-rage-killing-yacc-4.html http://jeffreykegler.github.io/Ocean-of-Awareness-blog/indiv... http://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2011/04/bovicide-5-parse-time-error-reporting.html http://jeffreykegler.github.io/Ocean-of-Awareness-blog/indiv... http://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2011/05/bovicide-6-the-final-requirement.html http://jeffreykegler.github.io/Ocean-of-Awareness-blog/indiv...
- wolfgke 12y agoEarley parsers give no guarantee that the grammar is not ambiguous. This is very important, since you don't want your parser return some arbitrary parse tree, but you want guarantees that the parse tree that you intended is returned. yacc does this IMHO in the correct way: give warnings (shift/reduce or reduce/reduce conflict in case of a possible ambiguity) and let the user resolve these manually. Since these conflicts are a strong sign of a bad specification of the language, the parser generator should be very cautious in resolving these ambiguities - doing this automatically probably leads to strange consequences the user did not intend.
- antimagic 12y agoFrom the article: "...though Bison still retains yacc's infuriating lack of detail in error messages. (I use an awk script to parse the bison.output file and tell me what really went wrong.)" Oh dear. Now I'm going to have to get a new Irony meter, because mine just blew...
- amelius 12y agoHas anybody here used Elkhound [1]? How does it compare to e.g. ANTLR? Also, why do parser generators always have to be so language specific? [1] http://scottmcpeak.com/elkhound/ http://scottmcpeak.com/elkhound/ > Elkhound is a parser generator, similar to Bison. The parsers it generates use the Generalized LR (GLR) parsing algorithm. GLR works with any context-free grammar, whereas LR parsers (such as Bison) require grammars to be LALR(1).
- dalke 12y agoAccording to this swtch.com essay, "GNU Bison can optionally generate a GLR parser instead of an LALR(1) parsers" and checking history shows that GLR was available in Bison 1.75 in 2002 (See http://lists.gnu.org/archive/html/info-gnu/2002-10/msg00008.html http://lists.gnu.org/archive/html/info-gnu/2002-10/msg00008.... .) Regarding "so language specific"; proper language support for a given language is hard, and that's where most of the development time goes. Adding support for two languages is more than twice as hard as support for one language. Take a look at the comments for Java support in Bison, at http://www.gnu.org/software/bison/manual/bison.html#Java-Parsers http://www.gnu.org/software/bison/manual/bison.html#Java-Par... to see some of the difficulties and incomplete aspects of that port. Now consider a port to Python, which doesn't have a switch statement so likely needs very different code generation style.
- sklogic 12y agoI used Elsa a lot for static C++ code analysis, it was long before Clang was available. Cannot compare to antlr, since I've never seen a usable antlr C++ grammar implementation.
- 101914 12y agoMy favorite utility for this task is spitbol. I do not know of any software that is more naturally suited to working with BNF. Nothing I have seen is as flexible, either. I'm currently learning an additional, interpreted language and testing its limits; it is quite fast, so my opinion could change. But I doubt it.
- agumonkey 12y agoWhat killed my understanding of Yacc is the ad-hoc nature of semantic actions, I could never grasp what was in scope when it happened. You could access some state. Well I was never imperative oriented. I feel it could be enhanced with better integrated constructs like closures. C++ have them, I've seen people adding lambdas to C too, so maybe ... PS: Also, see that article thread about limitations of Parsing (composability) and other ideas. https://news.ycombinator.com/item?id=2327313 https://news.ycombinator.com/item?id=2327313
- BruceIV 12y agoI've been working on a derivative parser for PEGs; it's not quite working yet, but the inherent lack of ambiguity in PEGs is helpful to the time bounds there (I think I can make it worst case cubic, and linear in a lot of common cases). I've got some ideas how to modify the algorithm to a better derivative parser for CFGs; I should be able to recognize arbitrary CFGs in linear time, and I think parse them in cubic (carrying around the set of current parse tree options is expensive, but I think if you store them as a DAG of parsing paths rather than a parse tree you can make it tolerable).