コンパイラ 2011年10月20日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2011/index.html.

Presentation on theme: "コンパイラ 2011年10月20日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2011/index.html."— Presentation transcript:

1 コンパイラ 2011年10月20日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp)

2 構文解析 字句の列を入力とする。 字句の列として表されたプログラムが、文法のどの部分 に対応するかを解析する。 今回の内容
字句の列は字句解析器から出力される。 字句の列として表されたプログラムが、文法のどの部分 に対応するかを解析する。 今回の内容 構文解析の概論 下向き構文解析法の説明 下向き構文解析法の問題点と解決法

3 構文解析の役割 プログラミング言語の文法はＢＮＦなどで記述される。 それに基づいてソースプログラムの字句が解析される。
字句の列から文法で許される並びであるかどうか調べる。 許されなれない並びであればエラーとする。 許される並びであれば、解析木を生成し構文木を出力する。 さらに変数や関数の名前は名前表に出力する。 ソース プログラム 構文解析 字句解析 字句出力 字句要求 構文木 名前表

4 構文規則（生成規則） この例では、乗算は加算よりも 先に行うことを示している。 非終端記号 終端記号 → 演算順序を文法で規定している。
この例では、乗算は加算よりも 先に行うことを示している。 演算順序を文法で規定している。 非終端記号 式・項・因子・名前 終端記号 ａ・ｂ・ｃ → 左辺の非終端記号を右辺に 書き換え可能であることを示す。 【式の構文規則】 式 →　項｜式＋項 項 →　因子｜項＊因子 因子 →　名前｜（式） 【文法Ｇ１】 式 →　式＋項 式 →　項 項 →　項＊因子 項 →　因子 因子 →　（式） 因子 →　名前 名前 →　ａ｜ｂ｜ｃ

5 構文図式 ＢＮＦと記述力は変わらない。 直感的でわかりやすい。 [プログラム] 関数定義 変数宣言 ; 返戻型 ブロック 識別子 ( ) ,
[関数定義] [変数宣言] 要素型 識別子 文 { } [ブロック]

6 [文] 式 return 条件式 ブロック 文 識別子 変数宣言 ; ( = if while ) 関数呼出し 識別子 式 ( ) , [関数呼出し] [式] 項 加減演算子 [項] 因数 乗除演算子

7 [条件式] 式 == != > < >= <= [加減演算子] [乗除演算子] + - ＊ / 要素型 void [数字]と[英字]は非終端記号なので、 本来はそれらも終端記号に至るまでの 定義が必要。しかし、省略されている。 前回のＢＮＦの例でも省略されている。 [返戻型] 数字 英字 [識別子] [整数] 数字 int [要素型]

8 解析木では葉に終端記号で 末端以外が非終端記号
式ａ＊(ｂ＋ｃ)の解析木と構文木 項 因子 式 名前 ａ ｂ ｃ （ ） ＊ ＋ 文法解析ではこれらの木を生成する。 解析木では葉に終端記号で 末端以外が非終端記号 ａ ＊ ｂ ＋ ｃ 構文木 解析木

9 構文解析法 一般にはふた通りに分類可能。 上向き構文解析。 下向き構文解析。 解析木を下から生成していく。
右辺と一致する入力列を左辺に置き換える。 下向き構文解析。 解析木を上から生成していく。 生成可能な解析木を仮定し、一致するかどうかで解析をすすめる。 【文法Ｇ１】 式 →　式＋項 式 →　項 項 →　項＊因子 項 →　因子 因子 →　（式） 因子 →　名前 名前 →　ａ｜ｂ｜ｃ

10 上向き構文解析法 項 因子 式 名前 ａ ｂ ｃ ＋ ＊ 解析木の下のほう、 終端記号の非終端記号の 置き換えから始まる解析法。
右辺が一致し左辺に置き換えることを 還元という。 記号列： ａ＋ｂ＊ｃ ７を適用： 名前＋名前＊名前 ６を適用： 因子＋因子＊因子 ３，４を適用： 因子＋項＊因子 ⇒ 項＋項＊因子 項＋項 １，２を適用： 式＋項 式 上向き構文解析法については大学院で詳しくやります。 ここでは、概論だけ。 教科書では省略されているがシフトという操作もあるし、シフト・還元の間での競合もある。

11 下向き構文解析法 解析木を根のほうから生成する。 木の形を仮定して葉に至るかどうかを調べる。
葉に至るまで木が完成しなければ、読み込んだ字句は戻して 別の形を探っていく。別の形が尽きたらエラーになる。 仮定⇔後戻り、を繰り返す。 void S(){ aを読む; A(); /* Aを読む */ bを読む; dを読む; } void A(){ cを読む; または /* 解析が失敗して後戻りが発生したら */ void A(){ aを読む; B(); /* Bを読む */ cを読む; } 　　　直接導出の例

12 ａｃｂｄの解析手順例 最も左にある非終端記号から解析を始めている。 文法の展開に失敗したら後戻りがある。 最左導出という。 解析手順
入力記号 文法の適用 解析結果 a c b d S → a A b d １ a A b d ○ 2 c b d A → c b | c 3 c b 4 d × 5 6 c 7 b d

13 下向き構文解析の問題点 再帰的なプログラムで実現できない文法がある。
左再帰性の問題という。 再帰呼び出しが無限ループする。 左辺の非終端記号に対し、右辺に複数の生成規則 があるときに、どれを仮定すべきか一意に決まらない。 バックトラック問題という。 前のページの３～６のところ。 void 式(){ 式(); +を読む; 項(); }

14 左再帰性の除去 問題のある文法。 これを次のように書き換える。 一般には次の形をとるときが問題で、 このように書き換える。

15 バックトラック バックトラック法で解は求まるが、やはり速いほうがいい。 そこで、共通部分がある場合にくくりだす。 次のように書き換える。
void A(){ cを読む; bを読む; 　　　または /* 解析が失敗してバックトラックが発生したら */ 何も読まない; }

16 を に置き換えて解析。 の形の場合、 という形に文法を変形する。 バックトラックがなくなるわけではない。 解析手順 入力記号 文法の適用
　　　　を　　　　に置き換えて解析。 解析手順 入力記号 文法の適用 解析結果 a c b d S → a A b d 1 a A b d ○ 2 c b d 　A → c A' 3 c A' 4 b d 　A' → b |ε 5 b 6 d × 7 A' → b |ε 8 の形の場合、 という形に文法を変形する。 バックトラックがなくなるわけではない。