アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

80

3

章 最も単純なコンピュータ

3.3

　正規表現

非決定性と自由移動が、シミュレーションを妨げることなく、有限オートマトンの表現力を高めるの

を見てきました。ここでは、その重要かつ実用的な応用である正規表現マッチングについて見ていき

ましょう。

正規表現（regular expression）は文字列をマッチングさせるときのパターンを書くための言語を提供

します。正規表現の例をいくつか挙げます。

●

hello

は文字列

'hello'

にのみマッチします。

●

hello|goodbye

は文字列

'hello'

と

'goodbye'

にマッチします。

●

(hello)

*

は 文 字 列

'hello'

、

'hellohello'

、

'hellohellohello'

などと空 文 字 列に

マッチします。

この章では、正規表現を常に文字列全体にマッチするものと見なしています。現実世界にお

ける正規表現の実装では通常、正規表現を文字列の部分マッチングに使っています。文字列

全体にマッチさせたいときには、追加の構文を使う必要がありま

す。

たとえば、この章における正規表現

hello|goodbye

を

Ruby

で書く場合、マッチングを文

字列の開始（

\A

）と終了（

\z

）に固定するため、

/\A(hello|goodbye)\z/

と書きます。

正規表現と文字列が与えられたとき、その文字列がその正規表現にマッチするかを判断するプログ

ラムはどのように書けるのでしょうか。Rubyを含むほとんどのプログラミング言語には正規表現のサ

ポートがすで