Re: re2c-1.0 released!

> I don't know what this means ... every NFA has an equivalent DFA, so
> if a problem can be solved with NFA, it can be solved with DFA.


My wording is bad, sorry. I should have put it this way: regular
expression parsing (and submatch extraction as a special case of it) can
be solved on nondeterministic finite state transducers (NFST). And NFST
are not equivalent to DFST, despite the fact that NFA are equivalent to DFA.


Traditional NFA can be trivially converted to NFST by augmenting their
transitions with output symbols and extending the simulation procedure
to write these output symbols. In case of submatch extraction it means
equipping each path through NFA with a set of registers -- a pair per
capturing group -- that are updated during simulation.


However, NFST determinization is non-trivial. That was my point.


>> It may seem that only a lack of effort prevents developers of lexer
>> generators like Flex from implementing it (as well as fixing the
>> ever-broken trailing contexts [3]).
>
>Lack of justification due to, I suspect, lack of demand from
>sophisticated users of the tools, who use them for their intended
>purpose.


Well, the simple use case that I had in my mind was re2c's own lexer
(yes, re2c is self-hosted): it has a lexeme of the form
"{[0-9]+,[0-9]+}" that is used to denote bounded repetition of the given
regular expression. Without submatch extraction the rule looks like this:


        "{" [0-9]+ "," [0-9]+ "}" { ... strchr(token, ',') ... }


It is necessary to call 'strchr' to retrieve the position of the comma.
It would be nice if the lexer stored the position in a variable as it goes:


        "{" [0-9]+ @p "," [0-9]+ "}" { ... p /* points to ',' */ ... }


But there are other, more complex use cases, like parse URI or HTTP
messages:


http://re2c.org/examples/example_10.html
http://re2c.org/examples/example_11.html


This technique is already applied by re2c users, so at least someone
somewhere finds it handy. ;)




Ulya

Return to the comp.compilers page.
Search the comp.compilers archives again.