« 昔の自分 | Main | 今日の日記 »

2007.11.19

[HOP]パーサを作ろう その1

何年後かの自分向けメモ

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とか微妙な所で致命的に・・→ 後で書く。

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

|

« 昔の自分 | Main | 今日の日記 »

Comments

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/18154/17120859

Listed below are links to weblogs that reference [HOP]パーサを作ろう その1:

« 昔の自分 | Main | 今日の日記 »