これはLALR（1）パーサーによって解析できますか？

Question

は、私は他の人の間で、次の構文を持つ言語のためのBisonパーサを書いています：

• 自己派遣：[identifierarguments]
• 派遣：[expression。 identifierarguments]
• 文字列スライシング：expression [expression、expression] - Pythonに似ています。

argumentsはカンマで区切られた式のリストです。空の場合もあります。上のすべてが独自の表現でもあります。 私の問題は、[method [other_method]]と[someString[idx1, idx2].toInt]の両方を解析する方法がわからないこと、またはLALR（1）パーサーでこれをすべて行うことができるかどうかわからないことです。

より正確には、次の例を考えてみましょう。[a[b]]（メソッドbの結果を持つaメソッドを呼び出します）。状態が[aに達したとき。 [b]]（先読みが第二[ある）a[b,c]のようなものは、それ自体がexpressionに減少し、第二構築物で続けることができた（続く可能性があるので、それはexpressionに（すでにidentifierに縮小されています）aを削減するかどうかを知ることができませんargumentsのリスト（この場合は[b]など）が続くので、identifier（およびそれをシフトしてください）のままにしてください。

この文法をどのように表現したかによって、このシフト/リダクションの競合が起こっているのですか、またはLALR（1）パーサーでこれらの構文をすべて解析できませんか？

もっと一般的な質問ですが、言語が特定の種類のパーサーによって解析できないことをどのように証明できますか？

Answer 1

あなたの文法が明白であると仮定すると（その部分が現れると思われます）、あなたの最善の策は%glr-parserです。ほとんどの場合、正しい構文解析は少数のトークンの後で強制されるため、オーバーヘッドが目立たないようにし、ASTの文法や構造を複雑にする必要がないという利点があります。

一つの欠点は、バイソンは文法が明確であることを確認できないということです。一般に、これは不可能であり、証明するのは容易ではありません。一部の入力があいまいであることが判明した場合、GLRパーサーはエラーを生成するため、良いテストスイートが重要です。

言語がLR（1）でないことを証明するのは難しいでしょうし、おそらく言語がおそらく認識可能なLALR（1）パーサーでであるため、これは不可能と思われます。しかし、構文解析（CS理論の外で）は、構文解析ツリーを正しく作成する必要があり、LR文法を生成するために必要な変更の種類によって、ASTも変更されますパース後のフィックスアップが必要です。最初の（部分集合）場合

a[b[c],d] 

と

[a[b[c],d]] 

間の優先順位の差から正しいASTばねを作成する際の困難は、bは、その引数リスト[c]に結合し、カンマは、より低い優先順位を有します;最後にb[c]とdはスライスの兄弟の子です。 2番目のケース（メソッド呼び出し）では、コンマは引数リストの一部であり、メソッドアプリケーションよりも緊密にバインドされています。 b,[c]およびdは、メソッドアプリケーションの兄弟です。しかし、任意の長い入力（dが任意の式である可能性があるため）まで、解析ツリーの形状を決めることはできません。

"優先順位"は正式には定義できないため、ツリーを調整することができるハックがあるため、これは少し手間がかかります。 LRプロパティは実際には構成可能ではないので、より厳密な分析を提供することは本当に可能です。しかし、GLRパーサーは、最も単純で最も堅牢なソリューションである可能性が高いです。

今後の参考になる小さなポイント：CFGは単なるプログラミングツールではありません。問題の文法を明確に伝える目的を果たしています。 Nirmally、あなたの言語を説明したいなら、あなたは非公式に記述しようとするよりも明確なCFGを使う方が良いです。もちろん、意味のない非終端記号の名前が役立ちますが、いくつかの例は決して傷つけることはありませんが、文法の本質は形式的な記述であり、省略すると他の人が "助けになる"ことが難しくなります。