List of top Computer Science and IT Engineering Questions on Compiler Design asked in GATE CS

Consider the canonical 𝐿𝑅(0) parsing of the grammar below using terminals
{π‘Ž, 𝑏, 𝑐} and non-terminals {𝐴, 𝐡, 𝐢, 𝑆} with 𝑆 as the start symbol.
𝑆→𝐴𝐢𝐡
π΄β†’π‘Žπ΄ | πœ–
𝐢→𝑐𝐢 | πœ–
𝐡→𝑏𝐡 | 𝑏
Which one of the following options gives the number of shift-reduce conflicts that
will occur in the 𝐿𝑅(0) ACTION table?

A lexical analyzer uses the following token definitions
ο‚· π‘™π‘’π‘‘π‘‘π‘’π‘Ÿβ†’[π΄βˆ’π‘π‘Žβˆ’π‘§]
ο‚· 𝑑𝑖𝑔𝑖𝑑→[0 βˆ’9]
ο‚· π‘–π‘‘β†’π‘™π‘’π‘‘π‘‘π‘’π‘Ÿ (π‘™π‘’π‘‘π‘‘π‘’π‘Ÿ | 𝑑𝑖𝑔𝑖𝑑)*
ο‚· π‘›π‘’π‘šπ‘π‘’π‘Ÿβ†’π‘‘π‘–π‘”π‘–π‘‘+
ο‚· 𝑀𝑠→(π‘π‘™π‘Žπ‘›π‘˜ | π‘‘π‘Žπ‘ | 𝑛𝑒𝑀𝑙𝑖𝑛𝑒)+
For the string given below,
π‘₯1 23π‘šπ‘š 78 𝑦 7𝑧 𝑧𝑧5 14𝐴 8𝐻 π΄π‘Žπ‘Œπ‘π·
the number of tokens (excluding 𝑀𝑠) that will be produced by the lexical analyzer
is __________. (answer in integer)

Consider the following two syntax-directed definitions SDD1 and SDD2 for type
declarations.
𝐷 is the start symbol, and 𝑖𝑛𝑑, π‘“π‘™π‘œπ‘Žπ‘‘ and 𝑖𝑑 are the three terminals. The non-terminal
𝑉1 is the same as 𝑉 and the non-terminal 𝐷1 is the same as 𝐷. Here, the subscript is
used to differentiate the grammar symbols on the two sides of a production. The
function 𝑝𝑒𝑑 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?
SDD1
Grammar
(G1)
Semantic Rules
𝐷 →𝑇 𝑉
𝐷. 𝑑𝑦𝑝𝑒 = 𝑇. 𝑑𝑦𝑝𝑒
𝑉. 𝑑𝑦𝑝𝑒 = 𝑇. 𝑑𝑦𝑝𝑒
𝑇 β†’ 𝑖𝑛𝑑
𝑇. 𝑑𝑦𝑝𝑒 = 𝑖𝑛𝑑
𝑇 β†’ π‘“π‘™π‘œπ‘Žπ‘‘
𝑇. 𝑑𝑦𝑝𝑒 = π‘“π‘™π‘œπ‘Žπ‘‘
𝑉→𝑉1 𝑖𝑑
𝑉1. 𝑑𝑦𝑝𝑒= 𝑉. 𝑑𝑦𝑝𝑒
𝑝𝑒𝑑(𝑖𝑑. π‘’π‘›π‘‘π‘Ÿπ‘¦, 𝑉. 𝑑𝑦𝑝𝑒)
𝑉 β†’ 𝑖𝑑
𝑝𝑒𝑑(𝑖𝑑. π‘’π‘›π‘‘π‘Ÿπ‘¦, 𝑉. 𝑑𝑦𝑝𝑒)
SDD2
Grammar
(G2)
Semantic Rules
𝐷→𝐷1 𝑖𝑑
𝐷. 𝑑𝑦𝑝𝑒= 𝐷1. 𝑑𝑦𝑝𝑒
𝑝𝑒𝑑(𝑖𝑑. π‘’π‘›π‘‘π‘Ÿπ‘¦, 𝐷1. 𝑑𝑦𝑝𝑒)
𝐷 β†’ 𝑇 𝑖𝑑
𝐷. 𝑑𝑦𝑝𝑒 = 𝑇. 𝑑𝑦𝑝𝑒
𝑝𝑒𝑑(𝑖𝑑. π‘’π‘›π‘‘π‘Ÿπ‘¦, 𝑇. 𝑑𝑦𝑝𝑒)
𝑇 →𝑖𝑛𝑑
𝑇. 𝑑𝑦𝑝𝑒 = 𝑖𝑛𝑑
𝑇 β†’ π‘“π‘™π‘œπ‘Žπ‘‘
𝑇. 𝑑𝑦𝑝𝑒 = π‘“π‘™π‘œπ‘Žπ‘‘

Consider the control flow graph shown in the figure.
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.

Which of the following statements is/are true?

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 following definition of a lexical token id for an identifier in a programming language, using extended regular expressions: \[ \text{letter} \;\;\rightarrow\;\; [A\!-\!Za\!-\!z] \] \[ \text{digit} \;\;\rightarrow\;\; [0\!-\!9] \] \[ \text{id} \;\;\rightarrow\;\; \text{letter (letter | digit)}^* \] Which one of the following Non-deterministic Finite-state Automata with $\epsilon$-transitions accepts the set of valid identifiers? (A double-circle denotes a final state). 

Consider the control flow graph shown. Which one of the following choices correctly lists the set of live variables at the exit point of each basic block?