IAE Academy

GATE 2022 CS Q.13: solution and answer

GATE 2022 · CSQ.13 · 1 mark · MCQ

Which one of the following statements is TRUE?

  1. (A)

    The parser for a grammar cannot have reduce-reduce conflict if the parser for does not have reduce-reduce conflict.

  2. (B)

    Symbol table is accessed only during the lexical analysis phase.

  3. (C)

    Data flow analysis is necessary for run-time memory management.

  4. (D)

    parsing is sufficient for deterministic context-free languages.

See the question in the paper
GATE 2022 CS question 13Tap to open full size

Answer and solution

ANSWER

The true statement is (D): LR(1) parsing is sufficient for deterministic context-free languages.

Official answer: DSource: Official answer key, GATE 2022 CS (IIT Kharagpur)

  1. Check (A). LALR(1) merges LR(1) states that have the same core, and the merged state takes the union of their lookahead sets. Two reduce items that had disjoint lookaheads in separate LR(1) states can have overlapping lookaheads after the merge.

  2. So a grammar can have no reduce-reduce conflict in LR(1) and still have one in LALR(1). (A) is false. The converse does hold: merging only adds lookaheads, so an LR(1) reduce-reduce conflict remains in LALR(1).

  3. Check (B). The symbol table is used in lexical analysis, and also in syntax analysis, semantic analysis (type checking, scope), code generation and optimization. The word 'only' makes (B) false.

  4. Check (C). Run-time memory management (stack frames, heap allocation, garbage collection) does not need data flow analysis. Data flow analysis is a compile-time technique used for optimization, so (C) is false.

  5. Check (D). Every deterministic context-free language has an grammar, so an parser exists for every deterministic CFL. parsing is therefore sufficient for deterministic context-free languages, and (D) is true.

  6. Answer: D.

KEY IDEA

The languages that LR(1) grammars generate are exactly the deterministic context-free languages. LALR(1) merges same-core LR(1) states and unions their lookaheads, so it can gain conflicts that LR(1) does not have.

WATCH OUT FOR

Choosing (A) because LALR(1) is built from LR(1). Merging states can create reduce-reduce conflicts that LR(1) does not have, though it never creates shift-reduce conflicts that LR(1) lacks.

From the GATE 2022 CS paper. Every question of this paper · Download the full paper · All 13 Parsing questions, with notes

More Parsing questions