Cool. I came across derivative grammars recently while reading Property-based testing for the people. There, parsers are used to implement data generators for test suites; random input strings are used to generate random test examples, and derivatives of these parsers are used to sample from the possible choices, e.g. to find examples which satisfy some precondition.
When I was back in school, I remember doing some research on grammars. From what I remember the common algorithms mentioned are optimized for a subset of context free grammars and that is how we get some very efficient algorithms.
With it mentioning Earley, I know that reference is full context free grammars which is why the complexity is higher.
What I am not specifically certain about is what a derivative grammar is. I remember hearing about the term (about a decade ago) didn’t really look into it.
The derivative of a set of strings S with respect to a symbol a is the set of strings generated by stripping the leading a from the strings in S that start with a. For regular sets of strings, i.e. sets defined by regular expressions (REs), the derivative is also a regular set.
Cool. I came across derivative grammars recently while reading Property-based testing for the people. There, parsers are used to implement data generators for test suites; random input strings are used to generate random test examples, and derivatives of these parsers are used to sample from the possible choices, e.g. to find examples which satisfy some precondition.
When I was back in school, I remember doing some research on grammars. From what I remember the common algorithms mentioned are optimized for a subset of context free grammars and that is how we get some very efficient algorithms.
With it mentioning Earley, I know that reference is full context free grammars which is why the complexity is higher.
What I am not specifically certain about is what a derivative grammar is. I remember hearing about the term (about a decade ago) didn’t really look into it.
One of the main precursors to this paper is Matt Might’s 2010/2011 paper about parsing with derivatives in Haskell. Might’s paper generalises a much older idea, Brzozowski’s derivatives of regular expressions (1964), see also regular expression derivatives re-examined (2009) which introduces the idea thus:
For more on the topic and also some answers from Matt Might himself -> https://paperswelove.org/2016/video/david-nolen-parsing-with-derivatives/