ウィキペディアからの次の引用に混乱しています。
言い換えれば、言語が効率的なワンパスパーサーを許可するのに十分合理的である場合、LR(k) 文法で記述できます。そして、その文法は常に同等の (しかしより大きな) LR(1) 文法に機械的に変換できます。したがって、理論的には、LR(1) 解析メソッドは、合理的な言語を処理するのに十分強力でした。実際には、多くのプログラミング言語の自然文法は LR(1) に近いものです。[要出典]
これは、文法を文法に変換できる場合、 のようなパーサー ジェネレーターbisonが非常に強力であることを意味します (文法を処理できるため) 。これのいくつかの例、またはこれを行う方法に関するレシピはありますか? 文法にシフト/リデュースの競合があるのでこれを知りたいのですが、これは文法であり、文法に変換したいからだと思います。副次的な質問: は理不尽な言語です。LR(k)LR(k)LR(1)LR(2)LR(1)C++bison
LR(1)文法をカバーする文法を見つけるための汎用アルゴリズムのリファレンスについては、Real-world LR(k > 1) grammars?LR(k)を参照してください。
汎用アルゴリズムは非常に大きな文法を生成します。実際、結果として得られる PDA は、PDA と同じサイズになると確信していLR(k)ます。ただし、特定のケースでは、より単純なソリューションを考え出すことができます。ただし、一般的な原則が適用されます。単一の先読みトークンで決定が下されるまで、無条件にシフトすることにより、シフト/削減の決定を延期する必要があります。
あなたの文法についてもっと詳しく知らなければ、それ以上のことはできません。
C++ に関しては、解析が難しいのは、プリプロセッサと、テンプレートのインスタンス化の解析 (および字句解析) におけるいくつかのまれなケースです。式の解析がシンボルの「種類」(タイプではない) に依存するという事実 (シンボルが発生するコンテキストで) は、bison を使用した正確な解析を複雑にします。[1] 「不合理」とは、私が自信を持って判断できない価値判断です。確かに、ツールのサポート (正確な構文カラーライザーやタブ補完機能など) は、別の文法では単純だったでしょう。
ノート：
[1] C にも適用される古典的なトリッキーな解析は、型を表す(a)*b場合は間接参照のキャストであり、そうでない場合は乗算です。aコンテキストでそれを記述した場合: c/(a)*b、それがキャストか製品かを知らずに AST を構築できないことは明らかです。これは AST の形状に影響するためです。
より C++ 固有の問題は次のとおりx<y>(z)です。x<y<z>>(3)x