Rust で仮想言語のインタプリタを作る

概要

Rust を使って自分で定義した仮想言語のインタプリタを作っているので,
途中経過として, 四則演算, 関数の定義と呼び出しを処理の方法をまとめます.

C++ は普段から触っているけど, Rust を始めて触るので簡単そうな?インタプリタを作って見ました.

作ったコードはこちら
https://github.com/nagato0614/NagatoInterpreter

仮想言語の概要

対応しているのは

• 四則演算とmod
  • +, -, *, /, %
• 比較演算
  • ==, !=, <, <=, >, >=
• 変数への代入
  • =
• 関数
  • func
• return
  です.

取り扱える型は整数と浮動小数点数の２つで,
整数と浮動小数点数を組み合わせて計算した場合は浮動小数点数へ型変換されます.
比較演算を行い, 真の場合は1, 偽の場合は0の整数型を返します.

仮想言語の例

# 四則演算
a = 5 + 3 * 2;      # a = 11
b = (4 + 6) / 2;    # b = 5
c = 5.5 + 2.5;      # c = 8.0
d = 10 % 3;         # d = 1

# 比較演算
e = 10 > 5;         # e = 1 (true)
f = 10.0 <= 10.0;   # f = 1 (true)
g = 3 != 3;         # g = 0 (false)

# 変数代入と更新
h = a + b;          # h = 16
a = 100;            # a = 100 (上書き)

# 関数定義と呼び出し
func add(x, y) {
    a = x + y;
    return a;
}
i = add(1, 2);      # i = 3

# 関数の引数に変数を使用
j = add(a, h);      # j = 100 + 16 = 116

# 最後に評価した値を取得
return j;

BNFは以下のようになってます.
変数と関数が同じ Identifier として扱っており文脈で判断するようにしています.

  Statement ::= Equation | Function
  Equation ::= Identifier ';' | Assignment ';' | ReturnStatement ';'
  Assignment ::= Identifier '=' ArithmeticEquation
               | Identifier '=' Comparison
               
  Comparison ::= ArithmeticEquation ComparisonOperator ArithmeticEquation
 
  Function ::= "func" Identifier '(' Arguments ')' Block
  Block ::= '{' (Assignment ';')* ReturnStatement ';'}'
  Statement ::= Identifier ';' | Assignment ';'
  FunctionCall ::= Identifier '(' CallArgument ')'
  Arguments ::= [Variable] (',' [Variable])*
　CallArguments ::= [CallArgument] (',' [CallArgument])*
  ReturnStatement ::= "return" Value  | "return" Identifier
  
  ArithmeticEquation ::= Term | Term ArithmeticOperandHead Term
  Term ::= Factor | Factor ArithmeticOperandTail Factor
  Factor ::= Value | Identifier | '(' ArithmeticEquation ')' | FunctionCall
  ArithmeticOperandHead ::= + | -
  ArithmeticOperandTail ::= * | / | %  
  ArithmeticOperandParen ::= ( | )
  ComparisonOperator ::= < | > | == | <= | >= | !=
  BlockParen ::= { | }
  Identifier ::= (a-z)+
  Value ::= Integer | Float
  Integer ::= [0-9]+
  Float ::= [0-9]+ '.' [0-9]+

Statement

Statement ::= Equation | Function

すべての文は式(Equation) または, Function(関数)に分類されます.

Equation

Equation ::= Identifier ';' | Assignment ';' | ReturnStatement ';'

すべての式はセミコロンで終わるようになっており Identifier (識別子), Assignment (代入式), ReturnStatement (Return文) の3種類が含まれる.
Identifier 一つだけ記述した場合は標準出力に変数の値が出力されます.
ReturnStatement が実行された場合はそこでプログラムの処理が終了します.

Assignment

Assignment ::= Identifier '=' ArithmeticEquation
             | Identifier '=' Comparison
Comparison ::= ArithmeticEquation ComparisonOperator ArithmeticEquation

計算を行う場合は必ず Assignment (代入式) として取り扱います.
演算子の優先順位の関係で ArithmeticEquation (算術式) と Comparison (比較式)が同列になるように取り扱っています.
比較式内で ArithmeticEquation を評価しているので比較式ないでも演算が可能です.

演算子の優先順位

1. 比較演算
2. *, /, %
3. +, -

ArithmeticEquation

  ArithmeticEquation ::= Term | Term ArithmeticOperandHead Term
  Term ::= Factor | Factor ArithmeticOperandTail Factor
  Factor ::= Value | Identifier | '(' ArithmeticEquation ')' | FunctionCall
  ArithmeticOperandHead ::= + | -
  ArithmeticOperandTail ::= * | / | %  
  ArithmeticOperandParen ::= ( | )
  ComparisonOperator ::= < | > | == | <= | >= | !=
  Identifier ::= (a-z)+
  Value ::= Integer | Float
  Integer ::= [0-9]+
  Float ::= [0-9]+ '.' [0-9]+

算術式には主に Term (項), Factor (因子) が含まれています.
Factor が一番細かい要素で, Value (値), Identifier, (), FunctionCall (関数呼び出し)に対応しています.
()内では ArithmeticEquation が定義可能で再帰的に式を評価します.
Term では Factor と ArithmeticOperandTail を評価します.これによって優先度の高い演算子が先に処理されたあと ArithmeticEquation 内で優先度の低い演算子が評価されるようになっています.
変数は Identifier として評価され今のところ英字のみ取り扱います.
Value は Integer(整数) | Float(小数)の二種類のみです

