Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: gah4 <gah4@u.washington.edu>
Newsgroups: comp.compilers
Subject: Re: Deep expression chain performance
Date: Wed, 26 Apr 2023 13:06:51 -0700 (PDT)
Organization: Compilers Central
Sender: johnl@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <23-04-014@comp.compilers>
References: <23-04-012@comp.compilers>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 8bit
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
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
In-Reply-To: <23-04-012@comp.compilers>
Xref: csiph.com comp.compilers:3455

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.