言語プロセッサ2005 -No.6-

言語プロセッサ2008
-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)
確認のための演習
• 教科書の７３ページ問題１
（試験に出す予定）
演習
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 について説明する。
例１： (a|b)*ab
手順
1. Flexのプログラムを書く。
2. Flexのプログラムをflexにかける。
3. 出力ファイルlex.yy.cをgccでコンパイル
する。
4. 出力a.exeを実行する。
5. さまざまな文字列を入力する。
手順
ライブラリ（ｆｌ）
Flex
Program
Flex
Lex.yy.c
文字列入力
gcc
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
+
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);
%%
練習
• 前記の各例に対して、flexで処理プログラ
ムを書け。
（試験に出す予定?）
言語プロセッサ2008
-No.6（後半）東京工科大学
コンピュータサイエンス学部
亀田弘之
字句解析から構文解析へ
• （次回の予告）
キーワード（構文解析）
• 上向き解析/下向き解析
（bottom up & top down）
• Backtracking
• 括りだし(factoring)
• 左再帰性
• First集合/Follow集合など
これから学ぶ重要な用語
上向き解析/下向き解析
数式→数式演算子数式
数式→（数式）
数式→－数式
数式→id
演算子→ ＋|－|＊|/
例： 5 + 3
(2–1)*7

Download Report