コンパイラの肝の部分

植山せんせいのコンパイラ入門、9cc.cを機能別にいくつかのファイルに分割してコンパイルするところで、その機能が、

  • 9cc.h: ヘッダファイル
  • main.c: main関数
  • parse.c: パーサ
  • codegen.c: コードジェネレータ
  • container.c: ベクタ、マップ、およびそのテストコード

に分けられるらしいのだが、最後のcontainer.cが微妙に謎だ。ちなみにパーサというのは構文解析の機能で、トークン列を入力して抽象構文木を出力する。コードジェネレータはその構文木を入力してアセンブリ言語を出力する。

f:id:agongji:20200730110241p:plain

この図がコンパイラの肝の部分だと思う。アセンブリ言語まで変換してもそのあとはアセンブラやらリンカやらを通したりオプティマイザを適宜通したりしないといけないらしいが、コンパイラ自体はアセンブリ言語の出力をひとまずのゴールとするようだ。

順に見ていくと、文字列というのはCのソースコードのことである。しかしCのソースコードを一文字ずつ読み取っても、文法とは全く関連のない文字がたくさんある。たとえばスペースだったりタブだったり改行文字だったり。これら言語とは無関係の文字列を除去して、意味のある文字をひとつずつ読み取ったものをトークン列という。

トークン列ができたからといって、それが意味をなすかどうかはわからない。(ときて)がこないようならそれは文法的に間違いであるが、トークン列はトークンの順序には全く関与しない。それがCの文法にふさわしい構成であるかをチェックするのはパーサーの仕事である。パーサーはトークン列を飲み込んで抽象構文木を吐く。Cのデータ構造では、構文木のNodeはNode構造体で表される。

プログラミング言語の文法というのは多くの部分が生成規則(production rule)と呼ばれるもので記述されている。これは記号を展開する規則の集合である。たとえば加減算の生成規則は、

expr = mul ("+" mul | "-" mul)*

と定義することができる。これは記号exprが右辺に展開できるということを表している。そして生成規則は構文木として表すことができる。

生成規則に従って記号を展開していくと、無限に正しいソースコードを記述することができる。それではその逆に、なにかしらのソースコードが与えられたときに、それを表す生成規則(構文木)を抽出するにはどうすればいいだろうか?答え:再帰下降構文解析

1つの生成規則を1つの関数にマップするという構文解析の手法を「再帰下降構文解析」といいます。上記のパーサではトークンを1つだけ先読みして、どの関数を呼び出すか、あるいはリターンするか、ということを決めていたが、そのようにトークンを1つだけ先読みする再帰下降パーサのことをLL(1)パーサといいます。また、LL(1)パーサが書ける文法のことをLL(1)文法といいます。

抽象構文木が特定できれば、そこからアセンブリ言語を吐くだけだが、ここでもひとつのテクニックが必要になる。スタックマシンである。なぜスタックマシンが必要かというと、入力された順番どおりに計算してはいけないからだ。1+2*3のような単純な式でも1を保留しておいて、2*3を計算しないといけない。この保留プロセスにスタックマシンが必要になる。

細かいことをいうと、スタックマシンというのは仮想マシンなので、実際の物理アーキテクチャがこれを実装する仕方を学ばなければならない。x86アーキテクチャではSP(スタックポインタ)とBP(ベースポインタ)という2つのレジスタを用いて仮想スタックを実装することになる。

ここまできてアセンブリを出力することができる。機能的には貧弱であってもプロセスの肝は以上の通りだと思われる。あとは複雑な文法を増やしていくことが必要なのだろう。