language

日付や時間を表す文字列を受理するオートマトン③

どのパターンか判断できるようにしてみた。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式を構築するパーザを作ってみた。ここに恥を晒しておく。 // 字句の列からS式を作る public SExp Parse(IEnumerable<LexerToken> tokens) { IEnumerator<LexerToken> itor = tokens.GetEnumerator(); SExp exp = null; if (itor.MoveN</lexertoken></lexertoken>…

オートマトン

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