GATE CS Parsing (LL, LR) questions

Consider the following grammar: stmt $\rightarrow$ if expr then expr else expr; stmt | $Ò$ expr $\rightarrow$ term relop term | term term $\rightarrow$ id | number id $\rightarrow$ a | b | c number $\rightarrow [0-9]$ where relop is a relational operator $($e.g., $< , >,\ldots),$ $Ò$ refers to the empty statement, and if, then, else …

Consider the following expression grammar $G$: $E \rightarrow E-T \mid T$ $T \rightarrow T + F \mid F$ $F \rightarrow (E) \mid id$ Which of the following grammars is not left recursive, but is equivalent to $G$?

Which of the following statements about parser is/are CORRECT? $\text{Canonical LR}$ is more powerful than $\text{SLR}$ $\text{SLR}$ is more powerful than $\text{LALR}$ $\text{SLR}$ is more powerful than $\text{Canonical LR}$

The attribute of three arithmetic operators in some programming language are given below. …

A student wrote two context-free grammars G1 and G2 for generating a single C-like array declaration. The dimension of the array is at least one. For example, int a[10] [3]; The grammars use D as the start symbol, and use six terminal symbols int ; id [ ] num. …

Which one of the following grammars is free from left recursion?

Which one of the following is TRUE at any valid state in shift-reduce parsing?

Consider the following grammar G $S \rightarrow F \mid H$ $F \rightarrow p \mid c$ $H \rightarrow d \mid c$ Where $S$, $F$, and $H$ are non-terminal symbols, $p, d$, and $c$ are terminal symbols. Which of the following statement(s) is/are correct? S1: LL(1) can parse all strings that are generated using grammar G S2: LR(1) can parse all …

Among simple LR (SLR), canonical LR, and look-ahead LR (LALR), which of the following pairs identify the method that is very easy to implement and the method that is the most powerful, in that order?

A canonical set of items is given below $S \to L .> R$ $Q \to R.$ On input symbol $<$ the set has

Consider the grammar defined by the following production rules, with two operators $∗$ and $+$ $S\:\to\:T∗P$ $T\:\to\:U\mid T∗U$ $P\:\to\:Q+P\mid Q$ $Q\:\to Id$ $U\:\to Id$ Which one of the following is TRUE?

Consider the following two sets of $\textsf{LR(1)}$ items of an $\textsf{LR(1)}$ grammar.$$\begin{array}{l|l} X \rightarrow c.X, c∕d &X → c.X, \$\\ X \rightarrow .cX, c∕ d& X → .cX, \$\\ X \rightarrow .d, c∕ d & X → .d, \$ \end{array}$$Which of the following statements related to merging of the two sets in the corresponding $\textsf{LALR}$ …

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon and unit-production (i.e., of type $A \rightarrow \epsilon$ and $A \rightarrow a$) to parse a string with $n$ tokens?

For the grammar below, a partial $LL(1)$ parsing table is also presented along with the grammar. Entries that need to be filled are indicated as $E1, E2,$ and $E3$. $\varepsilon$ is the empty string, \$ indicates end of input, and, $\mid$ separates alternate right hand sides of productions. $S \rightarrow a A b B \mid b A a B \mid \varepsilon$ …

Consider two binary operators $\text{‘} \uparrow \text{’}$ and $\text{‘} \downarrow \text{’}$ with the precedence of operator $\downarrow$ being lower than that of the operator $\uparrow$. Operator $\uparrow$ is right associative while operator $\downarrow$ is left associative. Which one of the following represents the parse tree for expression …

The grammar $S \to aSa \mid bS \mid c$ is

Which of the following statements are TRUE? There exist parsing algorithms for some programming languages whose complexities are less than $\Theta(n^3)$ A programming language which allows recursion can be implemented with static storage allocation. No L-attributed definition can be evaluated in the framework of bottom-up parsing. Code improving …

An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if

Which of the following describes a handle (as applicable to LR-parsing) appropriately?

Which of the following statements are true? Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa All $\epsilon$-productions can be removed from any context-free grammar by suitable transformations The language generated by a context-free grammar all of whose productions are of the form $X \rightarrow w$ or …