Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2400 > unrolled thread

How change grammar to equivalent LL(1) ?

Back to article view | Back to comp.compilers

Contents

  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

#2400 — How change grammar to equivalent LL(1) ?

Obviously if is possible.
In Polish Wikipedia can we read, that even very simple grammar:
expr->number '+' expr
expr->number
is not LL(1) bacause we must see '+' to distinguish

But
is posssible equivalent grammar:
expr -> number optPlusExpr
optPlusExpr -> epsilon
optPlusExpr ->'+' expr

What are general rules to change grammar to equivalent LL(1) grammar if possible?
[This topic is covered in every compiler textbooks.  Or you can start
with this Wikipedia article
https://en.wikipedia.org/wiki/Left_recursion#Removing_left_recursion
-John]

[toc] | [next] | [standalone]

#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

[toc] | [prev] | [next] | [standalone]

#2406

Am 23.12.2019 um 00:55 schrieb Andy:
> Obviously if is possible.
> In Polish Wikipedia can we read, that even very simple grammar:
> expr->number '+' expr
> expr->number
> is not LL(1) bacause we must see '+' to distinguish
>
> But
> is posssible equivalent grammar:
> expr -> number optPlusExpr
> optPlusExpr -> epsilon
> optPlusExpr ->'+' expr
>
> What are general rules to change grammar to equivalent LL(1) grammar if possible?

Use EBNF:
   expr -> number { '+' expr }
or
   expr -> number { '+' number }

EBNF or "railroad diagrams" typically translate directly into LL
top-down parsers. Many problems vanish when the grammar does not allow
for too much freedom causing inobvious problems. E.g. in EBNF only a
single derivation of a (left hand) nonterminal is allowed.

DoDi

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web