Namaran

Code daily. Without assist.

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' も同じ理由で置かれており、文字を消費しない $ の分岐だけが、終端そのものを一致の条件にしています。