Information Technology Reference
In-Depth Information
is the 1,
n
+
1entryanditcontainstheset
of non-terminals, if any, that generate
w
.If
S
is in this set,
w
is in
L
(
G
)
.
Finally, the only entry in
B
(
n
)
that is not
∅
The transitive closure
S
=
B
+
involves
r
=
1
r
=(
n
+
1
)
n/
2 products of set matrices.
The product of two
(
n
+
1
)
(
n
+
1
)
set matrices of the type considered here involves at
most
n
products of sets. Thus, at most
O
(
n
3
)
products of sets is needed to form
S
.Inturn,
aproductoftwosets,
S
1
·
×
S
2
,canbeformedwith
O
(
q
2
)
operations, where
q
=
|N|
is the
number of non-terminals. It suffices to compare each pair of entries, one from
S
1
and the
other from
S
2
, through a table to determine if they form the right-hand side of a rule.
As the matrices are being constructed, if a pair of non-terminals is discovered that is the
right-hand side of a rule, that is,
A
→
BC
, then a link can be made from the entry
A
in the
product matrix to the entries
B
and
C
.Fromtheentry
S
in
a
1,
n
+
1
, if it exists, links can be
followedtogenerateaparsetreefortheinputstring.
The procedure described in this proof can be extended to show that membership in an
arbitrary CFL can be determined in time
O
(
M
(
n
))
,where
M
(
n
)
is the number of operations
to multiply two
n
n
matrices [
342
]. This is the fastest known general algorithm for this
problem when the grammar is part of the input. For some CFLs, faster algorithms are known
that are based on the use of the deterministic pushdown automaton. For fixed grammars
membership algorithms often run in
O
(
n
)
steps. The reader is referred to topics on compilers
for such results. The procedure of the proof is illustrated by the following example.
×
EXAMPLE
4.11.4
Consider the grammar
G
6
of Example
4.11.3
. We show how the five-character
string
a
6
matrices
B
(
1
)
,
B
(
2
)
,
B
(
3
)
,
B
(
4
)
,
B
(
5
)
,asshownbelow.Since
B
(
5
)
contains
E
in the
1,
n
+
1
position,
a
∗
b
+
a
in
L
(
G
6
)
can be parsed. We construct the
6
×
b
+
a
is in the language.
Furthermore, we can follow links between non-terminals (not shown) to demonstrate that this string
has the parse tree shown in Fig.
4.29
.Thematrix
B
(
4
)
is not shown because each of its entries is
∗
∅
.
⎡
⎤
∅{
E
,
F
,
T
}∅ ∅ ∅ ∅
⎣
⎦
∅
∅
{
∗
}
∅
∅
∅
∅
∅
∅
{
E
,
F
,
T
}∅ ∅
B
(
1
)
=
∅
∅
∅
∅
{
}
∅
+
∅
∅
∅
∅
∅
{
}
E
,
F
,
T
∅
∅
∅
∅
∅
∅
⎡
⎤
⎡
⎤
∅∅∅{
}∅ ∅
∅∅∅ ∅ ∅ ∅
∅∅∅ ∅ ∅{
∅∅∅ ∅ ∅ ∅
∅∅∅{
E
⎣
⎦
⎣
⎦
}∅ ∅
∅∅∅ ∅ ∅ ∅
∅∅∅ ∅ ∅{
B
}
∅∅∅ ∅ ∅ ∅
∅∅∅ ∅ ∅ ∅
∅∅∅ ∅ ∅ ∅
E
B
(
2
)
=
B
(
3
)
=
}
∅∅∅ ∅ ∅ ∅
∅∅∅ ∅ ∅ ∅
A
Search WWH ::
Custom Search