Interpreterパターン
Interpreterパターンは、文法を解釈しその内容を実行するインタプリタの作成に使う。ここでは、以下の仕様の 1 桁の数字を計算するインタプリタを作ってみる。
- 使用できる演算子は '*' と '+'。
- '*' は '+' より先に計算する。
- '(' と ')' で囲んだ部分は先に計算する。
このインタプリタの文法は以下の通り。
<AddExpression>: --> <MultiplyExpression> --+-----------------------------------+-->| A | | | +-- <MultiplyExpression> <-- '+' <--+ <MultiplyExpression>: --> <ElementExpression> --+---------------------------------+-->| A | | | +-- <ElementExpression> <-- '*' --+ <ElementExpression>: --+-------------> '数字' ----------------+-->| | A | | +--> '(' --> <AddExpression> --> ')' --+
Interpreterパターンは、文法要素を表す抽象クラスを作成し、それぞれの文法要素をその派生クラスとして定義する。この例では、以下のクラス階層を作成する。
- Expression
- AddExpression
- MultiplyExpression
- ElementExpression
文法要素を表す抽象クラスExpressionは、入力文字列を解釈するstaticメソッドのParse()と、式の内容を評価する抽象メソッドのEvaluate()を持つ。Lexerは入力の文字列を字句解析するクラスで、後で説明する。
internal abstract class Expression { internal static Expression Parse(string input) { var lexer = new Lexer(input); Expression expression = AddExpression.DoParse(lexer); if (!lexer.IsEndOfInput()) { throw new Exception("入力終了を予期していました。"); } return expression; } internal abstract int Evaluate(); }
文法要素<AddExpression>を表すAddExpressionクラスは、文法を解釈するDoParse()メソッドを持ち、基底クラスの抽象メソッドEvaluate()をoverrideする。
- DoParse()メソッド: MultiplyExpression.DoParse()を呼び、その後ろが '+' ならばMultiplyExpression.DoParse()の呼び出しを繰り返す。
- Evaluate()メソッド: 2つのExpressionの内容を評価し、それらの値を加える。
internal class AddExpression : Expression { internal static Expression DoParse(Lexer lexer) { Expression expression1 = MultiplyExpression.DoParse(lexer); for ( ; ; ) { if (!lexer.ReadIf('+')) { return expression1; } Expression expression2 = MultiplyExpression.DoParse(lexer); expression1 = new AddExpression(expression1, expression2); } } private readonly Expression m_expression1; private readonly Expression m_expression2; private AddExpression(Expression expression1, Expression expression2) { m_expression1 = expression1; m_expression2 = expression2; } internal override int Evaluate() { int result1 = m_expression1.Evaluate(); int result2 = m_expression2.Evaluate(); return result1 + result2; } }
文法要素<MultiplyExpression>を表すMultiplyExpressionクラスは、AddExpressionクラスとよく似ている。
- DoParse()メソッド: ElementExpression.DoParse()を呼び、その後ろが '*' ならばElementExpression.DoParse()の呼び出しを繰り返す。
- Evaluate()メソッド: 2つのExpressionの内容を評価し、それらの値を掛ける。
internal class MultiplyExpression : Expression { internal static Expression DoParse(Lexer lexer) { Expression expression1 = ElementExpression.DoParse(lexer); for ( ; ; ) { if (!lexer.ReadIf('*')) { return expression1; } Expression expression2 = ElementExpression.DoParse(lexer); expression1 = new MultiplyExpression(expression1, expression2); } } private readonly Expression m_expression1; private readonly Expression m_expression2; private MultiplyExpression(Expression expression1, Expression expression2) { m_expression1 = expression1; m_expression2 = expression2; } internal override int Evaluate() { int result1 = m_expression1.Evaluate(); int result2 = m_expression2.Evaluate(); return result1 * result2; } }
文法要素<ElementExpression>を表すElementExpressionクラスも同様に、DoParse()メソッドとEvaluate()メソッドを持つ。
- DoParse()メソッド:
- 現在の字句が数字ならば、その値を内容に持つElementExpressionのインスタンスを生成する。
- 現在の字句が '(' ならば、それに続く内容を解釈し ')' が閉じていることを確認する。
- 現在の字句が上記以外ならば、文法エラー。
- Evaluate()メソッド: 数字の値をそのまま返す。
internal class ElementExpression : Expression { internal static Expression DoParse(Lexer lexer) { if (lexer.IsDigit()) { int number = lexer.ReadCurrentAsNumber(); return new ElementExpression(number); } else if (lexer.ReadIf('(')) { Expression expression = AddExpression.DoParse(lexer); lexer.ReadExpected(')'); return expression; } else { throw new Exception("数字 あるいは '(' を予期していました。"); } } private readonly int m_number; private ElementExpression (int number) { m_number = number; } internal override int Evaluate() { return m_number; } }
このインタプリタの字句解析を行うLexerクラスは、以下のようにした。
- Current プロパティは、現在の字句を返す。取り扱う字句は 1 文字なので、戻り値の型はcharにする。
- MoveNext() メソッドは、次の字句に移動する。
- ReadXxx() メソッドは、現在の字句を読み込み、次の字句に移動する。
internal class Lexer { private readonly string m_input; private int m_index; private char m_current; private const char EndOfInput = '\x00'; internal Lexer(string input) { m_input = input; // DoMoveNext() で最初にインクリメントするので、-1 から始める。 m_index = -1; MoveNext(); } internal char Current { get { return m_current; } } internal void MoveNext() { m_current = DoMoveNext(); } private char DoMoveNext() { for (++m_index; !IsEndOfInput(); ++m_index) { char c = m_input[m_index]; if (!char.IsWhiteSpace(c)) { return c; } } return EndOfInput; } internal bool IsEndOfInput() { return m_input.Length <= m_index; } internal bool IsDigit() { return char.IsDigit(Current); } internal int ReadCurrentAsNumber() { int number = int.Parse(Current.ToString()); MoveNext(); return number; } internal bool ReadIf(char expected) { if (Current != expected) { return false; } else { MoveNext(); return true; } } internal void ReadExpected(char expected) { CheckExpected(expected); MoveNext(); } private void CheckExpected(char expected) { if (Current != expected) { string message = string.Format("文字 '{0}' を予期していました。", expected); throw new Exception(message); } } public override string ToString() { return m_input.Substring(m_index); } }
このインタプリタを動作させるプログラムは、次のようになる。
class Program { static void Main(string[] args) { const string Input = "2 * (3 + 4)"; Expression expression = Expression.Parse(Input); int result = expression.Evaluate(); Console.WriteLine("{0} => {1}", Input, result); } // ===== 画面への出力 ===== // 2 * (3 + 4) => 14 }