This set covers how meaning is attached to syntax and how source programs are lowered to intermediate form. You will evaluate syntax-directed definitions, distinguish synthesized and inherited attributes, classify S-attributed and L-attributed schemes, and work with three-address code, quadruples, triples, DAGs and postfix notation. It suits GATE CSE preparation, university compiler design exams and interviews that examine compiler internals.
How to practise: read each question and tap the option you think is correct. You will see right away whether you got it, along with a short explanation, and your score is tracked at the bottom of the screen. This set has 18 questions.
Topics covered in this set
- Synthesized and inherited attributes
- S-attributed and L-attributed definitions
- Evaluating SDT schemes on input strings
- Dependency graphs and evaluation order
- Three-address code, quadruples and triples
- DAGs for expressions
- Backpatching, SSA and array address calculation
Compiler Design MCQs with answers and explanations
Q1. A syntax-directed definition is called S-attributed when
a) it uses only synthesized attributes
b) it uses only inherited attributes
c) every attribute depends on the start symbol
d) it has no semantic rules on epsilon productions
Q2. In an L-attributed definition with production A -> X1 X2 ... Xn, an inherited attribute of Xi may depend on
a) attributes of X1 ... Xi-1 and inherited attributes of A
b) attributes of any Xj, including those to the right of Xi
c) synthesized attributes of A only
d) attributes of Xi+1 ... Xn only
Q3. An S-attributed definition is most naturally evaluated
a) only after building a complete DAG
b) by a right-to-left traversal of the tree
c) before lexical analysis
d) during bottom-up (LR) parsing, at each reduction
Q4. Using the translation scheme below, what value is computed for the input 2 # 3 & 4?
E -> E1 # T { E.val = E1.val * T.val }
E -> T { E.val = T.val }
T -> T1 & F { T.val = T1.val + F.val }
T -> F { T.val = F.val }
F -> num { F.val = num.value }
a) 10
b) 14
c) 20
d) 24
Q5. A bottom-up parser executes the translation scheme below on the input a + b * c. What is printed?
E -> E + T { print('+') }
E -> T
T -> T * F { print('*') }
T -> F
F -> id { print(id.name) }
a) ab+c*
b) +a*bc
c) abc*+
d) abc+*
Q6. How many nodes does the DAG for the expression below contain?
(x * y) + (x * y - z) * z
a) 6
b) 7
c) 8
d) 9
Q7. What is the main advantage of indirect triples over ordinary triples?
a) They need no temporary names in the symbol table
b) They use fewer fields per instruction than triples
c) They remove the need for a symbol table
d) Instructions can be reordered by rearranging a pointer list without changing operand references
Q8. A quadruple has the fields op, arg1, arg2 and result. Which of these fields is absent in a triple?
a) result
b) op
c) arg1
d) arg2
Q9. For int a[10][20] stored in row-major order with 0-based indices and 4-byte integers, what is the byte offset of a[i][j] from the base address?
a) (j * 10 + i) * 4
b) (i * 10 + j) * 4
c) (i * 20 + j) * 4
d) (i + j * 20) * 4
Q10. Backpatching is mainly used to
a) reorder basic blocks for better cache behaviour
b) eliminate common subexpressions
c) fill in jump targets that are unknown when the jump instruction is generated
d) allocate registers to temporaries
Q11. What is the postfix form of the expression a * (b + c) - d?
a) a b c + * d -
b) a b + c * d -
c) a b c * + d -
d) - * a + b c d
Q12. In static single assignment (SSA) form, which property holds?
a) Every variable is used exactly once
b) No temporary variables are allowed
c) Every variable is assigned exactly once in the program text, with phi functions merging values at join points
d) All assignments must be to array elements
Q13. What is the main advantage of representing an expression as a DAG rather than a syntax tree?
a) The DAG always has more nodes, allowing finer optimisation
b) A DAG removes the need for three-address code
c) A DAG can represent only constant expressions
d) Identical subexpressions share a single node, revealing common subexpressions
Q14. In the declaration rule D -> T L { L.in = T.type }, the attribute L.in is
a) a synthesized attribute
b) an inherited attribute
c) a lexical value
d) an intrinsic attribute of a terminal
Q15. For a syntax-directed definition on a given parse tree, a valid order of evaluating the attributes is
a) a postorder traversal in every case
b) the reverse of the order in which tokens appear
c) a breadth-first traversal of the parse tree
d) a topological sort of the dependency graph
Q16. Which of the following is NOT a valid three-address instruction?
a) x = y + z
b) x = y + z * w
c) if x < y goto L
d) x = y[i]
Q17. Which statement about attributed definitions is correct?
a) Every L-attributed definition is also S-attributed
b) Every S-attributed definition is also L-attributed
c) L-attributed definitions cannot use synthesized attributes
d) S-attributed definitions must use at least one inherited attribute
Q18. With short-circuit (jumping) code for the condition B1 || B2, what happens when B1 evaluates to true?
a) Control jumps to the true exit without evaluating B2
b) B2 is still evaluated and the results are combined with OR
c) Control jumps to the false exit
d) B2 is evaluated first and B1 is ignored
Quick revision notes
- Synthesized attribute: computed from children; inherited attribute: from parent and siblings.
- S-attributed = only synthesized attributes; evaluable bottom-up during LR parsing.
- L-attributed: inherited attributes of Xi depend only on X1..Xi-1 and inherited attributes of the parent; every S-attributed SDD is L-attributed.
- A valid evaluation order is a topological sort of the dependency graph; cycles mean no order exists.
- Quadruple: op, arg1, arg2, result. Triple: op, arg1, arg2 (results referred to by position).
- Indirect triples keep a separate list of pointers so statements can be reordered cheaply.
- Row-major address of a[i][j] in a[R][C]: base + (i*C + j) * w.
- DAG nodes for repeated subexpressions are shared, exposing common subexpressions.
Frequently asked questions
What is the difference between S-attributed and L-attributed definitions?
An S-attributed definition uses only synthesized attributes, so it can be evaluated in one bottom-up pass. An L-attributed definition also allows inherited attributes, but only those that depend on the parent and on siblings to the left, so it can be evaluated in a single left-to-right depth-first traversal.
Why do compilers use three-address code?
Three-address code breaks complex expressions into simple steps with at most one operator each. This form is close to machine instructions yet independent of any particular machine, making optimisation and retargeting easier.
What is backpatching?
Backpatching generates jump instructions with unfilled targets and records them in lists. When the target label becomes known later, the compiler fills in those targets, allowing boolean and control-flow code to be generated in one pass.
Comments
Post a Comment