# Recent questions tagged go2019-cd1

1
If we merge states in LR(1) parser to form a LALR(1) parser, we may introduce shift-reduce conflict reduce-reduce conflict no extra conflict both shift-reduce as well as reduce-reduce
2
Suppose we have a rightmost derivation which proceeds as follows: $\begin{array}{ccc}S &\rightarrow & Aabw \\ & \rightarrow &ABw \end{array}$ Which of the following is a possible handle for it? $\begin{array}{ccc} A &\rightarrow & ab \end{array}$ ... $\begin{array}{ccc} S &\rightarrow & A \end{array}$ $\begin{array}{ccc} B &\rightarrow & ab \end{array}$
3
Which of the following statements is FALSE? Any DCFL has an equivalent grammar that can be parsed by a SLR(1) parser with end string delimiter Languages of grammars parsed by LR(2) parsers is a strict super set of the languages of grammars parsed by LR(1) parsers Languages of ... of grammars parsed by LL(1) parsers There is no DCFL which is not having a grammar that can be parsed by a LR(1) parser
4
Which of the following statements is FALSE? In a SLR(1) parser, it is allowable for both shift and reduce items to be in the same state In a SLR(1) parser, it is allowable for multiple reduce items to be in the same state All SLR(1) grammars are LR(0) All LR(0) grammars are SLR(1)
5
Which of the following statements regarding $LR(0)$ parser is FALSE? A $LR(0)$ configurating set cannot have multiple reduce items A $LR(0)$ configurating set cannot have both shift as well as reduce items If a reduce item is present in a $LR(0)$ configurating set it cannot have any other item A $LR(0)$ parser can parse any regular grammar
6
Which of the following sentences is CORRECT? A top-down parse produces a leftmost derivation of a sentence A bottom-up parse produces a rightmost derivation of a sentence A top-down parse produces a rightmost derivation of a sentence A bottom-up parse produces a leftmost derivation of a sentence
7
Which of the following is a requirement for LL(1) grammar? Unambiguity No left recursion If $A \to \alpha \mid \beta$ are two productions, then $FIRST(\alpha)$ and $FIRST(\beta)$ are disjoint (i) and (ii) (iii) (i), (ii) and (iii) (ii) and (iii)
8
Which of the following sentences regarding Viable prefixes is/are CORRECT? Viable prefixes is the set of prefixes of right-sentential forms that can appear on the stack of a shift-reduce parser Viable prefixes is the set of prefixes of right-sentential forms that do not extend past the end of the ... prefixes can be recognized using a DFA Only (i) Only (ii) Only (i) and (ii) (i), (ii) and (iii)
9
For which of the following languages a LL(1) grammar does not exist? $\{a^n o b^n \mid n \geq 1\} \cup \{ a^n b^{n} \mid n \geq 1 \}$ $\{ a^n b^m \mid m,n \geq 0 \}$ $\{a^ib^j\mid i\geq j\}$ $\{a^ib^j\mid i= j\}$
10
Which of the following is TRUE regarding LL(0) grammar? We can have a LL(0) grammar for any regular language We can have a LL(0) grammar for a regular language only if it does not contain empty string We can have a LL(0) grammar for any regular language if and only if it has prefix property We can have a LL(0) grammar for only single string languages
1 vote
11
Which of the following is TRUE regarding the running time of a LR(1) parser? It runs in linear time for all inputs It runs in polynomial time but not necessarily $O(n^3)$ for all inputs For some inputs it may take exponential time It runs in $O(n^3)$ but not always $O(n^2)$
Match the following: $\begin{array}{|cc|cc|} \hline (i) &LL(1)&(A)& \text{bottom-up} \\ \hline (ii)& \text{Recursive Descent}& (B) &\text{Predictive} \\ \hline (iii) &\text{Recursive Ascent}& (C)& \text{Top-down} \\ \hline (iv) &LR(1) &(D)& \text{Deterministic CFL} \\ \hline \end{array}$ i-b; ii-c; iii-a; iv-d i-d; ii-a; iii-c; iv-d i-c; ii-b; iii-d; iv-a i-a; ii-c; iii-b; iv-d
Which of the below relations does hold TRUE regarding GRAMMARS? $LL(1) \subset SLR(1) \subset LR(1)$ $SLR(1) \subset \epsilon-\text{free}\; LL(1) \subset LR(1)$ $\epsilon-\text{free}\;LL(1) \subset SLR(1) \subset LR(1)$ $LL(1) \subset SLR(1) = LR(1)$