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

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

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

2 これからの内容 字句解析プログラムの作成方法 構文解析 手書きの方法 Flexを利用する方法 解析手法の種類 左再帰とその除去 括りだし
FirstとFollow

3 正規表現の練習 PCを立ち上げてください。 HTMLのソースコードから情報を抽出してみよう！

4 字句解析の実際 「符号なし数」の字句解析 num → digit+ ( . digit+)? (E(+|-)?digit+)?
=> n → d+( . d+)? (E(+|-)?d+)? => num → d+(.d+|ε)( (E((+|-)|ε)) d+|ε) |ε)

5 Flexのソースコード例 D [0-9] %% [\t ] { printf("Tab or Space\n"); }
参 考 D [0-9] %% [\t ] { printf("Tab or Space\n"); } {D}+(\.{D}+)?(E(\+|\-)?{D}+)? {printf("%s\n", yytext); } . { printf("NG %s\t", yytext); }

6 識別子のシンタックス letter → a|b|c|…|z|A|B|C|…|Z digit → 0|1|2|…|9
id → letter (letter|digit)*

7 Flexのコード例 LETTER [a-zA-Z] DIGIT [0-9] %%
[\t ] { printf("Tab or Space\n"); } {LETTER}({LETTER}|{DIGIT})* {printf("id=%s\n", yytext); } . { printf("NG %s\t", yytext); }

8 符号なし数のシンタックス digit → 0|1|2|3|4|5|6|7|8|9 digits → digit digit*
optional_fraction → . digits |ε optional_exponent → (E(+|-|ε)digits)|ε num → digits optional_fraction optional_exponent

9 トークン認識プログラム作成 （教科書を参考に作成してみよう！）

10 プログラムの文法（例)

11 stmt → if expr then stmt | if expr then stmt else stmt |ε
expr → term relop　term | term term → id | num

12 if → if then → then else → else relop → <|<=|=|<>|>|>= id → letter(letter|digit)* num → digit+(.digit+)?(E(+|-)?

13 delim → blank|tab|newline
ws → delim+

14 トークン-正規表現パタン 正規表現 トークン 属性値 ws if then else id num < <= =
<> > >= （なし） relop 　　（なし） 記号表のエントリへの 　　ポインタ 　　LT 　　LE 　　EQ 　　NE 　　GT 　　GE

15 オートマトンの作成

16 ＝ ＞ ０ ６ ７ other ８

17 図. 関係演算子の遷移図 ０ 1 2 ＝ ＜ Return(relop,LE) ＞ 3 Return(relop,NE) other 4
Return(relop,LT) ＞ ＝ 5 Return(relop,EQ) ＝ ６ ７ Return(relop,GE) other ８ Return(relop,GT) 図. 関係演算子の遷移図

18 Return(get_token( ), install_id( ))
letter letter other 9 10 11 Return(get_token( ), install_id( )) digit 図. 識別子とキーワードに対する遷移図

19 . digit digit － E ＋ digit other digit E digit digit digit 図. 数の遷移図(1)
17 digit 12 digit － 13 E 19 ＋ digit . other digit 16 18 E 14 digit 15 digit digit 図. 数の遷移図(1)

20 . digit digit digit digit digit digit other 図. 数の遷移図(2) 20 21 22 23 24
25 26 27 図. 数の遷移図(2)

21 単純な遷移図 b 1 a a 2 b

22 state = 0; while(TRUE) { switch(state) { case 0: c = nextChar( ); /* 先読み */ switch(c){ case ‘a’: state = 1; break; case ‘b’: state = 2; break; } case 1: c = nextChar( ); case ‘a’: state = 2; break; case ‘b’: state = 1; break; } }

23 state = 0; while(TRUE) { switch(state) { case 0: c = nextChar( ); /* 先読み */ switch(c){ case ‘a’: state = 1; break; case ‘b’: state = 2; break; } case 1: c = nextChar( ); case ‘a’: state = 2; break; case ‘b’: state = 1; break; } }

24 簡単な遷移図 b 26 a a 25 a 27 b b 28

25 練習問題 直前のページのオートマトンをシミュレートするプログラムを作成せよ。 符号なし数を処理する字句解析プログラムを作成せよ。
次ページに示した（C言語の）浮動小数点定数を処理する字句解析プログラムを作成せよ。

26 参考： （C言語の）浮動小数点定数 ． Numbers Numbers f Numbers ． e + l Numbers Numbers
－ F L

27 今度はflexを使ってみよう！

28 手順 ライブラリ（ｆｌ） Flex Lex.yy.c gcc Flex Program a.exe 文字列入力 出力

29 Flexプログラムの記述(1) delim [ \t\n] ws {delim}+ letter [a-zA-Z] digit [0-9]
id {letter}({letter}|{digit})* number {digit}+(\.{digit}+)?(E[+\-]?{digit}+)? %%

30 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);}

