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 |
|
Write short notes on:
Write short notes on:
Distinguish between Decision table versus decision tree
Define Quality Planning
