コンパイラ資料 ３章　構文解析

構文解析 トークン列から抽象構文木（AST）を作る AST：トークンの意味的な結合の強さを表す木 トークン トークン 要求 中間コード 字句解析 ルーチン 構文解析 ルーチン 意味解析 その他 トークン 抽象構文木 記号表 トークン列から抽象構文木（AST）を作る AST：トークンの意味的な結合の強さを表す木

ASTの例 x+ (y-3) * z- 45　　　　ソース 〈id, x〉〈plus〉〈lparen〉〈id, y〉〈minus〉〈num, 3〉〈rparen〉〈prod〉〈id, z〉〈minus〉〈num, 45〉 トークン列 　　　　　　　　　　　　　　　AST - + 45 x * - z y 3

構文解析へのヒント： 字句解析との比較 字句解析 構文解析 仕様記述 正規表現 文脈自由文法 認識方法 有限オートマトン プッシュダウンオートマトン 出力 トークン列 抽象構文木

文脈自由文法 構文は普通、文脈自由文法(context free grammar, CFG)で記述される。以下単に文法という。 文法Gは4つ組< V,T,P,S>で定義されるここで、 Vは変数（あるいは非終端記号）の集合： 変数は記号列の集合をあらわす Tは終端記号の集合 構文解析ルーチンではトークンの集合 Pは生成規則の集合 Sは開始記号

文法の例 数式の文法GExp Exp → Exp + Exp Exp－Exp Exp * Exp Exp / Exp ( Exp ) Atom id num

