Bissoy.com
Doctors Medicines MCQs Q&A

Consider the following two sets of LR(1) items of an LR(1) grammar. X → c.X, c/d           X → c.X, $ X → .cX, c/d           X → .cX, $ X → .x, c/d             X → .d, $ Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE? 1. Cannot be merged since look aheads are different. 2. Can be merged but will result in S-R conflict. 3. Can be merged but will result in R-R conflict. 4. Cannot be merged since goto on c will lead to two different sets.

Consider the following two sets of LR(1) items of an LR(1) grammar. X → c.X, c/d           X → c.X, $ X → .cX, c/d           X → .cX, $ X → .x, c/d             X → .d, $ Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE? 1. Cannot be merged since look aheads are different. 2. Can be merged but will result in S-R conflict. 3. Can be merged but will result in R-R conflict. 4. Cannot be merged since goto on c will lead to two different sets. Correct Answer 1, 2, 3 and 4

The correct answer is option 4.

Key Points

1. Cannot be merged since lookaheads are different.

False, We can find the LALR stage by merging LR(1) states that have the same set of the first component. We can take the union of lookahead symbol of the respective item. The given LR (1) items can be merged as, 

X → c.X, c/d/$

X → .cX, c/d/$  

X → .x, c/d/$   

2. Can be merged but will result in S-R conflict.

3. Can be merged but will result in R-R conflict.

The given items have no reduced entry(means dot at end of the production) then there is no S-R conflict and R-R conflict in the given grammar. So clearly it says both option 2 and 3 are false. 

4. Cannot be merged since goto on c will lead to two different sets. 

False, Because goto is carried on Non-terminals symbols, not on terminal symbols, and c is a terminal symbol.

Hence the correct answer is 1, 2, 3 and 4.

Additional Information

Checking LALR conflicts:

Shortcut:

[ alt="F1 Raju Madhuri 29.05.2021 D11" src="//storage.googleapis.com/tb-img/production/21/05/F1_Raju_Madhuri_29.05.2021_D11.png" style="width: 185px; height: 137px;">

Let's consider the production A → αaβ and B→α and a,b are lookaheads of the grammar. Then S-R conflicts will occur when one production with reducing production and another one is a shift production. This will make the conflict when shifting terminal and lookahead are same then parsing table has multiple entries. And R-R conflicts have two productions with the same lookaheads.

  • If there is no S-R conflict in LR(1) state it never be reflected in the LALR(1) parser.
  • If there is no R-R conflict in LR(1) state it may be R-R conflict in LALR(1) parser.
  • The parse generates tool 'YAAC' uses LALR(1) parsing algorithm. 

Related Questions

Which of the following statements is/are correct? A. SLR parser is more powerful than LALR parser. B. Canonical LR parser is more powerful than LALR parser. C. LALR parser is more powerful than Canonical LR parser.
Which of the following statement(s) is/are FALSE? (i) The grammar S → Aa | bAc | dc | bda, A → d is LALR(1) but not SLR(1). (ii) The grammar S → Aa | bAc | Bc | bBa, A → d, B → d is LALR(1) but not LR(1).
Which of the following statements are TRUE? I. Top-down parsers are equipped to handle left recursive grammar. II. LALR parser is more powerful than an SLR parser. III. Recursive descent parsing is an example of top-down parsing.
Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. Hence which one is true?
Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states.
LALR in LALR parser stands for:
Which of the following statements is/are true/false regarding modes of Conflict Management Styles?
1. The avoidance modes of conflict management aim at avoiding or postponing conflicts.
2. The compromise mode involves coercion and is likely to fail to reach a solution.
3. The main objective of the defusion mode of conflict resolution is to buy time for dealing with a conflict.
4. Withdrawal is a form of approach mode that involves getting away from a conflict situation.
An LALR(1) parser for a grammar can have shift-reduce (S-R) conflicts if and only if ___________
Consider the following statements. S1 : Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1). S2 : For any context-free grammar, there is a parser that takes at most O(n3) time to parse a string of length n. Which one of the following option is correct?
Which of the following statements are true of the teaching of grammar. A. Teaching of rules at the initial stage does not lend much to language learning. B. Rules of grammar are essential during the formative years of language learning. C. Grammar teaching should move from meaning to form. D. Grammar teaching should move from form to meaning.