しかくいさんかく

解答略のメモ

20日目: [コンパイラ] 構文解析 (人力編)

アドベントカレンダー2017 低レイヤ コンパイラ

この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の20日目の記事です。

今までx86のエミュレータやCPUなど、様々な低レイヤ環境を作ってきた。 その中で、個人的に最も製作が難しかったのが、コンパイラの構文解析器だ。 これを一日で解説するのは無理なので、2日に分けて書こうと思う。 今日はサンプルコードを人力で構文解析してコツをつかむ。 明日は実装コードの解説を行う予定。

構文解析とは

昨日作ったトークンの配列

f:id:kaitou_ryaku:20171219000027p:plain:w500

これを以下の解析木に変換することを、構文解析という。

f:id:kaitou_ryaku:20171219000052p:plain

ツリーを構成する長方形はノードと呼ばれている。 その中の、赤字で書かれたPROGRAMやF_DECをノード属性と呼ぶことにする。 ちなみに最初の画像の緑文字はトークン属性で、両者は別物だ。混同しないように。

このツリーは有効グラフで、最上段のPROGRAMノードはサンプルコード全体に対応している。 そこから下に向かってF_DECが生えており、そこから5個のノードが生えている。

重要なのは、これら5個のノード間には前後関係が存在することだ。 ツリー中にはあらわに描かなかったが、TYPEの次のノードがVARIABLEで、その次のノードがSKIP_NODEとなっている。 この順序は変更できない。

緑のトークン配列から赤の解析木を作るルールは、昨日の字句解析と同じくBNFで与えられる。

構文解析のBNF

ノードの種類を定義するBNFだが、正式版は以下で与えられる。

f:id:kaitou_ryaku:20171219073549p:plain

左辺の赤字で書かれたノード属性を、右辺のトークン属性とノード属性で再帰的に定義している。 ep は empty の略で、そこに何もないことを表している。

ちなみに、このBNFに文字列("int"とか"return"とか)は出現しない。理由がわかるだろうか？

昨日(字句解析)と今日(構文解析)のBNFの違いは

つまり今回のBNFでは、文字列の情報はトークン属性というラベルで隠蔽されている。 このBNFは理論的に真っ当な形式なのだが、人間には読みにくい。もう少し分かりやすい表記法を使うと

f:id:kaitou_ryaku:20171219073600p:plain

これはさっきの正式版BNFに対し、昨日の字句解析のBNFを参照して

トークン属性 字句解析のBNFの定義
EQUAL "="
COMMA ","
SEMICOLON ";"
IF_KEYWORD "if"

これらの、右辺が一種類しかないトークン属性を、その文字列で置換したものだ。

この簡易版BNFなら意味が理解しやすい。日本語でいくつか説明すると

ノード属性 日本語訳 構成要素
PROGRAM ソース全体 グローバル変数宣言と、関数宣言(定義)と、関数プロトタイプ宣言の3種類の列
F_DEC 関数宣言 型名と、関数名と、引数リストの列と、関数本体
FUNCTION 関数本体 ローカル変数宣言の列と、文の列
SENTENCE 文 種類としては、複数の文、IF文、WHILE文、RETURN文、関数呼び出し、代入文がある
ASSIGN 代入文 a = 1;, a = f(b)+2;, a = 1==2 ;など
EXPRESSION あらゆる式 両辺比較を含みうる数式。a*f(b) > 2*(3+4)+5, a*f(b), a, f(b), 2*(3+4)+5, (3+4), 5など
FORMULA 多項式 両辺比較を含まない数式。a*f(b), a, f(b), 2*(3+4)+5, (3+4), 5など。1<2はダメ。
TERM 単項式 因数分解された数式。a*f(b), a, f(b), 2*(3+4), 5など。1+2はダメ。
FACTOR 因子 a, f(b), 2, (3+4), (1==2) など。1*2はダメ。

構文解析のやりかたを直感的に把握するため、昨日と同様に人力でパースして、解析木を作ってみよう。

解析木の作成 (人力)

ここでは再帰下降という方法で構文解析を行う。

いつもの字句解析結果

f:id:kaitou_ryaku:20171219073613p:plain:w300

これを構文解析して解析木を作る。

BNFをここで使うやつだけに絞って再掲しておく。

f:id:kaitou_ryaku:20171219073622p:plain:w500

さぁ、いよいよ木を作るぞ。

プログラム全体の分割

まずプログラム全体からなるトークン配列を、構文解析器に入れる。

構文解析器は、プログラム全体がBNFの一番上のPROGRAMにマッチするか調べる。

ここで言うマッチとは、プログラム全体が

  • V_DEC ";"
  • F_DEC
  • PROTOTYPE ";"

の3種類がたくさん並んだトークン列であると見抜くことだ1。 マッチに成功した時点で以下のようなツリーを作る。

f:id:kaitou_ryaku:20171219072651p:plain:w500

今回解析したいコードは、グローバル変数も関数プロトタイプもないので、PROGRAMからF_DECだけ生えた木になる。

次にF_DECにマッチしたトークン列を、「F_DEC専用の解析器」に投げる。 (もしV_DECやPROTOTYPEが存在すれば、同様に専用解析器に投げる。)

F_DEC専用解析器は

ノード属性 構文解析BNFによる定義
F_DEC TYPE VARIABLE "(" (ep | V_DEC (, V_DEC)*) ")" FUNCTION

に従い、入力されたトークン列を解析する。

