Assignment # 2
Assignment # 2
Assignment # 2
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→term exp’
exp’
exp’ exp’ exp’ exp’ exp’→
→ε → add o → add ε
p term op
exp’ term
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.
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
( A , ( b , ( 2 ) ) , ( c ) ) $