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

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

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

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

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

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

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

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

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

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

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

ａｃｂｄの解析手順例 最も左にある非終端記号から解析を始めている。 文法の展開に失敗したら後戻りがある。 最左導出という。 解析手順 入力記号 文法の適用 解析結果 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

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

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

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

を に置き換えて解析。 の形の場合、 という形に文法を変形する。 バックトラックがなくなるわけではない。 解析手順 入力記号 文法の適用 　　　　を　　　　に置き換えて解析。 解析手順 入力記号 文法の適用 解析結果 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 の形の場合、 という形に文法を変形する。 バックトラックがなくなるわけではない。