正規表現

質問

すいません。もう一度質問します。
　Ｃ言語で「正規表現」プログラムしたいです。
　「[0-9]」や「[a-z]」の検知をどのようにプログラムしたらいいかアドバイスください。
　問題は『「.」は任意の文字一文字が存在することを示し、「*」はその前の文字の任意の繰り返し（1回もあり）「[文字-文字]」はその中のいずれかの文字の存在を示す。　これらを用いて「b.c」（argvを用いてキーボード入力）ならb1c、bsc、bah等を、「6*」なら6、66、6666等の存在する行（ファイルをよみこんで）を出力するプログラムをＣで書け。』ということです。
　なかなか分かりません。

　むずかしいです。

回答No.3

noname#11476 · ベストアンサー

まずまともに正規表現によるパターンマッチングを行うのは難しい話ですが、そのサブセット（一部機能）でかつ速度をきにしなければ、オートマンまで持ち出さなくてもプログラムできます。
問題の中には[0-9], [a-z] などの表現に対応せよと書いてありますか？

'.' と '*'(これ'+'の間違いではないですか？１文字以上だと'+'で、'*'は0文字以上ですけど、普通は）が課題ですね。

上記だけだと、 与えられた正規表現文字列s[]と検索対象の文字列src[]とを比較していくだけです。

[X-Y](X, Y は序列のある文字)の表現を組み込みたい場合は、一度内部形式に変換したほうがよいでしょう。
たとえば、
struct regt {
int type; /* type = 0 .. 1文字, type = 1 .. 任意文字, type = 2 .. 範囲文字 */
int n; /* n = 0 .. 0 1文字のみ, n = 1 一文字以上, n = 2 ... */
char a; /* 1文字の時にはここに入れる */
char b; /* 範囲文字の時にはここにも入れる */
} rege;

のようにして、配列 rege[] に一度正規表現を変換していれます。
そうすると後段の処理がやりやすくなります。
つまり、一つのクリアすべきマッチング単位に配列にするわけです。
一致すれば次の配列要素に進めますから。ポイントは * のコーディングですね。
まあ、ヨーク考えてください。

実用的であることを考えなければ（速度が遅くてもよければ）、src[0]からマッチするか、src[1]からマッチするか、src[2]からマッチするかとやればＯＫです。

＜本当は＞
正規表現では決まりとして、たとえば "b.*b" という表現だと "bxbxxxbxx" という文字があれば、はじめの"bxb"ではなくて、"bxbxxxb"にマッチする必要があります。
が、行を指摘するだけならばどちらでもかまわないでしょう。

回答No.2

ranx

正規表現を読んで決定性有限状態オートマトンを自動生成するプログラムを
書けということでしょうか。
maroniichanさんのスキルは分かりませんが、結構難しい話ですよね。
とりあえず、参考URLの図でも見ながら考えてみて下さい。

参考URL：

http://buri.sfc.keio.ac.jp/~yosuke/keisan-kino-ron/3rd.html

回答No.1

GOLDEN

[0-9]なら、'0'<=x<='9'(xが対象文字)ということですよ

課題だとおもうんで、ヒントだけにしときます