Path: csiph.com!eternal-september.org!feeder.eternal-september.org!adore2!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: Lasse =?iso-8859-1?q?Hiller=F8e?= Petersen <lhp+news@toft-hp.dk>
Newsgroups: comp.compilers
Subject: Re: How change grammar to equivalent LL(1) ?
Date: 23 Dec 2019 03:17:07 GMT
Organization: SunSITE.dk - Supporting Open source
Lines: 29
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <19-12-020@comp.compilers>
References: <19-12-019@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="89614"; mail-complaints-to="abuse@iecc.com"
Keywords: parse, LL(1)
Posted-Date: 22 Dec 2019 22:53:37 EST
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:2401

On Sun, 22 Dec 2019 15:55:12 -0800, Andy wrote:
> https://en.wikipedia.org/wiki/Left_recursion#Removing_left_recursion
> -John]

As the WP-article mentions under pitfalls, the change from left- to right-
recursion changes the parse tree, which needs to be dealt with.

I am writing a "toy" LL(1) tool in Javascript/Nodejs, and I have found a
method which I think is quite "clever".

Expr: Term | Expr AddOp Term.
AddOp: "+" | "-".

becomes

Expr: Term Exprtailety '{ $$=$2($1) }'.
Exprtailety: '{ $$=(x)=>(x) }'
| AddOp Term Exprtailety '{ $$=(x)=>($3([$1, x, $2]) }'.
AddOp: "+" '{ $$=$1 }' | "-" '{ $$=$1 }'.

(I have a naming convention I find useful, with "tail" in the name to
denote such tailing productions, and also all nullables end in "ety" as
they may produce "empty".)

Using "Yacc-like" actions, I simply pass a chain of functions up through
the parse, which get called from the Sum rule and constructs a parse tree
turned the right way (that is: the left way.)

/Lasse