問題タブ [ll]

LLパーサーとLRパーサーの基本的な違いを知っています。また、GLR、SLR、およびLALRはすべてLRパーサーの拡張機能であることも知っています。だから私の質問はもっと詳しく...

LL（*）パーサーとLRパーサーのバリエーションを考えると、一方で記述でき、他方で記述できない言語はありますか？それとももっと簡単に言えば、どちらでも表現できない特徴や特性はありますか？

具体的な例として。LL（*）パーサーを使用して言語を作成する場合、LRパーサーでのみ可能になる（またはその逆の）言語に追加したい機能/プロパティに遭遇することはありますか？

LL 構文解析と LR 構文解析の簡単な例を教えてください。

いくつかの主要な構文解析アルゴリズム (LL(1)、LR(1)、LR(0)、LALR(1)) の文法を集めたオンラインの優れたリソースはありますか? 私はこれらのファミリーに分類される多くの個々の文法を見つけましたが、誰かが大量の文法例を書き上げた優れたリソースを知りません。

そのようなリソースを知っている人はいますか？

LL（1）文法もLR（1）であることは広く知られている事実ですが、これの厳密な証拠はどこにも見つからないようです。証明の概要をいくつか聞いたことがあります（たとえば、LL（1）文法では、一度に1つのトークンから生成が決定されるため、LR（1）文法では、決定前にはるかに多くの入力をスキャンできます）作られています）。しかし、コンパイラに関する2つの教科書を調べ、解析してGoogleですばやく検索した後、この事実のより正式な証明を突き止めることができないようです。

誰かがこの証拠、または少なくともそれを見つける場所を知っていますか？

私は最近、LL(1) ではない多くの文法をいじっていますが、それらの多くは LL(1) の文法に変換できます。

しかし、 LL(1) ではない明確な言語の例を見たことがありません。言い換えれば、その言語の明確な文法が LL(1) ではない言語であり、偶然見つけた場合に、それを見つけたことをどのように証明できるかわかりません。

特定の明確な言語が LL(1) ではないことを証明する方法を知っている人はいますか?

文法があり、LL(1) であるかどうかを確認できます。しかし、文法によって生成された言語が LL(1) であるかどうかを確認する方法はありますか? では、LL(1) 文法と LL(1) 言語の正確な違いは何ですか?

代入を式として扱うために Tiny Language の文法を拡張しようとしています。したがって、次のように書くことは有効です

割り当ては、2 つの側面で他の演算子とは異なります。これは右結合 (大したことではありません) であり、左辺は変数でなければなりません。だから私はこのように文法を変更しました

非 LL(*) 決定が含まれているため、機能しません。私もこの変種を試しました：

しかし、同じエラーが発生しました。私は、に興味を持っています

• この特定の質問
• 非 LL(*) 決定を伴う文法が与えられた場合、問題を引き起こす 2 つのパスを見つける方法
• 修正方法

すべてのLL文法はLR文法ですが、その逆ではありませんが、私はまだその区別に対処するのに苦労しています。同等のLL表現を持たないLR文法の小さな例が存在する場合は、それについて興味があります。

Webには、LL（1）パーサーの最初/次のセットから文脈自由文法の構文解析テーブルを作成する方法を示す例がたくさんあります。

しかし、k>1のケースに関連する有用なものは何も見つかりませんでした。ウィキペディアでさえ、これについての情報を提供していません。

I expect that it must be in some way similar, but pointers to existing research in this area would be very helpful.