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

94

3

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

end

}

end

end

繰り返しになりますが、規則の順序は演算子の優先順位を反映しています。

|

演算子は最も結

合がゆるいため、最初に

choose

規則を書いています。優先順位の高い演算子の規則ほど、

文法の下のほうに登場します。

これで正規表現をパースするのに必要なものはすべてそろいました。正規表現を抽象構文木に変換

して、文字列をマッチさせましょう。

>>

require 'treetop'

=> true

>>

Treetop.load('pattern')

=> PatternParser

>>

parse_tree = PatternParser.new.parse('(a(|b))

*

')

=> SyntaxNode+Repeat1+Repeat0 offset=0, "(a(|b))

*

" (to_ast,brackets):

SyntaxNode+Brackets1+Brackets0 offset=0, "(a(|b))" (to_ast,choose):

SyntaxNode offset=0, "("

Sy

ntaxNode+Concatenate1+Concatenate0 offset=1, "a(|b)" (to_ast,first,rest):

SyntaxNode+Literal0 offset=1, "a" (to_ast)

SyntaxNode+Brackets1+Brackets0 offset=2, "(|b)" (to_ast,choose): ...