東京工科大学 コンピュータサイエンス学部 亀田弘之 言語プロセッサ2007 -No.6- 東京工科大学 コンピュータサイエンス学部 亀田弘之
内容 前回の復習と演習 正規表現のε-NFAへの変換方法 ε-NFAのDFAへの変換方法 Lexの紹介 構文解析（重要）
前回の復習 処理対象を正規表現で記述 正規表現→ε-NFA ε-NFA →DFA DFA→状態数最小DFA 例題：正規表現 (ab|bc)*a(b|c)
確認のための演習 教科書の７３ページ問題１ （試験に出す予定）
演習 ただし、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 = { +, - }
発展課題 ー 字句解析プログラム ー 教科書p.72～p.73のソースコードを解析せよ。 (典型的なコードですので、一度ゆっくり 解読することをお勧めします。 このあたりは、後日また授業で解説し ます。)
ここから今日の話
正規表現認識プログラム 例： (a|b)*ab C言語の浮動小数点定数 など
方法 Java, C, Pascalなどで記述することはできるが、以下では、flexを用いる方法を紹介する。 まず、(a|b)*ab について説明する。
例１： (a|b)*ab
手順 Flexのプログラムを書く。 Flexのプログラムをflexにかける。 出力ファイルlex.yy.cをgccでコンパイルする。 出力a.exeを実行する。 さまざまな文字列を入力する。
手順 ライブラリ（ｆｌ） Flex Lex.yy.c gcc Flex Program a.exe 文字列入力 出力
（１）flexのプログラムを書く %% [\t ] { } (a|b)*ab { printf(“OK %s\n”,yytext); } . { printf(“NG %s\n”,yytext); } <<注>> sample01.lに格納。
（２）＆（３） flexとgccを使用 C:\> flex sample01.l C:\> gcc lex.yy.c –lfl C:\> a.exe それでは、実際にやってみよう。
例2：正負の整数 FIGURE [0-9] %% -{FIGURE}+ {printf("negative integer\n");} \+?{FIGURE}+ {printf("positive integer\n");}
（参考）正負の整数・実数 数 → 整数|実数 整数 → 正整数｜負数 正整数 → 符号付正整数｜符号なし正整数 負数 → 符号付負数 符号付正整数 → ＋（0|1|2|…|9）+ 符号なし正整数 → （0|1|2|…|9）+ 符号付負整数 → ー（0|1|2|…|9）+
例3： （C言語の）浮動小数点定数 ． Numbers Numbers ． f Numbers e + l Numbers Numbers － F L
例3： （C言語の）浮動小数点整数 正規表現は、… ((([0-9]*\.[0-9]+)|([0-9]+\.))|([0-9]+)) ([eE][+-]?[0-9]+)?[flFL]?
例4：学籍番号 学籍番号の構造： [0-9]{2,2}(A|B|C|D|P)[0-9]{3,3}
%% [0-9]{2,2}(A|B|C|D|P)[0-9]{3,3} printf(“%s(Student ID)”,yytext);
練習 前記の各例に対して、flexで処理プログラムを書け。 （試験に出す予定）
東京工科大学 コンピュータサイエンス学部 亀田弘之 言語プロセッサ2007 -No.6（後半）- 東京工科大学 コンピュータサイエンス学部 亀田弘之
字句解析から構文解析へ
キーワード（構文解析） 上向き解析/下向き解析 （bottom up & top down） Backtracking 括りだし(factoring) 左再帰性 First集合/Follow集合 など
上向き解析/下向き解析 数式→数式 演算子 数式 数式→（数式） 数式→－数式 数式→id 演算子→ ＋|－|＊|/ 例： 5 + 3 ( 2 – 1 ) * 7