Rustで作る自作コンパイラ入門シリーズ
Part1【字句解析】 | Part2【構文解析】 | Part3【意味解析】 | Part4【コード生成】 | Part5【完結】

はじめに

前回はソースコードをトークン列に分解しました。

"let x = 1 + 2 * 3;"
→ [Let, Ident("x"), Eq, Number(1), Plus, Number(2), Star, Number(3), Semicolon]

でも、これだけじゃコンピュータは計算できません。なぜなら...

「1 + 2 * 3 は 1 + 6 なのか 3 * 3 なのか」

この情報がない！

今回は、トークン列を**木構造（AST）**に変換して、演算の順序を明確にします。

目次

ASTとは
演算子の優先順位
ASTを設計する
Parserを実装する
動かしてみる

ASTとは

AST（Abstract Syntax Tree） = 抽象構文木

プログラムの構造を木で表現したものです。

例

1 + 2 * 3

これのASTは：

木構造にすると、下から上に計算すればいいことがわかります：

Mul(2, 3) = 6
Add(1, 6) = 7

演算子の優先順位が木の深さで表現されているんです！

演算子の優先順位

プログラミング言語では、演算子に優先順位があります：

優先順位	演算子	例
高	`*` `/` `%`	乗除
↓	`+` `-`	加減
↓	`<` `>` `<=` `>=`	比較
↓	`==` `!=`	等値
↓	`&&`	論理AND
低	`

なぜ優先順位が必要？

if a < b && c > d || e == f { ... }

これを正しくパースするには：

||
├── &&
│   ├── <(a, b)
│   └── >(c, d)
└── ==(e, f)

こう解釈する必要があります。

ASTを設計する

式（Expression）

/// 式
#[derive(Debug, Clone)]
pub enum Expr {
    /// 数値リテラル: 42
    Number(i64),
    
    /// ブール値: true, false
    Bool(bool),
    
    /// 変数参照: x
    Var(String),
    
    /// 二項演算: a + b
    BinOp {
        op: BinOp,
        left: Box<Expr>,
        right: Box<Expr>,
    },
    
    /// 単項演算: -x, !flag
    UnaryOp {
        op: UnaryOp,
        expr: Box<Expr>,
    },
    
    /// 関数呼び出し: add(1, 2)
    Call {
        name: String,
        args: Vec<Expr>,
    },
}

Box<Expr>を使っているのは、再帰的なデータ構造だから。

文（Statement）

/// 文
#[derive(Debug, Clone)]
pub enum Stmt {
    /// 変数宣言: let x = 10;
    Let { name: String, value: Expr },
    
    /// 代入: x = 20;
    Assign { name: String, value: Expr },
    
    /// return文: return x + 1;
    Return(Option<Expr>),
    
    /// if文
    If {
        cond: Expr,
        then_body: Vec<Stmt>,
        else_body: Option<Vec<Stmt>>,
    },
    
    /// while文
    While {
        cond: Expr,
        body: Vec<Stmt>,
    },
}

関数とプログラム

/// 関数定義
#[derive(Debug, Clone)]
pub struct Function {
    pub name: String,
    pub params: Vec<String>,
    pub body: Vec<Stmt>,
}

/// プログラム全体
#[derive(Debug)]
pub struct Program {
    pub functions: Vec<Function>,
}

Parserを実装する

基本構造

pub struct Parser {
    tokens: Vec<Token>,
    pos: usize,
}

impl Parser {
    /// 現在のトークン
    fn current(&self) -> &Token { ... }
    
    /// 1トークン進める
    fn advance(&mut self) { ... }
    
    /// 期待するトークンを消費
    fn expect(&mut self, expected: TokenKind) -> Result<(), String> { ... }
}

演算子優先順位パーサー（Pratt Parser）

優先順位を扱うために、優先順位ごとに関数を分ける方法を使います：

// 優先順位：低 → 高
parse_expr()           // エントリポイント
  → parse_or()         // ||
    → parse_and()      // &&
      → parse_equality()   // == !=
        → parse_comparison()   // < > <= >=
          → parse_additive()   // + -
            → parse_multiplicative()   // * / %
              → parse_unary()    // - !
                → parse_primary()    // 数値、変数、括弧

低い優先順位ほど木の上に来ます。

加算・減算のパース

/// + - をパース
fn parse_additive(&mut self) -> Result<Expr, String> {
    // まず左辺（より優先順位の高いもの）をパース
    let mut left = self.parse_multiplicative()?;
    
    // + か - が続く限りループ
    loop {
        let op = match self.current_kind() {
            TokenKind::Plus => BinOp::Add,
            TokenKind::Minus => BinOp::Sub,
            _ => break,  // それ以外なら終了
        };
        self.advance();
        
        // 右辺をパース
        let right = self.parse_multiplicative()?;
        
        // 新しいノードを作成
        left = Expr::BinOp {
            op,
            left: Box::new(left),
            right: Box::new(right),
        };
    }
    
    Ok(left)
}

乗算・除算のパース

/// * / % をパース
fn parse_multiplicative(&mut self) -> Result<Expr, String> {
    let mut left = self.parse_unary()?;
    
    loop {
        let op = match self.current_kind() {
            TokenKind::Star => BinOp::Mul,
            TokenKind::Slash => BinOp::Div,
            TokenKind::Percent => BinOp::Mod,
            _ => break,
        };
        self.advance();
        
        let right = self.parse_unary()?;
        left = Expr::BinOp {
            op,
            left: Box::new(left),
            right: Box::new(right),
        };
    }
    
    Ok(left)
}

parse_multiplicative()がparse_additive()から呼ばれることで、
*が+より優先されます！

基本式のパース

fn parse_primary(&mut self) -> Result<Expr, String> {
    match self.current_kind().clone() {
        // 数値
        TokenKind::Number(n) => {
            self.advance();
            Ok(Expr::Number(n))
        }
        
        // 識別子（変数 or 関数呼び出し）
        TokenKind::Ident(name) => {
            self.advance();
            
            if self.match_token(TokenKind::LParen) {
                // 関数呼び出し
                let args = self.parse_args()?;
                self.expect(TokenKind::RParen)?;
                Ok(Expr::Call { name, args })
            } else {
                // 変数参照
                Ok(Expr::Var(name))
            }
        }
        
        // 括弧
        TokenKind::LParen => {
            self.advance();
            let expr = self.parse_expr()?;
            self.expect(TokenKind::RParen)?;
            Ok(expr)
        }
        
        _ => Err("Unexpected token".to_string()),
    }
}

文のパース

fn parse_stmt(&mut self) -> Result<Stmt, String> {
    match self.current_kind() {
        TokenKind::Let => self.parse_let(),
        TokenKind::Return => self.parse_return(),
        TokenKind::If => self.parse_if(),
        TokenKind::While => self.parse_while(),
        _ => Err("Unexpected statement".to_string()),
    }
}

fn parse_let(&mut self) -> Result<Stmt, String> {
    self.expect(TokenKind::Let)?;
    
    // 変数名
    let name = match self.current_kind().clone() {
        TokenKind::Ident(n) => { self.advance(); n }
        _ => return Err("Expected variable name".to_string()),
    };
    
    // =
    self.expect(TokenKind::Eq)?;
    
    // 値
    let value = self.parse_expr()?;
    
    // ;
    self.expect(TokenKind::Semicolon)?;
    
    Ok(Stmt::Let { name, value })
}

動かしてみる

サンプル：FizzBuzz

fn fizzbuzz(n) {
    if n % 15 == 0 {
        return 3;  // FizzBuzz
    } else {
        if n % 3 == 0 {
            return 1;  // Fizz
        } else {
            if n % 5 == 0 {
                return 2;  // Buzz
            } else {
                return 0;  // 数字
            }
        }
    }
}

fn main() {
    let i = 1;
    while i <= 20 {
        let result = fizzbuzz(i);
        i = i + 1;
    }
    return 0;
}

パース結果のAST

=== AST ===
Function: fizzbuzz
  params: ["n"]
  body:
    If:
      cond:
        BinOp(Eq)
          BinOp(Mod)
            Var(n)
            Number(15)
          Number(0)
      then:
        Return:
          Number(3)
      else:
        If:
          cond:
            BinOp(Eq)
              BinOp(Mod)
                Var(n)
                Number(3)
              Number(0)
          ...

n % 15 == 0 が正しく (n % 15) == 0 と解釈されています！

演算子優先順位のデモ

let x = 1 + 2 * 3 - 4 / 2;

AST:

Let x =
  BinOp(Sub)
    BinOp(Add)
      Number(1)
      BinOp(Mul)
        Number(2)
        Number(3)
    BinOp(Div)
      Number(4)
      Number(2)

計算順序：

2 * 3 = 6
4 / 2 = 2
1 + 6 = 7
7 - 2 = 5

完璧！

テスト

#[test]
fn test_binary_op() {
    let program = Parser::parse_source("fn main() { let x = 1 + 2 * 3; }").unwrap();
    
    if let Stmt::Let { value, .. } = &program.functions[0].body[0] {
        // 1 + (2 * 3) という構造になっているはず
        if let Expr::BinOp { op, left, right } = value {
            assert_eq!(*op, BinOp::Add);
            assert!(matches!(left.as_ref(), Expr::Number(1)));
            
            // 右側は Mul(2, 3)
            if let Expr::BinOp { op: inner_op, .. } = right.as_ref() {
                assert_eq!(*inner_op, BinOp::Mul);
            }
        }
    }
}

テスト実行：

cargo test

running 11 tests
test lexer::tests::test_arrow ... ok
test lexer::tests::test_comment ... ok
test parser::tests::test_binary_op ... ok
test parser::tests::test_function_call ... ok
test parser::tests::test_if_else ... ok
test parser::tests::test_simple_let ... ok
...

test result: ok. 11 passed; 0 failed

まとめ

今回やったこと

項目	内容
AST設計	Expr, Stmt, Function, Program
Parser実装	約400行
演算子優先順位	再帰下降パーサーで実現

学び

ASTは木構造
- 演算の順序が深さで表現される
優先順位は関数の呼び出し順で決まる
- 低い優先順位 → 高い優先順位の順に呼ぶ
RustのBox<T>
- 再帰的なデータ構造に必須

次回予告

Part3では 意味解析（Semantic Analysis） を実装します！

変数のスコープ管理
型チェック（簡易版）
未定義変数の検出

fn main() {
    let x = 10;
    return y;  // エラー: yは未定義！
}

こういうエラーを検出できるようになります。お楽しみに！