How are FIRST and FOLLOW sets used in GATE Compiler Design?

FIRST sets contain the terminals that can begin strings derived from a non-terminal. FOLLOW sets contain terminals that can appear after a non-terminal in a sentential form. GATE tests their computation for constructing LL(1) and SLR parsing tables, and resolving shift-reduce conflicts.

What is the difference between SLR, LALR, and Canonical LR parsers in GATE?

SLR uses FOLLOW sets to decide reductions and is the weakest. LALR merges states with the same core items from Canonical LR and uses lookahead sets — it handles more grammars than SLR with the same number of states. Canonical LR is the most powerful but has the most states. GATE tests conflict resolution and grammar classification across these three.

How is bottom-up parsing tested in GATE CS Compiler Design?

GATE tests shift-reduce parsing, the number of reductions for a given string and grammar, handle identification, and LR item set construction (closure and GOTO operations). Questions ask for the number of items in a specific state or reductions taken while parsing a string.

What kind of derivation does LR parsing use in GATE questions?

LR parsers use rightmost derivation in reverse. While the parser reads input left to right, it constructs a rightmost derivation from the bottom up. This is a frequently tested concept in GATE, distinguishing LR (bottom-up) from LL (top-down, leftmost derivation).

CS/IT Gate Subject

Aptitude and Reasoning
Engineering Mathematics
C Programming
Data Structure
Design Algorithm Analysis
Operating System
Computer Network
Digital Logic Design
Compiler Design
Database Management System
Theory of Computation

Compiler Design GATE previous year questions with answer

Ques 14 Gate 2019

Consider the augmented grammar given below:

S′ → S
S → ⏐id
L → L, S⏐S
Let I₀= CLOSURE ({[S′ → S]}).

The number of items in the set GOTO (I₀, <) is __________.

(5) is the correct answer.

Ques 15 Gate 2017 Set-2

Which of the following statements about the parser is/are correct?

I. Canonical LR is more powerful than SLR.
II. SLR is more powerful than LALR.
III. SLR is more powerful than canonical LR.

I only

II only

III only

II and III only

(Parsing) is the correct answer.

Ques 16 Gate 2017 Set-2

Match the following according to input(from the left column) to the compiler phase(in the right column) that process it:

(P)Syntax Tree	(i)Code generator
(Q)Character Stream	(ii)Syntax analyser
(R)Intermediate representation	(iii)Semantic analyser
(S)Token stream	(iv)Lexical analyser

P -> (ii), Q -> (iii), R -> (iv), S -> (i)

P -> (ii), Q -> (i), R -> (iii), S -> (iv)

P -> (iii), Q -> (iv), R -> (i), S -> (ii)

P -> (i), Q -> (iv), R -> (ii), S -> (iii)

(Compiler Design) is the correct answer.

Ques 17 Gate 2016 Set-2

Match the following

(P) Lexical analysis	(i)Leftmost derivation
(Q) Top down parsing	(ii) Type checking
(R) Semantic analysis	(iii) Regular expressions
(S) Runtime environments	(iv) Activation records

P ↔ i, Q ↔ ii, R ↔ iv, S ↔ iii

P ↔ iii, Q ↔ i, R ↔ ii, S ↔ iv

P ↔ ii, Q ↔ iii, R ↔ i, S ↔ iv

P ↔ iv, Q ↔ i, R ↔ ii, S ↔ iii

(Phase of Compiler) is the correct answer.

Ques 18 Gate 2016 Set-1

Consider the following code segment.

x = u - t;
y = x * v;
x = y + w;
y = t - z;
y = x * y;

The minimum number of total variables required to convert the above code segment to static single assignment form is ____

(a) is the correct answer.

Ques 19 Gate 2016 Set-1

Consider the following Syntax Directed Translation Scheme (SDTS), with non-terminals {S, A} and terminals {a, b}.

S −→ aA { print 1 }
S −→ a { print 2 }
A −→ Sb { print 3 }

Using the above SDTS, the output printed by a bottom-up parser, for the input aab is:

1 3 2

2 2 3

2 3 1

Syntax Error

(SDT) is the correct answer.

Ques 20 Gate 2015 Set-3

Consider the following grammar G.

S → F ⎪ H
F → p ⎪ c
H → d ⎪ c

Where S, F and H are non-terminal symbols, p, d and c are terminal symbols. Which of the following statement(s) is/are correct?

S1: LL(1) can parse all strings that are generated using grammar G.
S2: LR(1) can parse all strings that are generated using grammar G.

Only S1

Only S2

Both S1 and S2

Neither S1 and S2

(Parser) is the correct answer.

Ques 21 Gate 2015 Set-3

Among simple LR (SLR), canonical LR, and look-ahead LR (LALR), which of the following pairs identify the method that is very easy to implement and the method that is the most powerful, in that order?

SLR, LALR

Canonical LR, LALR

SLR, canonical LR

LALR, canonical LR

(Parser) is the correct answer.

Ques 22 Gate 2015 Set-2

In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is True?

In both AST and CFG, let node N₂ be the successor of node N₁. In the input program, the code corresponding to N₂ is present after the code corresponding to N₁.

For any input program, neither AST nor CFG will contain a cycle.

The maximum number of successors of a node in an AST and a CFG depends on the input program.

Each node in AST and CFG corresponds to at most one statement in the input program.

(CFG) is the correct answer.

Ques 23 GATE 2015 SET-2

Match the following:

P-2, Q-3, R-1, S-4

P-2, Q-1, R-4, S-3

P-2, Q-4, R-1, S-3

P-2, Q-3, R-4, S-1

(a) is the correct answer.

Total Unique Visitors

Loading......

CS/IT Gate Subject

Compiler Design GATE previous year questions with answer

Question Options

Sign in to ExamPrev