第3章 演習問題解答例
演習1 演習2 演習3 演習4 演習5 演習6 演習7 演習8 演習9
(e) [s, [pp, [np, [n, 学校]], [p, に]], VP]
(f) [s, [pp, [np, [n, 学校]], [p, に]], [vp, V, TENS]]
(g) [s, [pp, [np, [n, 学校]], [p, に]], [vp, [v, 行k], TENS]]
(1) []
(2) [[S, [学校, に, 行k, ita]]]
(3) [[[s, PP, VP], [学校, に, 行k, ita]]]
(4) [[[s, [pp, NP, P], VP], [学校, に, 行k, ita]]]
(5) [[[s, [pp, [np, N], P], VP], [学校, に, 行k, ita]]]
(6) [[[s, [pp, [np, [n, 学校]], P], VP], [に, 行k, ita]]]
(7) [[[s, [pp, [np, [n, 学校]], [p, に]], VP], [行k, ita]]]
(8) [[[s, [pp, [np, [n, 学校]], [p, に]], [vp, V, TENS]], [行k, ita]],
[[s, [pp, [np, [n, 学校]], [p, に]], [vp, PP, VP]], [行k, ita]]]
(9) [[[s, [pp, [np, [n, 学校]], [p, に]], [vp, [v, 行k ], TENS]], [ita]],
[[s, [pp, [np, [n, 学校]], [p, に]], [vp, PP, VP]], [行k, ita]]]
(10) [[[s, [pp, [np, [n, 学校]], [p, に]], [vp, [v, 行k ], [tens, ita]]], []],
[[s, [pp, [np, [n, 学校]], [p, に]], [vp, PP, VP]], [行k, ita]]]
演習3 step.5-1を次のように変更する.
step.5-1 inputが空ならば,Treeを出力してstep.3に行く.
(1) [[学校, に, 行k, ita]]
(2) [[[n, 学校], に, 行k, ita],
[学校, [p, に], 行k, ita],
[学校, に, [v 行k], ita],
[学校, に, 行k, [tens, ita]]]
(3) [[学校, [p, に], 行k, ita],
[学校, に, [v 行k], ita],
[学校, に, 行k, [tens,
ita]],
[[np,
[n, 学校]], に, 行k, ita],
[[n, 学校], [p, に], 行k, ita],
[[n, 学校], に, [v, 行k], ita],
[[n, 学校], に, 行k, [tens, ita]]]
(4) [[学校, に, [v 行k], ita],
[学校, に, 行k, [tens,
ita]],
[[np,
[n, 学校]], に, 行k, ita],
[[n, 学校], [p, に], 行k, ita],
[[n, 学校], に, [v, 行k], ita],
[[n, 学校], に, 行k, [tens,
ita]],
[学校, [p, に], [v, 行k], ita],
[学校, [p, に], 行k, [tens, ita]]]
(5) [[学校, に, 行k, [tens, ita]],
[[np,
[n, 学校]], に, 行k, ita],
[[n, 学校], [p, に], 行k, ita],
[[n, 学校], に, [v, 行k], ita],
[[n, 学校], に, 行k, [tens,
ita]],
[学校, [p, に], [v, 行k], ita],
[学校, [p, に], 行k, [tens,
ita]],
[学校, に, [v 行k], [tens, ita]]]
(6) [[[np, [n, 学校]], に, 行k, ita],
[[n, 学校], [p, に], 行k, ita],
[[n, 学校], に, [v, 行k], ita],
[[n, 学校], に, 行k, [tens,
ita]],
[学校, [p, に], [v, 行k], ita],
[学校, [p, に], 行k, [tens,
ita]],
[学校, に, [v 行k], [tens, ita]]]
(7) [[[n, 学校], [p, に], 行k, ita],
[[n, 学校], に, [v, 行k], ita],
[[n, 学校], に, 行k, [tens,
ita]],
[学校, [p, に], [v, 行k], ita],
[学校, [p, に], 行k, [tens,
ita]],
[学校, に, [v 行k], [tens,
ita]],
[[np,
[n, 学校]], [p, に], 行k, ita],
[[np,
[n, 学校]], に, [v, 行k], ita],
[[np, [n, 学校]], に, 行k, [tens, ita]]]
(8) [[[n, 学校], に, [v, 行k], ita],
[[n, 学校], に, 行k, [tens,
ita]],
[学校, [p, に], [v, 行k], ita],
[学校, [p, に], 行k, [tens,
ita]],
[学校, に, [v 行k], [tens,
ita]],
[[np,
[n, 学校]], [p, に], 行k, ita],
[[np,
[n, 学校]], に, [v, 行k], ita],
[[np,
[n, 学校]], に, 行k, [tens, ita]],
[[n, 学校], [p, に], [v, 行k], ita],
[[n, 学校], [p, に], 行k, [tens, ita]]]
(9) [[[n, 学校], に, 行k, [tens, ita]],
[学校, [p, に], [v, 行k], ita],
[学校, [p, に], 行k, [tens,
ita]],
[学校, に, [v 行k], [tens,
ita]],
[[np,
[n, 学校]], [p, に], 行k, ita],
[[np,
[n, 学校]], に, [v, 行k], ita],
[[np,
[n, 学校]], に, 行k, [tens, ita]],
[[n, 学校], [p, に], [v, 行k], ita],
[[n, 学校], [p, に], 行k, [tens,
ita]],
[[n, 学校], に, [v, 行k], [tens, ita]]]
(10) [[学校, [p, に], [v, 行k], ita],
[学校, [p, に], 行k, [tens,
ita]],
[学校, に, [v 行k], [tens,
ita]],
[[np,
[n, 学校]], [p, に], 行k, ita],
[[np,
[n, 学校]], に, [v, 行k], ita],
[[np,
[n, 学校]], に, 行k, [tens, ita]],
[[n, 学校], [p, に], [v, 行k], ita],
[[n, 学校], [p, に], 行k, [tens,
ita]],
[[n, 学校], に, [v, 行k], [tens, ita]]]
(11) [[学校, [p, に], 行k, [tens, ita]],
[学校, に, [v 行k], [tens,
ita]],
[[np,
[n, 学校]], [p, に], 行k, ita],
[[np,
[n, 学校]], に, [v, 行k], ita],
[[np,
[n, 学校]], に, 行k, [tens, ita]],
[[n, 学校], [p, に], [v, 行k], ita],
[[n, 学校], [p, に], 行k, [tens,
ita]],
[[n, 学校], に, [v, 行k], [tens, ita]],
[学校, [p, に], [v, 行k], [tens, ita]]]
(12) [[学校, に, [v 行k], [tens, ita]],
[[np,
[n, 学校]], [p, に], 行k, ita],
[[np,
[n, 学校]], に, [v, 行k], ita],
[[np,
[n, 学校]], に, 行k, [tens, ita]],
[[n, 学校], [p, に], [v, 行k], ita],
[[n, 学校], [p, に], 行k, [tens,
ita]],
[[n, 学校], に, [v, 行k], [tens,
ita]],
[学校, [p, に], [v, 行k], [tens, ita]]]
(13) [[[np, [n, 学校]], [p, に], 行k, ita],
[[np,
[n, 学校]], に, [v, 行k], ita],
[[np,
[n, 学校]], に, 行k, [tens, ita]],
[[n, 学校], [p, に], [v, 行k], ita],
[[n, 学校], [p, に], 行k, [tens,
ita]],
[[n, 学校], に, [v, 行k], [tens,
ita]],
[学校, [p, に], [v, 行k], [tens,
ita]],
[学校, に, [vp, [v 行k], [tens, ita]]]]
(14) [[[np, [n, 学校]], に, [v, 行k], ita],
[[np,
[n, 学校]], に, 行k, [tens, ita]],
[[n, 学校], [p, に], [v, 行k], ita],
[[n, 学校], [p, に], 行k, [tens,
ita]],
[[n, 学校], に, [v, 行k], [tens,
ita]],
[学校, [p, に], [v, 行k], [tens,
ita]],
[学校, に, [vp, [v 行k], [tens,
ita]]],
[[pp,
[np, [n, 学校]], [p, に]], 行k, ita],
[[np,
[n, 学校]], [p, に], [v, 行k], ita],
[[np, [n, 学校]], [p, に], 行k, [tens, ita]]]
以下,省略
図3.15のアルゴリズムを深さ優先のアルゴリズムに変更するためには、 step.5-2とstep.5-3を次のように変更する.
[step.5-2] β=εならば,
chartに項 <k, i, C→γ・Aδ> が存在するならば,
項 <k, j, C→γA・δ> を作成してagendaの先頭に追加する.
B→Aγ なる形式をもつすべての書換え規則について,
項 <i, i, B→・Aγ> を作成してagendaの先頭に追加する.
[step.5-3] β=Cδ で,chartに項 <j, k, C→ζ・> が存在するならば, 項 <i, k, A→αC・δ> を作成してagendaの先頭に追加する.
番号 |
始点 |
終点 |
ラベル |
1 |
0 |
1 |
N → 学校・ |
2 |
0 |
0 |
NP → ・N |
3 |
0 |
1 |
NP → N・ |
4 |
0 |
0 |
PP → ・NP P |
5 |
0 |
1 |
PP → NP・P |
6 |
1 |
2 |
P → に・ |
7 |
0 |
2 |
PP → NP P・ |
8 |
0 |
0 |
S → ・PP VP |
9 |
0 |
2 |
S → PP・VP |
10 |
0 |
0 |
VP → ・PP VP |
11 |
0 |
2 |
VP → PP・VP |
12 |
2 |
3 |
V → 行k・ |
13 |
2 |
2 |
VP → ・V TENS |
14 |
2 |
3 |
VP → V・TENS |
15 |
3 |
4 |
TENS → ita・ |
16 |
2 |
4 |
VP → V TENS・ |
17 |
0 |
4 |
S → PP VP・ |
18 |
0 |
4 |
VP → PP VP・ |
番号 |
始点 |
終点 |
ラベル |
1 |
0 |
1 |
N → 学校・ |
2 |
1 |
2 |
P → に・ |
3 |
2 |
3 |
V → 行k・ |
4 |
3 |
4 |
TENS → ita・ |
5 |
0 |
0 |
S → ・PP VP |
6 |
0 |
0 |
PP → ・NP P |
7 |
0 |
0 |
NP → ・N |
8 |
0 |
1 |
NP → N・ |
9 |
0 |
1 |
PP → NP・P |
10 |
0 |
2 |
PP → NP P・ |
11 |
0 |
2 |
S → PP・VP |
12 |
2 |
2 |
VP → ・PP VP |
13 |
2 |
2 |
VP → ・V TENS |
14 |
2 |
2 |
PP → ・NP P |
15 |
2 |
3 |
VP → V・TENS |
16 |
2 |
2 |
NP → ・N |
17 |
2 |
4 |
VP → V TENS・ |
18 |
0 |
4 |
S → PP VP・ |
step.6-2 β=Bγならば,B→δなる形式をもつすべての書換え規則について,
(1) δが終端記号でないならば,項 <j, j, B→・δ> を作成して agenda の末尾に追加する.
(2) δが終端記号で,かつ節点 j と j+1 の間にある単語に等しいならば,項 <j, j+1, B→δ・> を作成して agenda の末尾に追加する.
step.1 j := 1 ;
step.2 chart を空にする.
step.3 開始記号 S を左辺にもつすべての書換え規則 S → α について項 <0, 0, S → ・α> を作り,chart に入れる.
step.4 step.4-1とstep.4-2を新しい項が作れなくなるまで繰り返す.
step.4-1 項 <0, 0, A → α・> がchart に存在するならば,chart にあるすべての項 <0, 0, B → β・Aγ> に対して,項 <0, 0, B → βA・γ> を chart に追加する.
step.4-2 項 <0, 0, B → β・Aγ> がchart に存在するならば,すべての書換え規則 A → α について,項 <0, 0, A → ・α> を chart に追加する.
step.5 chart に項 < i, j-1, B → α・Mjβ> が存在するならば,項 < i, j, B → αMj・β> を chart に追加する.
step.6 step.6-1とstep.6-2を新しい項が作れなくなるまで繰り返す.
step.6-1 項 < i, j, A → α・> がchart に存在するならば,chart にあるすべての項 <k, i, B → β・Aγ> に対して,項 <k, j, B → βA・γ> を chart に追加する.
step.6-2 項 < i, j, B → β・Aγ> がchart に存在するならば,すべての書換え規則 A → α について,項 < j, j, A → ・α> を chart に追加する.
step.8 j = n ならば終了する.そうでなければ,j := j + 1 として step.5 に行く.
アルゴリズム |
時間計算量 |
領域計算量 |
深さ優先のトップダウン構文解析アルゴリズム(図3.6) |
O(Cn) |
O(n) |
深さ優先のボトムアップ構文解析アルゴリズム(1)(図3.8) |
O(Cn) |
O(n) |
深さ優先のボトムアップ構文解析アルゴリズム(2)(図3.8) |
O(Cn) |
O(n) |
ボトムアップのチャート法(図3.15) |
O(n3) |
O(n2) |
トップダウンのチャート法(図3.16) |
O(n3) |
O(n2) |
CYK法(図3.18) |
O(n3) |
O(n2) |
Early法(図3.20) |
O(n3) |
O(n2) |
シフトレデュース・パーサ |
O(Cn) |
O(n) |
LRパーサ |
O(n) |
O(n) |