Java Reference
In-Depth Information
50. Consider the grammar generated by 1
≤
i
,
j
≤
n
,
i
j
using the following
template:
S
→
X
i
z
i
X
i
→
y
j
X
i
|
y
j
The resulting grammar has
O
(
n
2
)productions.
(a) Show that the CFSM for this grammar has
O
(2
n
) states.
(b) Explain why the grammar is, or is not, SLR(1).
51. The bottom-up parsing techniques given in this chapter are more pow-
erful than top-down techniques given in Chapter 5.
Using the alphabet
, devise a language that is not LL(
k
)forany
k
but is LR(
k
)forsome
k
.WhatpropertyofLR(
k
) parsing allows such a
grammar to be constructed?
{
a
,
b
}
