アルゴリズムとデータ構造1

コンパイラ
2012年10月18日
酒居敬一＠Ａ４６８([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html
1
構文解析
字句の列を入力とする。


字句の列は字句解析器から出力される。

字句の列として表されたプログラムが、文法のどの部分
に対応するかを解析する。

今回の内容



2
構文解析の概論
下向き構文解析法の説明
下向き構文解析法の問題点と解決法
構文解析の役割
プログラミング言語の文法はＢＮＦなどで記述される。
それに基づいてソースプログラムの字句が解析される。
字句の列から文法で許される並びであるかどうか調べる。





許されなれない並びであればエラーとする。
許される並びであれば、解析木を生成し構文木を出力する。

さらに変数や関数の名前は名前表に出力する。
字句要求
ソース
プログラム
字句解析
字句出力
3
構文解析
構文木
名前表
構文規則（生成規則）
この例では、乗算は加算よりも
先に行うことを示している。


演算順序を文法で規定している。
【式の構文規則】
1.式
→ 項｜式＋項
2.項
→ 因子｜項＊因子
3.因子 → 名前｜（式）
非終端記号


式・項・因子・名前
終端記号


ａ・ｂ・ｃ
→


4
左辺の非終端記号を右辺に
書き換え可能であることを示す。
【文法Ｇ１】
1.式
→
2.式
→
3.項
→
4.項
→
5.因子 →
6.因子 →
7.名前 →
式＋項
項
項＊因子
因子
（式）
名前
ａ｜ｂ｜ｃ
構文図式
ＢＮＦと記述力は変わらない。
直感的でわかりやすい。


[プログラム]
;
変数宣言
関数定義
[関数定義]
[変数宣言]
[ブロック]
5
返戻型
識別子
(
変数宣言
,
要素型
{
識別子
文
}
)
ブロック
[文]
変数宣言
=
識別子
;
式
;
関数呼出し
if
while
(
条件式
)
文
(
条件式
)
文
ブロック
return
[関数呼出し]
[式]
[項]
識別子
(
式
)
,
項
項
加減演算子
因数
因数
6
;
式
乗除演算子
[条件式]
式
式
==
[加減演算子]
!=
>
>=
<
<=
[乗除演算子]
+
-
[返戻型]
＊
/
[数字]と[英字]は非終端記号なので、
本来はそれらも終端記号に至るまでの
定義が必要。しかし、省略されている。
前回のＢＮＦの例でも省略されている。
要素型
void
英字
[識別子]
英字
数字
[整数]
7
数字
[要素型]
int
式ａ＊(ｂ＋ｃ)の解析木と構文木
式
項
項
文法解析ではこれらの木を生成する。
因子
解析木では葉に終端記号で
末端以外が非終端記号
式
因子
名前
式
項
項
因子
因子
＊
名前
ａ
名前
ａ
＊
（
ｂ
解析木
8
＋
ｃ
）
＋
ｂ
構文木
ｃ
構文解析法
一般にはふた通りに分類可能。


上向き構文解析。



解析木を下から生成していく。
右辺と一致する入力列を左辺に置き換える。
下向き構文解析。


解析木を上から生成していく。
生成可能な解析木を仮定し、一致するかどうかで解析をすすめる。
【文法Ｇ１】
1.式
→
2.式
→
3.項
→
4.項
→
5.因子 →
6.因子 →
7.名前 →
9
式＋項
項
項＊因子
因子
（式）
名前
ａ｜ｂ｜ｃ
上向き構文解析法
式
式
解析木の下のほう、
終端記号の非終端記号の
置き換えから始まる解析法。
右辺が一致し左辺に置き換えることを
還元という。
項
項
因子
因子
因子
因子
名前
名前
名前
ａ
10
項
＋
記号列：
ａ＋ｂ＊ｃ
７を適用：
名前＋名前＊名前
６を適用：
因子＋因子＊因子
３，４を適用：
因子＋項＊因子
⇒
項＋項＊因子
１，２を適用：
式＋項
⇒
式
ｂ
⇒
＊
ｃ
項＋項
下向き構文解析法

解析木を根のほうから生成する。


木の形を仮定して葉に至るかどうかを調べる。
葉に至るまで木が完成しなければ、読み込んだ字句は戻して
別の形を探っていく。別の形が尽きたらエラーになる。

仮定⇔後戻り、を繰り返す。
void S(){
aを読む;
A();
bを読む;
dを読む;
void A(){
aを読む;
B();
cを読む;
}
直接導出の例
/* Bを読む */
/* Aを読む */
S  aAbd
A  cb | c
}
void A(){
cを読む;
bを読む;
または
/* 解析が失敗して後戻りが発生したら */
cを読む;
}
11
ａｃｂｄの解析手順例
解析手順
入力記号
文法の適用
解析結果
a c b d S→a A b d
１
c b d
A→c b|c
3
c b d
c b
d a A b d
○
×
5
c b d
A→c b|c
6
c b d
c
7
b d a A b d
○
○
最も左にある非終端記号から解析を始めている。


○
2
4

a c b d a A b d
最左導出という。
文法の展開に失敗したら後戻りがある。
12
下向き構文解析の問題点

再帰的なプログラムで実現できない文法がある。

左再帰性の問題という。

再帰呼び出しが無限ループする。
void 式(){
式();
+を読む;
項();
}

左辺の非終端記号に対し、右辺に複数の生成規則
があるときに、どれを仮定すべきか一意に決まらない。

バックトラック問題という。

13
前のページの３～６のところ。
左再帰性の除去

問題のある文法。
A  A | 

これを次のように書き換える。
A  A 
A  A | 

一般には次の形をとるときが問題で、
A  A1 | A 2 |  | A m | 1 |  2 |  |  n
このように書き換える。
A  1 A  |  2 A  |  |  n A 
A   1 A |  2 A |  |  m A | 
14
バックトラック


バックトラック法で解は求まるが、やはり速いほうがいい。
そこで、共通部分がある場合にくくりだす。
A  cb | c
次のように書き換える。

A  cA 
A  b | 
void A(){
cを読む;
bを読む;
または
/* 解析が失敗してバックトラックが発生したら */
何も読まない;
}
15
S  aAbd
A  cb | c
を
解析手順
S  aAbd
A  cA 
A  b | 
に置き換えて解析。
入力記号
文法の適用
解析結果
a c b d S→a A b d
1
16
a c b d a A b d
○
2
c b d
A → c A'
3
c b d
4
b d
5
b d
6
d
a A b d
7
b d
A' → b |ε
8
b d a A b d
c A'
○
A' → b |ε
b
○
×
○
A  1 |  2 |  |  m |  1 |  2 |  |  n
の形の場合、
A  A |  1 |  2 |  |  n
A   1 |  2 |  |  m
という形に文法を変形する。
バックトラックがなくなるわけではない。

Download Report