Function

  Function ::= "func" Identifier '(' Arguments ')' Block
  Block ::= '{' (Equation ';')* ReturnStatement ';'}'
  Statement ::= Identifier ';' | Assignment ';'
  FunctionCall ::= Identifier '(' CallArgument ')'
  Arguments ::= [Identifier] (',' [Identifier])*
　CallArguments ::= [CallArgument] (',' [CallArgument])*
  ReturnStatement ::= "return" Value  | "return" Identifier

関数は先頭に func をつけ関数名を定義する必要があります.
定義のときには引数として Arguments が適用されます.
一つ以上の Identifier を定義します.
0個の場合は考慮できていません.
関数内部の処理 Block は {} で囲って処理を記述します.
Block 内部には一つ以上の式を記述する必要がありますが, 最後は必ず ReturnStatement を記述します.
BNF の書き方がわかっていないので Equation 内に ReturnStatement が含まれているため要素が重複していますが, 実装としては ReturnStatement を評価した時点で処理が終了します.

関数定義の例

func add(a, b) {
    c = a + b;
    return c;
}

関数呼び出しは引数にValueまたはIdentifier を渡して計算を行います.

関数呼び出し

a = add(1, 1)
b = add(1, 1)
c = add(a, b)

実装

実装は BNFで定義した項を一つの関数として実装する形にしています.

処理の流れ

1. ファイルを開いてテキストを読み取る
2. ソースコードをパースして Token 列に置き換える.
3. Token列を評価して計算を行う

式が二行に分かれた場合はうまく処理できないため, 一つの行に一つの式を記述する必要がある.
ここでは一部の処理について紹介します.

Factor

プログラムの例として Factor 部分を処理する関数を見ていくと
トークン列を受け取って, Value, Identifier, OperatorParenかを識別して処理していく.
Valueの場合はそのまま値を返却するが, Identifier の場合は関数なのか変数なのかを識別して関数の場合は関数呼び出しを行い変数の場合は変数の値を返却する.
Rust は Enum に紐づけて異なる型の値を紐づけできるため使い方がわかってくると便利だった.
(を見つけた場合は更に ArithmeticEquationを処理する関数を呼び出し再帰的に処理をする.

Factor

 fn factor(&mut self, tokens: &mut Vec<Token>) -> Value
    {
        let token = tokens.pop().unwrap();
        match token
        {
            Token::Value(val) => val,
            Token::Identifier(var) =>
                {
                    if let Some(val) = self.identifiers.get(&var)
                    {
                        match val
                        {
                            Identifier::Variable(val) => val.clone(),
                            Identifier::Function(func) => {
                                // 関数を実行して結果を返す
                                self.function_call(func.clone(), tokens)
                            }
                        }
                    } else {
                        panic!("変数がありません : {}", var);
                    }
                }
            Token::OperatorParen(ArithmeticOperandParen::Left) =>
                {
                    let result = self.arithmetic_equation(tokens);
                    if let Some(T) = tokens.pop() // get next token
                    {
                        match T
                        {
                            Token::OperatorParen(ArithmeticOperandParen::Right) => {
                                result
                            }
                            _ =>
                                {
                                    panic!("括弧が閉じられていません : {}", T);
                                }
                        }
                    } else {
                        panic!("括弧が閉じられていません : {}", token);
                    }
                }
            Token::OperatorParen(ArithmeticOperandParen::Right) =>
                {
                    panic!("括弧が閉じられていません : {}", token);
                }
            _ =>
                {
                    panic!("数値でも変数でもありません : {}", token);
                }
        }
    }

FunctionCall

関数呼び出しの処理は特殊で内部で関数を処理する Interpreter を作成し実行する.
そのため関数外の変数にはアクセスせずに処理をすることができる.
引数の値はあらかじめインタプリタに登録しておき, それをもとに処理を開始する.

FunctionCall

  fn function_call(&mut self, mut function: Function, token: &mut Vec<Token>) -> Value
    {
        let mut arguments = Vec::new();
        // ) が見つかるまで Token を除去
        while let Some(t) = token.pop()
        {
            match t
            {
                Token::OperatorParen(ArithmeticOperandParen::Right) => break,
                Token::COMMA => {}
                Token::Value(val) => arguments.push(val),
                Token::Identifier(var) =>
                    {
                        if let Some(val) = self.identifiers.get(&var)
                        {
                            match val
                            {
                                Identifier::Variable(val) => arguments.push(val.clone()),
                                _ => panic!("関数の引数に関数を使用することはできません : {:?}", val),
                            }
                        } else {
                            panic!("変数がありません : {}", var);
                        }
                    }
                _ => {}
            }
        }

        // 関数を実行
        function.run(arguments)
    }

最後に

C++を触っているのですぐに行けると思ったけど, Rust の非常に強い型付けにだいぶ苦戦した.
型付けに苦戦したというよりは, 可変, 不可変の取り扱いが大変だった.
今後は, 関数をより使いやすくしたり, if文, while文の実装をしたり, 配列型を取り扱えるようにしていきたい.

参考

https://qiita.com/h_sakurai/items/3cc328a6db8941ac6336

https://qiita.com/kazuki_tamaribuchi/items/77a4b4e6214646a079ed

https://ja.wikipedia.org/wiki/構文解析器