31 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);} %%

32 Flexプログラムの記述(4) install_id( ){ static int id_ptr=0; return(id_ptr); }
install_num( ){ static int num_ptr=0; return(num_ptr); }

33 Flexのデモ

34 手順 Flexのプログラムを書く。 Flexのプログラムをflexにかける。 出力ファイルlex.yy.cをgccでコンパイルする。
出力a.exeを実行する。 さまざまな文字列を入力する。

35 手順 ライブラリ（ｆｌ） Flex Lex.yy.c gcc Flex Program a.exe 文字列入力 出力

36 実際の手順 C:\> flex sample01.l C:\> gcc lex.yy.c –lfl C:\> a.exe
それでは、実際にやってみよう。

37 字句解析から構文解析へ 以上で、字句解析は終わり。 字句解析の次の処理は、構文解析でしたね。

38 構文解析編

39 キーワード（構文解析） 上向き解析/下向き解析 （bottom up & top down） Backtracking
括りだし(factoring) 左再帰性 First集合/Follow集合　　など

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

41 処理対象の文法の性質を利用して、 より効率的な手法がいろいろと提案 されている。

42 通常のプログラミング言語は、文脈自由文法ではないが、その構成要素の多くは文脈自由文法で記述可能！
Early法・Chart法　など 通常のプログラミング言語は、文脈自由文法ではないが、その構成要素の多くは文脈自由文法で記述可能！ 文法の制限の仕方にもいろいろある。

43 LR文法とLL文法(1) LR文法に対する構文解析法（LR構文解析法） → bottom up 型
LL文法に対する構文解析法（LL構文解析法） → top down 型 （教科書76-77ページ参照）

44 LR文法とLL文法(2) LR文法に対する構文解析法（LR構文解析法） → bottom up 型 ＜＝ 自動生成向き(Bison)
LL文法に対する構文解析法（LL構文解析法） → top down 型　＜＝　手作業可能 （教科書76-77ページ参照）

45 LL(k)文法 構文解析は、文法規則（書き換え規則）を適用しつつ進行。
適用すべき規則は、一般には複数個存在。 →　backtrack発生 →　効率低下（回避すべき！） k文字先読で適用すべき規則が決定される文法がある！（LL(k)文法と呼ぶ） これは すごい！ Backtrackなし！

46 以下、LL(1)を取り扱います

47 実例で考えよう！ 括りだし 左再帰の回避

48 １．括りだし 文法 S → aBd B → b | bc 入力： abcd

49 a d b c

50 S B a d b c

51 S B a d b c ?

52 Backtrac発生！ S B a d b c

53 S 解析成功！ B a d b c

54 backtrack回避の方法 →　括りだし

55 １．括りだし 文法 S → aBd　　　　　　　　 S → aBd B → b | bc　　　　　　　B → b (c |ε)

56 左再帰の回避 A→Aβ A 無限降下だ！ β A A β Fermat

57 左再帰の回避方法 A→Aα|β A → βA’ A’ → αA’ | ε （教科書81ページ参照）

58 左再帰の例 E → E + T | T T → T * F | F F → ( E ) | id

59 左再帰の回避 E → E + T | T T → T * F | F F → ( E ) | id E → T E’

60 左再帰の回避 E → E + T | T T → T * F | F F → ( E ) | id E → T E’
T → F T’ T’ → * F T’ | ε F → ( E ) | id

61 LL(1)文法 LL(1)文法は、１文字先読みすることで、適用すべき規則が一意に決まる、という性質を備え持っている。
つまり、「A→α｜β」に対して、１文字先読みすれば、 「A→α」 と「A→β」のどちらを適用すればいいのかが決まる。 （効率のよい処理が望める）

62 　でも、与えられた文法がLL(1)文法であることをどうやって知ることができるのだろうか？

63 これは後日やりましょう。少し煩雑ですが、難しくはありません。
LL(1)文法の判定法 First Follow これは後日やりましょう。少し煩雑ですが、難しくはありません。 でも重要ですよ！