The case of directly-executable parsers

    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
times bigger.


    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?


~velco

Return to the comp.compilers page.
Search the comp.compilers archives again.