数式を解くプログラム その6(最後) - 構文解析3

id:yone-ken:20090223:p1 の続きです。さっそく、Expressionクラスから見ていきます。

class Expression : Node
{
    public override void Evaluate(Context<Token> context)
    {
        Node left = new Term();
        left.Evaluate(context);
        this.Value = left.Value;

        while (true)
        {
            Func<decimal, decimal, decimal> func = null;
            switch (context.Current.Kind)
            {
                case TokenKind.OpAdd: func = (d1, d2) => d1 + d2; break;
                case TokenKind.OpSub: func = (d1, d2) => d1 - d2; break; 
                case TokenKind.Invalid:
                    throw new EvaluateException("無効な文字が含まれています。", context.Current);
                case TokenKind.Eof:
                    return;     // 正常終了
                default:
                    return;     // Expressionを終了して、処理は継続
            }

            context.MoveNext();
            Node right = new Term();
            right.Evaluate(context);
            this.Value = func(this.Value, right.Value);

        }
    }
}

ExpressionクラスはNodeクラスのEvaluateメソッドをオーバーライドしています。はで始まるため、最初にTermクラスのインスタンスを生成し、TermのEvalutateメソッドを実行します。実行後、TermクラスのValueプロパティに評価結果が入っていますので、これをExpressionのValueプロパティに反映します。続いて、加算/減算記号の有無をチェックします。トークンが加算/減算記号の場合、decimalの引数2つ、戻り値decimalのデリゲートに加算用または減算用の匿名メソッド(例えば「(d1, d2) => d1 + d2」と記述している箇所。)をセットします。ここではわざわざ匿名メソッドを使っていますが、decimal.Addとdecimal.SubtractでもOKです。

加算/減算記号以外で無効なトークンの場合は評価の例外としてEvaluateExceptionを発生させます。それ以外のトークンだった場合はの評価は終了のため、メソッドを抜けます。加算/減算記号だった場合は引き続き、右辺側のを評価するため、加算/減算記号のトークンを読み飛ばして、TermクラスのEvaluateメソッドを実行します。処理結果は、デリゲートの処理を使ってExpressionのValueプロパティに反映しておきます。以上、加算/減算記号が登場する限り、右辺の計算を続けます。次にTermクラスを見ていきます。

class Term : Node
{
    public override void Evaluate(Context<Token> context)
    {
        Node left = new Factor();
        left.Evaluate(context);
        this.Value = left.Value;

        while (true)
        {
            Func<decimal, decimal, decimal> func = null;
            switch (context.Current.Kind)
            {
                case TokenKind.OpMul: func = (d1, d2) => d1 * d2; break;
                case TokenKind.OpDiv: func = (d1, d2) => d1 / d2; break; 
                default:
                    return;     // Termを終了して、処理は継続
            }
            // 計算の例外発生時のためにトークンを保持しておく。
            Token snapshot = context.Current;

            context.MoveNext();
            Node right = new Factor();
            right.Evaluate(context);
            try
            {
                this.Value = func(this.Value, right.Value);
            }
            catch (DivideByZeroException)
            {
                throw new EvaluateException("0で除算できません。", snapshot);
            }

        }

    }
}

基本的にはとの関係が、との関係にスライドしただけです。Expressionクラスとで異なるところは加算/減算に対して乗算/除算を扱っているため、除算のときの0割り例外の発生を考慮している点です。続いてFactorクラスを見ていきます。

class Factor : Node
{
    public override void Evaluate(Context<Token> context)
    {
        Node exp = null;
        switch (context.Current.Kind)
        {
            case TokenKind.LParen:
                context.MoveNext();
                exp = new Expression();
                exp.Evaluate(context);
                if (context.Current.Kind != TokenKind.RParen)
                {
                    throw new EvaluateException("')'が足りません。", context.Current);
                }
                this.Value = exp.Value;
                break;
            case TokenKind.OpAdd:
            case TokenKind.OpSub:
                decimal sign = (context.Current.Kind == TokenKind.OpSub) ? -1 : 1;
                context.MoveNext();
                exp = new Expression();
                exp.Evaluate(context);
                this.Value = sign * exp.Value;
                break;
            case TokenKind.Number:
                this.Value = (decimal)context.Current.Value;
                break;
            case TokenKind.Invalid:
                throw new EvaluateException("無効な文字が含まれています。", context.Current);
            case TokenKind.Eof:
                throw new EvaluateException("式が途中で終わっています。", context.Current);
            default:
                throw new EvaluateException("不正な式です。", context.Current);
        }
        context.MoveNext();
    }
}

