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

From	Lasse Hillerøe Petersen <lhp+news@toft-hp.dk>
Newsgroups	comp.compilers
Subject	Re: How change grammar to equivalent LL(1) ?
Date	2019-12-23 03:17 +0000
Organization	SunSITE.dk - Supporting Open source
Message-ID	<19-12-020@comp.compilers> (permalink)
References	<19-12-019@comp.compilers>

Show all headers | 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