parsing - Assistance swapping a grammar to LL(1) -


i have following grammar

s -> e | s | e -> if (c) {s} | if (c) {s} else {s} -> v := t; t -> | b v -> x | y c -> v o t | t o v | v o v | t o t o -> < | > 

from this, correct in saying grammar not ll(1) because rule e, "if (c) {s}" can left-factored out , rule s has left recursion?

what correct way fix this? thinking like:

s -> p p -> er | ar r -> ar | ε e -> if (c) {s} b b -> else {s} -> v := t; t -> | b v -> x | y c -> v o t | t o v | v o v | t o t o -> < | > 

left-factoring e

you propose factor

e -> if (c) {s} | if (c) {s} else {s} 

into

e -> if (c) {s} b b -> else {s} 

now, it's no longer possible parse if (c) {s} form, since b can't empty. so, transformation not correct.

instead, consider this:

b -> else {s} | ε 

removing direct left recursion in s

you propose replace

s -> e | s | 

by

s -> p p -> er | ar r -> ar | ε 

while correct transformation, following sufficient:

s -> er | ar r -> ar | ε 

Comments