in Compiler Design edited by
1,872 views
3 votes
3 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.
in Compiler Design edited by
by
1.9k views

2 Comments

0
0

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

1 Answer

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

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.

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

edited by
Answer:

Related questions