GATE CS 2022 Q.13: Parsing and Syntax Analysis (LL and LR)

Which one of the following statements is TRUE?

The LALR (1) parser for a grammar G cannot have reduce-reduce conflict if the LR (1) parser for G does not have reduce-reduce conflict.

Symbol table is accessed only during the lexical analysis phase.

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

LR (1) parsing is sufficient for deterministic context-free languages.

Official answer and solution

Official answer: D
From: Official GATE 2022 answer key

Solution

Evaluate standard compiler design concepts regarding parser classes, symbol table phases, and data flow analysis.

We evaluate each statement:

(A) FALSE: Merging states with identical cores in an LR(1) parser to form an LALR(1) parser can create reduce-reduce conflicts that were not present in the original LR(1) parser.
(B) FALSE: The symbol table is accessed throughout multiple compiler phases, including lexical analysis, syntax analysis, semantic analysis, intermediate code generation, and optimization.
(C) FALSE: Data flow analysis is used at compile time for code optimizations (such as dead code elimination, constant propagation, and register allocation), not for run-time memory management.
(D) TRUE: Every deterministic context-free language (DCFL) can be parsed by an LR(1) parser, making LR(1) parsing sufficient for all DCFLs.

Final answer

Option (D)

Common trap

Thinking that merging LR(1) states cannot introduce any conflicts; state merging never introduces shift-reduce conflicts, but it can introduce reduce-reduce conflicts.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2022 Computer Science and Information Technology (CS)
Question: 13 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source