Unityでのゲーム作り日記#4 ～自作言語の構文解析器を作る 前編～

前回の記事はこちら

今回は、ターコイズ言語の構文解析器を作っていきたいと思います。
構文解析系は結構作るのが大変なので二回に分けて書いていこうと思います。

あと、途中プログラムで高階関数を作るためのコードがありますが、やっぱりゲーム性的に言語の不便さを出したいので、高階関数は実装しません。（本当は実装するの大変すぎて萎えただけだけどね...）
もしバグが見つかったら修正します。

実際に作っていく

構文解析器とは、例えば字句解析器によって分解された 3, +, 5, *, x というトークンを、次のような構文木に変換するものです。

まず、値を表すクラスを書いていきます。

TurquoiseValue.cs

using System.Collections;
using System.Collections.Generic;
using System.Reflection;
using UnityEngine;

namespace TurquoiseValue
{
   public interface Value //インターフェイス
   {
       object get(); //object型で取得

       double getDouble(); //ダブル型で取得

       string getFunctionName(); //名前として取得（高階関数用）
   }

   public class DoubleValue : Value //ダブル型を表す
   {
       object value;

       public DoubleValue(double value)
       {
           this.value = value;
       }

       public object get()
       {
           return value;
       }

       public double getDouble()
       {
           return (double)value;
       }

       public string getFunctionName()
       {
           throw new GarnetException($"{(double)value} is not a function name."); //名前はないのでエラー
       }
   }

   public class FunctionValue : Value
   {
       object value;

       public FunctionValue(string value) //高階関数を表す
       {
           this.value = value;
       }

       public object get()
       {
           return value;
       }

       public double getDouble() //ダブル型ではないのでエラー
       {
           throw new GarnetException($"{value.ToString()} is not a number.");
       }

       public string getFunctionName()
       {
           return value.ToString();
       }
   }

   static class ValueConvert //名前が合ってないかも...
   {
       static public Value createValue(double v) //ダブル型を表す値を作る
       {
           return new DoubleValue(v);
       }

       static public Value createValue(string v) //高階関数を表す値を作る
       {
           return new FunctionValue(v);
       }

       static public Value createValue(object v) //ダブル型か高階関数かわからない場合
       {
           double value;
           if (double.TryParse(v.ToString(), out value))
           {
               return new DoubleValue(value);
           }

           string valueS = v.ToString();
           return new FunctionValue(valueS);
       }
   }
}

次に、構文解析器で生成する構文木の要素（ノード）となるものを書いていきます。（図中の「演算子:+」や「数字:5」）
また、ついでに環境（変数の値を格納するもの）なども書いていきます。

TurquoiseAstNode.cs

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using TurquoiseValue;
using System;
using Unity.VisualScripting;

namespace TurquoiseAstNode
{
   public interface IExpression //インターフェイス
   {
       Value Evaluate(); //実行
       void printNode(); //デバッグ用の表示メソッド
       bool isFunctionCall(); //関数呼び出しかどうか
   }

   public class NumberExpression : IExpression //数字を表すノード
   {
       private Value _num;

       public NumberExpression(double num)
       {
           _num = new DoubleValue(num);
       }

       public Value Evaluate()
       {
           return (DoubleValue)_num;
       }

       public void printNode()
       {
           Debug.Log($"Num:{_num.getDouble()}");
       }

       public bool isFunctionCall()
       {
           return false;
       }
   }

   public class VariableExpression : IExpression //変数を表すノード
   {
       private string _identifier;

       public VariableExpression(string identifier)
       {
           _identifier = identifier;
       }

       public Value Evaluate()
       {
           Value value = Environments.getVarValue(_identifier);

           return value;
       }

       public void printNode()
       {
           Debug.Log($"Var:{_identifier}");
       }

       public bool isFunctionCall()
       {
           return false;
       }

       public string getName()
       {
           return _identifier;
       }
   }

   public class FunctionExpression : IExpression //関数の呼び出しを表すノード
   {
       private string _identifier;
       private ParameterExpression _parameter;

       public FunctionExpression(string identifier, ParameterExpression parameter)
       {
           _identifier = identifier;
           _parameter = parameter;
       }

