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

41–45 of 45 posts

Re: Yacc is dead

#41

Post by mattmight »

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

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)?

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.

Re: Yacc is dead

#42

Post by copper »

davdar wrote: post #38
copper wrote: post #32

Earlier quoted context omitted.

"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/d…

Thank you!

Re: Yacc is dead

#43

Post by jules »

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:/…

How does your approach compare with Koen Claessen's Parallel Parsing Processes?

http://www.cse.chalmers.se/edu/course/afp/Papers/parser-clae...

I haven't studies either approach well but they seem similar in that both are like a breadth first traversal of the parser combinators, instead of the traditional depth first (backtracking) traversal. That is, when you have a union A u B you process this by advancing both sides in tandem D_c A u D_c B, instead of the traditional approach of first computing all results of A on the entire input and then computing all results of B on the entire input?

Parallel Parsing Processes don't seem to handle left recursion. On the other hand they parse S expressions in linear time without a special coded repetition operation ;)

When I find time I'm going to try to do an F# implementation.

Re: Yacc is dead

#44

Post by davdar »

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

How does your approach compare with Koen Claessen's Parallel Parsing Processes? http://www.cse.chalmers.se/edu/course/afp/Papers/parser-clae... I haven't studies either approach well but they seem similar in that both are like a breadth first traversal of the parser combinators, instead of the traditional depth first (backtracking) traversal. That is, when you have a union A u B you process this by advancing both sid…

Yes, breadth first traversal of the solution space is very similar in spirit to our approach.

I have since completely rewritten the Haskell implementation. You should really check it out, especially if you are thinking about writing one of your own.

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

This implementation no longer requires a special coded repetition operator to get good complexity for regular and LL(k) grammars. This is a result of our progress w.r.t. performance of the theory since the paper's submission. My technique to achieve this uses structure derivatives (context based derivatives, or pseudo-equivalently, continuations) to avoid taking unnecessary parser derivatives. It in a sense "focuses" the parser computation on a small sub-parser.

Ping me if you have any questions; this paper has been getting passed around quite a bit lately and Matt and I have made progress on certain areas since the writing of the paper -- like that of the Rep hack.

Re: Yacc is dead

#45

Post by johnzabroski »

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?

Vladimir Safonov's Trustworthy Compilers is another good reference on this subject, in addition to the books already mentioned here on HN. Safonov works through some examples of real-world languages, and argues why hand-written parsers are superior to Yacc-style parser generators. He gives examples of ALGOL-68 and FORTRAN.

I don't know of any definitive text that covers a wide range of practical examples that I've been totally satisfied with, though. Even Safonov waives his hand a little, saying the parser is the one part of the compiler to be written by the most experienced and best compiler engineer on the team, because it influences the performance of everything after.

Post reply on HN