Factorクラスでは先頭のトークンにより処理が分岐します。左括弧'('で始まる場合は、'(' ')'、加算/減算記号で始まる場合は'+' 、'-' '、数値トークンの場合はです。どのパターンであるかが1つ目のトークンで判断できるため、単純な分岐で済みます。の処理を行う段階では、Eofトークンが来ることは正常な式ではありえません。与えられた式がまったくの空である場合は、Eofトークンしかないため、ExpressionクラスのEvaluateメソッドでEofの場合をはじいており、FactorクラスのEvaluateメソッドは呼ばれません。それ以外では、必ずTermクラスのEvaluateメソッドから呼ばれます。数式が単体の数値だけの場合は別として、は乗算/除算/加算/減算の演算子の後に処理される要素のため、の評価でEofトークンが来るということは、式が演算子で終わっているということです。(たとえば、「1+1*」のようなパターン)。

また、Evaluateメソッドの最後に「context.MoveNext()」で処理済みのトークンを読み飛ばしていますが、これは重要です。、、のすべてで共通ですが、Evaluateメソッドの処理開始時点では、その構文定義で処理を行うべきトークンがcontext.Currentにセットされていることを前提としており、そのため、Evaluateメソッドの終了時点では、その構文定義で処理すべきトークンはすべて読み飛ばされている状態でなければなりません。

最後にExpressionEvaluatorクラスを掲載します。今までに紹介した字句解析、構文解析を行うためのクラスを使って数式を評価するための外部向けインタフェースとなるクラスです。特に難しいことはしていませんので説明は端折ります。ざっとクラスを眺めてください。このクラスの使用例は最後に掲載します。

public class ExpressionEvaluator
{
    public String Expression { get; private set; }

    private Expression exp;
    public decimal Value
    {
        get 
        {
            if (this.LastError)
            {
                throw new InvalidOperationException("最後の評価にエラーがあります。");
            }
            return this.exp.Value; 
        }
    }

    public bool LastError { get; private set; }

    private string lastErrorMessage;
    public string LastErrorMessage
    {
        get 
        {
            if (!this.LastError)
            {
                throw new InvalidOperationException("最後の評価にエラーはありません。");
            }
            return this.lastErrorMessage;
        }
        private set { this.lastErrorMessage = value; }
    }

    private int lastErrorColumn;
    public int LastErrorColumn
    {
        get 
        {
            if (!this.LastError)
            {
                throw new InvalidOperationException("最後の評価にエラーはありません。");
            }
            return this.lastErrorColumn; 
        }
        private set { this.lastErrorColumn = value; }
    }

    public ExpressionEvaluator()
    {
        this.exp = new Expression();
    }

    public bool Evaluate(string expression)
    {
        this.Expression = expression;
        try
        {
            Context<Token> context = new Tokenizer(this.Expression);
            if (!context.MoveNext()) return false;
            exp.Evaluate(context);
            this.LastError = false;
            this.LastErrorColumn = 0;
            this.LastErrorMessage = string.Empty;
            return true;
        }
        catch (EvaluateException e)
        {
            this.LastError = true;
            this.LastErrorColumn = e.Token.Column;
            this.LastErrorMessage = e.Message;
            return false;
        }
    }
}

ExpressionEvaluatorクラスのEvaluateメソッドに数式を渡すと評価を行います。数式の評価の成否は戻り値でtrue/falseで示しますので、成功していたら、Valueプロパティで結果を参照できます。評価できなかった場合は、LastErrorMessageで失敗内容をLastErrorColumnで失敗位置を取得できます。以上で、数式を解くプログラムは完成です。呼び出し部分は例えば、以下のように書けます。

class Program
{
    static void Main(string[] args)
    {
        ExpressionEvaluator eval = new ExpressionEvaluator();
        string expression = "(1+4)*3/5-2";
        Console.Write(expression.PadRight(10));
        if (eval.Evaluate(expression)
        {
            Console.WriteLine("= {0}", eval.Value);
        }
        else
        {
            Console.WriteLine();
            Console.WriteLine(new String(' ', eval.LastErrorColumn) + "^ " + eval.LastErrorMessage);
        }
        Console.Read();  // Enter押下でコマンドプロンプトを閉じてください。
    }
}

数式を解くプログラムの解説はここまでです。ぼんやりとですが、このプログラムにはいろいろと課題があるなと思っています。このプログラムを元に拡張していくとその問題点も見えてくると思いますが、私自身はまだその問題点も一部しか見えていませんし、問題点に対する解決策も持っていません。徐々に研究を深めていきたいと思います。