Group A — Short Answer Questions (1 Mark Each)

Ans: A lexeme is the actual sequence of characters in the source program that matches the pattern for a token; it is the concrete text the scanner consumed. In int count; the lexemes are int, count and ; — here count is the lexeme matching the identifier pattern, for which the lexical analyser emits the token \( \langle id,\ ptr \rangle \).

Ans: A token is the pair \( \langle \text{token-name},\ \text{attribute-value} \rangle \) produced by the lexical analyser, where the token-name is an abstract symbol that the parser treats as a terminal and the (optional) attribute points to further information such as a symbol-table entry. For the lexeme count the token is \( \langle id,\ ptr \rangle \); tokens like ; or while need no attribute.

Ans: A pattern is the rule — normally a regular expression — that describes the form all lexemes of a given token may take. For the token id the pattern is \( letter\,(letter \mid digit)^{*} \); count is one lexeme matching that pattern, and \( \langle id,\ ptr \rangle \) is the token produced. So the pattern is the description, the lexeme is the matched text, and the token is the parser's symbol.

Ans: A cross compiler is a compiler that runs on one machine (the host) but generates target code for a different machine, i.e. host \( \ne \) target. It is essential for building software for embedded systems or a new architecture that cannot yet host a compiler — e.g. gcc executing on an x86 workstation and emitting ARM object code.

Ans: Bootstrapping is the technique of writing a compiler for a language in that same language: a small compiler for a subset \( S_0 \) is first written in an existing language (or machine code), and that compiler is then used to compile a fuller compiler written in \( S_0 \), the process repeating until the full language is supported. It is described using T-diagrams and is how compilers for C, Pascal and Go were built.

Ans: A symbol table is the compiler's data structure that records every identifier of the source program together with its attributes — type, scope/nesting level, storage class, size, and memory offset. It is created and filled during lexical and syntax analysis and consulted by semantic analysis, code generation and error reporting; it is usually a hash table supporting fast insert and lookup.

Ans: A compiler is split into an analysis part (front end) — lexical, syntax and semantic analysis plus intermediate-code generation, which breaks the source into pieces, builds the intermediate representation and symbol table and reports errors — and a synthesis part (back end) — code optimisation and target-code generation, which builds the target program from that intermediate representation. The split is what allows one front end to serve many machines.

