12 ms·

Yacc is dead

154 points by benblack 16y ago

mahmud 16y ago
Brzozowski's derivatives of regular expressions has been in use in the PLT compiler tools for ages now.
RiderOfGiraffes 16y ago
Fascinating. I don't understand it all yet - I'm reading it carefully but it'll be weeks before I really get it. However ... I'm getting the feeling that this encompasses properly a feeling I've had about parsing for some time, that there should be a way of parsing the entire text, with the parse settling onto the text all at the same time. I don't know if this is what it's saying, but that's the sense I get from it. But even if it isn't, it looks intriguing.
- jerf 16y ago
  You mean something like this?: http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html http://blog.sigfpe.com/2009/01/fast-incremental-regular-expr... Note that the post has 'prerequisites' at the beginning, which you will need to read, but they are actually pretty cool. Also I am not saying this is exactly what you mean, I'm just suggesting it as a possible connection. This sort of thing is one of the admittedly-rare exceptions where computer science is actually making surprising amounts of progress in relatively practical fields. Parsing has gotten noticeably easier in the past ten years, if you know where to look for the right libraries, and it has been affecting my programming quite a bit. Often, a parser is the "correct" solution, but we used to reach up for hacked up crap with regular expressions or worse because it was ten times easier and did 80% of the job (and ignore the 10% that is a serious security vulnerability since everybody always does). Now it's maybe twice as hard, or, given how easy it is to underestimate the difficulty of getting the hacked up crap to actually work everywhere in the real world you need it to, sometimes it's just flat-out easier if you make a full accounting of costs to actually do it correctly.
  - RiderOfGiraffes 16y ago
    Cool reference, and I'll be working on that too over the next week or so to see if that's close to what I mean. Thanks.
  - StrawberryFrog 16y ago
    regular expressions are always the wrong tool for the job of parsing languages with recursive syntax. See, for instance, http://stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/1732454#1732454 http://stackoverflow.com/questions/1732348/regex-match-open-...
    - jerf 16y ago
      Did you actually read the linked stuff, or did you just trigger on the keywords "parse" and "regular expression"? I did say it wasn't exactly what was looked for, but it would be interesting to see if someone could extend the results in the linked post from a regular expression to a parse tree. It isn't immediately obvious to me whether you could or could not.
      - pjscott 16y ago
        Yes, it's possible to extend the method in the linked post to parse trees. Check out monoidal parsing: http://comonad.com/reader/2009/iteratees-parsec-and-monoid/ http://comonad.com/reader/2009/iteratees-parsec-and-monoid/ This guy figured out how to turn parsers written with Parsec (an excellent collection of parser combinators; truly a pleasure to use) into monoidal parsers that you can use for incremental and/or parallel parsing.
  - pjscott 16y ago
    Here's a quick summary of the broader implications of that link, because I had trouble wrapping my head around it at first. Suppose you have the ability to take a chunk of text and construct a partial parse state from it. In the case of regexp matching, these partial parse states are functions mapping one state of the regexp matching automaton to another. You need one more thing: the ability to append two of these partial parse states, combining them into one. In the regexp example, this is just function composition. The key here is that this operation must be associative, and there must be an identity element: some partial parse state such that combining it with another state doesn't change anything. And its result must also be a partial parse state. This combination of parse states and an associative binary operation is called a monoid. Once you have these conditions fulfilled, you can do all sorts of fun stuff. For instance, you can represent a string as a tree of chunks, and cache partial parse states at the nodes in the tree. That way, when you change the string, you can recompute the changed parse states in something like O(lg n) time, rather than going through and re-parsing the entire string. Or you can almost trivially parallelize your parser. A week ago, I did exactly this: I had a language that needed parsing, and I wanted to incrementally reparse when I changed the (potentially very long) string, so I used a finger tree and wrote an incremental parser. It works beautifully.
