サンプルコードで身につける: 構文解析と AST — 生成規則 1 つが関数 1 つ(再帰下降)

// 再帰下降(recursive descent): 文法の生成規則 1 つを関数 1 つに写す。
// AdditiveExpression は「左結合」なので、左再帰をループに書き換える。10 - 2 - 3 は (10 - 2) - 3 = 5 になる。
#[derive(Debug, Clone, PartialEq)]
enum Token { Number(f64), Punctuator(char) }

enum Node {
    NumericLiteral(f64),
    BinaryExpression { operator: char, left: Box<Node>, right: Box<Node> },
}

impl Node {
    fn dump(&self, depth: usize) {
        match self {
            Node::NumericLiteral(v) => println!("{}NumericLiteral {}", "  ".repeat(depth), v),
            Node::BinaryExpression { operator, left, right } => {
                println!("{}BinaryExpression {}", "  ".repeat(depth), operator);
                left.dump(depth + 1);
                right.dump(depth + 1);
            }
        }
    }

    fn eval(&self) -> f64 {
        match self {
            Node::NumericLiteral(v) => *v,
            Node::BinaryExpression { operator: '+', left, right } => left.eval() + right.eval(),
            Node::BinaryExpression { left, right, .. } => left.eval() - right.eval(),
        }
    }
}

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

impl JsParser {
    fn is_punct(&self, c: char) -> bool {
        self.tokens.get(self.pos) == Some(&Token::Punctuator(c))
    }

    // AdditiveExpression : AdditiveExpression + PrimaryExpression | AdditiveExpression - PrimaryExpression | PrimaryExpression
    // 左再帰はそのまま関数にすると無限再帰になるので、「左を 1 つ読み、演算子が続く限り右を読んで包む」ループにする
    fn parse_additive_expression(&mut self) -> Node {
        let mut left = self.parse_primary_expression();
        while self.is_punct('+') || self.is_punct('-') {
            let operator = match &self.tokens[self.pos] { Token::Punctuator(c) => *c, _ => unreachable!() };
            self.pos += 1;
            let right = self.parse_primary_expression();
            left = Node::BinaryExpression { operator, left: Box::new(left), right: Box::new(right) }; // これまでの左を包む
        }
        left
    }

    // PrimaryExpression : NumericLiteral
    fn parse_primary_expression(&mut self) -> Node {
        let t = self.tokens[self.pos].clone();
        self.pos += 1;
        match t {
            Token::Number(n) => Node::NumericLiteral(n),
            other => panic!("数値を期待しましたが {:?} が来ました", other),
        }
    }
}

fn main() {
    // 字句解析の結果 "10 - 2 - 3" を手で与える
    let tokens = vec![Token::Number(10.0), Token::Punctuator('-'), Token::Number(2.0), Token::Punctuator('-'), Token::Number(3.0)];
    let mut parser = JsParser { tokens, pos: 0 };
    let ast = parser.parse_additive_expression();
    ast.dump(0);
    println!("評価 = {}(右結合なら 10 - (2 - 3) = 11 になってしまう)", ast.eval());
}

// AssignmentExpression は「右結合」なので右側を自分自身の再帰で読む(a = b = c は a = (b = c))。MemberExpression(.)と
// CallExpression(( ))は PrimaryExpression の後ろに何個でも続くので、ループで外側に包む。期待と違うトークンが来たら None で抜ける。
#[derive(Clone, PartialEq)]
enum Token { Punctuator(char), Identifier(String) }

enum Node {
    AssignmentExpression { target: Box<Node>, value: Box<Node> },
    MemberExpression { object: Box<Node>, property: String },
    CallExpression { callee: Box<Node>, arguments: Vec<Node> },
    Identifier(String),
}

impl Node {
    /// 木を 1 行で表す。括弧の付き方で結合の向きが見える
    fn show(&self) -> String {
        match self {
            Node::AssignmentExpression { target, value } => format!("Assign({} = {})", target.show(), value.show()),
            Node::MemberExpression { object, property } => format!("Member({}.{})", object.show(), property),
            Node::CallExpression { callee, arguments } => format!("Call({}({}))", callee.show(), arguments.iter().map(|a| a.show()).collect::<Vec<_>>().join(", ")),
            Node::Identifier(name) => name.clone(),
        }
    }
}
struct JsParser { tokens: Vec<Token>, pos: usize }