Ans: A grammar is left recursive if some non-terminal \( A \) admits a derivation \( A \Rightarrow^{+} A\alpha \); the immediate case is \( A \to A\alpha \mid \beta \). It makes a top-down (recursive-descent / LL) parser recurse for ever without consuming input, so it must be eliminated by rewriting as \( A \to \beta A' \), \( A' \to \alpha A' \mid \epsilon \). Bottom-up LR parsers, in contrast, handle left recursion happily.

Ans: Left factoring is the grammar transformation that postpones a parsing decision when two or more alternatives share a common prefix: \( A \to \alpha\beta_1 \mid \alpha\beta_2 \) is rewritten as \( A \to \alpha A' \), \( A' \to \beta_1 \mid \beta_2 \). It removes the non-determinism of choice so that one lookahead token suffices for LL(1) — whereas removing left recursion cures infinite recursion; the two transformations fix different defects and both may be needed.

Ans: A grammar is ambiguous if it produces more than one parse tree — equivalently more than one leftmost (or rightmost) derivation — for some sentence of its language. For \( E \to E+E \mid E*E \mid id \), the string id+id*id has two distinct parse trees. An ambiguous grammar is neither LL(1) nor LR(k) for any \( k \), and is disambiguated by precedence/associativity rules or by rewriting.

Ans: A parse tree (concrete syntax tree) is a tree depicting a derivation: its root is the start symbol, each interior node is a non-terminal whose children are the symbols of the right side of the production applied, and the leaves read left to right give the input string (the yield). It records every grammar symbol, including punctuation and single-child chains, unlike a syntax tree.

Ans: An abstract syntax tree is a condensed parse tree in which operators (or language constructs) label the interior nodes and their operands are the children, while symbols needed only for parsing — parentheses, commas, chains of single productions — are dropped. For a = b + c the AST is = with children a and the subtree +(b, c); a DAG goes one step further by sharing identical subtrees.

Ans: A shift-reduce conflict occurs when, in some LR state with a given lookahead, the parsing table allows both shifting the next input symbol and reducing by a completed production, so the action is not unique. The standard example is the dangling-else grammar \( S \to \textbf{if } E \textbf{ then } S \mid \textbf{if } E \textbf{ then } S \textbf{ else } S \) on lookahead else; Yacc resolves such conflicts in favour of shift.

Ans: A reduce-reduce conflict occurs when two or more different productions are simultaneously complete in an LR state and both are legal reductions on the same lookahead, so the parser cannot tell which production to reduce by. Unlike a shift-reduce conflict it almost always signals a genuinely badly designed or ambiguous grammar; LALR(1) can introduce reduce-reduce conflicts by merging CLR(1) states with the same core.

Ans: LL(1) parsing is table-driven predictive top-down parsing: the first L means the input is scanned Left to right, the second L means a Leftmost derivation is produced, and the 1 means one lookahead token is used, with no backtracking. A grammar is LL(1) iff for every pair \( A \to \alpha \mid \beta \), \( FIRST(\alpha) \cap FIRST(\beta) = \emptyset \) and, if \( \beta \Rightarrow^{*} \epsilon \), \( FIRST(\alpha) \cap FOLLOW(A) = \emptyset \) — so it must be free of left recursion and left factored. Because it must commit to a production before seeing the right side, every LL(1) grammar is LR(1) but not conversely.

Ans: For a grammar symbol string \( \alpha \), \( FIRST(\alpha) \) is the set of terminals that can begin some string derived from \( \alpha \), and it also contains \( \epsilon \) if \( \alpha \Rightarrow^{*} \epsilon \). A predictive parser uses it to choose a production: for \( A \to \alpha \), the entry \( M[A,\ a] \) is filled for every \( a \in FIRST(\alpha) \) — so \( FIRST \) looks at what a production can start with, unlike \( FOLLOW \).

Ans: For a non-terminal \( A \), \( FOLLOW(A) \) is the set of terminals that can appear immediately to the right of \( A \) in some sentential form, i.e. all \( a \) with \( S \Rightarrow^{*} \alpha A a \beta \); the endmarker \( \$ \) is always in \( FOLLOW(S) \) for the start symbol \( S \). It is what decides when to apply an \( \epsilon \)-production: if \( A \to \alpha \) and \( \epsilon \in FIRST(\alpha) \), the entry \( M[A,\ b] \) is filled for every \( b \in FOLLOW(A) \).

Ans: \( \$ \) is the endmarker, an artificial symbol appended to the right end of the input to mark end-of-file; it is also pushed at the bottom of the parser stack initially. It is used as a lookahead column in the LL(1)/LR parsing table and always belongs to \( FOLLOW(S) \) for the start symbol \( S \); the parser accepts when the input has reduced to \( S \) with \( \$ \) as lookahead.

Ans: An \( \epsilon \)-production is a production of the form \( A \to \epsilon \), which derives the empty string and makes \( A \) nullable. It lets a non-terminal be matched by no input at all; in LL(1) table construction, when \( \epsilon \in FIRST(\alpha) \) for \( A \to \alpha \), the entry \( M[A, b] \) is filled for every \( b \in FOLLOW(A) \) (including \( \$ \)).

Ans: A handle of a right-sentential form \( \gamma \) is a substring \( \beta \) together with a production \( A \to \beta \) such that replacing \( \beta \) by \( A \) yields the previous right-sentential form of a rightmost derivation, i.e. \( S \Rightarrow_{rm}^{*} \alpha A w \Rightarrow_{rm} \alpha\beta w \) with \( w \) a string of terminals. Bottom-up parsing is exactly repeated handle pruning, and the handle always appears on top of the stack, which is why a stack suffices.

Ans: Shift is the LR action that pushes the next input symbol (together with the new state number from the ACTION table) onto the parser stack and advances the input pointer. It is chosen when the symbols on the stack do not yet form a complete handle, so more input is needed before a reduction can be made.

Ans: Reduce is the LR action taken when the right side \( \beta \) of a production \( A \to \beta \) — the handle — sits on top of the stack: the parser pops \( 2|\beta| \) entries (\( |\beta| \) symbols with their states), pushes \( A \), and moves to state \( GOTO[s, A] \) where \( s \) is the exposed state. Each reduction is one step of the rightmost derivation traced in reverse.

Ans: Accept is the action that announces a successful parse and halts the parser. In an LR parser built for the augmented grammar it is taken in the state containing the item \( S' \to S\ \cdot \) when the lookahead is \( \$ \) — that is, the whole input has been reduced to the start symbol with nothing left to read.

Ans: Yacc (Yet Another Compiler-Compiler) is the UNIX parser generator: from a .y specification — declarations, translation rules (a context-free grammar with embedded C semantic actions), and support routines, separated by %% — it produces y.tab.c containing the driver yyparse(). The parser it builds is LALR(1), and it calls yylex(), normally generated by Lex, for tokens.

Ans: Lex (GNU version Flex) is a lexical-analyser generator: from a .l specification of regular-expression patterns with C actions it produces lex.yy.c containing yylex(), a DFA obtained internally by Thompson's construction followed by subset construction. Ties are resolved by the longest-match rule and, for equal lengths, by the rule listed first.

Ans: A synthesized attribute of a node \( N \) is one whose value is computed only from the attributes of \( N \)'s children (and of \( N \) itself), so information flows up the parse tree — e.g. \( E \to E_1 + T\ \{\ E.val := E_1.val + T.val\ \} \). Terminals can carry only synthesized attributes, supplied by the lexical analyser, and such attributes can always be evaluated in a bottom-up pass.

Ans: An inherited attribute of a node \( N \) is one whose value is computed from attributes of \( N \)'s parent and/or its siblings, so information flows down and across the tree — e.g. \( D \to T\ L\ \{\ L.type := T.type\ \} \), which passes a declared type to a list of identifiers. It is evaluated in a depth-first, left-to-right traversal rather than purely bottom-up.

Ans: An S-attributed syntax-directed definition is one that uses only synthesized attributes. Every semantic action can therefore be placed at the right end of its production and evaluated bottom-up as the parser reduces, which is why S-attributed definitions can be implemented directly on an LR parser in a single pass with no explicit tree.

Ans: An L-attributed syntax-directed definition allows synthesized attributes plus inherited attributes restricted so that, in a production \( A \to X_1 X_2 \ldots X_n \), an inherited attribute of \( X_j \) depends only on inherited attributes of \( A \) and on attributes of \( X_1, \ldots, X_{j-1} \) — i.e. only on symbols to its left. Such definitions are evaluable in one depth-first left-to-right pass, so they suit predictive/LL translation; every S-attributed SDD is L-attributed, but not conversely.

Ans: Three-address code is a linearised intermediate representation in which every instruction has at most one operator on the right-hand side and at most three addresses, in the general form \( x := y\ op\ z \). Nested expressions are broken up using compiler-generated temporaries: \( a := b + c * d \) becomes \( t_1 := c * d;\ t_2 := b + t_1;\ a := t_2 \).

Ans: A quadruple represents one three-address instruction as a record of four fields — op, arg1, arg2, result; e.g. \( t_1 := b * c \) is (*, b, c, t1). Because the result temporary is named explicitly, instructions may be moved or reordered freely during optimisation, at the cost of storing all those temporary names.

Ans: A triple represents an instruction with only three fields — op, arg1, arg2 — the result is not named; instead the instruction is referred to by its position (index) in the triple array. This saves the space of temporary names, but since operands are encoded as triple positions, moving or reordering an instruction invalidates those references, making optimisation awkward.

Ans: An indirect triple representation keeps the triples in one array plus a separate list of pointers to them giving the execution order. Optimisation reorders or deletes entries in the pointer list only, leaving the triples and their indices untouched — thus retaining the space economy of triples while regaining the reorderability of quadruples.

Ans: Backpatching is the technique that lets jump code be generated in a single pass when a jump's target address is not yet known: the instruction is emitted with the target left blank and its index is kept on a list built by \( makelist() \) and \( merge() \); when the label's address becomes known, \( backpatch(list,\ addr) \) fills that address into every instruction on the list. It is used for boolean expressions and control flow (if, while, short-circuit &&/||).

Ans: An activation record (stack frame) is the block of memory pushed on the control stack for one activation of a procedure. It typically holds, from top down: the returned value, the actual parameters, an optional control link (to the caller's record) and access/static link (for non-local data), saved machine status including the return address and registers, local data, and temporaries.

Ans: A display is an array \( d \) in which \( d[i] \) points to the most recent activation record of the procedure at nesting depth \( i \). It gives constant-time access to non-local variables — the variable is found at a fixed offset in \( d[i] \) — whereas the static-link chain requires walking \( n_{use} - n_{decl} \) links; the cost is saving and restoring display entries on call and return.

Ans: A basic block is a maximal sequence of consecutive three-address instructions with a single entry (its first instruction, the leader) and a single exit (its last instruction): control can enter only at the beginning and, apart from the last instruction, no instruction is a jump or a jump target. Hence if the first instruction executes, all of them execute in order.

Ans: A control flow graph (flow graph) is a directed graph whose nodes are the basic blocks of a procedure, with an edge \( B_1 \to B_2 \) whenever control may pass from the last instruction of \( B_1 \) to the first of \( B_2 \) — either by a jump to \( B_2 \)'s leader or by falling through. Distinguished ENTRY and EXIT nodes are added; the flow graph is the substrate for global data-flow analysis and loop detection.

Ans: A leader is the first instruction of a basic block. The leaders are found by three rules: (i) the first instruction of the intermediate code is a leader; (ii) any instruction that is the target of a conditional or unconditional jump is a leader; (iii) any instruction immediately following a jump is a leader. Each basic block then consists of a leader and all instructions up to, but not including, the next leader.

Ans: A DAG is a directed acyclic graph built for a basic block in which leaves are the initial values of identifiers/constants, interior nodes are operators, and every node carries the identifiers whose value it holds. Identical subexpressions are represented by a single shared node rather than duplicated as in a syntax tree, which directly exposes common subexpressions, dead code and reordering opportunities for local optimisation.

Ans: Common subexpression elimination replaces a recomputation of an expression \( E \) by a reference to its previously computed value, provided \( E \) was already evaluated on every path to this point and none of its operands has been modified since (i.e. \( E \) is available). Thus \( t_1 := b*c; \ldots; t_2 := b*c \) becomes \( t_2 := t_1 \); it is done locally with a DAG/value numbering and globally with available-expressions data-flow analysis.

Ans: Dead code elimination removes instructions whose computed value is never subsequently used — the assigned variable is dead at that point — as well as code that is unreachable. For instance \( x := y + z \) is deleted if \( x \) is never live afterwards, and the body of if (false) { ... } is unreachable. Liveness is established by live-variable (backward) data-flow analysis.

Ans: Constant folding is the compile-time evaluation of expressions whose operands are all known constants, replacing the expression by its computed value — \( x := 3 * 4 + 2 \) becomes \( x := 14 \). It saves run-time work and code space, and is usually enabled and re-triggered by constant propagation.

Ans: Copy propagation replaces later uses of \( x \) by \( y \) after a copy statement \( x := y \), provided that copy is the only definition of \( x \) reaching that use and neither \( x \) nor \( y \) is redefined in between. It does not by itself make the code faster; its value is that it renders \( x \) dead, so dead-code elimination can then delete the copy statement altogether.

Ans: Loop invariant code motion hoists a computation whose operands do not change anywhere inside the loop out of the loop body and into its pre-header, so it is evaluated once instead of once per iteration. The move is legal only if the instruction's block dominates all loop exits (or the variable is dead on exit) and the target is not assigned elsewhere in the loop.

Ans: Strength reduction replaces an expensive operation with an equivalent cheaper one — classically a multiplication by a repeated addition on an induction variable, so that \( t := i * 4 \) inside a loop becomes \( t := t + 4 \) per iteration. Machine-level instances include \( x * 2 \to x + x \) or \( x \ll 1 \), and \( x / 2 \to x \gg 1 \).

Ans: Peephole optimisation is a simple, local improvement technique that slides a small window — the peephole — of a few consecutive target or intermediate instructions and replaces the sequence in it by a shorter or faster equivalent, repeating passes until no more improvements occur. Typical transformations are removing redundant load/store pairs and unreachable code, flow-of-control optimisation (jump to a jump), algebraic simplification (\( x := x + 0 \)), strength reduction and use of machine idioms.

Ans: Register allocation is the phase that decides which program values are held in the machine's limited set of registers at each point in the program, while register assignment chooses the specific physical register for each. The goal is to minimise memory loads and stores; it is normally solved as graph colouring of the interference graph, and the general problem is NP-complete.

Ans: A register interference graph is an undirected graph with one node per live range (variable/temporary) and an edge between two nodes whose live ranges overlap, meaning both are simultaneously live and therefore cannot share a register. Finding a legal allocation is then \( k \)-colouring this graph, where \( k \) is the number of available registers; nodes that cannot be coloured are spilled to memory.

Ans: Spilling is what a register allocator does when registers run short: the value in a register is stored to a location in the activation record and reloaded just before its next use, freeing that register in between. In graph-colouring allocation, a node that cannot be given one of the \( k \) colours is chosen for spilling by a cost heuristic (spill cost / degree), and the graph is rebuilt and recoloured.

Ans: Static Single Assignment form is an intermediate representation in which every variable is assigned exactly once: each assignment creates a new subscripted name (\( x_1, x_2, \ldots \)), and at control-flow join points a \( \phi \)-function such as \( x_3 := \phi(x_1, x_2) \) selects the value that arrived along the executed path. Because every use has a unique definition, def-use information is explicit, which greatly simplifies constant propagation, dead-code elimination and register allocation.

Ans: In a flow graph, a node \( d \) dominates node \( n \) (written \( d\ dom\ n \)) if every path from the ENTRY node to \( n \) passes through \( d \); every node dominates itself, and the closest strict dominator of \( n \) is its immediate dominator \( idom(n) \). Dominators identify natural loops: a back edge \( n \to d \) is one whose head \( d \) dominates its tail \( n \).