antimatter15 16y ago
The implementations are at http://www.ucombinator.org/projects/parsing/ http://www.ucombinator.org/projects/parsing/
- davdar 16y ago
  I have since rewritten the Haskell implementation to compute fixed points on cyclic graphs without using pointers or Monads. Check it out if it interests you (git repo): http://david.darais.com/git/research/der-parser-3/ http://david.darais.com/git/research/der-parser-3/
amichail 16y ago
Why was it rejected by ESOP?
- fizx 16y ago
  Possibly because they hand-waved away a lot of formal specification of their solution. For example, there was no attempt to analyze the complexity of the generated rules trees.
- stupidsignup 16y ago
  Well, if you want to know what ESOP rejection reviews look like: http://phlegmaticprogrammer.wordpress.com/2010/11/21/reviews-for-purely-functional-structured-programming/ http://phlegmaticprogrammer.wordpress.com/2010/11/21/reviews... and the response to these reviews here: http://phlegmaticprogrammer.wordpress.com/2010/11/21/response-to-reviews/ http://phlegmaticprogrammer.wordpress.com/2010/11/21/respons...
DanielRibeiro 16y ago
Well, Antlr (http://www.antlr.org/ http://www.antlr.org/) has replaced yacc for most of the practical work already. Daniel Spiewak also mentions parser combinators and how GLL parsers can be much easier to use and yet fast enough most of the time (http://www.codecommit.com/blog/scala/unveiling-the-mysteries-of-gll-part-1 http://www.codecommit.com/blog/scala/unveiling-the-mysteries...). He mentions parser combinators as domain specif languages for creating parsers (http://www.codecommit.com/blog/scala/the-magic-behind-parser-combinators http://www.codecommit.com/blog/scala/the-magic-behind-parser...). Despite all of these, adoption of better techniques is really slow. As usual.
- sliverstorm 16y ago
  Heh... Yacc, Bison, Antlr...
johkra 16y ago
What is actually state-of-the-art in parsing? When I, as an Amateur, last looked into it, PEG[1] and extensions like OMeta[2] seemed to be the best options. I've heard good things about Parsec[3], too. [1](http://en.wikipedia.org/wiki/Parsing_expression_grammar http://en.wikipedia.org/wiki/Parsing_expression_grammar) [2](http://www.tinlizzie.org/ometa/ http://www.tinlizzie.org/ometa/) [3](http://legacy.cs.uu.nl/daan/parsec.html http://legacy.cs.uu.nl/daan/parsec.html)
- sb 16y ago
  I am not so sure about the actual state-of-the-art (I have read some PEG papers and some OMeta stuff from vpri, plus used ANTLR, Bison, and Coco/R), but a very interesting comment on HN (http://news.ycombinator.com/item?id=1643715 http://news.ycombinator.com/item?id=1643715) points out that most production compilers use hand-written recursive-descent parsers, primarily due to practical reasons. I have taken two compiler construction courses during my college years, one with LL(1) grammar using a recursive descent parser, the other one with LR(1) grammar using flex+bison tool-chain. I found the experience from the LL case helped me tremendously in the course of writing the LR-language compiler. I think that recursive-descent experience also helps understanding attribute grammars, too. Probably the best introduction to recursive-descent parsers is from Niklaus Wirth's compiler construction book (http://www-old.oberon.ethz.ch/WirthPubl/CBEAll.pdf http://www-old.oberon.ethz.ch/WirthPubl/CBEAll.pdf).
  - krakensden 16y ago
    What are the practical reasons? Dealing with non-uniform edge cases and other strange constraints? Integrating the stuff the compiler needs to do with the parser-generator?
    - k4st 16y ago
      I can imagine one practical reason is that a lot of stuff (e.g. type information, variable bindings) goes top-down, but bottom-up parsers reduce rules in the opposite direction and so it takes extra effort to make the mental model of programming fit with the reduction strategy of bottom-up parsers.
fizx 16y ago
Here's what a grammar actually looks like in their scala version. This grammar is for arithmetic over the language where x represents 1, and s represents +. This only generates the parse tree, not the final answer. Comments are added by me: // The Nodes in the parse tree abstract class Exp case object One extends Exp case class Sum(e1 : Exp, e2 : Exp) extends Exp // Terminals lazy val S : Parser[Char,Char] = new EqT[Char] ('s') lazy val X : Parser[Char,Char] = new EqT[Char] ('x') // Definition of an expression // I'm pretty sure all the asInstanceOfs are avoidable/unnecessary. lazy val EXP : Parser[Char,Exp] = rule(X) ==> { case x => One.asInstanceOf[Exp] } || rule(EXP ~ S ~ EXP) ==> { case e1 ~ s ~ e2 => Sum(e1,e2).asInstanceOf[Exp] } || rule(EXP ~ S ~ X) ==> { case e1 ~ s ~ e2 => Sum(e1,One).asInstanceOf[Exp] } || rule(X ~ S ~ EXP) ==> { case e1 ~ s ~ e2 => Sum(One,e2).asInstanceOf[Exp] } || rule(X) ==> { case x => One.asInstanceOf[Exp] } || rule(EXP) ==> { case e => e } || rule(Epsilon[Char]) ==> { case () => One } // Actually run the rule val xin = Stream.fromIterator("xsxsxsxsx".elements) EXP.parseFull(xin) // return value => Stream(Sum(One,Sum(Sum(One,One),Sum(One,One))), ?)
kleiba 16y ago
Do I hear John McCarthy chuckle?
mattmight 16y ago
(Article author here.) I'm delighted to see this get some attention here. I absolutely love these techniques for parsing, but as my primary research areas is static analysis, I haven't had time to revise this paper and resubmit. As it stands, I may never get the time to do so. :( I posted it on arxiv so that David could reference it for his Ph.D. school apps. Since some of you have asked, here are the reviews: http://matt.might.net/papers/reviews/esop2010-derivatives.txt http://matt.might.net/papers/reviews/esop2010-derivatives.tx... I do have an updated implementation that's much cleaner and faster, and I've been planning to do that in a blog post. (Alas, no opportunity yet.) David's also done another implementation in Haskell that's screaming fast and efficient on many restricted classes of grammars (like LL(k)). I'll encourage him to post that as well. If you're interested in getting your name on a scientific publication and helping this get the attention of the scientific community, you can help us by creating an implementation of either technique in your favorite language and beating on it to help find the inefficiencies. (For instance, the original Scala version linked from this paper has memory leaks from the way it caches derivatives. We got around them by rolling top-level repetition by hand.) Please email me if that's something you're interested in doing. Can HN do science? I'd love to find out.
- k4st 16y ago
  I haven't finished the paper yet, but this type of technique excites me as well. Recently, I did an assignment on the paper "memoization in top-down parsing" by Mark Johnson. Have you seen this paper, and do you think that there are any similarities between the derivatives of a CFG and continuations of parsing procedures (for variables and their related productions)?
  - mattmight 16y ago
    I'll have to check out Mark's paper, but just by your description, I bet they're related. For finite-state and pushdown automata, derivatives and continuations are two sides of the same coin.
- copper 16y ago
  "this is not quantum theory, after all..." is one of the funnier comments I've seen on a review. Judging by the rest of it, I'm tempted to guess that it was written by someone from team-PLT :) Could either you or David put the source for the LL(k) version up somewhere? Comparing it head-to-head with parsec (or its faster cousins) something fun to do.
benblack 16y ago
So many useful links in this discussion, I consolidated them (and a few extras) here http://post.b3k.us/modern-parsing-bibliography http://post.b3k.us/modern-parsing-bibliography
herdrick 16y ago
Better comments at programming.reddit, sadly: http://www.reddit.com/r/programming/comments/ed2pb/yacc_is_dead/ http://www.reddit.com/r/programming/comments/ed2pb/yacc_is_d...

154 points by benblack 16y ago

Brzozowski's derivatives of regular expressions has been in use in the PLT compiler tools for ages now.

Fascinating. I don't understand it all yet - I'm reading it carefully but it'll be weeks before I really get it. However ... I'm getting the feeling that this encompasses properly a feeling I've had about parsing for some time, that there should be a way of parsing the entire text, with the parse settling onto the text all at the same time. I don't know if this is what it's saying, but that's the sense I get from it. But even if it isn't, it looks intriguing.

jerf 16y ago
You mean something like this?: http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html http://blog.sigfpe.com/2009/01/fast-incremental-regular-expr... Note that the post has 'prerequisites' at the beginning, which you will need to read, but they are actually pretty cool. Also I am not saying this is exactly what you mean, I'm just suggesting it as a possible connection. This sort of thing is one of the admittedly-rare exceptions where computer science is actually making surprising amounts of progress in relatively practical fields. Parsing has gotten noticeably easier in the past ten years, if you know where to look for the right libraries, and it has been affecting my programming quite a bit. Often, a parser is the "correct" solution, but we used to reach up for hacked up crap with regular expressions or worse because it was ten times easier and did 80% of the job (and ignore the 10% that is a serious security vulnerability since everybody always does). Now it's maybe twice as hard, or, given how easy it is to underestimate the difficulty of getting the hacked up crap to actually work everywhere in the real world you need it to, sometimes it's just flat-out easier if you make a full accounting of costs to actually do it correctly.
- RiderOfGiraffes 16y ago
  Cool reference, and I'll be working on that too over the next week or so to see if that's close to what I mean. Thanks.
- StrawberryFrog 16y ago
  regular expressions are always the wrong tool for the job of parsing languages with recursive syntax. See, for instance, http://stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/1732454#1732454 http://stackoverflow.com/questions/1732348/regex-match-open-...
  - jerf 16y ago
    Did you actually read the linked stuff, or did you just trigger on the keywords "parse" and "regular expression"? I did say it wasn't exactly what was looked for, but it would be interesting to see if someone could extend the results in the linked post from a regular expression to a parse tree. It isn't immediately obvious to me whether you could or could not.
    - pjscott 16y ago
      Yes, it's possible to extend the method in the linked post to parse trees. Check out monoidal parsing: http://comonad.com/reader/2009/iteratees-parsec-and-monoid/ http://comonad.com/reader/2009/iteratees-parsec-and-monoid/ This guy figured out how to turn parsers written with Parsec (an excellent collection of parser combinators; truly a pleasure to use) into monoidal parsers that you can use for incremental and/or parallel parsing.
- pjscott 16y ago
  Here's a quick summary of the broader implications of that link, because I had trouble wrapping my head around it at first. Suppose you have the ability to take a chunk of text and construct a partial parse state from it. In the case of regexp matching, these partial parse states are functions mapping one state of the regexp matching automaton to another. You need one more thing: the ability to append two of these partial parse states, combining them into one. In the regexp example, this is just function composition. The key here is that this operation must be associative, and there must be an identity element: some partial parse state such that combining it with another state doesn't change anything. And its result must also be a partial parse state. This combination of parse states and an associative binary operation is called a monoid. Once you have these conditions fulfilled, you can do all sorts of fun stuff. For instance, you can represent a string as a tree of chunks, and cache partial parse states at the nodes in the tree. That way, when you change the string, you can recompute the changed parse states in something like O(lg n) time, rather than going through and re-parsing the entire string. Or you can almost trivially parallelize your parser. A week ago, I did exactly this: I had a language that needed parsing, and I wanted to incrementally reparse when I changed the (potentially very long) string, so I used a finger tree and wrote an incremental parser. It works beautifully.

antimatter15 16y ago

The implementations are at http://www.ucombinator.org/projects/parsing/ http://www.ucombinator.org/projects/parsing/

davdar 16y ago
I have since rewritten the Haskell implementation to compute fixed points on cyclic graphs without using pointers or Monads. Check it out if it interests you (git repo): http://david.darais.com/git/research/der-parser-3/ http://david.darais.com/git/research/der-parser-3/

amichail 16y ago

Why was it rejected by ESOP?

fizx 16y ago
Possibly because they hand-waved away a lot of formal specification of their solution. For example, there was no attempt to analyze the complexity of the generated rules trees.
stupidsignup 16y ago
Well, if you want to know what ESOP rejection reviews look like: http://phlegmaticprogrammer.wordpress.com/2010/11/21/reviews-for-purely-functional-structured-programming/ http://phlegmaticprogrammer.wordpress.com/2010/11/21/reviews... and the response to these reviews here: http://phlegmaticprogrammer.wordpress.com/2010/11/21/response-to-reviews/ http://phlegmaticprogrammer.wordpress.com/2010/11/21/respons...

DanielRibeiro 16y ago

Well, Antlr (http://www.antlr.org/ http://www.antlr.org/) has replaced yacc for most of the practical work already. Daniel Spiewak also mentions parser combinators and how GLL parsers can be much easier to use and yet fast enough most of the time (http://www.codecommit.com/blog/scala/unveiling-the-mysteries-of-gll-part-1 http://www.codecommit.com/blog/scala/unveiling-the-mysteries...). He mentions parser combinators as domain specif languages for creating parsers (http://www.codecommit.com/blog/scala/the-magic-behind-parser-combinators http://www.codecommit.com/blog/scala/the-magic-behind-parser...). Despite all of these, adoption of better techniques is really slow. As usual.

sliverstorm 16y ago
Heh... Yacc, Bison, Antlr...

johkra 16y ago

What is actually state-of-the-art in parsing? When I, as an Amateur, last looked into it, PEG[1] and extensions like OMeta[2] seemed to be the best options. I've heard good things about Parsec[3], too. [1](http://en.wikipedia.org/wiki/Parsing_expression_grammar http://en.wikipedia.org/wiki/Parsing_expression_grammar) [2](http://www.tinlizzie.org/ometa/ http://www.tinlizzie.org/ometa/) [3](http://legacy.cs.uu.nl/daan/parsec.html http://legacy.cs.uu.nl/daan/parsec.html)

sb 16y ago
I am not so sure about the actual state-of-the-art (I have read some PEG papers and some OMeta stuff from vpri, plus used ANTLR, Bison, and Coco/R), but a very interesting comment on HN (http://news.ycombinator.com/item?id=1643715 http://news.ycombinator.com/item?id=1643715) points out that most production compilers use hand-written recursive-descent parsers, primarily due to practical reasons. I have taken two compiler construction courses during my college years, one with LL(1) grammar using a recursive descent parser, the other one with LR(1) grammar using flex+bison tool-chain. I found the experience from the LL case helped me tremendously in the course of writing the LR-language compiler. I think that recursive-descent experience also helps understanding attribute grammars, too. Probably the best introduction to recursive-descent parsers is from Niklaus Wirth's compiler construction book (http://www-old.oberon.ethz.ch/WirthPubl/CBEAll.pdf http://www-old.oberon.ethz.ch/WirthPubl/CBEAll.pdf).
- krakensden 16y ago
  What are the practical reasons? Dealing with non-uniform edge cases and other strange constraints? Integrating the stuff the compiler needs to do with the parser-generator?
  - k4st 16y ago
    I can imagine one practical reason is that a lot of stuff (e.g. type information, variable bindings) goes top-down, but bottom-up parsers reduce rules in the opposite direction and so it takes extra effort to make the mental model of programming fit with the reduction strategy of bottom-up parsers.

fizx 16y ago

Here's what a grammar actually looks like in their scala version. This grammar is for arithmetic over the language where x represents 1, and s represents +. This only generates the parse tree, not the final answer. Comments are added by me: // The Nodes in the parse tree abstract class Exp case object One extends Exp case class Sum(e1 : Exp, e2 : Exp) extends Exp // Terminals lazy val S : Parser[Char,Char] = new EqT[Char] ('s') lazy val X : Parser[Char,Char] = new EqT[Char] ('x') // Definition of an expression // I'm pretty sure all the asInstanceOfs are avoidable/unnecessary. lazy val EXP : Parser[Char,Exp] = rule(X) ==> { case x => One.asInstanceOf[Exp] } || rule(EXP ~ S ~ EXP) ==> { case e1 ~ s ~ e2 => Sum(e1,e2).asInstanceOf[Exp] } || rule(EXP ~ S ~ X) ==> { case e1 ~ s ~ e2 => Sum(e1,One).asInstanceOf[Exp] } || rule(X ~ S ~ EXP) ==> { case e1 ~ s ~ e2 => Sum(One,e2).asInstanceOf[Exp] } || rule(X) ==> { case x => One.asInstanceOf[Exp] } || rule(EXP) ==> { case e => e } || rule(Epsilon[Char]) ==> { case () => One } // Actually run the rule val xin = Stream.fromIterator("xsxsxsxsx".elements) EXP.parseFull(xin) // return value => Stream(Sum(One,Sum(Sum(One,One),Sum(One,One))), ?)

kleiba 16y ago

Do I hear John McCarthy chuckle?

mattmight 16y ago

(Article author here.) I'm delighted to see this get some attention here. I absolutely love these techniques for parsing, but as my primary research areas is static analysis, I haven't had time to revise this paper and resubmit. As it stands, I may never get the time to do so. :( I posted it on arxiv so that David could reference it for his Ph.D. school apps. Since some of you have asked, here are the reviews: http://matt.might.net/papers/reviews/esop2010-derivatives.txt http://matt.might.net/papers/reviews/esop2010-derivatives.tx... I do have an updated implementation that's much cleaner and faster, and I've been planning to do that in a blog post. (Alas, no opportunity yet.) David's also done another implementation in Haskell that's screaming fast and efficient on many restricted classes of grammars (like LL(k)). I'll encourage him to post that as well. If you're interested in getting your name on a scientific publication and helping this get the attention of the scientific community, you can help us by creating an implementation of either technique in your favorite language and beating on it to help find the inefficiencies. (For instance, the original Scala version linked from this paper has memory leaks from the way it caches derivatives. We got around them by rolling top-level repetition by hand.) Please email me if that's something you're interested in doing. Can HN do science? I'd love to find out.

k4st 16y ago
I haven't finished the paper yet, but this type of technique excites me as well. Recently, I did an assignment on the paper "memoization in top-down parsing" by Mark Johnson. Have you seen this paper, and do you think that there are any similarities between the derivatives of a CFG and continuations of parsing procedures (for variables and their related productions)?
- mattmight 16y ago
  I'll have to check out Mark's paper, but just by your description, I bet they're related. For finite-state and pushdown automata, derivatives and continuations are two sides of the same coin.
copper 16y ago
"this is not quantum theory, after all..." is one of the funnier comments I've seen on a review. Judging by the rest of it, I'm tempted to guess that it was written by someone from team-PLT :) Could either you or David put the source for the LL(k) version up somewhere? Comparing it head-to-head with parsec (or its faster cousins) something fun to do.

benblack 16y ago

So many useful links in this discussion, I consolidated them (and a few extras) here http://post.b3k.us/modern-parsing-bibliography http://post.b3k.us/modern-parsing-bibliography

herdrick 16y ago

Better comments at programming.reddit, sadly: http://www.reddit.com/r/programming/comments/ed2pb/yacc_is_dead/ http://www.reddit.com/r/programming/comments/ed2pb/yacc_is_d...