How to prove left-recursive grammar is not in LL(1

问题:

I have a grammar and would like to prove that it is not in LL(1):

S->SA|A
A->a

As it is a left-recursive grammarm, to find the first and follow sets I eliminated the left recursion and got:

S->AS'
S'->AS'|Empty
A->a

first of A={a}      follow of S={$}
first of s'={a,ε}   follow of S'={$}
first of S={a}       follow of A={a,$}

But when I filled in the parsing table, I did not get any cell with 2 entries. Then how is one to prove that the given grammar is not in LL(1)?

回答1:

First of all you are finding FIRST and FOLLOW over the grammar in which you have removed left recursion. Therefore surely if you try to create LL(1) parsing table there won't be any 2 entries as left recursion is removed and grammar is unambiguous.

Grammar[ S->SA|A A->a ] is not LL(1) as left recursion exists. To prove it by constructing LL(1) parsing table you need to find FIRST and FOLLOW on this grammar only without modifying it.

Start from bottom A->a , gives FIRST(A)={a}

S->A , gives FIRST(S)=FIRST(A)={a}

S->SA , gives FIRST(S)=FIRST(S) , I think problem arises here. In such recursive calls rules says calculate FIRST(S) till it changes i.e. until elements are added in FIRST(S) continue to calculate. Once it stops changing that is you answer

Therefore FIRST(S)=FIRST(S)={a} , you call FIRST(S) as many times possible it won't change. Parsing Table:

      a
------------ 
S   S->SA
    S->A
-------------
A   A->a 

So there are two entries for (S,a). Thus it is not LL(1)

回答2:

For this Left recursive grammar:

S->SA|A
A->a

We can eliminate left recursion because it will give the same result as Previous Left recursive grammar does.

S->AS'
S'->AS'|Empty
A->a

first of A={a}      follow of S={$}
first of s'={a,ε}   follow of S'={$}
first of S={a}       follow of A={a,$}

So, for above case actually, we are checking LL(1) for modified Left recursive grammar (as it is same). But for following Left-Recursive Grammar:-

E -> E+n/n

We can not modify that grammar, it will Change associativity of + operator.

So, the only thing we will have to do is checking LL(1) without modifying

(E->E+n/n ).

So, we can say E->E+n/n is not LL(1).