Consider the following grammar:
Prove the above grammar is LL (1). Draw the parsing table. Now check whether the string “ab” and “acbd” are the languages of the above grammar. (Derive each step with the help of a stack.)
S → aABb
A → c|𝜖
B → d|𝜖
Left Factoring is a grammar transformation technique. It consists in "factoring out" prefixes which are common to two or more productions. Ex. A -> α β | α γ
Left Recursion is a property a grammar has whenever you can derive from a given variable (non terminal) a RHS that begins with the same variable, in one or more steps. Ex. A -> A α
In the above grammar, there is no Left Factoring, or Left Recursion. So, we can say that this is LL(1).
FIRST(S)={a}
FIRST(A)={c,𝜖}
FIRST(B)={d,𝜖}
FOLLOW(S)={$}
FOLLOW(A)={d,b}
FOLLOW(B)={b}
LL(1) Parsing Table:
|
a |
b |
c |
d |
$ |
S → aABb |
S → aABb |
|
|
|
|
A → c|𝜖 |
|
A → 𝜖 |
A → c |
A → 𝜖 |
|
B → d|𝜖 |
|
B → 𝜖 |
|
B → d |
|
Checking the acceptance of the string ‘ab’
Stack |
Input |
Action |
Output |
$S |
ab$ |
Top of stack is Nonterminal, so expand |
S → aABb |
$bBAa |
ab$ |
Top of stack is Terminal, so pops off |
|
$bBA |
b$ |
Top of stack is Nonterminal, so expand |
A → 𝜖 |
$bB |
b$ |
Top of stack is Nonterminal, so expand |
B → 𝜖 |
$b |
b$ |
Top of stack is Terminal, so pops off |
|
$ |
$ |
Accept, successful completion |
|
Checking the acceptance of the string ‘acdb’
Stack |
Input |
Action |
Output |
$S |
acdb$ |
Top of stack is Nonterminal, so expand |
S → aABb |
$bBAa |
acdb$ |
Top of stack is Terminal, so pops off |
|
$bBA |
cdb$ |
Top of stack is Nonterminal, so expand |
A → c |
$bBc |
cdb$ |
Top of stack is Terminal, so pops off |
|
$bB |
db$ |
Top of stack is Nonterminal, so expand |
B → d |
$bd |
db$ |
Top of stack is Terminal, so pops off |
|
$b |
b$ |
Top of stack is Terminal, so pops off |
|
$ |
$ |
Accept, successful completion |
|
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. |
… |
Write a C program to find a number is AMSTRONG or NOT.
What is ISO 9000 Certification? How to Get ISO 9000 Certification?
What operations can be performed on Queues?
What are the propositions of Putnam’s model?