Home > lambdatheultimate > Yacc is dead

Yacc is dead

November 28th, 2010 11:48 admin Leave a comment Go to comments

In Yacc is dead (2010) Matthew Might and David Darais of the University of Utah, Salt Lake City…

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.

It seems every problem in computer science can be solved with either one more level of indirection or a derivative.

Source: Yacc is dead

Related Articles:

  1. Zune Dead, Then Not Dead, Then Officially Dead
  2. Parsing: The Solved Problem That Isn’t
  3. Parsing: The Solved Problem That Isn’t
  4. Dead Pigs Used To Investigate Ocean’s “Dead Zones”
  5. Dead Reckoning For Your Car Eliminates GPS Dead Zones
blog comments powered by Disqus