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

3.3

 正規表現

83

数式の場合、掛け算の方が足し算よりも密に結合しますが（

1 + 2

×

3

は、

9

ではなく

7

にな

る）、正規表現の具象構文の場合、

*

演算子の方が連結よりも密に結合し、連結の方が

|

演算

子よりも密に結合します。たとえば、正規表現

abc

*

の場合、

*

は

c

に適用するものと解釈さ

れ ま す（

'abc'

、

'abcc'

、

'abccc'

……）。 こ れ を

abc

全 体 に 適 用 す る に は（

'abc'

、

'abcabc'

……）、括弧を追加して

(abc)

*

とする必要があります。

これらの構文クラスの

#to_s

実装は、必要に応じて

Pattern#bracket

を使って括弧を自

動的に挿入しています。これによって、構造に関する情報を失うことなく、抽象構文木の簡単

な文字列表現を見ることができます。

こうして定義したクラスを使うことで、正規表現を表す木を手作業で構築することができます。

>>

pattern =

Repeat.new(

Choose.new(

Concatenate.new(Literal.new('a'), Literal.new('b')),

Literal.new('a')

)

)

=> /(ab|a)

*

/

もちろん、現実の実装では、手作業ではなくパーサを使って木を構築します。やり方については

「3.3.3　パース」を参照してください。

3.3.2

　意味論

これで正規表現の構文をRuby オブジェクトの木として表現できるようになりましたが、NFAに変

換するにはどうすればよいのでし