第3章 演習問題解答例

 

演習1  演習2  演習3  演習4  演習5  演習6  演習7  演習8 演習9

 

演習1 

(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]]

 

演習2 

(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に行く.

 

演習4 

(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]]]

 

以下,省略

 

演習5 

図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 NPP

6

1

2

P に・

7

0

2

PP NP P

8

0

0

S PP VP

9

0

2

S PPVP

10

0

0

VP PP VP

11

0

2

VP PPVP

12

2

3

V k

13

2

2

VP V TENS

14

2

3

VP VTENS

15

3

4

TENS ita

16

2

4

VP V TENS

17

0

4

S PP VP

18

0

4

VP PP VP

 

演習6 

番号

始点

終点

ラベル

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 NPP

10

0

2

PP NP P

11

0

2

S PPVP

12

2

2

VP PP VP

13

2

2

VP V TENS

14

2

2

PP NP P

15

2

3

VP VTENS

16

2

2

NP N

17

2

4

VP V TENS

18

0

4

S PP VP

 

演習7 step.6-2を次のように変更する.

step.6-2 β=Bγならば,B→δなる形式をもつすべての書換え規則について,

(1)    δが終端記号でないならば,項 <j, j, B→・δ> を作成して agenda の末尾に追加する.

(2)    δが終端記号で,かつ節点 j j+1 の間にある単語に等しいならば,項 <j, j+1, B→δ・> を作成して agenda の末尾に追加する.

 

演習8 

step.1 j := 1 ;

step.2 chart を空にする.

step.3 開始記号 S を左辺にもつすべての書換え規則 S α について項 <0, 0, S ・α> を作り,chart に入れる.

step.4 step.4-1step.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-1step.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 に行く.

 

演習9 

アルゴリズム

時間計算量

領域計算量

深さ優先のトップダウン構文解析アルゴリズム(図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)