syntax-directed translation
syntax-directed translation MCQs
1
Q: In an S-attributed grammar all attributes are:
A. inherited only
B. synthesized only
C. both inherited and synthesized
D. neither
Answer: B
Solution: S-attributed grammars use only synthesized attributes; these can be evaluated in a bottom-up parse.
2
Q: Which attribute evaluation strategy is guaranteed to work for any L-attributed grammar during a single left-to-right traversal of a top-down parser?
A. Postorder on parse tree
B. Leftmost depth-first traversal evaluating attributes as soon as possible
C. Any order
D. Rightmost depth-first traversal
Answer: B
Solution: L-attributed grammars allow inherited attributes to depend only on left siblings and parent, so left-to-right top-down evaluation works.
3
Q: Given production A → B C where B has synthesized attribute b.val and C has inherited attribute c.type that depends on b.val, is this L-attributed?
A. Yes
B. No
C. Only if b.val is constant
D. Only if grammar is S-attributed
Answer: A
Solution: Inherited attribute of C depending on synthesized attribute of left sibling B is allowed in L-attributed grammars.
4
Q: Semantic actions in a syntax-directed translation placed after the RHS of a production are best for:
A. Top-down parsers only
B. Bottom-up parsers only
C. Both parsers equally
D. Neither parser
Answer: B
Solution: Actions after RHS correspond to reductions — natural for bottom-up parsers (e.g., YACC).
5
Q: For production E → E1 + T with semantic action E.val = E1.val + T.val, these attributes are:
A. synthesized for E, using synthesized for E1 and T
B. inherited for E, synthesized for E1 and T
C. synthesized for E1, inherited for T
D. inherited for all
Answer: A
Solution: E.val is computed from children — synthesized; children attributes are synthesized.
6
Q: Which translation scheme converts parse tree nodes to postfix notation by printing operator after children?
A. Preorder with print before children
B. Inorder with print between children
C. Postorder with print after children
D. Level order traversal
Answer: C
Solution: Postorder prints operands first then operator — produces postfix.
7
Q: In Bison/YACC, semantic actions in C code are executed at:
A. Shift time
B. Reduce time
C. Goto time
D. At parser initialization only
Answer: B
Solution: YACC executes semantic actions when a reduction occurs (after recognizing the RHS).
8
Q: An attribute grammar is circular if:
A. evaluation order is impossible due to cycles
B. all attributes are synthesized
C. it has left recursion
D. it is L-attributed
Answer: A
Solution: Circular dependencies between attributes mean no finite evaluation order exists.
9
Q: For bottom-up parsing, semantic actions that need child attribute values must be placed:
A. before the first symbol of RHS
B. between symbols appropriately
C. after the RHS
D. never possible
Answer: C
Solution: After RHS ensures children attributes are available during reduction.
10
Q: Consider grammar S → a S b | ε with semantic action to check equal numbers of a and b using a synthesized attribute S.count. Is this S-attributed?
A. Yes
B. No
C. Only if ε sets count 0
D. Only if counts are inherited
Answer: A
Solution: Counts can be synthesized: ε sets 0; for a S b, S.count = S1.count + 1 (or similar), so synthesized only.
11
Q: Which of the following is not true about L-attributed grammars?
A. They allow left-to-right attribute evaluation during top-down parsing.
B. They permit inherited attributes that depend on right siblings.
C. All S-attributed grammars are L-attributed.
D. They support many practical translation schemes.
Answer: B
Solution: Inherited attributes cannot depend on right siblings in L-attributed grammars.
12
Q: If semantic action @1 is placed between symbols A and B in production X → A @1 B, when is it executed in bottom-up parsing?
A. When A is shifted
B. When B is shifted
C. At reduction of A
D. At reduction of entire RHS
Answer: C
Solution: Action placed between corresponds to action executed when left part A has been reduced (i.e., during a reduce that creates the left context).
13
Q: To translate infix expression to three-address code while parsing top-down, you should attach semantic actions:
A. only at the end of production
B. to compute temporaries as you reduce subexpressions (postorder)
C. before any tokens
D. randomly
Answer: B
Solution: For top-down, place actions to compute temporaries after subexpressions are parsed (postorder style).
14
Q: A synthesized attribute can depend on:
A. inherited attributes of the same node only
B. attributes of children and their synthesized/inherited attributes
C. only the parent attributes
D. global variables only
Answer: B
Solution: Synthesized attributes are computed from children attributes (both kinds).
15
Q: Which method is typically used to implement short-circuit boolean evaluation in an SDT?
A. Immediate printing of results
B. Backpatching with true/false lists
C. L-attributed evaluation always
D. S-attributed evaluation always
Answer: B
Solution: Backpatching creates lists of jump targets (true/false) and patches later to support short-circuit codegen.
16
Q: The translation scheme uses markers like M in productions S → E M where M triggers M.place = nextquad. This is an example of:
A. inherited attribute usage
B. synthesized attribute usage
C. using dummy nonterminals for actions (semantic marker)
D. invalid SDT
Answer: C
Solution: Marker nonterminals hold actions like storing nextquad — common technique for backpatching.
17
Q: For grammar E → E + T | T, if we use left recursion, evaluation for three address code with synthesized attributes is:
A. easy with bottom-up parsing
B. impossible
C. only if we convert to right recursion
D. only with inherited attributes
Answer: A
Solution: Synthesized attributes for left-recursive grammar can be evaluated during bottom-up reductions.
18
Q: In a translation scheme to produce prefix notation, semantic action should print operator:
A. before its operands (preorder)
B. between operands (inorder)
C. after operands (postorder)
D. not printable
Answer: A
Solution: Prefix prints operator first, so action executed before processing operands.
19
Q: If an inherited attribute of nonterminal B depends on the synthesized attribute of C (right sibling), is grammar L-attributed?
A. Yes
B. No
C. Only for binary grammars
D. Only if left recursion absent
Answer: B
Solution: L-attributed forbids dependency on right siblings’ synthesized attributes.
20
Q: Which is true about converting an SDT with actions inside RHS to an equivalent grammar without embedded actions?
A. Always impossible
B. Use marker nonterminals to represent actions
C. Only for S-attributed grammars
D. Only for L-attributed grammars
Answer: B
Solution: Insert new nonterminals (markers) whose productions carry the action to move actions to reductions.
21
Q: For production S → if ( E ) S1 else S2 with backpatching, we maintain E.truelist and E.falselist. After generating code for S1, we must:
A. patch E.truelist to start of S1
B. patch E.falselist to S1
C. patch both to S2
D. do nothing
Answer: A
Solution: True list branches to S1; false list goes to S2. Backpatching fills addresses when known.
22
Q: Which attribute evaluation order is safe for any parse tree with only synthesized attributes?
A. Bottom-up postorder traversal
B. Top-down preorder traversal
C. Random order
D. Requires backpatching
Answer: A
Solution: Synthesized attributes depend on children; postorder (children first) is safe.
23
Q: In an L-attributed grammar, inherited attributes can be passed:
A. from left siblings and parent only
B. from right siblings only
C. from children only
D. from anywhere in tree
Answer: A
Solution: L-attributed rules allow inherited attrs to depend on parent and left siblings.
24
Q: Consider SDT: L → L1 , E { print(","); }. If we want comma after each element except last, where should action be placed?
A. After E and before comma in production L → L , E
B. After entire list
C. At start of grammar
D. After L1 only
Answer: A
Solution: Place action between E and comma or use marker to print comma before next element.
25
Q: A translation scheme that computes the value of arithmetic expressions using attributes but requires no inherited attributes is:
A. S-attributed
B. L-attributed only
C. Not possible
D. Requires marker nonterminals
Answer: A
Solution: All synthesized attributes — S-attributed — suitable for bottom-up evaluation.
26
Q: The main reason to use inherited attributes is to:
A. propagate type information or context from parent to children
B. reduce code size
C. confuse the parser
D. ensure S-attributed grammar
Answer: A
Solution: Inherited attributes supply context (like expected type, symbol table pointers) from parent/left siblings.
27
Q: For translation S → id := E generating code E.code; id = E.place, where E.place is a temporary. Here id receives value by:
A. synthesized attribute of id
B. semantic action after RHS assigning to id
C. inherited attribute of id
D. cannot be done
Answer: B
Solution: Use action after RHS to emit assignment instruction assigning E.place to id.
28
Q: If a grammar is S-attributed, which parser style is easiest to implement code generation?
A. Bottom-up LR parser
B. Predictive top-down parser only
C. Neither parser can be used
D. Fixed order interpreter
Answer: A
Solution: Bottom-up parsers naturally evaluate synthesized attributes during reductions.
29
Q: In three-address code generation, temporary names are usually produced by:
A. inherited attributes only
B. a global nexttemp counter referenced by semantic actions
C. const folding only
D. not required
Answer: B
Solution: Typical codegen uses newtemp() (global counter), called in semantic actions to allocate temporaries.
30
Q: Given production T → F { T.place = F.place } and T → T1 * F { T.place = gen(T1.place, '*', F.place) }, attributes used are:
A. inherited only
B. synthesized only
C. both inherited and synthesized
D. none
Answer: B
Solution: place is synthesized — computed from child attributes.
31
Q: Backpatching requires which of the following?
A. Maintaining lists of incomplete jump instructions
B. Converting grammar to S-attributed only
C. Eliminating left recursion
D. No marker nonterminals
Answer: A
Solution: Backpatching accumulates lists of jump sites to be filled later.
32
Q: In SDT, to print number of nodes in a subtree using inherited attributes, you would:
A. pass a running count to children via inherited attribute
B. use synthesized attributes only
C. can’t compute counts with inherited attributes
D. require S-attributed grammar
Answer: A
Solution: Inherited attrs convey context (like current count) to children for accumulation.
33
Q: For expression evaluation with operator precedence using SDT, common approach is:
A. use left recursion with synthesized attrs
B. use right recursion only
C. leave precedence to semantic actions only
D. avoid any recursion
Answer: A
Solution: Left recursion with synthesized attributes and grammar structure enforces precedence and associativity.
34
Q: To support declarations where type is specified before list of identifiers (type idlist), a practical approach in SDT is:
A. use inherited attribute id.type set from type
B. use synthesized attribute only
C. use global variables only
D. parse without attributes
Answer: A
Solution: Inherited attribute propagates declared type down to identifier nodes for symbol table insertion.
35
Q: Which of the following is easiest to evaluate during a single bottom-up pass?
A. An S-attributed grammar
B. A grammar with only inherited attributes
C. A grammar with cycles in attributes
D. A grammar needing right-sibling info for inherited attrs
Answer: A
Solution: S-attributed grammars suit bottom-up one-pass evaluation since synthesized attrs derive from children.
36
Q: For translating while ( E ) S with backpatching, standard code order is:
A. evaluate E, if true goto body, after body goto E’s start, false goto exit
B. body first, then E
C. emit exit code then enter loop
D. none
Answer: A
Solution: Backpatch true list to body start, false list to exit; after body jump back to E start.
37
Q: If semantic action depends on attributes of tokens (like num.val), the token must carry:
A. no data
B. lexeme/value in token attribute structure (yylval in YACC)
C. only position info
D. only type info
Answer: B
Solution: Lexer returns tokens with semantic values for parser actions to use.
38
Q: Which property ensures that semantic actions placed before RHS components can be executed in top-down parsers?
A. Action uses only inherited attributes available at that point
B. Action uses synthesized attributes of future symbols
C. Action uses attributes of right siblings
D. Actions always invalid before RHS
Answer: A
Solution: Actions before RHS can only rely on inherited/available info, not on yet-to-be parsed children.
39
Q: In LALR parser with embedded actions, an action between RHS symbols executes when:
A. the parser reduces the left part that forms the context for the action
B. at shift of next symbol always
C. at parser termination
D. never
Answer: A
Solution: Embedded action becomes a production; it’s reduced when left part is complete, triggering action.
40
Q: Given grammar with List → List , E | E, to generate code for printing items separated by commas without trailing comma, best is to:
A. print comma before printing subsequent E using marker grammar
B. always print comma after E
C. print commas randomly
D. impossible
Answer: A
Solution: Use marker to print comma before next element, avoiding trailing comma.
41
Q: In a translation scheme, using inherited attribute offset for array declarations is used to:
A. compute memory offsets for each element as you enter identifier nodes
B. avoid symbol tables
C. always produce constants only
D. none
Answer: A
Solution: offset inherited to each declarator gives its location; incremented as you process list.
42
Q: Which is NOT a typical component of an attribute grammar implementation?
A. Attribute evaluation engine
B. Storage for attributes on nodes
C. Global nextquad and nexttemp counters
D. Compiler optimizer invoked during parsing automatically
Answer: D
Solution: Optimizer is separate; parsing/SDT handles attribute evaluation and codegen primitives.
43
Q: For short-circuiting A && B in SDT, code generated should:
A. evaluate A, if false jump to false target without evaluating B
B. always evaluate both A and B
C. evaluate B first
D. print both expressions
Answer: A
Solution: Short-circuit: if A false, overall false; backpatching handles jumps.
44
Q: In a bottom-up parser, semantic action placed mid-RHS can be simulated by:
A. introducing a new nonterminal M whose production includes the action as a reduction
B. removing action entirely
C. shifting action into lexer
D. converting grammar to S-attributed
Answer: A
Solution: Marker nonterminals represent actions so they reduce at proper times.
45
Q: A grammar with only synthesized attributes is guaranteed to be:
A. S-attributed
B. L-attributed only
C. Not evaluable
D. Cyclic
Answer: A
Solution: Synthesized-only defines S-attributed grammars.
46
Q: Which technique helps to evaluate attributes on the fly without building full parse tree?
A. Use semantic actions in parser during shifts/reductions to compute and store attributes
B. Build entire parse tree then evaluate attributes in separate pass only
C. Only use global variables
D. Not possible
Answer: A
Solution: Many parsers compute attributes during parsing to avoid building full tree (e.g., YACC).
47
Q: If E → T E' and E'.inh = T.val and E'.syn computed accordingly, this demonstrates:
A. use of inherited attributes to thread left-associativity
B. impossible design
C. only synthesized usage
D. grammar is S-attributed
Answer: A
Solution: Inherited attr E'.inh passes T’s value to E' for left-associative accumulation.
48
Q: For grammar S → A and A → B C, an inherited attribute of B can be set only from:
A. attributes of A or left siblings (none)
B. attributes of C (right sibling)
C. attributes of B itself only
D. random global state
Answer: A
Solution: Inherited attrs of B come from parent A or left siblings (none here), not from right sibling C in L-attributed grammar.
49
Q: The common way to generate code for a = b + c * d that respects precedence is to:
A. let grammar structure ensure * binds tighter and generate temporaries accordingly
B. evaluate left to right blindly
C. multiply before parsing
D. assign random order
Answer: A
Solution: Grammar for terms/factors ensures c * d reduced first, producing temp, then b + temp.
50
Q: For creating parse-tree nodes with attributes, where are attributes stored?
A. In table entries associated with node handles/objects
B. In the token stream only
C. In the grammar file statically
D. Not stored at all
Answer: A
Solution: Nodes carry attribute fields (e.g., .val, .type) stored in AST or parse tree nodes.
51
Q: If a semantic action prints something, and you place it before parsing E in production S → @print E, the action occurs:
A. before E is parsed (useful for prefix)
B. after E parsed only
C. at end of parsing
D. never
Answer: A
Solution: Actions before RHS execute immediately during top-down parse; used for prefix output.
52
Q: In translating for ( i = 0; i < n; i++ ) S, we need markers to record:
A. start of condition, start of body, and nextquad for increment
B. only end of program
C. nothing
D. tokens only
Answer: A
Solution: Markers capture positions for conditional test, body, and back-jump for increment.
53
Q: Which of these is essential for code generation of Boolean expressions using backpatching?
A. Maintaining truelist and falselist for each expr
B. Computing entire expression value as integer only
C. Using S-attributed grammar only
D. Precomputing all jumps statically
Answer: A
Solution: truelist and falselist store pending jumps to be patched when targets known.
54
Q: Suppose you have semantic action that needs to know address of next instruction. Which helper is used?
A. nextquad or nextinstr called at that point
B. newtemp counter
C. yylex only
D. not required
Answer: A
Solution: nextquad returns current instruction number for backpatching/labels.
55
Q: Is it safe to evaluate synthesized attributes during shift operations in an LR parser?
A. No — children may not be complete
B. Yes always
C. Only for inherited attrs
D. Only if grammar is L-attributed
Answer: A
Solution: During shifts, the RHS is not fully reduced; synthesized attrs need full child values — evaluate on reduce.
56
Q: Which transform helps to convert semantic actions for a top-down parser into ones usable by bottom-up parser?
A. Move actions to the end of productions by introducing marker nonterminals
B. Keep them inline only
C. Convert them into lexical rules
D. Not possible
Answer: A
Solution: Marker nonterminals allow actions to occur at reductions compatible with bottom-up parsing.
57
Q: For grammar generating XML-like nested tags, an inherited attribute expectedClose passed to child helps to:
A. ensure matching closing tag for nested structure
B. ignore matching
C. synthesize unrelated data
D. none
Answer: A
Solution: expectedClose conveys the tag name expected for closing, enabling checking during parse.
58
Q: If an attribute computation requires both left and right subtree info at once, a simple S-attributed approach:
A. may require building full tree then doing a postorder evaluation
B. works in single left-to-right pass always
C. needs no tree
D. impossible
Answer: A
Solution: When cross-dependencies exist, build tree and evaluate in appropriate order.
59
Q: For translation of if E1 then S1 else S2, backpatching usually:
A. patches E1.truelist to S1.start and E1.falselist to S2.start
B. patches both to S1 only
C. uses no patching
D. patches S1 to S2 only
Answer: A
Solution: True branch to S1, false to S2; backpatch when S1 and S2 starts are known.
60
Q: A semantic action that uses a nonterminal’s inherited attribute that hasn’t been computed yet is:
A. illegal / leads to undefined behavior
B. acceptable if delayed
C. always fine
D. necessary for S-attributed grammars
Answer: A
Solution: Using uninitialized inherited attribute leads to wrong behavior; ensure it’s set before use.
61
Q: In code generation, to ensure consistent temporary names in nested expressions like a + (b + c) + d, one should:
A. generate temporaries with newtemp() deterministically when computing subexpressions
B. reuse same temp always
C. avoid temps altogether
D. only use global variables
Answer: A
Solution: Using newtemp() produces unique temporaries for intermediate results.
62
Q: Which of the following is an example of inherited attribute use?
A. Propagating a symbol-table pointer env from declarations to nested scopes
B. Summing sizes upward only
C. Assigning value from children to parent only
D. Printing expressions after parsing
Answer: A
Solution: env is context info passed down as inherited attribute to nested declarations.
63
Q: Concerning evaluation order, a cyclic dependency like A.x depends on B.y and B.y depends on A.x is:
A. unsolvable — circular
B. solvable by top-down only
C. solvable by bottom-up only
D. always okay for L-attributed grammars
Answer: A
Solution: Circular attribute dependencies cannot be evaluated without fixing the grammar/semantics.
64
Q: For generating code for assignment statement list S → S1 ; S2, to preserve ordering you must:
A. execute S1.code then S2.code in semantic actions placed after respective productions
B. execute S2 first always
C. combine codes unordered
D. none
Answer: A
Solution: Place actions to emit S1 code before S2 code to preserve program order.
65
Q: Which translation scheme is suitable for generating assembly labels for statements?
A. Use markers M to capture nextquad for label positions
B. Use only synthesized attrs to compute labels after entire program parsed
C. Avoid labels completely
D. Use right recursion only
Answer: A
Solution: Markers capture instruction indices where labels should point; backpatch later.
66
Q: For grammar Dec → type idlist ; with action for each id in idlist insert into symbol table with type, what attribute is convenient?
A. idlist.list synthesized list of identifiers
B. type synthesized only
C. inherited id.type only
D. None
Answer: A
Solution: idlist.list is synthesized to collect identifiers, then symbol table insert uses type.
67
Q: Which feature makes an attribute grammar not L-attributed?
A. Inherited attribute of a symbol depending on right sibling’s synthesized attribute
B. Parent passing attribute to left child
C. Left sibling passing attribute to right sibling
D. Using only synthesized attributes
Answer: A
Solution: Dependency on right sibling’s synthesized attribute violates L-attributed constraints.
68
Q: In SDT, to print a comma-separated list while parsing left to right with top-down parser, you usually:
A. when parsing subsequent element, print comma before printing element (use inherited flag)
B. print comma after last element only
C. print comma after each element regardless
D. cannot do this top-down
Answer: A
Solution: Use an inherited flag telling node whether it’s first; print comma before element if not first.
69
Q: Marker nonterminal M with semantic action M.quad = nextquad is used mainly to:
A. capture current instruction address to use later for backpatching
B. create new temporaries
C. compute expression values only
D. lexically analyze tokens
Answer: A
Solution: M records current quad number for jumps/labels when code is generated later.
70
Q: For grammar converting infix to postfix using SDT, where should print(op) for operator be placed?
A. After parsing both operands (postorder)
B. Before parsing operands
C. At start of program
D. Not at all
Answer: A
Solution: Postorder prints operands first, then operator — yields postfix.
71
Q: In a bottom-up parser, an action placed immediately on the right of a symbol in RHS is executed:
A. when a reduction completes that creates that symbol and left context
B. immediately upon shift of that symbol
C. never
D. only at end of input
Answer: A
Solution: Embedded action becomes a separate production and reduces when its left context is reduced.
72
Q: To check redeclaration errors during parsing declarations int a, b, a;, semantic action should:
A. look up each id in symbol table, if found signal error; insert otherwise
B. ignore duplicates entirely
C. delay check until codegen
D. only check types, not duplicates
Answer: A
Solution: Semantic action on each identifier insertion performs lookup and reports redeclaration.
73
Q: For generating three-address code for x = y * z + w, a correct sequence is:
A. t1 = y * z; t2 = t1 + w; x = t2
B. t1 = y; t2 = z; x = t1 * t2 + w
C. x = y * z + w (one instruction)
D. t1 = y + z; t2 = t1 * w; x = t2
Answer: A
Solution: Respect precedence: * first, then +, using temporaries for intermediate results.
74
Q: Which of the following is a potential problem when placing semantic actions in the grammar arbitrarily?
A. They may require attributes not available at that point
B. They always optimize code
C. They reduce parser speed always
D. No problems exist
Answer: A
Solution: Actions can reference attributes not yet defined; must be placed carefully or use markers.
75
Q: In SDT for expression translation using inherited attribute E.in and synthesized E.syn, the purpose is typically to:
A. carry partial computation left to right while accumulating result
B. prevent code generation
C. only print tree
D. lexically analyze expressions
Answer: A
Solution: E.in passes accumulated left value to rest of expression for left-associative evaluation.
76
Q: When converting an SDT with embedded print actions to YACC, the embedded actions should be:
A. moved into separate productions so they execute at appropriate reductions
B. left as-is always
C. moved to lexer only
D. removed
Answer: A
Solution: YACC executes actions at reductions, so embedding into productions via markers aligns semantics.
77
Q: Consider grammar S → A B where B needs type info from A (synthesized). To supply B with that info in L-attributed style, you:
A. set B.in = A.syn as an inherited attribute when expanding S
B. cannot pass synthesized info to B
C. use only global variables
D. delay B’s parsing until A is reduced (not possible in top-down)
Answer: A
Solution: Parent can pass B.in from A.syn once A is available — in parsing, achievable via action or by rewriting grammar with markers.
78
Q: For expression grammar using right recursion E → T | T + E, is it easy to obtain left associative + with synthesized attributes?
A. No — right recursion yields right associativity by default
B. Yes — synthesized attributes make it left associative
C. Associativity unaffected by recursion
D. Impossible to define associativity
Answer: A
Solution: Right recursion gives right associativity; left recursion preferred for left associativity.
79
Q: Which approach is commonly used to avoid building a full parse tree yet still do semantic checks?
A. Execute semantic actions during parsing and maintain symbol tables and attribute values in node records created transiently
B. Always build full tree and then traverse it
C. Use no semantic checks at parse time
D. Only use static analysis later
Answer: A
Solution: Parsers often perform actions on the fly, avoiding storing full tree but keeping necessary info.
80
Q: In backpatching, an empty list is denoted by:
A. [] and the makelist operation creates a new list containing the current quad
B. {0} always
C. None required
D. -1 placeholder only
Answer: A
Solution: makelist(nextquad) creates list with current instruction index; merge combines lists.
81
Q: If you need to generate code for function calls f(a,b), semantic actions must:
A. evaluate argument expressions, push arguments, call function, handle return value
B. only print function name
C. evaluate function body at call site
D. nothing
Answer: A
Solution: Actions compute arg places, emit argument pushes, call instruction, and retrieve return value into temp.
82
Q: Evaluating attributes in a parse tree by repeatedly evaluating nodes whose dependencies are satisfied is:
A. a topological sorting approach to attribute evaluation
B. unrelated to attribute grammars
C. always fails
D. only for L-attributed grammars
Answer: A
Solution: Topological order of dependency graph yields a valid evaluation schedule if acyclic.
83
Q: A semantic action inserted immediately after an operator in production E → E1 + @op + T can be used to:
A. record operator token for later use or print prefix/postfix forms
B. change parser state arbitrarily
C. access right sibling synthesized attrs immediately
D. not useful
Answer: A
Solution: Action can capture operator’s lexeme into attribute for subsequent code generation.
84
Q: Which is true about using global variables (like nexttemp) in semantic actions?
A. They simplify implementation but reduce modularity and testability
B. They are forbidden always
C. They guarantee thread safety
D. They avoid need for attribute grammars
Answer: A
Solution: Globals are expedient but less clean; commonly used for counters in simple SDT implementations.
85
Q: Suppose you have production S → id := E and want to perform type check ensuring id.type == E.type. Where should check be placed?
A. After evaluating E.type, i.e., in action after RHS
B. Before parsing id
C. At end of program only
D. Not possible
Answer: A
Solution: Action placed after E is evaluated and has E.type synthesized; compare with id’s type in symbol table.
86
Q: In SDT for nested scopes, which attribute is essential to pass into declarations in a block?
A. env (symbol table pointer) as inherited attribute
B. nexttemp only
C. nextquad only
D. none
Answer: A
Solution: env inherited into nested declarations ensures correct scope insertion and lookup.
87
Q: For grammar that includes print statements, semantic action to emit print code should have access to expression value — this suggests:
A. expr.place synthesized and action uses it after RHS
B. expr must be evaluated later in codegen only
C. use inherited only
D. impossible
Answer: A
Solution: expr.place provides temporary holding result; print action emits code referencing it.
88
Q: When you convert an SDT with inline actions into an equivalent grammar with marker nonterminals, the number of productions:
A. increases (because of inserted markers)
B. decreases
C. stays same always
D. becomes infinite
Answer: A
Solution: Each action becomes a new nonterminal production, increasing grammar size.
89
Q: A typical semantic action for field access e.f in object language will:
A. compute address offset using e.offset and field layout info, produce a place pointing to memory location
B. ignore object layout entirely
C. always copy entire object
D. not type check fields
Answer: A
Solution: Action computes field offset and generates code to access memory location or value.
90
Q: If you want to implement operator precedence and associativity in SDT, which grammar design helps?
A. Use separate nonterminals for E, T, F (expression/term/factor) with appropriate recursions
B. Single production with all operators same precedence
C. Random production order
D. None of the above
Answer: A
Solution: Grammar layering enforces precedence and associativity structurally, simplifying SDT.
91
Q: For semantic actions printing assembly labels, you often need a function emit(label:) that uses:
A. nextquad or stored marker positions to place label before instruction
B. print after program finish only
C. ignore labels completely
D. none
Answer: A
Solution: emit places label at the recorded quad index or uses marker to insert label.
92
Q: Consider E → E1 + T where you decide to compute E.place = newtemp(); emit(E.place := E1.place + T.place) in semantic action. This requires that:
A. E1.place and T.place are already available (synthesized) — hence action must be after RHS reduce
B. action can be before parsing E1
C. action can execute at any time
D. newtemp not needed
Answer: A
Solution: To emit correct code, child places must exist — action executes when children are reduced.
93
Q: The attribute dependency graph for a node:
A. has nodes for attributes and directed edges for dependencies and must be acyclic for evaluation
B. always cyclic
C. irrelevant to evaluation order
D. only used in lexical analysis
Answer: A
Solution: Edge A→B if B depends on A; acyclicity ensures evaluation order exists.
94
Q: For switch statement translation, switch value is compared to each case; efficient SDT often uses:
A. jump table generation when case labels are dense, else chain of comparisons with backpatching
B. always linear comparisons only
C. always use binary search of cases at parse time
D. ignore labels
Answer: A
Solution: TD/BU SDT can emit jump tables or comparisons based on case density using semantic actions.
95
Q: Using SDT, unreachable code detection during parsing is:
A. possible to some extent by tracking control flow and marking unreachable blocks as you backpatch
B. impossible until optimization phase only
C. not related to SDT
D. always perfect at parse time
Answer: A
Solution: Basic unreachable detection (e.g., after return) can be caught via semantic actions tracking control flow.
96
Q: Which of the following transformations may be necessary to make a grammar suitable for LL(1) parsing while preserving SDT semantics?
A. Left-factor and remove left recursion; move semantic actions into markers appropriate for top-down parsing
B. Introduce left recursion only
C. Merge unrelated productions
D. Do nothing
Answer: A
Solution: For LL(1), rewrite grammar and relocate actions so inherited/synthesized attr flow preserved.
97
Q: To build a symbol table entry for function f before parsing its body (for recursive calls), you should:
A. insert function header into symbol table with type before parsing body using action after header
B. parse body first then insert header
C. never insert into symbol table
D. insert only after type checking whole program
Answer: A
Solution: Insert function signature early so recursive calls can find the symbol.
98
Q: Which of these is true regarding code generation by SDT and optimizations?
A. SDT often produces naive code; optimizations typically run as separate passes on IR generated by SDT
B. SDT always produces fully optimized code during parsing
C. SDT cannot produce IR
D. SDT solves register allocation optimally always
Answer: A
Solution: SDT emits intermediate code; later passes perform optimizations (constant folding, dead code elimination).
99
Q: A grammar with attribute width that depends on a list’s length using synthesized attribute list.len is:
A. easily handled by collecting elements into list via synthesized attributes then computing width = len * elementSize
B. impossible unless inherited attrs used
C. requires backpatching only
D. none
Answer: A
Solution: Synthesize list.len by combining child lengths; compute width afterward.
100
Q: In SDT, generating correct l-values vs r-values (address vs content) for expressions like *p = q requires:
A. distinguishing place (r-value) from addr (l-value) attributes and emitting store addr, place
B. always using only place attribute
C. treating both same always
D. not supported by SDT
Answer: A
Solution: Maintain addr for addressable expressions and place for computed values; use appropriate store/load ops.
About the Author
