The Thompson algorithm

Thompson regex algorithm implementation.

Author:
Mathieu Turcotte
Date:
November 2010

To compile on GCC: g++ -std=gnu++0x thompson.cpp

Should compile fine on VS2010.

The regex grammar used:

    <regexp>    ::= <branche> { '|' <branche> }
    <branche>   ::= <fragment> { <fragment> }
    <fragment>  ::= <atome> { '*' | '?' | '+' }
    <atome>     ::= '(' <regexp> ')' | <caractere> | <nombre>
    <caractere> ::= 'a' | 'b' | ... | 'z'
    <nombre>    ::= '0' | '1' | ... | '9'