数式を解くプログラム その3 - 字句解析2
id:yone-ken:20090219:1235007962 の続きです。前回用意したTokenKind列挙型、Tokenクラスを使って、字句解析処理を実装します。字句解析を行うクラスはTokenizerクラスと命名します。そして、字句解析クラスのインターフェースを規定するクラスとしてContext
abstract class Context<T> { public abstract T Current { get; } public abstract bool MoveNext(); }
想定される字句解析処理は、式の文字列表現を何らかの形で受け取ります。それを字句解析した上で、構文解析処理からのトークンちょうだい！という要求をトリガーに次のトークンを読み出すことができます。また、読み出したトークンを取得することができます。これらの要求を満たすように、次のトークンの読み出しを行い、読み出せたかどうかの結果を返すためにMoveNextメソッドを、読み出したトークンを取得するためにCurrentプロパティを用意します。
Tokenクラスの構造は字句解析処理、構文解析処理の都合で変わりますので、トークンの実装が増えてもよいように、Contextクラスはジェネリッククラスとしています。今回の数式用の字句解析処理のTokenizerクラスはContext
…と、このクラスの存在意義を語ってみましたが、正直、このクラスは微妙です。そもそもなくても良いかもしれません。また、全部抽象メソッドならインターフェースで良いのでは？インターフェースで良いなら、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(次のトークンの有無)です。これを踏まえて処理フローを説明します。
- 空白をすべて読み飛ばしてその分だけindexを更新する。
- トークンの切り出しに入る前に、切り出し開始位置のindexをローカル変数startIndexに保存する。
- indexが数式末尾なら、eof=trueにセットし、TokenKind.Eofを持つTokenを返す。(MoveNextではeofで次のトークンの有無を判断する)
- index位置の1文字を取り出し、(, ), +, -, *, /とチェックします。一致すれば対応するTokenKindの値を持つTokenインスタンスを返す。
- 残るは数値か無効なトークンのため、正規表現を使って文法定義の
にマッチするかをチェックする。
次回はこのTokenizerクラスを使って、構文解析を行います。
数式を解くプログラム その1 - 概要
下記の掲示板での質問に触発されて、私も
数式を解くプログラムをC#3.0で作ってみました。
■電卓 （（1+2）3）カッコの入れ子
http://bbs.wankuma.com/index.cgi?mode=al2&namber=32500
数式といっても対応するのは、四則演算(+, -, *, /)と丸括弧による演算のみで、数値についてはすべてdecimal型(System.Decimal)として扱うことにします。このプログラムでOKな式とNGな式の例を以下に示します。
【OKな式の例】
- 1+(2-3)*4/5
- 10+((9-8)*3)/2
- -2 * 3.14 + 0 - 1.414
- +8.9+10
【NGな式の例】
- 1+a
- 2**3
- )1+3(
- 100+20+
さて、例示だけでやろうとしていることは十分に伝わると思いますが、厳密さに欠けます。そこで、ここで取り扱う数式の文法を拡張したBNFで定義しておきます。BNFって何？という方は以下を参考にしてください。
wikipedia:バッカス・ナウア記法
::= ('+' )* | ('-' )* ::= ('*' )* | ('/' )* ::= '(' ')' | '+' | '-' | ::= ('.' *)+ ::= * | '0' ::= '1'...'9' ::= '0'...'9' ※字句と字句の間のホワイトスペースは無視するものとする。
< >で囲った部分は非終端記号といい、' 'で囲った部分はその文字そのものを表し、終端記号といいます。(非終端記号というのは文法を構成する抽象的要素で、終端記号は具体的な要素、というくらいの理解で十分です。) ( )で囲まれた部分はそれを1グループとして扱い、*はその直前の要素が0以上現れ、+は0または1回現れることを意味します。正規表現に似せたルールにしているのでなんとなくは理解できると思います。
数値は
今回はここまでの説明に加えて、このプログラムで作るクラスを一覧できる図を掲載して終わります。次回は字句解析部分を解説する予定です。
C#のメソッド名の制限事項
先日、WPFをまねてTransformクラスとその継承クラスRotateTransform、ScaleTransform、SkewTransform、MatrixTransform、TransformGroupクラスをC#のWindows Formsアプリケーションのプロジェクトで作ろうとしたときのこと。Transformクラスを抽象クラスとして、この階層でTransformメソッドとValueプロパティを定義しようとしました。Transformメソッドはクラス名と同名のため、
error CS0542:'Transform': メンバ名をそれを囲む型の名前と同じにすることはできません
というエラーになりました。
クラス名と同名のメンバを定義できないのです。
C#ではコンストラクタはクラス名と同名を持つというルールがあるので、このような制約があるのかなという予想をしましたが、コンストラクタは通常のメソッドと違って戻り値の指定がない形式のため、構文上明確に区別できます。そう考えると、この制約は言語仕様上で回避できないものではないように思えます。メソッド名がクラス名と同名になることを積極的に禁止する理由がわかりません。
このときは仕方ないので、Transformクラス及び〜Transformクラスは命名を変えて、Transformerクラスと〜Transformerクラスにしました。ただでさえ長い名前がより長くなってしまい不満です。ちなみに、WPFのクラスライブラリではTransformクラスの基底クラスとしてGeneralTransformクラスがあり、Transformメソッドはそこで定義されているため、仮にC#で実装されているとしても問題は発生しません。
確かにクラス名と同名のメソッドやプロパティが定義できるのは通常は混乱のもとだとは思いますが、これを禁止してしまうと、例えば、定義しようとしているクラス名が、継承元クラスのメンバ名や実装するインタフェースのメンバ名とたまたまかぶった場合に不都合が起きます。継承元クラスでオーバーライドしたいメソッドが自分のクラス名と同名の場合、オーバーライドができません。実装したいインターフェースに自分のクラス名と同名のメンバがあった場合には通常の実装はできず、明示的な実装しかできません。ちなみにVBではクラス名と同名のメソッドも定義できます。C#では残念ながら定義できないようですから、命名には注意が必要です。
これに対する反論を想定すると、そもそもクラス名とメソッド名に同じ名称を使う必要があるのか？ということになるかと思いますが、Transform(変換)クラスのTrasform(変換する)メソッドのように動詞と名詞が同じ単語の場合にそのような命名にしたい場合がありえます。私の場合、回避策としてTransformerと命名しましたが、TransformとTransformerは少々ニュアンスが違うので、なんとなく嫌だなと思いました。
最後に検証コードを載せておきます。
続きを読むブログはじめました。
去年の年始からブログをやろうやろうと１年の目標に挙げていました。結局、去年は目標を果たせず、今の今まで実践できていませんでしたが、いよいよブログを始動します。
このブログでやりたいこと。
ジャンルを問わず、プログラミングに関することで私が興味を持ったことであれば何でも取り上げていきます。特に興味のある分野は.NET Framework、VB、C#、MSIL、Python、言語処理系、ゲーム系、言語仕様の詳細とか重箱の隅とか。目新しい言語や新しいパラダイムとかも興味はあります。とはいえ、現状、一番ホットなのは、C#3.0周辺なので、C#3.0、VB9.0、.NET Framework3.5、WPF辺りが多くなるのではと思います。よろしくお願いいたします。
静的サイトもやってますが、HTMLを書くのが面倒で更新が滞りがち。ブログで即時にネタを扱っていって、ある程度まとまったら、静的サイトに反映したいなぁなどとたくらんでおります。
http://www5b.biglobe.ne.jp/~yone-ken/
