[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Performance of SableCC v ANTLR



Steve Jones wrote:
It was only when I started to compile larger programs (>250 lines) that I noticed that the compilation was taking several seconds on a 2.1 Ghz PC. This worried me greatly...
For comparison I've re-coded the front-end with ANTLR...
My observations so far are that the ANTLR front-end runs more than five times faster than the SableCC equivalent. SableCC produces 445 AST node types
for the grammar, the ANTRL solution just 77...
Can I ask is SableCC intrinsicly slower than ANTLR?

No. SableCC parsers can, in fact, be theoretically much faster than some ANTLR parsers, as the LALR(1) algorithm is linear in the size of the parse tree, whereas some ANTLR parsers might use an algorithm with (worst case) exponential running time in the size of the parse tree. (parse tree == Concrete Syntax Tree != actually built AST)

Etienne

--
Etienne M. Gagnon, Ph.D.             http://www.info.uqam.ca/~egagnon/
SableVM:                                       http://www.sablevm.org/
SableCC:                                       http://www.sablecc.org/