Parsing Practice Questions

To construct the predictive parsing table $M$, we first determine the $FIRST$ and $FOLLOW$ sets:
$FIRST(F) = \{id\}$, $FIRST(R) = \{*, \varepsilon\}$, and $FIRST(S) = FIRST(FR) = \{id\}$.
The $FOLLOW$ set for $R$ is FOLLOW(R) = FOLLOW(S) = \{\}$because$R$follows$S$\in the production$S \rightarrow FR$. For$M[S, id]$, since$id \in FIRST(FR)$, the entry is${S \rightarrow FR}$. For$M[R, $]$, since$R \rightarrow \varepsilon$is a production and$$ \in FOLLOW(R)$, we include the production${R \rightarrow \varepsilon}$. Thus,$M[S, id] = {S \rightarrow FR}$and$M[R, $] = {R \rightarrow \varepsilon}$.

The grammar $S \rightarrow (S) \mid a$ is augmented as $S' \rightarrow S$. The number of states for an $\text{SLR}(1)$ parser is equal to the number of states in the $\text{LR}(0)$ state machine, as $\text{SLR}(1)$ uses $\text{LR}(0)$ kernels with $\text{FOLLOW}$ sets. $\text{LALR}(1)$ parsers are constructed by merging $\text{LR}(1)$ states that have the same $\text{LR}(0)$ core, which results in the same number of states as the $\text{LR}(0)$ collection. Thus, $n_1 = n_3$.

For this grammar, the $\text{LR}(0)$ collection contains 6 states. $\text{LR}(1)$ parsers maintain distinct lookahead sets for items, causing state splitting when lookaheads differ (e.g., distinguishing between reductions after $a$ at different nesting levels), which results in $n_2 > 6$. Therefore, the relationship is $n_1 = n_3 < n_2$.

A grammar is ambiguous if there exists at least one string in the language with more than one leftmost derivation or parse tree. The rule $E \rightarrow E+E$ is inherently ambiguous because it does not specify associativity, allowing multiple ways to group additions for strings with three or more $id$ tokens. For the string $id+id+id+id$, we can derive it as $(id+id)+(id+id)$, $((id+id)+id)+id$, or $id+(id+(id+id))$, all of which correspond to different parse trees. The other options contain parentheses that force a specific structure, uniquely defining the order of operations for the multiplication or addition operators in those specific strings. Therefore, only $id+id+id+id$ is ambiguous.

Since the target string $\text{id} + \text{id} + \text{id} + \text{id}$ contains no parentheses or the symbol $*$, the production $E \rightarrow (E * E)$ cannot be used. The grammar effectively reduces to $E \rightarrow E+E \mid \text{id}$. For an expression with $n$ identifiers and a binary operator, the number of distinct parse trees is given by the $(n-1)$-th Catalan number, $C_{n-1}$. With $n=4$ identifiers, we calculate $C_3$:
$C_n = \frac{1}{n+1} \binom{2n}{n} \implies C_3 = \frac{1}{4} \binom{6}{3} = \frac{1}{4} \times 20 = 5$
These 5 trees correspond to the distinct ways to parenthesize the expression: $((\text{id}+\text{id})+\text{id})+\text{id}$, $(\text{id}+(\text{id}+\text{id}))+\text{id}$, $(\text{id}+\text{id})+(\text{id}+\text{id})$, $\text{id}+((\text{id}+\text{id})+\text{id})$, and $\text{id}+(\text{id}+(\text{id}+\text{id}))$.

To find the handles for the sentence $n + n * n$ using the grammar $E \rightarrow E + n \mid E * n \mid n$, we perform a bottom-up reduction:

1. Start: The sentence is $n + n * n$.
2. Reduce: Replace the first $n$ with $E$ ($E \rightarrow n$). The handle is $n$. The form becomes $E + n * n$.
3. Reduce: Replace $E + n$ with $E$ ($E \rightarrow E + n$). The handle is $E + n$. The form becomes $E * n$.
4. Reduce: Replace $E * n$ with $E$ ($E \rightarrow E * n$). The handle is $E * n$. The form becomes $E$.

The sequence of handles identified during the reduction process is $n, E + n,$ and $E * n$.

