Regular Expression Engine in 14 lines of Python

Re:Regular Expression Engine in 14 lines of Python by psykotic on Sunday November 06, 2011 @10:38AM (#3202881)

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

[ Parent | on HN ]

Re:Regular Expression Engine in 14 lines of Python by qntm on Monday November 07, 2011 @09:28AM (#3206353)

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

[ Parent | on HN ]

Re:Regular Expression Engine in 14 lines of Python by psykotic on Tuesday November 08, 2011 @04:23PM (#3212878)

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

    (|a)*

[ Parent | on HN ]

Re:Regular Expression Engine in 14 lines of Python by qntm on Wednesday November 09, 2011 @10:53AM (#3215945)

That's not left-recursion.

[ Parent | on HN ]

Re:Regular Expression Engine in 14 lines of Python by psykotic on Friday November 11, 2011 @09:15PM (#3226918)

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.

[ Parent | on HN ]

Re:Regular Expression Engine in 14 lines of Python by Bjartr on Monday November 07, 2011 @01:14PM (#3207453)

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

[ Parent | on HN ]