Tutorial-03
1) Which of the following grammars are ambiguous? Justify.
1) S → a | Sa | bSS | SSb | SbS
2) S → a | S+S | SS | S* | (S)
3) S → S (S) S | є
4) S → aS | aSbS | є
5) S → SS+ | SS- | a
2) Parse following string using unambiguous grammar of arithmetic expression:
i) id – id * (id + id ^ id) + id
ii) id * id – id ^ id ^ id / id
iii) – (id + id ) * id / id
3) Test whether given grammar is LL(1) or not? And Construct Predictive Parsing
table/ LL(1) table for it.
1) S → AB | eDa
A → ab |c
B → dC
C → eC| є
D →fD| є
2) A → BCx | y
B → yA | є
C → Ay | x
3) S → aA|AB
A → Ab|c
B → e|f
4) R → R ‘|’ R | R . R | R* | (R) | a | b, parse a|b* (b|a)
5) bexpr → bexpr or bterm | bterm
bterm → bterm and bfactor | bfactor
bfactor → not bfactor | (bexpr) | true | false
Also parse the string - not (true or false).
6) S → 1ABd | є
A → 1AC | &C
B → &S
C→1
7) A → BCx | y
B → yA | є
C → Ay | x
4) Eliminate Left recursion from given grammar.
1) S → Aa | b
A → Ac | Sd | є
2) S → ABC
A→Aa|d
B → Bb | e
A → Cc|f
3) E → Ma | Sb
M → ES | ah
S → ShE | є
5) Compute FIRST and FOLLOW set of following.
1) A → (A) A | є
6) Construct a recursive decent parser with backtracking for the grammar:
S → aSbS | bSaS | є
