Go to Qiita Advent Calendar Top
LoginSignup
4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

Day 6

あくあ Advent Calendar 2025

@Aqua-218(Aqua)inデジタル創作サークルUniProject

ASTって何？木構造で式を理解する Part2

Last updated at Posted at 2025-12-09

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）**に変換して、演算の順序を明確にします。

目次

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

ASTとは

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

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

例

1 + 2 * 3

これのASTは：

    Add
   /   \
  1    Mul
      /   \
     2     3

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

  1. Mul(2, 3) = 6
  2. 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)

計算順序：

  1. 2 * 3 = 6
  2. 4 / 2 = 2
  3. 1 + 6 = 7
  4. 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行
演算子優先順位 再帰下降パーサーで実現

学び

  1. ASTは木構造

    • 演算の順序が深さで表現される

  2. 優先順位は関数の呼び出し順で決まる

    • 低い優先順位 → 高い優先順位の順に呼ぶ

  3. RustのBox<T>

    • 再帰的なデータ構造に必須

次回予告

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

  • 変数のスコープ管理
  • 型チェック（簡易版）
  • 未定義変数の検出
fn main() {
    let x = 10;
    return y;  // エラー: yは未定義！
}

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

4
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?