157

私はパーサーとパーサージェネレーターについて読んでいて、ウィキペディアのLR解析ページでこのステートメントを見つけました：

多くのプログラミング言語は、LRパーサーのバリエーションを使用して解析できます。注目すべき例外の1つはC++です。

なんでそうなの？C ++のどの特定のプロパティにより、LRパーサーで解析できなくなりますか？

グーグルを使用して、私はCがLR（1）で完全に解析できることを発見しただけですが、C ++はLR（∞）を必要とします。

4

6 に答える 6

241

LR パーサーは、設計上、あいまいな文法規則を処理できません。(アイデアが練り上げられていた 1970 年代に理論をより簡単にしました)。

C と C++ の両方で、次のステートメントを使用できます。

x * y ;

2 つの異なる解析があります。

  1. 型 x へのポインターとして、y の宣言にすることができます
  2. 答えを捨てて、x と y の乗算になる場合があります。

さて、後者はばかげているので無視すべきだと思うかもしれません。ほとんどの人はあなたに同意するでしょう。ただし、副作用がある場合もあります (たとえば、multiply がオーバーロードされた場合)。しかし、それはポイントではありません。ポイントは、2 つの異なる解析があり、したがって、これがどのように解析されるべきかによって、プログラムは異なることを意味する可能性があるということです。

コンパイラは、適切な状況下で適切なものを受け入れる必要があり、他の情報 (x の型の知識など) がない場合は、後で何をすべきかを決定するために両方を収集する必要があります。したがって、文法はこれを許可する必要があります。そして、それは文法を曖昧にします。

したがって、純粋な LR 解析ではこれを処理できません。Antlr、JavaCC、YACC、従来の Bison、さらには PEG スタイルのパーサーなど、広く利用されている他の多くのパーサー ジェネレーターを「純粋な」方法で使用することもできません。

より複雑なケースはたくさんあります (テンプレート構文の解析には任意の先読みが必要ですが、LALR(k) は最大 k 個のトークンを先読みできます) が、純粋なLR (またはその他) の解析を打ち破る反例が 1 つだけ必要です。

ほとんどの実際の C/C++ パーサーは、追加のハックを備えたある種の決定論的パーサーを使用してこの例を処理します。それらは、構文解析とシンボル テーブル コレクションを絡み合わせて...「x」が検出されるまでに、パーサーは x が型であるかどうかを認識します。かどうか、したがって、2 つの潜在的な解析から選択できます。しかし、これを行うパーサーはコンテキスト フリーではなく、LR パーサー (純粋なものなど) は (せいぜい) コンテキスト フリーです。

このあいまいさを解消するために、ごまかし、ルールごとの短縮時間セマンティック チェックを LR パーサーに追加することができます。(このコードはしばしば単純ではありません)。他のほとんどのパーサー タイプには、解析のさまざまなポイントでセマンティック チェックを追加する手段があり、これを使用してこれを行うことができます。

そして、十分にごまかすことができれば、LR パーサーを C および C++ で動作させることができます。GCC 関係者はしばらくの間そうしましたが、手でコード化された解析のためにそれをあきらめました。彼らはより良いエラー診断を望んでいたからだと思います。

ただし、別のアプローチがあります。これは、シンボルテーブルのハッカーなしで、C と C++ を適切に解析する、素晴らしくクリーンなアプローチです: GLR パーサー。これらは、完全なコンテキスト フリー パーサーです (実質的に無限の先読み機能を備えています)。GLR パーサーは単純に両方の解析を受け入れ、あいまいな解析を表す「ツリー」(実際にはほとんどがツリーに似た有向非巡回グラフ) を生成します。解析後のパスは、あいまいさを解決できます。

この手法は、DMS ソフトウェア リエンジニアリング ツールキットの C および C++ フロント エンドで使用されます (2017 年 6 月現在、これらは MS および GNU 方言で完全な C++17 を処理します)。それらは、数百万行の大規模な C および C++ システムを処理するために使用されており、ソース コードの完全な詳細を含む AST を生成する完全で正確な解析が行われています。( C++ の最も厄介な解析については、AST を参照してください。 )

于 2009-06-17T02:01:10.477 に答える
96

Lambda the Ultimateには、 C++の LALR 文法について説明している興味深いスレッドがあります。

これには、次のように述べている C++ 解析の説明を含む博士論文へのリンクが含まれています。

