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

C# .NET 言語処理系

id:yone-ken:20090218:1234954345 の続きです。前回記載した数式の文法を踏まえた話をしますので、必要に応じて参照してください。「数式を解く」ためにはまず字句解析という処理が必要です。
wikipedia:字句解析
例によって細かい話は上記を参照して頂くとして、字句解析というのはざっくり言うと字句に分解することです。字句は文法上で意味のある一塊です。具体的には以下の数式で見てみましょう。

20+9*(10-2)/8+1.2

このような式があったとすると、字句に分解すると

20, +, 9, *, (, 10, -, 2, ), /, 8, +, 1.2

となります(ここでの,は単なる区切りで、字句ではありません)。つまり、数値なのか演算子なのか(演算子であればどの演算子なのか)といったことを区別する作業です。これを踏まえて、これらの字句を区別するために列挙型を作成します。以下にその列挙型の定義を記載します。ちなみに、字句のことを格好よく言うとトークン(token)といいますので、トークンの種類ということでTokenKindと命名しています。さらに余談を書くとIronPythonの同様の役目を負っている列挙型もTokenKindと命名されています。

enum TokenKind
{
    LParen,
    RParen,
    OpAdd,
    OpSub,
    OpMul,
    OpDiv,
    Number,
    Invalid,
    Eof
}

上から順に(, ), +, -, *, /, 数値, 無効な字句、式の終わり、を意味するものとします。丸括弧は英単語ではParenthesisとなりますが、長ったらしく、かつ、日本人はタイプミスしまくりそうなので、ここでは今時の命名ではなく短縮した名前にしています。いわずもがなですがL/RはLeft/Rightの意味です。Opと頭についているものは、演算子のグループです。Invalid(無効な字句)を用意しているのは、与えられる式が正しい文法に則ったものとは限らないため、想定外の字句を発見した場合に使います。EofはEnd Of Fileの略でファイルの終端を表す言葉のため正しい命名ではありませんが、ここではそんな細かいことは気にしないことにします(正確にはEnd Of ExpressionだとかEnd Of Lineでしょう)。この命名がいまいちだなと思ったら、リファクタリングで名称を好きに変更しましょう。Eofはとにかく式の終わりを意味します。

この列挙型とは別にトークンを表すためにTokenクラスを作成します。Tokenクラスを作る目的は、TokenKindだけでは後で困るからです。例えばTokenKind.Numberのトークンだった場合、後の処理で実際の数値が必要になります。そのため、TokenKind.Numberで数値だと判別できるだけでなく、実際の値も情報として保持しておく必要がありそうです。また、数式を評価するときに無効なトークンを見つけた場合は、後で数式のどの場所が不正なのかを判断できるようにしたいところです。というわけで、以下のようなTokenクラスを作成します。

class Token
{
    public int Column { get; private set; }
    public TokenKind Kind { get; private set; }
    public object Value { get; private set; }

    public Token(TokenKind kind, int column)
        : this(kind, column, null)
    {
    }

    public Token(TokenKind kind, int column, object value)
    {
        this.Kind = kind;
        this.Column = column;
        this.Value = value;
    }
}

TokenクラスはColumn、Kind、Valueの3つのプロパティを持ちます。Valueはトークンが数値だった場合に実際の値を保持します。また、Columnは数式を表す文字列でのトークンの開始位置を保持します。想定している数式は単一行のため、行番号は考慮しません。トークンの終了位置もあまり重要でないので考慮しません。

ここまでで字句解析を行うための準備ができました。字句解析のメイン処理は次回に説明します。