タスク概要

構文解析で得られた Abstract Syntax Tree(AST) のインタプリタを作る。

入力は Compiler/Syntax Analyzer での出力形式に基づいたテキスト。

f:id:mtXTJocj:20190623232628p:plain

実装

基本的には AST をトラバースしながら各ノードを評価していく。評価することで得られる値は

String
Integer
なし

の 3 種類がある。なので、return value 用に

pub enum Value<'a> {
    Integer(i32),
    String(&'a str),
}

という enum を用意した。String の値は AST が所有しているため、reference を用いる。また、これだけだと return value なしの場合が扱えないため、Option にする。

    pub fn interpret(node: &'a ASTNode, writer: &mut Write) -> Result<Option<Value<'a>>>

enum Value に None を加えても良かったかもしれない。

変数

インタプリタに変数名と値をむすびつけるための HashMap を用意する。今回実装している言語はグローバル変数しか持たないため、これだけで ok。

pub struct ASTInterpreter<'a> {
    global: HashMap<&'a str, Value<'a>>,
}

リーフの評価

AST のリーフ(葉) になるのは終端記号である String, Identifier, Integer。String と Integer はそのままの値が評価結果になる。

            NodeKind::String(value) => Ok(Some(Value::String(value))),
            NodeKind::Integer(value) => Ok(Some(Value::Integer(*value))),

一方で Identifier は変数へのアクセスになるため、前述の HashMap へのアクセスを行う。

    fn interpret_identifier(&mut self, identifier: &'a str) -> Result<Option<Value<'a>>> {
        Ok(Some(self.global[identifier]))
    }

なお、変数への代入では左辺の Identifier を評価しないことに注意。

中間ノードの評価

2 項演算

add や equal などが該当する。処理は非常に単純で、両辺を評価してから対応する演算を適用するだけ。ソース内では interpret_binary_op() で行っている。

ところで、2 項演算の中には equal 等の関係演算が含まれる。一方で今回実装している言語に boolean を直接表すデータ型というものは存在しない。rosetta code のサイトではちゃんとした言語の仕様が見つからず、代わりに "C 言語と Python による実装を参照実装として考えていいよ"。とある。それによると、C 言語同様 0 を false とし、それ以外を true と見なすようだ。
よって false 時には 0 を true 時には 1 を評価結果とした。

単項演算

2 項演算とほとんど変わらない。違いは子ノードが片方しかない点のみ。interpret_unary_op() を参照。

代入

Identifier の評価のところでも書いたけれど、代入先になる左辺の Identifier は評価せず、右辺のみを評価し、評価結果を global の HashMap に Identifer 名をキーとして記憶させる。

    fn interpret_assign(
        &mut self,
        node: &'a ASTNode,
        writer: &mut Write,
    ) -> Result<Option<Value<'a>>> {
        let variable = node.lhs().unwrap();
        let value = self.interpret_body(node.rhs().unwrap(), writer)?.unwrap();

        match variable.kind() {
            NodeKind::Identifier(ref identifier) => {
                self.global.insert(identifier, value);
                Ok(None)
            }
            _ => Err(CompileError::new(
                ErrorKind::InterpretationError,
                "Identifier is expected.",
            )),
        }
    }

if

条件文にあたる paren_expr を評価し、その結果により実行対象が変わる。else 節は存在しない場合もある。

    fn interpret_if(&mut self, node: &'a ASTNode, writer: &mut Write) -> Result<Option<Value<'a>>> {
        let condition = self.interpret_body(node.lhs().unwrap(), writer)?.unwrap();
        let statement_node = node.rhs().unwrap();

        if condition != Value::Integer(0) {
            self.interpret_body(statement_node.lhs().unwrap(), writer)?;
        } else {
            if let Some(else_clause) = statement_node.rhs() {
                self.interpret_body(else_clause, writer)?;
            }
        }

        Ok(None)
    }

while

条件の評価と本体の評価を繰り返す。条件の評価結果が 0 になったらループ終了。

    fn interpret_while(
        &mut self,
        node: &'a ASTNode,
        writer: &mut Write,
    ) -> Result<Option<Value<'a>>> {
        let condition = node.lhs().unwrap();
        let statement = node.rhs().unwrap();

        while self.interpret_body(condition, writer)? != Some(Value::Integer(0)) {
            self.interpret_body(statement, writer)?;
        }
        Ok(None)
    }

その他

特に注意すべき点もないのでソースを見ればわかるはず。

余談

AST Interpreter というタスク名だったから interpret() という関数名にしたけど、個人的には eval の方がしっくりくる。

mtXTJocj’s blog

Compiler/AST Interpreter