83

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

Linux ボックスで実行するためにこれを書いていた場合、flex/bison を使用できます。8 ビット プラットフォームに限定したので、パーサーをどのようにコーディングすればよいでしょうか。

4

4 に答える 4

237

パーサーを簡単にコーディングする方法が必要な場合、またはスペースが限られている場合は、再帰降下パーサーを手動でコーディングする必要があります。これらは基本的にLL (1) パーサーです。これは、Basic と同じくらい「単純」な言語で特に効果的です。（私は70年代にこれらのいくつかをやりました！）。幸いなことに、これらにはライブラリ コードが含まれていません。あなたが書いたものだけです。

すでに文法を知っていれば、コーディングは非常に簡単です。まず、左再帰規則 (例えば、 X = XY ) を取り除かなければなりません。これは一般的に非常に簡単に実行できるので、演習として残します。(リスト形成規則ではこれを行う必要はありません。以下の説明を参照してください)。

次に、次の形式の BNF ルールがある場合:

 X = A B C ;

ルール (X、A、B、C) の各項目に対して、「対応する構文構造を見ました」というブール値を返すサブルーチンを作成します。X の場合、次のようにコーディングします。

subroutine X()
     if ~(A()) return false;
     if ~(B()) { error(); return false; }
     if ~(C()) { error(); return false; }
     // insert semantic action here: generate code, do the work, ....
     return true;
end X;

A、B、Cも同様です。

トークンが端末の場合、端末を構成する文字列の入力ストリームをチェックするコードを記述します。たとえば、数値の場合、入力ストリームに数字が含まれていることを確認し、入力ストリーム カーソルを数字を超えて進めます。これは、単純にバッファ スキャン ポインタを進めたり進めなかったりすることによって、バッファから解析する場合 (BASIC の場合、一度に 1 行を取得する傾向があります) の場合に特に簡単です。このコードは、基本的にパーサーのレクサー部分です。

BNF ルールが再帰的である場合でも、心配する必要はありません。再帰呼び出しをコーディングするだけです。これは、次のような文法規則を処理します。

T  =  '('  T  ')' ;

これは次のようにコーディングできます。

subroutine T()
     if ~(left_paren()) return false;
     if ~(T()) { error(); return false; }
     if ~(right_paren()) { error(); return false; }
     // insert semantic action here: generate code, do the work, ....
     return true;
end T;

代替の BNF ルールがある場合:

 P = Q | R ;

次に、別の選択肢を使用して P をコーディングします。

subroutine P()
    if ~(Q())
        {if ~(R()) return false;
         return true;
        }
    return true;
end P;

リスト形成規則に遭遇することがあります。これらは再帰的に残される傾向があり、このケースは簡単に処理できます。基本的な考え方は、再帰ではなく反復を使用することです。これにより、これを「明白な」方法で行う無限の再帰を回避できます。例：

L  =  A |  L A ;

これは、反復を使用して次のようにコーディングできます。

subroutine L()
    if ~(A()) then return false;
    while (A()) do { /* loop */ }
    return true;
end L;

この方法で、1 日か 2 日で数百の文法規則をコーディングできます。記入すべき詳細は他にもありますが、ここでの基本事項で十分です。

スペースが非常に限られている場合は、これらのアイデアを実装する仮想マシンを構築できます。それは、8K 16 ビット ワードが得られるものだった 70 年代に私が行ったことです。

これを手動でコーディングしたくない場合は、本質的に同じものを生成するメタコンパイラ( Meta II ) を使用して自動化できます。これらは驚異的な技術的な楽しみであり、大きな文法であっても、実際にこれを行うのにすべての作業が必要です.

2014 年 8 月:

「パーサーで AST をビルドする方法」というリクエストが多く寄せられます。この回答を本質的に詳しく説明する詳細については、私の他の SO 回答https://stackoverflow.com/a/25106688/120163を参照してください。

2015 年 7 月:

単純な式評価器を書きたいと思っている人はたくさんいます。上記の「ASTビルダー」リンクが示唆するのと同じ種類のことを行うことでこれを行うことができます。ツリーノードを構築する代わりに、算術を行うだけです。この方法で実行された式評価器を次に示します。

