37

単純なレクサーとパーサーを作成するたびに、同じ質問に出くわします: レクサーとパーサーはどのように通信する必要があるのでしょうか? 私は4つの異なるアプローチを見ています：

  1. lexer は、入力文字列全体を積極的にトークンのベクトルに変換します。これが完了すると、ベクターはパーサーに渡され、パーサーがツリーに変換します。これは実装する最も簡単なソリューションですが、すべてのトークンがメモリに格納されるため、多くのスペースが無駄になります。

  2. レクサーはトークンを見つけるたびに、パーサーで関数を呼び出し、現在のトークンを渡します。私の経験では、これは、パーサーが LALR パーサーのようなステート マシンとして自然に実装できる場合にのみ機能します。対照的に、再帰降下パーサーではまったく機能しないと思います。

  3. パーサーがトークンを必要とするたびに、レクサーに次のトークンを要求します。これは、キーワードにより C# で実装するのは非常に簡単ですがyield、それを持たない C++ では非常に困難です。

  4. レクサーとパーサーは、非同期キューを介して通信します。これは一般に「プロデューサー/コンシューマー」というタイトルで知られており、レクサーとパーサーの間の通信を大幅に簡素化する必要があります。また、マルチコアで他のソリューションよりも優れていますか? それとも、レキシングはあまりにも些細なことですか？

私の分析は正しいですか？私が考えていない他のアプローチはありますか？実際のコンパイラでは何が使用されていますか? Eric Lippert のようなコンパイラ ライターがこの問題に光を当てることができれば、本当に素晴らしいことです。

4

5 に答える 5

12

上記の多くを間違っていると分類するつもりはありませんが、いくつかの項目は誤解を招くと思います。

  1. パーサーを実行する前に入力全体を字句解析することには、他のオプションよりも多くの利点があります。実装はさまざまですが、一般に、この操作に必要なメモリは問題になりません。特に、コンパイル エラーを報告するために必要な情報の種類を考慮する場合はそうです。

    • 利点
      • エラー報告中に利用可能な情報が増える可能性があります。
      • 構文解析の前に字句解析を実行できるように作成された言語は、コンパイラの指定と作成が容易です。
    • 欠点
      • 一部の言語では、構文解析フェーズの前に操作できないコンテキスト依存のレクサーが必要です。

    言語の実装に関する注意:これは私の好みの戦略です。コードが分離可能になり、その言語の IDE を実装するための変換に最適だからです。

    パーサーの実装に関する注意:この戦略でのメモリ オーバーヘッドに関して、ANTLR v3 で実験しました。C ターゲットはトークンごとに 130 バイト以上を使用し、Java ターゲットはトークンごとに約 44 バイトを使用します。変更された C# ターゲットを使用して、トークン化された入力をトークンあたりわずか 8 バイトで完全に表現できることを示しました。これにより、この戦略は非常に大きなソース ファイルでも実用的になります。

    言語設計に関する注意:新しい言語を設計する人には、最終的に参照コンパイラとして選択するかどうかに関係なく、この構文解析戦略を可能にする方法で設計することをお勧めします。

  2. ＃3のように、「プル」パーサーとして一般的に説明されているものの「プッシュ」バージョンについて説明したようです。私の仕事は常に LL 構文解析に重点を置いていたので、これは私にとって実際には選択肢ではありませんでした。＃3以上の利点がある場合は驚くでしょうが、それらを除外することはできません.

  3. これの最も誤解を招く部分は、C++ に関する記述です。C++ で反復子を適切に使用すると、このタイプの動作に非常に適したものになります。

  4. キューは、仲買人との #3 の再ハッシュのように見えます。独立した操作を抽象化すると、モジュール式のソフトウェア開発などの分野で多くの利点が得られますが、配布可能な製品オファリングのレクサー/パーサーのペアはパフォーマンスに非常に敏感です。 . これよりもオプション #3 を使用することをお勧めします。

    マルチコア解析に関する追加の注意事項: 単一のコンパイル ユニットのコンパイルの最初のレクサー/パーサー フェーズは、一般に並列化できません。また、異なるコンパイル ユニットで並列コンパイル タスクを単純に実行することがいかに簡単かを考慮する必要もありません (たとえば、ソース ファイルごとに 1 つのレクサー/パーサー操作を行い、ソース ファイル間で並列化しますが、任意のファイルに対して 1 つのスレッドのみを使用します)。

その他のオプションについて: 広く使用されることを意図したコンパイラ (商用またはその他) の場合、一般に実装者は、ターゲット言語の制約の下で最高のパフォーマンスを提供する解析戦略と実装を選択します。一部の言語 (Go など) は単純な LR 解析戦略で非常に高速に解析できますが、「より強力な」解析戦略 (つまり、不要な機能) を使用すると、処理が遅くなるだけです。他の言語 (C++ など) は、一般的なアルゴリズムで解析するのが非常に困難または不可能であるため、低速ですがより強力で柔軟なパーサーが使用されます。

