2,031 views

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

1. 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.
2. Symbol table is accessed only during the lexical analysis phase.
3. Data flow analysis is necessary for run-time memory management.
4. $\textit{LR}(1)$ parsing is sufficient for deterministic context-free languages.

Notable Points:

1. LR(0) ⊂ LR(1) = LR(2) = LR(K), note this is not true for LL(k) grammars
2. LR(0) set of Grammars is equivalent with Set of All DCFL that is having Prefix Property. (Prefix Property: This is a property which says that let L1 be a string and belongs to your Language then no other Prefix of this string in this language)
3. LR(1) set of Languages are equivalent to Set of all DCFL languages.

$\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? }$ –

if $\alpha = \beta$ then only it has a conflict otherwise ($\alpha \neq \beta$ ) it doesn't have any conflict. Most of the aspirant miss this crucial point. More importantly, think if any state can have such items in single state if $\alpha \neq \beta$ ?.

$\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