Brzozowski's method of derivatives is a very pretty technique for building deterministic automata from regular expressions in a nicely algebraic way. I've worked out some cute generalizations of this technique to handle some larger classes of grammars, but the algorithms are straightforward enough that it seems quite possible that they've been discovered before. But Googling references to descendants of this technique doesn't seem to turn up much. Anyone know of anything?
$\begingroup$
$\endgroup$
5
asked Nov 23, 2010 at 11:01
-
2$\begingroup$ I am quite curious about what classes of grammars you are thinking of. About descendants, the technique of Antimirov, which produces nondeterministic automata instead, is very nice: Partial derivatives of regular expressions and finite automaton constructions, TCS 155(2), 1996, (dx.doi.org/10.1016/0304-3975(95)00182-4). $\endgroup$– SylvainCommented Nov 23, 2010 at 21:54
-
$\begingroup$ do you mean generalizations to more complex languages, like regular < context-free < context-sensitive < ... ? $\endgroup$– s8soj3o289Commented Nov 24, 2010 at 9:50
-
$\begingroup$ I've been looking at subsystems of CFGs roughly in the neighborhood of VPLs, mostly. $\endgroup$– Neel KrishnaswamiCommented Nov 24, 2010 at 10:53
-
$\begingroup$ ... but the set of derivatives is not finite then. And indeed if you want something deterministic as with Brzozowski's method, you are probably restricted to DCFLs (thus I imagine it can make sense for VPLs). $\endgroup$– SylvainCommented Nov 24, 2010 at 12:15
-
$\begingroup$ arxiv.org/abs/1604.04695 $\endgroup$– user541686Commented Feb 11, 2017 at 9:08
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
In Total Parser Combinators (ICFP 2010) I use Brzozowski derivatives to establish that language membership is decidable for a certain class of potentially infinite grammars.
$\begingroup$
$\endgroup$
1
You might be interested in this paper:
Yacc is Dead by Matthew Might and David Darais, 2010
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.
Also of potential interest:
- Yacc is Not Dead, review of this paper by Russ Cox, of re2 fame.
- Yacc is dead: An update, reply from Matt Might.
- Functional Pearl: Parsing with Derivatives by Matthew Might, David Darais and Daniel Spiewak - an updated version of the "Yacc is Dead" paper, presented at ICFP 2011 in Tokyo.
answered Nov 25, 2010 at 11:20
-
1
$\begingroup$
$\endgroup$
1
Back in the mid 80's while I was working on recursive ascent parsers and factoring of grammars, I started by defining partial derivatives of grammars.
Lots of nice theory there.
Do you have any specific questions?
-
$\begingroup$ Right now I'm just fishing around for related work. Since I've been thinking mostly of recursive descent parsers, so I would find applications to LR-style parsing like you suggest particularly intriguing. Can you point me at any of your papers? $\endgroup$ Commented Nov 24, 2010 at 10:52