|The case of directly-executable parsers email@example.com (2006-01-28)|
|Re: The case of directly-executable parsers derek@_NOSPAM_knosof.co.uk (Derek M. Jones) (2006-01-28)|
|Re: The case of directly-executable parsers firstname.lastname@example.org (email@example.com) (2006-01-30)|
|Re: The case of directly-executable parsers firstname.lastname@example.org (Clint Olsen) (2006-01-31)|
|Re: The case of directly-executable parsers email@example.com (Ranjit Mathew) (2006-01-31)|
|Re: The case of directly-executable parsers firstname.lastname@example.org (Karsten Nyblad) (2006-01-31)|
|Re: The case of directly-executable parsers email@example.com (firstname.lastname@example.org) (2006-02-02)|
|Date:||28 Jan 2006 15:18:48 -0500|
|Posted-Date:||28 Jan 2006 15:18:48 EST|
Directly-executable LR parsers are well-known and a number of
researchers have published amazing speedups over table-driver LR
parsers, in the 2x to 6x or more range, cf.:
Achyutram Bhamidipaty and Todd A. Proebsting
"Very Fast YACC-Compatible Parsers (For Very Little Effort)
R.N.Horspool and M. Whitney
"Even faster LR parsing"
Thomas J. Pennello
"Very fast LR parsing"
I have developed such a LALR(1) generator, which generates a
directly-executable parser in ISO C. Admittedly, the parser performs
only a few low-level optimizations - inverted table for non-terminal
transitions and separating the most frequent transition as a default.
However, the speedup I observe is nowhere near the previously reported
ones. Compared to a parser, generated by Bison 2.1 for the ISO C 99
grammar (taken straight from the standard, with one minor
modification), the directly-executable parser is only 5-9% faster on
P4 and about 12% faster on P3 Xeon, at the same time being about 3
I assume I'm not actually doing anything stupid with the generated
parser. A sample of the generated code (preprocessed and indent(1)ed)
is here: http://www.geocities.com/velcok/test-17.i.txt
What could be the reason for this parser performing so poorly? Or for
the Bison parser performing so well? Has anyone got some recent
observations with directly-executable vs. table driven recognizers -
scanning (re2c?), parsing, tree-matching?
Return to the
Search the comp.compilers archives again.