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

Lasse =?iso-8859-1?q?Hiller=F8e?= Petersen <lhp+news@toft-hp.dk>
23 Dec 2019 03:17:07 GMT

          From comp.compilers

Related articles
How change grammar to equivalent LL(1) ? borucki.andrzej@gmail.com (Andy) (2019-12-22)
Re: How change grammar to equivalent LL(1) ? lhp+news@toft-hp.dk (Lasse =?iso-8859-1?q?Hiller=F8e?= Petersen) (2019-12-23)
Re: How change grammar to equivalent LL(1) ? christopher.f.clark@compiler-resources.com (Christopher F Clark) (2019-12-23)
Re: How change grammar to equivalent LL(1) ? DrDiettrich1@netscape.net (Hans-Peter Diettrich) (2019-12-23)
Re: How change grammar to equivalent LL(1) ? lhp+news@toft-hp.dk (Lasse =?iso-8859-1?q?Hiller=F8e?= Petersen) (2020-04-24)
Re: How change grammar to equivalent LL(1) ? 773-297-7223@kylheku.com (Kaz Kylheku) (2020-04-24)
| List of all articles for this month |

From: Lasse =?iso-8859-1?q?Hiller=F8e?= Petersen <lhp+news@toft-hp.dk>
Newsgroups: comp.compilers
Date: 23 Dec 2019 03:17:07 GMT
Organization: SunSITE.dk - Supporting Open source
References: 19-12-019
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

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


Post a followup to this message

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