言語プロセッサ2009 -No.6東京工科大学 コンピュータサイエンス学部 亀田弘之 今日の内容 1. 前回の復習と演習 1. 正規表現のε-NFAへの変換方法 2. ε-NFAのDFAへの変換方法 2. Lexの紹介 3. 構文解析(重要) <=これは もう少し後で 前回の復習 1. 2. 3. 4. 処理対象を正規表現で記述 正規表現→ε-NFA ε-NFA →DFA <=ここまでやりました。 DFA→状態数最小DFA 例題:正規表現 (ab|bc)*a(b|c) 確認のための演習 • 教科書の73ページ問題1 (試験に出す予定ですので、各自練習して おいてください。) 演習 1. 次の正規表現αについて答えよ。 1. 簡単化せよ。 2. αを受理する状態数最少のDFNを作れ。 α = dd* | dd*.dd* | .dd* | | dd*E(s|ε)dd* |E(s|ε)dd* |.dd*E(s|ε)dd* ただし、d = { 0, 1, 2, 3, …, 9 }, s = { +, - } 発展課題 ー 字句解析プログラム ー 1. 教科書p.72~p.73のソースコードを解 析し、自分の言葉で説明しなさい。 (典型的なコードですので、一度ゆっくり 解読することをお勧めします。) ここから今日の話 正規表現認識プログラム • 例: – (a|b)*ab – C言語の浮動小数点定数 など 方法 • Java, C, Pascalなどで記述することはでき るが、以下では、flexを用いる方法を紹介 する。 • まず、(a|b)*ab について説明する。 例1: (a|b)*ab 手順 1. Flexのプログラムを書く。 2. Flexのプログラムをflexにかける。 3. 出力ファイルlex.yy.cをgccでコンパイル する。 4. 出力a.exeを実行する。 5. さまざまな文字列を入力し、動作を確認 する。 手順 ライブラリ(fl) Flex Program Flex Lex.yy.c 文字列入力 gcc a.exe 出力 (1)flexのプログラムを書く %% [\t ] { } (a|b)*ab { printf(“OK %s\n”,yytext); } . { printf(“NG %s\n”,yytext); } %% <<注>> sample01.lに格納。 (2)&(3) 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 + Numbers l Numbers E - 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); %%
© Copyright 2024 ExpyDoc