Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #3454

Re: Deep expression chain performance

Show all headers | View raw

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/

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Deep expression chain performance Andy <borucki.andrzej@gmail.com> - 2023-04-25 06:51 -0700
  Re: Deep expression chain performance anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2023-04-26 16:33 +0000
  Re: Deep expression chain performance gah4 <gah4@u.washington.edu> - 2023-04-26 13:06 -0700
  Re: Deep expression chain performance Kaz Kylheku <864-117-4973@kylheku.com> - 2023-04-27 00:28 +0000
    Re: Deep expression chain performance anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2023-04-27 06:17 +0000

csiph-web