コンパイラとプログラミング⾔語
第7週 構⽂解析の概要/上向き構⽂解析
2013年5⽉29⽇
⾦岡 晃
授業計画
第1週 (4/10)
コンパイラの概要 第2週
(4/24)
コンパイラの構成 第3週
(5/1)
プログラミング⾔語の形式的な 記述
第4週 (5/8)
字句解析の概要と⾮決定性有限 オートマトン
第5週 (5/15)
決定性有限オートマトン・字句 解析プログラム
第6週 (5/22)
中間試験 第7週
(5/29)
構⽂解析の概要/上向き構⽂解析
第8週 (6/5)
下向き構⽂解析/構⽂解析プ ログラム
第9週 (6/12)
中間表現と意味解析 第10週
(6/19)
Java仮想マシンとその機械語 第11週
(6/26)
条件分岐⽂と繰り返し⽂の コード⽣成
第12週 (7/3)
関数呼び出しのコード⽣成 第13週
(7/10)
休講 (7/24 or
7/31)
期末試験
中間試験 解説
コンパイラとプログラミング⾔語
問1
（１）
プログラムソース
プログラムソース
・・・
（２）
（２）
プログラム⽬的
プログラム⽬的
（３）
ライブラリ実⾏時
プログラム実⾏
実⾏
（４）
下に⽰す⾔語処理系のなかで、コンパイラを⽰すものは（１）〜（４）
のどれか答えよ
⾔語処理系
• コンパイラ、リンケージエディタ、エディタ、デバッガ、実⾏時ラ イブラリなど、プログラムの開発・翻訳（コンパイル）・実⾏に関 係するプログラム群の総称
• 処理系とも呼ぶ
エディタ
プログラムソース
プログラムソース
・・・
コンパイラ
コンパイラ
プログラム⽬的
プログラム⽬的
リンケージ エディタ ライブラリ実⾏時
プログラム実⾏
実⾏
デバッガ
問1：（２）
問 2
コンパイラの内部は5つのフェーズから成り立つ。
その5つのフェーズをすべて書き出せ。
プログラムソース ⽬的
プログラム
コンパイラ
字句解析 構⽂
解析 意味
解析 最適化 コード
⽣成
中間情報（中間語、名前表）
フェーズ
問 3
＜問 3‐1 ＞以下の中置記法で記述された式を後置記法に変換せよ A+B*C‐D
＜問 3‐2 ＞以下の中置記法で記述された式を後置記法に変換せよ Y=(A+B)*(C‐D/E)
＜問 3‐3 ＞以下の後置記法で記述された式を中置記法に変換せよ
EF‐G/CD‐AB+/+
中置記法 → 後置記法
• 優先順位の⾼い演算から変換していく – 同じ優先順位だったら、左から
A+B*C-D A+BC*-D A+BC*-D ABC*+-D ABC*+-D ABC*+D-
Y=(A+B)*(C-D/E) Y=AB+*(C-D/E) Y=AB+*(C-D/E) Y=AB+*(C-DE/) Y=AB+*(C-DE/)
Y=AB+*CDE/- Y=AB+*CDE/- Y=AB+CDE/-*
Y=AB+CDE/-*
YAB+CDE/-*=
優先順位
()
*, / +, ‐
=
問 3‐1 ： ABC*+D‐ 問 3‐2 ： YAB+CDE/‐*=
後置記法 → 中置記法
• やりかたはいろいろ
– 優先順位が⾼い演算から変換 – アタマから変換
• 変換のポイント
– 後置記法は演算される 2 つが先に来て、そして演算⼦が後に来る
演算⼦を⾒つけて、その直前の2⽂字を変換
EF-G/CD-AB+/+
(E-F)G/CD-AB+/+
((E-F)/G)CD-AB+/+
((E-F)/G)CD-AB+/+
((E-F)/G)(C-D) AB+/+
((E-F)/G)(C-D)AB+/+
((E-F)/G)(C-D)(A+B)/+
((E-F)/G)(C-D)(A+B)/+
((E-F)/G)((C-D)/(A+B))+
((E-F)/G)((C-D)/(A+B))+
((E-F)/G)+((C-D)/(A+B))
外しても演算の順番に関係ない()を 外す
問 3‐3 ： (E‐F)/G+(C‐D)/(A+B)
問 4
次の規則から⽣成することができる式はどれか答えよ
〔規則〕 ＜式＞ :: ＝＜変数＞｜ ( ＜式＞ + ＜式＞ ) ｜＜式＞ * ＜式＞
＜変数＞ :: ＝ A ｜ B ｜ C ｜ D
（ア） A+(B+C)*D （イ） (A+B)+(C+D)
（ウ） (A+B)*(C+D) （エ） (A*B)+(C*D)
1 つずつチェックをしていく
（ア） A+(B+C)*D
これが式かどうかを確認する
＜式＞ ::＝＜変数＞｜(＜式＞+＜式＞)｜＜式＞*＜式＞
＜変数＞ ::＝A｜B｜C｜D
どれにも当てはまらないので×
（イ） (A+B)+(C+D)
これが式かどうかを確認する
＜式＞ ::＝＜変数＞｜(＜式＞+＜式＞)｜＜式＞*＜式＞
＜変数＞ ::＝A｜B｜C｜D
どれにも当てはまらないので×
1 つずつチェックをしていく
（ウ） (A+B)*(C+D)
これが式かどうかを確認する
＜式＞ ::＝＜変数＞｜(＜式＞+＜式＞)｜＜式＞*＜式＞
＜変数＞ ::＝A｜B｜C｜D
この形式の様⼦。
あとは（A＋B)と（C+B）が 式になっているかの確認が必要
（A＋B) これが式かどうかを確認する
＜式＞ ::＝＜変数＞｜(＜式＞+＜式＞)｜＜式＞*＜式＞
この形式の様⼦。あとはAとBが 式になっているかの確認が必要
1 つずつチェックをしていく
A これが式かどうかを確認する
＜式＞ ::＝＜変数＞｜(＜式＞+＜式＞)｜＜式＞*＜式＞
＜変数＞ ::＝A｜B｜C｜D
式になっている
※B、C、Dも同様
（A＋B)は式である
※（C+D）も同様
（A＋B)*(C+D)は式である
※（C+D）も同様
1 つずつチェックをしていく
（エ） (A*B)+(C*D)
これが式かどうかを確認する
＜式＞ ::＝＜変数＞｜(＜式＞+＜式＞)｜＜式＞*＜式＞
＜変数＞ ::＝A｜B｜C｜D
どれにも当てはまらないので×
問 4 ：（ウ）
問 5
＜問 5‐1 ＞ 以下の BNF で表された構⽂規則を構⽂図式で表現せよ
<while ⽂ >::=while(< 条件式 >)< ⽂ >
while( 条件式 ) ⽂
：終端記号
：構成要素 問5－1：
問 5
＜問 5‐2 ＞ 以下の構⽂図式で表現された構⽂規則を BNF で表現せよ
因数
乗除演算⼦
因数
ループしているが、
ループを通過しても良い 0個以上ならべたもの、を示す
{}
を使う問 5 － 2 ： < 因数 > { < 乗除演算⼦ >< 因数 > }
問 6
＜問 6‐1 ＞ 正規表現で (ab)*(c|d)e と表されたものと⼀致する⽂字列を
選べ （ア） abaabcde （イ） abababbe
（ウ） de （エ） ededab
(ab)*(c|d)e
まず、ab を1セットとして、それを0個以上繰り返す。その後、c か d が1回出現する。
最後にe が出現する。
（ア） abaabcde 表現に沿っていないので×
（イ） abababbe 表現に沿っていないので×
（ウ） de 表現に沿っているので ○
（ウ） ededab 表現に沿っていないので×
問 6 － 1 ：（ウ）
問 6
＜問 6‐2 ＞ 下記の⾮決定性有限オートマトンを正規表現で表せ
1 4
F
C B 2 0 E
3 A
D
G
一番シンプルなのは、すべての道筋を洗い出して、| でつなぐ。
ABD*F ACED*F
ACG
(ABD*F)|(ACED*F)|(ACG)第 7 週
構⽂解析の概要 / 上向き構⽂解析
コンパイラとプログラミング⾔語
コンパイラの論理的な構成
プログラムソース ⽬的
プログラム
コンパイラ
字句解析 構⽂
解析 意味
解析 最適化 コード
⽣成
中間情報（中間語、名前表）
フェーズ
字句解析の概要
• ソースプログラムからトークンを取り出して構⽂解析に渡す – ソースプログラム：⽂字列（数字含む）の集まり
– トークン：プログラム上の構成要素
• トークンの取り出しは、⽂法に従って⾏う
import java.io.*;
class Sample throws IOException{
public static void main(String[] args){
BufferedReader br = ….
}
} • ⼈間から⾒るとプログラム
• コンピュータから⾒ると⽂字列
import java.io.*;class Sample throws IOException{public static void main(String[] args){BufferedReader br = …. }}
import java
. io * ;
class Sample
throws IOException
public static ・・・
トークン
字句解析の流れ
プログラムソース
字句解析
構⽂解析
⽂字（列）
読み取り 字句
読み取り トークントークン
• ⼈間から⾒るとプログラム
• コンピュータから⾒ると⽂字列 ただの⽂字列
扱い 意味を持つ
要素に分割
分割されたトークンの集まりが
⽂法として間違っていないかチェック
（ここでBNFを使って定義された
⽂法と照らし合わせる）
構⽂解析
• 字句解析が出⼒したトークンを読み込みながら、そのトークンの列 がプログラム⾔語の⽂法で許されているパターンと合うかを解析す る
プログラムソース 字句解析 トークントークン 構⽂解析
構⽂⽊
構⽂⽊
名前表
• 許されているパターンであれば、トークンの列は構⽂規則 に従って構成され、字句を葉とする構⽂⽊が⽣成される。
• 構⽂解析の結果、ソースプログラムの構造は構⽂⽊として 出⼒され、名前や数字などの情報は名前表に出⼒される。
構⽂解析の例
構⽂規則 <式> ::= <項> | <式>+<項>
<項> ::= <因⼦>| <項>＊<因⼦>
<因⼦> ::= <名前>|(<式>)
<名前> ::= a|b|c
a ＊ ( b + c ) ソースコード
（字句解析の
⼊⼒） a＊(b+c)
（字句解析のトークン 出⼒）
構⽂解析の例
a ＊ ( b + c )
（字句解析の出⼒）トークン
（構⽂解析の出⼒）構⽂⽊
名前
a ＊ ( b + c )
名前 因⼦
項 式
名前 因⼦
項 式
因⼦
項
因⼦
項 式
構⽂解析法
上向き構⽂解析法
（bottom-up parser)
下向き構⽂解析法
（top-down parser)
⼊⼒した記号列が構⽂規則の 右辺と⼀致した場合に左辺の 記号に置き換えていく
記号列として次に何が来るの かを仮定しながら構⽂解析を
進めていく a ＊ ( b + c )
名前 名前
因⼦
項 式
名前 因⼦
項 式
因⼦
項
因⼦
項
上向き 式
解析法構⽂
下向き構⽂
解析法
上向き構⽂解析法の例
a ＊ ( b + c )
名前 名前
因⼦
項 式
名前 因⼦
項 式
因⼦
項
因⼦
項 式
構⽂規則
<式> ::= <項> | <式>+<項>
<項> ::= <因⼦>| <項>＊<因⼦>
<因⼦> ::= <名前>|(<式>)
<名前> ::= a|b|c
<名前> ::= a|b|c
<因子> ::= <名前>|(式)
<項> ::= <因子>| <項>＊<因子>
<式> ::= <項> | <式>+<項>
<式> ::= <項> | <式>+<項>
<因子> ::= <名前>|(式)
<項> ::= <因子>| <項>＊<因子>
<式> ::= <項> | <式>+<項>
