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
- GATE CS - 2025
- Adjoint and Inverse of a Matrix
Consider the following code:
int a; int arr[] = {30, 50, 10}; int *ptr = arr[10] + 1; a = *ptr; (*ptr)++; ptr = ptr + 1; printf("%d", a + arr[1] + *ptr);In the diagram, the lines QR and ST are parallel to each other. The shortest distance between these two lines is half the shortest distance between the point P and the line QR. What is the ratio of the area of the triangle PST to the area of the trapezium SQRT?
Note: The figure shown is representative
- GATE CS - 2025
- Geometry
Consider the following process information for Shortest Remaining Time First (SRTF) scheduling:
\[ \begin{array}{|c|c|c|} \hline \textbf{Process} & \textbf{Arrival Time (AT)} & \textbf{Burst Time (BT)} \\ \hline P1 & 0 & 10 \\ P2 & 1 & 13 \\ P3 & 2 & 6 \\ P4 & 8 & 9 \\ \hline \end{array} \]Find the turnaround time for each process.
- GATE CS - 2025
- Programming in C
- If IMAGE and FIELD are coded as FHBNJ and EMFJG respectively then, which one among the given options is the most appropriate code for BEACH?
- GATE CS - 2025
- GATE IN - 2025
- GATE MT - 2025
- GATE NM - 2025
- GATE TF - 2025
- Logical and Analytical Reasoning Skills