Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1910

Re: re2c-1.0 released!

Show all headers | View raw

> 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

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

re2c-1.0 released! Ulya Trofimovich <skvadrik@gmail.com> - 2017-08-27 18:25 +0100
  Re: re2c-1.0 released! Kaz Kylheku <398-816-0742@kylheku.com> - 2017-09-02 11:18 -0400
    Re: re2c-1.0 released! anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2017-09-02 17:02 +0000
      Re: re2c-1.0 released! Kaz Kylheku <398-816-0742@kylheku.com> - 2017-09-03 15:14 +0000
      Re: re2c-1.0 released! Ulya Trofimovich <skvadrik@gmail.com> - 2017-09-03 17:58 +0100
      Re: re2c-1.0 released! Ulya Trofimovich <skvadrik@gmail.com> - 2017-09-03 18:31 +0100
        Re: re2c-1.0 released! Ben Hanson <jamin.hanson@googlemail.com> - 2017-09-04 05:19 -0700
          Re: re2c-1.0 released! Ulya Trofimovich <skvadrik@gmail.com> - 2017-09-08 23:40 +0100
  Re: re2c-1.0 released! Kaz Kylheku <398-816-0742@kylheku.com> - 2017-09-02 11:18 -0400
  Re: re2c-1.0 released! George Neuner <gneuner2@comcast.net> - 2017-09-02 14:11 -0400
    Re: re2c-1.0 released! Ulya Trofimovich <skvadrik@gmail.com> - 2017-09-03 09:00 +0100
    Re: re2c-1.0 released! Ben Hanson <jamin.hanson@googlemail.com> - 2017-09-03 03:13 -0700
  Re: re2c-1.0 released! Ben Hanson <jamin.hanson@googlemail.com> - 2017-09-03 03:16 -0700

csiph-web