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

Yacc is dead

arxiv.org

Post reply on HN
Print view View original

31–40 of 45 posts

Re: Yacc is dead

#31

Post by k4st »

krakensden wrote: post #29
sb wrote: post #10

Earlier quoted context omitted.

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?

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.

Re: Yacc is dead

#32

Post by copper »

mattmight wrote: post #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:/…

"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.

Re: Yacc is dead

#33

Post by timtadh »

mattmight wrote: post #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:/…

emailed!

Re: Yacc is dead

#34

Post by fhars »

Zef wrote: post #11
johkra wrote: post #9

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 ) [2]( http://www.tinlizzie.org/ometa/ ) [3]( http://legacy.cs.uu.nl/daan/parsec.html )

State of the art in parsing is SGLR ( http://strategoxt.org/Sdf/SGLR ) and GLL parsing

The SGLR parser in Strtego/XT is not state of the art, at least not for production use. It only supports pure seven bit ASCII, it is a throwback to the 1970ies.

Re: Yacc is dead

#35

Post by sb »

krakensden wrote: post #29
sb wrote: post #10

Earlier quoted context omitted.

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?

The comment I referenced mentions that the context available in recursive-descent parsers can be used for error recovery, e.g., phrase-level recovery. The excellent "Programming Language Pragmatics" by Michael Scott has a good chapter on this, so does "Modern Compiler Design" by Grune, Bal, Jacobs and Langendoen.

Re: Yacc is dead

#38

Post by davdar »

copper wrote: post #32
mattmight wrote: post #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:/…

"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.

Here is the git repo (over http) for my Haskell implementation which exploits the technique to be linear for LL(k) (the Zip module is where this technique is implemented). The constant overhead for the implementation is still extremely high because we need to compute a fixed point computation on the whole parse graph for every input token. I'm working on getting all that down...

http://david.darais.com/git/research/der-parser-3/

Re: Yacc is dead

#39

Post by davdar »

antimatter15 wrote: post #3

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

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/

Re: Yacc is dead

#40

Post by davdar »

mattmight wrote: post #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:/…

Here is my latest Haskell implementation that Matt is referring to (git repo):

http://david.darais.com/git/research/der-parser-3/

Post reply on HN