programming

実数を表す文字列を受理するオートマトン(訂正)

3年くらい前、実数を表す文字列を受理するオートマトンを実装してみた。 最近、簡単な正規表現を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>…

継続渡しに関する無駄思案

さっさと続き書けよって感じだけど。また横道へ。 継続渡し形式で手続きは、概念的に「呼び出し元へ戻る」ってことがなくなるので、例えばC#でちゃんとした継続渡し形式の手続きを書こうとすると、複数の文(セミコロンが2個以上)になることはないような気…

自戒

スレッドセーフについてちゃんと勉強しないとだめだ。

オートマトン

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

CUIの開発環境

眠れない。こんな時ははてな日記でも書いてみる。 仕事でプログラミングする必要があるときは、Windows OS上の某ほげほげStudioでやってる。コンパイルやらリンクやらこまけぇことは良いんだよとばかりに、コーディング以外のことはIDE任せにできるので楽だ…

可変個の集合から、直積の集合を作る(その4)

見当違いなこと言ってた。 無限リストを有限リストに小分けしていくというアプローチで解決してみようと思っているところ。 可変個の集合から、直積の集合を作る(その3) - チキン煮込みチーズミックス4辛 偶数の集合と奇数の集合の直積を考えるとき、例え…

可変個の集合から、直積の集合を作る(その3)

無限リストの直積を列挙するとき、うまくいかないことを昨日のエントリで書いた。これを解決する方法がid:doloopwhile:20100707:1278504056で紹介されている。Clojureやったこと無いけど、良いきっかけかな。今度読んでみる。 無限リストを有限リストに小分…

メッセージ

id:yagiey:20100210:1265827551のmake-accountのところで、 make-accountの戻り値は「第1引数に操作の名称を受け取る手続き」ですが、それはまた、「第1引数にメッセージを受け取るオブジェクト」と解釈することもできます。 (p269)という記述がある。 自…

if文

else ifを使ったら最後に必ずelseが必要だと思っていた。恥ずかしながら。 if (cond1) proc1(); else if (cond2) proc2(); else proc3(); みたいな。 ここで、もし、proc3で特に何もやることが無い場合、 else nop(); // nop()は何もしない関数 とか、 else …

マクロ定義はメタプログラミング?

id:yagiey:20100128:1264631316で定義したマクロfooはhogeが束縛されているかどうかは気にしない。 展開された結果の式が、評価できる式なら構わないんだな。 マクロ展開を計算と捉えれば、マクロの定義はメタプログラミング考えられる。しかもホスト言語と…

気になったので実験

ちょっと気になったことを実験してみた。 実験1:defineで名前をつけるとき、2つ目の引数は評価されるのか? gosh> (define add-n (lambda (m) (+ m n))) add-n gosh> (add-n 1) *** ERROR: unbound variable: n Stack Trace: _____________________________…

今後の課題

今回作ったevalだと、defineが無いから名前をつけられない。 defineでテーブルにエントリを追加しなきゃダメだなぁ。 あと、defineでテーブルに追加しても、現時点では以下のものはテーブルから探さずに、決まった処理してるので、再定義ができない。 lambda…

後はeval

字句解析、構文解析、S式の出力を実装出来たので、REPLの「R」と「P」はできたことになる(のか?) ってことで、あとはエヴァりたい。むしろヱヴァりたい。 ...でも、やっぱ本を進めたい。 ってことで、少し暖めておく。 早くSICP読みたいし。 積読書は堆く…

名前をまとめる何か

item-properties item-property-get get-player-attr update-player-attr! たった4つの手続きなのに、もうだめだ。 全ての名前が平等で、のっぺりとしたイメージが気持ち悪い。 クラスや名前空間など、名前をまとめる何かが欲しくなるな。 じゃぁ、作れば?…

不安

新しい技術には目もくれず、なぜかScheme。 古い技術は大切だ、とかそういうのじゃなく、ただ楽しいから勉強している。 そんな自分は使えないプログラマなんだろうなぁ。 PHPの勉強も途中で投げ出したし。 こういうことはモラトリアムな学生時代にやっとくべ…

きになる

他人が書いたCやC++をC#に移植中... 全ての変数(for文のカウンタすらも)が関数スコープってどういうことよ。 ポインタ的な使い方をする変数名の前にはpをつけろ、ってどういうことよ。 ハンガリアン記法推奨ってどういうことよ。 1つの関数が数百行ってど…

Strategyパターン

僕が一番よく使うGoFパターンはStrategyパターン。 Strategyパターンによってカプセル化される処理(関数)は、シグネチャを統一させなければならないけれども、異なる型の引数で呼び出したりしたいと思うことがたまにある。 となると、引数の型をobject型と…

Gmailのチェッカー、再び

あれから少し勉強して、フィードって何なのか分かってきた。 GMailの場合は、Atomという規格(なのかな?)のフィードになってて、こいつを読んでやるようなプログラムを作ってやれば良さそう。 RSSやらAtomやらいくつか形式があるらしいけど、フィードはXML…

継続渡しスタイル

C#でも無名関数作れるし、ここを参考にやってみた。 # トラックバックの使い方がわかりません orz class Program { // 継続(っていうの?)への参照 delegate int Method(int a); static void Main(string[] args) { /////////////////////////////////////…