Do I hear John McCarthy chuckle?
Yacc is dead
21–30 of 45 posts
Re: Yacc is dead
#22What 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 ) [2]( http://www.tinlizzie.org/ometa/ ) [3]( http://legacy.cs.uu.nl/daan/parsec.html )
There was a really cool parsing paper at POPL this year [1] that goes 'beyond CFGs'... but as far as I know their system YAKKER is still in development / unreleased. I think from a user's perspective, e.g. someone wanting to design a DSL, it would be nice to be able to write down arbitrary CFGs and not necessarily have to know lots of technical parsing details ("what are all these shift-reduce conflicts!?"). Maybe PE…
PDF of paper that isn't behind a paywall: http://www2.research.att.com/~yitzhak/publications/ddg-tr.pd...
Re: Yacc is dead
#23What 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 ) [2]( http://www.tinlizzie.org/ometa/ ) [3]( http://legacy.cs.uu.nl/daan/parsec.html )
There was a really cool parsing paper at POPL this year [1] that goes 'beyond CFGs'... but as far as I know their system YAKKER is still in development / unreleased. I think from a user's perspective, e.g. someone wanting to design a DSL, it would be nice to be able to write down arbitrary CFGs and not necessarily have to know lots of technical parsing details ("what are all these shift-reduce conflicts!?"). Maybe PE…
The PDF from AT&T Labs for those of us without ACM digital library access:
http://www2.research.att.com/~yitzhak/publications/ddg-tr.pd...
Re: Yacc is dead
#24Earlier quoted context omitted.
You mean something like this?: 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 s…
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 pa…
Is it me or this would fit quite nicely into an IDE (ie. the language-specific editor) ?
Re: Yacc is dead
#25Earlier quoted context omitted.
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 pa…
Is it me or this would fit quite nicely into an IDE (ie. the language-specific editor) ?
I think it would but regexps are not enough to parse most interesting languages. Perhaps you could extend it to general parsers, but I think it may be impossible to do it efficiently for general context sensitive parsers, because unlike regular expressions the parser can be in infinitely many different states when it arrives at the substring. Perhaps laziness can do some tricks though. Anyone have some ideas?
Re: Yacc is dead
#26Well, Antlr ( 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... ). He mentions parser combinators as domain specif languages for creating parsers ( http://www.codecommit.com/blog/scala/the-ma…
Heh... Yacc, Bison, Antlr...
Re: Yacc is dead
#27Brzozowski's derivatives of regular expressions has been in use in the PLT compiler tools for ages now.
Re: Yacc is dead
#28(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.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.
Re: Yacc is dead
#29What 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 ) [2]( http://www.tinlizzie.org/ometa/ ) [3]( http://legacy.cs.uu.nl/daan/parsec.html )
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 ) 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…
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?
Re: Yacc is dead
#30(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:/…
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)?