「C++ 文法はあいまいで、コンテキストに依存しており、いくつかのあいまいさを解決するために無限先読みが必要になる可能性があります」.

いくつかの例を挙げています (pdf の 147 ページを参照)。

例は次のとおりです。

int(x), y, *const z;

意味

int x;
int y;
int *const z;

比較:

int(x), y, new int;

意味

(int(x)), (y), (new int));

(コンマ区切り式)。

2 つのトークン シーケンスは、最初のサブシーケンスは同じですが、最後の要素に依存する異なる解析ツリーを持ちます。曖昧さを解消するトークンの前に任意の数のトークンが存在する可能性があります。

于 2008-10-28T14:01:47.253 に答える
15

問題はこのように定義されることはありませんが、興味深いはずです:

この新しい文法が「非コンテキスト フリー」の yacc パーサーによって完全に解析されるようにするために必要な C++ 文法の最小の変更セットは何ですか? （1つの「ハック」のみを使用します：型名/識別子の曖昧さの解消、すべての型定義/クラス/構造体のレクサーに通知するパーサー）

私はいくつかのものを見ます：

  1. Type Type;禁止されています。型名として宣言された識別子は、非型名識別子になることはできません (struct Type Typeあいまいではなく、引き続き許可される可能性があることに注意してください)。

    には次の 3 種類がありますnames tokens。

    • types: 組み込み型または typedef/class/struct のため
    • テンプレート関数
    • 識別子 : 関数/メソッドおよび変数/オブジェクト

    テンプレート関数を異なるトークンと見なすことで、func<あいまいさが解決されます。funcがテンプレート関数名である場合は<、テンプレート パラメーター リストの先頭でなければなりません。それ以外の場合funcは、関数ポインターで<あり、比較演算子です。

  2. Type a(2);オブジェクトのインスタンス化です。 Type a();とType a(int)は関数プロトタイプです。

  3. int (k); は完全に禁止されています、書かれるべきですint k;

  4. typedef int func_type();typedef int (func_type)();禁止されています 。

    関数 typedef は関数ポインタ typedef でなければなりません:typedef int (*func_ptr_type)();

  5. テンプレートの再帰は 1024 に制限されています。それ以外の場合は、最大値を増やして、オプションとしてコンパイラに渡すことができます。

  6. int a,b,c[9],*d,(*f)(), (*g)()[9], h(char); も禁止される可能性があり、 int a,b,c[9],*d; int (*f)();

    int (*g)()[9];

    int h(char);

    関数プロトタイプまたは関数ポインター宣言ごとに 1 行。

    非常に好ましい代替手段は、ひどい関数ポインター構文を変更することです。

    int (MyClass::*MethodPtr)(char*);

    次のように再構文化されます。

    int (MyClass::*)(char*) MethodPtr;

    これはキャスト演算子と一貫性があります (int (MyClass::*)(char*))

  7. typedef int type, *type_ptr; も禁止される可能性があります：typedefごとに1行。したがって、それは

    typedef int type;

    typedef int *type_ptr;

  8. sizeof int、、sizeof charおよびsizeof long long共同。各ソースファイルで宣言できます。したがって、型を使用する各ソース ファイルはint、

    #type int : signed_integer(4)

    そのディレクティブの外でunsigned_integer(4)は禁止されます。これは、非常に多くの C++ ヘッダーに存在#type する愚かなあいまいさへの大きな一歩となります。sizeof int

再構文化された C++ を実装するコンパイラは、あいまいな構文を使用する C++ ソースに遭遇した場合source.cpp、フォルダも移動し、コンパイルする前にambiguous_syntax、あいまいでない翻訳を自動的に作成します。source.cpp

あいまいな C++ 構文を知っている場合は、追加してください。

于 2013-02-13T11:37:38.247 に答える
9

ここでの私の答えからわかるように、C ++には、型解決段階（通常は後解析）によって操作の順序が変更されるため、LLまたはLRパーサーでは決定論的に解析できない構文が含まれているため、ASTの基本的な形状（通常、第1段階の解析によって提供されることが期待されます）。

于 2009-09-02T02:05:41.423 に答える
6

あなたは答えにかなり近いと思います。

LR(1) は、左から右への構文解析でコンテキストの先読みに必要なトークンが 1 つだけであることを意味しますが、LR(∞) は無限の先読みを意味します。つまり、パーサーは、現在の場所を把握するために、これから来るものすべてを知っている必要があります。

于 2008-10-28T14:05:08.370 に答える