in Compiler Design edited by
7,522 views
36 votes

Consider the $\text{SLR(1)}$ and $\text{LALR (1)}$  parsing tables for a context free grammar. Which of the following statement is/are true?

  1. The goto part of both tables may be different.
  2. The shift entries are identical in both the tables.
  3. The reduce entries in the tables may be different.
  4. The error entries in tables may be different
in Compiler Design edited by
7.5k views

3 Comments

I understood what a Shift entry is, a Reduce entry is and goto part is in parsing table. But what is an error entry?
0
blank in the parsing table
6
blank entries in table are treated as syntactical errors.
0

Subscribe to GO Classes for GATE CSE 2022

2 Answers

35 votes
 
Best answer
  • Goto part & shift entry must be same.
  • Reduce entry & error entry may b different due to conflicts.

Correct Answer: B;C;D.

edited by

19 Comments

Seeing some examples we can say that the goto entries and shift entries are same but can give u some ,logic behind it and why is not affected by the lookahead symbols present in LALR(1) parser .
0
in LALR(1) we merge LR(1) items states with same LR(0) items but with different lookaheads
2
answer must be b,c,d
9
  • Reduce entry & error entry may b different due to conflicts. I think reduce entries are different because of look a heads.
2
yes Reduce entries are different because of look aheads due to combining of states.

Reduce(LALR) >= Reduce(SLR)
5

Anu007  can you explain how "Reduce(LALR) >= Reduce(SLR)"? Does it means LALR can have more reduce entries than SLR?

0

@meghna @Anu007

Reduce entries in LALR and SLR are different unless Follow of nonterminals != Lookaheads

We can't always say that Reduce(LALR) >= Reduce(SLR)

In LALR we place reduce only in Lookaheads but in SLR we place it in FOLLOWs

Corrrect me if i am wrong

0
The Answer should be B, C & D.

Shift Entries are also identical in both SLR(1) & LALR(1).
1
Same applies for LR(0) as well right?
0
Yes
0

@Verma Ashish how?..... number of state in LR(0) & SLR(1)  not same

0

@VIDYADHAR SHELKE 1 

where i said that?

0
you said "yes".for this question answer applicable for also LR(0).
0
And there is no option about number of states..right?

Ofcourse there will be same number of states in slr(1), LR(0) and LALR(1).

But if question is about LR(0) and SLR(1) or LR(0) and LALR(0) then also same options will be correct...(that's why i added "yes" in that comment)
0
Bro.. number of state in LR(0)<=SLR(1)=LALR(1)..... it will be effect on GOTO entries .... so how can you say that This ans is also applicable for "LR(0) & SLR(1)" or  "LR(0) & LALR(1)"......................GOTO entries same because of number of state ........let me know if i am wrong
0
Number of states in LR(0) parsing table are always equal to states in SLR(1)..it can never be less
0
thank you very much  for correct me
0
If in ques asked for slr and clr then what would be ans?
0
Probably A,C,D because no of states in clr >= lr,slr,lalr. So the entries will definitely differ for clr when compared with any of the other 3 parsers
1
8 votes

All the LR parsers differ just in the placement of reduce moves.

The entire GoTo part is the same for LR(0), SLR(1), LALR(1) and CLR(1).

The placements of shift-moves is the same for LR(0), SLR(1), LALR(1) and CLR(1).

 

However, they differ in the placement of reduce moves. Which, in turn, makes them differ in the blank spaces(error entries) left in the parsing table.

 

Options B, C and D


How they differ in the placement of reduce moves in the parsing table?

  1. LR(0) puts reduce moves in the entire row for the final item.
     
  2. SLR(1) puts reduce moves only in the Follow() of LHS of the final item.
     
  3.  CLR(1) puts reduce moves only in the lookaheads of the final item.
     
  4. LALR(1) puts reduce moves in all the merged lookaheads for same final items. (You need to get a grip over LR(1) items to get this line)

4 Comments

don’t you think that since CLR(1) has more states and therefore even the shift entries differ? Even though the number of error entries does not change in both.

For example, suppose in LALR(1) there is a state $I_{47}$ in two-shift entries. Then CLR(1) will split that state because of different look-aheads and will have $I_{4}$ as one shift entry and $I_{7}$ as another.

So shouldn’t we say that LALR(1) and LR(1) differ in shift entries too?
0
why error entries are same?
0
oh yes, even error entries will differ since we will get extra rows.
1

The entire GoTo part is the same for LR(0), SLR(1), LALR(1) and CLR(1).

False.

Reason: if the number of states is different, then no of GOTO must be different. Why? without GOTO, you can't reach the states. if you're saying there is a new state compare to SLR with CLR, then there exists a GOTO entry to reach that state. 

0
Answer:

Related questions