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
Post a Comment