Consider the following augmented grammar, which is to be parsed with an SLR parser. The set of terminals is \(\{a, b, c, d, \#, @\}\).
\[
S' \rightarrow S \quad S \rightarrow SS \, | \, Aa \, | \, bAc \, | \, BC \, | \, bBa \quad A \rightarrow d\# \quad B \rightarrow @
\]
Let \(I_0 = \text{CLOSURE}(\{S' \rightarrow \cdot S\}\). The number of items in the set \(GOTO(I_0, S)\) is ............
Show Hint
Solution and Explanation
Step 1: Analyze the given DFA diagram.
The given DFA represents the items in the closure of \(I_0\) and the GOTO function for the symbol \(S\).
Step 2: Identify the items in the closure of \(I_0\).
The closure of \(I_0\) contains the following items: \(S \to \cdot S\) \(S \to \cdot SS\) \(S \to \cdot Aa\) \(S \to \cdot bAc\) \(S \to \cdot Bc\) \(S \to \cdot bAb\) \(A \to \cdot d\#\) \(B \to \cdot @\)
Step 3: Apply the GOTO function on the symbol \(S\).
When the GOTO function is applied to \(S\), the following transitions occur: \(S \to S\cdot\) \(S \to S\cdot S\) \(S \to SS\cdot\) \(S \to Aa\cdot\) \(S \to bAc\cdot\) \(S \to Bc\cdot\) \(S \to bAb\cdot\) \(A \to d\#\cdot\) \(B \to @\cdot\)
Step 4: Count the total number of items.
From the diagram, the GOTO function \(GOTO(\text{closure}(I_0), S)\) results in 9 items: \[ S \to S\cdot, \, S \to S\cdot S, \, S \to SS\cdot, \, S \to Aa\cdot, \, S \to bAc\cdot, \, S \to Bc\cdot, \, S \to bAb\cdot, \, A \to d\#\cdot, \, B \to @\cdot. \]
Final Answer: From the above DFA, we can conclude that: \[ \boxed{\text{GOTO}(\text{closure}(I_0), S) \text{ contains 9 items.}} \]
Top Questions on Syntax Directed Translation
Given the following syntax directed translation rules:
Rule 1: \( R \to AB \) { \( B.i = R.i - 1 \); \( A.i = B.i \); \( R.i = A.i + 1 \); }
Rule 2: \( P \to CD \) { \( P.i = C.i + D.i \); \( D.i = C.i + 2 \); }
Rule 3: \( Q \to EF \) { \( Q.i = E.i + F.i \); }
Which ONE is the CORRECT option among the following?- GATE CS - 2025
- Compiler Design
- Syntax Directed Translation
- The number of distinct minimum-weight spanning trees of the following graph is ............ \begin{center} \includegraphics[width=0.5\textwidth]{59.png} \end{center}
- GATE CS - 2024
- Compiler Design
- Syntax Directed Translation
- Consider the following expression: \(x[i] = (p + r) * -s[i] + u / w\). The following sequence shows the list of triples representing the given expression, with entries missing for triples (1), (3), and (6). \begin{center} \begin{tabular}{|c|c|c|c|} \hline (0) & \(+\) & \(p\) & \(r\)
\hline (1) & & &
\hline (2) & \texttt{uminus} & \((1)\) &
\hline (3) & & &
\hline (4) & \(/\) & \(u\) & \(w\)
\hline (5) & \(+\) & \((3)\) & \((4)\)
\hline (6) & & &
\hline (7) & \(=\) & \((6)\) & \(x[i]\)
\hline \end{tabular} \end{center} Which one of the following options fills in the missing entries CORRECTLY?- GATE CS - 2024
- Compiler Design
- Syntax Directed Translation
- Consider the following context-free grammar where the start symbol is \(S\) and the set of terminals is \(\{a, b, c, d\}\): \[ S \to AaAb \, | \, BbBa \quad \quad A \to cS \, | \, \epsilon \quad \quad B \to dS \, | \, \epsilon \] The following is a partially-filled LL(1) parsing table. \begin{center} \begin{tabular}{|c|c|c|c|c|c|} \hline & \(a\) & \(b\) & \(c\) & \(d\) & \(\$\)
\hline \(S\) & \(S \to AaAb\) & \(S \to BbBa\) & (1) & (2) &
\hline \(A\) & \(A \to \epsilon\) & (3) & \(A \to cS\) & &
\hline \(B\) & (4) & \(B \to \epsilon\) & & \(B \to dS\) &
\hline \end{tabular} \end{center} Which one of the following options represents the CORRECT combination for the numbered cells in the parsing table? Note: In the options, "blank" denotes that the corresponding cell is empty.}- GATE CS - 2024
- Compiler Design
- Syntax Directed Translation
- Let \(A\) be an array containing integer values. The distance of \(A\) is defined as the minimum number of elements in \(A\) that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. The distance of the array \([2, 5, 3, 1, 4, 2, 6]\) is ...........\_\_\_.
- GATE CS - 2024
- Compiler Design
- Syntax Directed Translation
Questions Asked in GATE CS exam
In a 4-bit ripple counter, if the period of the waveform at the last flip-flop is 64 microseconds, then the frequency of the ripple counter in kHz is ______________. {(Answer in integer)}
- GATE CS - 2025
- Flip-Flop
Consider the following C code segment:
int x = 126, y = 105; do { if (x > y) x = x - y; else y = y - x; } while (x != y); printf("%d", x);The output of the given C code segment is ____________. (Answer in integer)
- GATE CS - 2025
- Programming in C
The following two signed 2’s complement numbers (multiplicand \( M \) and multiplier \( Q \)) are being multiplied using Booth’s algorithm:
Multiplicand (\( M \)) Multiplier (\( Q \)) 1100 1101 1110 1101 1010 0100 1010 1010 The total number of addition and subtraction operations to be performed is __________. (Answer in integer)
- GATE CS - 2025
- Complementation
The maximum value of \(x\) such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is __________ (answer in integer).
- GATE CS - 2025
- Programming and Data Structures
Consider the following C program
The value printed by the given C program is __________ (Answer in integer).- GATE CS - 2025
- Programming in C