<p>You might be interested in this paper:</p>

<blockquote>
  <p><a href="http://arxiv.org/abs/1010.5023" rel="noreferrer">Yacc is Dead</a> by Matthew Might and David Darais, 2010</p>
  
  <p>We present two novel approaches to
  parsing context-free languages. <strong>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.</strong> 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.</p>
</blockquote>

<p>Also of potential interest:</p>

<ul>
<li><a href="http://research.swtch.com/2010/12/yacc-is-not-dead.html" rel="noreferrer">Yacc is Not Dead</a>, review of this paper by Russ Cox, of <a href="http://code.google.com/p/re2/" rel="noreferrer">re2</a> fame.</li>
<li><a href="http://matt.might.net/articles/parsing-with-derivatives/" rel="noreferrer">Yacc is dead: An update</a>, reply from Matt Might.</li>
<li><a href="http://matt.might.net/papers/might2011derivatives.pdf" rel="noreferrer">Functional Pearl: Parsing with Derivatives</a> by Matthew Might, David Darais and Daniel Spiewak - an updated version of the "Yacc is Dead" paper, presented at ICFP 2011 in Tokyo.</li>
</ul>

CC BY-SA 2.5
2010-11-26T06:32:53.397Z
Very funny paper title! :-)
Dai Le
CC BY-SA 3.0
2010-11-25T11:20:58.247Z
2012-11-06T04:34:26.517Z
2012-11-06T04:34:26.517Z
Mikhail Glushenkov
<p>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. </p>

<p>Lots of nice theory there.</p>

<p>Do you have any specific questions?</p>

CC BY-SA 2.5
2010-11-24T10:52:09.387Z
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?
Neel Krishnaswami
CC BY-SA 2.5
2010-11-24T01:03:54.037Z
2010-11-24T01:03:54.037Z
GHR
<p>In <a href="http://www.cs.nott.ac.uk/~nad/publications/danielsson-parser-combinators.html">Total Parser Combinators</a> (ICFP 2010) I use Brzozowski derivatives to establish that language membership is decidable for a certain class of potentially infinite grammars.</p>

CC BY-SA 2.5
2010-12-16T10:58:40.530Z
2010-12-16T10:58:40.530Z
Nils Anders Danielsson
<p><a href="http://portal.acm.org/citation.cfm?id=321249">Brzozowski's method of derivatives</a> 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?</p>

CC BY-SA 3.0
2017-02-11T09:08:00.753Z
https://arxiv.org/abs/1604.04695
user541686
CC BY-SA 2.5
2010-11-23T21:54:32.687Z
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, (http://dx.doi.org/10.1016/0304-3975(95)00182-4).
Sylvain
CC BY-SA 2.5
2010-11-24T09:50:22.197Z
do you mean generalizations to more complex languages, like regular < context-free < context-sensitive < ... ?
s8soj3o289
CC BY-SA 2.5
2010-11-24T10:53:05.143Z
I've been looking at subsystems of CFGs roughly in the neighborhood of VPLs, mostly.
Neel Krishnaswami
CC BY-SA 2.5
2010-11-24T12:15:45.457Z
... 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).
Sylvain
<reference-request><fl.formal-languages><parsing>
Generalizations of Brzozowski's method of derivatives of regular expressions to grammars?
Neel Krishnaswami
# Generalizations of Brzozowski's method of derivatives of regular expressions to grammars?

(Asked by: username_0 on 2010-11-23)

[Brzozowski's method of derivatives](http://portal.acm.org/citation.cfm?id=321249) 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?

**Tags:** reference-request, fl.formal-languages, parsing
> **Comments:**
> **username_2**: 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, (http://dx.doi.org/10.1016/0304-3975(95)00182-4).  
> **username_3**: do you mean generalizations to more complex languages, like regular < context-free < context-sensitive < ... ?  
> **username_0**: I've been looking at subsystems of CFGs roughly in the neighborhood of VPLs, mostly.  
> **username_2**: ... 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).  
> **username_1**: https://arxiv.org/abs/1604.04695  

---

## 3 answers

### Answer by username_7 on 2010-12-16. Score: 9 | Accepted answer

In [Total Parser Combinators](http://www.cs.nott.ac.uk/~nad/publications/danielsson-parser-combinators.html) (ICFP 2010) I use Brzozowski derivatives to establish that language membership is decidable for a certain class of potentially infinite grammars.


---

### Answer by username_4 on 2010-11-25. Score: 13

You might be interested in this paper:

> [Yacc is Dead](http://arxiv.org/abs/1010.5023) 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](http://research.swtch.com/2010/12/yacc-is-not-dead.html), review of this paper by Russ Cox, of [re2](http://code.google.com/p/re2/) fame.
* [Yacc is dead: An update](http://matt.might.net/articles/parsing-with-derivatives/), reply from Matt Might.
* [Functional Pearl: Parsing with Derivatives](http://matt.might.net/papers/might2011derivatives.pdf) by Matthew Might, David Darais and Daniel Spiewak - an updated version of the "Yacc is Dead" paper, presented at ICFP 2011 in Tokyo.

> **Comments:**
> **username_5**: Very funny paper title! :-)  

---

### Answer by username_6 on 2010-11-24. Score: 8

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?

> **Comments:**
> **username_0**: 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?  

---

