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)?
Then how is one to prove that the given grammar is not in LL(1)? If the grammar is ambiguous (at least one sentence has more than one parse tree), then the grammar is not in LL(1).
Essential conditions to check first are as follows:The grammar is free from left recursion. The grammar should not be ambiguous. The grammar has to be left factored in so that the grammar is deterministic grammar.
If a grammar contain left recursion it can not be LL(1) Eg - S -> Sa | b S -> Sa goes to FIRST(S) = b S -> b goes to b, thus b has 2 entries hence not LL(1) 3. If a grammar is ambiguous then it can not be LL(1) 4.
Left recursion often poses problems for parsers, either because it leads them into infinite recursion (as in the case of most top-down parsers) or because they expect rules in a normal form that forbids it (as in the case of many bottom-up parsers, including the CYK algorithm).
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)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With