« 最もタメになる「初心者用言語」はVerilog HDL! | Main | [minipy] 繰り返しの実装 »

2008.02.05

[minipy] パーサーを作ってみる その1

適当にHOPを参考にしながら、(長門の)minipyを始めた。

とりあえず、改行+EOFはパース出来るようになった。
改行+改行+EOFはまだこれから。

改行+EOFの場合
YUKI.N>python parser.py
[file_input]
[TOK_NEWLINE]TOK_NEWLINE
[TOK_EOF]TOK_EOF
YUKI.N>

改行+改行+EOFの場合
YUKI.N>python parser.py
parse error
[file_input]
[TOK_NEWLINE]TOK_NEWLINE
[TOK_EOF]TOK_NEWLINE
error Token:TOK_NEWLINE, line = 2

パースしていったら、順に構文ツリーを作るようにした。最後にエラーの場合はエラー箇所の表示までできた。プログラミングは楽しい。

Python(というかLL)の凄いところは、適当にかけること。Cだったらツリー構造一つとっても結構悩む。構文ツリーはbranchが2個じゃないので、malloc使うか、文法から最大数を抑え行くか、そこを決めないと先に進まない。

実際に手を動かしてパースをして気がついた事。
再帰下降形のパーサってのは、パースに失敗した時点で、パース全体が失敗したのかどうかが分からないこと。パース全体が失敗したか成功したかを返すのは簡単だけど、どのトークンで失敗になったかを返すのはパースの戻り値だけでは分からない。

だから、パース失敗のエラーメッセージを出すためには、順番に失敗を返して行って全体が失敗だったら、再帰のトレースをしないと行けない。これは面白い。

最初はHOPのサンプルそのままに、成功/失敗だけを返すように書いてういた。上に書いた事にに気がついてからは、パースに失敗したらその場所(トークン)にフラグをつけて、失敗した状態の構文ツリーを返すようにした。全体が失敗したなら、そのツリーを下っていってフラグの付いているトークンを元にエラー表示をさせればどこでgive upしたかがわかる。

こういう変更がPythonだったらすぐに出来るのがうれしい。Cだったら今まで0、1を返していた関数を、構文ツリーの構造体を返す仕様に変更したら結構手間だ。ポインターを返すにしても、引数のポインターに入れるにしても、だれが領域を確保するのかを考えないといけない。ツリーを再帰的に下っていくのもこんな簡単にかけて感激。

def dump_tree(self, depth=0):
 print self.string_for_dump(depth)
 for br in self.branches:
  br.dump_tree(depth + 1)

次は、A | Bの部分を作ろう。それができると、複数の改行+EOFがパース出来るはず。

次の目標はこれだ!
#file_input ::=
# (NEWLINE | statement)* EOF

Pythonいいよ。Python。
minipyいいよ。minipy。

|

« 最もタメになる「初心者用言語」はVerilog HDL! | Main | [minipy] 繰り返しの実装 »

Comments

Post a comment



(Not displayed with comment.)




TrackBack

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

Listed below are links to weblogs that reference [minipy] パーサーを作ってみる その1:

« 最もタメになる「初心者用言語」はVerilog HDL! | Main | [minipy] 繰り返しの実装 »