Alexander Leidinger

Just another weblog

Mar
12

Google’s new RE engine

I stum­bled over Google’s new RE engine. Unfor­tu­nately it is not han­dling back­ref­er­ences, so it is not a drop-in replace­ment for the reg­u­lar expres­sions code in FreeBSD. It has a POSIX mode, but this only seems to be enough for the egrep syn­tax. For peo­ple which need back­ref­er­ences, they refer to the Google Chrome’s RE engine irreg­exp which in turn ref­er­ences a paper from 2007 which is titled Reg­u­lar Expres­sion Match­ing Can Be Sim­ple And Fast.

The tech­niques in the paper can not be applied to the irreg­exp engine, but maybe could help to speed up awk, egrep and sim­i­lar programs.

I think it would be inter­est­ing to com­pare those recent devel­op­ments to what we have in FreeBSD, and if they are faster, to see if it is pos­si­ble to improve the FreeBSD imple­men­ta­tion based upon them (either by writ­ing new code, or by import­ing exist­ing code, depend­ing on the cor­re­spond­ing license and the lan­guage the code is writ­ten in).

Maybe a can­di­date for the GSoC?

GD Star Rat­ing
load­ing…
GD Star Rat­ing
load­ing…
Google’s new RE engine, 10.0 out of 10 based on 1 rating
Tags: , , , , , , , , ,

5 Responses to “Google’s new RE engine”

  1. Ollivier Robert Says:

    I still have the goal of import­ing PCRE in the FreeBSD libc…

    GD Star Rating
    loading...
    GD Star Rating
    loading...
  2. Aditya Sarawgi Says:

    Sounds like a nice project for gsoc

    GD Star Rating
    loading...
    GD Star Rating
    loading...
  3. Gabor Kovesdan Says:

    I think for libc TRE is the way to go. But still, PCRE is a good can­di­date for base sys­tem so that tools, like grep can have Perl-syntax sup­port, as well. And this work could serve to review TRE algo­rithms and maybe improve them. TRE is also BSD-licensed and very well doc­u­mented in the author’s MSc thesis.

    GD Star Rating
    loading...
    GD Star Rating
    loading...
  4. Murray Stokely Says:

    That would be an inter­est­ing GSoC project. You should add this to the FreeBSD ideas page.

    GD Star Rating
    loading...
    GD Star Rating
    loading...
  5. netchild Says:

    Or I do not do this and have a look if some­one is read­ing the FreeBSD blogs. Some kind of exper­i­ment to see if peo­ple inter­ested in the GSoC look fur­ther into FreeBSD than just fol­low­ing the link from Google to the FreeBSD ideas page.

    GD Star Rating
    loading...
    GD Star Rating
    loading...

Leave a Reply