| Andrew Cooke | Contents | Latest | RSS | Twitter | Previous | Next

C[omp]ute

Welcome to my blog, which was once a mailing list of the same name and is still generated by mail. Please reply via the "comment" links.

Always interested in offers/projects/new ideas. Eclectic experience in fields like: numerical computing; Python web; Java enterprise; functional languages; GPGPU; SQL databases; etc. Based in Santiago, Chile; telecommute worldwide. CV; email.

Personal Projects

Lepl parser for Python.

Colorless Green.

Photography around Santiago.

SVG experiment.

Professional Portfolio

Calibration of seismometers.

Data access via web services.

Cache rewrite.

Extending OpenSSH.

Last 100 entries

Saturday Surf Sessions With Juvenile Delinquents; Ssh, tty, stdout and stderr; Feathers falling in a vacuum; Santiago 30m Bike Route; Mapa de Ciclovias en Santiago; How Unreliable is UDP?; SE Santiago 20m Bike Route; Cameron's Rap; Configuring libxml with Eclipse; Reducing Combinatorial Complexity With Occam - AI; Sentidos Comunes (Chilean Online Magazine); Hilary Mantel: The Assassination of Margaret Thatcher - August 6th 1983; NSA Interceptng Gmail During Delivery; General IIR Filters; What's happening with Scala?; Interesting (But Largely Illegible) Typeface; Retiring Essentialism; Poorest in UK, Poorest in N Europe; I Want To Be A Redneck!; Reverse Racism; The Lost Art Of Nomography; IBM Data Center (Photo); Interesting Account Of Gamma Hack; The Most Interesting Audiophile In The World; How did the first world war actually end?; Ky - Restaurant Santiago; The Black Dork Lives!; The UN Requires Unaninmous Decisions; LPIR - Steganography in Practice; How I Am 6; Clear Explanation of Verizon / Level 3 / Netflix; Teenage Girls; Formalising NSA Attacks; Switching Brakes (Tektro Hydraulic); Naim NAP 100 (Power Amp); AKG 550 First Impressions; Facebook manipulates emotions (no really); Map Reduce "No Longer Used" At Google; Removing RAID metadata; New Bike (Good Bike Shop, Santiago Chile); Removing APE Tags in Linux; Compiling Python 3.0 With GCC 4.8; Maven is Amazing; Generating Docs from a GitHub Wiki; Modular Shelves; Bash Best Practices; Good Emergency Gasfiter (Santiago, Chile); Readings in Recent Architecture; Roger Casement; Integrated Information Theory (Or Not); Possibly undefined macro AC_ENABLE_SHARED; Update on Charges; Sunburst Visualisation; Spectral Embeddings (Distances -> Coordinates); Introduction to Causality; Filtering To Help Colour-Blindness; ASUS 1015E-DS02 Too; Ready Player One; Writing Clear, Fast Julia Code; List of LatAm Novels; Running (for women); Building a Jenkins Plugin and a Jar (for Command Line use); Headphone Test Recordings; Causal Consistency; The Quest for Randomness; Chat Wars; Real-life Financial Co Without ACID Database...; Flexible Muscle-Based Locomotion for Bipedal Creatures; SQL Performance Explained; The Little Manual of API Design; Multiple Word Sizes; CRC - Next Steps; FizzBuzz; Update on CRCs; Decent Links / Discussion Community; Automated Reasoning About LLVM Optimizations and Undefined Behavior; A Painless Guide To CRC Error Detection Algorithms; Tests in Julia; Dave Eggers: what's so funny about peace, love and Starship?; Cello - High Level C Programming; autoreconf needs tar; Will Self Goes To Heathrow; Top 5 BioInformatics Papers; Vasovagal Response; Good Food in Vina; Chilean Drug Criminals Use Subsitution Cipher; Adrenaline; Stiglitz on the Impact of Technology; Why Not; How I Am 5; Lenovo X240 OpenSuse 13.1; NSA and GCHQ - Psychological Trolls; Finite Fields in Julia (Defining Your Own Number Type); Julian Assange; Starting Qemu on OpenSuse; Noisy GAs/TMs; Venezuela; Reinstalling GRUB with EFI; Instructions For Disabling KDE Indexing; Evolving Speakers; Changing Salt Size in Simple Crypt 3.0.0

© 2006-2013 Andrew Cooke (site) / post authors (content).

Compiling Recursive Descent to Regular Expressions

From: "andrew cooke" <andrew@...>

