List of top Compiler Design Questions asked in GATE CS

A lexical analyzer uses the following token definitions:

$letter \rightarrow [A-Za-z]$
$digit \rightarrow [0-9]$
$id \rightarrow letter\,(letter\,|\,digit)^{*}$
$number \rightarrow digit^{+}$
$ws \rightarrow (blank\,|\,tab\,|\,newline)^{+}$

For the string given below,
\[ x1\ \ 23mm\ \ 78\ \ y\ \ 7z\ \ zz5\ \ 14A\ \ 8H\ \ AaYcD \]
the number of tokens (excluding $ws$) that will be produced by the lexical analyzer is ______.

Consider the control flow graph given below.

Which one of the following options is the set of live variables at the exit point of each basic block?

Consider the canonical $LR(0)$ parsing of the grammar below using terminals $\{a,b,c\}$ and non-terminals $\{A,B,C,S\}$ with $S$ as the start symbol.
\[ S \to ACB \]
\[ A \to aA \mid \epsilon \]
\[ C \to cC \mid \epsilon \]
\[ B \to bB \mid b \]
Which one of the following options gives the number of shift-reduce conflicts that will occur in the $LR(0)$ ACTION table?

Consider the following two syntax-directed definitions SDD1 and SDD2 for type declarations.

SDD1
Grammar (G1): $D \rightarrow T\,V$; Semantic Rules: $D.type = T.type;\ V.type = T.type$
Grammar (G1): $T \rightarrow int$; Semantic Rules: $T.type = int$
Grammar (G1): $T \rightarrow float$; Semantic Rules: $T.type = float$
Grammar (G1): $V \rightarrow V_1\,id$; Semantic Rules: $V_1.type = V.type;\ put(id.entry, V.type)$
Grammar (G1): $V \rightarrow id$; Semantic Rules: $put(id.entry, V.type)$

SDD2
Grammar (G2): $D \rightarrow D_1\,id$; Semantic Rules: $D.type = D_1.type;\ put(id.entry, D_1.type)$
Grammar (G2): $D \rightarrow T\,id$; Semantic Rules: $D.type = T.type;\ put(id.entry, T.type)$
Grammar (G2): $T \rightarrow int$; Semantic Rules: $T.type = int$
Grammar (G2): $T \rightarrow float$; Semantic Rules: $T.type = float$

$D$ is the start symbol, and $int$, $float$ and $id$ are the three terminals. The non-terminal $V_1$ is the same as $V$ and the non-terminal $D_1$ is the same as $D$. Here, the subscript is used to differentiate the grammar symbols on the two sides of a production. The function $put$ updates the symbol table with the type information for an identifier.
Let P and Q be the languages specified by grammars G1 and G2, respectively.
Which of the following statements is/are true?

Which of the following statements is/are true?

Consider the following C statements:

char *str1 = "Hello;      /* Statement S1 */
char *str2 = "Hello;";    /* Statement S2 */
int  *str3 = "Hello";     /* Statement S3 */

Which of the following options is/are correct?

Consider the control flow graph shown in the figure.

The basic blocks are:
B1: $a = b + i$
B2: $a = g*k$; $f = d-f$; $a = c*4$
B3: $t = g*k$; $b = c+m$
B4: $x = g*k$; $y = b+i$
B5: $z = c+m$

B1 has two successors, B2 and B3, both B2 and B3 flow into B4, and B4 flows into B5.

Which one of the following options correctly lists the set of redundant expressions (common subexpressions) in the basic blocks B4 and B5?

Note: All the variables are integers.

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?

Consider the following statements about the use of backpatching in a compiler for intermediate code generation:
1. Backpatching can be used to generate code for Boolean expressions in one pass.
2. Backpatching can be used to generate code for flow-of-control statements in one pass.
Which ONE of the following options is CORRECT?

Which of the following statement(s) is/are TRUE while computing First and Follow during top-down parsing by a compiler?

The number of distinct minimum-weight spanning trees of the following graph is ............ \begin{center} \includegraphics[width=0.5\textwidth]{59.png} \end{center}

