2026-10-18
ids.c
#include <stdio.h>
static bool here(const char *re, const char *s) {
if (re[0] == '\0') return true;
if (re[1] == '*') {
do {
if (here(re + 2, s)) return true;
} while (*s != '\0' && (*s++ == re[0] || re[0] == '.'));
return false;
}
if (re[0] == '$' && re[1] == '\0') return *s == '\0';
if (re[0] == '.' || re[0] == *s) return here(re + 1, s + 1);
return false;
}
int main(void) {
const char *ids[] = {"id7", "id", "ix9"};
for (int i = 0; i < 3; i++) {
printf("%s %d\n", ids[i], here("id.", ids[i]));
}
}
here(re, s) は、^ $ . * だけを扱う正規表現 re が文字列 s の先頭から始まる部分に一致するかを返す関数で、. は任意の1文字に一致します。main は、id の後ろに少なくとも1文字続く文字列だけを通すつもりで、パターン id. を3つの文字列に当てています。いまの出力は id7 1、id 1、ix9 0 の3行で、2文字しかない id も通ってしまいます。本来の出力は id7 1、id 0、ix9 0 です。
Answer
Wrong
if (re[0] == '.' || re[0] == *s) return here(re + 1, s + 1);
here("id.", "id") は i と d を1文字ずつ照合し、s が終端の '\0' を指した状態で残りのパターン . に来ます。この行は re[0] == '.' だけで一致とみなすので、文字列の終わりを示す '\0' まで1文字として数え、残りのパターンが空になって true を返します。. 以外の文字は '\0' と等しくならないので、この誤りが表に出るのは . のときだけです。
このとき再帰に渡る s + 1 は配列 "id" の終わりの1つ先で、パターンが id. なら読まれずに終わります。id.x のように . の後ろに文字が続くと、次の呼び出しが re[0] == *s でこの位置を読み、配列の外を読む未定義動作になります。
Right
if (*s != '\0' && (re[0] == '.' || re[0] == *s)) return here(re + 1, s + 1);
*s != '\0' を先に調べると、文字列が尽きた位置では . もほかの文字も一致しなくなります。&& は左が偽なら右を評価しないので、終端の先を読むこともありません。文字を1つ消費する箇所には、どれも消費する前に終端かどうかを調べる条件が要ります。* の分岐の while にある *s != '\0' も同じ理由で置かれており、文字を消費しない $ の分岐だけが、終端そのものを一致の条件にしています。