GATE CSE 2022 | Question: 3

Question

Which one of the following statements is $\text{TRUE}?$

• A. The $\textit{LALR}(1)$ parser for a grammar $\textit{G}$ cannot have reduce-reduce conflict if the $\textit{LR}(1)$ parser for $\textit{G}$ does not have reduce-reduce conflict.
• B. Symbol table is accessed only during the lexical analysis phase.
• C. Data flow analysis is necessary for run-time memory management.
• D. $\textit{LR}(1)$ parsing is sufficient for deterministic context-free languages.

Comments

@ShouvikSVK These points are taken from Gatecse

---

the set of languages parseable by LR(1) parsers is exactly the set of deterministic context-free languages. 

---

$
\begin{aligned}
&\text{Grammars: } \mathrm{LR}(0) \subset \mathrm{LR}(1) \subset \mathrm{LR}(2) \subset \cdots \quad (\text{strict subset hierarchy}) \\
&\text{Languages: } \mathcal{L}(\mathrm{LR}(1)) = \mathcal{L}(\mathrm{LR}(2)) = \cdots = \mathcal{L}(\mathrm{LR}(k))
\end{aligned}
$
 

Increasing the lookahead k allows you to write simpler grammars for the same language, but it does not allow you to parse new languages that couldn't be parsed with k=1.
 

Source: Keith_Cooper_Linda_Torczon-Engineering_a_Compiler-EN.pdf

Answer 1

Answer D

$\text{Option A}$

Connsider a LR(1) DFA with no RR Conflicts. Take two states, say, I3 and I5 in such LR(1) DFA.

I3 :  $[A \rightarrow \alpha.\color{red}{, a}, B \rightarrow \beta.\color{blue}{, b}]$ and

I5: $[A \rightarrow \alpha.\color{blue}{, b}, B \rightarrow \beta.\color{red}{, a}]$

Since the core items are same, we will merge $I_3$ and $I_5$ in LALR, say merged state is $I_{35}$

$I_{35}$ :  $[A \rightarrow \alpha.\color{red}{, a}\color{blue}{, b} \text{  } B \rightarrow \beta.\color{red}{, a}\color{blue}{, b}]$ 

A common confusion: $I_{35}$ has RR conflict on $a \text{ and } b$.​

$\text{Do } I_{35} \text{ really has any conflict? }$ –  Yes.

See one example – here

 

$\text{Option B}$

Symbol table is accessed among all phases. For example – “int x”, here lexical analyzer will assign 2 tokens, but lexical  analyzer won’t know whether x is of type int since it reads int and x as two different tokens. Syntax analyzer will feed type of x to symbol table.

C. It is optional

D. LR(1) = DCFL Ref: https://cs.stackexchange.com/questions/43/language-theoretic-comparison-of-ll-and-lr-grammars

Comments

About option C: Data flow Analysis helps in Code Optimization. This phase is not compulsory and is optional. Thus, terming it as a “necessary” step makes option C False.

---

https://cs.stackexchange.com/questions/68499/every-dcfl-has-an-lr1-an-lalr1-and-even-an-slr1-grammar

---

For those like me who did not understand the explanation for option A, this is how the reduce-reduce conflict emerges: 

• The parser in state $I_{35}$ sees either lookahead token 'a' or 'b'.
• Both reductions for A and B are vaild on these lookaheads since the lookaheads for the two items are merged as {a, b} in LALR.
• When reducing, the parser much decide which production to reduce by, but it cannot decide between $A \to \alpha .$ and $B \to \beta .$ because both are simultaneously applicable for the same lookahead tokens.
• This ambiguty causes a reduce-reduce conflict as two different reductions are valid on the same lookahead.

Note that 'a' and 'b' are lookaheads in the answer. 

Answer 2

A. 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.

❌ False

• LALR(1) is obtained by merging LR(1) states that have the same LR(0) core.

• When states are merged, their lookahead sets are combined.

• This merging can introduce new conflicts, including reduce–reduce conflicts, even if the original LR(1) parser had none.

✅ Hence, LR(1) being conflict-free does not guarantee LALR(1) will be conflict-free.

---

B. Symbol table is accessed only during the lexical analysis phase.

❌ False

The symbol table is used in multiple phases, such as:

• Lexical analysis (installing identifiers)

• Semantic analysis (type checking, scope checking)

• Intermediate code generation (addresses, types)

• Optimization / Code generation (storage locations)

✅ Hence, it is not limited to lexical analysis.

---

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

❌ False

• Run-time memory management (stack allocation, heap management, garbage collection) is mainly handled by the runtime system and compilation strategy.

• Data flow analysis is primarily used for compile-time optimizations, such as:

  • dead code elimination

  • reaching definitions

  • liveness analysis (used for register allocation, not runtime memory allocation)

✅ Hence, it is not necessary for runtime memory management.

---

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

✅ True

• Deterministic context-free languages (DCFLs) are exactly the class of languages accepted by deterministic pushdown automata (DPDA).

• It is a known result in compiler theory that LR(1) parsers can parse all deterministic CFLs.

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