Re: Deep expression chain performance

gah4 <gah4@u.washington.edu>
Wed, 26 Apr 2023 13:06:51 -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: gah4 <gah4@u.washington.edu>
Newsgroups: comp.compilers
Date: Wed, 26 Apr 2023 13:06:51 -0700 (PDT)
Organization: Compilers Central
References: 23-04-012
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="23409"; mail-complaints-to="abuse@iecc.com"
Keywords: parse, performance
Posted-Date: 26 Apr 2023 20:41:09 EDT
In-Reply-To: 23-04-012

On Tuesday, April 25, 2023 at 9:21:44 AM UTC-7, Andy wrote:
> 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


A not unusual compiler design in the olden (small memory) days, is recursive
descent
for statements, and operator precedence for expressions. If you do
expressions with
recursive descent, you get, as you note, 20 levels on the stack. Operator
precedence
avoids all those levels, and works well for expressions for most languages.


Others have explained how parser generators do it.


Otherwise, the design of small-memory compilers is a lost art.

Post a followup to this message

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