Deep expression chain performance

Andy <borucki.andrzej@gmail.com>
Tue, 25 Apr 2023 06:51:55 -0700 (PDT)

          From comp.compilers

Related articles
Deep expression chain performance borucki.andrzej@gmail.com (Andy) (2023-04-25)
Re: Deep expression chain performance anton@mips.complang.tuwien.ac.at (2023-04-26)
Re: Deep expression chain performance gah4@u.washington.edu (gah4) (2023-04-26)
Re: Deep expression chain performance 864-117-4973@kylheku.com (Kaz Kylheku) (2023-04-27)
Re: Deep expression chain performance anton@mips.complang.tuwien.ac.at (2023-04-27)
| List of all articles for this month |

From: Andy <borucki.andrzej@gmail.com>
Newsgroups: comp.compilers
Date: Tue, 25 Apr 2023 06:51:55 -0700 (PDT)
Organization: Compilers Central
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="39482"; mail-complaints-to="abuse@iecc.com"
Keywords: C, parse, question, comment
Posted-Date: 25 Apr 2023 12:21:40 EDT

I am writing C grammar.
Grammar speed may be down caused by deep expression chain.
For example, simple "n=0" has 20 levels:
assignmentExpression
conditionalExpression
logicalOrExpression
logicalAndExpression
inclusiveOrExpression
exclusiveOrExpression
andExpression
eqaulityExpression
relationalExpression
shiftExpression
additiveExpression
multiplicativeExpression
castExpression
unaryExpression
postfixExpression
postfixExpressionLeft
atom
literal
IntegerConstant
DeciamlConstant


In other hand, Rust grammar for Antlr4
https://github.com/antlr/grammars-v4/blob/master/rust/RustParser.g4
has precedence definition:
expression
      : outerAttribute+ expression # AttributedExpression // technical, remove left recursive
      | literalExpression # LiteralExpression_
      | pathExpression # PathExpression_
      | expression '.' pathExprSegment '(' callParams? ')' # MethodCallExpression // 8.2.10
      | expression '.' identifier # FieldExpression // 8.2.11
      | expression '.' tupleIndex # TupleIndexingExpression // 8.2.7
      | expression '.' 'await' # AwaitExpression // 8.2.18
..............................
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)


My ask:
form expr: expr operator expr
is always ambiguous and waste time or I something bad have written?
How is possible to reduce depth of chain?
Parsing time with Antlr is much longer than parsing + semantic actions with GCC. Probably big part of this time is long depth of expressions.
[If your parser is taking a lot of time, something is wrong. In the
compilers I know, the pareer is always a tiny part of the work, which
is dominated by the lexer which has to look at each character in the
input, and optimizers that have to make multiple passes over the whole
intermediate representation. -John]


Post a followup to this message

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