Assignment # 2

ASSIGNMENT # 2 (CLO-2) B.S.
(CS) -7
Date of submission: 25-10-2021 (10 points)
Q.1
Given the grammar :
lexp → number | ( op lexp-seq)
op → + | - | *
lexp-seq → lexp-seq lexp | lexp
Write pseudo code to compute the numeric value of an lexp by recursive descent.
Q.2
Show the actions of an LL(1) parser that uses the following table to recognize the
following Arithmetic expression..
3 * (4 – 5 + 6)
M(N,T) ( Number ) + - * $
Exp exp→term exp’ exp→term exp’
exp’ exp’ exp’→ exp’→ exp’→
→𝜀 𝑎𝑑𝑑op 𝑎𝑑𝑑op 𝜀
term term
exp’ exp’
addop addop addop
→+ →-
Term term→ term→
factor term’ factor term’
term’ term’ term’→ term’→ term’→mulop term’→
→𝜀 𝜀 𝜀 factor term’ 𝜀
mulop mulop → *
factor factor→(exp) factor→number
Q.3
Consider the following grammar.
lexp→ atom | list
atom→ number | identifier
list→ ( lexp-seq)
lexp-seq → lexp-seq lexp | lexp
a. Remove the Left-recursion.
b. Construct first and follow sets for the non-terminal of the resulting grammar.
c. Is the resulting grammar LL(1)?Justify your answer from the two conditions on
its First and Follow sets.
d. Construct the LL(1) parsing table for the above grammar.
e. Show the actions of an LL(1) parser that uses the above grammar to recognize
the following input string.
( a ( B ( 2 ) ) ( c ) ) $
Q.4.
a) Can an LL(1) grammar be ambiguous? Why or why not?

b) Can an ambiguous grammar be LL(1)? Why or why not?
c) Must an unambiguous grammar be LL(1)? Why or why not?
d) Can a left recursive grammar be LL(1). Why or why not?
Q. 5
A Non-terminal is use-less if there is no derivation from the start symbol to a
string of tokens in which A appears.
a. Give a mathematical formulation of this property.
b. Is it likely that a programming language grammar will have a useless symbol?
Explain
c. Show that, if a grammar has a useless symbol, the computation of First and
Follow sets as given in this chapter may produce sets that are too large to
accurately construct an LL(1) parsing table.
Q.6
ERROR RECOVERY TABLE
Trace the actions of an LL(1) parser on the input (2+ - 3)* 4 - + 5 using the
error recovery as given in the following table.
M(N,T) ( Number ) + - * $
Exp exp→term exp’ exp→term exp’ Pop Scan Scan Scan Pop
exp’ Scan Scan exp’ exp’→ exp’→ Scan exp’→
→𝜀 𝑎𝑑𝑑op 𝑎𝑑𝑑op 𝜀
term term
exp’ exp’
Addop Pop Pop Scan addop addop Scan Pop
→+ →-
Term term→ term→ Pop Pop Pop Scan Pop
factor term’ factor term’
term’ Scan Scan term’ term’→ term’→ term’→mulop term’→
→𝜀 𝜀 𝜀 factor term’ 𝜀
Mulop Pop Pop Scan Scan scan mulop → * Pop
Factor factor→(exp) factor→number Pop Pop pop Pop Pop
Q.7
Compute FIRST and FOLLOW sets for the following Grammar.
Consider the expression grammar below:
E → T E′
E’→ + T E′ | ∈
T → F T′
T’→ * F T′ | ∈
F → ( E ) | id
-------------------------------------------------------------------------------------
Q.8
Consider the following Grammar:
declaration → type var-list
type → int | float
var-list → identifier, var-list | identifier
a. Left-factor this grammar.