2021 年 10 月:

この種のパーサーは、再帰的降下がうまく処理できない複雑さが言語にない場合に機能することに注意してください。私は 2 種類の複雑さを提供します: a) 本当にあいまいな解析 (たとえば、フレーズを解析する複数の方法) および b) 任意に長い先読み (たとえば、定数に制限されない)。これらの場合、再帰的降下は地獄への再帰的降下に変わり、それらを処理できるパーサージェネレーターを取得する時が来ました。GLR パーサー ジェネレーターを使用して 50 以上の異なる言語を処理するシステムについては、私の略歴を参照してください。

于 2010-02-25T19:00:35.913 に答える
60

ATmega328pを対象とした単純なコマンド言語用のパーサーを実装しました。このチップには 32k の ROM と 2k の RAM しかありません。RAM は間違いなくより重要な制限です。まだ特定のチップに縛られていない場合は、できるだけ多くの RAM を搭載したものを選択してください。これにより、あなたの人生はずっと楽になります。

最初はflex/bisonの使用を検討しました。私は次の 2 つの主な理由から、このオプションに反対することにしました。

  • デフォルトでは、Flex と Bison は、avr-libc では利用できないか、同じように動作しないいくつかの標準ライブラリ関数 (特に I/O 用) に依存しています。サポートされている回避策があると確信していますが、これは考慮に入れる必要がある追加の作業です。
  • AVR にはハーバード アーキテクチャがあります。C はこれを考慮して設計されていないため、定数変数でさえデフォルトで RAM にロードされます。フラッシュとEEPROMにデータを保存してアクセスするには、特別なマクロ/関数を使用する必要があります。Flex と Bison は比較的大きなルックアップ テーブルをいくつか作成するため、RAM をすぐに使い果たしてしまいます。私が間違っていない限り (その可能性は十分にあります)、特別な Flash & EEPROM インターフェイスを利用するには、出力ソースを編集する必要があります。

Flex & Bison を拒否した後、他のジェネレーター ツールを探しに行きました。ここに私が考えたいくつかがあります：

ウィキペディアの比較も参照してください。

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

解析には、再帰降下パーサーを使用しました。Ira Baxterはすでにこのトピックを十分にカバーしていると思いますし、オンラインにはたくさんのチュートリアルがあります。

私の字句解析器では、すべての端末の正規表現を作成し、同等のステート マシンを図式化して、状態goto間をジャンプするために を使用して 1 つの巨大な関数として実装しました。これは面倒でしたが、結果はうまくいきました。余談ですが、gotoはステート マシンを実装するための優れたツールです。すべての状態で、関連するコードのすぐ隣に明確なラベルを付けることができます。関数呼び出しや状態変数のオーバーヘッドはなく、可能な限り高速です。C には、静的ステート マシンを構築するための優れた構造がありません。

考えるべきこと: レクサーは実際にはパーサーの特殊化にすぎません。最大の違いは、ほとんどのプログラミング言語には (ほとんどの場合) 文脈自由文法があるのに対し、通常は通常の文法で字句解析に十分であるということです。したがって、レクサーを再帰降下パーサーとして実装したり、パーサー ジェネレーターを使用してレクサーを作成したりすることを妨げるものは何もありません。通常、より専門的なツールを使用するほど便利ではありません。

于 2010-02-26T00:15:34.390 に答える
11

Linux で flex/bison をそのネイティブ gcc とともに使用してコードを生成し、それを組み込みターゲット用に AVR gcc でクロスコンパイルできます。

于 2010-02-11T16:59:58.297 に答える
2

GCC はさまざまなプラットフォームにクロスコンパイルできますが、コンパイラを実行しているプラ​​ットフォームで flex と bison を実行します。コンパイラがビルドする C コードを吐き出すだけです。テストして、結果の実行可能ファイルが実際にどれくらい大きいかを確認します。ターゲットにクロスコンパイルする必要があるランタイムライブラリ（libfl.aなど）があることに注意してください。

于 2010-02-11T17:04:11.810 に答える