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

言語プロセッサ2008
-No.4平成20年10月8日
東京工科大学
コンピュータサイエンス学部
亀田弘之
Copyright© 2008 School of Computer Science, Tokyo University of Technology
内容
1. 前回の復習
•
オートマトン（特に、有限オートマトン）
•
•
決定性有限オートマトン
非決定性有限オートマトン
– 遷移先の曖昧性、ε遷移
2. 正規表現
3. 正規表現のε-NFAへの変換方法
4. ε-NFAのDFAへの変換方法
今日は２～4についてお話します。
Copyright© 2008 School of Computer Science, Tokyo University of Technology
正規表現
• 一般に字句は正規表現で記述できることが
多い。
• アルファベット：記号（文字）の有限集合
Copyright© 2008 School of Computer Science, Tokyo University of Technology
正規表現(定義)
アルファベットVの上の正規表現とは以下の
ものである。
1.
2.
3.
4.
5.
6.
εは正規表現
a∈Vならば、aは正規表現
rとsが正規表現ならば rs は正規表現
rとsが正規表現ならば r | s は正規表現
rが正規表現ならば r* は正規表現
以上のものだけが正規表現
Copyright© 2008 School of Computer Science, Tokyo University of Technology
正規表現（例）
• 識別子：
英字 ( 英字 | 数字 )*
Copyright© 2008 School of Computer Science, Tokyo University of Technology
字句解析プログラム(例)
if( c >= ‘a’&& c <= ‘z’ ||
c >= ‘A’ && c <= ‘Z’|| c == ‘_’){
k = 0;
while ( c >=‘a’&& c <= ‘z’||
c >= ‘A’ && c <= ‘Z’||
c >= ‘0’&& c <= ‘9’){
id[k++] = c;
}
cget( );
}
Copyright© 2008 School of Computer Science, Tokyo University of Technology
字句解析プログラムは、このように
自力で作成できるが、オートマトン
理論を知っていればもっとスマート
に作成できる。
Copyright© 2008 School of Computer Science, Tokyo University of Technology
正規表現(定義)（再）
アルファベットVの上の正規表現とは以下の
ものである。
1.
2.
3.
4.
5.
6.
εは正規表現
a∈Vならば、aは正規表現
rとsが正規表現ならば rs は正規表現
rとsが正規表現ならば r | s は正規表現
rが正規表現ならば r* は正規表現
以上のものだけが正規表現
Copyright© 2008 School of Computer Science, Tokyo University of Technology
正規表現からのNFAの構成法
（参考）これからの話の流れ
正規表現
ー＞ εーNFA
ー＞ DFA
ー＞状態数最少DFA
Copyright© 2008 School of Computer Science, Tokyo University of Technology
正規表現からのNFAの構成法
• 正規表現の定義に対応して、次のようにすれ
ばいい。
（以下、しばらく黒板で説明します。教科書の
p.54 の４．３参照のこと。）
Copyright© 2008 School of Computer Science, Tokyo University of Technology
正規表現(定義)
アルファベットVの上の正規表現とは以下の
ものである。
1.
2.
3.
4.
5.
6.
εは正規表現
a∈Vならば、aは正規表現
rとsが正規表現ならば rs は正規表現
rとsが正規表現ならば r | s は正規表現
rが正規表現ならば r* は正規表現
以上のものだけが正規表現
Copyright© 2008 School of Computer Science, Tokyo University of Technology
正規表現(定義)’
1. ε
2. a
3. rs
4. r | s
5. r*
ただし、a∈V, rとsは正規表現。
Copyright© 2008 School of Computer Science, Tokyo University of Technology
例
1. 英字 ( 英字 | 数字 )*
=> m ( m | s )*
Copyright© 2008 School of Computer Science, Tokyo University of Technology
m ( m | s )*
Copyright© 2008 School of Computer Science, Tokyo University of Technology
正規表現 m
m
Copyright© 2008 School of Computer Science, Tokyo University of Technology
正規表現 AB
A
B
Copyright© 2008 School of Computer Science, Tokyo University of Technology
正規表現 A｜B
A
B
Copyright© 2008 School of Computer Science, Tokyo University of Technology
正規表現 A*
ε
ε
A
ε
ε
Copyright© 2008 School of Computer Science, Tokyo University of Technology
練習問題
• 教科書 p.７３の問題１を練習しなさい。
Copyright© 2008 School of Computer Science, Tokyo University of Technology

Download Report