Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: anton@mips.complang.tuwien.ac.at (Anton Ertl) Newsgroups: comp.compilers Subject: Re: Deep expression chain performance Date: Wed, 26 Apr 2023 16:33:54 GMT Organization: Institut fuer Computersprachen, Technische Universitaet Wien Sender: johnl@iecc.com Approved: comp.compilers@iecc.com Message-ID: <23-04-013@comp.compilers> References: <23-04-012@comp.compilers> Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="8681"; mail-complaints-to="abuse@iecc.com" Keywords: C, parse, performance Posted-Date: 26 Apr 2023 12:50:51 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:3454 Andy 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/