       public Value Evaluate()
       {
           Environment argments = new Environment();
           ParameterExpression dummyArgments = Environments.getFuncNameAndValue(_identifier).function.getParameter();

           for (int i = 0; i < _parameter.Size(); i++)
           {
               VariableExpression dummyArgmentName = (VariableExpression)dummyArgments.Get(i);
               argments.addVarValue(dummyArgmentName.getName(), _parameter.Get(i).Evaluate()); //引数を環境に追加
           }

           Environments.push(argments);

           Value result = Environments.getFuncNameAndValue(_identifier).expression.Evaluate(); //結果を求める

           Environments.pop(); //引数の環境を削除

           return result;
       }

       public void printNode()
       {
           Debug.Log($"Func:{_identifier}");
       }

       public bool isFunctionCall()
       {
           return true;
       }

       public ParameterExpression getParameter()
       {
           return _parameter;
       }
   }

   public class BinOpExpression : IExpression //二項演算子のノード
   {
       private IExpression _left;
       private IExpression _right;
       private string _op;

       public BinOpExpression(IExpression left, IExpression right, string op)
       {
           _left = left;
           _right = right;
           _op = op;
       }

       public Value Evaluate()
       {
           switch (_op)
           {
               case "+":
                   return new DoubleValue(_left.Evaluate().getDouble() + _right.Evaluate().getDouble());
               case "-":
                   return new DoubleValue(_left.Evaluate().getDouble() - _right.Evaluate().getDouble());
               case "*":
                   return new DoubleValue(_left.Evaluate().getDouble() * _right.Evaluate().getDouble());
               case "/":
                   return new DoubleValue(_left.Evaluate().getDouble() / _right.Evaluate().getDouble());
               case "%":
                   return new DoubleValue(_left.Evaluate().getDouble() % _right.Evaluate().getDouble());
               case "^":
                   return new DoubleValue(Math.Pow(_left.Evaluate().getDouble(), _right.Evaluate().getDouble()));
               case "<":
                   return new DoubleValue(_left.Evaluate().getDouble() < _right.Evaluate().getDouble() ? 1.0 : 0.0);
               case ">":
                   return new DoubleValue(_left.Evaluate().getDouble() > _right.Evaluate().getDouble() ? 1.0 : 0.0);
               case "<=":
                   return new DoubleValue(_left.Evaluate().getDouble() <= _right.Evaluate().getDouble() ? 1.0 : 0.0);
               case ">=":
                   return new DoubleValue(_left.Evaluate().getDouble() >= _right.Evaluate().getDouble() ? 1.0 : 0.0);
               case "==":
                   return new DoubleValue(_left.Evaluate().getDouble() == _right.Evaluate().getDouble() ? 1.0 : 0.0);
               case "!=":
                   return new DoubleValue(_left.Evaluate().getDouble() != _right.Evaluate().getDouble() ? 1.0 : 0.0);
               default:
                   throw new GarnetException($"Binary operator \'{_op}\' is undefined.");
           }
       }

       public void printNode()
       {
           Debug.Log($"(BinOp:{_op} ");
           _left.printNode();
           _right.printNode();
           Debug.Log(")");
       }

       public bool isFunctionCall()
       {
           return _left.isFunctionCall() || _right.isFunctionCall();
       }
   }

   public class UnuOpExpression : IExpression //単項演算子のノード（現時点では "-" のみ）
   {
       private IExpression _factor;
       private string _op;

       public UnuOpExpression(IExpression factor, string op)
       {
           _factor = factor;
           _op = op;
       }

       public Value Evaluate()
       {
           switch (_op)
           {
               case "-":
                   return new DoubleValue(_factor.Evaluate().getDouble() * -1);
               default:
                   throw new GarnetException($"Unury operator \'{_op}\' is undefined.");
           }
       }

       public void printNode()
       {
           Debug.Log($"(UnuOp:{_op} ");
           _factor.printNode();
           Debug.Log(")");
       }

       public bool isFunctionCall()
       {
           return _factor.isFunctionCall();
       }
   }

   public class ParameterExpression : IExpression //パラメータのノード
   {
       private IExpression[] _expressions;

       public ParameterExpression()
       {
           _expressions = new IExpression[0];
       }

       public ParameterExpression(IExpression[] expressions)
       {
           _expressions = expressions;
       }

