Improving std.regex(p)

[Andrei Alexandrescu]

Ellery Newcomer wrote:
> On 06/18/2010 06:36 AM, Ben Hanson wrote:
>> Reading your original post again and thinking about this a bit more...
>>
>> If someone can help me get up to speed with TMP in D, I could probably 
>> put
>> together a proof of concept pretty quickly. Aside from the D syntax, 
>> it is all
>> in the design (which is why I would like to discuss it in more 
>> detail). For
>> anyone who is interested, here is how I go about DFA production 
>> currently:
>>
>> - Bog standard tokenisation of regex tokens
>> - Normalise each regex charset and enumerate in a map
>> - build a regex syntax tree with leaf nodes storing the enumerated 
>> charset id
>> - Intersect all the charsets and build a vector of equivalent charsets
>> - Perform the followset to DFA transform as described in the Dragon book
>>
>> For my lexer generator, I build a lookup table for each character to an
>> equivalence class. For my wild card matcher, I leave the 
>> representation as
>> characters and do a linear lookup of chars to 'next' state. The lexer
>> equivalence class method (a la flex) is more efficient as you just 
>> have two
>> lookups per character with no linear searches.
>>
>> I'm thinking I could look at getting as far as the regex syntax tree 
>> and then
>> we could discuss DFA representation (it sounds like you want to 
>> generate code
>> directly - how do you do that?! This is why I mentioned the .NET 
>> bytecode stuff
>> - I imagine there is some overlap there, but I don't know enough to be 
>> sure.
>> Can you output source code at compilation time and have D compile it, 
>> or do you
>> use a load of recursion like C++ TMP?
>>
>> And I forgot to mention - boost.spirit uses my lexertl library.
>>
>> Regards,
>>
>> Ben
> 
> I've always understood that dfas have an exponential lower bound 
> relative to .. something .. but I don't believe I have ever actually 
> used a dfa generator (or written one, sadly enough). What has your 
> experience been on dfa compile time?

I think only backtracking engines (not DFAs) have the exponential run 
time problem. Regular expression grammar is itself context free (so it's 
parsable efficiently), the NFA and NFA->DFA algorithms are polynomial, 
and the generated DFA makes one transition per input character.


Andrei