言語処理系 （コンパイラ）

概
要
• 言語処理系の概要
• 言語とオートマトン
•
•
•
•
•
•
字句解析
構文解析
意味解析
コード生成
最適化
その他
（続き）
正規（正則）表現
[ 定義 ]
・Σ上の記号列 ｘ, ｙ に対して、ｘ と ｙ をつなぎ合せてできる記号列 ｘｙ
⇒
・Σ上の言語 L1, L2 に対して、L1 と L2 をつなぎ合せてできる L1L2 あるい
は L1・L2
⇒
・ ある言語 Ｌ に対し、言語 Ｌ に属する任意個の記号列を任意回数、任意の順
序で並べて得られる記号列のすべての集合を Ｌ*
・ ある言語 Ｌ に対し、次のような集合 Ｌ を
[ 定義 ]
Σ上の正規（正則）集合 (regular set) を次の 1) から 5) のように
定義する。
1)
2)
3)
4)
(ⅰ) Ｒ∪Ｓ [
(ⅱ) ＲＳ
[
(ⅲ) Ｒ*
[
]
]
]
5) 上記 1) から 3) の正規集合から出発して、4) の演算を有限回
繰り返すことにより得られる集合だけがΣ 上の正規集合である
[ 定義 ]
Σ上の正規（正則）表現 (regular expression) を次の 1) から 5)
のように定義する。
1)
2)
3)
4) Ｒ, Ｓ を Ｒ, Ｓ を表す Σ 上の正規表現とするとき、
(ⅰ) (Ｒ＋Ｓ) は、
(ⅱ) (ＲＳ) は、
(ⅲ) (Ｒ*) は、
5) 上記 1) から 3) の正規表現から出発して、4) の演算を有限回
繰り返すことにより得られる表現だけがΣ 上の正規表現である
注：
・ 正規表現 Ｒ で表される言語：正規言語
・ Ｌ（Ｒ） = Ｌ（Ｓ）
⇒
⇒
（例）
{ 010, 011 } からなる言語 ⇒
の和集合
と表現
算術のように扱う ：
ただし、連接の順序は変化させない
εＬ ＝
φＬ ＝
Ｌ＋φ＝
0* =
ε* =
φ* =
{ 1, 10, 100, 1000, … } ⇒
{ ε, 0, 1, 00, 01, … } =
⇒
{ ε, 00, 11, 0011, 1100, … } ⇒
[定理]
(1) 有限オートマトンＡによって識別される言語は
(2) 与えられた正規集合を識別
(2) の例：
Ａ( 01 ) ：
x を識別する有限オートマトンを Ａ(x) で表す
Ａ( 0+1 ) ：
Ａ( (0+1)* ) ：
一般的にすると …
Ａ( PQ ) ：
Ａ( P+Q ) ：
Ａ( P* ) ：
Ａ( ε+ 01( 10 + 01 )* ( 11 )* )