From: Peter Zotov <whitequark@...>
Date: 2011-03-01T22:41:59+09:00
Subject: Re: Automatic question generator libs in Ruby Language

 On Tue, 1 Mar 2011 22:15:45 +0900, Adam Prescott wrote:
> On Tue, Mar 1, 2011 at 12:28 PM, Peter Zotov
> <whitequark@whitequark.org>wrote:
>
>> On Tue, 1 Mar 2011 20:02:13 +0900, Adam Prescott wrote:
>>
>>>
>>> This could be a long rabbit hole.
>>>
>>>
>> Well, you've started this. Now I shall show you what a rabbit hole 
>> is ;)
>>
>> [impressiveness]
>>
>>
> Hm!
>
> opine = "You think ' is an excellent grapheme?" # arguably this is a 
> valid
> fully-formed question...
>
> questions(opine) # endless loop!

 A debug modification has accidentally slipped through. The regexp 
 should have been defined this way:

 QUESTION_REGEXP = Regexp.compile(<<'END'.strip, Regexp::EXTENDED | 
 Regexp::MULTILINE)
 (?<mstc>\g<inf>[!?.]?\s*){0}(?<stc>\g<inf>[!?.]\s*){0}(?<text>[^!.?]+?){0}
 (?<inf>(?<pq>["'])\g<mstc>\k<pq+0>\g<inf>|«\g<mstc>»\g<inf>|\g<text>\g<inf>|){0}
 \g<stc>
 END

 (look at the last [] in first line: it has ' removed).

 I am aware of this problem. (I hadn't written about it because of 
 several reasons: I don't know what exactly causes it, and I wanted to 
 see if someone would trigger it — congratulations. Given the time this 
 regexp executes even on a simple strings, the code is already not suited 
 for production, and this small misinformation would not hurt the OP.)

 I've triggered it several times while trying different forms of the 
 regexp, and sometimes it occurs when using one of seemingly equivalent 
 constructs, but does not occur with other one. A quick look at some 
 backtraces taken at random times during the execution suggests that it 
 really loops (and not just executes for a lot of time), but oniguruma is 
 really huge and complex, and I don't have enough time to debug this.

 Also, as I am not a regular expression guru, it may contain blatant 
 errors. (I've seen once a book on optimizing regexps. It was scary.) 
 I've tried to use my experience with LALR parsers here, but sometimes 
 oniguruma behaves in a completely different way. E.g. at the some point 
 I've tried to replace an empty token at the end of (?<inf>...) group 
 with a plain \g<text>, which of course includes empty string, it would 
 not compile due to _indefinite recursion_. It works perfectly with 
 current variant. The (?<text>...) token always was a terminal, of 
 course.

 The ideal way of accomplishing this task would be using a lexer and a 
 parser; it is easy enough to write them manually in this case (as 
 opposed to using a tool like RACC). Thus, one would create a finite 
 state machine, which is what regular expression compiler does, too, but 
 the former will be optimized properly.

 I'll leave this as a homework to someone else :)

-- 
   WBR, Peter Zotov.

 P.S. Given that Oniguruma RE can compile a full LALR parser, I wonder 
 how a regular expression matching a regular expression look like. And 
 the amount of time and memory it will use.