入力されたトークン列は

  • TYPE
  • VARIABLE
  • V_DEC
  • FUNCTION

の4種類のノードに分割される。この時点で以下のようなツリーを作る。

f:id:kaitou_ryaku:20171219072658p:plain:w400

今回解析したいコードには引数が無いので、TYPEとVARIABLEとFUNCTIONの3ノードが生えたツリーになる。

関数型と関数名の解析

続いてTYPEにマッチしたトークン列を、TYPE専用解析器に投げる。

ノード属性 構文解析BNFによる定義
TYPE TYPE_KEYWORD

に従って解析すると、、、 このBNFの右辺は、トークン属性のTYPE_KEYWORDだけしかない。ノード属性が入っていない。 ツリーの言葉に直すと、要するにTYPEはツリーの末端ということだ。これでTYPEの解析は終了。

次にVARIABLEにマッチしたトークン列をVARIABLE専用解析器に投げる。

ノード属性 構文解析BNFによる定義
VARIABLE IDENTITY

これもトークン属性しかないので、ツリーの末端ということで解析終了。

関数本体の解析

前節で TYPE(関数の型)と VARIABLE(関数名)の解析は終わった。

最後に残された FUNCTION(関数本体)にマッチしたトークン列を、FUNCTION専用解析器に投げる。この解析器は

ノード属性 構文解析BNFによる定義
FUNCTION "{" ( V_DEC ";" )* SENTENCE* "}"

に従って、入力されたトークン列を解析する。そしてマッチに成功した時点で以下のようなツリーを作る。

f:id:kaitou_ryaku:20171219072702p:plain:w400

次はV_DECにマッチしたトークン列

TYPE_KEYWORD IDENTIFY ";"

これをV_DEC専用解析器に投げる。以下のBNF

ノード属性 構文解析BNFによる定義
V_DEC TYPE VARIABLE

にマッチさせる。結果、V_DECノードは TYPEとVARIABLE という2つのノードに分割される。

これらのノードは、前節で書いたようにノードの末端になるので、解析は即座に終わる。 その結果得られるツリーは

f:id:kaitou_ryaku:20171219072707p:plain:w400

文の解析

だいぶ慣れてきたと思うので、ここからは飛ばし気味に行こう。 変数宣言の解析は終了したので、次の「文1」にあたる

IDENTIFY "=" NUMBER ";"

というトークン列をSENTENCE専用解析器に投げる。 以下のBNFに従って解析すると

ノード属性 構文解析BNFによる定義
SENTENCE ( ";" | "{" SENTENCE* "}" | IF_FLOW | WHILE_FLOW | RETURN | CALL ";" | ASSIGN )

トークン列全体がASSIGNにマッチする。 これをASSIGN専用解析器に投げる。 以下のBNFに従って解析すると

ノード属性 構文解析BNFによる定義
ASSIGN VARIABLE "=" EXPRESSION ";"

VARIABLEにマッチした部分は、前述の通りノードの末端になるので、解析は即座に終わる。

次にEXPRESSIONにマッチした部分を専用解析器に投げて、、と繰り返していくと、最終的にIMMEDIATE専用解析器に投げることになる。

ノード属性 構文解析BNFによる定義
IMMEDIATE NUMBER

BNFの定義の中にノード属性(赤字)が入っていないので、ここで解析が終了する。

この時点でのツリーは

f:id:kaitou_ryaku:20171219072713p:plain:w500

「文1」の解析が終わったので、次は「文2」の解析に移る。

"return" NUMBER ";"

というトークン列をSENTENCE専用解析器に投げると、 トークン列全体がRETURNにマッチする。

続いてトークン列全体をRETURN専用解析器に投げるとEXPRESSIONにマッチして、EXPRESSION専用解析器に投げるとFORMULAにマッチして、、、と繰り返すと、最終的にIMMEDIATE専用解析器に到達し、前述の通り解析が終了する。

最終結果は

f:id:kaitou_ryaku:20171219072722p:plain:w500

やっと解析木の作成が終わった。めでたい。

SKIP_NODEに関する補足

プログラム中の代入文 a=3; に着目してほしい。

処理を追うと、まず字句解析してIDENTIFY "=" NUMBER ";"を得たのだった。

次にASSIGN専用の構文解析器

ノード属性 構文解析BNFによる定義
ASSIGN VARIABLE "=" EXPRESSION ";"

を用いて解析を行った結果

  • VARIABLE の トークン(IDENTITY, a)
  • EXPRESSION の (NUMBER, 3)

を得たのだった。

この構文解析の際に、"="と";"の2つのトークンを読み飛ばした。 つまり解析木の中にイコールとセミコロンは存在しなかった。

人力でパースする場合は今回のように読み飛ばしても構わないのだが、構文解析用のプログラムを作るときに読み飛ばしを行うと、バグが発生しやすくなる。 これを避けるテクニックとして、読み飛ばしを行う代わりにSKIP_NODEという名前の仮想ノードを生やす作戦がある。 この記事の冒頭の解析木はSKIP_NODEのテクを駆使して作成したバージョンになっている。

明日は、このSKIP_NODEが存在する解析木を自動生成するプログラムを作ろう。

  1. 本来は、完璧に見抜いてから後続の処理を実行すべきだ。しかしそれは難しいので、僕の作ったプログラムは「後ろに“(”が無いからV_DECぽい」「後ろに“(”があって“{”がないからF_DECぽい」みたいな雰囲気でPROGRAMの下にノードを生やしている。↩