Path: csiph.com!weretis.net!feeder6.news.weretis.net!feeder.usenetexpress.com!feeder-in1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Ben Hanson Newsgroups: comp.compilers Subject: Re: re2c-1.0 released! Date: Mon, 4 Sep 2017 05:19:49 -0700 (PDT) Organization: Compilers Central Lines: 54 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <17-09-011@comp.compilers> References: <17-08-007@comp.compilers> <17-09-001@comp.compilers> <17-09-003@comp.compilers> <17-09-010@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="38646"; mail-complaints-to="abuse@iecc.com" Keywords: lex, design Posted-Date: 04 Sep 2017 10:58:59 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:1916 On Sunday, 3 September 2017 18:44:57 UTC+1, Ulya Trofimovich wrote: > 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. Ah, overheads. I'm guessing you're being a bit gloomy there, as "DFA is too slow!" has been the battle cry for NFA advocates for decades now. I didn't believe it in the '90s and I don't believe it now. However, you raise an interesting point. There are plenty of regexes I use at work that are fixed, so they could indeed just use generated code to save the construction cost at runtime. The only reason I haven't done this up until now is that it makes maintenance easier to just have a string you can tweak directly in the source. The holy grail (I believe) is sufficiently powerful meta-programming to do the whole thing at compile time, although you could of course do it today with custom build steps to generate code via re2c or whatever other tool (that kind of thing tends to scare developers where I work). When I want lookup speed I use my own (runtime) lexer generator with a single rule of interest, and then a single skip rule for anything else. This works very well and I'm sure re2c could easily be used the same way. I'm currently playing with searching using LALR(1) grammars and have written a search tool gram_grep which I will be extending soon. I would like to put together an LR(*) algorithm to make defining rules easier for people, but I don't know when I'll have the time to really get into that. I believe there are many more possibilities for text processing than the traditional tools everyone normally turns to and I applaud your efforts in bringing TDFA to re2c! Regards, Ben