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

Groups > comp.compilers > #1915

Re: re2c-1.0 released!

Path csiph.com!3.us.feeder.erje.net!feeder.erje.net!news.linkpendium.com!news.linkpendium.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From Ulya Trofimovich <skvadrik@gmail.com>
Newsgroups comp.compilers
Subject Re: re2c-1.0 released!
Date Sun, 3 Sep 2017 18:31:39 +0100
Organization Compilers Central
Lines 31
Sender news@iecc.com
Approved comp.compilers@iecc.com
Message-ID <17-09-010@comp.compilers> (permalink)
References <17-08-007@comp.compilers> <17-09-001@comp.compilers> <17-09-003@comp.compilers>
Mime-Version 1.0
Content-Type text/plain; charset=utf-8
Content-Transfer-Encoding 8bit
Injection-Info gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="55066"; mail-complaints-to="abuse@iecc.com"
Keywords lex
Posted-Date 03 Sep 2017 13:44:54 EDT
X-submission-address compilers@iecc.com
X-moderator-address compilers-request@iecc.com
X-FAQ-and-archives http://compilers.iecc.com
Content-Language en-US
Xref csiph.com comp.compilers:1915

Show key headers only | View raw

> Thanks for this. I will take a look at the implementation when I get
> the time.
>
> I'm most interested in your refinements/bug fixes to the original
> TDFA algorithms and I would like to see this used as a runtime regex
> library more than for a lexer generator.

Using TDFA in a runtime library has certain downsides:

1. It implies the runtime overhead on (lazy) determinization: it's only
useful if the regexp is compiled once and used many times. Libraries
such as RE2 (by Russ Cox) or TRE (by Ville Laurikari) mostly use NFA for
submatching.

2. Also, due to ahead-of-time compilation lexer generators are able to
perform extensive optimization of the generated code, including
minimization of the number of submatch variables and operations on them.
A runtime library cannot afford that.

However, if TDFA algorithm is to be used in a library, then my paper
contains two improvements worth consideration:

1. TDFA(1) with one-symbol lookahead instead of default TDFA(0)

2. Formal algorithm for POSIX disambiguation semantics.

I'd be glad to answer any questions anyway.


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