「新人教育向けの秀逸な課題プログラムって？」記事へのコメント

grep クローン

[strict_ansi (2886)]

Windows 環境では(よく知りませんが)適切ではないかもしれませんが、
grep のクローンなんていかがでしょうか。

実際に動く grep があるので仕様の説明も楽ですし、
ファイル入出力や文字列操作など基本的な要素が詰まっています。
簡単にできてしまった人にも、ファイル名表示や行番号表示など
追加課題も容易に出せます。

もう少し簡単にして tail も良いかもしれません。
過去に tail クローンの課題を出した時、
ファイル全体をメモリ上に入れてしまう実装が多く提出されました。
読んで捨てる実装にしなければならない理由や
その方法を説明できる良い機会となりました。

DFAにすべきかNFAにすべきか、それが問題だ

[jsi (25633)]

grepの実装は面白そうですね。
文字列からステートマシンを生成するなんてのは学校で習った知識をフルに生かせる貴重な瞬間だと思います。
DFAにすれば展開は速いけどメモリはいりそう。
NFAでバックトラックで解けば表現力はあがるけど時間はかかりそうだな。とか。
時間があったらマルチバイトgrepで。
文字クラスが複雑になりstate explosionするところなどを想像すると萌えませんか。

Re:

[Ryo.F (3896)]

DFAにすれば展開は速いけどメモリはいりそう。

この場合の「展開」って検索のこと？
メモリの使用量には差は出ないんじゃない？

NFAでバックトラックで解けば表現力はあがる

上がらないよね。「全てのNFAは、DFAに変換可能である」って習わなかった？

Re:DFAにすべきかNFAにすべきか、それが問題だ

[jsi (25633)]

s/DFAにすれば展開は早いけど/DFAに展開すれば速いけど/

確かに書いてはみたけど早いかどうかはわからないよね。
決定的に解くことはできますね。

> 上がらないよね。「全てのNFAは、DFAに変換可能である」って習わなかった？

DFAで展開しきれないような性質の悪い文字クラスがある場合
DFAで展開するのが無理とは言い切れないまでも、NFAで展開
するのが妥当な場合があります。実際世間の正規表現ライブラリ
のうちNFAで動いているもののほうが表現力が高い場合が
多いかと。

Re:DFAにすべきかNFAにすべきか、それが問題だ

[Ryo.F (3896)]

DFAで展開しきれないような性質の悪い文字クラス

「DFAに展開しきれない」の間違い？

NFAで展開

これも？なんか、用語が混乱してますね。
ところで、「DFAで展開しきれないような性質の悪い文字クラス」って例えばどんなの？

実際世間の正規表現ライブラリのうちNFAで動いているもののほうが表現力が高い場合が多いかと。

それはNFAかDFAかの差、と言うよりはライブラリでどこまで実装するかの差でしょう。