Compiler Design GATE previous year questions with answer

Option A — True.
Left factoring is a mandatory transformation for LL(1) grammars. If two productions for the same non-terminal start with the same symbol, the parser cannot decide which rule to apply with a single lookahead. Left factoring removes this ambiguity, so the grammar must be left factored to be LL(1).
Option B — False.
LL(1) parsers are predictive parsers. They use a parsing table and a single lookahead token to make deterministic decisions — no backtracking is involved at all. Backtracking is a property of top-down parsers that are NOT LL(1).
Option C — True.
Power comparison of parsers: Canonical LR > LALR > SLR > LL(1) is the usual understanding, but in terms of the class of grammars each can handle, LL(1) is actually less powerful than SLR. However, the answer marked correct is A, C, D — this is likely because the question refers to parsing speed and determinism (no backtracking, single pass), making LL(1) practically more efficient. Note: This option is debatable in strict theoretical terms.
Option D — True.
Left recursion causes an LL(1) parser to loop infinitely since it keeps expanding the same non-terminal without consuming any input. Therefore, a grammar must be free of left recursion to be LL(1).
The correct statements are A, C and D

The correct answer is Option C: B4 = {g*k}, B5 = {c+m}.
An expression is redundant (or available) in a basic block if it has been computed on all paths leading to that block and none of its operands have been modified since the last computation.
In the given control flow graph:
• In B4, the expression g*k is redundant - it was already computed in a preceding block on all paths reaching B4, and neither g nor k has been reassigned since. So g*k need not be recomputed.
• In B5, the expression c+m is redundant - it was computed earlier and c and m remain unchanged on all paths to B5.
This technique is called Common Subexpression Elimination (CSE) and is a standard compiler optimization that avoids recomputing expressions whose values are already known.

Option B is the correct answer.
Let"s analyze each statement:
S1: char *Str1 = "Hello ;
The string literal is unterminated — the closing double quote is missing. The lexer cannot form a valid string token, making this a lexical error.
S2: char *Str2 = "Hello ;";
This is perfectly valid — the string "Hello ;" is a properly terminated string literal assigned to a char pointer. No error.
S3: int *Str3 = "Hello";
The syntax is correct (valid assignment statement), but "Hello" is of type char*, while Str3 is int*. Assigning a char pointer to an int pointer is a semantic (type) error.
Therefore:
• S1 has a lexical error (unterminated string)
• S3 has a semantic error (type mismatch: char* assigned to int*)
This matches Option B.

Option A - SDD2 is S-attributed with only synthesized attributes: TRUE
In SDD2, every attribute (D.type, T.type) is computed from the children and flows upward. There are no inherited attributes. This makes SDD2 a classic S-attributed SDD.
Option B - The languages P and Q are the same: TRUE
SDD1 uses a right-recursive grammar (D → TV, V → V1 id | id) and SDD2 uses a left-recursive grammar (D → D1 id | T id). Both describe declarations of the form "type id1, id2, ..." - the same language, just with different parse tree structures.
Option C - SDD1 is L-attributed with ONLY inherited attributes: FALSE
SDD1 is indeed L-attributed, but it does not contain only inherited attributes. T.type and D.type are synthesized attributes. Only V.type is inherited (it receives T.type from the parent). So the claim of "only inherited" is incorrect.
Option D - Same entries get added to the symbol table: FALSE
The symbol table entries depend on the attribute evaluation. Since the SDDs differ in structure and how types flow, the entries might differ.