なつたん

何年後かの自分向けメモ

Higher-Order Perlにでてくるparserを自分の物にしたい。
まずはgrammerを定義する。

# grammar definition
expression_clause1 = ('INT', '+', 'expression')
expression_clause2 = ('INT', '*', 'expression')
expression_clause3 = ('(', 'expression', ')')
expression_clause4 = ('INT')

grammar = {'expression' : (expression_clause1, expression_clause2, expression_clause3, expression_clause4)}

リファレンスとか、デリファレンスとか気にしないで良いので、perlよりはわかりやすくなっていると思う。電卓の文法だと、exressionの代わりに、exprとかtermが来る。

最初の関数is_nonterminalは簡単で、引数がterminalかnonterminalかを判断する。

def is_nonterminal (symbol):
　　return grammar.has_key(symbol)

is_interestingの方は難しくて、別の章で定義してあるツリーの検索ルーチンから呼ばれる。directory walkingのようにツリー構造の構文を順に検索しながら、目的のパターンと一致したかを返す。このとき、ツリー構造の検索には深さ優先ではなく、幅優先を使う。

一般的にツリー構造を検索していく場合、再帰しながら深さ優先で下っていく方が簡単。ただ、深さ優先には無限ループに入ってしまう欠点がある（ディレクトリだと、ループ構造のシンボリックリンクがそう）。幅優先だと、検索の効率（メモリの使用量なども）は悪いが、検索対象が存在するなら必ず検索に成功する。30代半ばにして始めて知る事実。

これがparseしたいtoken列がこんな感じとする。（これはlexerから渡されるtokenのリスト）

target = ('(', 'INT', '*', '(', 'INT', '+', 'INT', ')', ')' )

これをtargetとして、ツリー検索ルーチンがこんなリストを渡してくる。

1回目：'expression' → これはparerに与えられた、最初はどこから始めるかという値。expressionはnonterminalなので(True)返しとく
2回目：'INT + expression' → 1回目で(True)が返ったのでツリーを深く検索していく。先頭が（じゃないから(False)を返す。
3回目：'INT * expression' → 最初のgrammerで定義されたexpressionが順番に渡されている。先頭が（じゃないから(False)を返す。
4回目：'( expression )' → 最初が（で一致、次のexpressionが nonterminalなので、（True)を返す。
5回目：'( INT + expression )' → 4回目に(True)を返したので、ツリーを一歩深くする。expressionが、'INT + expression'になっているのは、2回目と同じ理由。
6回目：'( INT * expression )' → 3回目と同じく( expression )のexpressionが、INT * expressionに展開される。今度は、*まで一致していて、expressionがnonterminalなので(True)を返し、さらに深く検索を続ける
7回目( INT * INT + expression )：以下同様

最後に( INT * ( INT + INT ) ) で、parse終了。

def is_interesting (sentential_form):
　　for i in range(len(sentential_form)):
　　　　if is_nonterminal(sentential_form[i]):
　　　　　　return (True)
　　　　if i >= len(target) :
　　　　　　return (False)
　　　　if sentential_form[i] != target[i]:
　　　　　　return (False)

　　return sentential_form

rangeが痒いところに手が届いてくれてうれしい。
C言語の文字列は、+1とか、-1とか微妙な所で致命的に・・→ 後で書く。

次は、ツリーを検索するアルゴリズムを追おう。
ソースはここ。