Search code examples
parsingcompiler-constructionautomationformal-languagesll-grammar

How to prove left-recursive grammar is not in LL(1) using parsing table

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)?

Solution

  • 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)