于 2012-07-09T15:31:46.543 に答える
5

ここには黄金律はないと思います。要件はケースごとに異なる場合があります。したがって、合理的な解決策も異なる場合があります。私自身の経験からあなたの選択肢についてコメントさせてください。

  1. 「トークンのベクトル」。このソリューションでは、メモリ フットプリントが大きくなる可能性があります。多くのヘッダーを含むソース ファイルをコンパイルすることを想像してください。トークン自体を保存するだけでは不十分です。エラー メッセージには、ファイル名と行番号を含むコンテキストが含まれている必要があります。lexer がパーサーに依存する場合があります。合理的な例: ">>" - これはシフト演算子ですか、それともテンプレートのインスタンス化の 2 つのレイヤーを閉じていますか? 私はこのオプションに反対票を投じます。

  2. (2,3)。「ある部分が別の部分を呼び出す」。私の印象は、より複雑なシステムはより単純なシステムを呼び出すべきだというものです。レクサーはもっと単純だと思います。これは、パーサーがレクサーを呼び出す必要があることを意味します。C# が C++ より優れている理由がわかりません。文法ベースのパーサーから呼び出されるサブルーチン (実際にはこれは複雑なクラスです) として C/C++ lexer を実装しました。この実装では問題はありませんでした。

  3. 「通信プロセス」。これはやり過ぎのように思えます。このアプローチには何も問題はありませんが、物事をシンプルに保つ方が良いのでしょうか? マルチコアの側面。単一のファイルをコンパイルすることは、比較的まれなケースです。各コアに独自のファイルをロードすることをお勧めします。

lexer と parser を組み合わせる他の合理的なオプションは見当たりません。

私は、ソフトウェア プロジェクトのソースをコンパイルすることを考えて、これらのノートを書きました。短いクエリ リクエストを解析することはまったく別のことであり、その理由は大きく異なる可能性があります。私の答えは、私自身の経験に基づいています。他の人はこれを違った見方をするかもしれません。

于 2012-07-09T16:04:14.143 に答える
3

レクサーとパーサーの関係は、コルーチンの最も一般的なケースよりも単純です。これは、一般に通信が一方向であるためです。パーサーは情報をレクサーに送り返す必要はありません。これが、熱心な生成の方法が機能する理由です (多少のペナルティはありますが、入力を早期に破棄できることを意味します)。

見てきたように、レクサーまたはパーサーのいずれかを再呼び出し可能なスタイルで記述できる場合、もう一方は単純なサブルーチンとして扱うことができます。これは常にソース コード変換として実装でき、ローカル変数はオブジェクト スロットに変換されます。

C++ にはコルーチンの言語サポートがありませんが、ライブラリサポート、特にfiberを利用することは可能です。Unixsetcontextファミリーは 1 つのオプションです。もう 1 つは、マルチスレッドを使用するが、同期キューを使用することです (基本的にはシングルスレッドですが、制御の 2 つのスレッドを切り替えます)。

于 2012-07-09T15:13:59.717 に答える
2

また、＃1については、たとえばエラーが発生した場合など、トークンを必要としないlexトークンを検討します。さらに、メモリまたはI/O帯域幅が不足する可能性があります。最善の解決策は、バイソンなどのツールによって生成されたパーサーによって採用されるものであると思います。パーサーは、次のトークンを取得するためにレクサーを呼び出します。スペース要件とメモリ帯域幅要件を最小限に抑えます。

#4それだけの価値はありません。字句解析と構文解析は本質的に同期しています。通信のコストを正当化するのに十分な処理が行われていないだけです。さらに、通常、複数のファイルを同時に解析/lexします。これにより、すべてのコアを一度に最大化できます。

于 2012-07-09T15:26:57.057 に答える
1

進行中のおもちゃの buildsystem プロジェクトでそれを処理する方法は、「ファイル リーダー」クラスを関数で持つことbool next_token(std::string&,const std::set<char>&)です。このクラスには 1 行の入力が含まれます (行番号付きのエラー報告用)。std::stringこの関数は、トークンを入れるための参照とstd::set<char>、「トークン終了」文字を含むを受け入れます。私の入力クラスはパーサーとレクサーの両方ですが、さらに凝ったものが必要な場合は簡単に分割できます。そのため、解析関数は呼び出すだけnext_tokenで、非常に詳細なエラー出力を含めて、その機能を実行できます。

逐語的な入力を保持する必要がある場合は、読み取った各行を avector<string>または何かに保存する必要がありますが、各トークンを個別に保存したり、y を二重に保存したりしないでください。

私が話しているコードはここにあります：

https://github.com/rubenvb/Ambrosia/blob/master/libAmbrosia/Source/nectar_loader.cpp

(関数を検索し::next_tokenて、すべてが始まる場所)extract_nectar

于 2012-07-09T15:12:31.763 に答える