Path: csiph.com!xmission!news.snarked.org!border2.nntp.dca1.giganews.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.www.ucenet.org!nerds-end From: Ulya Trofimovich Newsgroups: comp.compilers Subject: re2c-1.0 released! Date: Sun, 27 Aug 2017 18:25:41 +0100 Organization: Compilers Central Lines: 47 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <17-08-007@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Injection-Info: miucha.iecc.com; posting-host="www.ucenet.org:2001:470:1f07:1126:0:7563:656e:6574"; logging-data="80784"; mail-complaints-to="abuse@iecc.com" Keywords: tools, available, lex Posted-Date: 27 Aug 2017 13:45:46 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:1905 Hello everybody, I'm glad to announce the new major release of re2c lexer generator, 1.0. re2c specializes in generating fast and flexible lexers; it was written by Peter Bumbulis around 1994 [0] and since then maintained by many people. See release notes for the full story [1]. The main breakthrough of this release is the addition of fast submatch extraction: re2c now supports capturing groups with POSIX longest-match semantics, as well as standalone capturing "tags" with leftmost greedy semantics. The implementation is based on the efficient novel algorithm [2]. The challenge of adding submatch extraction to a lexer generator is not immediately obvious: this feature is provided by many regular expression libraries and command-line tools like grep and sed. 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]). The truth is, libraries and tools process regular expressions at run time and use NFA-based algorithms when they need submatch extraction. Lexer generators, on the other hand, compile regular expressions to DFA. As it turns out, submatch extraction is inherently more complex than recognition: it can be solved on NFA, but not on (ordinary) DFA. The new algorithm [1] is based on the Tagged DFA invented by Ville Laurikari in 2000 [4]; it also incorporates POSIX disambiguation algorithm informally described by Kuklewicz in 2007 [5]. Any feedback on the new algorithm would be much appreciated. Ulya Trofimovich [0] https://compilers.iecc.com/comparch/article/94-04-115 [1] http://re2c.org/news/release_notes/1_0.html [2] http://re2c.org/2017_trofimovich_tagged_deterministic_finite_automata_with_lookahead.pdf [3] https://ftp.gnu.org/old-gnu/Manuals/flex-2.5.4/html_node/flex_23.html [4] https://laurikari.net/ville/spire2000-tnfa.pdf [5] https://wiki.haskell.org/index.php?title=Regular_expressions/Bounded_space_proposal&oldid=11475