コマ1: AST + インタープリター

スキャフォールドの動作確認 — AST を見てみる

実装に入る前に、教員提供の Lexer/Parser が AST を正しく構築できることを確認する。 この回で初めて提供 Lexer/Parser を使うため、まずここで動作を確かめる。 Lexer は // 行コメントを読み飛ばし、if while return などキーワード12語と それ以外の識別子を区別する。この字句解析はすでに提供されており、自分で書く対象ではない。

python3 scaffold/parse_viewer.py sessions/01_interpreter/tests/add_mul.c

このプログラムの内容は次の通り。

int main() {
    return 1 + 2 * 3;
}

実行すると、次のようなS式が表示される。

(program
  (funcdef "main" :type int (params)
    (block
      (return
        (add (num 1)
          (mul (num 2) (num 3)))))))

この出力は、1 + 2 * 3 が次の構造として解析されたことを表している。

つまり、1 + 2 * 3 は次のような木として表されている。

(add
  (num 1)
  (mul (num 2) (num 3)))

2 * 3 が add の右側の子になっている。 掛け算が先にまとめられている（演算子の優先順位が正しく反映されている）ことを確認する。 演算子の優先順位は Parser がすでに処理しているため、eval_ast() は渡された木をそのまま評価すればよい。

S 式ではなく木の形で見たいときは、学習ツールの構造表示 に同じソースを貼るとブラウザ上に構文木が表示され、ノードとソース範囲の対応も確認できる。

木の形は規則で決まっている

上の木の形は偶然ではない。Parser は次の規則で木を組み立てる。

• 優先順位の低い演算子ほど、根に近い側に置かれる。 1 + 2 * 3 の根が add で mul がその子になるのは、+ が * より優先順位が低いからである。
• 同じ優先順位の演算子が並んだときは、左から順にまとめる（左結合）。 10 - 3 - 2 は (sub (sub (num 10) (num 3)) (num 2)) となり、(10 - 3) - 2 を表す。
• カッコは、この規則に優先して木の形を直接指定する。 (1 + 2) * 3 では逆に add が mul の子になる。

この3つの規則で、どの式についても届く木の形が決まる。演算子ごとの優先順位は、 後述の言語仕様の節で優先順位表として示す。疑わしいときは parse_viewer.py に 式を入れて、規則どおりの木になることを確かめられる。

この回で扱う範囲

対象にするプログラムは、次の形に限定する。

int main() {
    return 式;
}

扱う式は以下の通り。

変数、代入、if、while、関数呼び出しはまだ扱わない。

program       ::= func_def        /* ユーザー定義関数はコマ6 */

func_def    ::= 'int' 'main' '(' ')' func_body   /* 一般の関数定義はコマ6 */
func_body   ::= '{' stmt '}'

stmt        ::= 'return' expr ';'

expr        ::= binary_expr      /* 代入はコマ3、条件はコマ4 */
binary_expr ::= unary_expr { bin_op unary_expr }
bin_op      ::= '*' | '/' | '%'  /* 優先順位・結合は下の表。関係・等値はコマ4、論理はコマ13 */
              | '+' | '-'
unary_expr  ::= primary_expr
              | '-'  unary_expr
primary_expr ::= INT_LITERAL
               | '(' expr ')'

Node の構造

parse_viewer.py のS式は表示用の形式である。 mycc.py に渡される実体は、scaffold/ast_def.py で定義されている Node オブジェクトである。

Node は、AST の1つの節点を表す入れ物である。 たとえば、数値、足し算、掛け算は、それぞれ別の種類の Node として表される。

主に見るフィールドは次の通り。

ノードの種類は、ast_def.py で定義されている定数で判定する。

たとえば、次のS式を考える。

(add (num 1) (mul (num 2) (num 3)))

これは Node では次のような関係になっている。

実装方針

eval_ast(node) は、node.kind を見て処理を分ける。 node.kind は文字列（'Num', 'Add', …）であり、ast_def.py で定数 ND_NUM, ND_ADD 等も定義されている。 スケルトンでは eval_ast が TODO になっているため、以下の各ケースを実装する。

方針は次の通り。

重要なのは、子ノードもまた Node であるという点である。 そのため、子ノードの値を求めるときも同じ eval_ast() を使える。

このように、自分自身を使って木をたどる関数を再帰関数という。

葉の値が親に返り、根まで上がると式全体の値になる。 ①〜⑤は値が確定する順番である。

編集するファイル

• mycc.py

eval_ast(node) を実装する。

実装手順

1. スケルトンの eval_ast に case 'Num' が実装例として書かれていることを確認する（node.val を返すだけ）
2. case 'Add' / case 'Sub' / case 'Mul' を埋める（eval_ast(node.lhs) と eval_ast(node.rhs) を再帰で求め、足す・引く・掛ける）
3. case 'Neg' を埋める（eval_ast(node.operand) の符号を反転する）
4. case 'Div' / case 'Mod' を埋める（提供済みの c_div / c_mod に左右の評価結果を渡す。Python の // と % は使わない）

case _ で RuntimeError を上げる分岐と、main の return 式を eval_ast へ渡す run_main(prog) は、あらかじめスケルトンに書かれている。

tests/

上から順に通していくと、どこで詰まっているかが1機能ぶんに絞られる。 「通る目安」は実装手順の番号である。

テスト

python3 sessions/01_interpreter/check.py

tests/*.c の main 関数内の return 式を評価し、対応する .ans と比較する。

個別に実行する場合は、次のようにする。

python3 sessions/01_interpreter/mycc.py sessions/01_interpreter/tests/add_mul.c

成功すると、次のように表示される。

評価結果: 7

注意

この回のテストでは、割り算・剰余の右辺は 0 にならない。

また、この回では負数を含む割り算・剰余は扱わない。 Python の // や % は、負数を含む場合に C の整数除算・剰余と挙動が異なるためである。

ここまでで着手できる発展課題

AST とインタープリターまで作ったので、字句解析・構文解析とは何かを CYK 法で体験する F0（コンパイラ本編と独立、前提はこのコマまで）に着手できる。

この資料の原稿を見る