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.
For the input expression (4*7+1)*2, construct an annotated parse tree.
Show that no left recursive grammar can be LL(1). Show that no LL(1) grammar can be ambiguous.
Write a C program to manage array operation using switch case.
Explain the LOC, Function point and Feature point?
Explain View with suitable example. What is the usefulness of a view?
Briefly differentiate between CDMA and GSM technologies.
Convert the Regular Expression 
into e-NFA and then corresponding DFA.
