Re: How change grammar to equivalent LL(1) ?

Path	csiph.com!eternal-september.org!feeder.eternal-september.org!adore2!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From	Lasse Hillerøe 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> (permalink)
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

Show key headers only | View raw

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

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

How change grammar to equivalent LL(1) ? Andy <borucki.andrzej@gmail.com> - 2019-12-22 15:55 -0800
  Re: How change grammar to equivalent LL(1) ? Lasse Hillerøe Petersen <lhp+news@toft-hp.dk> - 2019-12-23 03:17 +0000
  Re: How change grammar to equivalent LL(1) ? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-12-23 10:01 +0100

csiph-web