0

Let's say i have this grammar:

S -> A C x | u B A
A -> z A y | S u | ε
B -> C x | y B u
C -> B w B | w A

This grammar is obviously not LL(1), which i can find constructing the parsing table. But is there any way i can prove that this grammar is not LL(1) without using the classical methods i.e. without constructing the parsing table or finding any conflicts?

Also how can i convert this grammar to LL(1)? I think i have to use both epsilon-derivation elimination and left recursion elimination but its a bit tricky and as many times i've tried i couldn't transform it to LL(1).

Thank you in advance.

Dragonite LvL 100
  • 11
  • 1
  • 7
  • 1
    It can be seen directly that the grammar is not LL(1) by the fact that you can reach S from itself by going S(first alternative)->A(second alternative)->S, with no tokens consumed in between. That would cause infinite recursion in a recursive descent parser. I'll leave the transformation to LL(1) for someone like @rici - I could probably do it (if it's possible), but it's not routine for me (either). – 500 - Internal Server Error Dec 04 '18 at 11:59

1 Answers1

2

Both S/A and B/C involve indirect left-recursion.

Since no left-recursive grammar (direct or indirect) is LL(k) for any k, you can prove the grammar is not LL(1) simply by showing the left-recursive cycle. (On the other hand, if you have a tool which computes FIRST and FOLLOW sets, the "classical" method is really very simple.)

Eliminating indirect left recursion involves first finding one possible topological sort of the non-terminals and then breaking the derivation cycle by substituting some uses of a non-terminal with its right-hand side. After that, the simple left recursion elimination algorithm can be applied.

You can find concrete examples of this transformation here on StackOverflow, or here, or in any good textbook on parsing theory. (Or, of course, by searching for the term "indirect left recursion" and looking for pages with some credibility.)

rici
  • 234,347
  • 28
  • 237
  • 341