問題タブ [lr]

私はこのような規則を持つ文法を持っています

この文法を LALR(1) に変換する方法はありますか? 私が理解できることから、パーサーがpブロック内を見ると、シフト/抽出の競合が発生します。

CFG を見て与えられた場合、それが LL クラスの文法か LR クラスの文法かを判断できますか? Google でこの質問を検索したところ、これらの文法のパーサーがどのように機能するかがわかりましたが、それは私が望んでいるものではありません。どんな援助でも大歓迎です。

yacc には次の文法があります。

そしてフレックスでは：

次のような有効な解析を作成したい:

ここで、最初の行は「Directivas」、次に 1 行の空白行であり、次に「Conceitos」が続きます。1 つの Conceitos は 1 つの単語であり、その後に「-」で始まるいくつかのテキスト行が続きます。これらの 'Conceitos は 1 つの空白行で区切られています

しかし、シフト/リデュースの競合が見つかります..私はこれが初めてで、理由がわかりません

私の英語でごめんなさい

ありがとうございました

LR(1) クロージャーをすばやく計算するために、Warshall のアルゴリズムを実装しようとしています。

LR（0）でどのように機能するかを理解していると思います：

• グラフのノードは、次のようなLR アイテムです。A → B • C
• エッジは、から始まる「トランジション」ですA → B • C。C → • D

問題は、LR(1) には先読みの計算が必要であり、それらをアルゴリズムに組み込む方法がわかりません。与えられた LR アイテムの推移閉包を知っ
ていたとしても、各アイテムの先読みセットが何であるかを理解するためだけに、同じ計算をすべて行う必要があるように思えます。

ウォーシャルのアルゴリズムを使用して正規の LR(1) クロージャーを計算することは可能ですか?それとも、より制限されたケース (LR(0)、SLR(1) など) でのみ可能ですか?

解決できない LR(1) 競合のある文法があります。それでも、文法は明確であるべきです。(最初に、、)、{}、 の5 つのトークンを使用した簡略化された文法で問題を示します。,id

EBNF は次のようになります。

文法は明確で、最大 2 つの先読みトークンが必要です。が(シフトされると、次の 5 つの可能性しかありません。

1. (→再発。
2. )→ のように縮小し'(' args ')'ます。
3. id )ない{}→ として減らす'(' expression ')'。
4. id ) {}→'(' args ')' '{}'
5. id ,'(' args ')' '{}'→ (最終的に)として削減します。

単純な翻訳では、次の結果 (および競合)が得られます。

そのため、文法では、決定する先読みの最大 3 つのトークンが必要です。LR(3) 文法は LR(1) 文法に変換できることを知っています。

ただし、この特定のケースで変換を行う方法がよくわかりません。上記の単純化された文法は、より大きなコード本体からの抜粋であることに注意してください。特に、 上記のすべてprimaryをタッチせずに変換することは可能ですか?expr

lr(0) パーサーについて疑問があります。たとえば、次の文法があります。

lr0 オートマトンの最初の状態を構築しようとすると、次の最初の状態が得られます。

ですから、ここで私にはばかげた疑問が浮かびます。「S -> 」があるので。最初の状態では、これは lr0 パーサーのシフト/リデュースの状況ですか? パーサーは、非終端記号 S によってアクションをシフトしたり、空のトランジションによってアクションを減らしたりすることができます (私はそう思います)。

空のトランジションの例を探して Web を検索しましたが、見つかりませんでした。

次の文法の LALR(1) パーサーを作成しようとしていて、シフト/リデュースの競合を見つけようとしています。

そのため、パーサーは文字列 "ID[ID]" を正しく解析できません。私の質問は、

1. そのような非 LALR(1) 文法を LALR(1) 文法に変換する一般的な方法はありますか?
2. 2 つの文法がまったく同じ言語を生成し、一方が LALR(1) ではないことがわかっている場合、もう一方が LALR(1) であるかどうかを知ることができますか?

上記の文法は一例に過ぎません。私が本当に知りたいのは、これらの文法の問題を解決する一般的な方法です。提案や読書の推奨事項は大歓迎です。

前もって感謝します。

次の型のプロダクションが見つかった場合、 follow(A) を見つけます

あ→α

ここで α は ε でありえますか?

以下の例のように:

P → aPa | bPb | ε

α が ε である場合、それは LR(1) ではありません

私は LR(k) 解析テーブルの構築について読み始めました。k > 0 のアルゴリズムを説明するすべてのテキストは、アイテム セットを生成する前にすべてのシンボルに対して先読みを計算する必要があることを示唆しています。冗長なものをマージして、最小限の解析テーブルを生成する必要があります。

次の疑似状態/アイテムセット構築ルーチンを検討してください。

1. 先読みなしで状態遷移を決定できると仮定することから始めます (k = 0)
2. 現在の状態のアイテムセット全体を計算する
3. 現在の状態のアクションを決定してみてください。
   • セット内にアイテムが 1 つしかなく、それがすべての入力を消費した場合 (rhs の右側にあるマーカー、アクションはアイテムの lhs に縮小されます。
   • セット内のすべてのアイテムが入力を期待している場合、アクションはシフトして次の状態に進むことです
   • 入力を期待する項目と入力を期待しない項目がある場合、これは shift/reduce 競合です
   • lhs が異なる 2 つ以上のアイテムが入力の最後に達した場合、これは reduce /reduce の競合です。最後の 2 つのケースのいずれかが発生した場合は、状態のアクションを決定する前に先を見据える必要があることを意味します。k を 1 増やして、ステップ 2 に戻ります。
4. アクションがシフトする場合は、入力の組み合わせ (および k > 0 の場合は先読み) をシミュレートしてフォローアップ状態を作成し、新しい状態ごとにステップ 1 に戻ります。

上記の手順を使用して、任意の LR(k) 文法のテーブルを構築することは可能/実行可能でしょうか? そうでない場合、何が欠けていますか？

LR と LALR の両方がボトムアップの解析アルゴリズムであることは理解していますが、この 2 つの違いは何ですか?

LR(0)、LALR(1)、LR(1) 解析の違いは何ですか? 文法が LR(0)、LALR(1)、または LR(1) であるかどうかはどうすればわかりますか?