() / (front end) (back end) (phase) (pass) 1 2

(1)

コンパイラの構成

コンパイラの解析部

(

フロントエンド

)

コンパイラの合成部

(

バックエンド

)

正規表現

有限オートマトン

正規表現からオートマトンへの変換

lex

による字句解析

文脈自由文法

文脈自由文法による導出と解析木

最左導出と解析木

最右導出と解析木

解析木の先行順走査

解析木の後行順走査

山田俊行

http://www.cs.info.mie-u.ac.jp/~toshi/lectures/compiler/

2018

年

4 月

(2)

コンパイラの構成

コンパイラは，ソースコードを受け取り，何段階かの処理で中間段階の表現を経て，命令列を生成する． ●構成図 ON ML HI

_{ソースコード}

JK

文字列

字句解析

字句列

構文解析

解析木/構文木

記号表

pp !! nn == ss

意味解析・中間コード生成

中間コード

最適化・目的コード生成

命令列

ON ML HI

_{目的コード}

JK ●基本用語フロントエンド (front end) コンパイラの処理の前半部分で，ソースコードを解析バックエンド (back end) コンパイラの処理の後半部分で，目的コードを合成フェーズ (phase) 処理の論理的なまとまり ※上図のが各フェーズパス (pass) ソースプログラムを先頭から順に読んで行う 1 度の処理 ※いくつかのフェーズを一つのパスにまとめる

(3)

コンパイラの解析部 (フロントエンド)

コンパイラの前半部分であるフロントエンドでは，ソースコードを解析して各要素のもつ意味を調べる．

●ソースコード

var left, right; fun int main() {

left = 0; right = 10;

return ((left + right) / 2); }

↓ 字句解析

●トークン列

VAR ID:left , ID:right ; FUN INT ID:main ( ) { ID:left = NUM:0 ; ID:right = NUM:10 ; RETURN ( ( ID:left + ID:right ) / NUM:2 ) ; }

↓ 構文解析 ●構文木/解析木

prog

gggggggggggg gggg W W W W W W W W W W W W W W W W

var

seq

ooooooo OOOOOOO O

seq

???

fun

ooooooo ???O?OOOOO O

◦

left

seq

????

int main

◦

◦ seq

oooooooo OOOO O O O

right

◦

=

?????

seq

oooooooo OOOO O O O

left

0 =

????

seq

????

right

10 ret

◦

/

???? ?

+

????

2 left

right

(4)

コンパイラの合成部 (バックエンド)

コンパイラの後半部分であるバックエンドでは，解析で得たプログラムの情報を元に命令列を合成する． ●抽象構文木

=

mmmmmmm RRRRRR R

val

/

kkkkkkkRRRRRRR

*

mmmmmmm QQQQQQ Q

m

+

||||| DDDD D

+

||||| DDDD D

n

1 n

1

↓ 意味解析・中間コード生成 ●中間コード

tmp1 = n + 1

tmp2 = n + 1

tmp3 = tmp1 * tmp2

val

= tmp3 / m

↓ 最適化

tmp1 = n + 1

tmp3 = tmp1 * tmp1

val

= tmp3 / m

↓ 目的コード生成 ●目的コード

LD

R1

n

ADD

R1

1 ST

tmp1

R1

LD

R1

tmp1

MUL

R1

tmp1

ST

tmp3

R1

LD

R1

tmp3

DIV

R1

m

ST

val

R1

(5)

正規表現

