Rustで手書きC言語パーサー

Rust

達人プログラマーにこう書かれています。

毎年少なくとも言語を1つ学習する。 言語が異なると、同じ問題でも違った解決方法が採用されます。いくつかの異なったアプローチを学習すれば、思考に幅が生まれ、ぬかるみにはまる自体を避けられるようになります。

達人プログラマー P.20 より

今年の学習言語はRust！

インプットの軸として何が良いのかなと検討したところ、オライリーの『プログラミングRust 第2版』を読むのが良さそう。読みつつ何か作りながら学ぼうと思いました。 id:t-wada さんもオススメしていたし！

そして、「そういえば以前からC言語のコンパイラを作ってみたかった...」ということで、RustでC言語コンパイラを作りにチャレンジしてみることにしました。という日記です。

プログラミングRust 第2版

プログラミングRust 第2版

Amazon

Parserが動いた

Rustを書いていて面白かったのは、所有権とmoveの概念。move後の変数を使おうとするとコンパイルエラーになるのは面白い！本を読んでいるときは難しそうに感じたけど、実際にコードを書くとそこまで困らず、むしろ良いコードを書くのをRustコンパイラが助けてくれる感覚があって心強い。

さて、C言語コンパイラ実装の道のりはまだまだあるけど、なんとなく動くParserはできました。

コードはこちら↓

GitHub - kariyayo/ore-c-rust

勉強用なのでパーサージェネレータは使わずにパーサーを手書きしました。「Go言語でつくるインタプリタ」という本で紹介されているPratt構文解析の実装を参考にしています。

例えば以下のお試しCコード（上記リポジトリのsample.c）。

int main() {
    int s = 1 + 2;
    return 0;
}

実行（ $ cargo run --package ore_c_rust --bin parse ）すると、以下のASTになる。

Program {
  external_items: [
    FunctionDecl {
      return_type_dec: Named(
          "int",
      ),
      name: "main",
      parameters: [],
      body: Some(
        Block(
          [
            VarDecl(
              [
                (
                  Named(
                    "int",
                  ),
                  Declarator {
                    name: "s",
                    value: Some(
                      InfixExpression {
                        operator: "+",
                        left: Int(
                          1,
                        ),
                        right: Int(
                          2,
                        ),
                      },
                    ),
                  },
                ),
              ],
            ),
            Return(
              Some(
                Int(
                  0,
                ),
              ),
            ),
          ],
        ),
      ),
    },
  ],
}

悩んだところ

C言語Switch文のfallthrough

そこまで困らずと書いたものの、困ったところもあった。C言語のswitch文。

switch (x) {
    case 1:
        printf("One\n");
    case 2:
        printf("Two\n");
        break;
    case 3:
        printf("Three\n");
        break;
}

最初、ASTの構造体は以下のようにしていた。 enum Statement が文を表すASTのノード。

pub enum Statement {
    Return(Option<Expression>),
    If { condition: Expression, consequence: Box<Statement>, alternative: Option<Box<Statement>> },
    ...
    Switch { condition: Expression, arms: Vec<SwitchArm> },
    ...
}

pub enum SwitchArm {
    Case(Vec<Expression>, Vec<Statement>),
    Default(Vec<Statement>),
}

Statement::Switch の condition がCコードの switch (x) の x を表して、 arms がCコードの各 case ... 部分を表す。

ところが、以下のようなfallthroughに対応しようとして困った。

switch (x) {
    case 1:
    case 2:
        printf("One or Two\n");
    case 3:
        printf("Three\n");
        break;
}

この場合、 printf("Three\n"); break; は、 case 1 , case 2 , case 3 いずれでも実行される。

つまり、 printf("Three\n"); を表す Statement は、複数の SwitchArm から参照されることになる。ここで出てくるのがRustの所有権。

私が普段使ってる他の言語だったら、Statementオブジェクトへの参照を複数のSwitchArmで持つ実装をしたと思う。そして、 Statementの参照カウントがゼロになるとGCによりメモリからStatementが回収される。

Rustではmoveがあり所有者は1つ。Rustでも Rc 型 で参照カウント方式を使えるが、なんとなくRustらしくないのかなと思って避ける方法を考えた。

解決策

考えた結果、以下のような表現にした。fallthroughする場合でも Statement の所有者は SwitchBlock のみであり、 SwitchBlock はswitchブロック内の Statement を全て持つ。また、 SwitchLabelEntry でcaseごとに「どのインデックスから実行するか」を管理する。

pub enum Statement {
    ...
    Switch { condition: Expression, switch_block: SwitchBlock },
    ...
}

pub struct SwitchBlock {
    pub label_entries: Vec<SwitchLabelEntry>,
    pub body: Vec<Statement>, // case節共通の文リスト
}

pub struct SwitchLabelEntry {
    pub labels: Vec<SwitchLabel>, // case 1: case 2: や case 3: を表す
    pub start_index: i32,         // body内のどこから実行を始めるか
}

pub enum SwitchLabel {
    Case(Expression),
    Default,
}

さきほどのfallthroughするコードをparseすると、以下のようになる。

Switch {
  condition: Identifier(
    "x",
  ),
  switch_block: SwitchBlock {
    label_entries: [
      SwitchLabelEntry {
        labels: [
          Case(
            Int(
              1,
            ),
          ),
          Case(
            Int(
              2,
            ),
          ),
        ],
        start_index: 0,
      },
      SwitchLabelEntry {
        labels: [
          Case(
            Int(
              3,
            ),
          ),
        ],
        start_index: 1,
      },
    ],
    body: [
      ExpressionStatement(
        FunctionCallExpression {
          function_name: "printf",
          arguments: [
            StringLiteral(
              "One or Two\\n",
            ),
          ],
        },
      ),
      ExpressionStatement(
        FunctionCallExpression {
          function_name: "printf",
          arguments: [
            StringLiteral(
              "Three\\n",
            ),
          ],
        },
      ),
      Break,
    ],
  },
},

Rc 型を使わずにfallthroughに対応できた！これが良い設計かどうかは正直まだ自信がない……誰か教えてください 🙏

おしまい

まだ対応できてないことがありつつも、Parserがなんとなく動くところまでできました！

さて、次は意味解析。...なのだけど、Parserを手書きした時点で『プログラミングRust』を読む目的はそこそこ満たされてしまった感がある。

実装がこの先進むかどうか、少し不安。。

（まだ読んでない19章「並列性」、20章「非同期プログラミング」も楽しみ）