0

数日前にSLR(1) と LALR(1) と Reduceについて質問 します。多くの検索と教授への連絡を行っていますが、2番目の問題の解決策が正しいか間違っているかを要約できませんでした。2 つの異なる年の入試で 2 つの質問があります。

二問は選択式です。2010年の質問では、次のようにしています。

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

S->AB
A->dAa
A-> lambda (lambda is a string with length=0)
B->aAb

そして、質問デザイナーは次のようにソリューションを選択します。

Solution: the number of elements with R (reduce) in S is more than L.

2 年後、デザイナーは次のように質問します。

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

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

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

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

解決：

(a) is selected by the question designer.

私の質問は：

any one could describe for me why the solution of 1st question is contradict to 2nd question?

誰かが以前の投稿で 2 つの解決策が正しいと答えましたが、非常に整形式であるとは説明していません。

とにかく私は混乱から抜け出す専門家を待っています!!!

4

1 に答える 1

1

Q1 への回答:

まず、SLR(1) および LALR(1) パーサー用の DFA を作成する必要があります。両方の DFA を作成しました。

SLR(1) および LALR(1) DFA

SLR(1) では 10 の状態と 10 の削減エントリを取得しましたが、LALR(1) では 13 の状態で CLR(1) の DFA を作成し、7 つの削減エントリで 10 の状態に最小化しました。それはあなたの最初の質問に答えます。

Q2 への回答:

G は SLR(1) 文法であり、SLR(1) テーブルに競合 (またはエラー) SR または RR はありません。LALR(1) は SLR(1) よりも強力であるため、指定された文法 G の LALR(1) テーブルにも競合はありません。オプションごとに見てみましょう。

(c) : T1 と T2 にエラーはありません (間違ったオプション)

(b) : 非エラーエントリとは、シフトエントリとリデュースエントリを意味します。パーサーからパーサーへのボトムアップ パーサーでは、レデュース エントリのルールのみが変更され、シフト エントリのルールは同じままであることに注意してください。たとえば、LR(0) では縮小エントリは各列で作成され、SLR(1) では左側の変数の FOLLOW で作成されますが、CLR(1) と LALR(1) では縮小エントリは先読みシンボルで作成されます。したがって、パーサーからパーサーへのエントリの変更を減らしますが、シフト エントリは同じです。

また、Q1 では、SLR(1) 解析テーブルのエントリの削減が LALR(1) のエントリの削減よりも多いことも既に証明されています。したがって、(b) オプションが正しくないことを証明します。

(a) T1 と T2 は同じになる場合がありますが、常にそうとは限りません。もう 1 つの重要な点は、多肢選択式の質問では、最も適切な選択肢を選択する必要がある場合があることです。したがって、私にとっては (a) が答えです

于 2015-01-18T15:30:42.870 に答える