How to prove a left recursive grammar not in LL (1) using a parsing table
I have a grammar and would like to prove that this is not in LL (1):
S->SA|A A->a
Since this is a left recursive grammar, in order to find the first and subsequent set, 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 out the parsing table, I didn't get a single cell with two entries. Then how to prove that the given grammar is not in LL (1)?
source to share
First of all you find FIRST and FOLLOW above the grammar where you removed the left recursion. So if you try to create an LL (1) parsing table, there won't be any two entries, since the left recursion will be removed and the grammar is unambiguous.
Gram [S-> SA | A A-> a] is not LL (1), since left recursion exists. To prove this by building the LL (1) parsing table, you must find FIRST and FOLLOW on this grammar only without modifying it.
Start at the bottom A-> a, give FIRST (A) = {a}
S-> A, gives FIRST (S) = FIRST (A) = {a}
S-> SA, gives FIRST (S) = FIRST (S), I think the problem arises here. In such recursive calls, the rules say that it evaluates FIRST (S) until it changes, i.e. until items are added to FIRST (S) continue to be evaluated. When it stops changing, you answer
Therefore FIRST (S) = FIRST (S) = {a}, you call FIRST (S) as many times as it cannot change. Analysis table:
a ------------ S S->SA S->A ------------- A A->a
So there are two entries for (S, a). So it is not LL (1)
source to share