記号 役割 小文字英字(前半) a, b, c 演算子記号　+, - 括弧、コンマ　( , 数字　0, 1, 2 太英字列　id, if 終端記号 大文字英字(前半)　A, B, C 大文字英字　S (開始記号専用) イタリック体文字列　expr, stmt 非終端記号 大文字英字(後半)　X, Y, Z 文法記号 (終端記号＋非終端記号) 小文字英字列(後半) u,v, …, z 終端記号列 小文字ギリシャ文字列 a, b, g 文法記号列

略記法 例 略記法による数式の文法 GExp : E → E + E | E - E | E * E | E / E |( E ) | A A → a1, A → a2, … , A → anは A → a1 | a2 | … | an のように書いてよい。 例　略記法による数式の文法 GExp : E → E + E | E - E | E * E | E / E |( E ) | A A → num | id

導出 GExp: E → E+E | E-E | E*E | E/E | (E) | A 生成規則は、その左辺の非終端記号を右辺の列に書き換える書き換えの規則をあらわす。 開始記号から始めて、非終端記号の書き換えを次々に行って列を生成することで言語を定義する。 GExp: E → E+E | E-E | E*E | E/E | (E) | A A → num | id 5番目の規則をつかうと、 E は(E) に書き換えられる。これを　　E ⇒ (E)と書く。 引き続いて1,6,8,6,8番目の規則をつかうと、全部で E ⇒(E)⇒(E+E) ⇒(A+E) ⇒(id+E) ⇒(id+A)⇒(id +id) この書き換えの系列をEからの(id + id)の導出という。 1 2 3 4 5 6 7 8

導出の形式的定義 A → g を生成規則とすると、aAb ⇒ agb a1 ⇒ a2 ⇒ … ⇒ anのときa1はanを導出するといい、 ⇒* は0ステップ以上の導出 ⇒+ は1ステップ以上の導出 Sを開始記号とすると、文法Gによって生成される言語L(G)は L(G)={w 終端記号| S ⇒* w} 　　　 L(G)のことを、文法Gが表す言語ともいう S ⇒* aなる記号列aを文形式という。aは非終端記号を含んでもよい。

最左(右)導出 導出の各書き換えステップで一番左（右）の非終端記号の書き換えのみをおこなう導出を最左（右）導出という。 最左導出でa1からのa2の導出ができるとき a1 ⇒*lm a2 などとかく。 S ⇒* lm aなるaを左文形式という。aは非終端記号を含んでもよい。 問い：　前の文法の例で、Eからid -(id + id)の最左導出を求めよ。

解析木 導出を、どの非終端記号を書き換えるかの順序を捨象して木であらわしたものを解析木(parse tree)という。 id id 解析木の各節点は非終端記号、葉は終端記号、根は開始記号。 各節点の子の並びはその節の非終端記号の書き換えにもちいた生成規則の右辺。 ( ) E E + E A A id id E⇒(E)⇒(E+E)⇒(A+E)⇒(id+E)⇒(id+A)⇒(id+id) E⇒(E)⇒(E+E)⇒(E+A)⇒(E+id)⇒(A+id)⇒(id+id) …

構文解析における解析木の役割 入力wに対するGによる解析木が存在 → Gによるwの導出の存在 → w ∈ L(G) 正しい文であることの検査 目的の構文木ではないが、構文木に近い構造を取り出す。

課題 literal: トークン列検査器 単純不等式（リテラルと呼ぶ）は次の文法で表される。 GLiteral: Literal → Atom rel Atom Atom → num | id 課題：　入力が単純不等式であることを判定するプログラムliteralを書け。 hint: 文法の形を参考にして関数を作れば、簡潔に書ける。

再帰下降(recursive descent)解析 最左導出を前向きに探索 例：　w=cad S → cAd A → ab | a 問　左再帰文法の例で再帰下降解析を試みよ。 展開 マッチ 後戻り cad ↑ cad ↑ cad ↑ cad ↑ cad ↑ cad ↑ S S S S cにマッチ Sを展開 c A d c A d c A d a b a

予測型構文解析 現在のポインタの指す文字aと展開対象の非終端記号Aにたいして、 A→ a1 | a2 | … | an の右辺のaiのうちどれを選べば将来aとマッチするかが一意に決まる文法(LL(1)とよばれる)による 再帰下降解析を予測型構文解析という。 予測型解析は後戻りが不要。 （今回の実装ではこの方法を用いる。）

予測型構文解析ルーチンの遷移図 A: 字句解析の場合と同様に（ある種の）遷移図を用いて認識を行う。 遷移図の構成 各非終端記号Aについて、 開始状態と終状態を作る。 各生成規則A → X1 X2… Xnに対して初期状態から終状態への経路を作る。 Xn X1 X2 A: 1 2 n-1 n

例：kittyの文 (Statement)の一部 Gifprint Statement → If-Statement | Print-Statement If-Statement → if lparen Literal rparen Statement else Statement Print-Statement → print Atom semi Literal → Atom rel Atom Atom → num | id 問い：　 Gifprint の遷移図を書け

Statement : If-Statement : Print-Statement : Literal : Atom : 1 Print-Statement If-Statement : Statement Statement if lparen Literal rparen else 1 2 3 4 5 6 7 Print-Statement : Literal : Atom :

予測型構文解析の動作 a a A A e e abc… ↑ abc… ↑ s t s t abc… ↑ abc… ↑ …h … ↑ …h … A A s t s t Aのaから予測した 右辺の開始状態 Aの終状態 abc… ↑ abc… ↑ e e s t s t 　　　　　　　　　　　　現在の状態

… 解析動作の例 Statement Statement if lparen Literal rparen else 1 2 3 4 5 6 if (n=0) if (m>0) print m ; else print n ; else print 0; 解析動作の例 Statement Statement if lparen Literal rparen else 1 2 3 4 5 6 7 Atom rel Atom If-Statement 1 2 3 1 num num 2 3 2 3 Print-Statement id id lparen Literal rparen Statement Statement if else 1 2 3 4 5 6 7 … 有限状態ではない！

解析器（前半：解析木まで）の作りかた 各非終端記号Aに対するルールは関数A()で作る. （非終端記号関数） 右辺の各非終端記号B（のルールへ）の遷移は関数B()の呼び出し.（returnで呼び出し元に戻る） Aに対するルールが複数あるときは、先頭トークン（現在のトークン）で場合わけし、該当するものをひとつだけ指定する. 問い：　解析木に相当するものは何か？

課題 ifprint 前掲Gifprintの文か否かを判定するプログラムを書け. ヒント：まず前課題literal （ifprintの一部）を前頁の方法で再実装せよ.

数式の解析 数式の文法 GExp : E → E + E | E - E | E * E | E / E |( E ) | A A → num | id （ただし、+等の記号のトークンは現物で代用した。以降も。） 数式の例（ソース）: 　x + (y -3) * z - 45 対応するGExpの文 （字句解析の出力）：　 id + (id - num) * id - num 　　　　　　　　　　　　　　　　　　（属性は省略）

構文木 - + 45 x * - z y 3 x + (y -3) * z - 45の構文木

文法の書き換え GExp は曖昧であるのでこのままでは解析には使わない。 次の性質をみていく さらに左再帰をもつので再帰下降解析には使えない。 そこで 曖昧性と左再帰を除去して文法G1に書き換える。 ただし、生成する言語はL (GExp)のまま。

曖昧さ 1つの文について2つ以上の解析木が作れる文法は曖昧であるという。 曖昧であることは最左（右）導出が2つ以上あることと同じ。 問　前の文法でid+id*idの解析木を2つ作れ。

x - y - 4の解析木. 葉はトークンの代わりに字句で示す GExpは曖昧である E E E E - E - E A A E E - E - E 4 x A A A A y y x 4 x - y - 4の解析木. 　葉はトークンの代わりに字句で示す

演算子の結合性 （associativity）* 被演算数が左右どちらの演算子と結合するか。 E → E - E の代わりに E → E - A としてみる。 *代数のassociativity（結合律） とは異なる概念 x - y 4 E A

E E A * E - A 4 A y x E → E - A | E * A | A による x - y * 4の解析木. 葉はトークンの代わりに字句で示す E - A 4 A y x 曖昧ではなくなったが、結合順が変

優先順位 （precedence） E E - T T T * A A A 4 x y E → E - A | E * A | A 結合性 優先順位 * / 左 1 + - 2 E → E - A | E * A | A の代わりに E → E - T | T T → T * A | A 順位ごとに非終端記号を用いて、上位のものを組み立てて下位のものを定義する。 E E - T T T * A A A 4 x y

共通左端の括りだし （再帰下降解析のみ） A-生成規則の右辺に共通の接頭語をもつものがあれば括りだす。 再帰下降解析で、トークンを読み込んだとき、どの規則を使うべきか区別できるまで判断を遅らせる。） A → ab1 | ab2 | … | abn | g の左端を括りだすと A → aA’ | g A’ → b1 | b2 | … | bn

左再帰 文法はA⇒+Aa なる導出が存在するとき、 左再帰である、という。特に、 A⇒+Aなる導出が存在するとき、その導出は閉路とよばれる。 例　A → Aa | b は左再帰である。(直接左再帰) この文法はどのような文を生成するか？（a, b はそのままでよい。）また、その文の解析木をつくれ。 左再帰の文法は再帰下降解析が（止まらないため、）使えない 実験：　E → E - id | id を22ページの方法で実装、x - yを入力として実験せよ。

左再帰の除去（再帰下降解析のみ） E → E - T | T これは左再帰なので再帰下降解析では解析不能。 演算子の結合性を解析木に反映することはあきらめ、ひとまず E → T - E | T をつかう。この右辺はTを共通の頭部にもつので予測できない。 そこで T を括（くく）りだして、 E → T (- E | e )　　　　　括弧はメタな記号 と書いて選択を先送りしたいがこういう括弧は文法では書けない。 そこで、括弧のなかをあたらしい非終端記号E’でおきかえ E → T E’ E’ → - E | e と書けばよい。ここで、E’の規則の右辺のEは唯一の規則により TE’にしかならないので E’ → - T E’| e と書いたほうが無駄がない。

左再帰除去の公式 一般に、 A → Aa | b (直接左再帰) の左再帰を除去すると以下のようになる。 A →bA’ A’→ aA’ | e 文法GExpの左再帰をすべて除去せよ。 ただし演算子の優先順位結合性はあきらめる。 （答えは次ページ）

数式の文法 （予測型再帰下降解析用、 優先順位付き 結合性あきらめ版） 数式の文法　 （予測型再帰下降解析用、 優先順位付き　結合性あきらめ版） G1: E → T E’ E’→ + T E’| - T E’| e T → A T’ T’→ * A T’| / A T’| e 　A → ( E ) | num | id

課題 exppp G1による解析木を表示するプログラムexpppを作成せよ。 ヒント: 木を標準出力で表示する方法を工夫せよ。親子関係と子の順序がわかることが条件。 ヒント： depth段のインデント（字下げ） 　　　　　void indentn(int depth) 　 を作る。

左再帰除去後の解析木 E T E’ A T - E’ x A T - E’ y A e 4 E → T E’ E’ → - T E’| e T → A による x - y - 4 の解析木（ G1 による木のT’の枝を省いたもの） T E’ A T - E’ x A T - E’ 左再帰ではなくなった。 が y A e 右結合っぽくなってしまった！ 4

E E T E - T E’ T A E A - T - E’ T A 4 x A T - E’ A y y A e x 4 左再帰除去前後 右：除去後 E → T E’ E’ → - T E’| e T → A 　 による解析木 y A e 左： 除去前 E → E - T | T T → A による解析木 x 4

(抽象)構文木 Abstract Syntax Tree (AST) - y 4 E’ E T A e 解析木（parse tree）は当該の文法でいかに生成するかを表すだけ。構文解析の最終目的ではない。 - - 4 x y 書き換えればOK？ 構文解析の目的はASTの生成。ASTは意味に即した構造をあらわす

Abstract Syntax E → E + E | E - E | E * E | E / E|num | id - x - y 4 数式の抽象構文 E → E + E | E - E | E * E | E / E|num | id 一旦解析木ができれば、解析のための文法に依存した構造は捨て去って本来の意味を表す元の文法に戻したほうが後々処理が簡単になる. 元の文法は単に内部的に表現するためのデータ構造と読み替えられる.（抽象構文） - x - y 4 問い: 構文木が右図のようになる数式は何か？

ASTのデータ構造 x - 4 y x y - - 4 class Node { string name; Node* children[2+1]; 　 //子の数の上限＋終端判定用 }; class IDNode : public Node { string varname; class NumNode : public Node { int value; enum Operator { PLUS_OP, … } class OpNode : public Node { Operator op_kind; op - op num - 4 id id x y

ノードコンストラクタ str op n op_node(Token tk, Node* left, Node* right) ヒント：　Operator op_of_token(Token tk)をつくれ id_node(string str) num_node(int n) op id *right op str *left num n

Parsing Action いつASTをつくるか？ 再帰下降解析ではparse treeは関数の呼び出し関係を表すだけで実体はない。（終わってしまえばなくなってしまう。） ヒント： expppでは各関数呼び出し時に非終端記号名を印字した

exppp.cc //“exppp.cc”の一部 // Exp ::= Trm ExpPrim void Exp() { indentn(depth++);　　 printf(“Exp\n”); Trm(); ExpPrime(); --depth; }

E T E’ A E’ - T x A - T E’ y A e 4 expppの呼び出し木（call tree） printf(“E”) printf(“T”) printf(“E’”) - T x printf(“A”) A - T E’ printf(“T”) printf(“E’”) y printf(“A”) printf(“T”) A printf(“E’”) e printf(“A”) 4 expppの呼び出し木（call tree）

実行タイミングの表現 E → {printf(“E\n”);} T E’ {コマンド文}を文法記号と同じように取り扱って規則に埋め込む。 右辺の関数を左から順に実行する。 このような表現を翻訳スキームという。

E op T E’ - op A T - E’ - num x A T - E’ 4 y A e id id x 4 y

木データの授受 E’ E’ T - A - e e’ e e’ t t E’(e)→ - t=T(){e’=op_node(MINUS,e,t);} return E’(e’) この表現を翻訳関数と呼ぶ　（ほぼ実装言語のコード） - e E’ e’ e e’ E’ T t - t A {e’=op_node(MINUS,e,t);}

翻訳関数の作り方 呼び出し木をトラバースする道の中で、材料となる情報（子ノード、オペレータの種類）が出そろった後、それらを集約できるノードを選ぶ。 材料の情報の取得位置から集約するノードへの情報伝達 子から親へ：　戻り値 左の子から右の子へ：局所変数 親から子へ：　引数渡し

翻訳関数のまとめ・注意 非終端記号関数の引数／戻り値で情報の授受を行う。構文木への翻訳では材料となる木／処理後の木。 右辺の非終端記号関数は右辺の仮引数と、当該終端記号関数より左の関数呼び出しの戻り値を実引数とできる。 非終端記号関数は入れ子にして呼んではいけない。（出現順と呼び出し順は同じ） C/Ｃ++の関数呼び出しの複数の実引数で非終端記号関数を呼び出してはいけない。

数式から構文木への翻訳関数 … (+, /は省略) E()→ t=T() return E’(t) E’(e) → - t= T() 　　　　　　　 {e=op_node(MINUS,e,t);} return E’(e) | e return e T() → a=A () return T’(a) T’(t) → * 　a=A() 　　　　　　　 {t=op_node(PROD,t,a);} return T’(t) | e return t A() → {a=id_node(yy_val);} id return a … (+, /は省略)

課題: expast 数式を構文木に変換（翻訳）するプログラムexpastを作成せよ。 ヒント： Node* E(void) { Node* t = T(); return EPrm(t); } 　...

課題: astpp 構文木の構造を表示するプログラムastppを書き、出力結果を解析木の構造(＝expppの出力) と比較せよ。 ヒント：　class Node*（およびその派生クラス）を拡張してもよい。

課題 clause GExp に次の規則を追加した構文の解析器を作成せよ。（追加分のみ記す） E → E rel E | E & E | E|E | E => E | ! E | A A → true | false 優先順位：!,*/,+-,rel,&,|,=>の順に強い 結合性：　rel,&,|は左, 　　　=>は右 注意：kittyの式（値を持つ構文要素）のうち、関数呼び出しを除いたものに相当する。

kittyの構文 kittyの構文の解析器を作成せよ。 kitty用のASTはkitty用AST仕様を用いよ。

参考

文法の表す言語の検証 S → (S)S | e は釣り合いの取れた括弧の列だけからなる言語Lを生成する。 [証明] （Sから導出可能ならLの文）導出のステップ数nに関する帰納法 n=0のとき e ∊ L nステップ未満ならでLの文を導出すると仮定する。nステップの導出は一般に S ⇒ (S)S ⇒*lm(x)S ⇒*lm (x)y の形をしている。ここでx, yは帰納法の仮定からLの文であるから、(x)y ∊ Lが成り立つ。 （Lの文ならSから導出可能）　示せ （ヒント：記号列の長さに関する帰納法）

構文解析ルーチン生成系 Yacc コンパイラ hoge.y y.tab.c C コンパイラ y.tab.c a.out a.out 入力 出力

Yaccソースの構成 /* 宣言部 */ %{ #include <ctype.c> }% %token DIGIT %% /* 翻訳則部 */ expr : expr ’+’ term {$$ = $1+$2;} | term ; ... factor : ’(’ expr ’)’ {$$ = $2;} | DIGIT 支援用Cルーチン部 yylex(){ ... yylval= ... return DIGIT; }

予測型構文解析器の概念図 入力 a + b $ スタック 予測型構文解析 ルーチン X Y Z $ 構文解析表 M[A,a] 解析器の構造

解析器の動作(1/2) a + b $ a + b $ a Y Y Z Z $ $ a + b $ 停止 $

解析器の動作(2/2) a + b $ a + b $ A U Y V a S Z A UVW W $ Y Z A $ 構文解析表のエントリM[A, a]は入力a, 最左の非終端記号Aのとき、適用すべき 生成規則（の右辺）をあらわす。 U V W

誤りの検出 予測型構文解析器による誤りの検出 b $ a $ a A Y Y Z Z a≠b M[A,a]=空 $ $

参考：構文解析表の構成 FIRST(a) ----- 文法記号列aから導出される記号 列の先頭の集合(eの先頭はeとする) FIRST(a) = {head(b)| a ⇒*b} ただしhead(b)は記号列bの先頭の記号 FOLLOW(A) ----- 非終端記号Aのすぐ右に現れ 　る終端記号の集合 （Aが最右端のときはすぐ右は$） FOLLOW(A) = {a| S ⇒* aAab}

FIRST(a) Xが終端記号のとき FIRST(X)={X} Xが非終端記号のとき 問 左再帰をもつ文法に適用するとどうなるか？ 生成規則　X→e があるとき　　　　　　　　 FIRST(X) ∪= {e} （FIRST(X):=FIRST(X)∪{e} の意。ここだけ） 生成規則　X→Y1Y2…Ykがあるとき FIRST(X) ∪= FIRST(Y1) for i=2 to k+1　　　　　　　　 　　　　　　　if e ∈FIRST(Yi-1) then FIRST(X) ∪= FIRST(Yi) 　　else 終わり 上で　FIRST(Yk+1) ={e}　とせよ 問　左再帰をもつ文法に適用するとどうなるか？

FIRST(a) = X1X2…Xnとする FIRST(a) ∪= FIRST(X1)＼{e} for i=2 to k　　　　　　　　 　　　　　　　if e ∈FIRST(Xi-1) then FIRST(a) ∪= FIRST(Xi)＼{e} 　else 終わり if e ∈FIRST(Xn) then FIRST(a) ∪= {e} 問　FIRSTを再帰を使った擬似コードで書き直せ (ヒント：　条件式を使う)

FOLLOW(A) FOLLOW(S) :={$} A→aBb なる規則があれば FOLLOW(B) ∪= FIRST(b)＼{e} A→aBb なる規則があってe ∈FIRST(b)か、 または、 A→aBなる規則があれば FOLLOW(B) ∪= FOLLOW(A)

解析表の作成アルゴリズム 各生成規則 A→a について次を行う。 各a∈FIRST(a)について M[A, a]∪={a} /* aがA由来 */ e∈FIRST(a)なら各b∈FOLLOW(A)について M[A, b]∪={a} /* bがAの右外由来。含$ */

LL(1)文法 解析表作成アルゴリズムはどの文法にも有効であるが、表のエントリが多重になる可能性あり。 （左から走査、最左導出、先読み1文字）

誤りの回復 パニックモードによる回復： 同期集合 S(A)の要素に出会うまで読み飛ばす。 同期集合の案 S(A)=FOLLOW(A): S(A)の要素に出会ったらAをpop　（Aの部分を諦める） B→aAb があるときはS(A)=FOLLOW(A)∪FOLLOW(B) 例：　文→式 ; で“;”の書き忘れ

誤りの回復（続き） S(A)にFIRST(A)を加える。：Aはpopしない。（ゴミだったとおもってAを再開） 入力記号b ≠ スタックの上の終端記号a のとき、bはaだとおもって進める。 「S(a)=終端記号全体」と等価

左再帰除去アルゴリズム アルゴリズム 入力 文法G（閉路がなく、左辺がe のみの規則を持たない） 非終端記号をA1, A2 , …, Anとする。 for i:=1 to n do for j:=1 to i-1 do begin Aj-生成規則をAj → d1 | d2 | … | dnとすると、 　Ai → Ajgなる生成規則をAi → d1g | d2g | … | dng 　でおきかえる; Ai-生成規則から直接左再帰を除去; end 問　行列のはきだし法と比較せよ。 問　 S → Aa | b A → Ac | Sd | e から左再帰を除去せよ。（このばあいはeがあっても動く）