[Python-Dev] Re: Automatic flex interface for Python?

[François Pinard]

[Skip Montanaro]

> The SpamAssassin folks are starting to look at Flex for much faster
> regular expression matching in situations where large numbers of static
> re's must be matched.

This problem was also vivid in `procmail'-based SPAM filtering, as I observed
it many years ago, and I remembered having quite lurked on the side of Flex
at the time.  I finally solved my own problem by writing a Python program
able to sustain thousands of specialised rules rather speedily, proving once
again that algorithmic approaches are often much slower than languages :-).

> I wonder if using something like SciPy's weave tool would make it
> (relatively) painless to incorporate fairly high-speed scanners into
> Python programs.

For a pure Python solution, PLEX could also be an avenue.  It compiles a fast
automaton, similar to what Flex does, from a grammar describing all tokens.
I tried PLEX recently and was satisfied, even if not astonished by the speed.
Also wanting fast parsing, I first used various Python heuristics, but the
result was not solid enough to my taste.  So I finally opted for Bison,
and once on that road, it was just natural to rewrite the PLEX part in Flex.

[Guido van Rossum]

> I think you're exaggerating the problem, or at least underestimating
> the re module.  The re module is pretty fast!

There are limits to what a backtracking matcher could do, speed-wise,
when there are many hundreds of alternated patterns.

[Eric S. Raymond]

> It's pretty simple, actually.  Lexing *is* tokenizing; it's breaking the
> input stream into appropopriate lexical units.  [...]  Parsing, on the
> other hand, consists of attempting to match your input to a grammar.
> The result of a parse is typically either "this matches" or to throw
> an error.  There are two kinds of parsers -- event generators and
> structure builders.

Maybe lexing matches a grammar to a point, generates an event according to
the match, advances the cursor and repeats until the end-of-file is met.
Typically, parsing matches a grammar at point and does not repeat.

In some less usual applications, they may be successive lexing stages,
each taking its input from the output of the previous one.  Parsing may
be driven in stages too.  I guess that we use the word `lexer' when the
output structure is more flat, and `parser' when the output structure is
more sexy!  There are cases where the distinction is almost fuzzy.

[Skip Montanaro]

>     Guido> I haven't given up on the re module for fast scanners (see
>     Guido> Tim's note on the speed of tokenizing 20,000 messages in
>     Guido> mere minutes).  Note that the Bayes approach doesn't *need*
>     Guido> a trick to apply many regexes in parallel to the text.

> Right.  I'm thinking of it in situations where you do need such tricks.
> SpamAssassin is one such place.  I think Eric has an application (quickly
> tokenizing the data produced by an external program, where the data can
> run into several hundreds of thousands of lines) where this might be
> beneficial as well.

Heap queues could be useful here as well.  Consider you have hundreds of
regexps to match in parallel on a big text.  When the regexp is not too
complex, it is more easy or likely that there exists a fast searcher for it.
Let's build one searcher per regexp.  Always beginning from the start of
text, find the spot where each regexp first matches.  Build a heap queue
using the position as key, and both the regexp and match data as value.

The top of the heap is the spot of your first match, process it, and while
removing it from the heap, search forward from that spot for the same regexp,
and add any result back to the heap.  Merely repeat until the heap is empty.

I'm not fully sure, but I have the intuition the above could be advantageous.

-- 
François Pinard   http://www.iro.umontreal.ca/~pinard