b. Construct First and Follow sets for the non-terminals of the resulting grammar.
c. Show that the resulting grammar is LL(1).
d. Construct the LL(1) parsing table for the resulting grammar.
e. Show the actions of the corresponding LL(1) parser, given the input string int x,y,z.
Q.9
For the following EBNF, Convert it into CFG that has no left-recursion and is also
left-factored(without changing the meaning of the grammar).Then find the First and
Follow sets for the modified grammar with the complete paring table.
G={N,T,S,P}
N={A,B,C,D}
T = { "(" , ")" , "+" , "a" , "[" , "]" , "." }
Start symbol = A
P = productions:
A→B "."
B→ [ "a" | "(" C ")" | "[" B "]" ]
C→B D
D→{ "+" B }
Convert the above EBNF into CFG more suitable for Top-down parsing.
(i.e. A grammar that is left-factored and also without left-recursion.)
Q.10
Consider the following grammar:
A→ xCB
B→ z|Ax
C→ yBz|∈
Where {A, B, C} is the set of nonterminal symbols, A is the start symbol, {x, y, z} is the set of
terminal symbols, and ∈ denotes the empty string.
i) Is the above grammar LL(1).
ii) Construct the first and follow sets for the above grammar.
iii) Make the predictive parsing two-dimensional(M,N) table.
Answer the following questions:
a) What does table(A, x) contain? a) ∈ b) x c) xCB d) A x.
b) What does table(A, y) contain? a) x b) error c) xCB d) A x.
c) What does table(A, z) contain? a) yBZ b) error c) xCB d) A x.
d) What does table (B, x) contain? a) error b) z c) x d) A x.
e) What does table (B, y) contain? a) ∈ b) error c) z d) A x.
f) What does table (B, z) contain? a) error b) c x c) z d) A x.
g) What does table (C, x) contain? a) ∈ b) error c) yBz d) xCB.
h) What does table(C, y) contain? a) error b) x c) yBz d) xCB.
i) What does table(C, z) contain? a) error b) ∈ c) y B z d) xCB.
----------------------------------------------------------------------------------------
Q.11
a. Consider the following grammar:
S → iEtS | iEtSeS | a
E→b
Is this left-factored? If no, then make it left-factored else write yes.
b. Consider the following Backus-Naur Form (BNF):
S→ S+T | T
T→ T*F | F
F → (S) | id
Remove the left recursion from the above grammar.
-----------------------------------------------------------------------------------------
Q.12 Consider the following grammar:
P→bSe
S → AR
R → AR | ∈
A → id = E ;
E → FT
T → + FT | ∈
F → (E) | id
a) Construct the First and Follow sets for the above grammar.
b) Construct the Parsing table for the above grammar:
c) Is the above grammar LL(1)? Justify your answer from the two conditions on its First and
Follow sets.
d) Parse the input b id = id + 1 ; e $ using the parsing table constructed in part (b).
Q.13
i. Given the grammar A → (A) A | ∈
Is the above grammar LL(1)? Prove with logic.
ii. Given the grammar A → a A a | ∈
Is the above grammar LL(1)? Prove with logic.
Construct First and Follow sets for the non-terminal A of the above two parts.
Q.14
a. Consider the following Grammar.
S → a | ab | abc | abcd
Is it suitable for Top-down parser? If not Why?
Modify the above grammar (i.e.without changing the meaning of the grammar) in such a way
that it should be suitable for L.L.(1) parser.
b. Consider the following Context-free grammar.
S→ S S + | S S* |a
And the input string a a + a*

Draw the table showing the stages of the parsing stack, position of input tape header and
action taken at each step.
Q. 15
Consider the following grammar.:
lexp → atom | list
atom→ number | identifier
list→ (lexp-seq)
lexp-seq → lexp , lexp-seq | lexp
a) Left factor this grammar.
b) Construct first and follow sets for the non-terminal of the resulting grammar.
c) Is the resulting grammar LL(1)?. Justify your answer from the two conditions
on its First and Follow sets.
d) Construct the LL(1) parsing table for the above grammar.
e) Show the actions of an LL(1) parser that uses the above grammar to recognize
the following input string.
( A , ( b , ( 2 ) ) , ( c ) ) $
--------------------------------------------- THE END --------------------------------------------------------------

Assignment # 2

Uploaded by

Copyright:

Available Formats

Assignment # 2

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Assignment # 2

Uploaded by

Copyright:

Available Formats

ASSIGNMENT # 2 (CLO-2) B.S.

a) Can an LL(1) grammar be ambiguous? Why or why not?

a. Left-factor this grammar.

b. Consider the following Backus-Naur Form (BNF):

And the input string a a + a*

--------------------------------------------- THE END --------------------------------------------------------------

You might also like