読者です 読者をやめる 読者になる 読者になる

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
    }