正規表現の仕組み
正規表現エンジンの基本原理
正規表現エンジンの内部実装は大きく分けて以下の要素から成り立っている:
1. パーサー: 正規表現パターンを解析して内部表現に変換
2. コンパイラ: 内部表現を実行可能な形式に変換
3. マッチャー: 実際に文字列とパターンのマッチングを行う
特に実装方式として主要なものは:
DFA (決定性有限オートマトン) - 高速だが機能制限あり
NFA (非決定性有限オートマトン) - 柔軟だが場合によっては遅い
バックトラッキングNFA - 多くの言語で採用されている方式
ステップ1: 超シンプルなリテラルマッチャーの実装
まずは最も単純な「文字列リテラル」だけをマッチする実装から始めてみる:
code: (typescript)
function simpleMatcher(pattern: string, text: string): boolean {
return text.includes(pattern);
}
// 使用例
console.log(simpleMatcher("abc", "xabcy")); // true
console.log(simpleMatcher("abc", "xabz")); // false
これはまだ正規表現とは言えないが、基本のマッチング機能としては動作する。
ステップ2: 単一文字のワイルドカード対応
次に、単一文字のワイルドカード「.」をサポートしてみる:
code: (typescript)
function wildcardMatcher(pattern: string, text: string): boolean {
if (pattern.length === 0) return true;
if (text.length === 0) return false;
// パターン全体を検査する関数
function matchHere(patIndex: number, txtIndex: number): boolean {
// パターンの最後まで来たらマッチ成功
if (patIndex === pattern.length) return true;
// テキストの最後まで来たのにパターンが残っているならマッチ失敗
if (txtIndex === text.length) return false;
// 現在の文字がマッチするかチェック
if (patChar === '.' || patChar === txtChar) {
// マッチしたら次の文字へ
return matchHere(patIndex + 1, txtIndex + 1);
}
return false;
}
// テキストの各位置からマッチングを試みる
for (let i = 0; i <= text.length - pattern.length; i++) {
if (matchHere(0, i)) return true;
}
return false;
}
// 使用例
console.log(wildcardMatcher("a.c", "abc")); // true
console.log(wildcardMatcher("a.c", "adc")); // true
console.log(wildcardMatcher("a.c", "ac")); // false
これで「.」が任意の1文字にマッチするようになった。だいぶ正規表現っぽくなってきた。
ステップ3: 量指定子「*」の追加
次に、0回以上の繰り返しを表す「*」をサポートする:
code: (typescript)
function starMatcher(pattern: string, text: string): boolean {
// パターン全体を検査する関数
function matchHere(patIndex: number, txtIndex: number): boolean {
// パターンの最後まで来たらマッチ成功
if (patIndex === pattern.length) return true;
// 次の文字が '*' なら特別処理
if (patIndex + 1 < pattern.length && patternpatIndex + 1 === '*') { // '*'の前の文字が0回以上出現するパターン
return matchStar(patternpatIndex, patIndex + 2, txtIndex); }
// テキストの最後まで来たのにパターンが残っているならマッチ失敗
if (txtIndex === text.length) return false;
// 現在の文字がマッチするかチェック
return matchHere(patIndex + 1, txtIndex + 1);
}
return false;
}
// '*'付きのパターンを処理する関数
function matchStar(c: string, patIndex: number, txtIndex: number): boolean {
// 0回以上の出現なので、まず0回でマッチするか試す
if (matchHere(patIndex, txtIndex)) return true;
// 1回以上出現するケースを試す
while (txtIndex < text.length &&
txtIndex++;
// 文字をマッチさせた後、残りのパターンがマッチするか試す
if (matchHere(patIndex, txtIndex)) return true;
}
return false;
}
// テキスト全体に対してマッチを試みる
return matchHere(0, 0);
}
// 使用例
console.log(starMatcher("a*b", "b")); // true
console.log(starMatcher("a*b", "aab")); // true
console.log(starMatcher("a.*c", "abc")); // true
console.log(starMatcher("a.*c", "ac")); // true
これで「*」の繰り返し量指定子が実装できた。バックトラッキングの基本的な動作も含まれている。
ステップ4: 文字クラスの実装
code: (typescript)
function regexMatcher(pattern: string, text: string): boolean {
let patIndex = 0;
// パターンをパースする
function parsePattern(): any {
const result: any = {};
// 文字クラスの処理
result.type = 'charClass';
result.chars = new Set();
patIndex++; // '[' をスキップ
while (patIndex < pattern.length && patternpatIndex !== ']') { patIndex++;
}
if (patIndex < pattern.length) patIndex++; // ']' をスキップ
} else {
// 通常の文字またはワイルドカード
result.type = 'char';
patIndex++;
}
// 量指定子の処理
if (patIndex < pattern.length && patternpatIndex === '*') { result.quantifier = '*';
patIndex++;
} else {
result.quantifier = '';
}
return result;
}
// パースしたパターンに基づいてマッチング
function matchPattern(patternObj: any, txtIndex: number): number[] {
const matches = [];
if (patternObj.type === 'char') {
const c = patternObj.value;
if (txtIndex < text.length && (c === '.' || c === texttxtIndex)) { matches.push(txtIndex + 1);
}
} else if (patternObj.type === 'charClass') {
if (txtIndex < text.length && patternObj.chars.has(texttxtIndex)) { matches.push(txtIndex + 1);
}
}
// 量指定子の処理
if (patternObj.quantifier === '*') {
matches.push(txtIndex); // 0回マッチ
// 1回以上のマッチを再帰的に試す
for (const nextIndex of matches.slice()) {
if (nextIndex < text.length) {
const moreMatches = matchPattern(patternObj, nextIndex);
matches.push(...moreMatches);
}
}
}
}
// 全体のマッチング処理
function matchHere(patIndex: number, txtIndex: number): boolean {
// パターンを最後まで処理したらマッチ成功
if (patIndex >= pattern.length) return txtIndex === text.length;
// パターンを一つパースして処理
const savedPatIndex = patIndex;
const patternObj = parsePattern();
patIndex = savedPatIndex;
const nextPositions = matchPattern(patternObj, txtIndex);
// 次の位置でマッチングを続ける
for (const nextPos of nextPositions) {
patIndex += patternObj.value ? 1 : 0;
if (patternObj.quantifier) patIndex++;
if (matchHere(patIndex, nextPos)) return true;
}
return false;
}
return matchHere(0, 0);
}
// 使用例
console.log(regexMatcher("abc", "a")); // true console.log(regexMatcher("abc", "d")); // false console.log(regexMatcher("abc*d", "abcd")); // true console.log(regexMatcher("abc*d", "ad")); // true 残念ながら上記のコードは不完全で、文字クラスの実装としては正確ではないが、基本的な考え方は示している。
正規表現エンジンの主要実装方式
実用的な正規表現エンジンでは、主に以下の2つの方式が使われている:
1. NFA (非決定性有限オートマトン) - バックトラッキング方式
特徴: Perlから始まり、多くの言語で採用
長所: 豊富な機能、キャプチャグループなどが実装しやすい
短所: 最悪の場合、指数関数的な時間がかかる（ReDoS脆弱性）
代表例: JavaScript, Python, Ruby, PHP, Java
2. DFA (決定性有限オートマトン)
特徴: 常に線形時間で動作する保証がある
長所: 高速で安定したパフォーマンス
短所: 後方参照やルックアヘッドなどの高度な機能が実装しづらい
代表例: grep, awk, lex
最も完全な形の正規表現エンジンになると以下の機能を実装することになる:
メタ文字: ., ^, $, \d, \w など
量指定子: *, +, ?, {n}, {n,m}
文字クラス: [abc], [^abc]
グループと参照: (...), \1 など
選択: a|b
アサーション: (?=...), (?!...), \b など
最適化テクニック
実際の正規表現エンジンでは以下のような最適化も行われている:
1. リテラル前方一致の最適化: パターンが文字リテラルで始まる場合、文字列中からそのリテラルを効率的に検索
2. バイトコード変換: 正規表現をバイトコードに変換して実行速度を上げる
3. キャッシング: 頻繁に使用されるパターンの結果をキャッシュ
4. 線形時間保証: 特定のケースでバックトラッキングを制限
最低限の正規表現エンジン実装
code:typescript
/**
* 最低限の正規表現エンジン実装
* サポート機能:
* - リテラル文字マッチング
* - ワイルドカード(.)
* - 量指定子(*, +, ?)
*/
export class MinimalRegex {
private pattern: string;
private tokens: Token[] = [];
constructor(pattern: string) {
this.pattern = pattern;
this.tokens = this.parsePattern();
}
/**
* 正規表現パターンが文字列にマッチするかを判定
*/
test(text: string): boolean {
return this.match(text, 0, 0);
}
/**
* 再帰的にパターンと文字列をマッチング
*/
private match(text: string, textPos: number, tokenPos: number): boolean {
// すべてのトークンを処理し終えたら成功
if (tokenPos === this.tokens.length) {
return textPos === text.length;
}
// テキスト終了なのにトークンが残っていたら失敗
if (textPos === text.length) {
// ただし、残りのトークンがすべて「0回以上」や「0または1回」の場合は成功
for (let i = tokenPos; i < this.tokens.length; i++) {
const token = this.tokensi; if (token.quantifier !== '*' && token.quantifier !== '?') {
return false;
}
}
return true;
}
let matched = false;
// 現在の文字がトークンにマッチするか確認
if (token.type === 'char') {
matched = token.value === '.' || token.value === texttextPos; } else if (token.type === 'charClass') {
matched = token.chars.has(texttextPos); }
// 量指定子に基づいて処理
switch (token.quantifier) {
case '*': // 0回以上
// 0回のケース: 現在のトークンをスキップ
if (this.match(text, textPos, tokenPos + 1)) {
return true;
}
// 1回以上のケース: 現在の文字がマッチしたら次の文字へ
if (matched && this.match(text, textPos + 1, tokenPos)) {
return true;
}
break;
case '+': // 1回以上
if (matched) {
// 1回マッチ後、同じトークンで次の文字を試す
if (this.match(text, textPos + 1, tokenPos)) {
return true;
}
// または次のトークンへ進む
if (this.match(text, textPos + 1, tokenPos + 1)) {
return true;
}
}
break;
case '?': // 0または1回
// 0回のケース
if (this.match(text, textPos, tokenPos + 1)) {
return true;
}
// 1回のケース
if (matched && this.match(text, textPos + 1, tokenPos + 1)) {
return true;
}
break;
default: // 量指定子なし（1回だけ）
if (matched && this.match(text, textPos + 1, tokenPos + 1)) {
return true;
}
}
return false;
}
/**
* 正規表現パターンをパースしてトークン列に変換
*/
private parsePattern(): Token[] {
const tokens: Token[] = [];
let i = 0;
while (i < this.pattern.length) {
let token: Token;
if (this.patterni === '[') { // 文字クラスの処理
const chars = new Set<string>();
i++; // '[' をスキップ
// 文字クラスの内容を解析
while (i < this.pattern.length && this.patterni !== ']') { chars.add(this.patterni); i++;
}
if (i < this.pattern.length) i++; // ']' をスキップ
token = { type: 'charClass', chars, quantifier: '' };
} else {
// 通常の文字
token = { type: 'char', value: this.patterni, quantifier: '' }; i++;
}
// 量指定子があれば取得
if (i < this.pattern.length && (this.patterni === '*' || this.patterni === '+' || this.patterni === '?')) { token.quantifier = this.patterni; i++;
}
tokens.push(token);
}
return tokens;
}
}
// トークンの型定義
type Token = CharToken | CharClassToken;
interface BaseToken {
quantifier: string; // '', '*', '+', or '?'
}
interface CharToken extends BaseToken {
type: 'char';
value: string;
}
interface CharClassToken extends BaseToken {
type: 'charClass';
chars: Set<string>;
}
// テスト関数
export function testRegex() {
const tests = [
{ pattern: 'abc', text: 'abc', expected: true },
{ pattern: 'abc', text: 'abx', expected: false },
{ pattern: 'a.c', text: 'abc', expected: true },
{ pattern: 'a.c', text: 'adc', expected: true },
{ pattern: 'a.c', text: 'ac', expected: false },
{ pattern: 'a*b', text: 'b', expected: true },
{ pattern: 'a*b', text: 'aab', expected: true },
{ pattern: 'a+b', text: 'b', expected: false },
{ pattern: 'a+b', text: 'aab', expected: true },
{ pattern: 'a?b', text: 'b', expected: true },
{ pattern: 'a?b', text: 'ab', expected: true },
{ pattern: 'a?b', text: 'aab', expected: false },
{ pattern: 'abc', text: 'a', expected: true }, { pattern: 'abc', text: 'd', expected: false }, { pattern: 'abc*d', text: 'abcd', expected: true }, { pattern: 'abc*d', text: 'ad', expected: true }, { pattern: 'a.*c', text: 'abc', expected: true },
{ pattern: 'a.*c', text: 'ac', expected: true },
{ pattern: 'a.*c', text: 'abx', expected: false },
];
for (const test of tests) {
const regex = new MinimalRegex(test.pattern);
const result = regex.test(test.text);
console.log(Pattern: ${test.pattern}, Text: ${test.text}, Expected: ${test.expected}, Result: ${result});
}
}
// 実行
testRegex();
実装の解説と考察
上記で実装した最低限の正規表現エンジンについて特徴を整理してみる:
実装アプローチ
トークナイズ → マッチングの2段階処理
バックトラッキングNFAに近い再帰的マッチング
深さ優先探索で可能な全パターンを試行
サポート機能
リテラル文字: 通常の文字列マッチング
ワイルドカード(.): 任意の1文字にマッチ
量指定子: *(0回以上), +(1回以上), ?(0または1回)
文字クラス(...): 指定した文字集合のいずれかにマッチ 実装上の課題
パフォーマンス: バックトラッキングによる最悪ケースの指数爆発
機能不足: 開始/終了アンカー、後方参照、ルックアヘッドなどが未実装
エスケープ処理: メタ文字のエスケープ処理が未実装
実用的な正規表現エンジンへの拡張ポイント
より実用的な正規表現エンジンを構築するには:
1. パフォーマンス最適化
リテラル先頭文字の高速検索
不要なバックトラッキングの削減
メモ化による計算結果の再利用
2. 機能拡張
グループ化 ()
選択 |
アンカー ^ $
エスケープシーケンス \d \w \s
後方参照 \1 \2
非貪欲マッチング *? +?
3. ユーザビリティ
エラー報告
デバッグ情報
グループキャプチャ
まとめ
正規表現エンジンの実装は、有限オートマトン理論とコンパイラ設計の基本原則に基づいている。実装方式によって処理速度と機能にトレードオフがあり、多くの実用エンジンではバックトラッキングNFAとDFAを使い分けることで性能と機能のバランスを取っている。
実装の難しさは主に:
豊富な表現力と高速なマッチングの両立
エッジケースの適切な処理
効率的なバックトラッキング制御
メモリ使用量の最適化
今回実装した最低限の正規表現エンジンは理解のためには十分だが、実用的なものを作るには多くの最適化と機能拡張が必要になる。ここからさらに機能を追加するのであれば、まずはグループ化と選択演算子の実装から始めるのがよさそう。
人気のある正規表現エンジンとしては、RE2(Google)、PCRE(PHP/Apache)、Oniguruma(Ruby)などがあり、どれも異なる特徴と最適化戦略を持っているので、より深く学ぶのであればこれらのソースコードを読んでみるのもいいかもしれない。