       public Value Evaluate() { return new DoubleValue(0); }

       public void printNode()
       {
           Debug.Log("(Param ");
           foreach (IExpression expression in _expressions)
           {
               expression.printNode();
           }
           Debug.Log(")");
       }

       public bool isFunctionCall()
       {
           return false;
       }

       public IExpression Get(int i)
       {
           return _expressions[i];
       }

       public int Size()
       {
           return _expressions.Length;
       }
   }

   public class AssignmentVarExpression : IExpression //変数定義のノード
   {
       private string _name;
       private IExpression _valueExpression;

       public AssignmentVarExpression(string name, IExpression valueExpression)
       {
           _name = name;
           _valueExpression = valueExpression;
       }

       public Value Evaluate()
       {
           Environment environment = Environments.peek();
           environment.addVarValue(_name, _valueExpression.Evaluate());
           Environments.pop();
           Environments.push(environment);

           return _valueExpression.Evaluate();
       }

       public void printNode()
       {
           Debug.Log($"Assignment {_name} {_valueExpression.Evaluate().getDouble()}");
       }

       public bool isFunctionCall()
       {
           return false;
       }
   }

   public class DefineFuncExpression : IExpression
   {
       private string _name;
       private FunctionsNameAndValue _nameAndValue;

       public DefineFuncExpression(string name, FunctionsNameAndValue nameAndValue)
       {
           _name = name;
           _nameAndValue = nameAndValue;
       }

       public Value Evaluate()
       {
           Environment environment = Environments.pop();
           environment.addFuncNameAndValue(_name, _nameAndValue);
           Environments.push(environment);

           return new DoubleValue(0);
       }

       public void printNode()
       {
           Debug.Log($"(DefFunc:{_name}) ");
       }

       public bool isFunctionCall()
       {
           return false;
       }
   }

   public class Statement : IExpression
   {
       private string[] _statementNames; //ifの場合は2つになることがある
       private IExpression[] _expressionAndBodys; //ifの場合はbodyが2つになることもある

       public Statement(string[] statementNames, IExpression[] expressionAndBodys)
       {
           _statementNames = statementNames;
           _expressionAndBodys = expressionAndBodys;
       }

       public Value Evaluate()
       {
           switch (_statementNames[0])
           {
               case "while":
                   IExpression expression = _expressionAndBodys[0];
                   IExpression body = _expressionAndBodys[1];

                   while(expression.Evaluate().getDouble() != 0)
                   {
                       body.Evaluate();
                   }

                   return null;

               default:
                   throw new TurquoiseException($"{_statementNames[0]} is not define statement.");
           }
       }

       public void printNode()
       {
           Debug.Log($"(Statement:{_statementNames})");
       }

       public bool isFunctionCall()
       {
           return false;
       }
   }

   public class BlockExpression : IExpression
   {
       private IExpression[] _expressions;

       public BlockExpression(IExpression[] expressions)
       {
           _expressions = expressions;
       }

       public Value Evaluate()
       {
           object result = null;
           foreach (IExpression expression in _expressions)
           {
               result = expression.Evaluate().get();
           }
           return ValueConvert.createValue(result);
       }

       public void printNode()
       {
           Debug.Log("(Block ");
           foreach (IExpression expression in _expressions)
           {
               expression.printNode();
           }
           Debug.Log(")");
       }

       public bool isFunctionCall()
       {
           return false;
       }
   }

   public class BlockExpression : IExpression //ブロックを表すノード（{と}で囲まれた部分）
   {
       private IExpression[] _expressions;

       public BlockExpression(IExpression[] expressions)
       {
           _expressions = expressions;
       }

       public Value Evaluate()
       {
           object result = null;
           foreach (IExpression expression in _expressions)
           {
               result = expression.Evaluate().get();
           }
           return ValueConvert.createValue(result);
       }

       public void printNode()
       {
           Debug.Log("(Block ");
           foreach (IExpression expression in _expressions)
           {
               expression.printNode();
           }
           Debug.Log(")");
       }

       public bool isFunctionCall()
       {
           return false;
       }
   }
   
   public class NativeProcess : IExpression //ネイティブ関数の処理
   {
       private string _funcName;
       private string[] _argmentNames;

