img
Question:
Published on: 28 March, 2024

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

 

Answer:

            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

 

Random questions