News for hackers. Stuff that matters.

A comment on Regular Expression Engine in 14 lines of Python. Parent comment

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 ]