古典的なコンパイラ理論では、最初の 2 つのフェーズは字句解析と構文解析です。彼らはパイプラインにいます。字句解析は、トークンを解析の入力として認識します。
しかし、字句解析では正しく認識しにくいケースに出くわしました。たとえば、C++ テンプレートに関する次のコード:
map<int, vector<int>>
これ>>は、「通常の」字句解析ではビットごとの右シフトとして認識されますが、正しくありません。この種の文法の処理を 2 つのフェーズに分割するのは難しいと思います。字句解析作業は構文解析フェーズで行う必要があります>>。これは、単純な字句規則だけでなく、文法を正しく解析することが依存しているためです。
この問題についての理論と実践を知りたいです。また、C++ コンパイラがこのケースをどのように処理するのか知りたいですか?
C++ 標準では、構文解析段階の前に、実装で字句解析を実行してトークンのストリームを生成する必要があります。字句解析規則に従って、2 つの連続>する文字 (後に が続かない) は常に 1 つのトークン=として解釈されます。>>C++ 標準で提供される文法は、これらのトークンに関して定義されます。
特定のコンテキスト (テンプレート ID 内で a を予期する場合など) では、実装が2 として>解釈する必要があるという要件は、文法内で指定されていません。代わりに、ルールは特別なケースとして指定されます。>>>
14.2 テンプレートの特殊化の名前 [temp.names] ###
名前ルックアップ (3.4) の後、名前がテンプレート名であるか、operator-function-idまたはliteral-operator-idがオーバーロードされた関数のセットを参照し、そのメンバーのいずれかが関数テンプレートであることがわかります。 a
<、 the<は常にtemplate-argument-listの区切り文字として使用され、小なり演算子として使用されることはありません。template-argument-list を解析するとき、ネストされていない最初の>ものが大なり演算子ではなく終了区切り文字として使用されます。同様に、ネストされていない最初のトークンは、>>連続しているが別個の 2 つのトークンとして扱われ、その最初のトークンがtemplate-argument-list>の末尾として取得され、 テンプレート ID。[ 注:>この置換規則によって生成される 2 番目のトークンは、それを囲む template-id構造を終了させるか、別の構造 (キャストなど) の一部である可能性があります。
特定のコンテキストでは、template-argument-list<内のとして解釈する必要があるという前述の規則に注意してください。これは、構文解析を明確にするためにコンテキストを必要とする構成の別の例です。<
C++ の文法には、構文解析中にコンテキストに関する情報がないと解決できないようなあいまいさが多数含まれています。これらの中で最もよく知られているのはMost Vexing Parseとして知られており、コンテキストに応じて識別子が型名として解釈される可能性があります。
前述のコンテキストを C++ で追跡するには、構文解析段階と並行して何らかの意味分析を実行する実装が必要です。これは一般に、特定の文法構造が特定のコンテキストで認識されたときに呼び出されるセマンティック アクションの形式で実装されます。これらのセマンティック アクションは、コンテキストを表すデータ構造を構築し、効率的なクエリを可能にします。これはしばしばシンボル テーブルと呼ばれますが、C++ に必要な構造はほぼAST全体です。
このような状況依存のセマンティック アクションは、あいまいさを解決するためにも使用できます。たとえば、 namespace-bodyのコンテキストで識別子を認識すると、セマンティック アクションは、その名前が以前にテンプレートとして定義されていたかどうかを確認します。この結果は、パーサーにフィードバックされます。これは、識別子トークンを結果でマークするか、別の文法規則に一致する特別なトークンに置き換えることで実行できます。
同じテクニックを使用して、 a をtemplate-argument-list<の先頭としてマークしたり、 aを末尾としてマークしたりできます。with twoの状況依存置換のルールは、本質的に同じ問題を提起し、同じ方法を使用して解決できます。>>>>
おっしゃる通り、レクサーとパーサーを理論的に明確に区別できるとは限りません。学生時代に取り組んだプロジェクトを思い出します。私たちは C コンパイラを実装することになっており、基本として使用した文法は、型定義された名前を場合によっては型として扱い、他の場合では識別子として扱います。そのため、レクサーはこれら 2 つのモードを切り替える必要がありました。当時私がこれを実装した方法は、コンテキストに応じてレクサーを再構成する特別な空のルールを使用していました。これを実現するには、パーサーが常に1 つの先読みトークンを使用することを知っておくことが不可欠でした。したがって、レクサーの動作に対する変更は、影響を受ける場所の少なくとも 1 つのレキシカル トークンの前に発生する必要があります。最終的に、これは非常にうまく機能しました。
あなたが言及したC++の場合、>>コンパイラが実際に何をするのかわかりません。willj は、仕様がこれをどのように表現しているかを引用しましたが、実装は、目に見える結果が同じである限り、内部で異なることを行うことが許可されています。したがって、これに取り組む方法は次のとおりです。 a を読み取る>と、レクサーは tokenを発行しますが、間にスペースを入れずにGREATER後続のそれぞれが lexed される状態にも切り替わります。他のシンボルは、状態を通常に戻します。状態スイッチの代わりに、正規表現を字句解析し、このルールから複数のトークンを発行することでこれを行うこともできます。パーサーでは、次のようなルールを使用できます。> GREATER_REPEATED>+
rightAngleBracket: GREATER | GREATER_REPEATED;
rightShift: GREATER GREATER_REPEATED;
運が良ければ、テンプレートの引数ルールで rightAngleBracket を使用し、式で rightShift を使用することができます。パーサーがどれだけ先読みしているかによっては、あいまいなコンテンツのより長いシーケンスを保持するために追加の非終端記号を導入する必要がある場合があります。これは、最終的にこれらのケースの間で決定を下すことができるコンテキストに遭遇するまで続きます。