impl JsParser {
    fn is_punct(&self, c: char) -> bool {
        self.tokens.get(self.pos) == Some(&Token::Punctuator(c))
    }
    fn next(&mut self) -> Option<Token> {
        self.pos += 1;
        self.tokens.get(self.pos - 1).cloned() // 入力の終わりなら None
    }
    // AssignmentExpression : LeftHandSideExpression = AssignmentExpression | LeftHandSideExpression
    fn parse_assignment_expression(&mut self) -> Option<Node> {
        let left = self.parse_left_hand_side_expression()?;
        if self.is_punct('=') {
            self.pos += 1;
            let value = self.parse_assignment_expression()?; // 右結合: 右側は自分自身
            return Some(Node::AssignmentExpression { target: Box::new(left), value: Box::new(value) });
        }
        Some(left)
    }
    // LeftHandSideExpression : PrimaryExpression ( . IdentifierName | ( Arguments ) )*
    fn parse_left_hand_side_expression(&mut self) -> Option<Node> {
        let mut expr = match self.next()? {
            Token::Identifier(name) => Node::Identifier(name),
            Token::Punctuator(_) => return None, // 式の先頭に記号は来ない(参照実装はここで ParseError を返す)
        };
        loop {
            if self.is_punct('.') {
                self.pos += 1;
                let property = match self.next()? {
                    Token::Identifier(name) => name,
                    _ => return None, // . の後ろは識別子
                };
                expr = Node::MemberExpression { object: Box::new(expr), property }; // これまでの expr を包む
            } else if self.is_punct('(') {
                self.pos += 1;
                let mut arguments = Vec::new();
                if !self.is_punct(')') {
                    arguments.push(self.parse_assignment_expression()?); // 引数 1 個まで(本物は , で繰り返す)
                }
                if self.next()? != Token::Punctuator(')') {
                    return None;
                }
                expr = Node::CallExpression { callee: Box::new(expr), arguments };
            } else {
                return Some(expr);
            }
        }
    }
}
fn id(s: &str) -> Token { Token::Identifier(s.to_string()) }
fn p(c: char) -> Token { Token::Punctuator(c) }
fn main() {
    let programs = vec![ // 字句解析の結果を手で与える
        ("a = b = c", vec![id("a"), p('='), id("b"), p('='), id("c")]),
        ("document.getElementById(t).textContent = x",
         vec![id("document"), p('.'), id("getElementById"), p('('), id("t"), p(')'), p('.'), id("textContent"), p('='), id("x")]),
        ("f(", vec![id("f"), p('(')]),
    ];
    for (src, tokens) in programs {
        match (JsParser { tokens, pos: 0 }).parse_assignment_expression() {
            Some(ast) => println!("{:<44} -> {}", src, ast.show()),
            None => println!("{:<44} -> SyntaxError", src),
        }
    }
}

// 実務に写す: 料金の計算式を設定ファイルから読んで評価する電卓。
// 生成規則を Additive → Multiplicative → Primary の 3 段にするだけで、* / が + - より先に計算される(優先順位は文法の段で表す)。
// ここでは AST を作らず、読みながら計算する(構造は同じ: 規則 1 つ = 関数 1 つ、左結合はループ)。
use std::collections::HashMap;

struct Calc<'a> { chars: Vec<char>, pos: usize, vars: &'a HashMap<&'a str, f64> }

impl<'a> Calc<'a> {
    fn peek(&mut self) -> Option<char> {
        while self.chars.get(self.pos).map_or(false, |c| c.is_whitespace()) {
            self.pos += 1; // 空白を飛ばす(字句解析を兼ねる)
        }
        self.chars.get(self.pos).copied()
    }

    // Additive : Multiplicative (('+' | '-') Multiplicative)*
    fn parse_additive(&mut self) -> Result<f64, String> {
        let mut left = self.parse_multiplicative()?;
        while let Some(op) = self.peek().filter(|c| *c == '+' || *c == '-') {
            self.pos += 1;
            let right = self.parse_multiplicative()?;
            left = if op == '+' { left + right } else { left - right };
        }
        Ok(left)
    }

    // Multiplicative : Primary (('*' | '/') Primary)*     ← この段があるから * / が先に結合する
    fn parse_multiplicative(&mut self) -> Result<f64, String> {
        let mut left = self.parse_primary()?;
        while let Some(op) = self.peek().filter(|c| *c == '*' || *c == '/') {
            self.pos += 1;
            let right = self.parse_primary()?;
            left = if op == '*' { left * right } else { left / right };
        }
        Ok(left)
    }

    // Primary : Number | Identifier | '(' Additive ')'
    fn parse_primary(&mut self) -> Result<f64, String> {
        match self.peek() {
            Some('(') => {
                self.pos += 1;
                let v = self.parse_additive()?;
                if self.peek() != Some(')') {
                    return Err("')' を期待しましたが入力が終わりました".to_string());
                }
                self.pos += 1;
                Ok(v)
            }
            Some(c) if c.is_ascii_digit() => Ok(self.take(|c| c.is_ascii_digit() || c == '.').parse().unwrap_or(0.0)),
            Some(c) if c.is_ascii_alphabetic() => {
                let name = self.take(|c| c.is_ascii_alphanumeric() || c == '_');
                self.vars.get(name.as_str()).copied().ok_or(format!("変数 {} が未定義です", name))
            }
            Some(c) => Err(format!("式を期待しましたが '{}' が来ました", c)),
            None => Err("式を期待しましたが入力が終わりました".to_string()),
        }
    }

    fn take(&mut self, cond: fn(char) -> bool) -> String {
        let start = self.pos;
        while self.chars.get(self.pos).map_or(false, |c| cond(*c)) {
            self.pos += 1;
        }
        self.chars[start..self.pos].iter().collect()
    }
}

fn evaluate(src: &str, vars: &HashMap<&str, f64>) -> Result<f64, String> {
    let mut calc = Calc { chars: src.chars().collect(), pos: 0, vars };
    let v = calc.parse_additive()?;
    match calc.peek() {
        None => Ok(v),
        Some(c) => Err(format!("式の後ろに '{}' が余っています", c)),
    }
}

fn main() {
    let vars: HashMap<&str, f64> = [("price", 1200.0), ("qty", 3.0), ("tax_rate", 0.1), ("shipping", 500.0)].iter().cloned().collect();
    let formulas = ["price * qty + price * qty * tax_rate", "(price + shipping) * qty", "price * (qty", "price * qty )"];
    for f in formulas.iter() {
        match evaluate(f, &vars) {
            Ok(v) => println!("{:<40} = {}", f, v),
            Err(e) => println!("{:<40} -> SyntaxError: {}", f, e),
        }
    }
}