retagged by
7,262 views
9 votes
9 votes

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.
retagged by

1 Answer

Best answer
13 votes
13 votes

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

selected by
Answer:

Related questions

7 votes
7 votes
3 answers
2
Arjun asked Feb 15, 2022
5,749 views
Consider the following grammar along with translation rules.$$\begin{aligned} & S \rightarrow S_{1} \# T \qquad \{S._{\text{val}} =S_{1}. _{\text{val}} \; ^{\ast} T._{\te...
13 votes
13 votes
1 answer
3
Arjun asked Feb 15, 2022
5,611 views
Let $r$ be a root of the equation $x^{2} + 2x + 6 = 0.$Then the value of the expression $(r+2) (r+3) (r+4) (r+5)$ is$51$$-51$$126$$-126$
36 votes
36 votes
2 answers
4
Arjun asked Feb 15, 2022
15,474 views
Which one of the following statements is $\text{TRUE}$ for all positive functions $f(n)?$$f(n^{2}) = \theta (f(n)^{2}),$ when $f(n)$ is a polynomial$f(n^{2}) = o (f(n)^{2...