18
$\begingroup$

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?

$\endgroup$
  • 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$ – Sylvain Nov 23 '10 at 21:54
  • $\begingroup$ do you mean generalizations to more complex languages, like regular < context-free < context-sensitive < ... ? $\endgroup$ – s8soj3o289 Nov 24 '10 at 9:50
  • $\begingroup$ I've been looking at subsystems of CFGs roughly in the neighborhood of VPLs, mostly. $\endgroup$ – Neel Krishnaswami Nov 24 '10 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$ – Sylvain Nov 24 '10 at 12:15
  • $\begingroup$ arxiv.org/abs/1604.04695 $\endgroup$ – Mehrdad Feb 11 '17 at 9:08
7
$\begingroup$

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.

$\endgroup$
12
$\begingroup$

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:

$\endgroup$
  • $\begingroup$ Very funny paper title! :-) $\endgroup$ – Dai Le Nov 26 '10 at 6:32
7
$\begingroup$

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?

$\endgroup$
  • $\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$ – Neel Krishnaswami Nov 24 '10 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.