0
$\begingroup$

im trying to check if this grammar is LL(1).

S -> L = R
L -> * L | id
R -> L | R + R | num

As you can see there is a Left recursion on R production. So i remove that and what i get is:

S -> L = R
L -> * L | id
R -> L R' | num R'
R' -> + R R' | ε

Now the problem that i have is that First and Follow set of R' rule have a common non-terminal ("+") and also FIRST(R) and FOLLOW(R') has a common non-terminal. So i wonder how to create the parsing table if there's this conflict. My question is: is there a way to solve this problem or simply this isn't an LL(1) grammar?

Thanks.

$\endgroup$
0
$\begingroup$

Your factoring is wrong. It should be (written as regular espressions):

$\begin{align*} R &\to (L \mid \operatorname{num}) (+ R)^* \end{align*}$

Thus the grammar with left recursion fixed is:

$\begin{align*} S &\to L = R \\ L &\to * L \mid \operatorname{id} \\ R &\to L R' \mid \operatorname{num} R' \\ R' &\to + R R' \mid \varepsilon \end{align*}$

You can check that this doesn't have conflicts.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Sry isn't this the same as i wrote? I mean the fixed left- recursion @vonbrand $\endgroup$ – Samuel Primus May 17 at 16:12
0
$\begingroup$

Your original grammar is not only left-recursive, it is also ambiguous. Left-recursion only matters to certain parsing techniques, but ambiguous grammars are, by definition, impossible to parse with a deterministic parser. And removing left-recursion does not in general fix ambiguity.

The ambiguity is in the production

R → R + R

which allows 1 + 2 + 3 to be parsed in two different ways: as the result of adding 3 to 1 + 2 or as the result of adding 2 + 3 to 1. (These have the same value, but if the operator had been - instead of +, the ambiguity would allow two different evaluations.)

The correct way to write this grammar unambiguously is

 S → L = R
 L → *L | id
 R → F | R + F
 F → L | num

With that grammar, 1 + 2 + 3 can only be parsed as the sum of 1 + 2 and 3, because 2 + 3 is not an F. That makes + a left-associative operator, which is the normal usage. (Again, this is clearer if you consider the operator -: 1 - 2 - 3 is -4, not 0.)

You can then, if you want to, apply the left-recursion elimination algorithm, to yield:

 S → L = R
 L → *L | id
 R → F R'
 R'→ + F R' | ε
 F → L | num

Note, however, that after left-recursion elimination, the associativity of + is not so clear. With a simple operator grammar like this, left-recursion elimination is essentially the same as the two steps:

  1. Change left-associative operators (left-recursive productions) to being right-associative.

  2. Left-factor the productions.

Thus, after left-recursion elimination, a left-associative grammar and a right-associative grammar are the same.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you so much, you helped me a lot! All clear now. I wasn't even thinking about ambiguity of the grammar. Thank you again. @rici $\endgroup$ – Samuel Primus May 17 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.