コンパイラの実装

全体の流れ

プログラミング言語の処理系はだいたい似たような手順を踏むものです。Mae-Bの処理系も、「プログラミング言語を作る」で作ったDiksamや、そのだいぶ後にJavaで作ったsamplanと構造は似ています。コンパイラの大まかな手順は以下の通り。カッコ内のファイル名は、compilerディレクトリ以下のソースファイル名です。

1. レキシカルアナライザでソースをトークンに分割(lexer.c)
2. パーサでトークンから解析木を構築(parser.c)
3. パーサで解釈しきれなかった付属情報を付与(fix_tree.c)
4. コード生成(gencode.c)

今回は、(Diksamとは違って)yacc/lexのようなツールは使っていません。samplanと同様にレキシカルアナライザとパーサを手書きで作っています。

レキシカルアナライザ(lexer.c)

レキシカルアナライザはふつうに「取りすぎたら1文字分だけungetc()で1文戻せる有限オートマトンで実装しています。bcp_get_token()を呼ぶごとに、入力ファイルからトークンを取得できます。

取得できるトークンを表現するのがToken構造体で、その定義は以下の通り。

typedef enum {
    IF_TOKEN,
    ELSE_TOKEN,
    WHILE_TOKEN,
    SWITCH_TOKEN,
    CASE_TOKEN,
    DEFAULT_TOKEN,
    GOTO_TOKEN,
    BREAK_TOKEN,
    RETURN_TOKEN,
    EXTRN_TOKEN,
    AUTO_TOKEN,
    LP_TOKEN,
    RP_TOKEN,
    LC_TOKEN,
    RC_TOKEN,
    LB_TOKEN,
    RB_TOKEN,
    AMPERSAND_TOKEN,
    QUESTION_TOKEN,
    COLON_TOKEN,
    SEMICOLON_TOKEN,
    ASSIGN_TOKEN,
    ADD_ASSIGN_TOKEN,
    SUB_ASSIGN_TOKEN,
    MUL_ASSIGN_TOKEN,
    DIV_ASSIGN_TOKEN,
    MOD_ASSIGN_TOKEN,
    LEFT_SHIFT_ASSIGN_TOKEN,
    RIGHT_SHIFT_ASSIGN_TOKEN,
    LT_ASSIGN_TOKEN,
    LE_ASSIGN_TOKEN,
    GT_ASSIGN_TOKEN,
    GE_ASSIGN_TOKEN,
    EQ_ASSIGN_TOKEN,
    NE_ASSIGN_TOKEN,
    BIT_AND_ASSIGN_TOKEN,
    BIT_OR_ASSIGN_TOKEN,
    BIT_XOR_ASSIGN_TOKEN,
    INC_TOKEN,
    DEC_TOKEN,
    MINUS_TOKEN,
    EXCLAMATION_TOKEN,
    BIT_OR_TOKEN,
    BIT_XOR_TOKEN,
    BIT_NOT_TOKEN,
    EQ_TOKEN,
    NE_TOKEN,
    LT_TOKEN,
    LE_TOKEN,
    GT_TOKEN,
    GE_TOKEN,
    LEFT_BIT_SHIFT_TOKEN,
    RIGHT_BIT_SHIFT_TOKEN,
    PLUS_TOKEN,
    PERCENT_TOKEN,
    ASTERISK_TOKEN,
    SLASH_TOKEN,
    COMMA_TOKEN,
    NAME_TOKEN,
    INT_LITERAL_TOKEN,
    STRING_LITERAL_TOKEN,
    CHARS_TOKEN,
    END_OF_FILE_TOKEN
} TokenKind;

typedef struct {
    int length;
    signed char *str;
} StringLiteral;

typedef struct {
    TokenKind kind;
    union {
        int int_value;
        char *name;
        StringLiteral str_literal;
        unsigned int chars;
    } u;
    int line_number;
} Token;

見ての通り、列挙型TokenKindでトークンの種類を示しています。数値定数、変数名等の名前、文字列リテラル、文字リテラルはトークンに値を持つのでToken内に保持しています。ここで、文字列リテラルについて、単なるchar *ではなく文字数まで持っているのは、Bでは「*0」と書くことで文字列リテラル中に0を含めることができるからです(書き方が「\0」なだけでCでも同じですが)。

パーサ(parser.c)

パーサも普通に再帰下降パーサです。Mae-BはMH-TSS版をベースにすると言っておいてなんですが、文法は基本的にPDP-11版を参照しています。そっちのドキュメントにしかBNFが載っていないからです。

