Microsoft PowerPoint - アルデIII 02回目10月15日

Size: px

Start display at page:

Download "Microsoft PowerPoint - アルデIII 02回目10月15日"

たいちあざみ
4 years ago
Views:

1 アルゴリズムとデータ構造 III 2 回目 :10 月 15 日文脈自由文法,CYK 法授業資料授業の予定 ( 中間試験まで ) 10/01 スタック ( 後置記法で書かれた式の計算 ) 10/15 文脈自由文法, 構文解析,CYK 法 10/22 構文解析 CYK 法 10/29 構文解析 CYK 法 11/12 構文解析 ( チャート法 ), グラフ ( ダイクストラ法 ) 11/ 構文解析 ( チャート法 ), グラフ ( ダイクストラ法, DPマッチング ) 11/ グラフ (DPマッチング,* アルゴリズム ) 11/19 グラフ (* アルゴリズム ), 前半のまとめ 11/26 中間試験 10/08, 11/05 の代わりの補講日は後日相談授業の予定 ( 中間試験以降 ) 12/03 全文検索アルゴリズム (simple serch, KMP) 12/10 全文検索アルゴリズム (M, ho-corsick) 12/17 全文検索アルゴリズム (ho-corsick), データ圧縮 01/07 暗号 ( 黄金虫, 踊る人形 ) 符号化 ( モールス信号, Zipfの法則, ハフマン符号 ) テキスト圧縮 01/14 テキスト圧縮 (zip), 音声圧縮 (DPCM,MP3,CELP), 画像圧縮 (JPEG) 01/21 期末試験を計算してみよう ( アセンブリ言語でプログラミング ) 数式 ( ) をメモリ ( データ領域 ) に書き込まれている 1. データ領域から1 文字読み込む 1. 数字 ( アスキーコード :30H~39H) なら 1. 数値に変換し, 数値をスタックにプッシュ 2. 演算子なら 1. 一旦スタックにプッシュし, ポップする. 2. スタックからポップし, 数値をレジスタに取り込む 3. スタックからポップし, 数値をレジスタ ( アキュムレータ ) に取り込む 4. 演算子が+なら 1. + を計算し,レジスタに計算結果を格納 5. 演算子が-なら 1. - を計算し,レジスタに計算結果を格納 6. レジスタの内容をスタックにプッシュ 2. データ領域すべてを読み終えるまで続ける. 簡単な計算の例 ; 後置記法の計算 ORG 8000H ; LD HL, DT ; 数式の先頭番地を指定 LOOP: LD, (HL) CP 00H JP Z, OWRI ; 数式を全部読み込んだら終わり LD E, (HL) LD D, 0H LD, (HL) INC HL CP 2H JP Z, LOOP ; +なら加算処理へ CP 2DH JP Z, LOOP ; -なら減算処理へ LD, E U 30H ; 数字なら数値に変換 ; レジスタの内容をスタックへプッシュ TPUH: LD E, LD D, 0H PUH DE ; 読み込んだ数値をスタックへプッシュ JP LOOP ; つぎの文字読み込みへ ; 加算 LOOP: ; 減算 LOOP: PUH DE ; 演算子をスタックへプッシュ POP DE ; 演算子をスタックからポップ LD, E ; スタックトップの値をレジスタへ LD, E ; スタックトップの値をレジスタへ DD, ; 加算 ( <= + ) JP TPUH PUH DE ; 演算子をスタックへプッシュ POP DE ; 演算子をスタックからポップ LD, E ; スタックトップの値をレジスタへ LD, E ; スタックトップの値をレジスタへ U ; 減算 ( <= - ) JP TPUH ; OWRI: HLT ; 入力データ DT: DEF 37H ;7 DEF 32H ;2 DEF 33H ;3 DEF 2H ;+ DEF 2DH ;- DEF 00H ;END END Z80 シミュレータ Z80 シミュレータ for Win32 1

2 ( スタックを含めた ) メモリの様子オートマトンと計算理論オートマトンの受理する言語クラスオートマトン受理言語型言語クラスチューリング機械第 0 型言語句構造言語 (PL) 線形拘束チューリング第 1 型言語文脈依存言語機械 (CL) プッシュダウンオートマ第 2 型言語文脈自由言語 (CFL) トン有限オートマトン第 3 型言語正規言語 (RL) RL CFL CL PL ( チョムスキーの言語階層 ) ( は包含関係を表す) 8 形式言語と有限オートマトン入門 5 形式言語理論入門 5.1 形式言語理論 5.2 文脈自由文法 5.3 線形文法と正規言語 5.4 形式言語のクラス階層とオートマトン 5.5 言語処理への応用形式文法 G の定義 G=(N,T,P,) N: 非終端記号の集合 T: 終端記号の集合 P: プロダクション : 開始記号文脈自由文法文脈自由文法 (CFG: Contet Free Grmmr) 文脈自由プロダクションのみから構成される文脈自由プロダクション β ただし, N,β V* N: 非終端記号の集合,T: 終端記号の集合,V: NとTの直和左辺が変数 1つ文脈依存文法 (CG: Contet ensitive Grmmr) 文脈依存プロダクションを含むプロダクションから構成される文脈依存プロダクション uv uβv ただし, N,u,v V*,β V + N: 非終端記号の集合,T: 終端記号の集合,V: NとTの直和 u=v=εのとき ( β) 文脈自由プロダクションとなる 11 文脈自由文法の例 ( 例題 5.9) CFG G=(N,T,P,) N( 非終端記号 )={,} T( 終端記号 )={,} P: 語の導出過程 L(G) はどのような言語か 12 2

