Re: Deep expression chain performance

Andy <borucki.andrzej@gmail.com> writes:
[ANTLR]
>If I do similar in C grammar:
>expr
> : atom # atom_
> | '__extension__'? '(' compoundStatement ')' # groupedExpression
> | expr '(' argumentExpressionList? ')' # postfixExpression
> | expr '.' Identifier # postfixExpression
> | expr '->' Identifier # postfixExpression
> | expr '[' expr ']' # postfixExpression
>
>parsing time increased by orders of magnitude: short .c files was processed longer a long file I didn't wait for it to finish (probably increasing nonlinear)


I am not an expert on ANTLR, but it is based on LL-parsing, and
normally LL-based parsers endlessly recurse on left recursion.
However, given that your Rust grammar has left recursion, too, ANTLR
seems to be able to cope with that problem at least in some cases.


There are other features in ANTLR that cause superlinear parsing
times: syntactic predicates and semantic predicates. IIRC there can
also be slowdowns if a long lookahead is necessary.


>My ask:
>form expr: expr operator expr
>is always ambiguous


Yes.


>and waste time


Depends on how the ambiguity is dealt with. E.g., yacc resolves the
ambiguity in some way, and suppresses the alternative parse, and
therefore has linear performance. However, the suppressed alternative
may be the one you were interested in, so better define the grammar
unambiguously. I don't see such a rule in the example above, though.


By contrast, a GLR parser or Early parser keeps the alternatives in
some way, resulting in superexponential performance (n^3 for Early,
not sure for GLR).


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

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