プログラミング言語を再帰下降パーサでパースするというと、簡単な言語ではLL(1)パーサを作ることが多いと思います。つまり「1トークンだけ先読みしてパースするパーサ」です。たとえば上で挙げたsamplanはLL(1)です。

しかし、Bの文法はLL(1)ではパースできません。ラベルがあるからです。

標準PascalがLL(1)文法なのですが、標準PascalはLL(1)の文法に収めるためにラベルに名前が使えませんでした(番号しか使えない)。Bではラベルに名前が使えるのでLL(1)をはみ出すことになります。

ところで、LL(1)の再帰下降パーサを書く時、「常にひとつ先のトークンを先読みしておく」やり方と、「読み込みすぎたらトークンをひとつだけ戻せるようにしておく」やり方という2種類の方法があります。私は(当人の性格が行き当たりばったりであるせいか)いつも後者の方法で書いていました。この方法でラベル付きの文をパースしようとすると、こうなります。

1. 今、「文」をパースしようとしている。
2. 最初に読み込んだトークンが「名前」だった。この時点では、以下のようなラベル付きの文のラベル部分を読み込んだのか、それとも代入文の左辺の変数名を読み込んだのか、関数呼び出しの関数名を読み込んだのか、区別がつかない。

     abc:
       printf("hello*n");
   