正規表現は，選択・連接・反復を使って文字列集合を表す記法であり，字句の構文を正確に書ける． ●正規表現の定義文字集合 Σ 上の正規表現を，以下の場合分けで帰納的に定義する． • ∅ と ϵ は正規表現 • a ∈ Σ ならば，a は正規表現 • R と S が正規表現ならば，選択 (R | S)，連接 (R S)，反復 (R∗₎_{は正規表現} 正規表現の括弧を省くときには，選択や連接が結合的（左右どちらから考えても同じ）で，優先順位が 選択 < 連接 < 反復の順であると約束する．最外の括弧も省ける． ●正規表現が表す文字列集合正規表現は文字列の集合を表す．その対応を次の表に示す．正規表現文字列集合意味 ∅ ∅ 空集合 ϵ { ε } 空列単体 a { a } 文字単体 R| S LR∪ LS 選択 R S { xy | x ∈ LR, y∈ LS} 連接 R∗ { x1x2· · · xn| n ≥ 0, x1, x2, . . . , xn ∈ LR} 反復 ここで，ε は (長さ 0 の) 空文字列，xy は文字列 x の後に文字列 y を並べたものである．また，この表 では，正規表現 R と S が表す文字列集合を LRと LSで表した． ●正規表現による字句構文の定義例 2進定数の字句構文の定義を正規表現を使って書く．2 進定数とは，集合{ 0, 1 } 上の長さ 1 以上の文字 列のうち，先頭が 0 なら長さが 1，という条件を満たすものである，と定義する．正規表現を使えば，この定義は，2 進定数 ::= 0 | 1 ( 0 | 1 )∗ と簡潔に書ける． ●参考文献 • 『オートマトン言語理論計算論 I』，第 2 版， J.ホップクロフト，R. モトワニ，J. ウルマン，サイエンス社，2003．形式言語と計算機械についての標準的な教科書，第 3 章正則表現と正則言語を参照． • 『詳説正規表現』，第 3 版， J. E. F.フリードル，オライリー・ジャパン，2008．正規表現の仕組みや利用法の詳しい解説．

(6)

有限オートマトン

有限オートマトンは，文字列の認識機械の数学モデルである．入力を 1 文字ずつ読んで状態遷移し，入力文字列がパターンに合うかを判定できる． ●有限オートマトンの定義 (決定性) 有限オートマトンは，次の五つ組 (Q, Σ, δ, q0, F )で定まる． Q · · · 状態の有限集合 Σ · · · 入力文字の有限集合 δ · · · 遷移関数，状態 q と入力文字 a から次状態 δ(q, a) を決定 q0 · · · 開始状態，q0∈ Q F · · · 受理状態集合，F ⊆ Q ●有限オートマトンの図示有限オートマトンは，遷移図でも表せる．状態は円内に書き，遷移は入力文字を添えた矢印で表す．開始状態は始点に状態がない矢印の終点に示し，受理状態は 2 重丸で表す． GFED @ABC

_A

//

0, 1, %

a, b

_//GFED_@ABC_?>=<_89:;

B

a, b, 0, 1

%

?>=< 89:;

_C

a, b, 0, 1, %

II この例で，状態集合は Q ={ A, B, C }，入力文字集合は Σ = { a, b, 0, 1, % }，遷移関数 δ は，以下の遷移 表でも表せる．開始状態は q0= A，受理状態集合は F ={ B } である． a b 0 1 % A B B C C C B B B B B C C C C C C C 有限オートマトンは，初期状態から始めて，入力文字列を 1 文字ずつ読み，現状態と読んだ文字に応じて状態遷移する．入力を読み終えたときに受理状態なら，入力文字列を (正しい綴りとして) 受理する． 例えば，入力文字列 ab1 は，このオートマトンで受理される．状態が A, B, B, B と遷移し，入力を読み 終えた状態 B が受理状態だからである．一方，入力文字列 b0%a は，このオートマトンで受理されない． 状態が A, B, B, C, C と遷移し，入力を読み終えた状態 C が受理状態でないからである． ●参考文献 • 『オートマトン言語理論計算論 I』，第 2 版， J.ホップクロフト，R. モトワニ，J. ウルマン，サイエンス社，2003，第 2 章有限オートマトン．

(7)

正規表現からオートマトンへの変換

字句構文を正規表現で書けば，構文に合う文字列を受理する抽象機械 (字句解析器) へと自動変換できる． ●正規表現 (字句構文の定義に使用)

0 | 1 ( 0 | 1 )

∗ ↓ 再帰的に合成 ●非決定性有限オートマトン (複数の遷移先や空語遷移を許可) ?>=< 89:;_B 0 _//?>=<_89:; C ε ** ?>=< 89:;_A // ε .. ε && ?>=< 89:;76540123_D ?>=< 89:;_E 1 _//?>=<_89:; F ε // ?>=<89:;G ε // ε >> ?>=< 89:;_H ε _// ε --?>=< 89:;_I 0 _//?>=<_89:; J ε // ?>=<89:;K ε // ε zz ?>=< 89:;_L ε 88 ?>=< 89:;_M 1 _{// ?>=<}_89:; N ε CC ↓ 遷移先を集合に統合 ●決定性有限オートマトン (状態と入力から遷移先が一つに決定) ?> =< 89/.(){ C, D }:;-,*+ 0, 1 //?> =<89 :;{ } 0, 1 ?> =< 89{ A, B, E }:; // 0_j_jjjj 44j j j j j j 1 ''O O O O O O O ?> =< 89/.(){ F, G, H, I, M, L, D }:;-,*+ 0 // 1 66 ?> =< 89/.(){ J, K, H, I, M, L, D }:;-,*+ 0 1 _//?> =< 89/.(){ N, K, H, I, M, L, D }:;-,*+ 0 oo 1 ↓ 区別できない状態を統合 ●状態数最小の決定性有限オートマトン (字句解析に使用) GFED

@ABC?>=<89:; 0, 1 // GFED@ABC 0, 1 GFED @ABC // 0_r_rrr 88r r r r 1LLL &&L L L L L GFED @ABC?>=<89:; 0, 1

(8)

lex

による字句解析

lexを使うと，字句解析プログラムを自動生成できる．lex 記述では，字句の構文規則を正規表現で与え，動作規則をコード片として書く．

● lex 記述の例

/*

* cprime.l -- CPrime 言語の字句構文の flex 記述

*

* 使い方： flex cprime.l && gcc lex.yy.c -lfl && ./a.out < input.txt */ %% var printf("VAR "); fun printf("FUN "); void printf("VOID "); int printf("INT "); if printf("IF "); else printf("ELSE "); while printf("WHILE "); return printf("RETURN "); "==" printf("EQ "); "!=" printf("NEQ "); "<=" printf("LEQ "); ">=" printf("GEQ "); [+\-*/%<>=(){},;] printf("%c ", *yytext); [0-9]+ printf("NUM:%s ", yytext); [_a-zA-Z][_a-zA-Z0-9]* printf("ID:%s ", yytext); [ \t\n]+ /* 空白類を無視 */

. printf("??? "); /* 誤り */ %%

int main(void) { yylex(); printf("\n"); return 0; }

●実行例入力

if else while return var fun void int + - * / % > >= < <= == != =

( ) { } , ; 123 value @

var x;

fun void main() { x = 5;

}

出力

IF ELSE WHILE RETURN VAR FUN VOID INT + - * / % > GEQ < LEQ EQ NEQ = ( ) { } , ; NUM:123 ID:value ??? VAR ID:x ; FUN VOID ID:main ( ) { ID:x = NUM:5 ; }

(9)

文脈自由文法

文脈自由文法は，生成規則を使って記号列の集合を表す記法であり，言語の構文定義を正確に書ける． ●文脈自由文法の定義 文脈自由文法 (context-free grammar) は，次の四つ組 (V, T, P, S) で定まる． V · · · 変数 (variable)(非終端記号ともいう) の有限集合 T · · · 終端記号 (terminal symbol) の有集限合

P · · · 生成規則 (production rule) A → α の有限集合，A ∈ V, α ∈ (V ∪ T )∗ S · · · 開始記号 (start symbol)，S ∈ V ここで，V ∪ T の要素を文法記号といい，生成規則の右辺 α は 0 個以上の文法記号が並んだ列である． ●文法による構文定義の例文脈自由文法を使えば，コンパイラが扱う言語の構文を厳密に定義できる．字句解析で得られる字句を終端記号とみなし，一つの構文単位に対して文法の変数 (非終端記号) を割り当てて，各構文の生成のしかたを規則として書く．識別子 ID，数 NUM，四則演算，括弧，からなる算術式の集合を，次の文脈自由文法で定める． 1 : E → ( E + E ) 5 : E → ID 2 : E → ( E - E ) 6 : E → NUM 3 : E → ( E * E ) 4 : E → ( E / E ) この例で，非終端記号の集合は V ={ E }，終端記号の集合は T = { (, ), +, -, *, /, ID, NUM }，生成規 則の集合 P は上の 6 個の規則からなる集合，開始記号は E，である．なお，生成規則の左の番号は，解 説のためのもので文法の一部ではない．左辺が同じ生成規則をまとめて，次のように書いてもよい． E → ( E + E ) | ( E - E ) | ( E * E ) | ( E / E ) | ID | NUM ●文法による導出文法に沿った正しい終端記号 (字句) 列は，開始記号から始めて生成規則を繰り返し使って導出できる．上記の文法による導出の例を示す． E ⇒ ( E + E ) ⇒ ( ( E * E ) + E ) ⇒ ( ( NUM * E ) + E ) ⇒ ( ( NUM * ID ) + E ) ⇒ ( ( NUM * ID ) + NUM ) 生成規則を使って，左辺に一致する部分を，対応する右辺に書き換える．これを⇒ で示す．この書き換 えの繰り返しを導出といい，⇒∗で表す．上の導出例で使った規則の番号は，順に 1, 3, 6, 5, 6 である． ●文法が生成する言語文法が生成する言語とは，開始記号からの導出で得られる終端記号列すべての集合 { w ∈ T∗_{| S ⇒}∗ _}

(10)

Cに似た小さな言語の構文を，以下の文脈自由文法で定義する．プログラム → 変数宣言関数定義列変数宣言 → var識別子系列; | ε 関数定義 → fun型ID (識別子列) {変数宣言文列} 型 → void | int 文 → ID (式列) ; | ID =式; | if (式)文else文 | if (式)文 | while (式)文 | {文列} | return式; | return ; 式 → 比較式等値演算列等値演算列 → 等値演算子比較式等値演算列 | ε 比較式 → 加減式比較式列比較演算列 → 比較演算子加減式比較演算列 | ε 加減式 → 乗除式加減演算列加減演算列 → 加減演算子乗除式加減演算列 | ε 乗除式 → 符号式乗除式列乗除演算列 → 乗除演算子符号式乗除演算列 | ε 符号式 → 加減演算子素式 | 素式素式 → NUM | (式) | ID (式列) | ID 等値演算子 → == | != 比較演算子 → > | < | >= | <= 加減演算子 → + | -乗除演算子 → * | / | % 関数定義列 → 関数定義関数定義列 | ε 識別子列 → 識別子系列 | ε 識別子系列 → ID ,識別子系列 | ID 文列 → 文文列 | ε 式列 → 式系列 | ε 式系列 → 式,式系列 | 式 ●参考文献 • 『オートマトン言語理論計算論 I』，第 2 版， J.ホップクロフト，R. モトワニ，J. ウルマン，サイエンス社，2003，第 5 章文脈自由文法と言語．

(11)

文脈自由文法による導出と解析木

文脈自由文法に従って記号列を導出すると，導出に対応する解析木が定まる． ●算術式の導出と解析木文法 1 : E → ( E + E ) 5 : E → ID 2 : E → ( E - E ) 6 : E → NUM 3 : E → ( E * E ) 4 : E → ( E / E ) 最左導出 E ⇒ ( E / E ) 4 ⇒ ( ( E + E ) / E ) 1 ⇒ ( ( ID + E ) / E ) 5 ⇒ ( ( ID + ID ) / E ) 5 ⇒ ( ( ID + ID ) / NUM ) 6 最右導出 E ⇒ ( E / E ) 4 ⇒ ( E / NUM ) 6 ⇒ ( ( E + E ) / NUM ) 1 ⇒ ( ( E + ID ) / NUM ) 5 ⇒ ( ( ID + ID ) / NUM ) 5 解析木 _E eeeeeeeeeeeeeeee e kkkkkkkk k H H H H H H S S S S S S S S S E ppppppp ???? ? N N N N N N N E E E ( ( ID + ID ) / NUM ) ●算術式の曖昧な文法文法 1 : E → E + E 6 : E → ID 2 : E → E - E 7 : E → NUM 3 : E → E * E 4 : E → E / E 5 : E → ( E ) 解析木 _E eeeeeeeeeee MMMM E hhhhhhhhVVVVVVVV E E qqqq MMMM E E ( ID + ID ) /NUM E mmmmmmmm m C C C C C C E {{{{{{ CCCC C C E E E ID + ID / NUM E {{{{{{ QQQQQQ Q Q Q E E {{{{{{ CCCC C C E E ID + ID / NUM

(12)

最左導出と解析木

文法を使って開始記号から字句列を導出できるとき，最左導出と解析木 (と適用した規則の列) が，それぞれ 1 対 1 に対応する．

●文法 (論理式)

1 : exp → exp && exp 論理積

2 : exp → ! exp 否定 3 : exp → VAR 変数 4 : exp → CON 定数 ●適用規則列最左展開 _'& 2 1 3 4 _%$ 下向き最左展開否定論理積変数定数 '& // 展開部抽出先行順走査 %$ oo ●最左導出 exp_ y ⇒ z}| {! exp_ y

⇒ ! z}|exp_ && exp{

y

⇒ ! z}|{VAR && exp_ y

⇒ ! VAR && z }| {CON

●解析木

exp

ssssss sss K K K K K K K K K

!

exp

ssssss sss K K K K K K K K K

exp

_&&

exp

VAR

CON

●解析木の下向き構築 (最左展開) 2 1 3 4 否定論理積変数定数 exp → exp mmmmmQQQQQ ! exp → exp mmmmmQQQQQ ! exp mmmmmQQQQQ

exp _&& exp

→ exp

mmmmmQQQQQ

! exp

mmmmmQQQQQ

exp _&& exp

VAR

→ exp

mmmmmQQQQQ

! exp

mmmmmQQQQQ

exp _&& exp

(13)

最右導出と解析木

文法を使って開始記号から字句列を導出できるとき，最右導出と解析木 (と適用した規則の列) が，それぞれ 1 対 1 に対応する．

●文法 (論理式)

1 : exp → exp && exp 論理積

2 : exp → ! exp 否定 3 : exp → VAR 変数 4 : exp → CON 定数 ●適用規則列最右展開 _'& 1 4 2 3 3 2 4 1 _%$ 上向き構築積定否変 oo // 変否定積逆順 '& // 展開部抽出後行順走査 %$ oo ●最右導出 exp_ y

⇒ z}|exp && exp_{

y     y 生成 ⇒ exp && z }| { CON  y

⇒ z}| {! exp_ && CON y x     還元

⇒ ! z}|{VAR && CON

●解析木

exp

qqqqqq qqqq M M M M M M M M M M

exp

< < < < < < <

&&

exp

!

exp

CON

VAR

●解析木の上向き構築 3 2 4 1 変数否定定数論理積 (空) → exp VAR → exp 66 66 6 ! exp VAR → exp 66 66 6 exp ! exp CON VAR → exp uuuuuu u I I I I I I I exp 66 66 6 && exp ! exp CON VAR

(14)

解析木の先行順走査

木の先行順走査では，深さ優先順で節を走査し，各節を初めて訪れた時 (行きがけ) に処理を実行する．下向き構文解析では，解析木の先行順走査に沿って処理が進む． ●先行順走査の例

exp

tttttt tttt J J J J J J J J J J

!

exp

_&&

exp

VAR

CON

木の項表現 exp ( !, exp (

exp(VAR), &&, exp( CON )

) ) ●再帰アルゴリズム

def traverse( T )

visit( T

の根 )

n = T

の子の数

for i = 1 to n

traverse( T

の i 番目の子 )

●実行例

traverse( exp( !, exp( exp( VAR ), &&, exp( CON ) ) ) )

visit( exp ) 1 exp

traverse( ! )

visit( ! ) 2 !

traverse( exp( exp( VAR ), &&, exp( CON ) ) )

traverse( exp( VAR ) )

traverse( VAR )

visit( VAR ) 5 VAR

traverse( && )

visit( && ) 6 && traverse( exp( CON ) )

traverse( CON )

(15)

解析木の後行順走査

木の後順走査では，深さ優先順で節を走査し，各節を最後に訪れた時 (帰りがけ) に処理を実行する．上向き構文解析では，解析木の後行順走査に沿って処理が進む． ●後行順走査の例

exp

!

exp

_&&

exp

VAR

CON

木の項表現 exp ( !, exp (

exp(VAR), &&, exp( CON )

) ) ●再帰アルゴリズム

def traverse( T )

n = T

の子の数

for i = 1 to n

traverse( T

の i 番目の子 )

visit( T

の根 )

●実行例

traverse( exp( !, exp( exp( VAR ), &&, exp( CON ) ) ) ) traverse( ! )

visit( ! ) 1 ! traverse( exp( exp( VAR ), &&, exp( CON ) ) )

traverse( exp( VAR ) ) traverse( VAR )

visit( VAR ) 2 VAR visit( exp ) 3 exp

traverse( && )

visit( && ) 4 && traverse( exp( CON ) )

traverse( CON )

visit( CON ) 5 CON visit( exp ) 6 exp

() / (front end) (back end) (phase) (pass) 1 2

コンパイラの構成

コンパイラの解析部

(

フロントエンド

)

コンパイラの合成部

(

バックエンド

)

正規表現

有限オートマトン

正規表現からオートマトンへの変換

lex

による字句解析

文脈自由文法

文脈自由文法による導出と解析木

最左導出と解析木

最右導出と解析木

解析木の先行順走査

解析木の後行順走査

山田 俊行

http://www.cs.info.mie-u.ac.jp/~toshi/lectures/compiler/

2018

年

4

月

コンパイラの構成

ソースコード

文字列

字句解析

字句列

構文解析

解析木/構文木

記号表

意味解析・中間コード生成

中間コード

最適化・目的コード生成

命令列

目的コード

コンパイラの解析部 (フロントエンド)

prog

var

seq

seq

fun

◦

left

seq

int main

◦

◦ seq

right

◦

=

seq

left

0

=

seq

right

10

ret

◦

/

+

2

left

right

コンパイラの合成部 (バックエンド)

=

val

/

*

m

+

+

n

1

n

山田俊行

_{ソースコード}

_{目的コード}

_A

_C

_&&