The given grammar $E \rightarrow \text{number} | E + E | E \times E$ is ambiguous because it lacks definitions for operator precedence and associativity. When parsing an expression such as $\text{number} + \text{number} \times \text{number}$, the parser reaches a state with the stack containing $E + E$ and the lookahead token being $\times$. At this point, the parser faces a choice: reduce $E + E$ to $E$ (performing addition) or shift the $\times$ operator onto the stack. This ambiguity results in a shift-reduce conflict. By default, Yacc resolves such shift-reduce conflicts by prioritizing the shift action over the reduce action.

A grammar is suitable for predictive parsing only if it is unambiguous and free of left recursion. The grammar $A \rightarrow AA \mid (A) \mid \varepsilon$ is inherently ambiguous because it generates multiple leftmost derivations for the same string, such as "()".
First derivation: $A \Rightarrow (A) \Rightarrow (\varepsilon) \Rightarrow ()$.
Second derivation: $A \Rightarrow AA \Rightarrow (A)A \Rightarrow (\varepsilon)A \Rightarrow ()A \Rightarrow ()\varepsilon \Rightarrow ()$.
Because the input string "()" has more than one distinct parse tree, the grammar is classified as ambiguous.
Consequently, it is unsuitable for predictive parsing, which requires a unique derivation for every input.

The provided grammar $E \rightarrow \text{number} \mid E \text{ '+' } E \mid E \text{ 'x' } E$ is ambiguous because it does not define operator precedence or associativity. When such a grammar is processed by a parser generator configured for right associativity with equal precedence, the expression $3 \times 2 + 1$ is parsed by grouping from the right. This structures the expression as $3 \times (2 + 1)$. Calculating this result gives $3 \times 3 = 9$. Since the parsing logic groups the right-hand operation first, it realizes right associativity, matching the provided target.

The grammar rules define $\#$ (in $E \to E \# T$) as having lower precedence than $\&$ (in $T \to T \& F$), with both being left-associative.
Given the expression $2 \# 3 \& 5 \# 6 \& 4$, the $\&$ operations bind tighter: $(2 \# (3 \& 5)) \# (6 \& 4)$.

1. Evaluate $\&$ (addition): $3 \& 5 = 3 + 5 = 8$ and $6 \& 4 = 6 + 4 = 10$.
2. The expression becomes $2 \# 8 \# 10$.
3. Evaluate $\#$ (multiplication) left-associatively: $(2 \# 8) = 2 \times 8 = 16$, then $16 \# 10 = 16 \times 10 = 160$.

To compute the expression $E = E1 - E2$ on a single-register CPU where the first operand ($E1$) must reside in the register for the subtraction operation:

1. If $E2$ is evaluated first, its result is stored in memory $T$, and then $E1$ is evaluated, leaving its result in the register.
2. The final instruction is $SUB \ R, \ T$, which effectively performs $R - T = E1 - E2$.
3. If $E1$ is evaluated first, its result must be stored in memory, $E2$ must be evaluated and stored, and then $E1$ must be reloaded into the register to perform the subtraction.
4. Evaluating $E2$ first avoids redundant register-to-memory and memory-to-register moves, resulting in the shortest code.

To derive the code sequence for $X := Y + Z$, we use the provided Syntax Directed Definition:

1. The production $S \rightarrow \mathbf{id :=} E$ matches $X := Y + Z$, where $\mathbf{id} = X$ and $E = Y + Z$.
2. For $E \rightarrow E_1 + E_2$ (where $E_1 = Y$ and $E_2 = Z$), the semantic rules are:
   $t_1 = newtemp()$
   $gen(t_1 = E_1.place + E_2.place;) \implies gen(t_1 = Y + Z;)$
   $E.place = t_1$
3. Finally, the rule $S \rightarrow \mathbf{id :=} E$ generates the assignment $gen(\mathbf{id}.place = E.place;)$, which becomes $X = t_1;$.
4. Combining the generated code from steps 2 and 3 gives the sequence: $t_1 = Y + Z; X = t_1$.

The derivation of the translation scheme $S \rightarrow T R$, $R \rightarrow + T \{ \text{print('+');} \} R \mid \epsilon$, and $T \rightarrow \text{num} \{ \text{print(num.val);} \}$ for input '9 + 5 + 2' proceeds as follows:

