3 ms·
This is very interesting and I think the performance is pretty good with the right AST. Consider the regular expression "hello". There is no recursion to take
by jhallenworld 11y ago
This is very interesting and I think the performance is pretty good with the right AST. Consider the regular expression "hello".
There is no recursion to take the derivative of this, so O(n):
(, h (, e (, l (, l o))))
but with this AST, you have O(n!):
(, (, (, (, h e) l) l) o)