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

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

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

2 内容 前回の復習と演習 正規表現のε-NFAへの変換方法 ε-NFAのDFAへの変換方法 Lexの紹介 構文解析（重要）

3 前回の復習 処理対象を正規表現で記述 正規表現→ε-NFA ε-NFA →DFA DFA→状態数最小DFA
　例題：正規表現 (ab|bc)*a(b|c)

4 確認のための演習 教科書の７３ページ問題１ （試験に出す予定）

5 演習 ただし、d = { 0, 1, 2, 3, …, 9 }, s = { +, - } 次の正規表現αについて答えよ。 簡単化せよ。
αを受理する状態数最少のDFNを作れ。 α = dd* | dd*.dd* | .dd* | | dd*E(s|ε)dd* |E(s|ε)dd* |.dd*E(s|ε)dd* ただし、d = { 0, 1, 2, 3, …, 9 }, s = { +, - }

6 発展課題 ー 字句解析プログラム ー 教科書p.72～p.73のソースコードを解析せよ。 (典型的なコードですので、一度ゆっくり 　解読することをお勧めします。 　このあたりは、後日また授業で解説し　 　ます。)

7 ここから今日の話

8 正規表現認識プログラム 例： (a|b)*ab C言語の浮動小数点定数 など

9 方法 Java, C, Pascalなどで記述することはできるが、以下では、flexを用いる方法を紹介する。
まず、(a|b)*ab について説明する。

10 例１： (a|b)*ab

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

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

13 （１）flexのプログラムを書く %% [\t ] { } (a|b)*ab { printf(“OK %s\n”,yytext); }
. { printf(“NG %s\n”,yytext); } <<注>>　sample01.lに格納。

14 （２）＆（３） flexとgccを使用 C:\> flex sample01.l C:\> gcc lex.yy.c –lfl
C:\> a.exe それでは、実際にやってみよう。

15 例2：正負の整数 FIGURE [0-9] %% -{FIGURE}+ {printf("negative integer\n");}
\+?{FIGURE}+ {printf("positive integer\n");}

16 （参考）正負の整数・実数 数 → 整数|実数 整数 → 正整数｜負数 正整数 → 符号付正整数｜符号なし正整数 負数 → 符号付負数
符号付正整数 → ＋（0|1|2|…|9）+ 符号なし正整数 → （0|1|2|…|9）+ 符号付負整数 → ー（0|1|2|…|9）+

17 例3： （C言語の）浮動小数点定数 ． Numbers Numbers ． f Numbers e + l Numbers Numbers
－ F L

18 例3： （C言語の）浮動小数点整数 正規表現は、… ((([0-9]*\.[0-9]+)|([0-9]+\.))|([0-9]+))
([eE][+-]?[0-9]+)?[flFL]?

19 例4：学籍番号 学籍番号の構造： [0-9]{2,2}(A|B|C|D|P)[0-9]{3,3}

20 %% [0-9]{2,2}(A|B|C|D|P)[0-9]{3,3} printf(“%s(Student ID)”,yytext);

21 練習 前記の各例に対して、flexで処理プログラムを書け。 （試験に出す予定）

22 東京工科大学 コンピュータサイエンス学部 亀田弘之
言語プロセッサ2007 -No.6（後半）- 東京工科大学 コンピュータサイエンス学部 亀田弘之

23 字句解析から構文解析へ

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

25 上向き解析/下向き解析 数式→数式 演算子 数式 数式→（数式） 数式→－数式 数式→id
演算子→ ＋|－|＊|/ 例： ( 2 – 1 ) * 7