Compiler Design Notes, IIT Delhi
Compiler Design Notes, IIT Delhi
Compiler Design Notes, IIT Delhi
Title Page
CS432F/CSL 728:
Compiler Design
July 2004
Page 1 of 100
S. Arun-Kumar
[email protected] Department of Computer Science and Engineering I. I. T. Delhi, Hauz Khas, New Delhi 110 016. July 30, 2004
Go Back
Full Screen
Close
Quit
Contents
rst The Bigpicture last rst Lexical Analysis last rst Syntax Analysis last
Context-free Grammars last rst Ambiguity last rst Shift-Reduce Parsing last rst Parse Trees last
rst
Home Page
Title Page
Page 2 of 100
Go Back
rst Semantic Analysis last rst Synthesized Attributes last rst Inherited Attributes last
Contd . . .
Quit Full Screen
Close
Home Page
Contents
. . . Contd rst Abstract Syntax Trees last rst Symbol Tables last rst Intermediate Representation last
IR: Properties Typical Instruction Set IR: Generation
Title Page
Page 3 of 100
Go Back
Full Screen
Quit
Home Page
Title Page
Page 4 of 100
Go Back
Full Screen
Close
Quit
Home Page
Title Page
Page 5 of 100
Go Back
Full Screen
Close
Quit
Home Page
Title Page
Page 6 of 100
Go Back
Full Screen
Close
Quit
Home Page
Title Page
Page 7 of 100
Go Back
Full Screen
Close
Quit
Home Page
Title Page
Page 8 of 100
Go Back
Full Screen
Close
Quit
Home Page
Title Page
Page 9 of 100
Go Back
Full Screen
Close
Quit
Home Page
Title Page
Page 10 of 100
Go Back
Full Screen
Close
Quit
Home Page
Title Page
Page 11 of 100
Go Back
Full Screen
Close
Quit
Home Page
Title Page
Page 12 of 100
Go Back
Full Screen
Close
Quit
Home Page
Title Page
Page 13 of 100
Go Back
Full Screen
Close
Quit
Home Page
Scanning: 1
Takes a stream of characters and identies tokens from
the lexemes.
Title Page
Page 14 of 100
Full Screen
Close
Quit
Home Page
Scanning: 2
Whitespace:
A sequence of space, tab, newline, carriage-return, form-feed characters etc. limited by whitespace or special characters (e.g. operators like +, -, *).
Title Page
Examples of lexemes.
Go Back
reserved words, keywords, identiers etc. Each comment is usually a single lexeme preprocessor directives
Full Screen
Close
Quit
Scanning: 3
Token: A sequence of characters to be treated as a
single unit.
Home Page
Title Page
Examples of tokens.
Reserved words (e.g. begin, end, struct, if etc.) Keywords (integer, true etc.) Operators (+, &&, ++ etc) Identiers (variable names, procedure names, parameter names) Literal constants (numeric, string, character constants etc.) Punctuation marks (:, , etc.)
Page 16 of 100
Go Back
Full Screen
Close
Quit
Home Page
Scanning: 4
Identication of tokens is usually done by a Deterministic Finite-state automaton (DFA).
Title Page
This regular expression is fed to a lexical-analyser generator such as Lex, Flex or ML-Lex.
Go Back
Quit
Scanning: 5
Home Page Title Page
09
h, j
5 09
09
09
1
chars
6 real 09
Page 18 of 100
white space 14
Go Back
other
real
Full Screen
13 error
9 error
11 )
12 comment
Close
Quit
Syntax Analysis
Consider the following two languages over an alphabet A = {a, b}.
Home Page
Title Page
R = {anbn|n < 100} P = {anbn|n > 0} R may be nitely represented by a regular expression
(even though the actual expression is very long).
Page 19 of 100
Go Back
A regular expression is not powerful enough to represent languages which require parenthesis matching to arbitrary depths.
Full Screen
All high level programming languages require an underlying language of expressions which require parentheses to be nested and matched to arbitrary depth.
Close
Quit
CF-Grammars: Denition
A context-free grammar (CFG) G = N, T , P, S consists of
Home Page
Title Page
a set N of nonterminal symbols, a set T of terminal symbols or the alphabet, a set P of productions or rewrite rules, each production is of the form X , where
X N is a nonterminal and (N T ) is a string of terminals and nonterminals
Page 20 of 100
Go Back
Full Screen
a start symbol S N .
Close
Quit
CFG: Example
G = {S }, {a, b}, P, S , where S ab and S aSb are the only productions in P .
Derivations look like this:
Home Page
Title Page
S ab
Page 21 of 100
S aSb aabb S aSb aaSbb aaabbb L(G), the language generated by G is {anbn|n > 0}.
Full Screen Go Back
Close
Quit
Home Page
Title Page
Go Back
Full Screen
S SS SSS SS . . .
Could be quite confusing!
Close
Quit
Home Page
Title Page
put an articial order in which productions are red. instead look at trees of derivations in which we may think
of productions as being red in parallel.
Page 23 of 100
Quit
Home Page
Title Page
Page 24 of 100
Go Back
Full Screen
Close
Quit
Home Page
Title Page
Page 25 of 100
Go Back
b
Full Screen
Close
Quit
Home Page
Title Page
Page 26 of 100
Go Back
b
Full Screen
Close
Quit
Home Page
Title Page
Page 27 of 100
Go Back
Full Screen
Close
Quit
Ambiguity: 1
Home Page
E I | C | E +E | E E I y | z C 4
Consider the sentence y + 4 z.
Title Page
E
Page 28 of 100
Go Back
Full Screen
Close
Quit
Ambiguity: 2
Home Page
E I | C | E +E | E E I y | z C 4
Consider the sentence y + 4 z.
Title Page
E
Page 29 of 100
E
Go Back
Full Screen
Close
Quit
Ambiguity: 3
Home Page
E I | C | E +E | E E I y | z C 4
Consider the sentence y + 4 z.
Title Page
E
Page 30 of 100
E
Go Back
* I E
E I
Full Screen
Close
Quit
Ambiguity: 4
Home Page
E I | C | E +E | E E I y | z C 4
Consider the sentence y + 4 z.
Title Page
E
Page 31 of 100
E
Go Back
* I E
E I
Full Screen
I y C
C z
Close
Quit
Ambiguity: 5
Home Page
E I | C | E +E | E E I y | z C 4
Consider the sentence y + 4 z.
Title Page
E
Page 32 of 100
E
Go Back
* I E
E I
Full Screen
I y C
C z
Close
z 4
4
Quit
Home Page
Title Page
Page 33 of 100
Go Back
Full Screen
Close
Quit
Parsing: 0
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E ) a a / b
Page 34 of 100
Go Back
Full Screen
Close
Quit
Parsing: 1
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E ) a / b
Page 35 of 100
Principle:
Reduce whenever possible. Shift only when reduce is impossible
a
Go Back
Full Screen
Close
Shift
Quit
Parsing: 2
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E ) a / b
Page 36 of 100
Go Back
Full Screen
Close
Reduce by r5
Quit
Parsing: 3
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E ) a / b
Page 37 of 100
Go Back
Full Screen
Close
Reduce by r4
Quit
Parsing: 4
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E ) a / b
Page 38 of 100
Go Back
Full Screen
Close
Reduce by r2
Quit
Parsing: 5
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
b
Page 39 of 100
Go Back
Full Screen
Close
Shift
Quit
Parsing: 6
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
b
Page 40 of 100
Go Back
Full Screen
a E
Shift
Close
Quit
Parsing: 7
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
b
Page 41 of 100
Go Back
Full Screen
D E
Reduce by r5
Close
Quit
Parsing: 8
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
b
Page 42 of 100
Go Back
Full Screen
T E
Reduce by r4
Close
Quit
Parsing: 8a
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
b
Page 43 of 100
Go Back
Full Screen
T E
Reduce by r4
Close
Quit
Parsing: 9a
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
b
Page 44 of 100
Go Back
Full Screen
Close
Reduce by r1
Quit
Parsing: 10a
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
b
Page 45 of 100
Go Back
Full Screen
Close
/ E
Shift
Quit
Parsing: 11a
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
Page 46 of 100
Go Back
Full Screen
b / E
Shift
Close
Quit
Parsing: 12a
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
Page 47 of 100
Go Back
Full Screen
D / E
Reduce by r5
Close
Quit
Parsing: 13a
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
Page 48 of 100
Go Back
Full Screen
T / E
Reduce by r4
Close
Quit
Parsing: 14a
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
Page 49 of 100
Go Back
k!
St
uc
Full Screen
Reduce by r2
Close
Get back!
/ E
Quit
Parsing: 14b
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
Page 50 of 100
Go Back
Full Screen
Reduce by r2
Close
Get back!
/ E
Quit
Parsing: 13b
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
Page 51 of 100
Go Back
Full Screen
Reduce by r4
Close
Get back!
/ E
Quit
Parsing: 12b
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
Page 52 of 100
Go Back
Full Screen
Reduce by r5
Close
Get back!
/ E
Quit
Parsing: 11b
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
Page 53 of 100
Go Back
Full Screen
Get back!
b / E
Shift
Close
Quit
Parsing: 10b
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
b
Page 54 of 100
Go Back
Full Screen
Close
Get back!
/ E
Shift
Quit
Parsing: 9b
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
b
Page 55 of 100
Go Back
Full Screen
Close
Reduce by r1
Quit
Parsing: 8b
r1. E r2 E r3 T r4 T r5 D E T T / D a | b | ( E ) D T
fied i d o m Principle:
Reduce whenever possible, but but depending upon lookahead
Home Page
Title Page
b
Page 56 of 100
Go Back
Full Screen
Reduce by r4
Close
Quit
Parsing: 8
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
b
Page 57 of 100
Go Back
Full Screen
T E
Reduce by r4
Close
Quit
Parsing: 9
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
b
Page 58 of 100
Go Back
Full Screen
/ T E
Shift
Close
Quit
Parsing: 10
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
Page 59 of 100
Go Back
b / T E
Shift
Full Screen
Close
Quit
Parsing: 11
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
Page 60 of 100
Go Back
D / T
Reduce by r5
Full Screen
Close
E
Quit
Parsing: 12
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
Page 61 of 100
Go Back
Full Screen
T E
Reduce by r3
Close
Quit
Parsing: 13
Home Page
r1. E r2 E r3 T r4 T r5 D
E T T / D a |
T
Title Page
( E )
Page 62 of 100
Go Back
Full Screen
Close
Reduce by r1
Quit
Parse Trees: 0
r1. E r2 E r3 T E T T / D T r4 T r5 D D a | b | ( E )
Home Page
Title Page
Page 63 of 100
Go Back
Full Screen
Close
b
Quit
Parse Trees: 1
r1. E r2 E r3 T E T T / D T r4 T r5 D D a | b | ( E )
Home Page
Title Page
Page 64 of 100
Go Back
Full Screen
D
Close
b
Quit
Parse Trees: 2
r1. E r2 E r3 T E T T / D T r4 T r5 D D a | b | ( E )
Home Page
Title Page
Page 65 of 100
Go Back
T
Full Screen
D
Close
b
Quit
Parse Trees: 3
r1. E r2 E r3 T E T T / D T r4 T r5 D D a | b | ( E )
Home Page
Title Page
Page 66 of 100
E
Go Back
T
Full Screen
D
Close
b
Quit
Parse Trees: 3a
r1. E r2 E r3 T E T T / D T r4 T r5 D D a | b | ( E )
Home Page
Title Page
Page 67 of 100
E
Go Back
T
Full Screen
D
Close
b
Quit
Parse Trees: 3b
r1. E r2 E r3 T E T T / D T r4 T r5 D D a | b | ( E )
Home Page
Title Page
Page 68 of 100
E
Go Back
T
Full Screen
D
Close
b
Quit
Parse Trees: 4
r1. E r2 E r3 T E T T / D T r4 T r5 D D a | b | ( E )
Home Page
Title Page
Page 69 of 100
E
Go Back
T
Full Screen
D
Close
b
Quit
Parse Trees: 5
r1. E r2 E r3 T E T T / D T r4 T r5 D D a | b | ( E )
Home Page
Title Page
Page 70 of 100
E
Go Back
T
Full Screen
D
Close
b
Quit
Parse Trees: 5a
r1. E r2 E r3 T E T T / D T r4 T r5 D D a | b | ( E )
Home Page
Title Page
Page 71 of 100
E
Go Back
T
Full Screen
D
Close
b
Quit
Parse Trees: 5b
r1. E r2 E r3 T E T T / D T r4 T r5 D D a | b | ( E )
Home Page
Title Page
Page 72 of 100
E
Go Back
T
Full Screen
D
Close
b
Quit
Parse Trees: 6
r1. E r2 E r3 T E T T / D T r4 T r5 D D a | b | ( E )
Home Page
Title Page
Page 73 of 100
E
Go Back
T
Full Screen
D
Close
b
Quit
Parse Trees: 7
r1. E r2 E r3 T E T T / D T r4 T r5 D D a | b | ( E )
Home Page
Title Page
Page 74 of 100
T
Go Back
T
Full Screen
D
Close
b
Quit
Parse Trees: 8
r1. E r2 E r3 T E T T / D T r4 T r5 D D a | b | ( E )
Home Page
Title Page
Page 75 of 100
T
Go Back
T
Full Screen
D
Close
b
Quit
Home Page
Parsing: Summary: 1
All high-level languages are designed so that they may
be parsed in this fashion with only a single token lookahead.
Title Page
Parsers for a language can be automatically constructed by parger-generators such as Yacc, Bison, MLYacc.
Page 76 of 100
Go Back
Full Screen
Close
Quit
Parsing: Summary: 2
Very often shift-reduce conicts may occur because
of the prex problem. In such cases many parsergenerators resolve the conict in favour of shifting.
Home Page
Title Page
Go Back
Close
Quit
Semantic Analysis: 1
Every Programming langauge can be used to program
any computable function, assuming of course, it has unbounded memory, and unbounded time
Home Page
Title Page
Go Back
Full Screen
Close
Quit
Home Page
Semantic Analysis: 2
There are context-sensitive aspects of a program that
cannot be represented/enforced by a context-free grammar denition. Examples include correspondence between formal and actual parameters type consistency between declaration and use. scope and visibility issues with respect to identiers in a program.
Title Page
Page 79 of 100
Go Back
Full Screen
Close
Quit
Home Page
Title Page
Page 80 of 100
Go Back
Full Screen
Close
Quit
Synthesized Attributes: 0
E / T ( F ) n T E
Home Page
Title Page
T /
Page 81 of 100
n F
( E
Go Back
)
Full Screen
Close
F n
Quit
n
Synthesized Attributes: 1
E / T ( F ) n T E
Home Page
Title Page
T /
Page 82 of 100
n F
( E
Go Back
)
Synthesized Attributes 4 3 2 1
Full Screen
Close
F n
Quit
4 n
Synthesized Attributes: 2
E / T ( F ) n T E
Home Page
Title Page
T /
Page 83 of 100
n F
( E
Go Back
)
Synthesized Attributes 4 3 2 1
Full Screen
Close
F n
Quit
4 n
Synthesized Attributes: 3
E / T ( F ) n T E
Home Page
Title Page
T /
Page 84 of 100
n F
( E
Go Back
)
Full Screen
Synthesized Attributes 4 3 2 1
Close
F n
Quit
4 n
Synthesized Attributes: 4
E / T ( F ) n T E
Home Page
Title Page
T /
Page 85 of 100
n F
( E
Go Back
)
Synthesized Attributes 4 3 2 1
Full Screen
Close
F n
Quit
4 n
Synthesized Attributes: 5
E / T ( F ) n T E
Home Page
Title Page
T /
Page 86 of 100
n F
( E
Go Back
)
Full Screen
Synthesized Attributes 4 3 2 1
Close
F n 1
Quit
4 n
Synthesized Attributes: 6
E / T ( F ) n T E
Home Page
Title Page
T /
Page 87 of 100
n F
( E
Go Back
)
Full Screen
Synthesized Attributes 4 3 2 1
Close
F n 1
Quit
4 n
Synthesized Attributes: 7
E / T ( F ) n T E
Home Page
Title Page
T /
Page 88 of 100
n F
( E
Go Back
)
Synthesized Attributes 4 3 2 1
Full Screen
Close
F n 1
Quit
4 n
Synthesized Attributes: 8
E / T ( F ) n T E
Home Page
Title Page
T /
Page 89 of 100
n F
( E 3
Go Back
)
Full Screen
Synthesized Attributes 4 3 2 1
Close
F n 1
Quit
4 n
Synthesized Attributes: 9
E / T ( F ) n T E
Home Page
Title Page
T /
Page 90 of 100
F 3 n
( E 3
Go Back
)
Full Screen
Synthesized Attributes 4 3 2 1
Close
F n 1
Quit
4 n
Synthesized Attributes: 10
E / 3 / T ( F ) n T E
Home Page
Title Page
Page 91 of 100
F 3 n
( E 3
Go Back
)
Full Screen
Synthesized Attributes 4 3 2 1
Close
F n 1
Quit
4 n
Synthesized Attributes: 11
E / 3 / T ( F ) n T E
Home Page
Title Page
Page 92 of 100
F 3 n 2
( E 3
Go Back
)
Synthesized Attributes 4 3 2 1
Full Screen
Close
F n 1
Quit
4 n
Synthesized Attributes: 12
E / 3 / T ( F ) n T E
Home Page
Title Page
Page 93 of 100
F 3 n 2
( E 3
Go Back
)
Synthesized Attributes 4 3 2 1
Full Screen
Close
F n 1
Quit
4 n
Synthesized Attributes: 13
E / 3 / T ( F ) n T 1 E
Home Page
Title Page
Page 94 of 100
F 3 n 2
( E 3
Go Back
)
Full Screen
Synthesized Attributes 4 3 2 1
Close
F n 1
Quit
4 n
Synthesized Attributes: 14
E / 3 / T ( F ) n T 1 E 1
Home Page
Title Page
Page 95 of 100
F 3 n 2
( E 3
Go Back
)
Synthesized Attributes 4 3 2 1
Full Screen
Close
F n 1
Quit
4 n
An Attribute Grammar
E 1
Home Page
Title Page
E0 E1T E T
F 2 n 2
3 /
T0 T1/F T F F F (E ) n
( E 3
T.val := F.val
Go Back
F.val := E.val
Full Screen
F n 1
F.val := n.val
Close
Quit
Inherited Attributes: 0
C -style declarations generating int x, y, z. D TL L L,I | I
D
Home Page
T int | oat I x | y | z
Title Page
I int , L z I L ,
Go Back Page 97 of 100
y I D L T I
Full Screen
Close
int
x
Quit
Inherited Attributes: 1
C -style declarations generating int x, y, z. D TL L L,I | I
D
Home Page
T int | oat I x | y | z
Title Page
I int int , L z I L ,
Go Back Page 98 of 100
y I D L T I
Full Screen
Close
int
x
Quit
int
Inherited Attributes: 2
C -style declarations generating int x, y, z. D TL L L,I | I
D
Home Page
T int | oat I x | y | z
Title Page
int
I int int , L z I L ,
Go Back Page 99 of 100
y I D L T I
Full Screen
Close
int
x
Quit
int
int
Inherited Attributes: 3
C -style declarations generating int x, y, z. D TL L L,I | I
D
Home Page
T int | oat I x | y | z
Title Page
int
int
I int int , L z I L ,
Go Back Page 100 of 100
y I D L T I
Full Screen
Close
int
x
Quit
int
int
Inherited Attributes: 4
C -style declarations generating int x, y, z. D TL L L,I | I
D
Home Page
T int | oat I x | y | z
Title Page
int
int
int
Page 101 of 100
z I L ,
Go Back
y I D L T I
Full Screen
Close
int
x
Quit
int
int
Inherited Attributes: 5
D int T L int I int int , L int z I L int , int int int
Home Page
Title Page
y I D L T I
Go Back
Full Screen
int
x
Close
int
int
Quit
Inherited Attributes: 6
C -style declarations generating int x, y, z. D TL L L,I | I
D
Home Page
T int | oat I x | y | z
Title Page
int
int
int
Page 103 of 100
z I L int , int
int
Go Back
y I D L T I int
int
Full Screen
Close
int
x
Quit
int
int
Inherited Attributes: 7
C -style declarations generating int x, y, z. D TL L L,I | I
D
Home Page
T int | oat I x | y | z
Title Page
int
int
int
Page 104 of 100
z I L int , int
int
Go Back
y I D L T I int
int
Full Screen
Close
int
int
Quit
int
int
An Attribute Grammar
D
Home Page
Title Page
D TL
L int I int
int
int
int
T T
int oat
y I int
int
L0 L1,I L I I id
L1 := L0.in
Go Back
int
I.in := L.in
Full Screen
id.type := I.in
Close
Quit
Home Page
Title Page
Go Back
Full Screen
Close
Quit
Abstract Syntax: 0
E E T | T T T /F | F F n | (E )
Suppose we want to evaluate an expression (4 1)/2. What we actually want is a tree that looks like this:
Home Page Title Page
/
Go Back
Full Screen
Close
1
Quit
Evaluation: 0
/
Home Page
Title Page
2
Go Back
Full Screen
1
Close
Quit
Evaluation: 1
/
Home Page
Title Page
2
Go Back
Full Screen
1
Close
Quit
Evaluation: 2
/
Home Page
Title Page
2
Go Back
Full Screen
Close
Quit
Evaluation: 3
/
Home Page
Title Page
2
Go Back
Full Screen
Close
Quit
Evaluation: 4
Home Page Title Page
Go Back
Full Screen
Close
But what we actually get during parsing is a tree that looks like . . .
Quit
Abstract Syntax: 1
. . . THIS!
E
Home Page Title Page
T /
n F
( E
/
E T
Go Back
T F
Full Screen
n
F n
Close
Quit
Abstract Syntax: 2
We use attribute grammar rules to construct the abstract syntax tree (AST)!. But in order to do that we rst require two procedures for tree construction. makeLeaf(literal) : Creates a node with label literal and returns a pointer to it. makeBinaryNode(opr, opd1, opd2) : Creates a node with label opr (with elds which point to opd1 and opd2) and returns a pointer to the newly created node. Now we may associate a synthesized attribute called ptr with each terminal and nonterminal symbol which points to the root of the subtree created for it.
Home Page
Title Page
Go Back
Full Screen
Close
Quit
Abstract Syntax: 3
E0 E1T E T T0 T1/F T F F F (E ) n E0.ptr := makeBinaryN ode(, E1.ptr, T.ptr) E.ptr := T.ptr T0.ptr := makeBinaryN ode(/, T1.ptr, F.ptr)
Home Page
Title Page
T.ptr := F.ptr
Go Back
F.ptr := E.ptr
Full Screen
Home Page
Symbol Table:1
The store house of context-sensitive and run-time information about every identier in the source program.
Title Page
Close
Quit
Home Page
Symbol Table:2
Attributes stored in a symbol table for each identier:
Title Page
type size scope/visibility information base address addresses to location of auxiliary symbol tables (in case
of records, procedures, classes)
Page 117 of 100
Go Back
address of the location containing the string which actually names the identier and its length in the string pool
Full Screen
Close
Quit
Home Page
Symbol Table:3
A symbol table exists through out the compilation and
run-time.
Title Page
Go Back
Full Screen
Close
Quit
Symbol Table:4
Accesses to the symbol table at every stage of the compilation process, Scanning: Insertion of new identiers. Parsing: Access to the symbol table to ensure that an operand exists (declaration before use).
Home Page
Title Page
Semantic analysis: Determination of types of identiers from declarations type checking to ensure that operands are used in type-valid contexts. Checking scope, visibility violations.
Go Back
Full Screen
Close
Quit
Home Page
Symbol Table:5
IR generation: . Memory allocation and relativea address calculation. Optimization: All memory accesses through symbol table Target code: Translation of relative addresses to absolute addresses in terms of word length, word boundary etc. The Big picture
a
Title Page
Go Back
Full Screen
Close
Quit
Intermediate Representation
Intermediate representations are important for reasons of portability.
Home Page
Title Page
Full Screen
Close
Quit
IR Properties: 1
1. It is fairly low-level containing instructions common to all target architectures and assembly languages. How low can you stoop? . . . 2. It contains some fairly high-level instructions that are common to most high-level programming languages. How high can you rise? 3. To ensure portability
Home Page Title Page
an unbounded number of variables and memory locations no commitment to Representational Issues 4. To ensure type-safety
Go Back
Full Screen
Quit
Home Page
IR: Representation?
No commitment to word boundaries or byte boundaries No commitment to representation of
int vs. oat, oat vs. double, packed vs. unpacked, strings where and how?.
Title Page
Go Back
Back to IR Properties:1
Full Screen
Close
Quit
Home Page
Title Page
so as to be interpreted easily, the interpreter is fairly small, execution speeds are high, to have xed length instructions (where each operand
position has a specic meaning). Back to IR Properties:1
Full Screen Page 124 of 100
Go Back
Close
Quit
Home Page
Title Page
Go Back
Full Screen
Close
Quit
Home Page
Title Page
Close
Quit
Home Page
Title Page
Go Back
Full Screen
Close
Quit
Home Page
Title Page
Jumps (conditional and unconditional) Procedures and parameters Arrays and array-indexing Pointer Referencing and Dereferencing
Go Back
Full Screen
Close
Quit
Home Page
Title Page
Go Back
Procedures and parameters Arrays and array-indexing Pointer Referencing and Dereferencing
Full Screen
Close
Quit
Home Page
Title Page
Go Back
Full Screen
Close
Quit
Home Page
Title Page
Go Back
Full Screen
Close
Home Page
Title Page
Go Back
Full Screen
Close
Quit
Pointers
x *x *y y x := ^y @y x *y y
Home Page
Title Page
x *x @z
y *z x := *y *z z y *y
x @z
*z z y *y x *x := y z @z *y
Quit Full Screen Go Back
x @z *z
z
Close
IR: Generation
Can be generated by recursive traversal of the abstract
syntax tree.
Home Page
Title Page
Can be generated by syntax-directed translation as follows: For every non-terminal symbol N in the grammar of the source language there exist two attributes N.place , which denotes the address of a temporary variable where the result of the execution of the generated code is stored N.code , which is the actual code segment generated.
Page 134 of 100
Go Back
In addition a global counter for the instructions generated is maintained as part of the generation process.
Full Screen
It is independent of the source language but can express target machine operations without committing to too much detail.
Close
Quit
IR: Infrastructure
Given an abstract syntax tree T, with T also denoting its root node. T.place address of temporary variable where result of execution of the T is stored. newtemp returns a fresh variable name and also installs it in the symbol table along with relevant information T.code the actual sequence of instructions generated for the tree T. newlabel returns a label to mark an instruction in the generated code which may be the target of a jump. emit emits an instructions (regarded as a string).
Home Page
Title Page
Go Back
Full Screen
Close
Quit
Home Page
IR: Infrastructure
Colour and font coding of IR code generation
Title Page
Green: Nodes of the Abstract Syntax Tree Brown: Characters and strings of the Intermediate
Representation
Go Back
Quit
IR: Example
E id E.place := id.place; E.code := emit()
Home Page
Title Page
E0
E1 E2
Go Back
Full Screen
Close
Quit
IR: Example
Home Page
S S.code S0
Title Page
S0.begin := newlabel; S0.af ter := newlabel; S0.code := emit(S0.begin:) || E.code || emit(if E.place= 0 goto S0.af ter) || S1.code || emit(gotoS0.begin) || emit(S0.af ter:)
Go Back
Full Screen
Close
Quit
IR: Example
Home Page
S S.code S0
Title Page
S0.begin := newlabel; S0.af ter := newlabel; S0.code := emit(S0.begin:) || E.code || emit(if E.place= 0 goto S0.af ter) || S1.code || emit(gotoS0.begin) || emit(S0.af ter:)
Go Back
Full Screen
Close
Quit
IR: Generation
While generating the intermediate representation, it is sometimes necessary to generate jumps into code that has not been generated as yet (hence the address of the label is unknown). This usually happens while processing
Home Page
Title Page
Go Back
Full Screen
Close
Quit
A Calling Chain
Main program Globals Procedure P2 Locals of P2 Procedure P21 Locals of P21 Body of P21
Home Page
Title Page
Call P21
Page 141 of 100
Body of P2
Call P21
Go Back
Call P2
Main body
Close
Call P1
Quit
Run-time Structure: 1
Main program Globals Procedure P2 Locals of P2 Procedure P21 Locals of P21
Home Page
Title Page
Main body
Globals
Quit
Run-time Structure: 2
Main program Globals Procedure P2 Locals of P2 Procedure P21 Locals of P21
Home Page
Title Page
Return address to Main Dynamic link to Main Locals of P1 Static link to Main Formal par of P1 Globals
Full Screen
Close
Main body
Quit
Run-time Structure: 3
Main program Globals Procedure P2 Locals of P2 Procedure P21 Locals of P21 Return address to last of P1 Dynamic link to last P1 Locals of P2 Static link to last P1 Formal par P2 Return address to Main Dynamic link to Main Locals of P1 Static link to Main Formal par of P1 Globals
Home Page
Title Page
Go Back
Full Screen
Close
Main body
Quit
Run-time Structure: 4
Main program Globals Procedure P2 Locals of P2 Procedure P21 Locals of P21 Return address to last of P2 Dynamic link to last P2 Locals of P21 Static link last P2 Formal par P21 Return address to last of P1 Dynamic link to last P1 Locals of P2 Static link to last P1 Formal par P2 Return address to Main Dynamic link to Main Locals of P1 Static link to Main Formal par of P1 Globals
Home Page
Title Page
Go Back
Full Screen
Close
Main body
Quit
Run-time Structure: 5
Main program Globals Procedure P2 Locals of P2 Procedure P21 Locals of P21 Return address to last of P2 Dynamic link to last P2 Locals of P21 Static link last P2 Formal par P21 Return address to last of P1 Dynamic link to last P1 Locals of P2 Static link to last P1 Formal par P2 Return address to Main Dynamic link to Main Locals of P1 Static link to Main Formal par of P1 Globals Return address to last of P21 Dynamic link to last P21 Locals of P21 Static link to last P2 Formal par P21
Home Page
Title Page
Go Back
Full Screen
Close
Main body
Quit
Home Page
Title Page
Go Back
Full Screen
Close
Quit