       public NativeProcess(string funcName, string[] argmentNames)
       {
           _funcName = funcName;
           _argmentNames = argmentNames;
       }

       public Value Evaluate()
       {
           switch (_funcName)
           {
               case "print":
                   {
                       Value printValue = Environments.getVarValue(_argmentNames[0]);

                       Debug.Log(printValue.getDouble());

                       return printValue;
                   }
               default:
                   throw new TurquoiseException($"{_funcName} is not defined native function");
           }
       }

       public void printNode()
       {
           Debug.Log($"(NativeFunc:{_funcName})");
       }

       public bool isFunctionCall()
       {
           return true;
       }
   }

   public class Environment //環境（スコープ）
   {
       private Dictionary<string, Value> variables; //変数のリスト
       private Dictionary<string, FunctionsNameAndValue> functions; //関数のリスト

       public Environment()
       {
           variables = new Dictionary<string, Value>();
           functions = new Dictionary<string, FunctionsNameAndValue>();
       }
       public Environment(Dictionary<string, Value> variables, Dictionary<string, FunctionsNameAndValue> functions)
       {
           this.variables = variables;
           this.functions = functions;
       }

       public void addVarValue(string name, Value value) //変数の追加
       {
           variables[name] = value;
       }

       public void addFuncNameAndValue(string name, FunctionsNameAndValue nameAndValue) //関数の追加
       {
           functions[name] = nameAndValue;
       }

       public Value getVarValue(string name) //変数の取得
       {
           return variables[name];
       }

       public FunctionsNameAndValue getFuncNameAndValue(string name) //関数の取得
       {
           return functions[name];
       }

       public bool isItExistsVar(string name) //特定の変数があるかどうか
       {
           return variables.ContainsKey(name);
       }

       public bool isItExistsFunc(string name) //特定の関数があるかどうか
       {
           return functions.ContainsKey(name);
       }
   }

   public static class Environments //環境を管理するクラス
   {
       private static Stack<Environment> environments = new Stack<Environment>(); //スタックで管理

       static Environments()
       {
           Environment firstEnvironment = new Environment();

           ParameterExpression printParameter = new ParameterExpression(new IExpression[]{ new VariableExpression("n")});
           NativeProcess printProcess = new NativeProcess("print", new string[]{ "n"});
           firstEnvironment.addFuncNameAndValue("print", new FunctionsNameAndValue(new FunctionExpression("print", printParameter), printProcess));

           environments.Push(firstEnvironment); //ネイティブ関数の追加
       }

       public static void push(Environment environment) //環境の追加
       {
           environments.Push(environment);
           if (environments.Count > 1000)
           {
               throw new TurquoiseException("Stack over flow.");
           }
       }

       public static Environment pop() //環境の削除
       {
           return environments.Pop();
       }

       public static Environment peek() //一番上の環境を取得
       {
           return environments.Peek();
       }

       public static Value getVarValue(string name) //すべての環境の中から特定の変数を探す
       {
           foreach (Environment environment in environments)
           {
               if (environment.isItExistsVar(name))
                   return environment.getVarValue(name);
           }
           throw new TurquoiseException($"'{name}' is undefined.");
       }

       public static FunctionsNameAndValue getFuncNameAndValue(string name) //すべての環境の中から特定の関数を探す
       {
           foreach(Environment environment in environments)
           {
               if (environment.isItExistsFunc(name))
                   return environment.getFuncNameAndValue(name);
           }
           throw new TurquoiseException($"'{name}' is undefined.");
       }
   }

   public class FunctionsNameAndValue //関数を表すクラス
   {
       public FunctionExpression function;
       public IExpression expression;

       public FunctionsNameAndValue(FunctionExpression function, IExpression expression)
       {
           this.function = function;
           this.expression = expression;
       }
   }
}

書き忘れていましたが、使われているTurquoiseExceptionのコードはこちらです。

TurquoiseException.cs

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System;

public class TurquoiseException : Exception
{
   public TurquoiseException() : base() { }
   public TurquoiseException(string message) : base(message) { }
   public TurquoiseException(string message, Exception inner) : base(message, inner) { }
}

次回は、構文解析器を完成させていきます。
次回の記事はこちら