数式を解くプログラム その3 - 字句解析2

id:yone-ken:20090219:1235007962 の続きです。前回用意したTokenKind列挙型、Tokenクラスを使って、字句解析処理を実装します。字句解析を行うクラスはTokenizerクラスと命名します。そして、字句解析クラスのインターフェースを規定するクラスとしてContext抽象クラスを作ります。Contextクラスは以下のようにしました。

abstract class Context<T>
{
    public abstract T Current { get; }
    public abstract bool MoveNext();
}

想定される字句解析処理は、式の文字列表現を何らかの形で受け取ります。それを字句解析した上で、構文解析処理からのトークンちょうだい!という要求をトリガーに次のトークンを読み出すことができます。また、読み出したトークンを取得することができます。これらの要求を満たすように、次のトークンの読み出しを行い、読み出せたかどうかの結果を返すためにMoveNextメソッドを、読み出したトークンを取得するためにCurrentプロパティを用意します。

Tokenクラスの構造は字句解析処理、構文解析処理の都合で変わりますので、トークンの実装が増えてもよいように、Contextクラスはジェネリッククラスとしています。今回の数式用の字句解析処理のTokenizerクラスはContextを継承します。

…と、このクラスの存在意義を語ってみましたが、正直、このクラスは微妙です。そもそもなくても良いかもしれません。また、全部抽象メソッドならインターフェースで良いのでは?インターフェースで良いなら、IEnumeratorかIEnumeratorを継承したインターフェースでいいんじゃね?とか。いろいろ意見が分かれそうなところですが、とりあえず、こういうクラスを用意します。

次にTokenizerクラスを見ていきます。

class Tokenizer : Context<Token>
{
    private string expression;
    private int index;
    private bool eof;

    public Tokenizer(string expression)
    {
        this.expression = expression;
        this.index = 0;
        this.eof = false;
    }

    private Token current;
    public override Token Current
    {
        get { return this.current; }
    }

    public override bool MoveNext()
    {
        if (!this.eof)
        {
            this.current = GetToken();
            return true;
        }
        else
        {
            return false;
        }
    }

    private Token GetToken()
    {
        while (this.index < this.expression.Length && Char.IsWhiteSpace(this.expression[this.index]))
        {
            this.index++;
        }
        int startIndex = this.index;
        if (this.index == this.expression.Length)
        {
            this.eof = true;
            return new Token(TokenKind.Eof, startIndex);
        }
        char c = this.expression[index];
        switch (c)
        {
            case '(': index++; return new Token(TokenKind.LParen, startIndex);
            case ')': index++; return new Token(TokenKind.RParen, startIndex);
            case '+': index++; return new Token(TokenKind.OpAdd, startIndex);
            case '-': index++; return new Token(TokenKind.OpSub, startIndex);
            case '*': index++; return new Token(TokenKind.OpMul, startIndex);
            case '/': index++; return new Token(TokenKind.OpDiv, startIndex);
            default:
                Regex re = new Regex(@"^(0|[1-9][0-9]*)(\.[0-9]+)?");
                Match match = re.Match(this.expression.Substring(index));
                if (match.Success)
                {
                    decimal dec = decimal.Parse(match.Value, CultureInfo.InvariantCulture);
                    index += match.Length;
                    return new Token(TokenKind.Number, startIndex, dec);
                }
                else
                {
                    index = this.expression.Length;
                    return new Token(TokenKind.Invalid, startIndex, this.expression[startIndex]);
                }
        }
    }
}

Tokenizerクラスの中心的な処理はGetTokenメソッドで実装しています。GetTokenメソッドでは、3つのインスタンス変数を利用します。参照のみ行うexpression(数式を表す文字列。コンストラクタでセットされる)、参照と設定を行うindex(expressionでの現在処理している文字の位置)、設定のみ行うeof(次のトークンの有無)です。これを踏まえて処理フローを説明します。

  1. 空白をすべて読み飛ばしてその分だけindexを更新する。
  2. トークンの切り出しに入る前に、切り出し開始位置のindexをローカル変数startIndexに保存する。
  3. indexが数式末尾なら、eof=trueにセットし、TokenKind.Eofを持つTokenを返す。(MoveNextではeofで次のトークンの有無を判断する)
  4. index位置の1文字を取り出し、(, ), +, -, *, /とチェックします。一致すれば対応するTokenKindの値を持つTokenインスタンスを返す。
  5. 残るは数値か無効なトークンのため、正規表現を使って文法定義のにマッチするかをチェックする。
    1. マッチしたらTokenKind.Numberを持つTokenインスタンスを返す。この場合のTokenインスタンスの生成では、数値の値もコンストラクタに渡す。
    2. マッチしなければTokenKind.Invalidを持つTokenインスタンスを返す。


次回はこのTokenizerクラスを使って、構文解析を行います。