Java Reference
In-Depth Information
44. Based on the material in Exercises 40, 41, and 43, construct an LALR(1)
grammar for the language defined by the following grammar:
1 Start
→
Stmt $
2 Stmt
→
if e then Stmt else Stmt
3
|
if e then Stmt
4
|
while e Stmt
5
|
repeat Stmt until e
6
|
other
45. Show that there exist non-LL(1) grammars that are
(a) LR(0)
(b) SLR(1)
(c) LALR(1)
46. Normally, an LR parser traces a rightmost derivation (in reverse).
(a) How could an LR parser be modified to produce a leftmost parse as
LL(1) parsers do? Describe your answer in terms of the algorithm
in Figure 6.3.
(b) Would it help if we knew that the LR table was constructed for an
LL grammar? Explain your reasoning.
47. For each of the following, construct an appropriate grammar:
(a) The grammar is SLR(3) but not SLR(2).
(b) The grammar is LALR(2) but not LALR(1).
(c) The grammar is LR(2) but not LR(1).
(d) The grammar is LALR(1) and SLR(2) but not SLR(1).
48. Construct a single grammar that has
all
of the following properties:
•
It is SLR(3) but not SLR(2).
•
It is LALR(2) but not LALR(1).
•
It is LR(1).
49. For every
k
>
1 show that there exist grammars that are SLR(
k
+
1),
LALR(
k
+
1), and LR(
k
+
1) but not SLR(
k
), LALR(
k
), or LR(
k
).
