問題タブ [lr]

私はコンパイルの主題に不慣れで、ボトムアップ解析の演習を開始したばかりです。

私は次の問題に固執しました。

次の文法の LR(0) 解析テーブルを作成します。

E では、DFA の次の状態は次のようになります。

私がこれまでに学んだことから、これは SR 競合ではありませんか? 先読み変数がないため、パーサーは削減またはシフトするかどうかわからないためですか? これは LR(0) 文法であってはなりませんか?

しかし、私が読んでいるPDFはLR(0)テーブルを構築しています。PDFに間違いがありますか、それとも概念を理解する場所で間違っていますか?

1. 「右端の導出を逆に」と言う代わりに、「左端のリダクション」と言わないのはなぜですか? 同じ意味ですか？読んでいて非常に紛らわしいです。

2. クロージャ セットとは何ですか? また、解析プロセスでどのように役割を果たしますか? 私がインターネットで見つけた一連の講義ノートは、それが何であり、何をするのかを既に知っていることを前提としています。

以下の例では、 を介して状態0から状態に移行したい場合、1 つの状態で縮小状態と通常状態に直面することは明らかです。 正直なところ、私は前にそれを見ませんでした。それが私が尋ねている理由です。3T

これは可能ですか？普通に減量を続けますか？または私は間違っていますか？

必要な場合の文法は次のとおりです。

E ---> E+T | T
T ---> T*F | フフ ---> ( E
) | ID

歴史的に、LR(1) パーサーによって生成される多数の状態に必要なリソース要件のため、LALR(1) パーサーは LR(1) パーサーよりも好まれていました。これが今日のコンピューティング環境で引き続き問題であるとは信じがたいことです。LALR文法はLR文法の適切なサブセットであるため、これはまだ当てはまるのでしょうか、それとも現在のコンパイラは正規のLRパーサーで構築されているのでしょうか?

競合がある場合、LR(0) アクション テーブルの各エントリには、1 つのシフトと複数の削減アクションが含まれる場合があります。解析中に、スタックを分割することですべてのアクションを試すことができると思います。この解析方法には名前がありますか?

LR(1) パーサーで解析したい次の CFG があります。

S→A | B

A → ε | あ

B → ε |B

LR(1) パーサーはこの文法を解析できますか? もしそうなら、解析テーブルを見せてもらえますか? そうでない場合、その理由と、どのように判断できますか?

知っている：

言語が LL(1) 文法によって生成できる場合、その言語は LL(1) であると言われます。LL(1) 文法が

しかし、私は問題に遭遇しました。

なぜ文法

S-> aBDb

B -> ラムダ

D-> dD | ラムダ

なぜこの文法は LL(1) でも SLR でも LALR でもないのですか? 誰か私を説明できますか？

私の理解が正しければ、構文解析によって一連のシンボルがツリーに変換されます。私の質問は、標準的な手順 (LR、LL、PEG、..?) を使用して次の 2 つの例を解析することは可能ですか、それとも特殊なパーサーを手動で作成する必要がありますか?

1. Python ソース コード、つまり空白でインデントされたブロック

パーサーが先頭のスペースの数を追跡し、それらを中括弧に置き換えてブロックを区切るふりをどこかで読んだと思います。標準の解析手法が十分に強力ではないため、それが基本的に必要なのか、それともパフォーマンス上の理由からですか?

2. PNG 画像形式。ブロックはヘッダーとブロック サイズで始まり、その後にブロックのコンテンツが続きます。

コンテンツにはヘッダーに似たバイトが含まれる可能性があるため、次の x バイトが「解析」されないこと、つまりスキップされることを「認識する」必要があります。これを PEG で表現するにはどうすればよいでしょうか。つまり、「閉じ括弧」はコンテンツの長さで表されます。

私は正確に混乱しました!!!!!!

教授ノートの1つで次の例を読みました。

1) 次のような SLR(1) Grammar G があります。SLR(1) パーサー ジェネレーターを使用して、G の解析テーブル S を生成します。LALR(1) パーサー ジェネレーターを使用して、G の解析テーブル L を生成します。

解決策: S の R (reduce) を持つ要素の数が L を超えています。

しかし、あるサイトで私が読んだ：

2) T1、T2 が文法 G の SLR(1) と LALR(1) で作成されたとします。G が SLR(1) 文法の場合、次のうちどれが真ですか?

a) T1 と T2 に違いはありません。

b) T1 の非エラー エントリの合計数が T2 より少ない

c) T1 のエラー エントリの合計数が T2 より少ない

解決：

LALR(1) アルゴリズムは、SLR(1) アルゴリズムとまったく同じ状態を生成しますが、異なるアクションを生成できます。SLR(1) アルゴリズムよりも多くの競合を解決できます。ただし、文法が SLR(1) の場合、両方のアルゴリズムがまったく同じマシンを生成します (a が正しい)。

どれが真実であるかを説明できる人はいますか?

編集: 実際、私の質問は、特定の SLR(1) 文法について、LALAR(1) と SLR(1) の解析テーブルがまったく同じである理由です (エラーと非エラーのエントリは等しく、reduce の数は等しい)。しかし、上記の文法では、S の Reduced の数は L より多いです。

私は別の本で、一般的に次のことを知っています。

概要：

1) 質問 1 で私が書いた上記の文法の場合、還元される数が異なるのはなぜですか?

2) SLR(1) 文法がある場合、テーブルがまったく同じなのはなぜですか? (削減エントリとエラーエントリの数は同じになります)