« カーニハン先生のありがたいお言葉 | Main | 今日の日記 »

2008.02.07

[minipy] パーサを作ろう その2

0回以上の繰り返しは、結局ループで処理した。
print 1 + 1 がそれっぽくパース完了

YUKI.N>python parser.py
[file_input]
 [nl_or_st_star]
  [nl_or_st]
   [statement]
    [print_stmt]
     [TOK_KW_PRINT]TOK_KW_PRINT
     [expression]
      [a_expr]
       [TOK_LITERAL_INT]TOK_LITERAL_INT (1)
       [p_or_n_int_star]
        [p_or_n_int]
         [p_or_n]
          [TOK_PLUS]TOK_PLUS
         [TOK_LITERAL_INT]TOK_LITERAL_INT (1)
    [TOK_NEWLINE]TOK_NEWLINE
  [nl_or_st]
   [TOK_NEWLINE]TOK_NEWLINE
  [nl_or_st]
   [TOK_NEWLINE]TOK_NEWLINE
 [EOF]TOK_EOF
YUKI.N>

文法の定義はこれ
# 特定のトークンを見つけるパーサ
eoi = parser.end_of_input()
nl = parser.lookfor('TOK_NEWLINE')
lk_print = parser.lookfor('TOK_KW_PRINT')
int = parser.lookfor('TOK_LITERAL_INT')
plus = parser.lookfor('TOK_PLUS')
minus = parser.lookfor('TOK_MINUS')

#a_expr ::= integer ( ( "+" | "-" ) integer)*
p_or_n = parser.alt('p_or_n', [plus, minus])
p_or_n_int = parser.cat('p_or_n_int', [p_or_n, int])
p_or_n_int_star = parser.star('p_or_n_int_star', p_or_n_int)
a_expr = parser.cat('a_expr', [int, p_or_n_int_star])

#expression ::= a_expr
expression = parser.cat('expression', [a_expr,])

#print_stmt ::= "print" expression_list_with_comma
print_stmt = parser.cat('print_stmt', [lk_print, expression])

#statement ::= print_stmt NEWLINE
statement = parser.cat('statement', [print_stmt, nl])

#file_input ::= (NEWLINE | statement)* EOF
nl_or_st = parser.alt('nl_or_st', [nl, statement])
nl_or_st_star = parser.star('nl_or_st_star', nl_or_st)
entire_input = parser.cat('file_input',[nl_or_st_star, eoi])

最後のentire_inputに対して、entire_input.parse(tk)で引数のTokenizerからトークンを読み込んでパースする。

mini とはいえ、すべての構文でこれを手書きするのは気が進まないので良い方法を考えよう。BNFを読み込んでこの形式に変更し、importするのがそこそこ楽そうな気がするんだが、気になる点が2つ

・上のやり方だと基本的に前方参照で文法を解決しないいけないので、いったん全部の文法を読み込んでから、順番を変えていかないといけない。言い方を変えると、文法はentire_inputが一番最初にあるけど、ソースに落とすときには一番最後でないとダメ。
・変換をするために、BNFをパースしないといけない。何がなんだか分からなくなる可能性が高い

一瞬S式という単語が浮かんだが、気にしないことにした。

HOPを見ると、演算子のオーバーロードを利用して見やすくしろ、とのこと。

#a_expr ::= integer ( ( "+" | "-" ) integer)*
p_or_n = parser.alt('p_or_n', [plus, minus])
p_or_n_int = parser.cat('p_or_n_int', [p_or_n, int])
p_or_n_int_star = parser.star('p_or_n_int_star', p_or_n_int)
a_expr = parser.cat('a_expr', [int, p_or_n_int_star])

同じ事が、これくらいで表現できるとうれしい
a_expr = int + ( (plus | minus) + int) >> star

ちょっと、演算子のオーバーロード勉強してくる。

|

« カーニハン先生のありがたいお言葉 | Main | 今日の日記 »

Comments

Post a comment



(Not displayed with comment.)




TrackBack

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

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

« カーニハン先生のありがたいお言葉 | Main | 今日の日記 »