"Parsing with Derivatives" is the title of a 2011 paper by Matt Might, David Darais, and Daniel Spiewak that generalizes the Brzozowski derivative from regular expressions to context-free grammars. In the present discussion, I assumed the context to be about CFGs instead of REs because that is most often what people are referring to when we talk about parsers in programming languages, though I admit that I could have been more explicit about this.
What you linked is an improvement of the Brzozowski derivative, but it does not constitute a parser for CFGs.
According to "Parsing Techniques: A Practical Guide" [1], it is quite common for computer languages to have most of the grammar in the regular grammars class and some parts to be, actually, context-free.
For example, consider addition and subtraction in most grammars. They can be expressed as "summation ::= factor ((PLUS | MINUS) factor) * " and factor can be similarly defined as "factor ::= multiplicand ((MUL | DIV) multiplicand) * ".
Authors of PTAPG note that these regularities can be exploited for speed. And I think "parsing with derivatives" techniques can be used for speedy parsing too.
Uhh sure, but you're kind of deflecting. The phrase "parsing with derivatives" (or "Might's 'Parsing with Derivatives'" as I wrote in my initial comment to which you first replied) refers specifically to the technique developed by Might et al that generalizes the Brzozowski derivative to CFGs. And, more to the point, their technique has very poor performance, which is addressed directly in the paper.
If you talk to parsing people about "parsing with derivatives", they will undoubtedly assume that you specifically mean the Might et al work and not some other, more general notion, regardless of whether one could technically call such notion a "parsing with derivatives" technique. I have never heard of anybody calling anything else "parsing with derivatives" and, indeed, the paper you linked never uses this phrase (the closest they come is "matching with derivatives", which is a bit different in semantics).
I appreciate the points you've raised, and I do think the RE-parsing paper you linked previously looks very interesting (I hadn't seen it before), but the crux of the issue is that you misinterpreted what I said and haven't yet acknowledged that misinterpretation. Instead, it feels like you're trying to fight me on other points to win back some ground or something, though I hope I'm just misreading this because I find that kind of a frustrating conversational method.
My point was that "parsing with derivatives" not necessarily a slow thing and I provided example supporting that point.
I specifically has been searching for performant regular expression library recently. The "parsing with derivatives" approach can share more of the state, I believe, when doing several matches in parallel (think about trie-encoded dictionary) than DFA-based libraries do and should have smaller startup time.
I have not misinterpreted your argument. I have provided a point where it does break because I consider that point important. The reader of our conversation will, from now on, I hope, not consider the original "parsing with derivatives" paper as the state of the art and, probably, will come up with something himself.
I, actually, did and I am glad you answered my points. They made me thinking.
I think that parsing with derivatives can be used as a tool to parse (in parallel! possibly sharing derivatives computed!) parts of text with regular subgrammars and then something like CYK can be applied (again, in parallel like in [1]) to the regions parsed.
Please note that in [1] they show that chart parsing struggle with exactly regular subgrammars - typical chart parsing algorithm has O(n^2) complexity for repetitions expressed with asterisk in regular grammars. I do not think my "solution" is necessarily better than in the [1], but I think I have to think about it more.
I want to preface this by saying that most of this comment is kind of blunt and wordy, but I really don't intend it to be taken rudely. I just wanted to address your points very explicitly to explain my position more clearly. I value your contributions and hope you'll take this response in the spirit I intend it.
> My point was that "parsing with derivatives" not necessarily a slow thing and I provided example supporting that point.
I actually don't think you supported this point, because I specifically said (emphasis new):
> A fun one to include might be Might's "Parsing with Derivatives", which is algorithmically novel (though not very performant).
I was explicitly talking about the 2011 paper titled "Parsing with Derivatives" which generalizes Brzozowski's derivatives from REs to CFGs, and which has absolutely terrible performance compared to most other parsers for CFGs.
You went on a bit of a tangent by arguing about "using derivatives to parse REs in general" (to paraphrase). This was never the scope of what I was talking about. Whether derivatives can be used to parse REs efficiently is irrelevant when I was specifically referring to the 2011 paper, which provides a novel, general parsing algorithm — not LL, not LR, not GLL, not GLR, but just "general", for all CFGs in existence.
> I have not misinterpreted your argument. I have provided a point where it does break because I consider that point important.
I still think you misinterpreted me, because you're talking about "how can derivatives be used to parse things efficiently" while I was talking about "the contributions of this specific 2011 paper that introduced a new general parsing algorithm that can handle all CFGs and which happens to be called 'Parsing with Derivatives'".
At this point I want to say that I'm not trying to be mean here, and I really hope that's not how I'm coming across. I just think something isn't connecting in our dialogue, so I'm trying to be overly explicit and cautious in my wording to make sure I don't introduce any possibility for misinterpretation.
> The reader of our conversation will, from now on, I hope, not consider the original "parsing with derivatives" paper as the state of the art and, probably, will come up with something himself.
See, this is the thing. The 2011 paper I referenced isn't about REs, but your papers were about REs. The 2011 paper introduced a brand-new general parsing algorithm to the world. It was subsequently refined by Adams, Hollenbeck, and Might in 2016's "On the Complexity and Performance of Parsing with Derivatives" [0], and then again refined by Darragh and Adams in "Parsing with Zippers" [1] (published at ICFP this year). To the best of my knowledge, the materials you've linked so far do not even reference the 2011 paper and so cannot be said to improve on the state of the art in that regard, where "state of the art" refers to "state of parsing all CFGs using a derivative-based approach rooted in the Brzozowski derivative". They instead start with the 1964 Brzozowski paper that originated the derivative of regular expressions and improve on that directly — meaning they are not addressing CFGs in general, as the 2011 paper I was talking about does. Your paper and the 2011 paper are more like siblings in that they both descend from the same 1964 paper, but solve different problems. So I think it would be misleading to suggest that your paper is an improvement on the state of the art of the 2011 paper because they're really very different problem domains, despite both involving "parsing" and "derivatives".
> I think that parsing with derivatives can be used as a tool to parse (in parallel! possibly sharing derivatives computed!) parts of text with regular subgrammars and then something like CYK can be applied (again, in parallel like in [1]) to the regions parsed.
So, if I'm understanding you right, you're suggesting using a hybrid approach. I think that's an interesting idea! I don't know that I've seen much done like that. I do know that CYK is almost completely ignored in PL these days, so perhaps there is some other strategy to use there to augment the derivatives-of-REs subcomponents. I'll have to think about that. What a neat idea!
"Parsing with Derivatives" is the title of a 2011 paper by Matt Might, David Darais, and Daniel Spiewak that generalizes the Brzozowski derivative from regular expressions to context-free grammars. In the present discussion, I assumed the context to be about CFGs instead of REs because that is most often what people are referring to when we talk about parsers in programming languages, though I admit that I could have been more explicit about this.
What you linked is an improvement of the Brzozowski derivative, but it does not constitute a parser for CFGs.