C++ を LR(1) パーサーで解析できないのはなぜですか?

StackOverflow https://stackoverflow.com/questions/243383

質問

パーサーとパーサー ジェネレーターについて読んでいたところ、ウィキペディアの LR 解析ページで次の記述を見つけました。

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

なぜそうなるのでしょうか？LR パーサーで解析できない原因となる C++ の特定のプロパティは何ですか?

Google を使用すると、C は LR(1) で完全に解析できるが、C++ には LR(∞) が必要であることがわかりました。

役に立ちましたか？

解決

Lambda the Ultimate には、 C ++のLALR文法。

博士論文へのリンクが含まれていますこれには、C ++解析の説明が含まれており、次のように記述されています。

  

<！> quot; C ++の文法はあいまいです。   コンテキスト依存で潜在的に   解決するには無限の先読みが必要です   いくつかのあいまいさ<！> quot;。

さらに、いくつかの例を示します（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つのトークンシーケンスは、同じ初期サブシーケンスを持ちますが、最後の要素に依存する解析ツリーが異なります。あいまいさを解消する前に、任意の数のトークンが存在する可能性があります。

他のヒント

LRパーサーは、設計上、あいまいな文法規則を処理できません。 （アイデアが考え出されていた1970年代に、理論をより簡単にしました。）

CとC ++はどちらも次のステートメントを許可します。

x * y ;

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

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

今、後者はバカだと思うかもしれませんが、無視すべきです。 ほとんどがあなたに同意するでしょう。ただし、場合によっては 副作用があります（乗算が過負荷の場合など）。しかし、それはポイントではありません。 ポイントは2つの異なる解析である ため、プログラム この の解析方法に応じて、さまざまな意味があります。

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

したがって、純粋なLR解析はこれを処理できません。また、Antlr、JavaCC、YACC、または従来のBisonなどの広く利用可能な他の多くのパーサージェネレーター、または<！> quot; pure <！> quotで使用されるPEGスタイルパーサーも使用できません。方法。

より複雑なケースがたくさんあります（テンプレート構文の解析には任意の先読みが必要ですが、LALR（k）はk個のトークンを先読みできます） LR（またはその他）の解析。

ほとんどの実際のC / C ++パーサーは、 追加のハックを備えた一種の決定論的なパーサー：シンボルテーブルと解析を組み合わせます コレクション...のように<！> quot; x <！> quot;遭遇する、 パーサーは、xが型であるかどうかを知っているため、 2つの潜在的な解析から選択します。しかし、パーサー これはコンテキストフリーではありません。LRパーサー （純粋なものなど）は（せいぜい）コンテキストフリーです。

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

十分にチートすれば、LRパーサーを動作させることができます CおよびC ++。 GCCの連中はしばらくやりましたが、それを与えました 手でコード化された構文解析のために より良いエラー診断。

ただし、別のアプローチがあります。 シンボルテーブルなしでCとC ++を問題なく解析します hackery： GLRパーサー。 これらは完全にコンテキストフリーのパーサーです（実質的に無限です 先のことを考える）。 GLRパーサーは単に両方の解析を受け入れ、 <！> quot; tree <！> quot; （実際には、主にツリーのような有向非巡回グラフ） あいまいな解析を表します。 解析後のパスであいまいさを解決できます。

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

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

この新しい文法を「非コンテキストフリー」yacc パーサーで完全に解析できるようにするために必要な、C++ 文法への最小の変更セットは何ですか?(「ハック」を 1 つだけ使用します:型名/識別子の曖昧さの解消、パーサーがすべての typedef/class/struct をレクサーに通知する)

いくつかあります。

  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) それ以外は禁止されるだろう #type 指令これは愚かなことへの大きな一歩になるでしょう sizeof int 非常に多くの C++ ヘッダーに存在するあいまいさ

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

曖昧な C++ 構文をご存知の場合は追加してください。

こちらから回答、C ++には、操作の順序を変更する型解決段階（通常は解析後）のため、LLまたはLRパーサーによって決定論的に解析できない構文が含まれているため、 AST（通常、最初の段階の解析によって提供されると予想されます）。

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

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

<！> quot; typedef <！> quot; C ++の問題は、構文解析中にシンボルテーブルを構築するLALR（1）パーサーで解析できます（純粋なLALRパーサーではありません）。 <！> quot; template <！> quot;この方法ではおそらく問題を解決できません。この種のLALR（1）パーサーの利点は、文法（以下に示す）がLALR（1）文法（あいまいさなし）であることです。 

/* C Typedef Solution. */

/* Terminal Declarations. */

   <identifier> => lookup();  /* Symbol table lookup. */

/* Rules. */

   Goal        -> [Declaration]... <eof>               +> goal_

   Declaration -> Type... VarList ';'                  +> decl_
               -> typedef Type... TypeVarList ';'      +> typedecl_

   VarList     -> Var /','...     
   TypeVarList -> TypeVar /','...

   Var         -> [Ptr]... Identifier 
   TypeVar     -> [Ptr]... TypeIdentifier                               

   Identifier     -> <identifier>       +> identifier_(1)      
   TypeIdentifier -> <identifier>      =+> typedefidentifier_(1,{typedef})

// The above line will assign {typedef} to the <identifier>,  
// because {typedef} is the second argument of the action typeidentifier_(). 
// This handles the context-sensitive feature of the C++ language.

   Ptr          -> '*'                  +> ptr_

   Type         -> char                 +> type_(1)
                -> int                  +> type_(1)
                -> short                +> type_(1)
                -> unsigned             +> type_(1)
                -> {typedef}            +> type_(1)

/* End Of Grammar. */

次の入力は問題なく解析できます：

 typedef int x;
 x * y;

 typedef unsigned int uint, *uintptr;
 uint    a, b, c;
 uintptr p, q, r;

LRSTARパーサージェネレーターは、上記の文法表記を読み取り、<！> quot; typedef <を処理するパーサーを生成します< ！> quot;解析ツリーまたはASTにあいまいさのない問題。 （開示：私はLRSTARを作成した男です。）

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top