1. Starting with $S \rightarrow T R$, the first $T$ processes '9', printing '9'. Current output: $9$.
2. The remaining string '+ 5 + 2' matches $R \rightarrow + T \{ \text{print('+');} \} R$.
3. The $T$ inside this $R$ processes '5', printing '5'. Then, the action executes, printing '+'. Current output: $95+$.
4. The remaining $R$ matches $+ T \{ \text{print('+');} \} R$ again, where $T$ processes '2', printing '2', followed by the action printing '+'. Current output: $95+2+$.
5. Finally, the last $R$ matches $\epsilon$, completing the parse with the final output $95+2+$.

To determine the predictive parse table entries, we first calculate the $FIRST$ and $FOLLOW$ sets for the non-terminals:

1. $FIRST(S') = \{e, \epsilon\}$ because $S' \rightarrow eS$ starts with $e$ and $S' \rightarrow \epsilon$ yields $\epsilon$.
2. $FOLLOW(S')$ contains \$$ (end of input) and e$because$S \rightarrow iEtSS'$puts$S'$\in a position followed by$FOLLOW(S)$, and \in$S' \rightarrow eS$,$S$is followed by$FOLLOW(S')$, while$S$is also followed by$S'$. Thus,$FOLLOW(S') = {e, $}$.
3. For $S' \rightarrow eS$, we add $S' \rightarrow eS$ to $M[S', e]$ since $e \in FIRST(eS)$.
4. For $S' \rightarrow \epsilon$, we add $S' \rightarrow \epsilon$ to $M[S', a]$ for all $a \in FOLLOW(S')$, which are $M[S', e]$ and M[S', \]$. Combining these,$M[S', e] = {S' \rightarrow eS, S' \rightarrow \epsilon}$and$M[S', $] = {S' \rightarrow \epsilon}$.

The SLR parser is constructed directly from the $LR(0)$ collection of items, meaning its number of states $n_1$ is equal to the number of $LR(0)$ states. The LALR parser is constructed by merging states in the $LR(1)$ collection that share the same $LR(0)$ core. Because the collection of these unique $LR(0)$ cores is identical to the set of $LR(0)$ states, the number of states in the LALR parser $n_2$ is equal to the number of $LR(0)$ states. Therefore, $n_1 = n_2$.

Statement A is false because, although an unambiguous grammar ensures a unique parse tree, the sequence of productions in a leftmost derivation differs from that of a rightmost derivation as they expand different non-terminals at each step. Statement B is true, as $LL(1)$ parsers perform top-down, predictive parsing. Statement C is true because the parser hierarchy is $SLR \subset LALR \subset LR(1)$, establishing $LALR$ as more powerful than $SLR$. Finally, statement D is true; $LR(k)$ grammars must be unambiguous to avoid conflicts during parsing, as an ambiguous grammar inherently allows multiple parse trees for the same input string.

In an expression grammar, precedence is determined by the hierarchy of non-terminals: operators located in productions of non-terminals "lower" in the derivation tree bind more tightly (have higher precedence). The grammar is defined as $E \to E * F \mid F + E \mid F$ and $F \to F - F \mid id$. Since $F$ is a constituent of $E$, the operator defined within $F$ (which is $-$) is nested deeper in the parse tree than the operators defined within $E$ (which are $*$ and $+$). Consequently, the operator $-$ must be evaluated before $*$ and $+$. This confirms that $-$ has higher precedence than $*$.

A top-down parser constructs a parse tree starting from the start symbol $S$ and proceeds toward the terminal input string. During this process, the parser consistently selects production rules to expand the leftmost non-terminal at each step as it scans the input from left to right. Since the derivation process targets the leftmost non-terminal in every sentential form until the complete string is generated, this sequence of rule applications corresponds exactly to a leftmost derivation. In contrast, bottom-up parsers reduce the string from leaves to the root, which effectively traces a rightmost derivation in reverse. Therefore, top-down parsing is synonymous with the leftmost derivation.

The parsing power hierarchy for deterministic context-free grammars follows the inclusion relationship: $LL(1) \subset SLR \subset LALR \subset \text{Canonical LR}$. Canonical LR (or $LR(1)$) is the most powerful because it maintains unique state information based on specific lookahead tokens for every item. In contrast, SLR relies on simple $LR(0)$ states with Follow sets, and LALR optimizes the table size by merging $LR(1)$ states, which inherently reduces the parser's distinguishing capability. Consequently, Canonical LR can parse the largest class of grammars among the options provided.