問題タブ [lr]

LR（1）アイテムの先読みを計算する方法を理解するのに問題があります。

私がこの文法を持っているとしましょう：

LR（1）アイテムは、先読みのあるLR（0）アイテムです。したがって、状態0の次のLR（0）アイテムを取得します。

状態：1

誰かが先読みを計算する方法を説明できますか？一般的なアプローチは何ですか？

前もって感謝します

私は LR(1) パーサーを作成していますが、さまざまな場所でパフォーマンスのボトルネックに遭遇しました。

パーサーのデータ構造の最適化を試みたいのですが、そのためには、C++ などの (おそらく複雑な) コンピューター言語に妥当な状態、規則、および終端記号の数を大まかに把握する必要があります。

私の推測では、複雑な言語の典型的な文法は次のようになります。

• ≤ 100 端子記号
• プロダクションあたり ≤ 50 シンボル
• ≤ 2,000 ルール
• ≤ 10,000 州

しかし、それらがどれほど正しいかは本当にわかりません。

各ルールは非終端記号→記号 記号 記号...の形式であると想定しているため、1 つfoo: (bar | baz)+の規則だけではなく、実際には 5 つの規則で構成されているように見える単一の複合「規則」であることに注意してください。

彼らは合理的ですか？そうでない場合、これらの数字はどこにありますか?

LR（1）パーサジェネレータの単純な（可能な限り、しかし単純ではありません！）実装はどこにありますか？

私はパフォーマンスを求めているのではなく、LR（1）状態（アイテムセット）を生成する機能だけを求めています。
C ++、C＃、Java、Pythonはすべて私のために機能します。

私は C++ が と のすべてのあいまいさを持つ「奇妙な」ものだと思っていましたが、パーサーを実装しよう<とした後、ジェネリック型を使用するほぼすべての言語>を壊す例を見つけたと思います:<>

これは、構文的にジェネリック メソッド呼び出し ( ) として解釈されるか、2 つの比較の結果をg与えるものとして解釈される可能性があります。f

そのような言語 (特に、LALR(1) で解析可能と考えられていたJava ) は、この構文上のあいまいさをどのように回避するのでしょうか?

これに対処するための非ハッキー/コンテキストフリーの方法を想像することはできません.LALR（1）解析可能は言うまでもなく、そのような言語がコンテキストフリーになる方法に困惑しています...

(GLR パーサーでさえ、コンテキストなしでこのステートメントの単一の解析を返すことはできないことに注意してください!!)

私はウィキペディアで両方を読んでいて、LR(0) パーサーは存在しますが、LL(0) パーサーのようなものは存在しないことに気付きました。

私が読んだことから、LL(k)/LR(k) の k は、パーサーが現在作業中の現在の文字を超えて認識できる文字数を意味することを理解しています。

私の質問は、LR(0) が存在するにもかかわらず、LL(0) パーサーなどがないのはなぜですか?

私は文法を作成しました。その簡略版を以下に再現します。

この言語は明確であり、LR解析可能である必要があると思います。（私が間違っている場合は私に知らせてください！）

ただし、この文法のLR（1）パーサーを生成しようとすると、シフト/リデュースの競合が発生します。パーサーがexp3先読み?で表示すると、シフトするかリデュースするかがわからないためです。

この言語をLR（1）解析可能（競合なし）にするための合理的な方法はありますか？

それとも、GLR（またはおそらくLR（2）？）は、このような言語の唯一の現実的なオプションですか？
（または、そもそも言語が明確であると信じるのは間違っていますか？）

参考までに、私が生成したあいまいなステートマシンは次のとおりです（♦はEOFです）。

私はLR（2）文法を持っていて、LR（1）文法に変換したいという演習をしました。しかし、どうすればそれができるのかわかりません。私はこの文法を持っています（4つのルール）：

• e -> 真 | 偽 | ID | e ^ e | 前夜 | (e)
• i -> もし e なら i | もし e なら、私はそうでなければ私 | ID = e | (i) | マ
• マ -> ア | あ^ま
• a -> id = e

彼女がreduce/reduceの衝突を引き起こすというこの文法の問題（誰もそれを好まない）。したがって、LR(1) でこの文法を変更する必要がありますが、それを行うためのアルゴリズムが実際にはわかりません。助けてください ：）

私は次の文法を書きました：

e は「空の文字列」を表します

したがって、この文法が認識する言語には、()、(())、(()()) などのように、左右の括弧が一致するすべての文字列が含まれます。

この文法は SLR ではありません。SLR 解析テーブルを作成する方法は次のとおりです。

1. この文法を拡張します。

   S1->S S->S(S)S S->e

2. 次に、LR(0) オートマトンを構築します。

   I0: S1->.S S->.S(S)S S->.e

   I1: S1->S。S->S.(S)S

...

I0 の場合、この文法が生成する文字列の最初のトークンである入力記号 '(' に対するシフトまたは削減アクションがないことに注意してください。

したがって、状態 I0 では、文字列 (()) を解析するときに何をすべきかわからないため、SLR 解析テーブルはエラーを生成します。

私の質問は：

この文法が SLR ではない原因は何ですか? 空文字列制作ですか？つまり、S->e です。?

そして、一般的な意味で、SLR 文法は空のプロダクションを持つことができますか? のように、この例では S->e です。ありがとう。