Re: Why are LR parsers faster than using if conditions

> I recall somebody said that typical compilers spend most time
> elsewhere than in the parser, e.g., the actions.


Yes, for compilers, parsing is about 5% or less, depending on
how much optimization is done.


But for searching text, parsing can be about 35-40% of the time. I'm
making an educated guess here.


> [The numbers I've seen say that the lexer is usually the slowest part
> of a compiler. -John]


Yes, a lexer is slower than a good LALR parser. But the lexer can be
made faster with some easy coding tricks.


In the compiler-front-ends built with a PG that I wrote many years
ago, the percentages were something like this:


Lexing time: 20%
Parsing time: 20%
Symbol-table lookup time: 15%
AST creation time: 15%
Other (I/O, etc): 30%


This was without doing any optimization on the AST and no code
was generated.


The early textbooks on compiler construction had the lexer calling
a function, getc(), for each character in the input stream. This was
a killer for performance. You can avoid this problem by loading
all or lots of the input source file into memory and incrementing a
pointer to move from one character to the next.


Paul B Mann
paulbmann@yahoo.com
[These days getc() is invariably a macro expanded in line, but I
agree that slurping up a bunch of text into a local buffer like
flex does is likely to be faster. -John]

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