Compiler Design exam preparation.
Practice questions for every unit in the style of the R23 end exam, a model answer for each, and a one-page revision summary. Built on the official syllabus units.
- Practice questions in the exam's style
- Drafted with AI and checked by a second AI pass. Doubtful points were verified against public sources. Report a mistake
- Units
- 5
- Questions
- 60
- 2-mark
- 30
- 10-mark
- 30
- Done
- Checked on
Exam guide
Paper pattern
Semester-end theory paper, 70 marks, from the JNTUK B.Tech R23 Regulations, end-examination pattern for theory subjects.
- Question 1 · 20 marksTen compulsory short-answer questions of 2 marks each (two from every unit).
- Questions 2 to 6 · 50 marksFive either/or questions of 10 marks each, one per unit. You answer one of the two in each.
- The semester-end examination carries 70 marks; internal assessment carries 30.
- Mid-semester examinations are separate: a 20-minute objective paper (10 marks) and a 90-minute subjective paper with three either/or questions of 10 marks (condensed to 15 marks).
- The regulations text does not state the length of the end examination. Use the duration printed on your hall ticket or question paper.
How to split your time
This plan assumes a 3-hour paper. If yours is different, keep the same proportions. Marks per minute stay roughly even across Question 1 and the 10-mark answers.
- 10 minRead the paper and choose one option in each either/or question
- 30 minQuestion 1: ten short answers (about 3 minutes each)
- 130 minQuestions 2 to 6: one 10-mark answer per unit (about 26 minutes each)
- 10 minFinal check of numbering, calculations and diagrams
Study tips for Compiler Design
- Practise FIRST and FOLLOW on several grammars until you can compute them without mistakes, because LL(1) and SLR tables are built directly from them.
- Build the LR(0) item sets for one small grammar, then fill its SLR, CLR and LALR tables, and parse one input string with each, writing the stack, input and action at every step.
- For intermediate code, write the three-address code, quadruples, triples and indirect triples for the same expression, and draw its syntax tree and DAG side by side.
- For optimization, split a short program into basic blocks, draw its flow graph, and compute reaching definitions or live variables by iterating until no set changes.
Lexical Analysis and Introduction to Syntax Analysis
Syllabus: Language processors; Structure of a compiler; The role of the lexical analyzer; Bootstrapping; Input buffering; Specification of tokens; Recognition of tokens; The lexical analyzer generator LEX; Finite automata, and from regular expressions to finite automata; Design of a lexical analyzer generator; The role of the parser and context-free grammars; Derivations, parse trees and ambiguity; Left recursion and left factoring
One-page revision summary
- A language-processing system chains a preprocessor (macros, file inclusion), the compiler, an assembler that produces relocatable machine code, and a linker and loader that join object files and libraries and place the program in memory.
- A hybrid processor such as Java first compiles source into bytecode, which a virtual machine then interprets or compiles just in time.
- A compiler is split into an analysis front end that builds the intermediate code and symbol table, and a synthesis back end that builds the target program from them.
- A pass is one reading of the program or its intermediate form; several phases can be grouped into one pass.
- The lexical analyzer reads characters, forms lexemes, returns tokens on each getNextToken call, fills the symbol table, removes white space and comments, and tracks line numbers.
- In T-diagram terms, compiling a compiler written in L with an existing L compiler on machine M gives a compiler that runs on M; a cross compiler runs on one machine but produces code for another.
- Input buffering uses two N-character buffers, the pointers lexemeBegin and forward, and an eof sentinel at the end of each buffer so that most characters need only one test.
- In a regular expression, * has the highest precedence, then concatenation, then |, and all three are left associative.
- A transition diagram has one start state and final states that return tokens; a final state marked * retracts forward by one character.
- Keywords are recognised as identifiers and separated by a lookup in the symbol table, where they are preloaded as reserved words.
- LEX translates lex.l into lex.yy.c, which the C compiler turns into a.out; yytext holds the lexeme, yyleng its length and yylval its attribute.
- An NFA may have ε-moves and several moves on one symbol, while a DFA has exactly one move per state and symbol; every NFA has an equivalent DFA.
- A lexical analyzer generator combines the NFAs of all patterns under one new start state, converts them into one DFA, and labels each final DFA state with the first-listed pattern it contains.
- Parsers are universal, top-down or bottom-up; syntax errors are handled by panic mode, phrase-level recovery, error productions or global correction.
- A sentential form is any string of grammar symbols derivable from the start symbol; a sentence is a sentential form made only of terminals.
- Indirect left recursion, as in S → A a | b, A → S d | c, is removed by substituting S into A, giving A → A a d | b d | c, and then A → b d A' | c A', A' → a d A' | ε.
Learn these by heart
- Left recursion removal: A → Aα | β becomes A → βA', A' → αA' | ε.
- Left factoring: A → αβ1 | αβ2 becomes A → αA', A' → β1 | β2.
- Subset construction: start state = ε-closure(s0); each DFA move is ε-closure(move(S, a)).
- A context-free grammar is G = (V, T, P, S): nonterminals, terminals, productions and start symbol.
- A grammar is ambiguous when some sentence has two or more parse trees, or two or more leftmost derivations.
- LEX conflict rules: prefer the longest matching prefix, then the pattern listed first.
- Token = <token name, attribute value>; pattern = rule for the lexemes; lexeme = matched character sequence.
2-mark questions
1 Distinguish between a compiler and an interpreter. 2 marks
A compiler translates the whole source program into an equivalent target program before it runs; the target then executes fast on its own, and errors are reported after the whole program is analysed. An interpreter executes the source statement by statement without producing a target program, so it is slower but gives better diagnostics, stopping at the faulty statement.
2 What is bootstrapping in compiler construction? 2 marks
Bootstrapping is writing a compiler for a language L in L itself. A small compiler for a simple subset of L is first written in an existing language; it compiles the full compiler, written in that subset, which can then compile itself. The steps are shown with T-diagrams, each giving a source language, a target language and an implementation language.
3 Define token, pattern and lexeme with an example. 2 marks
A token is a pair of a token name and an optional attribute value, such as <id, pointer to symbol-table entry>. A pattern describes the form of a token's lexemes, for example a letter followed by letters or digits. A lexeme is the character sequence in the source that matches a pattern, such as count in count = 10.
4 Define a context-free grammar and name its four components. 2 marks
A context-free grammar is G = (V, T, P, S): V is a finite set of nonterminals (syntactic variables), T a finite set of terminals (tokens), P a set of productions A → α with A in V and α in (V ∪ T)*, and S in V the start symbol. Example: E → E + E | id.
5 Eliminate left recursion from the grammar E → E + T | T. 2 marks
The rule A → Aα | β becomes A → βA', A' → αA' | ε. With A = E, α = + T and β = T, this gives E → T E', E' → + T E' | ε. The language is unchanged, but the grammar is no longer left recursive.
6 Left factor the grammar S → i E t S | i E t S e S | a, E → b. 2 marks
The first two S-alternatives share the prefix i E t S, so it is factored out and the choice is postponed: S → i E t S S' | a, S' → e S | ε, E → b. A predictive parser can now expand S after seeing only i, and chooses between e S and ε for S' later.
10-mark questions
1 Explain the phases of a compiler with a neat diagram. Show the output of each phase for the statement cost = price + qty * 2, where all three identifiers are of type float. 10 marks
A compiler translates a source program into an equivalent target program. Its work is divided into an analysis part (the front end), which breaks the source into its parts, checks them and builds an intermediate form and the symbol table, and a synthesis part (the back end), which builds the target program from them. Each part is a sequence of phases, and each phase passes its output to the next.
1. Lexical analyzer: it groups characters into lexemes and produces tokens. For the statement it gives <id,1> <=> <id,2> <+> <id,3> <*> <num,2>, where cost, price and qty are entries 1, 2 and 3 of the symbol table. 2. Syntax analyzer: it checks the tokens against the grammar and builds a syntax tree. Because * binds tighter than +, the tree is =(id1, +(id2, *(id3, 2))). 3. Semantic analyzer: it checks types using the tree and the symbol table. id3 is float but 2 is an integer, so it inserts the conversion inttofloat(2). 4. Intermediate code generator: the tree becomes three-address code:
t1 = inttofloat(2)
t2 = id3 * t1
t3 = id2 + t2
id1 = t35. Code optimizer: the conversion is done once at compile time, giving 2.0, and the copy through t3 is removed:
t1 = id3 * 2.0
id1 = id2 + t16. Code generator: registers are assigned and machine instructions (all floating-point operations) are produced:
LD R1, id3
MUL R1, R1, #2.0
LD R2, id2
ADD R2, R2, R1
ST id1, R2Two components serve all six phases. The symbol-table manager keeps a record for each identifier with its attributes, such as type, storage and scope, and lets every phase find it quickly. The error handler receives the errors that any phase detects, reports them with their position and lets compilation continue where possible.
In conclusion, the front end depends mainly on the source language and the back end mainly on the target machine, so one front end can be joined to several back ends through a common intermediate code. Several phases may also be grouped into a single pass over the input.
2 Explain the role of the lexical analyzer and its interaction with the parser. Describe the input buffering scheme that uses buffer pairs and sentinels. 10 marks
The lexical analyzer, or scanner, is the first phase of a compiler. It reads the characters of the source program, groups them into lexemes and gives the parser one token for each lexeme; the parser in turn passes its parse tree on to semantic analysis.
Role of the lexical analyzer:
- It works on demand: each getNextToken call from the parser makes it read characters until the next lexeme is complete, and it returns that lexeme's token, such as <id, pointer to entry> or <num, 60>.
- It enters identifiers into the symbol table and passes the entry as the token's attribute; the parser and later phases use the same table.
- It removes white space, newlines and comments, which the parser does not need, and counts newlines so that errors can be reported with line numbers.
- It detects lexical errors, where no pattern matches any prefix of the remaining input. The simplest recovery is panic mode, deleting characters until a token can begin; inserting, deleting or replacing a single character, or swapping two adjacent characters, are other repairs.
A separate scanner keeps the grammar simpler, allows fast special-purpose buffering, and confines input-device details to one place.
Input buffering: 1. Reading one character per system call is slow, and the scanner often looks past a lexeme before deciding (> or >=). So it uses two buffers of N characters each (N is the size of a disk block, such as 4096), each filled by one read. 2. Two pointers mark the text: lexemeBegin at the start of the current lexeme, and forward, which moves ahead until a pattern matches. Once the token is formed, lexemeBegin moves to the character after the lexeme. 3. When forward reaches the end of one buffer, the other buffer is reloaded and forward moves to its start. This is safe as long as a lexeme plus its look-ahead never exceeds N characters. 4. Without sentinels, every advance of forward makes two tests: has it reached a buffer end, and which character was read. A sentinel, the special character eof, placed at the end of each buffer leaves one test in the common case:
c = *forward; forward = forward + 1
if c == eof:
if forward is past the end of buffer 1:
reload buffer 2
forward = start of buffer 2
elif forward is past the end of buffer 2:
reload buffer 1
forward = start of buffer 1
else:
end of input: stop scanningAn eof anywhere other than a buffer end marks the real end of the input.
In conclusion, the lexical analyzer hides character-level detail from the parser, and buffer pairs with sentinels make scanning and look-ahead cheap.
3 Explain how tokens are specified with regular expressions and regular definitions, and how they are recognized with transition diagrams. Draw the transition diagram for relational operators. 10 marks
Tokens are specified by patterns written as regular expressions, and the lexical analyzer recognizes them by simulating transition diagrams built from those patterns.
Specification of tokens: 1. An alphabet Σ is a finite set of symbols, a string is a finite sequence of symbols, and a language is any set of strings over Σ. Tokens use union L ∪ M, concatenation LM, Kleene closure L* (zero or more) and positive closure L+ (one or more). 2. Regular expressions: ε and each symbol a are regular expressions; if r and s are, so are r|s, rs, r* and (r). Precedence is * highest, then concatenation, then |, all left associative. 3. A regular definition names expressions so that later lines can use them; r? means zero or one r:
letter -> A | ... | Z | a | ... | z | _
digit -> 0 | 1 | ... | 9
id -> letter (letter | digit)*
digits -> digit digit*
number -> digits (. digits)? (E (+|-)? digits)?
relop -> < | <= | = | <> | > | >=
ws -> (blank | tab | newline)+So x1 and _tmp are ids, and 42, 3.14 and 1.5E-3 are numbers, but 3. is not.
Recognition of tokens: 4. Each pattern becomes a transition diagram: states drawn as circles, edges labelled with characters, one start state, and final (accepting) states that return a token. A final state marked * means the last character read is not part of the lexeme, so forward is retracted by one. 5. The diagram for relop (its edge labels less than and greater than stand for the characters < and >):
From the start state 0, < leads to 1, where = returns LE, > returns NE and any other character returns LT after retracting. = returns EQ at once. > leads to 6, where = returns GE and any other character returns GT after retracting. 6. For x<y, after x the scanner reads <, then y. y is neither = nor >, so it reaches state 4*, retracts and returns <relop, LT>. 7. Keywords look like identifiers, so they are entered in the symbol table in advance as reserved words. When the id diagram accepts a lexeme, a table lookup decides whether it is a keyword or an identifier. 8. When ws is matched, no token is returned and scanning restarts.
In conclusion, regular definitions specify every token precisely, and transition diagrams turn them directly into a scanner.
4 Explain the structure of a LEX program with an example. How does a lexical analyzer generator turn LEX patterns into a working scanner? Illustrate with the rules for the keyword if and identifiers. 10 marks
LEX generates a lexical analyzer from a specification of patterns (regular expressions) and actions (C code); the tool, not the designer, builds the automaton.
Using LEX: the LEX compiler translates the specification lex.l into the C program lex.yy.c; the C compiler turns that into a.out, the lexical analyzer, which reads the input stream and returns a sequence of tokens.
Structure of a LEX program: three parts separated by %%.
%{
#define IF 1
#define ID 2
%}
letter [a-z]
%%
[ \t\n]+ { /* skip white space */ }
if { return IF; }
{letter}+ { yylval = installID(); return ID; }
%%
int installID() { /* add yytext to symbol table */ }1. Declarations: C declarations between %{ and %}, and regular definitions such as letter. 2. Translation rules: each line is a pattern and an action that runs when the pattern matches. 3. Auxiliary functions: C functions, such as installID, used by the actions. yytext points to the lexeme, yyleng is its length, and yylval carries the attribute.
Design of the lexical analyzer generator: 1. Each pattern is converted into an NFA, for example by Thompson's construction. Leaving out white space, the NFA for if is 1 →i 2 →f 3, and the NFA for {letter}+ is 4 →letter 5 with a letter loop on 5. 2. A new start state 0 is joined by ε-edges to states 1 and 4, giving one combined NFA in which each accepting state remembers its pattern: 3 for IF and 5 for ID. 3. The subset construction turns the combined NFA into a DFA:
A = {0, 1, 4} goes to B = {2, 5} on i and to C = {5} on any other letter. B goes to D = {3, 5} on f and to C on any other letter, and C and D go to C on every letter. B and C hold only accepting state 5, so they are final for ID. D contains both 3 and 5; if is listed before {letter}+, so D is final for IF. 4. The generated analyzer is a fixed driver plus this transition table and the actions. Starting at lexemeBegin, forward moves through the DFA while the driver remembers the last final state passed. When no move is possible, forward is retracted to that point and the matching action runs. 5. On if x, the blank stops the driver in D, so it returns IF; on iffy it passes D, continues to C and returns ID for all four letters.
In conclusion, a LEX-generated scanner settles conflicts by two rules: take the longest matching prefix, and among matches of equal length, take the pattern listed first.
5 Construct an NFA for the regular expression (a|b)*abb using Thompson's construction, and convert it into a DFA using the subset construction. 10 marks
Thompson's construction builds an NFA for a regular expression by induction on its structure, and the subset construction turns that NFA into a DFA whose states are sets of NFA states.
Thompson's rules:
- For ε or a symbol a: a new start state i and a new accepting state f, with one edge i → f labelled ε or a.
- For s|t: a new start state with ε-edges to the starts of N(s) and N(t), and ε-edges from their accepting states to a new accepting state.
- For st: the accepting state of N(s) is merged with the start state of N(t).
- For s*: new states i and f, with ε-edges from i to the start of N(s) and to f, and from the accepting state of N(s) back to its start and on to f.
For (a|b)*abb these rules give an NFA with 11 states, 0 to 10, start state 0 and final state 10:
Subset construction: 1. The DFA start state is A = ε-closure(0) = {0, 1, 2, 4, 7}. 2. For each unmarked DFA state S and each symbol x, U = ε-closure(move(S, x)); a new U becomes an unmarked DFA state. 3. move(A, a) = {3, 8}, whose closure is B = {1, 2, 3, 4, 6, 7, 8}. move(A, b) = {5}, giving C = {1, 2, 4, 5, 6, 7}. 4. move(B, a) = {3, 8} gives B again; move(B, b) = {5, 9} gives D = {1, 2, 4, 5, 6, 7, 9}. 5. From C, a gives B and b gives C. 6. From D, a gives B; move(D, b) = {5, 10} gives E = {1, 2, 4, 5, 6, 7, 10}. 7. From E, a gives B and b gives C. No new state appears, so the construction stops.
DFA state on a on b
→A B C
B B D
C B C
D B E
E (final) B CE is the only final state, because only E contains NFA state 10. For example, babb moves A → C → B → D → E and is accepted, while abba moves A → B → D → E → B and is rejected.
In conclusion, the DFA has five states. A and C are both non-final with the same moves, so minimization merges them, leaving a four-state DFA for the strings over {a, b} that end in abb.
6 Explain the role of the parser. Using derivations and parse trees, show that the grammar E → E + E | E * E | id is ambiguous, and rewrite it as an unambiguous grammar without left recursion. 10 marks
The parser takes tokens from the lexical analyzer, checks that the token string can be generated by the grammar, a context-free grammar G = (V, T, P, S), and builds a parse tree for the later phases. It also reports and recovers from syntax errors.
Derivations and parse trees: 1. Each derivation step replaces one nonterminal by the body of one of its productions. A leftmost derivation always replaces the leftmost nonterminal; a rightmost derivation, the rightmost. 2. A parse tree shows a derivation without its order: the root is the start symbol, interior nodes are nonterminals, leaves are terminals or ε, and a node's children form the body of the production used. Each parse tree has exactly one leftmost and one rightmost derivation. 3. A grammar is ambiguous if some sentence has more than one parse tree (equivalently, more than one leftmost derivation).
For id + id * id, the grammar E → E + E | E * E | id has two leftmost derivations:
LMD 1: E => E + E => id + E
=> id + E * E => id + id * E
=> id + id * id
LMD 2: E => E * E => E + E * E
=> id + E * E => id + id * E
=> id + id * idThe rightmost derivation for the first tree is E => E + E => E + E * E => E + E * id => E + id * id => id + id * id. The two parse trees are:
Tree 1 Tree 2
E E
/ | \ / | \
E + E E * E
| /|\ /|\ |
id E * E E + E id
| | | |
id id id idTree 1 multiplies first; Tree 2 adds first, against the usual precedence, so the grammar is ambiguous.
Removing the ambiguity: one nonterminal per precedence level, with left associativity, gives E → E + T | T, T → T * F | F, F → id. Now id + id * id has only one parse tree, with * lower than +:
Removing left recursion with A → Aα | β ⇒ A → βA', A' → αA' | ε gives:
E -> T E'
E' -> + T E' | ε
T -> F T'
T' -> * F T' | ε
F -> idIn conclusion, precedence and associativity built into the grammar remove the ambiguity, and removing left recursion then suits it to top-down parsing.
Top-Down and Bottom-Up Parsing
Syllabus: Preprocessing steps of top-down parsing; Backtracking and recursive-descent parsing; LL(1) grammars; Non-recursive predictive parsing; Error recovery in predictive parsing; Bottom-up parsing, and LR versus LL parsers; Types of LR parsers; Shift-reduce parsing; SLR parsers and construction of SLR parsing tables; Construction of CLR(1) and LALR parsing tables; Dangling-else ambiguity and handling ambiguous grammars with LR parsers; Error recovery in LR parsing
One-page revision summary
- Top-down parsing builds the parse tree from the root using a leftmost derivation; bottom-up parsing builds it from the leaves by reducing handles, which traces a rightmost derivation in reverse.
- Before top-down parsing, remove ambiguity, eliminate left recursion and left factor the grammar; these steps keep the language the same.
- Backtracking recursive descent tries the alternatives of a nonterminal in order and resets the input pointer when one fails, which wastes time and cannot handle left recursion.
- A predictive parser is a recursive-descent or table-driven parser that never backtracks, because one lookahead symbol selects the production.
- A grammar is LL(1) exactly when its predictive parsing table has no cell with two productions.
- The non-recursive predictive parser has an input buffer, a stack, the parsing table M[A, a] and a driver program, and outputs a leftmost derivation.
- Panic-mode recovery in predictive parsing uses synch entries from FOLLOW(A): skip the input on a blank cell, pop A on synch, and pop an unmatched terminal.
- Phrase-level recovery fills blank table cells with error routines that insert, delete or replace symbols; each routine must consume input or pop the stack so the parser cannot loop.
- A shift-reduce parser has four actions: shift, reduce, accept and error.
- A shift-reduce conflict means the parser cannot choose between shifting and reducing; a reduce-reduce conflict means two different reductions are possible.
- LL parsers predict a production before reading its body, while LR parsers reduce after seeing the whole body, so LR parsers accept left-recursive grammars and every LL(1) grammar is LR(1).
- All LR parsers share one driver with ACTION and GOTO tables; LR(0), SLR, LALR and CLR differ only in how the tables are built.
- SLR builds the LR(0) item sets and places reduce A → α only under the symbols in FOLLOW(A).
- CLR uses LR(1) items that carry a lookahead and reduces only on that lookahead; LALR merges CLR states with the same core.
- Merging states for LALR can create reduce-reduce conflicts but never a new shift-reduce conflict.
- The ambiguous grammar E → E + E | E * E | id has four shift-reduce conflicts in its SLR table; giving * higher precedence than + and making both left-associative resolves all four.
- The dangling-else conflict is resolved in favour of shift, so each else matches the nearest unmatched then.
- An LR parser detects an error at the first input symbol that cannot continue a valid prefix; LALR and SLR may reduce first, but never shift that symbol.
- In LR panic mode the parser pops states to one with a GOTO on a nonterminal A, discards input up to a symbol in FOLLOW(A), pushes GOTO(s, A) and resumes.
Learn these by heart
- Left recursion removal: A → Aα | β becomes A → βA', A' → αA' | ε.
- Left factoring: A → αβ1 | αβ2 becomes A → αA', A' → β1 | β2.
- FOLLOW rules: $ is in FOLLOW(start); for B → αAβ, add FIRST(β) − {ε} to FOLLOW(A); if β is empty or β ⇒* ε, add FOLLOW(B) to FOLLOW(A).
- LL(1) table: put A → α in M[A, a] for each a in FIRST(α); if α ⇒* ε, also for each a in FOLLOW(A).
- LR(1) closure: for [A → α.Bβ, a], add [B → .γ, b] for every b in FIRST(βa).
- Power of LR methods: LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ CLR(1); SLR and LALR tables have the same number of states.
2-mark questions
1 State the conditions under which a context-free grammar is LL(1). 2 marks
A grammar is LL(1) when its predictive parsing table has no cell with two productions. Equivalently, for every pair A → α | β:
- FIRST(α) and FIRST(β) are disjoint.
- At most one of α and β derives ε.
- If β ⇒* ε, FIRST(α) and FOLLOW(A) are disjoint.
Left-recursive and ambiguous grammars are never LL(1).
2 Give two differences between LL and LR parsers. 2 marks
- An LL parser works top-down and traces a leftmost derivation; an LR parser works bottom-up and traces a rightmost derivation in reverse.
- LL picks a production from the next input symbol before reading its body; LR reduces only after seeing the whole body and the lookahead, so it handles left recursion and a larger class (every LL(1) grammar is LR(1)).
3 Name the types of LR parsers and compare their power. 2 marks
The LR parsers are LR(0), SLR(1) (simple LR), LALR(1) (lookahead LR) and CLR(1) (canonical LR). All use the same driver and differ only in how the ACTION and GOTO tables are built. Their grammar classes nest as LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ CLR(1). SLR and LALR tables have equally many states; a CLR table can have many more.
4 What is a handle? What is handle pruning? 2 marks
A handle of a right-sentential form is a substring that matches a production body and whose reduction to the head gives the previous step of a rightmost derivation. With E → E + T | T, T → id, the handle of E + id is id. Handle pruning keeps reducing handles until only the start symbol remains, giving a rightmost derivation in reverse.
5 What is the dangling-else ambiguity, and how does an LR parser resolve it? 2 marks
In S → iEtS | iEtSeS | a, E → b (i = if, t = then, e = else), the string ibtibtaea has two parse trees: its e can match either t. The LR table gets a shift-reduce conflict on e between S → iEtS. and S → iEtS.eS. Choosing shift matches each else with the nearest unmatched then.
6 How does panic-mode error recovery work in an LR parser? 2 marks
On an error entry, the parser pops states until a state s with a GOTO on some nonterminal A, such as a statement or expression, is on top. It then discards input until a symbol in FOLLOW(A) appears, pushes GOTO(s, A) and resumes, as if a complete A had been parsed.
10-mark questions
1 What preprocessing does a grammar need before top-down parsing? Explain the elimination of immediate and indirect left recursion and left factoring, with examples. 10 marks
A top-down parser builds the parse tree from the root and must choose a production for the leftmost nonterminal by looking at the input. Three kinds of grammar stop it from choosing safely: ambiguous grammars, left-recursive grammars and grammars whose alternatives begin with the same symbols. So the given grammar is preprocessed first.
1. Remove ambiguity. Rewrite the grammar, for example with one nonterminal per precedence level, so that every sentence has exactly one parse tree.
2. Eliminate immediate left recursion. A production A → Aα makes the recursive-descent procedure for A call itself without consuming input, so it loops forever. The rule is:
A → Aα1 | Aα2 | β1 | β2
becomes
A → β1A' | β2A'
A' → α1A' | α2A' | εExample: E → E + T | T becomes E → TE', E' → +TE' | ε. Both grammars generate T, T + T, T + T + T and so on.
3. Eliminate indirect left recursion. Order the nonterminals A1, A2, …, An. For each Ai and each j < i, replace a production Ai → Ajγ by Ai → δ1γ | … | δkγ, where Aj → δ1 | … | δk are the current Aj-productions; then remove the immediate left recursion of Ai. The method assumes the grammar has no cycles (A ⇒+ A) and no ε-productions.
Example: S → Ab | c, A → Sd | a. Here S ⇒ Ab ⇒ Sdb, so S is left-recursive through A. With the order S, A, substitute the bodies of S into A → Sd:
A → Abd | cd | aThen remove the immediate left recursion of A:
S → Ab | c
A → cdA' | aA'
A' → bdA' | ε4. Left factoring. When two alternatives share a prefix, the parser cannot choose between them from one input symbol. Factor out the longest common prefix and delay the choice:
A → aBc | aBd | e
becomes
A → aBA' | e
A' → c | dAfter a and B are matched, the next input symbol selects A' → c or A' → d.
Conclusion: these steps do not change the language, only the shape of the parse trees. The grammar is then ready for computing FIRST and FOLLOW sets and building an LL(1) table, or for writing a recursive-descent parser that needs no backtracking.
2 Explain recursive-descent parsing with backtracking. Show how such a parser handles the input xpy for the grammar S → xAy, A → pq | p, and state the drawbacks of backtracking. 10 marks
A recursive-descent parser is a top-down parser made of one procedure for each nonterminal. The procedure for A chooses one of A's productions and matches its body from left to right: a terminal is compared with the current input symbol, and a nonterminal is handled by calling its procedure. When a chosen production fails and the parser must undo it and try another, the method is called backtracking.
Procedures for S → xAy, A → pq | p, where match(t) advances the input pointer ip if the current symbol is t and fails otherwise:
S(): match(x)
if A() = failure: error
match(y)
A(): save := ip
if match(p) and match(q):
return success // A → pq
ip := save // backtrack
if match(p):
return success // A → p
return failureTrace for the input xpy$:
1. S uses S → xAy. match(x) succeeds, so ip moves to p. 2. A saves ip (pointing at p) and tries A → pq. match(p) succeeds, so ip moves to y. 3. match(q) fails: q is expected but y is seen. The alternative A → pq is abandoned. 4. Backtrack: ip is reset to the saved position, so the current symbol is p again, and the partial subtree for A → pq is thrown away. 5. A tries A → p. match(p) succeeds and A returns success with ip at y. 6. Back in S, match(y) succeeds and ip reaches $. 7. S has matched its whole body and the input is used up, so xpy is accepted.
Drawbacks of backtracking:
- Work done on a failed alternative is thrown away, so in the worst case the time grows exponentially with the input length.
- Semantic actions done on the failed path, such as symbol-table entries, must be undone.
- Error reporting is poor, because a real error cannot be told apart from a wrong guess until every alternative has failed.
- A left-recursive production A → Aα makes the procedure call itself forever, so left recursion must be removed first.
Conclusion: backtracking is avoided by left factoring. With A → pA', A' → q | ε, A always matches p, and A' chooses by the next symbol: q selects A' → q, and y, which is in FOLLOW(A'), selects A' → ε. A recursive-descent parser that never backtracks in this way is a predictive parser.
3 For the grammar E → E + T | T, T → id | ( E ), remove left recursion, compute FIRST and FOLLOW sets, construct the LL(1) parsing table and show the moves of the parser on id + id. 10 marks
An LL(1) parser reads the input left to right, builds a leftmost derivation and uses one lookahead symbol. Its table is built from FIRST and FOLLOW sets of a grammar without left recursion.
Step 1. Remove left recursion. E → E + T | T becomes E → TE', E' → +TE' | ε:
1. E → TE'
2. E' → +TE'
3. E' → ε
4. T → id
5. T → (E)Step 2. FIRST sets.
- FIRST(T) = { id, ( } from productions 4 and 5.
- FIRST(E) = FIRST(T) = { id, ( }.
- FIRST(E') = { +, ε }.
Step 3. FOLLOW sets.
- FOLLOW(E) has $ (E is the start symbol) and ) from T → (E), so FOLLOW(E) = { ), $ }.
- E' ends the bodies of E and E', so FOLLOW(E') = FOLLOW(E) = { ), $ }.
- T is followed by E', so FOLLOW(T) has FIRST(E') − {ε} = { + }; because E' ⇒ ε, it also gets FOLLOW(E) and FOLLOW(E'). So FOLLOW(T) = { +, ), $ }.
Step 4. Table. Put A → α in M[A, a] for every a in FIRST(α); if α ⇒* ε, also for every a in FOLLOW(A).
id + ( ) $
E E→TE' E→TE'
E' E'→+TE' E'→ε E'→ε
T T→id T→(E)No cell holds two productions, so the grammar is LL(1).
Step 5. Parse id + id (stack top at the right).
Stack Input Action
$E id+id$ E→TE'
$E'T id+id$ T→id
$E'id id+id$ match id
$E' +id$ E'→+TE'
$E'T+ +id$ match +
$E'T id$ T→id
$E'id id$ match id
$E' $ E'→ε
$ $ acceptConclusion: the productions output in order give the leftmost derivation E ⇒ TE' ⇒ idE' ⇒ id+TE' ⇒ id+idE' ⇒ id+id, so id + id is accepted.
4 Explain the model and algorithm of a non-recursive predictive parser and its panic-mode error recovery. Illustrate with the grammar L → ER, R → ;ER | ε, E → id | num on the input id ; ; num. 10 marks
A non-recursive predictive parser does top-down parsing without recursive procedures. It keeps an explicit stack and is driven by an LL(1) parsing table.
Model.
- Input buffer: the string to be parsed, ending in $.
- Stack: grammar symbols, $ at the bottom and the start symbol on top at the beginning.
- Parsing table M[A, a]: for nonterminal A and input symbol a, a production or an error entry.
- Parsing program: reads the top symbol X and the current input a and decides the move. The output is the productions used, a leftmost derivation.
Algorithm. Repeat: 1. If X = a = $, accept. 2. If X is a terminal: if X = a, pop X and advance the input; otherwise it is an error. 3. If X is a nonterminal and M[X, a] = X → Y1Y2…Yk, pop X, push Yk, …, Y1 (Y1 on top) and output the production. 4. If M[X, a] is an error entry, call error recovery.
Panic-mode recovery. The parser skips input until a synchronizing token appears. For each nonterminal A, every symbol of FOLLOW(A) whose cell in row A is blank gets a synch entry. Then:
- If M[A, a] is blank, skip the input symbol a.
- If M[A, a] is synch, pop A, as if A had been seen.
- If a terminal on top does not match the input, pop it.
Example. FIRST(L) = FIRST(E) = { id, num }, FIRST(R) = { ;, ε }, FOLLOW(L) = FOLLOW(R) = { $ }, FOLLOW(E) = { ;, $ }.
id num ; $
L L→ER L→ER synch
R R→;ER R→ε
E E→id E→num synch synchTrace for id ; ; num (stack top at the right):
Stack Input Action
$L id;;num$ L→ER
$RE id;;num$ E→id
$Rid id;;num$ match id
$R ;;num$ R→;ER
$RE; ;;num$ match ;
$RE ;num$ error: synch, pop E
$R ;num$ R→;ER
$RE; ;num$ match ;
$RE num$ E→num
$Rnum num$ match num
$R $ R→ε
$ $ halt, 1 errorThe missing operand between the two semicolons is reported once and parsing goes on to the end. For the input id num ; id, M[R, num] is blank, so num would be skipped instead.
Phrase-level recovery is the other method: each blank cell holds a pointer to an error routine that may insert, delete or replace a symbol and print a message. Every routine must consume input or pop the stack, so the parser cannot loop.
Conclusion: the table drives both parsing and recovery, so errors are detected at the first wrong token and parsing continues.
5 Construct the SLR parsing table for the grammar E → E + T | T, T → T * F | F, F → id, and show the moves of the shift-reduce parser on id + id * id. 10 marks
Bottom-up parsing builds the parse tree from the leaves by shifting input onto a stack and reducing handles. An SLR parser is a shift-reduce parser whose table comes from the canonical collection of LR(0) items and the FOLLOW sets.
Step 1. Augment the grammar with E' → E and number the productions: 1. E → E+T, 2. E → T, 3. T → T*F, 4. T → F, 5. F → id.
Step 2. LR(0) item sets, found with closure and goto:
I0: E'→.E E→.E+T E→.T
T→.T*F T→.F F→.id
I1: E'→E. E→E.+T
I2: E→T. T→T.*F
I3: T→F.
I4: F→id.
I5: E→E+.T T→.T*F T→.F F→.id
I6: T→T*.F F→.id
I7: E→E+T. T→T.*F
I8: T→T*F.Transitions: I0 goes to I1 on E, I2 on T, I3 on F and I4 on id; I1 to I5 on +; I2 to I6 on *; I5 to I7 on T, I3 on F and I4 on id; I6 to I8 on F and I4 on id; I7 to I6 on *.
Step 3. FOLLOW(E) = { +, $ }, FOLLOW(T) = FOLLOW(F) = { +, *, $ }.
Step 4. Rules: goto(Ii, a) = Ij on a terminal gives shift j (sj); a complete item A → α. in Ii gives rn, reduce by production n = A → α, on every symbol in FOLLOW(A); E' → E. gives accept on $; goto on a nonterminal fills the GOTO part.
St id + * $ | E T F
0 s4 | 1 2 3
1 s5 acc |
2 r2 s6 r2 |
3 r4 r4 r4 |
4 r5 r5 r5 |
5 s4 | 7 3
6 s4 | 8
7 r1 s6 r1 |
8 r3 r3 r3 |I2 and I7 each hold a complete item and an item with the dot before *. An LR(0) parser would have a shift-reduce conflict there, but SLR reduces only on FOLLOW(E) = { +, $ }, which does not contain *. No cell has two entries, so the grammar is SLR(1).
Step 5. Moves on id + id * id:
Stack Input Action
0 id+id*id$ shift 4
0id4 +id*id$ reduce F→id
0F3 +id*id$ reduce T→F
0T2 +id*id$ reduce E→T
0E1 +id*id$ shift 5
0E1+5 id*id$ shift 4
0E1+5id4 *id$ reduce F→id
0E1+5F3 *id$ reduce T→F
0E1+5T7 *id$ shift 6
0E1+5T7*6 id$ shift 4
0E1+5T7*6id4 $ reduce F→id
0E1+5T7*6F8 $ reduce T→T*F
0E1+5T7 $ reduce E→E+T
0E1 $ acceptConclusion: in state 7 with * as input the parser shifts instead of reducing by E → E+T, so * is applied before +, as its higher precedence requires. The string is accepted.
6 Construct the CLR(1) parsing table for the grammar S → AcA, A → aA | b. Then build the LALR(1) table by merging states and compare the two. 10 marks
A canonical LR(1) (CLR) parser uses LR(1) items [A → α.β, a]: the lookahead a means the reduction by A → αβ is made only when the next input symbol is a. An LALR(1) parser merges LR(1) states with the same core (the same LR(0) items).
Step 1. Augment and number: S' → S, 1. S → AcA, 2. A → aA, 3. A → b.
Step 2. Closure: for [A → α.Bβ, a], add [B → .γ, b] for every b in FIRST(βa). In I0, [S → .AcA, $] gives the A-items lookahead FIRST(cA$) = { c }; in I5, [S → Ac.A, $] gives them $.
I0: S'→.S,$ S→.AcA,$
A→.aA,c A→.b,c
I1: S'→S.,$
I2: S→A.cA,$
I3: A→a.A,c A→.aA,c A→.b,c
I4: A→b.,c
I5: S→Ac.A,$ A→.aA,$ A→.b,$
I6: A→aA.,c
I7: S→AcA.,$
I8: A→a.A,$ A→.aA,$ A→.b,$
I9: A→b.,$
I10: A→aA.,$Transitions: I0 goes to I1 on S, I2 on A, I3 on a and I4 on b; I2 to I5 on c; I3 to I3 on a, I6 on A and I4 on b; I5 to I7 on A, I8 on a and I9 on b; I8 to I8 on a, I10 on A and I9 on b.
Step 3. CLR table. Shifts come from goto on terminals; [A → α., a] gives a reduce on a only.
St a b c $ | S A
0 s3 s4 | 1 2
1 acc |
2 s5 |
3 s3 s4 | 6
4 r3 |
5 s8 s9 | 7
6 r2 |
7 r1 |
8 s8 s9 | 10
9 r3 |
10 r2 |No cell has two entries, so the grammar is CLR(1).
Step 4. LALR merging. Three pairs share a core: I3 and I8 become I38, I4 and I9 become I49, I6 and I10 become I610, with their lookaheads joined (c/$). The 11 CLR states become 8.
St a b c $ | S A
0 s38 s49 | 1 2
1 acc |
2 s5 |
38 s38 s49 | 610
49 r3 r3 |
5 s38 s49 | 7
610 r2 r2 |
7 r1 |I49 and I610 each reduce by one production only, so merging creates no reduce-reduce conflict and the grammar is LALR(1).
Comparison:
- CLR has 11 states; LALR has 8, the same number as the LR(0) collection, so its table is much smaller.
- Both accept the same strings. On an error, LALR may make extra reductions first but never shifts a wrong symbol. For the input ab, CLR reports the error at once in state 4, which has no action on $; LALR first reduces by A → b and A → aA and reports it in state 2.
- Merging can create reduce-reduce conflicts but never a new shift-reduce conflict, so a few CLR(1) grammars are not LALR(1).
Syntax-Directed Translation and Intermediate Code Generation
Syllabus: Syntax-directed definitions; Evaluation orders for SDDs; Applications of syntax-directed translation; Syntax-directed translation schemes; Implementing L-attributed SDDs; Variants of syntax trees; Three-address code; Types and declarations; Translation of expressions; Type checking; Control flow; Backpatching; Intermediate code for procedures
One-page revision summary
- A syntax-directed definition attaches attributes to grammar symbols and semantic rules to productions, and an annotated parse tree shows each attribute's value.
- A synthesized attribute comes from the node's children and the node itself; an inherited attribute comes from the parent, the siblings and the node itself.
- A dependency graph has an edge from each attribute to every attribute computed from it; any topological sort is a valid evaluation order, and a cycle means none exists.
- An S-attributed SDD is evaluated in postorder, and an L-attributed SDD by one depth-first, left-to-right traversal.
- Syntax-directed translation is used to evaluate expressions, build syntax trees, check types, record declarations and generate intermediate code.
- An SDT embeds semantic actions in production bodies; a postfix SDT, with every action at the right end, runs on the reductions of an LR parser.
- An L-attributed SDD is implemented by placing inherited-attribute actions just before their nonterminal, or in recursive descent by passing inherited attributes as parameters and returning synthesized ones.
- A DAG shares common subexpressions, and the value-number method returns an existing node with the same operator and children instead of creating a new one.
- Three-address code has at most one operator on the right side of each instruction and is stored as quadruples, triples or indirect triples.
- Declarations are processed with a running offset: each name gets the current offset, which then grows by the width of its type.
- With indexes starting at 0, A[i1][i2] lies at base + i1 × w1 + i2 × w2, where w1 is the width of a row and w2 the width of an element.
- A type checker uses type synthesis or type inference, and inserts coercions such as widening integer to float when operand types differ.
- Boolean expressions are translated into jumping (short-circuit) code, so in B1 or B2 the code for B2 runs only when B1 is false.
- For while (B) S1 the code is a label begin, the jumping code of B, the label B.true, the code of S1 and goto begin, with B.false equal to S.next.
- Backpatching fills jump targets in one pass, using makelist, merge and backpatch on truelist, falselist and nextlist.
- A procedure call evaluates its arguments, generates param x1 … param xn and then call p, n, and return y passes a value back to the caller.
- A function's type is a type expression s → t, and each procedure body gets its own symbol table, linked to the table of the enclosing scope.
Learn these by heart
- Synthesized: computed from the children and the node itself; inherited: from the parent, the siblings and the node itself.
- L-attributed: an inherited attribute of Xi in A → X1 … Xn uses only inherited attributes of A and attributes of X1 … Xi-1 (or Xi itself, without cycles).
- Width of array(n, t) = n × width(t); after each declaration, offset = offset + T.width.
- Quadruple = (op, arg1, arg2, result); triple = (op, arg1, arg2), with results referred to by position.
- B → B1 or M B2: backpatch(B1.falselist, M.instr); B.truelist = merge(B1.truelist, B2.truelist); B.falselist = B2.falselist.
- B → B1 and M B2: backpatch(B1.truelist, M.instr); B.truelist = B2.truelist; B.falselist = merge(B1.falselist, B2.falselist).
- Call: param x1 … param xn, then call p, n (or t = call p, n when a value is returned).
2-mark questions
1 Distinguish between synthesized and inherited attributes in a syntax-directed definition. 2 marks
A synthesized attribute at a parse-tree node N is computed from attribute values at N's children and at N itself, as in E.val = E1.val + T.val. An inherited attribute at N is computed from values at N's parent, N itself and N's siblings, as in L.inh = T.type for D → T L. Terminals have only synthesized attributes.
2 What are S-attributed and L-attributed definitions? How are they related? 2 marks
An S-attributed SDD uses only synthesized attributes, so a postorder traversal evaluates it. An L-attributed SDD also allows inherited attributes, but an inherited attribute of Xi in A → X1 … Xn may use only inherited attributes of A and attributes of X1 … Xi-1, or of Xi itself without a cycle. Every S-attributed SDD is L-attributed.
3 What is a syntax-directed translation scheme? What is a postfix SDT? 2 marks
A syntax-directed translation scheme (SDT) is a context-free grammar with semantic actions, program fragments in braces, inside production bodies; an action runs when the parse reaches it. A postfix SDT has every action at the right end, as in E → E1 + T { E.val = E1.val + T.val }; an LR parser runs it on reduction.
4 Write three-address code for the statement if (a < b) x = 1; else x = 2; using jumps and labels. 2 marks
Taking B.true = L1, B.false = L2 and S.next = L3, the condition jumps to L1 when true and to L2 when false, and the then-part ends with a jump past the else-part.
if a < b goto L1
goto L2
L1: x = 1
goto L3
L2: x = 2
L3:5 Distinguish type synthesis from type inference. 2 marks
Type synthesis builds an expression's type from its subexpressions' types, so names must be declared first: from f : s → t and x : s it gives f(x) : t. Type inference finds a construct's type from its use: from f(x) it concludes f : α → β and x : α for some type variables α, β.
6 Write three-address code for the assignment y = f(a + b, c), which calls a function f. 2 marks
The arguments are evaluated first, each is passed with a param instruction, and call names the procedure and the number of arguments; the returned value goes into a temporary.
t1 = a + b
param t1
param c
t2 = call f, 2
y = t210-mark questions
1 What is a syntax-directed definition? Explain synthesized and inherited attributes, write an SDD for a simple desk calculator and draw the annotated parse tree for the input 3 * 5 + 4 n. 10 marks
A syntax-directed definition (SDD) is a context-free grammar in which grammar symbols carry attributes and productions carry semantic rules that compute those attributes. The parser builds the structure and the rules attach meaning to it; this is the basis of syntax-directed translation.
1. Attributes. An attribute is any quantity attached to a grammar symbol: a number, a type, a piece of code or a symbol-table entry. X.a is the value of attribute a of symbol X at one parse-tree node.
2. Synthesized attributes. At a node N for nonterminal A, a synthesized attribute is computed from the attributes of N's children and of N itself. Terminals have only synthesized attributes, which the lexical analyzer supplies, such as digit.lexval.
3. Inherited attributes. At node N, an inherited attribute is computed from the attributes of N's parent, N itself and N's siblings. In D → T L with the rule L.inh = T.type, the type passes from T to its sibling L.
4. SDD for a desk calculator. The end marker n closes the input, and every attribute is synthesized, so the SDD is S-attributed:
Production Semantic rule
L → E n L.val = E.val
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 → ( E ) F.val = E.val
F → digit F.val = digit.lexval5. Annotated parse tree. A parse tree that shows the attribute values at its nodes is an annotated parse tree. With only synthesized attributes, the values are filled in bottom-up, in postorder:
- the three F nodes get F.val = 3, 5 and 4 from digit.lexval;
- the lower T gets T.val = 3, and the T above it gets T.val = 3 × 5 = 15;
- the left E gets E.val = 15 and the right T gets T.val = 4;
- the top E gets E.val = 15 + 4 = 19, so L.val = 19.
6. Uses. The same method evaluates expressions, builds syntax trees, checks types, enters declarations in the symbol table and generates intermediate code.
In short, an SDD adds attributes and rules to a grammar; synthesized attributes flow upward, inherited attributes flow down or sideways, and the annotated parse tree for 3 * 5 + 4 n carries the result 19 at its root.
2 Explain dependency graphs and evaluation orders for SDDs. For the declaration SDD with D → T L, draw the dependency graph for float x, y and give an evaluation order. How is such an L-attributed SDD implemented? 10 marks
An SDD says what each attribute depends on but not when to compute it; the dependency graph of the parse tree fixes the order.
1. Dependency graph. It has one node per attribute instance. If a rule computes X.c from Y.b, there is an edge Y.b → X.c, since Y.b must be known first. A rule kept for its side effect, such as addType, gets a dummy attribute node.
2. Evaluation order. Any topological sort, an order in which every edge goes from an earlier node to a later one, is valid. A cycle means no order exists.
3. The SDD. T.type is synthesized, L.inh is inherited and carries the type down the list, and addType enters a name's type in the symbol table:
Production Semantic rules
D → T L L.inh = T.type
T → int T.type = integer
T → float T.type = float
L → L1 , id L1.inh = L.inh
addType(id.entry, L.inh)
L → id addType(id.entry, L.inh)4. Graph for float x, y. The parse tree is D → T L, T → float, L → L1 , id (y) and L1 → id (x). Its nodes are 1: x.entry, 2: y.entry, 3: T.type, 4: L.inh, 5: L1.inh, 6: addType(y.entry, L.inh) and 7: addType(x.entry, L1.inh), with edges 3 → 4, 4 → 5, 4 → 6, 2 → 6, 5 → 7 and 1 → 7.
Two valid orders are 1, 2, 3, 4, 5, 6, 7 and 3, 4, 5, 1, 7, 2, 6; either way x and y are entered with type float.
5. Guaranteed orders. An S-attributed SDD is evaluated in postorder, for example on each LR reduction. In an L-attributed SDD an inherited attribute of Xi in A → X1 … Xn uses only inherited attributes of A and attributes of X1 … Xi-1, so a depth-first, left-to-right traversal, computing inherited attributes on the way down and synthesized ones on the way up, evaluates it. The declaration SDD is L-attributed.
6. Implementation. Convert the SDD to an SDT: an action computing an inherited attribute of a nonterminal goes just before it, and actions for synthesized attributes go at the end of the body:
D → T { L.inh = T.type } L
L → { L1.inh = L.inh } L1 , id
{ addType(id.entry, L.inh) }
L → id { addType(id.entry, L.inh) }A recursive-descent translator (after left recursion is removed) passes inherited attributes as parameters and returns synthesized ones; an LR parser holds inherited values in marker nonterminals that derive ε.
Thus a topological sort of the dependency graph gives the order, and an L-attributed SDD needs only one left-to-right pass.
3 Explain how an SDD constructs syntax trees and how the same SDD can build a DAG instead. Construct the DAG for a * (b - c) + (b - c) * d, showing the steps and the value-number array. 10 marks
A syntax tree is a condensed parse tree: each interior node is an operator and its children are its operands, while chain productions and parentheses disappear. Building syntax trees is a main application of syntax-directed translation, and the directed acyclic graph (DAG) is a key variant.
1. SDD for syntax trees. Each nonterminal has a synthesized attribute node, a pointer to a tree node. Leaf(id, entry) creates a leaf and Node(op, left, right) an interior node:
- E → E1 + T: E.node = new Node('+', E1.node, T.node), and likewise for - and *
- E → T: E.node = T.node, and T → F: T.node = F.node
- F → ( E ): F.node = E.node
- F → id: F.node = new Leaf(id, id.entry)
2. DAG variant. A DAG has one node per distinct subexpression, so a common subexpression is shared. The same SDD builds a DAG if Leaf and Node first look for an existing node with the same label and children and return it.
3. Value-number method. Nodes are records in an array, and a record's index is its value number. A record holds the operator (or id and the name) and the children's value numbers; before creating (op, l, r), the constructor searches, usually by hashing, for an identical record.
4. Steps for a * (b - c) + (b - c) * d, in the order a bottom-up parse makes the calls:
p1 = Leaf(id, a) new node 1
p2 = Leaf(id, b) new node 2
p3 = Leaf(id, c) new node 3
p4 = Node('-', p2, p3) new node 4
p5 = Node('*', p1, p4) new node 5
p6 = Leaf(id, b) returns p2
p7 = Leaf(id, c) returns p3
p8 = Node('-', p2, p3) returns p4
p9 = Leaf(id, d) new node 6
p10 = Node('*', p4, p9) new node 7
p11 = Node('+', p5, p10) new node 8Resulting value-number array:
1: id a
2: id b
3: id c
4: - 2 3
5: * 1 4
6: id d
7: * 4 6
8: + 5 7The syntax tree has 11 nodes; the DAG has 8, because the second b - c, with its leaves b and c, is the node already built.
5. Use. Code generated from the DAG computes b - c only once:
t1 = b - c
t2 = a * t1
t3 = t1 * d
t4 = t2 + t3Postfix notation and three-address code are other intermediate forms produced the same way.
In short, the same rules build syntax trees and DAGs, and the DAG reuses nodes through value numbers.
4 What is three-address code? Give an SDD that translates assignment statements into three-address code, and write the three-address code, quadruples, triples and indirect triples for x = (a + b) * -c + d. 10 marks
Three-address code is a linear intermediate representation in which each instruction has at most one operator on its right side and at most three addresses: names, constants or compiler-generated temporaries.
1. Common instruction forms:
- x = y op z and x = op y (binary and unary operations)
- x = y (copy)
- goto L, if x goto L and if x relop y goto L (jumps)
- param x, call p, n and return y (procedures)
- x = y[i] and x[i] = y (indexed copies); x = &y, x = *y and *x = y (addresses and pointers)
2. SDD for expressions. E.addr is the name or temporary that holds the value of E, E.code is its instruction sequence, new Temp() makes a fresh temporary, gen(...) forms one instruction and || joins code:
- S → id = E ; : S.code = E.code || gen(top.get(id.lexeme) '=' E.addr)
- E → E1 + E2 : E.addr = new Temp(); E.code = E1.code || E2.code || gen(E.addr '=' E1.addr '+' E2.addr)
- E → - E1 : E.addr = new Temp(); E.code = E1.code || gen(E.addr '=' 'minus' E1.addr)
- E → ( E1 ) : E.addr = E1.addr; E.code = E1.code
- E → id : E.addr = top.get(id.lexeme); E.code = ''
The rule for * is like the rule for +. In the incremental form, gen appends each instruction to one output stream, so the code attributes are not needed.
3. Three-address code for x = (a + b) * -c + d. Unary minus binds tightest, then *, then +:
t1 = a + b
t2 = minus c
t3 = t1 * t2
t4 = t3 + d
x = t44. Quadruples have four fields, op, arg1, arg2 and result; temporaries are named explicitly.
op arg1 arg2 result
(0) + a b t1
(1) minus c t2
(2) * t1 t2 t3
(3) + t3 d t4
(4) = t4 x5. Triples have three fields, op, arg1 and arg2; a result is referred to by the position of the triple that computes it, so no temporaries are needed.
op arg1 arg2
(0) + a b
(1) minus c
(2) * (0) (1)
(3) + (2) d
(4) = x (3)6. Indirect triples keep a separate list of pointers to triples in execution order, so an optimizer can move an instruction by reordering the list alone.
instruction list
20: (0)
21: (1)
22: (2)
23: (3)
24: (4)Quadruples are easy to rearrange because results are named, triples save space, and indirect triples save space and still allow reordering.
5 What is backpatching? Give the backpatching translation scheme for boolean expressions and use it to translate if (a < b or c < d and e < f) x = 1; else x = 0; starting at instruction 100. 10 marks
When jumping code is produced in one pass, a forward jump is generated before its target is known. Backpatching leaves the target blank, keeps lists of such incomplete jumps, and fills the blanks when the target becomes known.
1. Functions and attributes. Instructions are numbered and nextinstr is the number of the next one.
- makelist(i) makes a new list holding only instruction i.
- merge(p1, p2) joins two lists.
- backpatch(p, i) makes i the target of every jump on list p.
B.truelist and B.falselist hold the jumps taken when B is true or false, and a marker M → ε records M.instr = nextinstr.
2. Translation scheme for boolean expressions:
B → B1 or M B2
{ backpatch(B1.falselist, M.instr);
B.truelist = merge(B1.truelist,
B2.truelist);
B.falselist = B2.falselist; }
B → B1 and M B2
{ backpatch(B1.truelist, M.instr);
B.truelist = B2.truelist;
B.falselist = merge(B1.falselist,
B2.falselist); }
B → not B1 { swap the two lists of B1 }
B → ( B1 ) { copy the lists of B1 }
B → E1 rel E2
{ B.truelist = makelist(nextinstr);
B.falselist = makelist(nextinstr + 1);
gen('if' E1.addr rel E2.addr 'goto _');
gen('goto _'); }
M → ε { M.instr = nextinstr; }3. The condition. The operator and binds tighter than or. Name the comparisons B1 (a < b), B2 (c < d) and B3 (e < f), and the and-subexpression B4:
- B1: truelist {100}, falselist {101}; then M.instr = 102
- B2: truelist {102}, falselist {103}; then M.instr = 104
- B3: truelist {104}, falselist {105}
- B4 (and): backpatch({102}, 104); truelist {104}, falselist {103, 105}
- B (or): backpatch({101}, 102); truelist {100, 104}, falselist {103, 105}
4. The statement. With S → if ( B ) M1 S1 N else M2 S2, M1.instr = 106 and M2.instr = 108, and N generates the jump at 107 past the else-part. The rule then calls backpatch(B.truelist, 106) and backpatch(B.falselist, 108):
100: if a < b goto 106
101: goto 102
102: if c < d goto 104
103: goto 108
104: if e < f goto 106
105: goto 108
106: x = 1
107: goto _
108: x = 0S.nextlist = {107}; it is filled when the instruction after the statement is known.
In short, backpatching gives short-circuit code in a single pass: every unknown target waits on a list until one backpatch call completes it.
6 Explain type expressions and the translation scheme that computes types, widths and relative addresses for declarations, applying it to int i; float f; int a[2][3];. Then explain type checking with coercion for the expression f + i * 2. 10 marks
A compiler records each name's type and storage and checks operand types; both jobs are syntax-directed.
1. Type expressions. A type expression is a basic type (boolean, char, integer, float, void) or a type constructor applied to type expressions: array(n, t), record, pointer(t), s × t or s → t. int a[2][3] has type array(2, array(3, integer)). Two type expressions are structurally equivalent when they are the same basic type or the same constructor applied to equivalent types.
2. Declarations. The width of a type is its size in bytes, here integer 4 and float 8; offset is the next free relative address:
P → { offset = 0 } D
D → T id ; { top.put(id.lexeme, T.type,
offset);
offset = offset + T.width } D1
D → ε
T → B { t = B.type; w = B.width }
C { T.type = C.type; T.width = C.width }
B → int { B.type = integer; B.width = 4 }
B → float { B.type = float; B.width = 8 }
C → ε { C.type = t; C.width = w }
C → [ num ] C1
{ C.type = array(num.value, C1.type);
C.width = num.value × C1.width }3. Worked example. In this grammar the dimensions are part of T, so the scheme reads int a[2][3] as int[2][3] a. For it, t = integer and w = 4; C → ε gives integer, 4; C → [3] C1 gives array(3, integer), 12; C → [2] C1 gives array(2, array(3, integer)), 24.
name width offset type
i 4 0 integer
f 8 4 float
a 24 12 array(2, array(3, integer))Total storage is 36 bytes. a[1] has type array(3, integer), and a[1][2] has type integer and lies 1 × 12 + 2 × 4 = 20 bytes into a.
4. Type checking. Each expression gets a type from rules such as: if E1 and E2 are integer, E1 * E2 is integer. When operand types differ, the checker inserts a coercion, an implicit conversion that widens the narrower type:
E → E1 + E2
{ E.type = max(E1.type, E2.type);
a1 = widen(E1.addr, E1.type, E.type);
a2 = widen(E2.addr, E2.type, E.type);
E.addr = new Temp();
gen(E.addr '=' a1 '+' a2); }max picks the wider type in the order integer < float; widen emits a conversion only when the types differ.
5. Checking f + i * 2. i * 2 is integer and f is float, so the sum is float and the product is widened:
t1 = i * 2
t2 = (float) t1
t3 = f + t2When no rule applies, a type error is reported.
Declarations thus fix each name's type, width and offset, which the checker uses to accept, convert or reject expressions.
Code Optimization
Syllabus: The principal sources of optimization; Basic blocks; Optimization of basic blocks; Structure-preserving transformations; Flow graphs; Loop optimization; Data-flow analysis; Peephole optimization
One-page revision summary
- Code optimization transforms intermediate code so that it runs faster or takes less space while computing exactly the same results, and the gain should justify the compile-time cost.
- Common subexpression elimination, copy propagation, dead-code elimination and constant folding are function-preserving transformations, the principal sources of optimization inside and across blocks.
- Local optimization works inside one basic block; global optimization works across the blocks of a flow graph and needs data-flow analysis.
- A basic block is entered only at its leader and left only at its last statement, so all its statements run whenever the first one does.
- A DAG of a basic block exposes local common subexpressions and, once the variables live on exit are known, dead code; any children-first order of its nodes is a valid evaluation order if each old value is used before its variable is assigned again.
- Algebraic transformations of a block use identities such as x + 0 = x and x * 1 = x, and replace expensive operations, such as x ^ 2 by x * x.
- The structure-preserving transformations are common subexpression elimination, dead-code elimination, renaming temporary variables and interchanging independent adjacent statements; a block in which every temporary is defined only once is a normal-form block.
- In a flow graph the initial node is the block holding the first statement, and an edge joins two blocks when control can pass directly from one to the other.
- An edge n → h is a back edge when h dominates n; its natural loop is h together with every node that can reach n without passing through h.
- A preheader is a new block placed just before a loop header, so that loop-invariant statements have a place to move to.
- Loop optimizations are code motion, strength reduction and induction-variable elimination; loop unrolling copies the body to save tests and jumps, and loop jamming merges two adjacent loops over the same range.
- A global common subexpression is one already computed on every path into a block with no operand changed since; available-expression analysis, a forward problem that intersects over predecessors, finds it.
- Live-variable analysis is a backward problem: a variable is live at a point if its current value may be used on some path from that point.
- Data-flow problems are solved by iterating the equations over all blocks until no set changes, which is the fixed point.
- Peephole optimization slides a small window over the target code and replaces short instruction sequences by shorter or faster ones, repeating the pass until nothing changes.
- Peephole transformations remove redundant loads and stores, unreachable code and jumps to jumps, simplify algebra, reduce strength and use machine idioms such as an increment instruction.
Learn these by heart
- Leaders: the first statement, every target of a jump, and every statement right after a jump.
- Reaching definitions: OUT[B] = gen[B] ∪ (IN[B] − kill[B]); IN[B] = ∪ OUT[P] over predecessors P.
- Live variables: IN[B] = use[B] ∪ (OUT[B] − def[B]); OUT[B] = ∪ IN[S] over successors S.
- Available expressions: OUT[B] = e_gen[B] ∪ (IN[B] − e_kill[B]); IN[B] = ∩ OUT[P] over predecessors P.
- d dominates n if every path from the entry to n goes through d; n → h is a back edge if h dominates n.
- Strength reduction: t = 4 * i with i = i + 1 becomes t = t + 4, with t = 4 * i set in the preheader.
- Structure-preserving transformations: common subexpression elimination, dead-code elimination, renaming temporaries, interchanging independent statements.
2-mark questions
1 Define a basic block. State the rules for finding leaders. 2 marks
A basic block is a maximal sequence of consecutive three-address statements that control enters only at the first statement and leaves only at the last. Leaders are the first statement, every target of a conditional or unconditional jump, and every statement just after a jump. Each block runs from a leader up to, not including, the next leader.
2 What is a flow graph? When does one node of a flow graph dominate another? 2 marks
A flow graph is a directed graph of basic blocks, with an edge B → C when C can run immediately after B: B jumps to the start of C, or C follows B and B does not end in an unconditional jump. Node d dominates node n if every path from the entry to n passes through d.
3 List the structure-preserving transformations on a basic block. 2 marks
- Common subexpression elimination: an expression recomputed with unchanged operands reuses the earlier result.
- Dead-code elimination: a statement whose result is never used is removed.
- Renaming temporaries: t = b + c may become u = b + c, with every use of t changed to u.
- Interchange of statements: two adjacent independent statements may be swapped.
4 What are induction variables? Show how strength reduction is applied to them. 2 marks
An induction variable changes by a constant on each loop iteration (i = i + 1) or is a linear function of one (t = 4 * i). Strength reduction replaces t = 4 * i by the cheaper t = t + 4 after i = i + 1, with t = 4 * i set once before the loop.
5 What is a reaching definition? Write the data-flow equations for reaching definitions. 2 marks
A definition d of a variable x reaches a point p if some path runs from just after d to p with no other definition of x on it, so d is not killed. For each block B:
OUT[B] = gen[B] ∪ (IN[B] − kill[B])
IN[B] = ∪ OUT[P], P a predecessor of Bwith OUT[ENTRY] = ∅.
6 Explain copy propagation and dead-code elimination with an example. 2 marks
After a copy x = y, copy propagation replaces later uses of x by y while neither is assigned again: x = y; z = x + 1 becomes x = y; z = y + 1. If x is not used later, x = y is now dead code, and dead-code elimination deletes it.
10-mark questions
1 Explain the principal sources of optimization. Illustrate each function-preserving and loop transformation with a short example. 10 marks
Code optimization improves the intermediate code so that the target program runs faster or takes less space, without changing what the program computes. A transformation must preserve the meaning of the program, should give a measurable gain, and should be worth its compile-time cost. The code optimizer sits between the front end and the code generator: control-flow analysis builds the flow graph, data-flow analysis collects facts about it, and the transformations use those facts.
A transformation is local if it works inside one basic block and global if it works across blocks. The principal sources of optimization are:
1. Common subexpression elimination. An expression is a common subexpression if it was computed before and none of its operands has changed since. In
t1 = 4 * i
t2 = a[t1]
t3 = 4 * i
t4 = b[t3]t3 recomputes 4 * i, so t3 = 4 * i is deleted and the last statement becomes t4 = b[t1].
2. Copy propagation. After a copy x = t1, later uses of x are replaced by t1: z = x + k becomes z = t1 + k. The copy itself often becomes dead.
3. Dead-code elimination. A variable is dead at a point if its value is never used later. A statement that computes only a dead value is removed, and so is code that can never run, such as the body of if (debug) when debug is the constant 0.
4. Constant folding. An expression whose operands are known constants is evaluated at compile time: r = 2 * 8 becomes r = 16. Constant propagation replaces a variable by its known constant value, which creates more folding.
5. Code motion. A loop-invariant computation gives the same value on every iteration, so it is moved before the loop. In for (i = 0; i < n; i++) b[i] = a[i] + k * m; the product is computed once as t = k * m before the loop, and the body becomes b[i] = a[i] + t.
6. Induction variables and strength reduction. If a loop contains i = i + 1 followed by j = 4 * i, then i and j change in lock step. The multiplication is replaced by the cheaper j = j + 4, with j = 4 * i computed once before the loop. If i is then used only in the loop test, the test is rewritten in terms of j and i is eliminated.
In conclusion, the largest gains come from inner loops, where code motion, strength reduction and induction-variable elimination save work on every iteration, while the other transformations clean up the code inside and across blocks.
2 What is peephole optimization? Explain its characteristic transformations with an example of each. 10 marks
Peephole optimization is a simple but effective way of improving target code; it can also be applied to intermediate code. The compiler slides a small window, the peephole, over the instruction sequence and replaces any group of instructions inside the window by a shorter or faster sequence. One improvement often exposes another, so the pass is repeated until nothing changes. Its characteristic transformations are:
1. Redundant loads and stores. In
ST a, R0
LD R0, athe load is redundant, because R0 already holds the value of a. It is deleted, provided LD R0, a carries no label, so that no jump can reach it without the store running first.
2. Unreachable code. An unlabeled instruction just after an unconditional jump can never run and is removed. Code behind a constant test also becomes unreachable:
if flag == 1 goto L1
goto L2
L1: call trace
L2: ...The jump over a jump is first replaced by if flag != 1 goto L2 followed directly by call trace. If flag is the constant 0, the test is always true, so it becomes goto L2, and call trace is then unreachable and deleted.
3. Flow-of-control optimizations. Jumps to jumps are shortened. A goto L1, where L1: goto L2, becomes goto L2, and if a < b goto L1 becomes if a < b goto L2. If no other jump then reaches L1 and the statement before it is an unconditional jump, L1: goto L2 itself is deleted.
4. Algebraic simplification. Statements such as x = x + 0 and x = x * 1 change nothing and are deleted.
5. Reduction in strength. An expensive operation is replaced by a cheaper one that gives the same result on the target machine: x ^ 2 becomes x * x, x * 2 becomes x + x, and an integer multiplied by 8 becomes a left shift by 3 bits.
6. Use of machine idioms. Special instructions are used where the machine has them: i = i + 1 becomes a single increment instruction such as INC i, and auto-increment addressing steps a pointer while it is being used.
In conclusion, peephole optimization looks at only a few instructions at a time, so it is fast and easy to implement, yet repeated passes remove many of the redundancies left by straightforward code generation.
3 Give the algorithm that partitions three-address code into basic blocks. Apply it to code that adds the positive elements a[1] to a[n] of an integer array into s, and draw the flow graph. 10 marks
A basic block is a maximal sequence of consecutive three-address statements with one entry, at its first statement, and one exit, at its last. Blocks are found in two steps.
1. Find the leaders: (a) the first statement is a leader; (b) every target of a conditional or unconditional jump is a leader; (c) every statement that immediately follows a conditional or unconditional jump is a leader. 2. For each leader, its basic block is the leader and every statement after it up to, but not including, the next leader or the end of the program.
The flow graph has an edge B → C if the last statement of B jumps to the leader of C, or if C immediately follows B and B does not end in an unconditional jump.
Example. The source
i = 1; s = 0;
while (i <= n) {
if (a[i] > 0) s = s + a[i];
i = i + 1;
}
return s;gives, with 4-byte integers:
(1) i = 1
(2) s = 0
(3) if i > n goto (12)
(4) t1 = 4 * i
(5) t2 = a[t1]
(6) if t2 <= 0 goto (10)
(7) t3 = 4 * i
(8) t4 = a[t3]
(9) s = s + t4
(10) i = i + 1
(11) goto (3)
(12) return sLeaders: (1) by rule (a); (3), (10) and (12) as jump targets; (4), (7) and (12) as statements after jumps. The leaders are therefore (1), (3), (4), (7), (10) and (12), which give six blocks:
- B1 = (1)–(2), B2 = (3), B3 = (4)–(6)
- B4 = (7)–(9), B5 = (10)–(11), B6 = (12)
Edges: B1 → B2; B2 → B3 when the test is false and B2 → B6 when it is true; B3 → B4 when false and B3 → B5 when true; B4 → B5; B5 → B2 through the goto; B6 leads to the exit.
Every path from B1 to B5 passes through B2, so B2 dominates B5 and B5 → B2 is a back edge. Its natural loop is {B2, B3, B4, B5}, which is the while loop. The flow graph also shows that 4 * i is computed in B3 and again in B4 with i unchanged, a global common subexpression that the optimizer can remove.
Basic blocks are the units of local optimization, and the flow graph is the base for global optimization and loop detection.
4 Explain the DAG representation of a basic block. Construct the DAG for the block t1 = a * b; t2 = t1 + c; x = t2 - d; t3 = a * b; y = t3 + c; a = y * d; t4 = a * b; x = t4 - y, where only a, x and y are live on exit, and use it to remove common subexpressions and dead code. 10 marks
A DAG (directed acyclic graph) for a basic block shows how each value computed in the block depends on earlier values. Its leaves are labelled by identifiers or constants and stand for their initial values (written a0, b0, …); each interior node is labelled by an operator and has the nodes of its operands as children; and each node carries the list of variables that currently hold its value.
Construction. Process each statement x = y op z in order:
1. Find the nodes that currently hold y and z, creating a leaf for a name seen for the first time. 2. If a node with operator op and exactly these children already exists, reuse it (a common subexpression); otherwise create a new node. 3. Remove x from the list of the node that held it before, and attach x to this node.
The block is
(1) t1 = a * b
(2) t2 = t1 + c
(3) x = t2 - d
(4) t3 = a * b
(5) y = t3 + c
(6) a = y * d
(7) t4 = a * b
(8) x = t4 - ySteps: (1) creates n1 = a0 * b0 {t1}; (2) creates n2 = n1 + c0 {t2}; (3) creates n3 = n2 - d0 {x}. (4) finds n1 again, so t3 joins it: {t1, t3}. (5) finds n2: {t2, y}. (6) creates n4 = n2 * d0 {a}. In (7), a now names n4, not a0, so a * b is not a common subexpression this time and a new node n5 = n4 * b0 {t4} is created. (8) creates n6 = n5 - n2 {x}, and x leaves n3.
Using the DAG:
- Common subexpressions: statements (4) and (5) added no nodes, so their values are not computed again.
- Dead code: n3 is a root with no live variable attached, since x moved to n6, so statement (3) is deleted.
- Names: each node keeps a live variable if one is attached (y on n2), otherwise one temporary (t1 on n1).
Regenerating code from the DAG in the order n1, n2, n4, n5, n6 gives
t1 = a * b
y = t1 + c
a = y * d
t4 = a * b
x = t4 - yThe block shrinks from eight statements to five and leaves the same final values in a, x and y. The DAG also shows which statements may be reordered: any order that computes children before parents is valid, as long as the old value a0 is used before a is assigned again.
5 Explain code motion, strength reduction and induction-variable elimination. Apply them step by step to the three-address code of the loop do { x[i] = y[i] * (p + q); i = i + 1; } while (i < n); with i starting at 0. 10 marks
Loop optimization pays most, because programs spend most of their time in inner loops. A loop is found in the flow graph as the natural loop of a back edge n → h, an edge whose head h dominates its tail n. The main transformations are:
- Code motion: a loop-invariant computation, whose operands are constants or defined only outside the loop, moves to a preheader, a new block just before the loop header.
- Strength reduction: an expensive operation on an induction variable, such as a multiplication, is replaced by a cheaper one, such as an addition.
- Induction-variable elimination: when several induction variables change in lock step, all but one are removed by rewriting the loop test.
Example (4-byte array elements):
B1: i = 0
B2: t1 = p + q
t2 = 4 * i
t3 = y[t2]
t4 = t3 * t1
t5 = 4 * i
x[t5] = t4
i = i + 1
if i < n goto B2B2 → B2 is a back edge, so B2 alone forms the loop.
1. Common subexpression: t5 = 4 * i repeats t2 with i unchanged, so it is removed and the store becomes x[t2] = t4. 2. Code motion: p and q are not assigned in the loop, so t1 = p + q is invariant. B2 dominates the only exit and t1 has no other definition in the loop, so it moves to the preheader. 3. Strength reduction: i is a basic induction variable (i = i + 1) and t2 = 4 * i is in its family. t2 = 4 * i moves to the preheader and t2 = t2 + 4 is added after i = i + 1, so t2 = 4 * i still holds wherever t2 is used. 4. Induction-variable elimination: since t2 = 4 * i, the test i < n is the same as t2 < 4 * n. With t6 = 4 * n in the preheader the test becomes if t2 < t6 goto B2. If i is not used after the loop, i = i + 1 is now dead and is removed.
Result:
B1: i = 0
Pre: t1 = p + q
t2 = 4 * i
t6 = 4 * n
B2: t3 = y[t2]
t4 = t3 * t1
x[t2] = t4
t2 = t2 + 4
if t2 < t6 goto B2Each iteration now runs five statements instead of eight and one multiplication instead of three, and p + q is computed only once. Both versions store the same values in x[0] to x[n − 1].
6 Explain data-flow analysis using reaching definitions. Give the gen and kill sets, the data-flow equations and the iterative algorithm, and compute IN and OUT of every block for a worked example. 10 marks
Data-flow analysis gathers facts about how values flow along the paths of a flow graph, such as which definitions reach a point, which expressions are available and which variables are live. Global optimizations such as constant propagation and code motion depend on it.
A definition d of x reaches a point p if some path runs from just after d to p with no other definition of x on it; any other definition of x kills d. For a block B, gen[B] is the set of definitions in B that reach its end, and kill[B] is the set of definitions elsewhere in the program of variables that B defines. The equations are
OUT[B] = gen[B] ∪ (IN[B] − kill[B])
IN[B] = ∪ OUT[P], P a predecessor of BIterative algorithm:
1. Set OUT[ENTRY] = ∅ and OUT[B] = ∅ for every other block. 2. For each block B in order, compute IN[B] and then OUT[B] from the equations. 3. Repeat step 2 until a full pass changes no OUT set. The sets only grow and are finite, so this ends.
Example. The program i = 1; s = 0; p = 1; do { s = s + i; if (i % 2 != 0) p = p * i; i = i + 1; } while (i <= n); gives four blocks; B4 either loops back to B2 or leaves to the exit:
B1: d1: i = 1
d2: s = 0
d3: p = 1
B2: d4: s = s + i
d5: r = i % 2
if r == 0 goto B4
B3: d6: p = p * i
B4: d7: i = i + 1
if i <= n goto B2Sets as bit vectors over d1 … d7:
Block gen kill
B1 1110000 0001011
B2 0001100 0100000
B3 0000010 0010000
B4 0000001 1000000Passes in the order B1, B2, B3, B4:
Pass 1 Pass 2
IN OUT IN OUT
B1 0000000 1110000 0000000 1110000
B2 1110000 1011100 1111111 1011111
B3 1011100 1001110 1011111 1001111
B4 1011110 0011111 1011111 0011111Pass 3 repeats the pass 2 values, so this is the fixed point:
- IN[B2] = {d1, …, d7}
- IN[B3] = IN[B4] = {d1, d3, d4, d5, d6, d7}
Use: d1 and d7 both reach the uses of i in B2, so i is not the constant 1 there and constant propagation must not replace it by 1. Likewise d3 and d6 both reach B3, so p may hold either value.
Reaching definitions thus tell the optimizer which assignments can supply each value that is used.
Run-Time Environments and Code Generation
Syllabus: Storage organization; Run-time storage allocation; Activation records; Procedure calls; Displays; Issues in the design of a code generator; Object code forms; Code generation algorithm; Register allocation and assignment
One-page revision summary
- Run-time memory is divided into code, static data, heap and stack, and the heap and stack grow towards each other through the free memory between them.
- Static allocation fixes every address at compile time, stack allocation gives each activation a fresh record, and heap allocation allocates and frees blocks in any order.
- A dangling reference arises when storage is freed while a pointer to it is still used; a memory leak arises when unreachable storage is never freed.
- The control stack holds one activation record for each live activation, with the record of the running procedure on top.
- Copy-restore (value-result) passing copies the actual values into the formals at the call and copies the final formal values back to the actuals on return.
- Call by name, as in Algol 60, behaves as if the actual parameter expression were substituted for the formal and evaluated afresh at each use.
- Access links point to the record of the enclosing procedure, and following them costs time proportional to the difference in nesting depths.
- A display reaches any nonlocal name with one indirection, at the cost of saving and restoring one display entry on each call.
- The code generator must preserve the meaning of the source program, use the target machine well and run efficiently itself.
- Relocatable object code allows separate compilation and libraries, while absolute code avoids linking but must run at a fixed address.
- Next-use information, found by scanning a basic block backwards, tells the code generator when a register holding a value can be reused.
- At the end of a basic block, every name live on exit whose memory copy is out of date is stored back.
- Variables used heavily inside loops gain the most from registers, because the loop body runs many times.
- Spilling stores a value to memory and reloads it later, freeing a register when all registers are in use.
Learn these by heart
- Activation record fields: actual parameters, returned value, control link, access link, saved machine status, local data, temporaries.
- Access links: a procedure at depth np reaching a name declared at depth nq follows np − nq links.
- Display: on a call to a procedure at depth n, save d[n] in the new record and point d[n] to it; on return, restore d[n].
- Object code forms: absolute machine code, relocatable machine code and assembly language.
- Code for x = y op z: getReg gives Rx, Ry, Rz; LD Ry, y and LD Rz, z if needed; then OP Rx, Ry, Rz.
- Usage-count savings of x in loop L = Σ over blocks B in L of [use(x, B) + 2 × live(x, B)].
- Two values interfere if one is live where the other is defined; k registers means coloring the interference graph with k colors.
2-mark questions
1 What is an activation record? Name its main fields. 2 marks
An activation record (frame) is the block of storage created for one activation, that is one execution, of a procedure; with stack allocation it is pushed on the control stack at the call. It usually holds the actual parameters, the returned value, a control link, an access link, the saved machine status, local data and temporaries.
2 Distinguish call by value from call by reference. 2 marks
In call by value, the caller evaluates the actual parameter and copies its value (r-value) into the formal parameter, so changes to the formal do not affect the caller. In call by reference, the address (l-value) of the actual parameter is passed, so every use or change of the formal acts on the caller's variable itself.
3 What is a display in run-time storage management? 2 marks
A display is an array d of pointers, one entry for each nesting depth, used to reach nonlocal names in a language with nested procedures. d[i] points to the most recent activation record on the stack of a procedure at depth i, so a name declared at depth i is reached through d[i] plus its offset.
4 List the forms of object code that a code generator can produce. 2 marks
- Absolute machine code: placed at a fixed memory location and run at once; quick for small programs.
- Relocatable machine code: modules are compiled separately and combined by a linking loader.
- Assembly language: the easiest to generate, but an assembler must translate it afterwards.
5 Define register descriptor and address descriptor. 2 marks
A register descriptor records, for each register, the names whose current values it holds; at the start of a block every register is empty. An address descriptor records, for each name, every location (register, memory address or stack slot) where its current value can be found. The code generator reads and updates both.
6 Differentiate register allocation from register assignment. 2 marks
Register allocation decides which values, such as variables and temporaries, will be kept in registers at each point of the program. Register assignment then decides which particular register holds each of those values. Both are done by the code generator, and finding an optimal assignment is NP-complete, so heuristics are used.
10-mark questions
1 Explain the organization of run-time storage. Describe the static, stack and heap storage-allocation strategies with their merits and limitations. 10 marks
When a compiled program runs, it receives a block of logical address space from the operating system. The compiler, working with the operating system and the target machine, decides how this space is divided and how names are bound to storage.
Storage organization. Run-time memory is commonly divided into four areas:
- Code: the generated target code. Its size is fixed at compile time, so it occupies a statically determined area, often at the low end of memory.
- Static data: global variables and constants whose size is known at compile time. Their addresses can be compiled into the target code.
- Heap: data whose lifetime is not tied to one procedure activation, created and freed under program control (for example with new and delete, or malloc and free).
- Stack: the activation records of procedure calls, pushed on a call and popped on return.
The sizes of the heap and the stack change while the program runs, so they are placed at opposite ends of the remaining free memory and grow towards each other.
Data layout also depends on the target machine. For example, a machine may require a 4-byte integer to begin at an address that is a multiple of 4, so the compiler may leave padding between fields to meet such alignment rules.
Storage-allocation strategies:
1. Static allocation: every name is bound to a fixed location at compile time, and the binding never changes. Every activation of a procedure uses the same locations, so local values survive between calls. Its limits are that the size of every data object must be known at compile time, recursive procedures cannot be supported because all activations would share one set of locations, and data structures cannot be created at run time. 2. Stack allocation: each call pushes a new activation record on the control stack and the return pops it. Locals get fresh storage in every activation, so recursion works, and each local is reached at a fixed offset from a pointer to the current record. The values of locals are lost when the activation ends. 3. Heap allocation: blocks are allocated and freed in any order, so data can outlive the procedure that created it, as with linked lists or objects returned from functions. A memory manager keeps track of free blocks, using strategies such as first fit or best fit, and must cope with fragmentation, memory leaks and dangling references; some languages reclaim unreachable data automatically by garbage collection.
Most languages combine the three: static storage for globals, a stack for procedure locals and a heap for dynamic data.
2 Draw the layout of a general activation record and explain each of its fields. How do the calling and return sequences of a procedure call set up and remove activation records? 10 marks
Each execution of a procedure is called an activation, and the information one activation needs is kept in a contiguous block called an activation record or frame. With stack allocation, a record is pushed on the control stack when the procedure is called and popped when it returns.
Fields of an activation record, starting from the caller's end:
1. Actual parameters: values supplied by the caller. The first few are often passed in registers instead. 2. Returned value: space for the value a function returns to its caller (also often a register). 3. Control link: points to the caller's activation record, so the caller's frame is restored on return. 4. Access link: points to the record of the enclosing procedure, used to reach nonlocal data when procedures are nested. 5. Saved machine status: the return address (where the caller continues) and the register values that must be restored after the call. 6. Local data: the procedure's local variables. 7. Temporaries: intermediate values of expressions that do not fit in registers.
The order is deliberate. Values exchanged between caller and callee come first, next to the caller's record, so the caller can fill them without knowing the callee's locals. Fixed-length items (the links and the machine status) sit in the middle, and items whose size may vary come last. A register top_sp points to the end of the machine-status field, so locals and temporaries are reached at fixed offsets from it.
Calling sequence (allocates the record and fills it):
1. The caller evaluates the actual parameters and places them in the callee's record. 2. The caller stores the return address and the old value of top_sp in the callee's record, then moves top_sp to the end of the callee's machine-status field. 3. The callee saves the register values and other status information. 4. The callee initializes its local data and begins execution.
Return sequence (restores the caller's state):
1. The callee places the returned value next to the parameters. 2. Using the saved machine status, the callee restores top_sp and the other registers and jumps to the return address. 3. The caller picks up the returned value, whose position relative to top_sp it knows, and continues.
As much of this work as possible is placed in the callee, because the callee's code is generated once while the caller's part is repeated at every call site. In this way each call gets its own storage, which is what makes recursive procedures possible.
3 Discuss the issues in the design of a code generator. Explain the forms of object code it may produce. 10 marks
The code generator is the final phase of a compiler. It takes the intermediate representation (intermediate code) of the source program, produced by the front end and possibly improved by the code optimizer, together with the symbol table, and produces an equivalent target program. The target code must be correct and of high quality, and the generator itself should run efficiently.
1. Input to the code generator: the intermediate code may be three-address code (quadruples, triples, indirect triples), a linear form such as postfix notation, a graphical form such as syntax trees or DAGs, or stack-machine code such as bytecode. The front end is assumed to have done type checking and inserted type conversions, so the input is free of errors. The symbol table supplies the run-time address of each name.
2. Target program (object code forms): the instruction set of the target, whether RISC, CISC or stack based, shapes the generator. The output can be:
- Absolute machine code, placed at a fixed location and executed immediately; it suits small programs that are compiled and run at once.
- Relocatable machine code, which lets modules be compiled separately; a linking loader combines them and fixes their addresses, at the extra cost of linking and loading.
- Assembly language, the easiest to generate because symbolic instructions and macros can be used, but an assembler must translate it afterwards.
3. Memory management: names in the intermediate code are mapped to addresses in static storage or in activation records, and labels of intermediate statements are converted into instruction addresses. A jump to a statement not yet translated is filled in later by backpatching.
4. Instruction selection: each intermediate statement must map to a good instruction sequence. Translating statement by statement is simple but produces redundant loads and stores. For example, a = a + 1 could become a load, an add and a store, but a machine with an increment instruction does it in one (INC a). The choice depends on the level of the intermediate code, the instruction set and the instruction costs.
5. Register allocation and assignment: operands in registers are the fastest to use. Allocation chooses which values stay in registers, and assignment chooses the particular register. Finding an optimal assignment is NP-complete, and some machines add rules, such as an even-odd register pair for multiplication or division.
6. Evaluation order: the order of computations affects how many registers are needed. Picking the best order is also NP-complete in general, so compilers use heuristics or keep the order of the intermediate code.
A code generator that handles these issues well produces target code that is correct, compact and fast.
4 How are nonlocal names accessed in a language with nested procedures? Explain displays with an example and compare them with access links. 10 marks
In a language with nested procedures, such as Pascal, a procedure may use names declared in the procedures that enclose it. Under lexical scope such a nonlocal name lives in the most recent activation record of the declaring procedure, which need not be the caller's record. Nesting depth helps to find it: the main program has depth 1, and a procedure declared inside a procedure of depth i has depth i + 1.
Access links. Each activation record keeps an access link to the record of its immediately enclosing procedure. If procedure p at depth np uses a name x declared in an enclosing procedure q at depth nq, the code follows np − nq access links from p's record and then adds the offset of x.
Displays. A display is an array d of pointers, one per nesting depth; d[i] points to the most recent activation record on the stack of a procedure at depth i. A nonlocal x declared at depth i is reached in one step: follow d[i] and add the offset of x. The calling and return sequences maintain the display:
1. When a procedure at depth n is called, its new record saves the old value of d[n]. 2. d[n] is set to point to the new record. 3. On return, d[n] is restored from the saved value.
Example: main (depth 1) declares procedures R and P (depth 2), and P declares Q (depth 3). Consider the calls main → P → Q → R.
- main starts: d[1] → main.
- P is called: P saves d[2] (undefined) and d[2] → P.
- Q is called: Q saves d[3] (undefined) and d[3] → Q. Q reaches P's names through d[2] and main's through d[1].
- Q calls R: R has depth 2, so R saves d[2], which points to P, and d[2] → R. Now d[1] → main, d[2] → R and d[3] → Q. R uses only d[1] and d[2], so the old entry in d[3] does no harm.
- When R returns, d[2] is restored to P, so Q again sees P's data.
Comparison:
- Access time: with access links, Q using a name of main follows 3 − 1 = 2 links; with the display it uses d[1] directly, the same cost for every nonlocal name.
- Work at a call: a display saves and restores one entry, while an access link must be computed at every call.
- Space: a display needs an array as long as the maximum nesting depth; access links need one field per record.
Thus a display trades a little work at each call for faster access to nonlocal data.
5 Explain the simple code-generation algorithm that uses register descriptors, address descriptors and the getReg function. Generate code with three registers for the block t1 = p + q, x = t1 * r, y = x - p, q = y, where t1 is a temporary and p, q, r, x and y are live on exit. 10 marks
A simple code generator translates one basic block at a time, keeping values in registers and using next-use (liveness) information to reuse registers safely. The target machine has load (LD R, x), store (ST x, R) and OP Rx, Ry, Rz, meaning Rx = Ry op Rz.
- Register descriptor: for each register, the names whose current value it holds; all registers start empty.
- Address descriptor: for each name, the locations (memory or registers) holding its current value.
For each statement x = y op z:
1. Call getReg to choose Ry and Rz for the operands and Rx for the result. 2. If y is not already in Ry, emit LD Ry, y; likewise for z and Rz. 3. Emit OP Rx, Ry, Rz and update the descriptors: Rx now holds only x, and x's only location is Rx.
A copy x = y loads y if needed and adds x to the descriptor of y's register. At the end of the block, emit ST x, R for every name live on exit whose memory copy is out of date.
getReg rules:
- Operand: a register already holding it; else an empty register; else the register needing fewest stores, first storing (spilling) each value in it that is neither in memory nor dead.
- Result: a register holding only x; else the register of an operand that is dead after the statement and alone in it; else an empty register; else a non-operand register whose value is also in memory.
Liveness: q is redefined by q = y before any use, so q is dead after statement 1, and t1 after statement 2.
Statement Code R1 R2 R3
t1 = p + q LD R1, p p t1 -
LD R2, q
ADD R2, R1, R2
x = t1 * r LD R3, r p x r
MUL R2, R2, R3
y = x - p SUB R3, R2, R1 p x y
q = y (no code) p x y,q
end ST q, R3
ST x, R2
ST y, R31. p and q go into empty R1 and R2; q is dead, so R2 is reused for t1. 2. r is loaded into R3; t1 is dead, so R2 receives x. 3. No register is empty; R3's value r is also in memory, so R3 receives y without a store. 4. The copy emits nothing: R3 now holds y and q, and q's address descriptor becomes R3. 5. q, x and y are only in registers, so they are stored; p and r are unchanged in memory.
The block needs 9 instructions and no spill, since registers of dead values were reused.
6 Explain register allocation and assignment, including usage counts and graph coloring. Allocate three registers to the block a = p + q, b = a * p, c = b - q, d = a + c, e = d * b, where p and q are live on entry and only e is live on exit. 10 marks
Instructions using registers are shorter and faster than those using memory. Register allocation chooses which values are kept in registers at each point; register assignment picks the particular register for each.
1. Global allocation with usage counts: busy variables are kept in registers across blocks, mainly inside loops, where most execution time is spent. The saving from keeping x in a register throughout a loop L is savings(x) = Σ over blocks B in L of [use(x, B) + 2 × live(x, B)], where use(x, B) is the number of uses of x in B before any definition of x there, and live(x, B) is 1 if x is assigned in B and live on exit from B (a store is saved), else 0. The variables with the largest savings get registers.
2. Graph coloring: code is first generated for unlimited symbolic registers. A register-interference graph then has one node per value and an edge between two values if one is live at a point where the other is defined. A coloring with k colors, for k registers, gives interfering values different registers. Heuristic: repeatedly remove a node with fewer than k neighbors and push it on a stack; then pop the nodes, giving each a color unused by its colored neighbors. If no node has fewer than k neighbors, a value is spilled.
Example (live sets from a backward scan):
Statement Live after
a = p + q a, p, q
b = a * p a, b, q
c = b - q a, b, c
d = a + c b, d
e = d * b ep and q are live together on entry, so the interference edges are p–q, a–p, a–q, a–b, b–q, a–c, b–c and b–d; e has no neighbor.
With k = 3, nodes are removed in the order c, d, b, a, e, p, q, each having fewer than 3 neighbors at removal. Popping in reverse order, each node takes the lowest free register (q = R1, p = R2, e = R1, a = R3, b = R2, d = R1, c = R1), giving, with p and q already in R2 and R1 on entry:
ADD R3, R2, R1 a = p + q
MUL R2, R3, R2 b = a * p
SUB R1, R2, R1 c = b - q
ADD R1, R3, R1 d = a + c
MUL R1, R1, R2 e = d * bValues with non-overlapping lifetimes share registers (b with p; c, d and e with q). The triangles a, b, q and a, b, c need three colors, so with k = 2 the heuristic gets stuck after removing d and e, forcing a spill.
Public sources that settled doubtful points
Only the points the second AI pass doubted were looked up. These are the pages that confirmed or contradicted them; nothing here is copied from them.
31 pages
- Ambiguous grammar (Wikipedia)
- Bootstrapping (compilers) (Wikipedia)
- Compilers lecture 10: types and declarations (NYU)
- DAG representation of basic blocks - NPTEL
- Thompson's construction (Wikipedia)
- Flex 2.5.4 manual: how the input is matched (GNU)
- lex: generate programs for lexical tasks (The Open Group, Single UNIX Specification)
- Regular expressions, course notes (East Carolina University)
- COMS W4115 lecture notes: LL(1) grammars and predictive parsing (Columbia University)
- LL grammar (Wikipedia)
- LALR parser (Wikipedia)
- COMS W4115 lecture notes: Yacc, ambiguous grammars and error recovery (Columbia University)
- NPTEL Compiler Design, Chapter 4: Syntax Analysis (panic-mode recovery in LR parsing)
- NPTEL Compiler Design, Chapter 4: Syntax Analysis (LALR state merging)
- L-attributed grammar (Wikipedia)
- Three-address code: quadruples, triples and indirect triples (WPI CS 544 notes)
- Backpatching (East Carolina University CSCI 4627 notes)
- Compilers lecture 10: syntax trees, DAGs and the value-number method (NYU)
- Reaching definition - Wikipedia
- Basic block - Wikipedia
- Natural Loops - WPI course notes
- Peephole optimization - Wikipedia
- Live variable analysis - Cornell CS 4120 lecture notes
- Strength reduction - Wikipedia
- Available expression - Wikipedia
- Global Register Allocation (Y. N. Srikant, NPTEL course on Compiler Design)
- NPTEL Compiler Design, Chapter 6: Runtime System (displays)
- Call stack (Wikipedia)
- NPTEL Compiler Design, Chapter 6: Activation Record
- NPTEL Compiler Design, Chapter 9: Code generation
- Concepts in Programming Languages, lecture 4 (University of Cambridge)
Further reading
Titles only, for your own study. Nothing on this page is copied from them. The units follow the official JNTUK R23 CSE syllabus (PDF) ↗.
- Compilers: Principles, Techniques and Tools · Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman
- Compiler Construction: Principles and Practice · Kenneth C. Louden
- Modern Compiler Implementation in C · Andrew W. Appel
- Optimizing Compilers for Modern Architectures · Randy Allen and Ken Kennedy
- lex & yacc · John R. Levine, Tony Mason and Doug Brown