東京工科大学 コンピュータサイエンス学部 亀田弘之

Presentation on theme: "東京工科大学 コンピュータサイエンス学部 亀田弘之"— Presentation transcript:

1 東京工科大学 コンピュータサイエンス学部 亀田弘之
言語プロセッサ2015 -No.4- 東京工科大学 コンピュータサイエンス学部 亀田弘之

2 お知らせ(再) 平成27年12月14日（月）は休講。 平成27年12月19日（土）に補講の予定。
言語プロセッサ2015（東京工科大学CS学部）

3 振り返り 正規表現と有限オートマトンは同じもの。 例：パックマン 言語プロセッサ2015（東京工科大学CS学部）

4 オートマトンの例 ゲーム人工知能 PackMan RPG (Role Playing Games) など 前々回の確認
言語プロセッサ2015（東京工科大学CS学部）

5 Packmanの観察 次のサイトに行って実際にPackmanを
前々回の確認 Packmanの観察 次のサイトに行って実際にPackmanを 体験してみよう。 (参考： 【課題】 どのような内部状態が存在するか？ 内部状態を書き出す。 内部状態同士の遷移関係を表す矢印を引く。 遷移の条件およびそのときの動作を書き込む。 オートマトンとしての解釈を考える。 言語プロセッサ2015（東京工科大学CS学部）

6 PacManの状態遷移図 餌を食べた モンスターに追いかけられ、食べられる 無敵となり、 モンスターを捕食できる 無敵化の 効力喪失
言語プロセッサ2015（東京工科大学CS学部）

7 Monsterの状態遷移図 PacMan発見 迷路をうろうろする PacManを追いかける (Wander the Maze)
(Chase PacMan) PacMan見失う PacManが餌を食べ、無敵化 PacManが餌を食べ、無敵化 無敵化の効力喪失 基地に戻る (Return to Base) PacManから逃げる (Flee from PackMan) 言語プロセッサ2015（東京工科大学CS学部）

8 これからの内容 字句解析プログラムの作成方法 構文解析 手書きの方法(今年は後回し。) Flexを利用する方法 解析手法の種類
左再帰とその除去 括りだし FirstとFollow 言語プロセッサ2015（東京工科大学CS学部）

9 復習課題： Ｆlexを使ってみよう！ 自分で過去問に取り組む。 自分で新しい課題を見つける。 その他（自由に）
言語プロセッサ2015（東京工科大学CS学部）

10 手順 ライブラリ（ｆｌ） Flex Lex.yy.c gcc Flex Program a.exe 文字列入力 出力
言語プロセッサ2015（東京工科大学CS学部）

11 Flexプログラムの記述(1) delim [ \t\n] ws {delim}+ letter [a-zA-Z] digit [0-9]
id {letter}({letter}|{digit})* number {digit}+(\.{digit}+)?(E[+\-]?{digit}+)? %% 言語プロセッサ2015（東京工科大学CS学部）

12 Flexプログラムの記述(2) {ws} { /* do nothing */ } If {return(IF);}
Then {return(THEN);} else {return(ELSE);} {id} {yylval = install_id( ); return(ID);} {number} {yylval = install_num(); return(NUMBER);} 言語プロセッサ2015（東京工科大学CS学部）

13 Flexプログラムの記述(3) “<” {yylval = LT; return(RELOP);}
“<=“ {yylval = LE; return(RELOP);} “=“ {yylval = EQ; return(RELOP);} “<>” {yylval = NE; return(RELOP);} “>“ {yylval = GT; return(RELOP);} “>=“ {yylval = GE; return(RELOP);} %% 言語プロセッサ2015（東京工科大学CS学部）

14 Flexプログラムの記述(4) install_id( ){ static int id_ptr=0; return(id_ptr); }
install_num( ){ static int num_ptr=0; return(num_ptr); } 言語プロセッサ2015（東京工科大学CS学部）

15 Flexの復習 (いくつか実例をやります。) 言語プロセッサ2015（東京工科大学CS学部）

16 数式をトークンに分解する！ 練習１ 練習２ 練習３ 入力： teika + teika * zei
出力： var(teika) op(+) var(teika) op(*) var(zei) 練習２ 入力： a123 * xyz * h 出力： var(a123) op(*) var(xyz) op(+) num(120) … 練習３ 入力： x1 + x2 * ( y1 + y2) 出力： var(x1) op(+) var(x2) op(*) lpa(() var(y1) … 言語プロセッサ2015（東京工科大学CS学部）

17 手順 Flexのプログラムを書く。 Flexのプログラムをflexにかける。
出力ファイルlex.yy.cをgccでコンパイルする。この際，ライブラリーを忘れずに！ 出力a.exeを実行する。 さまざまな文字列を入力する。 言語プロセッサ2015（東京工科大学CS学部）

18 手順 ライブラリ（ｆｌ） Flex Lex.yy.c gcc Flex Program a.exe 文字列入力 出力
言語プロセッサ2015（東京工科大学CS学部）

19 実際の手順 C:\> flex sample01.l C:\> gcc lex.yy.c –lfl C:\> a.exe
それでは、実際にやってみよう。 言語プロセッサ2015（東京工科大学CS学部）

20 数式をトークンに分解する！（再） 練習１ 練習２ 練習３ 入力： teika + teika * zei
出力： var(teika) op(+) var(teika) op(*) var(zei) 練習２ 入力： a123 * xyz * h 出力： var(a123) op(*) var(xyz) op(+) num(120) … 練習３ 入力： x1 + x2 * ( y1 + y2) 出力： var(x1) op(+) var(x2) op(*) lpa(() var(y1) … 言語プロセッサ2015（東京工科大学CS学部）

21 字句解析から構文解析へ 以上で、字句解析（入門）は一応終わり。 字句解析の次の処理は、構文解析でしたね。
言語プロセッサ2015（東京工科大学CS学部）

22 構文解析編 言語プロセッサ2015（東京工科大学CS学部）

23 キーワード（構文解析） 上向き解析/下向き解析 （bottom up & top down） Backtracking
括りだし(factoring) 左再帰性 First集合/Follow集合　　など 言語プロセッサ2015（東京工科大学CS学部）

24 自然言語処理（CS学部３年後期開講科目，担当教員：亀田）
いろいろな構文解析法 構文解析手法はとてもよく研究されており、様々な手法が知られている。 例えば、 Early法 Chart法 etc. （余裕のある人は是非勉強してください） プチお知らせ 自然言語処理（CS学部３年後期開講科目，担当教員：亀田） 言語プロセッサ2015（東京工科大学CS学部）

25 処理対象の文法の性質を利用して、 より効率的な手法がいろいろと提案 されている。
言語プロセッサ2015（東京工科大学CS学部）

26 通常のプログラミング言語は、文脈自由文法ではないが、その構成要素の多くは文脈自由文法で記述可能！
Early法・Chart法　など 通常のプログラミング言語は、文脈自由文法ではないが、その構成要素の多くは文脈自由文法で記述可能！ 文法の制限の仕方にもいろいろある。 言語プロセッサ2015（東京工科大学CS学部）

27 （参考）文脈自由文法の種類 曖昧でない文法 LR(k)文法 LL(k)文法 LR(1)文法 LALR(1)文法 曖昧な文法 LL(1)文法
言語プロセッサ2015（東京工科大学CS学部）

28 LR文法とLL文法(1) LR文法に対する構文解析法（LR構文解析法） → bottom up 型
LL文法に対する構文解析法（LL構文解析法） → top down 型 （教科書76-77ページ参照） 言語プロセッサ2015（東京工科大学CS学部）

29 LR文法とLL文法(2) LR文法に対する構文解析法（LR構文解析法） → bottom up 型 ＜＝ 自動生成向き(Bison)
LL文法に対する構文解析法（LL構文解析法） → top down 型　＜＝　手作業可能 （教科書76-77ページ参照） 言語プロセッサ2015（東京工科大学CS学部）

30 LL(k)文法 構文解析は、文法規則（書き換え規則）を適用しつつ進行。
適用すべき規則は、一般には複数個存在。 →　backtrack発生 →　効率低下（回避すべき！） k文字先読で適用すべき規則が決定される文法がある！（LL(k)文法と呼ぶ） これは すごい！ Backtrackなし！ 言語プロセッサ2015（東京工科大学CS学部）

31 以下、LL(1)を取り扱います 言語プロセッサ2015（東京工科大学CS学部）

32 実例で考えよう！ 括りだし 左再帰の回避 言語プロセッサ2015（東京工科大学CS学部）

33 １．括りだし 文法 S → aBd B → b | bc 入力： abcd 言語プロセッサ2015（東京工科大学CS学部）

34 a d b c 言語プロセッサ2015（東京工科大学CS学部）

35 S B a d b c 言語プロセッサ2015（東京工科大学CS学部）

36 S B a d b c ? 言語プロセッサ2015（東京工科大学CS学部）

37 Backtrac発生！ S B a d b c 言語プロセッサ2015（東京工科大学CS学部）

38 S 解析成功！ B a d b c 言語プロセッサ2015（東京工科大学CS学部）

39 backtrack回避の方法 →　括りだし 言語プロセッサ2015（東京工科大学CS学部）

40 １．括りだし 文法 S → aBd S → aBd B → b | bc B → b (c |ε)
言語プロセッサ2015（東京工科大学CS学部）

41 左再帰の回避 A→Aβ A 無限降下だ！ β A A β 言語プロセッサ2015（東京工科大学CS学部） Fermat

42 左再帰の回避方法 A→Aα|β A → βA’ A’ → αA’ | ε （教科書81ページ参照）
言語プロセッサ2015（東京工科大学CS学部）

43 左再帰の例 E → E + T | T T → T * F | F F → ( E ) | id
言語プロセッサ2015（東京工科大学CS学部）

44 左再帰の回避 E → E + T | T T → T * F | F F → ( E ) | id E → T E’
言語プロセッサ2015（東京工科大学CS学部）

45 左再帰の回避 E → E + T | T T → T * F | F F → ( E ) | id E → T E’
T → F T’ T’ → * F T’ | ε F → ( E ) | id 言語プロセッサ2015（東京工科大学CS学部）

46 LL(1)文法 LL(1)文法は、１文字先読みすることで、適用すべき規則が一意に決まる、という性質を備え持っている。
つまり、「A→α｜β」に対して、１文字先読みすれば、 「A→α」 と「A→β」のどちらを適用すればいいのかが決まる。 （効率のよい処理が望める） 言語プロセッサ2015（東京工科大学CS学部）

47 でも、与えられた文法がLL(1)文法であることをどうやって知ることができるのだろうか？
言語プロセッサ2015（東京工科大学CS学部）

48 これは次回やりましょう。少し煩雑ですが、
LL(1)文法の判定法 First Follow これは次回やりましょう。少し煩雑ですが、 難しくはありません。 でも重要です！ 言語プロセッサ2015（東京工科大学CS学部）