Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

like image 564
rajkumar Avatar asked Dec 30 '14 10:12

rajkumar


People also ask

How do you prove that grammar is not 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).

How do you check whether given grammar is LL 1 or not also explain parsing table?

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.

Can a left recursive grammar be LL 1?

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.

Is left recursion a problem for LL parsers?

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


1 Answers

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)

like image 158
obmjo Avatar answered Oct 13 '22 23:10

obmjo