Semantic analysis catches what a grammar cannot: a variable used before it is declared, an int added to a bool, a call made with the wrong number of arguments. Syntax-directed translation is how that work is organised, with every production carrying semantic rules that compute attributes on the parse tree. A synthesized attribute is computed from a node's children, so it flows upward and can be evaluated during a bottom-up parse. An inherited attribute comes from a parent or a left sibling, which is how a declared type reaches an identifier buried inside an expression.
Exam questions rarely ask for those definitions. They hand you a translation scheme and an input string, then ask what gets printed, in what order, or what value the root attribute holds. Each of the twelve below is a previous-year problem of that shape, marked with its exam and year, so trace it on paper before reading the working. For where this sits in the wider paper, see GATE CS Exam Preparation.
Semantic analysis and SDT MCQs 1-3
The first three fix the vocabulary: which phase owns type checking, what a semantic action may do, and which way each kind of attribute travels. For a broader mixed set, work through the Compiler Design MCQs collection.
Question 1: which phase does type checking
Type checking is normally done during which phase? (GATE CS 1998, step-by-step solution)
A. Lexical analysis
B. Syntax analysis
C. Syntax directed translation
D. Code optimization
Answer: C. Syntax directed translation.
Lexical analysis only groups characters into tokens and syntax analysis only checks the token order against the grammar; neither asks what a name was declared as. Type checking needs the declared type on record and a type attribute on every expression node, and both come from semantic rules attached to the productions. Code optimization runs later, on intermediate code that is already typed.
Question 2: what semantic actions do
What is the role of semantic actions in syntax-directed translation? (TPSC 2024, step-by-step solution)
A. Attach type information to syntax tree nodes
B. Perform code generation based on parse tree structure
C. Check for semantic errors and type mismatches
D. All of the above
Answer: D. All of the above.
A semantic action is ordinary code attached to a production, so it can do whatever the compiler needs at that point in the parse. Recording a type attribute on a node is option A, comparing two operand types and flagging a mismatch is option C, and calling the code generator with the operand places is option B. All three are everyday uses of one mechanism, so no single option is complete.
Question 3: synthesized and inherited translations
Which of the following statements is correct with reference to syntax-directed translation schemes? (BEL 2023, step-by-step solution)
I. Synthesized translation defines the value of the translation of the nonterminal on the left side of the production as a function of the translations of the nonterminal on the right side.
II. Translation of a non-terminal on the right side of the production is defined in terms of a translation of the non-terminal on left. Such translation is called inherited translation.
A. Both I and II
B. Only I
C. Only II
D. Neither I nor II
Answer: A. Both I and II.
Statement I is the definition of a synthesized translation: the left-hand-side value is a function of the values on the right-hand side, so information moves from children to parent. Statement II is the definition of an inherited translation: a right-hand-side non-terminal takes its value from its parent, and the same mechanism lets a left sibling pass a value across. Both are accurate as written, so neither can be rejected.
Type checking with SDT actions: MCQ 4
Question 4: what these SDT actions can type-check
Consider the following grammar, which admits a series of declarations followed by expressions, together with the associated syntax-directed translation (SDT) actions given as pseudo-code. (GATE CS 2021 Set 1, step-by-step solution)
P → D* E*
D → int ID { record that ID.lexeme is of type int }
D → bool ID { record that ID.lexeme is of type bool }
E → E1 + E2 { check that E1.type = E2.type = int; set E.type := int }
E → ! E1 { check that E1.type = bool; set E.type := bool }
E → ID { set E.type := int }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.
Answer: B. Integer variable declarations and integer expressions.
The declaration rules do record each name's type, but E → ID sets E.type := int unconditionally and never consults that record. A name declared bool therefore reaches the expression rules as an int and fails the check inside E → !E1, which rules out A and C. Integer declarations and integer expressions still check correctly, leaving B; nothing here recurses without consuming input, so D is wrong too.
Three-address code MCQ 5
Question 5: three-address code for X := Y + Z
Consider the syntax-directed definition shown below. (GATE CS 2003, step-by-step solution)
S → id := E { gen (id.place = E.place;); }
E → E1 + E2 { t = newtemp ( ); gen (t = E1.place + E2.place;); E.place = t }
E → id { E.place = id.place; }Here gen is a function that generates the output code and newtemp is a function that returns the name of a new temporary variable on every call, with t1, t2 and so on being the names it produces. For the statement X := Y + Z, the three-address code sequence generated by this definition is:
A. X = Y + Z
B. t1 = Y + Z; X = t1
C. t1 =Y; t2 = t1 + Z; X = t2
D. t1 = Y; t2 = Z; t3 = t1 + t2; X = t3
Answer: B. t1 = Y + Z; X = t1.
The rule E → id sets E.place to Y and to Z and emits nothing, so no temporary is spent on an operand. The addition rule calls newtemp exactly once, giving t1, emits t1 = Y + Z and sets E.place = t1, after which the assignment rule emits X = t1. That is two instructions, which is option B; C and D would each need extra newtemp calls this definition never makes.
Ambiguous grammar MCQs 6-7
Question 6: what yacc does with an ambiguous grammar
Consider the following expression grammar, with the semantic rules for expression calculation stated next to each production. (GATE CS 2005, step-by-step solution)
E → number E.val = number.val
| E '+' E E(1).val = E(2).val + E(3).val
| E '×' E E(1).val = E(2).val × E(3).valThe grammar and the semantic rules are fed to a yacc tool, which is an LALR(1) parser generator, for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar?
A. It detects recursion and eliminates recursion
B. It detects reduce-reduce conflict, and resolves
C. It detects shift-reduce conflict, and resolves the conflict in favor of a shift over a reduce action
D. It detects shift-reduce conflict, and resolves the conflict in favor of a reduce over a shift action
Answer: C. Shift-reduce conflict, resolved in favour of the shift.
The grammar is ambiguous, since a string such as 3 × 2 + 1 has more than one parse tree. In the LALR(1) automaton that shows up as a state where the parser has E + E on the stack and sees × ahead: it may reduce E + E to E, or shift the × and keep building. yacc reports the shift-reduce conflict rather than giving up, then applies its default rule and prefers the shift.
Question 7: the precedence and associativity yacc ends up with
Take the same expression grammar and semantic rules as in Question 6. Assume the conflicts above are resolved and an LALR(1) parser is generated for parsing arithmetic expressions. For the expression 3 × 2 + 1, what precedence and associativity properties does the generated parser realise? (GATE CS 2005, step-by-step solution)
A. Equal precedence and left associativity; expression is evaluated to 7
B. Equal precedence and right associativity; expression is evaluated to 9
C. Precedence of '×' is higher than that of '+', and both operators are left associative; expression is evaluated to 7
D. Precedence of '+' is higher than that of '×', and both operators are left associative; expression is evaluated to 9
Answer: B. Equal precedence, right associativity, value 9.
Because every conflict is settled by shifting, the parser never reduces while another operator is waiting, so it groups from the right and gives neither operator priority: equal precedence, right associative. On 3 × 2 + 1 that groups as 3 × (2 + 1), and the rules compute 2 + 1 = 3 then 3 × 3 = 9. Option C is the precedence you would want in a calculator, but not what this grammar produces.
Bottom-up SDT MCQ 8
Reduction order is the whole answer here, because a bottom-up parser fires each action the moment its production is reduced. If handles still feel unfamiliar, the Parsing MCQs set drills them directly.
Question 8: output of a bottom-up parser
Consider the following syntax-directed translation scheme (SDTS), with non-terminals {S, A} and terminals {a, b}. (GATE CS 2016 Set 1, step-by-step solution)
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:
A. 1 3 2
B. 2 2 3
C. 2 3 1
D. syntax error
Answer: C. 2 3 1.
Only one derivation produces aab: S ⇒ aA ⇒ aSb ⇒ aab, so it is not a syntax error. A bottom-up parser builds that in reverse, firing each action as its production is reduced: the second a reduces by S → a and prints 2, then Sb reduces by A → Sb and prints 3. The remaining aA reduces by S → aA and prints 1, giving 2 3 1.
Translation-scheme MCQs 9-10
Both turn on one detail: where each print sits inside the production body. Mark those positions before tracing a single token, because an action placed before a symbol runs ahead of that symbol's own actions and one placed after it runs later.
Question 9: what the scheme prints for 2 * 3 + 4
Consider the following translation scheme. (GATE CS 2006, step-by-step solution)
S → ER
R → *E{print("*");}R | ε
E → F + E {print("+");} | F
F → (S) | id {print(id.value);}Here id is a token that represents an integer and id.value represents the corresponding integer value. For an input 2 * 3 + 4, this translation scheme prints:
A. 2 * 3 + 4
B. 2 * +3 4
C. 2 3 * 4 +
D. 2 3 4+*
Answer: D. 2 3 4+*.
F matches the leading id and prints 2, and the lookahead * makes this first E take the F alternative and stop. Control passes to R → *E{print("*");}R, whose E covers 3 + 4: F prints 3, the nested E prints 4, and the action after that nested E prints +, giving 3 4 +. The print("*") sits after E in the R production, so it fires last and the output is 2 3 4 + *.
Question 10: what the scheme prints for 9 + 5 + 2
Consider the translation scheme shown below. (GATE CS 2003, step-by-step solution)
S → T R
R → + T {print ('+');} R | ε
T → num {print (num.val);}Here num is a token that represents an integer and num.val represents the corresponding integer value. For an input string 9 + 5 + 2, this translation scheme will print:
A. 9 + 5 + 2
B. 9 5 + 2 +
C. 9 5 2 + +
D. + + 9 5 2
Answer: B. 9 5 + 2 +.
S → T R sends the first num through T, which prints 9. R then consumes the first +, expands T so 5 is printed, and only afterwards runs its own action and prints +, leaving 9 5 + so far; the recursive R repeats that on the remaining + 2. The last R takes the ε alternative and prints nothing, so the output is 9 5 + 2 +.
Attribute-evaluation MCQs 11-12
These two ask for a number rather than a rule, and it only falls out once the parse tree is on paper. The Lexical Analysis MCQs cover the phase that runs before any of this.
Question 11: evaluating a grammar with custom operators
Consider the grammar below, with the following translation rules and E as the start symbol. (GATE CS 2004, step-by-step solution)
E → E1 # T { E.value = E1.value * T.value }
| T { E.value = T.value }
T → T1 & F { T.value = T1.value + F.value }
| F { T.value = F.value }
F → num { F.value = num.value }Compute E.value for the root of the parse tree for the expression 2 # 3 & 5 # 6 & 4.
A. 200
B. 180
C. 160
D. 40
Answer: C. 160.
The symbols are deliberately misleading: # multiplies and & adds, and because & sits one level lower in the grammar, inside T, it binds tighter. The expression groups as 2 # (3 & 5) # (6 & 4), so the T sub-trees give 3 + 5 = 8 and 6 + 4 = 10. E is left recursive, so # applies left to right: 2 × 8 = 16, then 16 × 10 = 160.
Question 12: the value an SDD computes for MMLK
Consider the following syntax-directed definition (SDD). (GATE CS 2024 Set 1, step-by-step solution)
S → DHTU {S.val = D.val + H.val + T.val + U.val;}
D → "M"D₁ {D.val = 5 + D₁.val;}
D → ε {D.val = −5;}
H → "L"H₁ {H.val = 5*10 + H₁.val;}
H → ε {H.val = −10;}
T → "C"T₁ {T.val = 5*100 + T₁.val;}
T → ε {T.val = −5;}
U → "K" {U.val = 5;}Given "MMLK" as the input, which one of the following options is the correct value computed by the SDD in the attribute S.val?
A. 45
B. 50
C. 55
D. 65
Answer: A. 45.
In S → DHTU the input splits as D = MM, H = L, T = nothing, U = K. D unwinds from the inside out, so the ε case gives −5, the inner M gives 5 + (−5) = 0 and the outer M gives 5; H is one L over an ε, so 50 + (−10) = 40. T matches ε for −5 and U matches K for 5, so S.val = 5 + 40 − 5 + 5 = 45.
How these questions examine semantic analysis and SDT
Three shapes cover nearly everything asked on this topic. Action timing: given a scheme and an input, say what the parser prints and in what order, decided entirely by where each action sits inside the production body (Questions 8, 9 and 10). Attribute arithmetic: evaluate the root attribute of a tree whose shape is fixed by the grammar rather than by ordinary operator precedence (Questions 11 and 12). Soundness: read a set of rules and decide what they can actually check, or how a parser generator settles an ambiguity (Questions 4, 6 and 7).
For the arithmetic group, draw the parse tree first, annotate the leaves, then fold values upward one node at a time; reading a value straight off the infix expression is the commonest way marks go missing, because the grammar and not convention decides what binds tighter. For the printing group, mark the position of every action inside its production before you start, since moving one print from before a symbol to after it changes the whole output string.
Answer map: 1-C, 2-D, 3-A, 4-B, 5-B, 6-C, 7-B, 8-C, 9-D, 10-B, 11-C, 12-A.
Redo any question you missed on paper, tracing the actions in the order the parser fires them rather than the order they are written down. For the full compiler design sequence, work through GATE Guidance by Sanchit Sir.