3 例題 5.9 の解答例 L(G): n n 正規表現では表せない CFG G=(N,T,P,) N={,} T={,} P:, プッシュダウンオートマトンでは表現可能構文木 13 練習問題 1 例題 5.10 文脈依存文法の例 CG G=(N,T,P,) N={,,} T={,} P:,,,, 語の導出過程 L(G) はどのような言語か 14 練習問題 1 解答例題 5.10 CG G=(N,T,P,) N={,,} T={,} P:,,,, 語の導出過程 L(G) はどのような言語か構文木 ( 導出木 ) Time flies like n rrow. 15 L(G): n n n 光陰矢の如し時蠅は矢を好む 16 NP N Time V flies VP like PP 2 種類の導出木文法が曖昧 PREP NP DET N n rrow DJ Time NP N flies V like VP DET n NP N rrow 問題 : 例題 5.11 文法 N={},T={,+,*},P={ + * }, = 語 w= +**+ を導出せよ語 wの導出木導出木 + 解答例導出 : + + +* +* +* +** +* *+ +**+ * * 17 例題問題文法解答例 N={},T={,+,*},P={ + * } 中置記法 +*(+*) 前置記法 +*+* + + +* +* +*+ +*+ +*+* +*+* +*+* 導出木 + * + * 18 3

4 練習問題 2 例題問題文法 N={},T={,+,*},P={ + * } 中置記法 (*+*)*(+)* 前置記法最左導出構文木 19 練習問題 2 例題の解答例問題文法 N={},T={,+,*},P={ + * } 中置記法 (*+*)*(+)* 導出木 * * + + 解答例前置記法 **+**+ * * * ** **+ **+* **+* **+* **+** **+** **+** **+**+ **+**+ 20 文脈自由文法の曖昧性例題 5.26 どのような導出を行っても同じ導出木が得られる文法 G は曖昧でない複数の異なった導出木が構成できるような語を含む文法 G は曖昧である文法 G=(N,T,P,) において, N={,,},T={,}, P:,, この文法が曖昧であることを示せ例題 5.26 解答例同一文字列に対して 2 種類の導出木が構成可能曖昧である P: 練習問題 3 例題 5.27 文法 G=(N,T,P,) において, N={,,,C},T={,}, P: C C,,, C C この文法が曖昧であることを, の導出木を構成して示せ

5 練習問題 3 例題 5.27 解答例同一文字列に対して 2 種類の導出木が構成可能曖昧である 1. C C 2. C C C C C P: C C, C C CFG の構文図式文脈自由プロダクション構文図式 1 2 n 1 2 n 1 2 n 1 2 n C ε 25 ε 26 ここまで構文解析 CYK 法文脈自由文法で生成された文から自動的に構文木を生成する. 構文解析とは (Wikipedi より ) ある文章の文法的な関係を説明すること (prse) 計算機科学の世界では構文解析は字句解析 (Leicl nlysis) とともにおもにプログラミング言語などの形式言語の解析に使用されるまた自然言語処理に応用されることもあるコンパイラにおいて構文解析を行う機構を構文解析器 (Prser) と呼ぶ構文解析は入力テキストを通常木構造のデータ構造に変換しその後の処理に適した形にする字句解析によって入力文字列から字句を取り出しそれらを構文解析器の入力として構文木や抽象構文木のようなデータ構造を生成する構文解析入力文 ( 記号列 ) が与えられたとき, 文法によってその文を解析し, その構造を明らかにする代表的な構文解析アルゴリズム CYK 法チャート法アーリー法 LR 法構文木 ( 一郎が速いボールを軽々と投げた ) 文後置詞句動詞句後置詞句名詞句動詞句名詞助詞形容詞名詞助詞副詞動詞一郎が速いボールを軽々と投げた 5

6 CYK(Cocke-Younger-Ksmi) 法ボトムアップアルゴリズム扱える文法チョムスキーの標準形 C CYK 表構文解析の途中経過を保持するための表 CYK アルゴリズムチョムスキーの標準形で表される文脈自由文法を対象とした構文解析法チョムスキーの標準形 C (,,C Vn) ( Vn, Vt) X はチョムスキーの標準形ではないが X, に分解できる X C はチョムスキーの標準形ではないが X Y, Y C に分解できる 6

Microsoft PowerPoint - アルデIII 02回目10月14日

Microsoft PowerPoint - アルデIII 02回目10月14日アルゴリズムとデータ構造 III 2 回目 :10 月 14 日文脈自由文法,CYK 法授業資料 http://ir.cs.ymnshi.c.jp/~ysuzuki/lgorithm3/inde.html 1 2 3 4 5 6 7 8 9 授業の予定 ( 中間試験まで ) 10/07 スタック ( 後置記法で書かれた式の計算 ) 10/14 チューリング機械, 文脈自由文法 10/21 構文解析