The Gateway to Computer Science Excellence
+29 votes

Choose the correct alternatives (more than one may be correct ) and write the corresponding letters only:

Consider the $SLR(1)$ and $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 by
edited by | 2.9k views
I understood what a Shift entry is, a Reduce entry is and goto part is in parsing table. But what is an error entry?
blank in the parsing table

2 Answers

+26 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
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 .
in LALR(1) we merge LR(1) items states with same LR(0) items but with different lookaheads
answer must be b,c,d
  • Reduce entry & error entry may b different due to conflicts. I think reduce entries are different because of look a heads.
yes Reduce entries are different because of look aheads due to combining of states.

Reduce(LALR) >= Reduce(SLR)

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


@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

The Answer should be B, C & D.

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

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



where i said that?

you said "yes".for this question answer applicable for also LR(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)
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
Number of states in LR(0) parsing table are always equal to states in SLR(1) can never be less
thank you very much  for correct me
If in ques asked for slr and clr then what would be ans?
+2 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)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,469 answers
95,272 users