3. 次のトークンが「:」だったら、ラベル付き文であることが確定する。ただし、そうでなかった場合、「式文」の式のパースに入りたいところだが、ここで戻すべきトークンは、「名前」と、その次に読み込んだ関数呼び出しの「(」とか代入の「=」とかのふたつであり、「トークンがひとつだけ戻せる」パーサではこれに対応できない。

まあこれを解決するのは簡単で、トークンを最大ふたつ戻せるようにするだけです(「常にひとつ先のトークンを先読みしておく」方法だと対応が面倒だと思う)。

Mae-Bでは、パーサはほとんど何も考えずに解析木を作るだけです。この段階でやっていることは、定数部分式の畳み込み(「1 + 1」という式があったらコンパイルの時点で計算して2にしてしまう)ぐらいです。Mae-Bでは、畳み込むのは定数同士の加減乗除剰余だけです。

付属情報の付与(fix_tree.c)

ファイル全体を解析木に変換したら、その解析木を頭から辿りながらその他の情報を追加していきます。

関数ローカルな名前

関数内で登場する名前は、以下の3種類です。

1. extrnで参照したグローバル変数
2. 内部記憶域の変数。つまり、ラベル
3. 自動変数

これを、関数ごとに、LocalName構造体の連結リストで保持します。

typedef enum {
    EXTERNAL_LOCAL_NAME,
    INTERNAL_LOCAL_NAME,
    AUTO_LOCAL_NAME
} LocalNameKind;

typedef struct {
    int static_name_index;
} ExternalLocalName;

typedef struct {
    int static_name_index;
    Boolean defined;
} InternalLocalName;

typedef struct {
    Boolean is_vec;
    int vec_size;
    Boolean is_parameter;
    int offset;
} AutoLocalName;

typedef struct LocalName_tag {
    LocalNameKind kind;
    char *name;
    int line_number;
    union {
        ExternalLocalName ext_ln;
        InternalLocalName int_ln;
        AutoLocalName auto_ln;
    } u;
    struct LocalName_tag *next;
} LocalName;

ここで、グローバル変数(ExternalLocalName)とラベル(InternalLocalName)はstatic_name_indexというメンバを持っています。これは次に説明するStaticName配列の添字です。グローバル変数とラベルは(ラベルにも代入できるようにすると決めたので)静的な記憶領域を保持するので、両方に登録します。

静的変数

静的な記憶領域に保持される名前はStaticName構造体に登録します。これはrealloc()により伸びる配列で保持しています。

typedef struct {
    char *name;
    Boolean is_function;
    Boolean is_vec;
    int vec_size;
    Boolean defined;
    int address;
    IVal *initializer;
} StaticName;

nameは(当然)名前ですが、ラベルは関数が違えば名前が重複する可能性があるので、StaticNameに登録する際には「<関数名>:<ラベル名>」という名前で登録しています。また、is_functionというメンバがあることからわかるように、関数もStaticNameに登録されます。

StaticName構造体のメンバのうち、fix_tree.cの段階では、addressは埋まりません。これはこの名前の静的変数領域でのアドレスなのですが、BVMのメモリマップを見ればわかるようにコード生成が終わるまで静的記憶領域のアドレスは決まらないからです。

breakの対象

break文は、「一番近い」while文かswitch文を抜けます。コード生成のときのため、fix_tree.cの段階でbreak文の構造体BreakStatementに抜ける対象の文へのポインタを持たせています。

typedef struct {
    Statement *outer; ←脱出対象の文
} BreakStatement;

whileとかswitchの方には、コード生成の段階で、脱出先のラベルを入れておきます。この「ラベル」が何かについては「ジャンプ先」を参照のこと。

typedef struct {
    Expression *cond;
    Statement *stmt;
    int end_label; ←脱出先のラベル
} WhileStatement;

直近のwhileとかswitchを探せるようにするために、fix_tree.cで解析木を辿りながらwhileとswitchだけをスタックに積んでいます。breakは、このスタックのトップの文を抜けるわけです。

static int st_outer_statement_count;
static int st_outer_statement_alloc_count;
static Statement **st_outer_statement_stack;

コード生成(gencode.c)

概要

コード生成は、解析木を深さ優先順で辿りながらコードを吐いていきます。たとえば以下のようなコードは、

  auto a;
  extrn ext1;

  a = ext1 + 5;

こんなバイトコードになります。

 15 PUSH_STATIC 28 ←アドレス28(ext1のアドレス)の値をスタックに積む
 17 PUSH 5         ←定数5をスタックに積む
 19 ADD            ←スタックトップのふたつの値を加算しスタックに積む
 20 POP_AUTO 0     ←スタックトップの値を0番目の自動変数(a)にポップする

ところで、Bは、Cと同様代入式も値を持ちます。よって、a = b = 0;のような式も書けます。この時、b = 0という部分式は、代入が終わった後に、値をスタックに残さなければいけません。しかし、ただ「a = 0;」と書いたときその値をいったんスタックに積んで無意味にPOPするのも無駄です。そこで、代入式、インクリメント/デクリメント式、関数呼び出しについては、文のトップレベルの場合だけ結果をスタックに積まないような制御を入れています。

領域の初期化

コード生成後、文字列リテラル領域と静的変数領域を初期化します。

文字列リテラルについては、この段階で、「バイトの並び」を、「intの上位ビットから左詰め」に変換します(つまりリトルエンディアンのCPUならバイト順なら逆順になります)。これを最後のフェーズで行うのは、早くやってしまうとデバッグのためにprintf()とかできなくなるためです……

静的変数領域については、初期化子があればその値で、なければゼロで埋めます。

出力したコードのフィックス

上述の通り、解析木を辿りながら順にコードを生成しますが、その段階では正しいコードを生成できないケースがあります。以下のようなケースです。

1. 静的変数のアドレス
   上のコードで、変数ext1の値をスタックに積む際に、PUSH_STATIC 28というコードを生成していますが、28というext1のアドレスはコード生成が終わるまでわかりません。そこで、最初のコード生成の段階では、PUSH_STATIC、 POP_STATICの後ろには暫定的にStaticNameの添字を出力しておいて、後でコードをスキャンして、PUSH_STATIC、 POP_STATICの後ろを置換しています。
2. ジャンプ先
   if文とかwhile文とかでジャンプするとき、ソースコードで見て下に向かって飛ぶときにはジャンプ命令の生成時には飛び先のアドレスは確定していません。そこで、(飛び先が上か下かにかかわらず)ジャンプ命令生成時にはget_label()関数でいったん「ラベル」を取得して、ジャンプ命令の後ろにはそのラベルを出力しておき、飛び先のアドレスが決まったらset_label()関数でラベルにアドレスをセットします。その上で、静的変数のアドレス同様後でコードをスキャンして、ジャンプ命令の後ろのラベルを実アドレスに変換します。
3. 静的変数のアドレスその2
   変数ext1の値をスタックに積む際はPUSH_STATIC命令を使いますが、&ext1の値をスタックに積むときは、単にPUSH 28というコードを生成しなければいけません。PUSH_STATICのケースと異なるのは、PUSHという命令は、ただ定数をスタックにプッシュする際にも使うということです。上のふたつのケースでは、後でコードをスキャンしてPUSH_STATICとかジャンプ命令の後ろをすべて置換すればよかったですが、PUSH命令の後ろを「すべて」置換するわけにはいきません。
   そこで、置換が必要なPUSH命令のアドレスをpending_pushという動的配列に保存しておいて、後でそこに記録されたPUSHの後ろだけを置換する、ということをしています。

公開日: 2026/01/18

間違い等ありましたら、掲示板にご連絡願います。

前のページ(B仮想マシン) | ひとつ上のページへ戻る | トップページへ戻る