# Compiler Design

 Question 1
Consider the following grammar along with translation rules.
\begin{aligned} &S \rightarrow S_1 \# T & & \{S._{val}=S_{1.val}*T._{val} \} \\ &S \rightarrow T & & \{S._{val}=T._{val} \} \\ &T \rightarrow T_1 \% R & & \{T._{val}=T_{1.val} \div R._{val} \} \\ &T \rightarrow R & & \{T._{val}=R._{val} \} \\ &R \rightarrow id & & \{R._{val}=id._{val} \} \\ \end{aligned}
Here $\#$ and $\%$ are operators and $id$ is a token that represents an integer and $id_{.val}$ represents the corresponding integer value. The set of non-terminals is $\{S,T,R,P \}$ and a subscripted non-terminal indicates an instance of the non-terminal.
Using this translation scheme, the computed value of $S_{.val}$ for root of the parse tree for the expression $20 \# 10 \% 5 \# 8 \% 2 \% 2$ is
 A 20 B 65 C 160 D 80
GATE CSE 2022      Parsing
Question 1 Explanation:
 Question 2
Consider the augmented grammar with $\{+, *, (, ), id \}$ as the set of terminals.
\begin{aligned}&S' \rightarrow S \\ &S \rightarrow S+R|R \\ &R \rightarrow R*P|P \\ &P \rightarrow (S)|id \end{aligned}
If $I_0$ is the set of two $LR(0)$ items $\{ [S' \rightarrow S.], [S \rightarrow S.+R] \}$, then $goto(closure(I_0 ),+)$ contains exactly ______ items.
 A 2 B 3 C 4 D 5
GATE CSE 2022      Parsing
Question 2 Explanation:
 Question 3
Which one of the following statements is TRUE?
 A The LALR(1) parser for a grammar G cannot have reduce-reduce conflict if the LR(1) parser for G does not have reduce-reduce conflict. B Symbol table is accessed only during the lexical analysis phase. C Data flow analysis is necessary for run-time memory management. D LR(1) parsing is sufficient for deterministic context-free languages.
GATE CSE 2022      Parsing
Question 3 Explanation:
 Question 4
Consider the following augmented grammar with $\{ \#, @, <, >, a, b, c \}$ as the set of terminals.

$\begin{array}{l} S' \rightarrow S \\ S \rightarrow S \# cS \\ S \rightarrow SS \\ S \rightarrow S @ \\ S \rightarrow < S > \\ S \rightarrow a \\ S \rightarrow b \\ S \rightarrow c \end{array}$

Let $I_0 = \text{CLOSURE}(\{S' \rightarrow \bullet S\})$. The number of items in the set $\text{GOTO(GOTO}(I_0 \lt ), \lt )$ is ___________
 A 6 B 7 C 8 D 9
GATE CSE 2021 SET-2      Parsing
Question 4 Explanation:
 Question 5
For a statement S in a program, in the context of liveness analysis, the following sets are defined:

USE(S) : the set of variables used in S
IN(S) : the set of variables that are live at the entry of S
OUT(S) : the set of variables that are live at the exit of S

Consider a basic block that consists of two statements, S1 followed by S2. Which one of the following statements is correct?
 A OUT(S1) = IN (S2) B OUT (S1) = IN (S1) $\cup$ USE (S1) C OUT (S1) =IN (S2) $\cup$ OUT (S2) D OUT (S1) = USE (S1)$\cup$ IN (S2)
GATE CSE 2021 SET-2      Runtime Environment
Question 5 Explanation:
 Question 6
In the context of compilers, which of the following is/are NOT an intermediate representation of the source program?
 A Three address code B Abstract Syntax Tree (AST) C Control Flow Graph (CFG) D Symbol table
GATE CSE 2021 SET-2      Intermediate Code Generation
Question 6 Explanation:
 Question 7
Consider the following ANSI C program:
int main () {
Integer x;
return 0;
} 
Which one of the following phases in a seven-phase C compiler will throw an error?
 A Lexical analyzer B Syntax analyzer C Semantic analyzer D Machine dependent optimizer
GATE CSE 2021 SET-2      Syntax-directed Translation
Question 7 Explanation:
 Question 8
Consider the following C code segment:

a = b + c;
e = a + 1;
d = b + c;
f = d + 1;
g = e + f;

In a compiler, this code segment is represented internally as a directed acyclic graph (DAG). The number of nodes in the DAG is _____________
 A 11 B 6 C 5 D 10
GATE CSE 2021 SET-1      Parsing
Question 8 Explanation:
 Question 9
Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation (SDT) actions, given as pseudo-code

$\begin{array}{lll} P & \rightarrow & D^* E^* \\ D & \rightarrow & \textsf{int ID} \{ \text{record that } \textsf{ID.} \text{lexeme is of type} \textsf{ int\}} \\ D & \rightarrow & \textsf{bool ID} \{ \text{record that } \textsf{ID.} \text{lexeme is of type} \textsf{ bool\}} \\ E& \rightarrow & E_1 +E_2 \{ \text{check that } E_1. \text{type}=E_2. \text{type} = \textsf{int}; \text{set } E.\text{type }:= \textsf{int} \} \\ E & \rightarrow & !E_1 \{ \text{check that } E_1. \text{type} = \textsf{bool}; \text{ set } E.\text{type} := \textsf{bool} \} \\ E & \rightarrow & \textsf{ID} \{ \text{set } E. \text{type } := \textsf{int} \} \end{array}$

With respect to the above grammar, which one of the following choices is correct?
 A The actions can be used to correctly type-check any syntactically correct program B The actions can be used to type-check syntactically correct integer variable declarations and integer expressions C The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions. D The actions will lead to an infinite loop
GATE CSE 2021 SET-1      Syntax-directed Translation
Question 9 Explanation:
 Question 10
Consider the following statements.

S1: Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).
S2: For any context-free grammar, there is a parser that takes at most $O(n^3)$ time to parse a string of length n.

Which one of the following options is correct?
 A S1 is true and S2 is false B S1 is false and S2 is true C S1 is true and S2 is true D S1 is false and S2 is false
GATE CSE 2021 SET-1      Parsing
Question 10 Explanation:

There are 10 questions to complete.