Date: Sat, 4 Apr 2009 09:20:37 -0400 (CLT)

I just finished some initial tests on "compiling" the recursive descent
parser in LEPL to a discrete finite automata (DFA) using regular
expressions.

There are some limitations, of course - I only change the lower parts of
the tree that match characters.  This is not quite as obvious as it may
sound because my regular expression engine can handle arbitrary Python
objects, so regular expressions do not have to be made of letters.  But I
do need to write the conversion from matcher to regular expression for
each matcher, and currently only handle And, Or, Any, Literal and some
calls to DepthFirst (which is the core repetition matcher).

But even that explanation is not complete, because those matchers are
actually a large fraction of what is used in most parsers (LEPL provides
many more matchers, but they are sugar built on top of these).  In
practice the biggest problem is that arbitrary transforms (functions) can
be invoked on the results as they are generated.

I ameliorated the effect of actions by making composition explicit -
composite actions are now available for inspection internally as lists of
functions, and the regular expression rewriting engine makes use of this
to identify "add" (the function used to combine strings).

Another limitation is that the fastest regular expression engine gives
only a single greedy match.  But a second engine, using a pushdown
automaton, is nearly as fast (see results below) and provides all possible
matches.


Anyway, as an example, here is the regular expression that is
auto-generated for the Float() matcher:
([\+\-]|)([0-9]([0-9])*(\.|)|([0-9]([0-9])*|)\.[0-9]([0-9])*)([Ee]([\+\-]|)[0-9]([0-9])*|)


Note that the code would be even faster if people used the Regexp()
matcher to provide a regular expression directly (which uses Python's fast
"re" library), but then you start to lose some of the other advantages of
LEPL (you only get the greedy match, the syntax is uglier, reuse is
harder).

Even then, I could replace my "greedy" engine with Python's (and keep the
automatic rewriting).  In practice, I don't do that because (1) the regexp
syntax I use is simpler and easier to target and (2) my engine works with
streams of data, while Python's requires (as far as I can tell) that the
string be in-memory (in theory you can use my regexp to parse a file that
is larger than the memory available to Python; testing large files is
still on my todo list).


Anyway, to the performance tests.  I used my standard expressions example,
but "spiced up" to add some complexity (yes, this improves the results
below).  So instead of matching integers I match float values (including
exponents).

The expression to match is '1.2e3 + 2.3e4 * (3.4e5 + 4.5e6 - 5.6e7)'

The results are (in arbitrary units):
Default config: 5.8
NFA (slower pushdown) regexp: 2.9
DFA (faster greedy) regexp: 2.8

So the parser is "twice as fast".  Note that this is only timing for
parsing - rewriting the parser will take more time with the extra
rewriting (I haven't measured it, and it's not noticeable in use, but it
must take more).


In summary the following aspects of LEPL's design helped here:
- Using a small core of matchers (with syntactic sugar on top)
- Exposing the DAG of matchers for rewriting before use
- Exposing composed actions to rewriting

Andrew

Caveats

From: "andrew cooke" <andrew@...>

Date: Sat, 4 Apr 2009 09:33:35 -0400 (CLT)

Ooops.  First sentence above should say "automaton" not "automata" :)

Another limitation I didn't mention is that (obvious if you think about
it) this won't work on anything that includes a recursive match.  It only
works on the "tree like" parts of the matcher graph.

And this doesn't always give a speedup.  My test with the ambiguous
grammar, for example, runs slower if this is enabled.  That's because that
test spends almost all its time backtracking over different combinations
and, worse, the work of matching characters is done via literals which are
*slower* when rewritten as a regular expression.

Andrew

Another Thought

From: "andrew cooke" <andrew@...>

Date: Sat, 4 Apr 2009 10:02:59 -0400 (CLT)

In a sense, a recursive decent parser implemented using trampolining is a
push-down automaton.  Perhaps the main difference being that "lookahead"
is not separate from actually doing the work (and perhaps failing).

In practice, another major difference is that my regexps don't allow
arbitrary actions to be associated with matches.

In a sense, then, this compilation to regular expressions is simply
providing a simplified, streamlined subset of the main parser.

Andrew

2.3 Released

From: "andrew cooke" <andrew@...>

Date: Mon, 6 Apr 2009 08:58:48 -0400 (CLT)

More detailed tests are described in the docs for the 2.3 release, which
includes this code -
http://www.acooke.org/lepl/examples.html#config-example

Andrew

Comment on this post