I've been worrying a lot about the next stage of my project and realizing that I had seriously screwed up somewhere along the way. The next task on my list is to convert the recognizer into a parser.

I'm going to refer to a couple of different things here. A quick bibliography:

  * [Herp, Rerp, and Derp](https://github.com/plum-umd/parsing-with-derivatives/blob/master/racket-code/racket-10-12/) all refer the final variants produced by David Darais in 2011, after Matt Might's original code.
  * [Adams 2016](https://bitbucket.org/ucombinator/derp-3) refers the the Derp-3 implementation in Racket, which as far as anyone knows has the greatest number of optimizations.
  * [McGuire 2012](https://maniagnosis.crsr.net/2012/04/parsing-with-derivatives-introduction.html) refers to Tommy McGuire's Java implementation.

There are three different main issues that need to be covered by this code.

First is the generation of a new parser for each new character, in much the same way that parser combinators work, and ideally this new parser is lazy, in that it doesn't actually recurse down a tree until an item is needed, and that once the item has been generated it is memoized so that it doesn't need to be generated a second time.

Second is the determination of nullability. Since these parsers are defined equationally, then given a language 𝑳, we calculate the fixed point of 𝑳 in the classic way: Feed 𝑳 into the equations repeatedly until 𝑳 doesn't change. This derivative of 𝑳 is both non-recursive and efficient.

Third is the extraction of the result from the language. This is where I'm a bit stuck, and trying to reverse-engineer the result from the code examples above.

The problem I have at the moment is that there appears to be two different ways of calculating and managing the the nullability and extraction issues. To understand the issue, you have to know that nullability is important not just when determining whether or not the parser is done, but whenever the parser needs to do concatentation, the single most common operation in regular expressions; for concatenation, the next parser-combinator generated is different depending on whether or not the first symbol in the concatenation machinery is nullable. In Matt Might's original Parsing With Derivatives: A Functional Pearl, he has a simple nullability function for recognition, but uses a different nullability function, a sort of "automatic cancellation" feature, in concatenation. McGuire also goes this route.

Darais goes back to the original way of doing things: Nullability is a simple true/false operation with no special behavior. It's effects on other equations are handled in those equations as special constructors, which is very useful when the constructors make decisions not about themselves, but about the results of their derivatives, a two-level analysis for performance reasons.

Adams goes even further; his code is deeply optimized with some very powerful features, but the biggest problem I have is that he does productions piecewise in order to reduce the length of the analysis chain the further into the expression you go. This kind of optimization is highly challenging in a strongly typed language like Rust, which is Why I've been having such a hard time with it.

Adams does this with "Reductions," which Might introduced in his original paper in the context of discussing parser combinators, using them interleaved with the parsing process, which again, is a challenge in a typed language.

This week, I'm going to focus on very small incremental features. I'm just going to implement Literals and Alternatives, and see if I can't get logical extractions out of them. If I can, then I'll try and get Concatenation working.

My fear is that, when that time comes, I'll have to implement Reductions as well. Since I've been using this project as a way to learn Rust, I've not yet delved into some deeper parts of it, like, for example, function pointers, which is how Reductions are stored. This should be fun.