SLR(1) and LALR(1) and Reduce

问题:

I confused Exactly !!!!!!

I read following example in one of my professor note.

1) we have a SLR(1) Grammar G as following. we use SLR(1) parser generator and generate a parse table S for G. we use LALR(1) parser generator and generate a parse table L for G.

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.

but in one site i read:

2) Suppose T1, T2 is created with SLR(1) and LALR(1) for Grammar G. if G be a SLR(1) Grammar which of the following is TRUE?

a) T1 and T2 has not any difference.

b) total Number of non-error entries in T1 is lower than T2

c) total Number of error entries in T1 is lower than T2

Solution:

The LALR(1) algorithm generates exactly the same states as the SLR(1) algorithm, but it can generate different actions; it is capable of resolving more conflicts than the SLR(1) algorithm. However, if the grammar is SLR(1), both algorithms will produce exactly the same machine (a is right).

any one could describe for me which of them is true?

EDIT: infact my question is why for a given SLR(1) Grammar, the parse table of LALAR(1) and SLR(1) is exactly the same, (error and non-error entries are equal and number of reduce is equal) but for the above grammar, the number of Reduced in S is more than L.

I see in another book that in general we have:

Summary:

1) for the above grammar that i wrote in question 1, why number of reduced is different?

2) if we have a SLR(1) Grammar, why the table is exactly the same? (number of reduced and error entries become the same)

回答1:

Both of these statements are true!

One of your questions was why SLR(1) and LALR(1) parsers have the same states as one another. SLR(1) parsers are formed by starting with an LR(0) automaton, then augmenting each production with lookahead information from FOLLOW sets. In an LALR(1) parser, we begin with an LR(1) parser (where each production has very precise lookahead information), then combine any two states that have the same underlying LR(0) state. This results in an LR(0) automaton with additional information because each LR(0) state corresponds to at least one LR(1) state and each LR(1) state corresponds to some underlying LR(0) state.

SLR(1) and LALR(1) parsers both have the same set of states, which are the same states as in an LR(0) parser. The parsers differ only in what actions they perform in each state.

In both SLR(1) and LALR(1) parsers, each item has an associated set of lookahead tokens. Whenever the parser enters a state with a reduce item in it, the parser will perform that reduction if the next token of input is in the lookahead set. In an SLR(1) parser, the lookahead set is the FOLLOW set for the nonterminal on the left-hand side of the production. In an LALR(1) parser, the lookahead set is, appropriately, called the LA set for the combination of the nonterminal in the production and the automaton state.

You can prove that the LA sets used in an LALR(1) parser are subsets of the FOLLOW sets used in SLR(1) parsers. This means that LALR(1) parsers will never have more reduce actions than SLR(1) parsers, and in some cases the LALR(1) parsers will choose to shift when an SLR(1) parser would have a shift/reduce conflict.

Hope this helps!

回答2:

Answer to Q1:

First of all you need to create DFA for SLR(1) and LALR(1) parsers. I created DFA for both of them.

Link to images of DFAs SLR(1) and LALR(1) DFAs

For SLR(1) I got 10 states and 10 reduce entries whereas for LALR(1) I created DFA for CLR(1) with 13 states which got minimized to 10 states with 7 reduce entries. Thats answers your first question.

---

Answer to Q2:

G is SLR(1) grammar, then surely there are no conflicts (or error) S-R or R-R in the SLR(1) table. LALR(1) has more power than SLR(1),therefore there is also no conflict in LALR(1) table for given grammar G. Lets see option by option

(c) : there no error in T1 and T2 (wrong option)

(b) : Non-error entries means shift entries and reduce entries. It should be clearly noted that in bottom up parsers from parser to parser only rules for reduce entries changes while for that of shift entries remain same. For e.g in LR(0) reduce entries are made in each column, for SLR(1) it is done in FOLLOW of left hand side variable, while in CLR(1) and LALR(1) reduce entries are made in lookahead symbols. Thus reduce entries changes from parser to parser but shift entries are same.

We have also already proved in Q1 where reduce entries of SLR(1) parsing table are more than that of LALR(1). Therefore proving (b) option to be incorrect.

(a) T1 and T2 may come out to be same but not always. And other important thing is that multiple choice questions sometimes wants you to choose most appropriate option. Thus for me (a) is the answer