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

言語プロセッサ2014
-No.2平成26年9月29日
東京工科大学
コンピュータサイエンス学部
亀田弘之
Copyright© 2014 School of Computer Science, Tokyo University of Technology
復習から
2
Copyright© 2014 School of Computer Science, Tokyo University of Technology
数式の解析
•
kingaku = teika + teika * shouhizei
3
Copyright© 2014 School of Computer Science, Tokyo University of Technology
数式の解析
1. 読み込み（文字列として）
“kingaku = teika + teika * shouhizei”
2. 要素(token)の切り出し
“kingaku”, “=“, “teika”, “+”, “*”, “shouhizei”
3. 要素の相互関係の分析
＝
kingaku
+
teika
*
teika
shouhizei
4
Copyright© 2014 School of Computer Science, Tokyo University of Technology
#include <stdio.h>
main(){
float kingaku = 0, teika = 100;
float shouhizei = 0.10;
kingaku = teika + teika*shouhizei;
printf("kingaku=%f\n", kingaku);
}
ソース言語
読み込み
字句解析
分析
構文解析
.file
"test2.c"
___main;
.scl
.type
32;
.section .rdata,"dr"LC3:
"kingaku=%f\12\0" .text.globl _main
_main;
.scl
.type
32;
pushl
%ebp
%esp, %ebp
andl
subl
$32, %esp
___main
movl
movl
%eax, 28(%esp)
$0x42c80000, %eax
%eax, 24(%esp)
movl
movl
%eax, 20(%esp)
24(%esp)
fmuls
fadds
24(%esp)
28(%esp)
flds
fstpl
4(%esp)
$LC3, (%esp)
call
leave
ret
_printf;
.scl
.type
32;
.endef
.def
2;
.endef
.ascii
.def
2;
.endef_main:
movl
$-16, %esp
call
$0x00000000, %eax
movl
movl
$0x3dcccccd, %eax
flds
20(%esp)
fstps
28(%esp)
movl
_printf
.def
2;
中間語生成
合成
コード生成
目的言語
5
Copyright© 2014 School of Computer Science, Tokyo University of Technology
ソース言語
読み込み
字句解析
分析
構文解析
中間語生成
合成
コード生成
目的言語
6
Copyright© 2014 School of Computer Science, Tokyo University of Technology
数式の解析
1. 読み込み（文字列として）
“kingaku = teika + teika * shouhizei”
2. 要素(token)の切り出し
“kingaku”, “=“, “teika”, “+”, “*”, “shouhizei”
3. 要素の相互関係の分析
＝
kingaku
+
teika
*
teika
shouhizei
7
Copyright© 2014 School of Computer Science, Tokyo University of Technology
数式の解析
1. 読み込み（文字列として）
“kingaku = teika + teika * shouhizei”
2. 要素(token)の切り出し
“kingaku”, “=“, “teika”, “+”, “*”, “shouhizei”
3. 要素の相互関係の分析
＝
kingaku
+
teika
*
teika
shouhizei
8
Copyright© 2014 School of Computer Science, Tokyo University of Technology
数式の解析
1. 読み込み（文字列として）
“kingaku = teika + teika * shouhizei”
2. 要素(token)の切り出し
“kingaku”, “=“, “teika”, “+”, “*”, “shouhizei”
3. 要素の相互関係の分析
＝
kingaku
+
teika
*
teika
shouhizei
9
Copyright© 2014 School of Computer Science, Tokyo University of Technology
数式の解析
1. 読み込み（文字列として）読み込み
“kingaku = teika + teika * shouhizei”
2. 要素(token)の切り出し語句解析
“kingaku”, “=“, “teika”, “+”, “*”, “shouhizei”
3. 要素の相互関係の分析構文解析
＝
kingaku
+
teika
*
teika
shouhizei
10
Copyright© 2014 School of Computer Science, Tokyo University of Technology
数式の解析
1. 読み込み
– ファイルからの入力技法
2. 字句解析
– 有限オートマトンの理論
– 正規文法
– 正規表現
3. 構文解析
– 線形有界オートマトン理論
– 文脈自由文法
11
Copyright© 2014 School of Computer Science, Tokyo University of Technology
前提知識
• 言語理論とオートマトン
– 前期科目「言語理論とオートマトン」
– 抽象的・論理的な思考への慣れ
(特に、正規表現と有限オートマトン)
• プログラミング技法
– 今までいろいろと習ってきましたよね！
– 基本的な知識があれば一応OK
– ファイルの入出力が難しい人もいるかも…
12
Copyright© 2014 School of Computer Science, Tokyo University of Technology
学んで得られるもの
• 言語理論とオートマトン
– 抽象的・論理的な思考への慣れ
– ソフトウェア分野における基本的概念
• 正規表現 etc.
• プログラミング言語へのより深い理解
• プログラミング技法
– プログラミング力（知識）アップ
– 洗練されたアルゴリズムの理解
などなど
13
Copyright© 2014 School of Computer Science, Tokyo University of Technology
• 言語プロセッサ関連は、コンピュータサイエン
スの英知が集積されている！
• この授業を取った人は先見の明がある！
14
Copyright© 2014 School of Computer Science, Tokyo University of Technology
今日の内容
1.
2.
3.
4.
5.
正規表現 (regular expressions; re)
オートマトン (automaton, pl. automata)
正規表現とオートマトンとの関係
オートマトンのシミュレータ
デモ
15
Copyright© 2014 School of Computer Science, Tokyo University of Technology
今日の学習目標
1. 正規表現が使える。
2. オートマトンを理解し，作れる。
16
Copyright© 2014 School of Computer Science, Tokyo University of Technology
１．正規表現
• 正規表現とは
– 聞いたことのある人は？
– 使ったことのある人は？
– 使い方説明できる人は？
①
②
③
どんな時に正規表現を使うのか？
17
Copyright© 2014 School of Computer Science, Tokyo University of Technology
正規表現とは
• 文字列のパターンを表現するためのもの
– 例：
1.
2.
3.
4.
{ a, aa, aaa, aaaa, aaaaa, ．．．}
{ 1, 01, 001, 0001, 00001, ．．．}
{ aab, bab }
{ 2, 4, 6, 8, 10, ．．．} ( = 正の偶数全体の集合 )
など
パターンが見つかりましたか？
18
Copyright© 2014 School of Computer Science, Tokyo University of Technology
練習
• いま current directory に以下のような
(名前の)ファイルがあるとする。
program62
infile2010
procedure71
filedummy777
profileV7 prototype52 parser
outfile777 file256
fixer8
• 問１ proで始まるファイル名のもの
• 問２ fileを含むもの
• 問３末尾に数字がありそれが偶数のもの
19
Copyright© 2014 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* は正規表現
以上のものだけが正規表現
20
Copyright© 2014 School of Computer Science, Tokyo University of Technology
正規表現
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
a
b
ab
a|b
a|(a|b)
a*
(a|b)*
a|b*
ab*
(ab)*
正規表現の例
具体的な文字列
1. {
2. {
3. {
4. {
5. {
6. {
7. {
8. {
9. {
10.{
}
}
}
}
}
}
}
}
}
}
21
Copyright© 2014 School of Computer Science, Tokyo University of Technology
有限オートマトンの定義
FA = ( K, Σ, δ, q0, F )
ただし、
K ：状態の集合( Kは有限集合)
Σ ：入力アルファベット（Σは有限集合）
δ ：状態遷移関数
δ： K×Σ∋( qi , a ) → qj ∈ K
q0 ：初期状態
そうなの
ですね
F ：最終状態の集合 ( F ⊆ K )
22
Copyright© 2014 School of Computer Science, Tokyo University of Technology
オートマトンのイメージ
遷移条件
（出力）
内部
状態
内部
状態
初期状態
最終状態など
23
Copyright© 2014 School of Computer Science, Tokyo University of Technology
オートマトンの例
• ゲーム人工知能
– PackMan
– RPG (Role Playing Games) など
24
Copyright© 2014 School of Computer Science, Tokyo University of Technology
今日の演習１
Packmanの観察
次のサイトに行って実際にPackmanを
体験してみよう。 (参考： http://j-game.net/packman.html)
【課題】
1.
2.
3.
4.
5.
どのような内部状態が存在するか？
内部状態を書き出す。
内部状態同士の遷移関係を表す矢印を引く。
遷移の条件およびそのときの動作を書き込む。
オートマトンとしての解釈を考える。
25
Copyright© 2014 School of Computer Science, Tokyo University of Technology
次の話題
オートマトンと正規表現の関係
• （有限）オートマトンと正規表現とは対応関係
にある。
つまり、(有限)オートマトンは正規表現で書き
表せるとともに、正規表現は(有限)オートマト
ンで書き表せる。
26
Copyright© 2014 School of Computer Science, Tokyo University of Technology
今日の演習２
練習
問正規表現 b(a|b)a を考える。
1. この正規表現が表わす文字列をすべて求めよ。
2. この正規表現の表わす文字列をすべて、かつ、
それらだけを受理するオートマトンを作れ。
27
Copyright© 2014 School of Computer Science, Tokyo University of Technology
もっと練習
問次の正規表現と等価なオートマトンを作れ。
1. ab
2. a*
3. 01(10|01)*11
28
Copyright© 2014 School of Computer Science, Tokyo University of Technology
オートマトンのシミュレータ
s = s0;
c = nextChar( );
while( c != eof ) {
積極的に理解
s = move( s, c );
しよう！
c = nextChar( );
}
if(sがFに含まれる) return “yes”;
else return “no”;
29
Copyright© 2014 School of Computer Science, Tokyo University of Technology
字句解析プログラムは、当然なが
ら自力で作成できるが、オートマト
ン理論を知っていればスマートに
作成できる。
30
Copyright© 2014 School of Computer Science, Tokyo University of Technology
Flexを使った例
• 正規表現 a(a|b)*c を受理するオートマトンを
シミュレートするプログラムの自動生成が可
能。
31
Copyright© 2014 School of Computer Science, Tokyo University of Technology
デモ
• （詳しくは後日）
32
Copyright© 2014 School of Computer Science, Tokyo University of Technology
次回までの予習（準備）
• 自分が普段使っているテキストエディタでは、
正規表現を扱えるか確認しなさい。
• 使えない場合は、正規表現が使えるエディタ
を探し、インストールしなさい。
本授業としては、復習をしっ
かりやすことをお勧めします。
33
Copyright© 2014 School of Computer Science, Tokyo University of Technology

Download Report