[解決済み] 8ビット組込みシステムで使えるFlex/Bisonのようなパーサーを書きたい

質問

私はAVRマイクロコントローラの練習として、avr-gccツールチェーンを使用してC言語で簡単なBASICのような言語のための小さなインタプリタを書いています。

もし私がこれを Linux ボックス上で実行するために書いていたなら、flex/bison を使用することができました。8 ビット プラットフォームに自分自身を制限している今、パーサーをどのようにコーディングしたらよいでしょうか。

どのように解決するのですか?

をターゲットとした簡単なコマンド言語のパーサーを実装しています。 ATmega328p . このチップは 32k の ROM とたった 2k の RAM を持っています。 もしあなたがまだ特定のチップに縛られていないのなら、できるだけ多くのRAMを持つものを選んでください。 そうすれば、あなたの生活はずっと楽になるでしょう。

当初、私は flex/bison を使用することを考えました。 しかし、2 つの大きな理由から、この選択肢を断念しました。

• デフォルトでは、Flex & Bisonは、avr-libcでは利用できないか、同じように動作しないいくつかの標準ライブラリ関数（特にI/O）に依存しています。 サポートされている回避策があることは確かですが、これは考慮する必要がある余分な労力です。
• AVR には ハーバード アーキテクチャ . C 言語はこれを考慮した設計になっていないため 定数変数でさえもデフォルトでRAMにロードされます . にデータを保存したりアクセスしたりするには、特別なマクロや関数を使用しなければなりません。 フラッシュ と EEPROM . Flex & Bisonは、いくつかの作成 比較的 を作成し、これらはかなり早くあなたのRAMを消費します。 私が間違っていなければ (これはかなり可能性があります)、特別なフラッシュおよび EEPROM インターフェイスを利用するために、出力ソースを編集する必要があります。

Flex & Bison を却下した後、他のジェネレーター ツールを探しました。 以下は、私が検討したいくつかのツールです。

• レモン
• ラジェル
• re2c

また、次のようなものも見てみましょう。 ウィキペディアの比較 .

最終的には、レキサーとパーサーの両方を手作業でコーディングすることになりました。

パースには再帰的降下パーサーを使いました。 私が思うに アイラ・バクスター はすでにこのトピックを十分にカバーしていますし、オンラインにもたくさんのチュートリアルがあります。

私のレキサーのために、私はすべての端末の正規表現を書き上げ、同等のステートマシンを図式化し、それを1つの巨大な関数として goto を使用して 1 つの巨大な関数として実装しました。 これは面倒な作業でしたが、結果的にはとてもうまくいきました。 余談ですが goto はステートマシンを実装するための素晴らしいツールです。すべてのステートに関連するコードのすぐ隣に明確なラベルを付けることができ、関数呼び出しやステート変数のオーバーヘッドもありませんし、得られるものと同じくらい高速です。 C 言語は、静的ステートマシンを構築するために、これ以上優れた構成を持っていません。

レキサーは本当にパーサーの特殊化です。 最大の違いは、ほとんどのプログラミング言語が (ほとんど) 文脈自由文法であるのに対し、字句解析には通常、通常の文法で十分であることです。 ですから、レキサーを再帰的降下パーサーとして実装したり、パーサージェネレーターを使ってレキサーを書いたりすることを妨げるものは何もありません。 ただ、より専門的なツールを使用するほど便利ではないのが普通です。