Yacc is dead

Details Yacc is dead Yacc is dead

2010-10-24

arxiv.org/abs/1010.5023v1

Computer Science

Programming Languages

18 pages; submitted October 2009 to ESOP; rejected

Scientific paper

We present two novel approaches to parsing context-free languages. The first approach is based on an extension of Brzozowski's derivative from regular expressions to context-free grammars. The second approach is based on a generalization of the derivative to parser combinators. The payoff of these techniques is a small (less than 250 lines of code), easy-to-implement parsing library capable of parsing arbitrary context-free grammars into lazy parse forests. Implementations for both Scala and Haskell are provided. Preliminary experiments with S-Expressions parsed millions of tokens per second, which suggests this technique is efficient enough for use in practice.

Affiliated with

Also associated with

No associations

Rating

Yacc is dead does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Yacc is dead, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Yacc is dead will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-93402