Hacker News Reader

Comment by psykotic | Hacker News Reader

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.56...

View on HN

How can this left-recurse? Can you give an example? I thought regular expressions weren't recursive at all.

They're not, most 'regex' engines today aren't actually regular.

The Kleene star is a fixed-point/recursion operator. Here's an example that causes an infinite loop:

    (|a)*

That's not left-recursion.

I 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.

Reply on news.ycombinator.com