3 ms·
This was a bit of a joke at the time. I'm surprised no-one yet pointed out the bug with unproductive left recursion which haunts this and all other similar matc
by psykotic 15y ago
This was a bit of a joke at the time. I'm surprised no-one yet pointed out the bug with unproductive left recursion which haunts this and all other similar matchers. Harper's classic Proof-Directed Debugging paper shows how to pre-normalize regular expressions to eliminate the issue: http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.5602 http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.56...
- qntm 15y agoHow can this left-recurse? Can you give an example? I thought regular expressions weren't recursive at all.
- Bjartr 15y agoThey're not, most 'regex' engines today aren't actually regular.
- psykotic 15y agoThe Kleene star is a fixed-point/recursion operator. Here's an example that causes an infinite loop: (|a)*
- qntm 15y agoThat's not left-recursion.
- psykotic 15y agoI probably shouldn't have used the 'left' adjective. But that expression results in an unproductive recursion (unproductive meaning that no characters are consumed through each cycle) analogous to what happens when you recursive-descent parse a context-free grammar containing left-recursive productions.