ASSIGNMENT # 2 (CLO-2) BCS-7th Semester (10 points)
Date of submission:08-10-25(for B) and 10-10-25(for A)
A: Describe Two basic conditions that satisfies a grammar to be in L.L.(1) Form.
Q.1
Given the grammar A → (A) A | ∈ , write Pseudocode to parse this grammar by
recursive-descent.
-------------------------------------------------------------------------------------------------
Q.2
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.3 Consider the following parsing table.
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’→mulo term’
’→ ε ε →ε p factor →ε
term’
mulop mulop→ *
factor factor→(exp) factor→numbe
r
i) Show the actions of an LL(1) parser that uses the above table to recognize the
following Arithmetic expression. 3 * (4 – 5 + 6)
ii) Fill the Error Recovery Entries for the following Parsing table.
iii) Trace the actions of an LL(1) parser on the input (2+ - 3)* 4 - + 5 using the error
recovery table of Part(ii).
-------------------------------------------------------------------------------------------------------------
Q.4
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.5.
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. 6
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.7
Compute FIRST and FOLLOW sets for the following Grammar.
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 along 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 →x C B
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,T) 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.
iv) For the following input tape, make the parsing stack and parsing actions and show if the
above grammar accepts it or Not.
x y x z x z z $
------------------------------------------------------------------------------------------------------------------
Q.11
a. Consider the following grammar:
S → iEtS | iEtSeS | a
E →b
Is this left-factored? If No, then make it left-factored.
b. Remove the left recursion from the following grammars.
i) S → S + T | T
T→ T*F | F
F → (S) | id
ii) S → Aa | b
A → Ac | Sd | ∈
-----------------------------------------------------------------------------------------------------------------
Q.12 Consider the following grammar:
P→bSe
S → AR
R → AR | ∈
A→ id = E ;
E → FT
T → + FT | ∈
F → (E) | id | int
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 following input:
b Id = id + 1 ; e $
using the parsing table constructed in part (b).
--------------------------------------------------------------------------------------------
Q.13
i. Given the grammar A → (A) A | ∈
ii. Given the grammar A → a A a | ∈
Is the above grammar LL(1)? Prove with logic.
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
parsing 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 ) ) $
----------------------------------------------------------------------------------------------------
Q.16
This question concerns the following grammar, which generates email
addresses:
Addr → Name @ Name . id
Name → id | id . Name
For example, this could generate the addresses
[email protected]
[email protected]
[email protected]
LL(1) Conflicts.This grammar, as written, is not LL(1). Rewrite the
grammar to eliminate all LL(1) conflicts.
---------------------------------------------------------------------------------------------------
Q.17
Consider the following grammar:
S ABC
Aa|Cb|∈
Bc|dA|∈
Ce|f
a) Construct first and follow sets for the non-terminal of the given grammar. (1 m)
b) Is the given grammar LL(1)? (1 m)
c) Construct the parsing table for the above grammar. ( 1 m)
d) Show the actions of an LL(1) parser that uses the above grammar to recognize the
following input string.
f b d a e $
----------------------------------------------------------------------------------
Q.18
Consider the following grammar:
A Ba | Aa | c
B Bb | Ab | d
Remove the left Recursion.
--------------------------------------------- THE
END --------------------------------------------------------------