Consider a 32-bit system with a 4 KB page size and page table entries of size 4 bytes each. Assume $1 \, \text{KB} = 2^{10} \, \text{bytes}$. The OS uses a 2-level page table for memory management, with the page table containing an outer page directory and an inner page table. The OS allocates a page for the outer page directory upon process creation. The OS uses demand paging when allocating memory for the inner page table, i.e., a page of the inner page table is allocated only if it contains at least one valid page table entry.
An active process in this system accesses $2000$ unique pages during its execution, and none of the pages are swapped out to disk. After it completes the page accesses, let $X$ denote the minimum and $Y$ denote the maximum number of pages across the two levels of the page table of the process. The value of $X + Y$ is ............

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 ............

Consider a disk with the following specifications: rotation speed of 6000 RPM, average seek time of 5 milliseconds, 500 sectors/track, 512-byte sectors. A file has content stored in 3000 sectors located randomly on the disk. Assuming average rotational latency, the total time (in seconds, rounded off to 2 decimal places) to read the entire file from the disk is ............

Consider a multi-threaded program with two threads $T1$ and $T2$. The threads share two semaphores: $s1$ (initialized to 1) and $s2$ (initialized to 0). The threads also share a global variable $x$ (initialized to 0). The threads execute the code shown below. \begin{verbatim} // code of T1 // code of T2 wait(s1); wait(s1); x = x+1; x = x+1; print(x); print(x); wait(s2); signal(s2); signal(s1); signal(s1); \end{verbatim} Which of the following outcomes is/are possible when threads $T1$ and $T2$ execute concurrently?

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?

Consider an array $X$ that contains $n$ positive integers. A subarray of $X$ is defined to be a sequence of array locations with consecutive indices. The C code snippet given below has been written to compute the length of the longest subarray of $X$ that contains at most two distinct integers. The code has two missing expressions labelled $(P)$ and $(Q)$. \begin{verbatim} int first=0, second=0, len1=0, len2=0, maxlen=0; for (int i=0; i<n; i++) { if (X[i] == first) { len2++; len1++; } else if (X[i] == second) { len2++; len1 = (P); second = first; } else { len2 = (Q); len1 = 1; second = first; } if (len2>maxlen) { maxlen = len2; } first = X[i]; } \end{verbatim} Which one of the following options gives the CORRECT missing expressions?

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.}

Consider a single processor system with four processes A, B, C, and D, represented as given below, where for each process the first value is its arrival time, and the second value is its CPU burst time. \[ A (0, 10), \, B (2, 6), \, C (4, 3), \, D (6, 7). \] Which one of the following options gives the average waiting times when preemptive Shortest Remaining Time First (SRTF) and Non-Preemptive Shortest Job First (NP-SJF) CPU scheduling algorithms are applied to the processes?

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 ...........\_\_\_.

Consider a process $P$ running on a CPU. Which one or more of the following events will always trigger a context switch by the OS that results in process $P$ moving to a non-running state (e.g., ready, blocked)?}

Which of the following tasks is/are the responsibility/responsibilities of the memory management unit (MMU) in a system with paging-based memory management?

Consider the following two sets: \begin{center} \begin{tabular}{|c|l|c|l|} \hline Set X & & Set Y &
\hline P. & Lexical Analyzer & 1. & Abstract Syntax Tree
Q. & Syntax Analyzer & 2. & Token
R. & Intermediate Code Generator & 3. & Parse Tree
S. & Code Optimizer & 4. & Constant Folding
\hline \end{tabular} \end{center} Which one of the following options is the CORRECT match from Set X to Set Y?

Which one of the following statements is TRUE?

Consider the augmented grammar with $\{+,* , (, ), id\}$ as the set of terminals. \[ S' \rightarrow S \] \[ S \rightarrow S + R \mid R \] \[ R \rightarrow R^{\,*} P \mid P \] \[ P \rightarrow (S) \mid id \] If $I_0$ is the set of two LR(0) items $\{[S' \rightarrow S.], [S \rightarrow S. + R]\}$, then $goto(\text{closure}(I_0), +)$ contains exactly $\underline{\hspace{1cm}}$ items.