GateShala
Playground

Compiler Design GATE Practice Set

Mixed GATE-style questions on tokens, FIRST and FOLLOW, LL(1) and LR parsing, syntax-directed translation, intermediate code, runtime environments and optimization.

These questions mix every lesson of the Compiler Design track, in the three GATE formats. For parsing questions, write the FIRST and FOLLOW sets or the item sets out in full; for code questions, number the instructions first. Every numerical answer is recomputed by a program when the site is built.

Lexical and syntax analysis

GATE-styleNAT · numerical answer

[Tokens] How many tokens does the C statement for(i=0;i<n;i++) s+=a[i]; contain?

import re
scanner = re.compile(r"\+\+|\+=|[A-Za-z_]\w*|\d+|[-+*/=<>;,()\[\]]")
print(len(scanner.findall("for(i=0;i<n;i++) s+=a[i];")))
Show answer and explanationAnswer: 20

for ( i = 0 ; i < n ; i ++ ) s += a [ i ] ; gives 20 tokens; ++ and += are one token each.

GATE-styleMCQ · one correct answer

[FOLLOW] For S → A B c, A → a | ε, B → b | ε, what is FOLLOW(A)?

Show answer and explanationAnswer: B

In S → A B c, A is followed by FIRST(B c). B can derive ε, so this is {b} ∪ {c} = {b, c}. A never appears at the end of a right side, so $ is not included.

GATE-styleNAT · numerical answer

[LL(1)] How many non-empty entries does the LL(1) parsing table for S → A B c, A → a | ε, B → b | ε have?

Show answer and explanationAnswer: 8

S → ABc goes under FIRST(ABc) = {a, b, c}: 3 entries. A → a under a, A → ε under FOLLOW(A) = {b, c}: 3 entries. B → b under b, B → ε under FOLLOW(B) = {c}: 2 entries. Total 8, with no conflicts.

GATE-styleNAT · numerical answer

[LR(0)] How many states does the canonical collection of LR(0) items have for the augmented grammar S′ → S, S → (S) | x?

Show answer and explanationAnswer: 6

I0 (start), goto on S (accept), on ( (S → (·S) with closure), on x (S → x·); from the ( state, goto on S gives S → (S·) and then on ) gives S → (S)·. The ( state loops to itself on ( and reaches the x state on x. Six states.

GATE-styleMCQ · one correct answer

[Parsers] Which statement is true?

Show answer and explanationAnswer: B

LR(1) parsing is strictly more general than LL(1). LALR(1) merges LR(1) states, so it has at most as many, and LALR(1) is more powerful than SLR(1).

Translation and intermediate code

GATE-styleNAT · numerical answer

[SDT] Using E → E * T { E.val = E.val − T.val } | T, T → T + F { T.val = T.val × F.val } | F, F → num, what is the value of 8 * 3 + 2 * 1?

import re
def ev(s):
    toks, pos = re.findall(r"\d+|\S", s), [0]
    def F():
        pos[0] += 1
        return int(toks[pos[0] - 1])
    def T():
        v = F()
        while pos[0] < len(toks) and toks[pos[0]] == "+":
            pos[0] += 1
            v = v * F()
        return v
    def E():
        v = T()
        while pos[0] < len(toks) and toks[pos[0]] == "*":
            pos[0] += 1
            v = v - T()
        return v
    return E()
print(ev("8 * 3 + 2 * 1"))
Show answer and explanationAnswer: 1

+ sits lower in the grammar, so it binds tighter, and it means multiplication: 3 + 2 → 3 × 2 = 6. * means subtraction, left-associative: 8 − 6 − 1 = 1.

GATE-styleNAT · numerical answer

[DAG] How many nodes does the DAG of t1 = a + b; t2 = t1 * c; t3 = a + b; t4 = t3 * c; t5 = t2 - t4 have?

Show answer and explanationAnswer: 6

Leaves a, b, c; the node a + b (shared by t1 and t3); the node (a + b) × c (shared by t2 and t4); and the subtraction: 6 nodes. (Both operands of the subtraction are the same node, so t5 is always 0, which an optimizer can exploit.)

GATE-styleNAT · numerical answer

[SSA] The code p = q + r; q = p - s; p = q * p; s = p + q is converted to SSA form. How many distinct variables (inputs plus new versions) does it use?

Show answer and explanationAnswer: 7

The values used before being assigned are q, r and s (3 inputs). The four assignments create p1, q1, p2 and s1. Total 3 + 4 = 7.

Runtime and optimization

GATE-styleNAT · numerical answer

[Basic blocks] How many basic blocks does this code have? 1: i = 0; 2: if i >= n goto 7; 3: t = a[i]; 4: s = s + t; 5: i = i + 1; 6: goto 2; 7: print s; 8: if s > 0 goto 1; 9: return

Show answer and explanationAnswer: 5

Leaders: 1 (first, and target of 8), 2 (target of 6), 3 (after the jump in 2), 7 (target of 2, and after the goto in 6) and 9 (after the jump in 8). Blocks: {1}, {2}, {3–6}, {7, 8}, {9}.

GATE-styleMCQ · one correct answer

[Scoping] int x = 5; void p() { x = x + 1; } void q() { int x = 10; p(); print(x); } main() { q(); print(x); } What does it print under static scoping?

g = {"x": 5}
out = []
def p():
    g["x"] = g["x"] + 1          # static scoping: p's x is the global x
def q():
    x = 10
    p()
    out.append(x)
q()
out.append(g["x"])
print(" ".join(map(str, out)))
Show answer and explanationAnswer: B

Under static scoping, p always updates the global x (5 → 6), so q's local x stays 10: the output is 10 then 6. Under dynamic scoping, p would update q's local x instead, printing 11 then 5.

GATE-styleMSQ · one or more correct answers

[Data flow] Which analyses are forward analyses? (Select all that apply.)

Show answer and explanationAnswer: A, B, D

Reaching definitions, available expressions and constant propagation follow values from where they are created to where they are used. Liveness looks ahead to future uses, so it flows backward.