３年くらい前、実数を表す文字列を受理するオートマトンを実装してみた。 最近、簡単な正規表現をDFAに変換するコードを書いてみてるけど、その中で、過去書いた日記に誤りを見つけたので、訂正しておく。

どのパターンか判断できるようにしてみた。Ideone.com - vcrHk5 - Online C# Compiler & Debugging Tool

以下のフォーマットを受理するDFAを作った。 Ideone.com - FxXej0 - Online C# Compiler & Debugging Tool yyyy/MM/dd HH:mm:ss.fff yyyy/MM/dd HH:mm:ss yyyy/MM/dd HH:mm yyyy/MM/dd HH yyyy/MM/dd yyyy/MM yy/MM/dd HH:mm:ss.fff yy/MM/dd HH:mm:ss yy/MM…

日付や時間に関する型も用意して、オートマトンでチェックしたい。受理したい形式は以下。 yyyy/MM/dd HH:mm:ss.fff yyyy/MM/dd HH:mm:ss yyyy/MM/dd HH:mm yyyy/MM/dd HH HH:mm:ss.fff HH:mm:ss HH:mm mm:ss.fff mm:ss ss.fff 時刻部分はAM/PM表記も許した…

以前作った整数のオートマトン、文字列"01"を受理するかどうかはさておき、"0"を受理しないのは問題だと思うので修正した。

先日εNFAをNFAに変換した。 今度はこのNFAをDFAに変換したい。これをやるのが「部分集合構成法」というものらしい。以下にDFAの状態遷移表を作っていく。 NFAの初期状態はのみなので、初期状態の集合はとなる。そして、初期状態の集合から遷移する可能性のあ…

自分の理解力の無さから、参考にしようとしていたサイトの説明では行き詰ってしまった。なのでオートマトンの教科書を読んでみた。 ε動作ありのNFAから、ε動作なしのNFAへの変換のやり方が書いてあったので、やってみた。 まず-（ε閉包というらしい）という…

前回のつづき。「正規表現とNFA・DFA」を参考に、実数の正規表現を元に状態遷移図を描いて、C#で実装してみたい。 RとSを正規表現とすると、RSとR|SとR*を受理するオートマトン（ただし、ε遷移あり）は次のように表現できるらしい。 RS R|S R* 「整数を表す…

正規表現は ^[-+]?[1-9][0-9]*$でいいんじゃないかな。これに相当する状態遷移図は でいいんじゃないかな。S2が受理状態。S3になったら直ちにエラーとして停止していい。これを元に作ってみたC#のクラスは interface Checker { /// <summary>このオブジェクトの状態を</summary>…

先日教えてもらったアルゴリズムで字句の列からS式を構築するパーザを作ってみた。ここに恥を晒しておく。 // 字句の列からS式を作る public SExp Parse(IEnumerable<LexerToken> tokens) { IEnumerator<LexerToken> itor = tokens.GetEnumerator(); SExp exp = null; if (itor.MoveN</lexertoken></lexertoken>…

S式のパーザを作っている。学生時代に習ったような気がする微かなオートマトンの記憶を元に字句解析は作ってみた。言語処理系の作成は古典的な話題なので、定石と言われる方法がある。自分のやり方でやるよりも、きっと定石に従った方が良いんじゃないだろう…