5 ms·

Are there any significant languages that do parsing with derivatives?

• mhh__ 5y ago
  What are derivatives in this context?
  • olzd 5y ago
    Probably Brzozowski’s derivative of regular expressions, e.g https://matt.might.net/papers/might2011derivatives.pdf https://matt.might.net/papers/might2011derivatives.pdf
  • drdeca 5y ago
    From what I can find, in the case of regexes, the derivative of a regex R with respect to a character c, is the regex \partial_c R , which matches a string S iff R matches c S. So, the derivative of (ab)* with respect to the character 'a' , would be b(ab)* . I imagine that the same idea applies for more general languages, so, I expect the derivative of a language with respect to a character, is the language of strings such that prepending one by the character results in a string of the original language. So, if R_1 and R_2 are two different regexes, then the derivative with respect to c of the regex R_1 | R_2 , i.e. \partial_c (R_1 | R_2) , would be (\partial_c R_1) | (\partial_c R_2), and, if + is used for concatenation of two regexes, the derivative of R_1 + R_2 would be, ((\partial_c R_1) + R_2) | ((if R_1 accepts the empty string, then the language which accepts only the empty string, otherwise, the language that does not accept any string) + (\partial_c R_2)) etc. ... I think.