式の構文解析

豊四季タイニーBASICのパーサー(式の構文解析をやる関数iexp)がどういう理屈で成り立っているのかを人に説明しなければならない事態に直面してしまった。正直、パーサーは体で覚えたやりかたをもとに試行錯誤で動かしたものだから理屈なんか考えたこともない。この1箇月あまり、もうちゃんと動いているものがどうして動くのかを調べるというきわめてややこしい状況におかれている。

古典的な文献は逆ポーランド記法に書き換えて計算する方法を説明している。念のためにその理屈をC言語で書いてみたらとんでもなく冗長で醜悪なソースが出来上がった。たぶんこれはアセンブリ言語で書くことを前提としているか、特定の言語を想定しない学術的な解法だと思う。少なくともボクが書いたやつはこれじゃない。

古典的ではない文献を調べると、パーサーの種類は大まかにふたつ、細かく7つくらいあって、どうやらその中のひとつに該当するようだ。どれだかはまだわからないから何とか法ですと言い切れないが、どれだかを調べるうちにだんだん理屈がわかってきた。またわからなくなってしまう前にこのもやもやっとした感じを書いておこうと思う。

式の計算で解決しなければならない課題はふたつ。ひとつは括弧が使われていない式における演算子の優先順位。もうひとつは括弧があって式の中に式が埋め込まれた状況の整理。

括弧が使われていない式における演算子の優先順位はこう解決する。まず計算の優先順位によって関数を区別する。たとえば、加減算をする関数、乗除算をする関数といった具合。次に、優先順位の低い関数から高い関数を呼び出す形を構成する。そして、それぞれの関数の中で、より優先順位の高い計算に出くわしたら、上の関数を呼び出し、答えを受け取って計算を続ける。この理屈でただの計算をするひとつの関数を完成させる。実をいうと自分では、とうていスマートとはいいがたい力ずくのやりかただと思っていたが、優先順位が逆のとき計算の過程をスタックに退避して、より優先順位の高い計算を実行し、それで逆が解決したら復帰して続けるという、たいへん合理的な仕組みだと判明した。

括弧があって式の中に式が埋め込まれた状況はこう整理する。とりあえずただの計算をする関数で計算を開始する。そして、括弧に出くわしたら括弧が閉じるまでの間を、ただの計算をする関数に計算してもらう。つまり、括弧に出くわすたびに再帰的呼び出しをする。これで計算が完了する。

豊四季タイニーBASICのパーサーはたぶんこんな理屈で成り立っている。現在、本当にそうなのかどうかをソースにあたっている。動いているパーサーに動く理由を当てはめてみるという、再帰的な作業の真っ最中。

広告
カテゴリー: TinyBASIC パーマリンク

式の構文解析 への2件のフィードバック

  1. kousoz より:

    どうもお久しぶりです、kousozです。お変わりはないでしょうか?

    TinyBasicですね、メモリをほとんど消費しないのでワンチップマイコンに組み込んで
    ロボット等の制御をする目的には非常に都合がよさそうですね。
    私も似たようなものを作ってロボットに組み込みましたが、余計な機能をあちこちに組み込んでしまったせいか簡単に手直しもメンテナンスもできない代物になってしまいました。
    やはりシンプルイズベストですね、少し方向性を変えて検討してみようと思います。

    それではお大事に。

    • vintagechips より:

      こんにちは。おかげさまで元気です。はいタイニーBASICです。電子工作の一環としてPIC24FやArduinoで動かすために作りました。メモリはRAMが2Kバイトほど必要で、パソコンやタブレットならほとんど消費しない感じでしょうが、電子工作だといっぱいいっぱいです。只今ドブズ医師のもとでダイエット中です。

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中