Show that no left recursive grammar can be LL(1). Show that no LL(1) grammar can be ambiguous.
First of all FIRST and FOLLOW over the grammar must find out in which left recursion has been removed. Therefore surely if we try to create LL(1) parsing table there won't be any 2 entries as left recursion is removed and grammar is unambiguous.
Let assume the following Grammar:-
S → SA|A
A → a
is not LL(1) as left recursion exists. To prove it by constructing LL(1) parsing table we 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) , the 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 the answer.
Therefore FIRST(S)=FIRST(S)={a} , 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). Hence, we can say that no left recursive grammar can be LL(1).
Let T and N be the sets of terminal and non-terminal symbols.
Let the following hold
MaybeEmpty(s) = true <=> s → empty
First(s) = X containing all x for which there exists Y such that s → xY
Follow(A) = X containing all x for which there exists Y,Z such that S → YAxZ
Note that a grammar is LL(1) if the following holds for every pair of productions A→B and A →C:
1. (not MaybeEmpty(B)) or (not MaybeEmpty(C))
2. (First(B) intersect First(C)) = empty
3. MaybeEmpty(C) => (First(B) intersect Follow(A)) = empty
Consider a language with is LL(1), with A→B and A → C. That is to say there is some string of terminals TZ which admits multiple derivations by distinct parse trees.
Suppose that the left derivation reaches S → TAY → TZ. The next step may be either TAY → TBY, or TAY → TCY. Thus the language is ambiguous if both BY →Z and CY → Z. (Note that since A is an arbitrary non-terminal, if no such case exists, the language is non-ambiguous.)
Case 1: Z = empty
By rule 1 of LL(1) grammars, at most one of B and C can derive empty (non-ambiguous case).
Case 2: Z non-empty, and neither B nor C derive empty
By rule 2 of LL(1) grammars, at most one of B and C can permit further derivation because the leading terminal of Z cannot be in both First(B) and First(C) (non-ambiguous case).
Case 3: Z non-empty, and either MaybeEmpty(B) or MaybeEmpty(C)
Note the by rule 1 of LL(1) grammars, B and C cannot both derive empty. Suppose therefore that MaybeEmpty(C) is true.
This gives two sub-cases.
Case 3a: CY → Y; and
Case 3b: CY → DY, where D is not empty.
In 3a we must choose between BY →Z and CY → Y → Z, but notice that First(Y) subset-of Follow(A). Since Follow(A) does not intersect First(B), only one derivation can proceed (non-ambiguous).
In 3b we must choose between BY →Z and CY → DY → Z, but notice that First(D) subset-of First(C). Since First(C) does not intersect First(B), only one derivation can proceed (non-ambiguous).
Thus in every case the derivation can only be expanded by one of the available productions. Therefore the grammar is not ambiguous.
What is Basic Block? List out the basic blocks and draw the flow graph for the following code:
1. |
location= -1 |
2. |
i=0 |
3. |
i<100 goto 5 |
4. |
goto 13 |
5. |
t1=4*i |
6. |
t2=A[t1] |
7. |
if t2=x goto 9 |
8. |
goto 10 |
9. |
location=i |
10. |
t3=i+1 |
11. |
i=t3 |
12. |
goto 3 |
13. |
… |
Show that no left recursive grammar can be LL(1). Show that no LL(1) grammar can be ambiguous.
Write an program to generate Pascal’s triangle.