Principles of Programming Languages
h"p://www.di.unipi.it/~andrea/Dida2ca/PLP-‐14/
Prof. Andrea Corradini
Department of Computer Science, Pisa
• Overview of a Simple Compiler Front-‐end
– Lexical analysis
– Intermediate code generaBon – StaBc checking
Lesson 3!
Admins
• Office Hours:
– Wednesday, 9 -‐ 11
• Check your data and add the University ID (matricola) in the sheet
2
Compiler Front-‐ and Back-‐end
Seman&c Analysis Scanner
(lexical analysis)
Parser
(syntax analysis)
Machine-‐Independent Code Improvement
Target Code Genera&on
Machine-‐Specific Code Improvement Source program (character stream)
Tokens
Parse tree
Abstract syntax tree, or …
Modified intermediate form
Assembly or object code
F ron t e n d an al ys is Bac k e n d syn th es is
Intermediate Code Genera&on
Three address code, or…
4
A Translator for Simple Expressions based on PredicBve Parsing and SemanBc AcBons
expr → expr + term expr → expr - term expr → term
term → 0 term → 1
…
term → 9
{ print(“+”) } { print(“-”) }
{ print(“0”) } { print(“1”) }
…
{ print(“9”) }
expr → term rest
rest → + term { print(“+”) } rest rest → - term { print(“+”) } rest rest → ε
term → 0 { print(“0”) } term → 1 { print(“1”) }
…
term → 9 { print(“9”) }
After left recursion elimination:
main()
{ lookahead = getchar();
expr();
}
expr()
{ term();
while (1) /* optimized by inlining rest() and removing recursive calls */
{ if (lookahead == ‘+’)
{ match(‘+’); term(); putchar(‘+’);
}
else if (lookahead == ‘-’)
{ match(‘-’); term(); putchar(‘-’);
}
else break;
} }
term()
{ if (isdigit(lookahead))
{ putchar(lookahead); match(lookahead);
}
else error();
}
match(int t)
{ if (lookahead == t)
lookahead = getchar();
else error();
}
error()
{ printf(“Syntax error\n”);
expr → term rest
term → 0 { print(“0”) } term → 1 { print(“1”) }
…
term → 9 { print(“9”) }
OpBmized code of the translator
rest → + term { print(“+”) } rest rest → - term { print(“-”) } rest rest → ε
The Structure of the Front-‐End
Source Program (Character
stream)
Token stream
Intermediate representation Develop
parser and code
generator for translator
IR specificaBon Lexical analyzer Syntax-‐directed
translator
Syntax definiBon (BNF grammar)
Adding a Lexical Analyzer
• Typical tasks of the lexical analyzer:
– Remove white space and comments – Encode constants as tokens
– Recognize keywords
– Recognize idenBfiers and store idenBfier names in
a global symbol table
The Lexical Analyzer (“lexer”)
Lexical analyzer
<id, “ y”> < assign, > <num, 31> <‘+’, > <num, 28> <‘*’, > <id, “ x”>
y := 31 + 28*x
Parser
token
(lookahead)
tokenval (token attribute)
The lookahead of the Parser can be a token, not just a character
Token A[ributes
factor → ( expr )
| num { print(num.value) }
#define NUM 256 /* token returned by lexer */
factor()
{ if (lookahead == ‘(‘)
{ match(‘(‘); expr(); match(‘)’);
}
else if (lookahead == NUM)
{ printf(“ %d “, tokenval); match(NUM);
}
else error();
The parser accesses the token via lookahead, and
the token a[ribute via the global variable tokenval
Symbol Table
insert(s, t)
: returns array index to new entry for string s token t
lookup(s)
: returns array index to entry for string s or 0
The symbol table is globally accessible (to all phases of the compiler) Each entry in the symbol table contains a string and a token value:
struct entry
{ char *lexptr; /* lexeme (string) for tokenval */
int token;
};
struct entry symtable[];
Possible implementaBons:
-‐ simple C code -‐ hashtables
Handling idenBfiers (lexer)
Code executed by the lexer after an identifier has been recognized (stored in lexbuf):
/* lexer.c */
int lexan() { …
tokenval = lookup(lexbuf);
if (tokenval == 0) /* not found */
tokenval = insert(lexbuf, ID);
return symtable[tokenval].token;
}
Handling idenBfiers (parser)
factor → ( expr )
| id { print(id.string) }
#define ID 259 /* token returned by lexer */
factor()
{ if (lookahead == ‘(‘)
{ match(‘(‘); expr(); match(‘)’);
}
else if (lookahead == ID)
{ printf(“ %s “, symtable[tokenval].lexptr);
match(ID);
}
else error();
} provided by the lexer for ID
Handling Reserved Keywords (lexer)
/* global.h */
#define DIV 257 /* token */
#define MOD 258 /* token */
#define ID 259 /* token */
/* init.c */
insert(“div”, DIV);
insert(“mod”, MOD);
/* lexer.c */
int lexan() { …
tokenval = lookup(lexbuf);
if (tokenval == 0) /* not found */
tokenval = insert(lexbuf, ID);
return symtable[tokenval].token;
Simply initialize the global symbol table
with the set of
keywords
Handling Reserved Keywords (parser)
morefactors → div factor { print(‘DIV’) } morefactors | mod factor { print(‘MOD’) } morefactors | …
/* parser.c */
morefactors()
{ if (lookahead == DIV)
{ match(DIV); factor(); printf(“DIV”); morefactors();
}
else if (lookahead == MOD)
{ match(MOD); factor(); printf(“MOD”); morefactors();
} else … }
Symbol Tables and Scopes
• The same idenBfier can be declared several Bmes in a program (e.g. in different blocks)
• Each declaraBon has its own a[ributes (e.g.
type)
• A soluBon: one Symbol Table per scope
– Chain of symbol tables for nested blocks – Hash table + auxiliary stack
– Entries have to be created by the parser
The Structure of the Front-‐End
Source Program (Character
stream)
Token stream
Intermediate representation Develop
parser and code
generator for translator
Syntax-‐directed translator
Syntax definiBon (BNF grammar) Lexical analyzer
IR specificaBon
Intermediate Code GeneraBon
• Two main kinds of intermediate representaBons:
– Trees (parse trees, abstract syntax trees)
• Useful for staBc semanBc analysis (“staBc checking”)
– Linear representaBons (“three-‐address code”)
• Good for machine-‐independent opBmizaBon
• Oaen compilers produce the linear code
during on-‐the-‐fly generaBon of the syntax tree
TranslaBon Scheme for generaBng the Abstract Syntax Tree: Expressions
• Each operator is a node, with “semanBcally meaningful components” as children
• For each producBon the semanBc acBon either builds a new node (with suitable parameters), or returns the node of the only subexpression
18
¾|Ϯ ̓h~̓ ̓ ̓·̓ ̓
ǐ+ ͆ Ϗ )&͆ ;͆ᅼዏᎰᅼཱུᗮ)&͆͆ j͆
)&͆ Ϗ ·ϮÎĈϮ ͆ĈĈϮ ;͆ )&͆͆'R ͆͆j͆
͆ Ϗ ͆ ͆ ;͆ -͆'R 'ɼ V͆? -͆ -8 ͆ j͆
8j 5ҿ ;͆ ͆-͆ 'R ŸŽNjNj͆ j͆
͆ Ϗ ñ͆ ;͆ -͆'R 'ɼ> ? -8 ͆ j͆
$
:ɼ͆ ͆ ė͆;͆ -͆'R'ɼ¼? -͆ -8 ͆ j͆
'ɼ ͆ ͆ ė͆
;͆ -͆'R'ɼ ƺ5͆? -͆ -8 ͆ j͆
ɼ ͆ 'ɼ ͆ ͆͆ñ͆
; -͆'R 'ɼ,ʙ ? - -8 j͆
)&͆ ;͆ -͆'R )&͆j͆
͆ Ϗ ͆Ϯ ͆ ;͆ -͆'R 'ɼx5͆˘ 'R-͆ -8͆ j͆
8j ͆ ;͆ -͆'R ͆͆ j͆
͆ ҿ ŭ͆ Ϯ ͆ ;͆ -͆'R 'ɼ ?Ĩ͆ -͆ -8 ͆ j͆
$
ŭ͆ Ϯ ͆ ;͆ -͆'R 'ɼ ?ɐɑ͆ŭ -͆ -8͆j͆$
͆ ;͆ ͆'R ͆ j͆͆ Ϗ b͆ n͆ ͆ ;͆ -͆'R 'ɼ Ĭ ?Ê͆ Ɇ -͆ -8 ͆ j͆
͆ ;͆ -͆ 'R -͆ j͆
͆ Ϗ ͆ É͆͆ ;͆ -͆'R'ɼ Ĭ ͆ ··.Ϯ - -8 ͆ j͆
Â؛ ͆ ;͆ -͆'R-͆j͆
͆ ҿ ͆ ͆ ;͆-͆'R -͆j͆
ŸŽǍ͆ ; -͆'R 'ɼ ?ŸŽǍ 8 ͆ j͆
֍್ஸᎰᅼᗮIK¾ƒϮԦအཱུበዏᅼᎰ।ዏ್အཱུᗮအᗮበᒹཱུዏࡐᒏᗮዏᅼበᗮအᅼᗮᒏႼᅼበበ್အཱུበᗮࡐཱུূᗮበዏࡐዏ༌ཱུዏበᗮ
TranslaBon Scheme for generaBng the Abstract Syntax Tree: Statements
• Statements as operators: note that the concrete syntax is dropped
19
¾|Ϯ
̓h~̓ ̓ ̓·̓ ̓
ǐ+ ͆ Ϗ )&͆ ;͆
ᅼዏᎰᅼཱུᗮ
)&͆͆ j͆)&͆ Ϗ ·ϮÎĈϮ ͆ĈĈϮ ;͆ )&͆͆'R ͆͆j͆
͆ Ϗ ͆ ͆ ;͆ -͆'R 'ɼ V͆? -͆ -8 ͆ j͆
8j
5ҿ ;͆ ͆-͆ 'R ŸŽNjNj͆ j͆͆ Ϗ ñ͆ ;͆ -͆'R 'ɼ> ? -8 ͆ j͆
$
:ɼ͆ ͆ ė͆;͆ -͆'R'ɼ¼? -͆ -8 ͆ j͆
'ɼ ͆ ͆ ė͆
;͆ -͆'R'ɼ ƺ5͆? -͆ -8 ͆ j͆
ɼ ͆ 'ɼ ͆ ͆͆ñ͆
; -͆'R 'ɼ,ʙ ? - -8 j͆
)&͆ ;͆ -͆'R )&͆j͆
͆ Ϗ ͆Ϯ ͆ ;͆ -͆'R 'ɼx5͆˘ 'R-͆ -8͆ j͆
8j
͆ ;͆ -͆'R ͆͆ j͆͆ ҿ ŭ͆ Ϯ ͆ ;͆ -͆'R 'ɼ ?Ĩ͆ -͆ -8 ͆ j͆
$
ŭ͆ Ϯ ͆ ;͆ -͆'R 'ɼ ?ɐɑ͆ŭ -͆ -8͆j͆$
͆ ;͆ ͆'R ͆ j͆͆ Ϗ b͆ n͆ ͆ ;͆ -͆'R 'ɼ Ĭ ?Ê͆ Ɇ -͆ -8 ͆ j͆
͆ ;͆ -͆ 'R -͆ j͆
͆ Ϗ ͆ É͆͆ ;͆ -͆'R'ɼ Ĭ ͆ ··.Ϯ - -8 ͆ j͆
Â؛
͆ ;͆ -͆'R-͆j͆͆ ҿ ͆ ͆ ;͆-͆'R -͆j͆
ŸŽǍ͆ ; -͆'R 'ɼ ?ŸŽǍ 8 ͆ j͆
An example: from a statement to the abstract syntax tree
<if> <(> <id, "peek"> <eq> <const, '\n'> <)>
<id, "line"> <assign> <id, "line"> <+> <num, 1> <;>
if ( peek == '\n' ) line = line + 1;
stmt
if ( expr ) stmt rel expr
rel == add rel = expr add term add rel term factor term add
factor num factor add + term id id term factor factor num id
+ -̓ ̓hm̓ ̓ ̓Ŭ̓ ̓
ªÁ
*" E 7 +EKKҿ 2 E E .*2 E Kҿ .*2 E - -
QÑwr§à
¬r§ÔÖºà)$E˔ԕД) E 7 +E 8 E 41:=E 2 E E
) E .*2 E::)&1E ) E .*2 E˓Г1>/E B E
)1=E
2 EˬϏ
cÔ¬ÃrÑ BºwÃ}àir¬À§rðºà
3
:)ÊÐ
§Á ҿ ӌ Ǎ
§Á ҿ
ѰҀҿ
%B *-- Kҿ *2E*- ѓDEE
- *#E.; E 7 +E KKҿ * - '*'- Ӳ
@ԉ .*2 E Kҿ .*2 E - -
"&B
֎೬ஸᎰᅻᗮ -È̓ ݬᑌအᗮႼအበበ೬࣓เᗮዏᅻࡐཱུበเࡐዏ೬အཱུበᗮအᗮࡐᗮበዏࡐዏ༌ཱུዏᗮ
ùᗮ ݬఀᗮበዏࡐᅻዏ೬ཱུஸᗮႼအ೬ཱུዏᗮအᅻᗮࡐᗮበᒹཱུዏࡐᒏƗূ೬ᅻहዏূᗮዏᅻࡐཱུበเࡐዏအᅻᗮ೬በᗮࡐᗮஸᅻࡐ༌༌ࡐᅻᗮအᅻᗮዏఀᗮ በအᎰᅻहᗮเࡐཱུஸᎰࡐஸȫᗮ ӕᗮ ͆ূበहᅻ೬࣓በᗮዏఏᗮఀ೬ᅻࡐᅻहఀ೬हࡐเᗮበዏᅻᎰहዏᎰᅻᗮအᗮႼᅻအᔳ ஸᅻࡐཪበȫᗮ ዏᗮ೬በᗮূ୳ཱུূᗮ೬ཱུᗮዏᅻ༌በᗮအᗮเ༌ཱུዏࡐᅻᒹᗮበᒹ༌࣓အเበᗮहࡐเเূᗮ ͆ࡐཱུূᗮ ᐟࡐᅻ೬ࡐ࣓เᗮበᒹ༌࣓အเበᗮहࡐเเ্ᗮ ƒ͆ ݬఀበᗮበᒹ༌࣓အเበᗮᅻႼᅻበཱུዏᗮเࡐཱུஸᎰࡐஸᗮ हအཱུበዏᅻᎰहዏበȫᗮݬఀᗮᅻᎰเበᗮအᅻᗮ Ą ͆အᗮࡐᗮஸᅻࡐ༌༬ࡐᅻᗮहအཱུበ೬በዏᗮအᗮࡐᗮཱུအཱུዏᅻ༌೬ཱུࡐไᗮ हࡐเเূᗮዏఀᗮĄ͆အᅻᗮø͆ Ą͆အᗮࡐᗮႼᅻအূᎰहዏ೬အཱུᗮࡐཱུূᗮࡐᗮበᅍᎰཱུहᗮအᗮዏᅻ༌೬ཱུࡐเበᗮ ࡐཱུূᗮཱུအཱུዏፊ༌೬ཱུࡐเበᗮहࡐเเূᗮዏఀᗮ)Ą͆အᅻᗮ ͆ Ą͆အ૨ᗮዏఀᗮႼᅻအূᎰहዏ೬အཱུȫᗮ ཱུۖᗮ
ཱུအཱུዏᅻ༌೬ཱུࡐเᗮ೬በᗮূበ೬ஸཱུࡐዏূᗮࡐበᗮዏఀᗮ͆በᒹ༌रအเȫᗮ
ùᗮ ཱུᗮበႼह೬૧ᒹ೬ཱུஸᗮࡐᗮዏᅻࡐཱུበเࡐዏအᅻýᗮ೬ዏᗮ೬በᗮఀเႼᎰเᗮዏအᗮࡐዏዏࡐहఀᗮࡐዏዏሾ೬࣓ᎰዏበᗮዏအᗮႼᅻအஸᅻࡐ༌༌೬ཱུஸᗮ हအཱུበዏᅻᎰहዏýᗮᑌఀᅻᗮࡐཱུᗮ )͆೬በᗮࡐཱུᒹᗮᅍᎰࡐཱུዏ೬ዏᒹᗮࡐበበအह೬ࡐዏূᗮᑌ೬ዏఀᗮࡐᗮहအཱུበዏᅻᎰहዏȫᗮ
ܺ೬ཱུहᗮ हအཱུበዏᅻᎰहዏበᗮ ࡐᅻᗮ ᅻႼᅻበཱུዏূᗮ ࣓ᒹᗮ ஸᅻࡐ༌༌ࡐᅻᗮ በᒹ༌࣓အเበýᗮ ዏఀᗮ हအཱུहႼዏᗮ အᗮ ࡐዏዏᅻ೬࣓Ꮀዏበᗮᒏዏ྆ূበᗮዏအᗮஸᅻࡐ༚༌ࡐᅻᗮበᒹ༌࣓အเበȫᗮ իᒏࡐ༌Ⴜเበᗮ အᗮࡐዏዏᅻ೬࣓Ꮀዏበᗮ೬ཱུहเᎰূᗮ ࡐཱུᗮ೬ཱུዏஸᅻᗮᐟࡐเᎰᗮࡐበበအह೬ࡐዏূᗮᑌ೬ዏఀᗮࡐᗮዏᅻ༌೬ཱུࡐเᗮ# ɼᅽႼᅻበཱུዏ೬ཱུஸᗮཱུᎰ༌࣓ᅻበýᗮ ࡐཱུূᗮࡐᗮበዏᅻ೬ཱུஸᗮࡐበበအह೬ࡐዏূᗮᑌ೬ዏఀᗮࡐᗮዏᅻ༌೬ཱུࡐเᗮȉ̺ϮᅻႼᅻበཱུዏ೬ཱུஸᗮ೬ূཱུዏ೬୳ᅻበȫᗮ
ùᗮ ӕᗮ ͆ 7͆ᅻࡐূበᗮዏᗮ೬ཱུႼᎰዏᗮအཱུᗮहఀࡐᅻࡐहዏᅻᗮࡐዏᗮࡐᗮዚ೬༌ᗮࡐཱུূᗮჇᅻအূᎰहበᗮ ࡐበᗮအᎰዏႼᎰዏᗮࡐᗮበዚᅻࡐ༌ᗮႪᗮ&͆ᑌఀᅻᗮࡐᗮዏအฅཱུᗮहအཱུበ೬በዏበᗮအᗮࡐᗮዏᅻ༌೬ཱུࡐเᗮበᓄ༌ࣧအเᗮ ࡐเအཱུஸᗮᑌ೬ዏఀᗮ ࡐূূ೬ዏ೬အཱུࡐเᗮ೬ཱུအᅻ༌ࡐዏ೬အཱུᗮ ೬ཱུᗮ ዏఀᗮ အᅻ༌ᗮ အᗮ ࡐዏዏᅻ೬࣓Ꮀዏᗮ ᐟࡐเᎰበȫᗮ ץཱུᗮ
֎೬ஸȫᗮ-Æ̓ዏအฅཱུበᗮ ࡐᅻᗮᑌᅻ೬ዏዏཱུᗮࡐበᗮዏᎰႼเበᗮཱུहเအበূᗮࣜዏᑌཱུᗮ ƱϮß ȫ ᗮ ݬఀᗮዺအฅཱུᗮ
ƱȉȂ.Ϯ qɁϮहအཱུበ೬በዏበᗮအᗮዏఀᗮᅻ༌೬ཱུࡐเᗮ͞ȂϮࡐཱུূᗮࡐᗮႼအ೬ཱུዏᅻᗮዏအᗮዏఀᗮበᒹ༌࣓အเżዏࡐ࣓เᗮ
ཱུዏᅻᒹᗮहအཱུዏࡐ೬ཱུ೬ཱུஸᗮዏఀᗮበዏᅻ೬ཱུஸᗮq aϮݬఀᗮዏᅻࡐཱུበเࡐዏအᅻᗮᎰበበᗮዏఀᗮዏࡐ࣓เᗮዏအᗮฅႼᗮ Scanner
Parser
GeneraBon of
Abstract Syntax Tree
StaBc Checking
• SyntacAc properAes (not captured by the context-‐free grammar of the language) are checked by analyzing the parse tree or the abstract syntax tree
• Context-‐dependent syntacAc properBes:
1. Every variable is declared before used
2. Each idenBfier is declared at most once per scope 3. Lea operands of assignments are L-‐values
4. Break statements must have enclosing loop or switch
• SemanAc analysis is applied by the compiler to discover the meaning of a program by analyzing its parse tree or abstract syntax tree. Useful to prevent runBme errors.
• StaAc semanAc checks performed at compile Bme:
5. Type checking: each operator is applied to arguments of the right type
– Handling of coercion and overloading
Exercise
• For each of the numbered items in the last slide, discuss how the property can be
checked either with a translaBon scheme or with suitable a[ributes of the parse tree
22
SemanBc Analysis
• Dynamic semanBc checks are performed at
run Bme, and the compiler produces code that performs these checks
– Array subscript values are within bounds – ArithmeBc errors, e.g. division by zero
– Pointers are not dereferenced unless poinBng to valid object
– A variable is used but hasn't been iniBalized – When a check fails at run Bme, an excepBon is
raised
GeneraBon of Three Address Code
• Linear Intermediate RepresentaBon generated by structural inducBon execuBng a funcBon on the nodes of the tree
• Sequence of instrucBons of the form x = y op z
• Arrays handled with instrucBons x[y] = z
x = y[z]
• Sequence control handled with jump instrucBons:
ifFalse x goto L ifTrue x goto L goto L
• Statement may have any number of labels, e.g.
L1:L2: x = y
24
TranslaBon of Statements
• Jumps are used to implement the control flow
• Example: if expr then stmt
1is translated to
25
]¡¡Ϯ ̓hm̓ ̓ ̓C̓ ̓
ޯఀᗮ୫ᅼበዏᗮႼᎰዏበᗮዏఀᗮᐟࡐเᎰᗮအ૨ᗮ7್ཱུ͆ᗮዏఀᗮเအ।ࡐዏ್အཱུᗮũʯ ͆ࡐཱུূᗮዏఀᗮበ।အཱུূᗮႼᎰዏበᗮዏఀᗮᐟࡐเᎰᗮ အ૨ᗮ ũ7ʮ್ཱུ͆ᗮዏఀᗮเအ।ࡐዏ್အཱུᗮ͆
ޯఀᅼŻࡐূূᅼበበᗮ್ཱུበዏᅼᎰ।ዏ್အཱུበᗮࡐᅼᗮᒏ।Ꮀዏূᗮ್ཱུᗮཱུᎰ༌ᅼ್।ࡐเᗮበᅑᎰཱུ।ᗮᎰཱུเበበᗮ૨အᅼ।ূᗮ ዏအᗮূအᗮအዏఀᅼᑌ್በᗮ࣓ᒹᗮࡐᗮ।အཱུূ್ዏ್အཱུࡐเᗮအᅼᗮᎰཱུ।အཱུূ್ዏ್အཱུࡐเᗮෟᎰ༌Ⴜʾᗮ ߖᗮ।ఀအအበᗮዏఀᗮ૨အเเအᑌ್ཱུஸᗮ
್ཱུበዏᅼᎰ।ዏ್အཱུበᗮ૨အᅼᗮ।အཱུዏᅼအเᗮအᑌёᗮ
Ϯƚ Ϯ͆sϮ©Ϯ
Ϯ°mϮ ͆sϮ©Ϯ sϮ+Ϯ
್૨ᗮ7ҿ್በᗮ૨ࡐเበčᗮཱུᒏዏᗮᒏ।Ꮀዏᗮዏఀᗮ್ཱུበዏᅼᎰ।ዏ್အཱུᗮเࡐ࣓เূᗮ©Ϯ
್૨ᗮ್͆በᗮዏᅼᎰčᗮཱུᒏዏᗮᒏ।Ꮀዏᗮዏఀᗮ್ཱུበዏᅼᎰ।ዏ್အཱུᗮเࡐ࣓เূᗮ©Ϯ
ཱུᒏዏᗮᒏ।Ꮀዏᗮዏఀᗮ್ཱུበዏᅼᎰ।ዏ್အཱུᗮเࡐ࣓เূᗮ©Ϯ
ӕᗮ เࡐ࣓เᗮ©Ϯ।ࡐཱུᗮ ࣓ᗮ ࡐዏዏࡐ।ఀূᗮ ዏအᗮࡐཱུᒹᗮ್ཱུበዏᅼᎰ।ዏ್အཱུᗮ࣓ᒹᗮႼᅼႼᗮཱུূ್ཱུஸᗮ ࡐᗮႼᅼ୫ᒏᗮ© ň F Ϯ ӕཱུᗮ
್ཱུበዏᅼᎰ।ዏ್အཱུᗮ।ࡐཱུᗮఀࡐᐟᗮ༌အᅼᗮዏఀࡐཱུᗮအཱུᗮเࡐ࣓เʾᗮ
֍್ཱུࡐเเᒹčᗮᑌᗮཱུূᗮ್ཱུበዏᅼᎰ।ዏ್အཱུበᗮዏఀࡐዏᗮ।အႼᒹᗮࡐᗮᐟࡐเᎰʾᗮ ޯఀᗮ૨အเเအᑌ್ཱུஸᗮዏఀᅼŻࡐূূᅼበበᗮ
್ཱུበዏᅼᎰ।ዏ್အཱུᗮ।အႼ್በᗮዏఀᗮᐟࡐเᎰᗮအ૨ᗮҿ್ཱུዏအᗮħϮ
× ͆͆
ɼ :ɼ¶ ɼ
ܺࡐዏ༌ཱུዏበᗮࡐᅼᗮዏᅼࡐཱུበเࡐዏূᗮ್ཱུዏအᗮዏఀᅼŻࡐূূᅼበበᗮ।အূᗮ࣓ᒹᗮᎰበ್ཱུஸᗮෟᎰ༌Ⴜᗮ್ཱུበዏᅼᎰ।ዏ್အཱུበᗮ ዏအᗮ್༌Ⴜเ༌ཱུዏᗮዏఀᗮအᑌᗮအ૨ᗮ।အཱུዏᅼအเᗮዏఀᅼအᎰஸఀᗮዏఀᗮበዏࡐዏ༌ཱུዏȩᗮ ޯఀᗮเࡐᒹအᎰዏᗮ್ཱུᗮ֍್ஸʾᗮ~̓
್เเᎰበዏᅼࡐዏበᗮዏఀᗮዏᅼࡐཱུበเࡐዏ್အཱུᗮအ૨ᗮ:ɼ ͆ɼ 4͆ ޯఀᗮෟᎰ༌Ⴜᗮ್ཱུበዏᅼᎰ।ዏ್အཱུᗮ್ཱུᗮዏఀᗮ เࡐᒹအᎰዏᗮ
Ϯƚ Ϯ͆ sϮ ø͆
ෟᎰ༌Ⴜበᗮအᐟᅼᗮዏఀᗮዏᅼࡐཱུበเࡐዏ್အཱུᗮအ૨ᗮ ್͆૨ᗮ ͆ᐟࡐเᎰࡐዏበᗮዏအᗮ:Eɼ ۖዏఀᅼᗮበዏࡐዏ༌ཱུዏᗮ
।အཱུበዏᅼᎰ।ዏበᗮࡐᅼᗮበ್༌್เࡐᅼเᒹᗮዏᅼࡐཱུበเࡐዏূᗮᎰበ್ཱུஸᗮࡐႼႼᅼအႼᅼ್ࡐዏᗮෟᎰ༌ႼበᗮࡐᅼအᎰཱུূᗮዏఀᗮ।အূᗮ૨အᅼᗮ ዏఀ್ᅼᗮ।အ༌Ⴜအཱཱུུዏበʾᗮ
w°}àðàw°ª´ËÃà 9[OP^¬Ã°àEǂ
кҿϔ:і҃бҿEǂ '*'-5>9P^
w°}à °ºà֟ƸֈƸ\
5>9P $^ ! ! Ğ ! ! řř
֍್ஸᎰᅼᗮ~Ȯ̓ԦအূᗮเࡐᒹအᎰዏᗮ૨အᅼᗮ್૨Żበዏࡐዏ༌ཱུዏበᗮ
֍အᅼᗮ।အཱུ।ᅼዏཱུበበčᗮᑌᗮበఀအᑌᗮዏఀᗮႼበᎰূအ।အূᗮ૨အᅼᗮ।เࡐበበᗮجଵᗮ್ཱུᗮ֍್ஸȩᗮ~̓ Ԧเࡐበበᗮ جଵᗮ್በᗮࡐᗮበᎰ࣓।เࡐበበᗮအ૨ᗮ ȃ͆ࡐበᗮࡐᅼᗮዏఀᗮ।เࡐበበበᗮ૨အᅼᗮዏఀᗮအዏఀᅼᗮበዏࡐዏ༌ཱུዏᗮ।အཱུበዏᅼᎰ।ዏበʾᗮ իࡐ।ఀᗮበᎰ࣓।เࡐበበᗮအ૨ᗮ ͆ఀࡐበᗮࡐᗮ।အཱུበዏᅼᎰ।ዏအᅼᗮȊ جଵᗮ್ཱུᗮዏఀ್በᗮ।ࡐበᗮž ࡐཱུূᗮࡐᗮ૨Ꮀཱུ।ዏ್အཱུᗮ͆
ዏఀࡐዏᗮ್በᗮ।ࡐเเূᗮዏအᗮஸཱུᅼࡐዏᗮዏఀᅼŻࡐূূᅼበበᗮ।အূᗮ૨အᅼᗮዏఀ್በᗮฅ್ཱུূᗮအ૨ᗮበዏࡐዏ༌ཱུዏɉᗮ h0ùm̓ ̓̓!̓
ɼɼ ɼ ͆;͆
> ͆ƪ͆ ͆ o͆
cj
#4ɼɼ?> ͆͆ ͆[؛;͆ =؛#5 ͆=؛[ V ؛ø͆ . 9)T o͆ j͆
#4ɼó ɼ ͆ƛ͆ ;͆
cj
> ͆-͆=؛4 T o ͆
?͆ łÝĖ͆ ϮᗮƇ͆ -4 T͆ E ł͆'Ϯᗮ E ø" o͆
4 T o ͆
? ø͆Ƈ͆ ł ɩ8 o ͆
֍೬ஸᎰᅼᗮI |KƒϮ֑Ꮀཱུहዐ೬အཱུᗮ͆೬ཱུᗮहเࡐበበᗮɼஸཱུᅼࡐዐበᗮዐఀᅼŸࡐূূᅼበበᗮहအূᗮ
4 4̓
ݬఀᗮहအཱུበዐᅼᎰहዐအᅼᗮɼ೬ཱུᗮ֍೬ஸȯᗮI|KϮहᅼࡐዐበᗮበᒹཱུዐࡐᒏŸዐᅼᗮཱུအূበᗮအᅼᗮ೬Ÿበዐࡐዐ༌ཱུዐበȯᗮ
ዐᗮ೬በᗮहࡐเเূᗮᑌ೬ዐఀᗮዐᑌအᗮႼࡐᅼࡐ༌ዐᅼበÿᗮࡐཱུᗮᒏႼᅼበበ೬အཱུᗮཱུအূᗮ#5 ࡐཱུূᗮࡐᗮበዐࡐዐ༌ཱུዐᗮཱུအূᗮ [ ؛ᑌఀ೬हఀᗮ೬ዐᗮበࡐᐕበᗮࡐበᗮࡐዐዐᅼ೬࣓Ꮀዐበᗮ͆ࡐཱུূᗮ 4͆ݬఀᗮहအཱུበዐᅼᎰहዐအᅼᗮࡐเበအᗮࡐበበ೬ஸཱུበᗮࡐዐዐᅼ೬࣓Ꮀዐᗮ
ø͆ࡐᗮᎰཱུ೬ᅑᎰᗮཱུᑌᗮเࡐ࣓เÿᗮ࣓ᒹᗮहࡐเเ೬ཱུஸᗮᎰཱུहዐ೬အཱུᗮ9)T 4͆ ݬఀᗮเࡐ࣓เᗮᑌ೬เเᗮ࣓ᗮᎰበূᗮ ࡐहहအᅼূ೬ཱུஸᗮዐအᗮዐఀᗮเࡐᒹအᎰዐᗮ೬ཱུᗮ֍೬ஸȴᗮI F|IFϮ
ཱུۖहᗮዐఀᗮཱུዐ೬ᅼᗮበᒹཱུዐࡐᒏᗮዐᅼᗮအᅼᗮࡐᗮበအᎰᅼहᗮႼᅼအஸᅼࡐ༌ᗮ೬በᗮहအཱུበዐᅼᎰहዐূÿᗮዐఀᗮᎰཱུहዐ೬အཱུᗮ
͆೬በᗮ हࡐเเূᗮ ࡐዐᗮ ዐఀᗮ ᅼအအዐᗮ အᗮዐఀᗮ በᒹཱུዐࡐᒏᗮ ዐᅼȯᗮ ܺ೬ཱུहᗮ ࡐᗮ Ⴜᅼအஸᅼࡐ༌ᗮ ೬በᗮ ࡐᗮ ࣓เအहฅᗮ೬ཱུᗮ အᎰᅼᗮ በ೬༌Ⴜเᗮ เࡐཱུஸᎰࡐஸťᗮ ዐఀᗮ ᅼအအዐᗮ အᗮዐఀᗮ በᒹཱུዐࡐᒏᗮ ዐᅼᗮ ᅼႼᅼበཱུዐበᗮ ዐఀᗮ በᅑᎰཱུहᗮ အᗮ በዐࡐዐ༌ཱུዐበᗮ೬ཱུᗮዐఀᗮ࣓เအहฅȯᗮ ӕเเᗮበዐࡐዐ༌ཱུዐᗮहเࡐበበበᗮहအཱུዐࡐ೬ཱུᗮࡐᗮᎰཱུहዐ೬အཱུᗮ4͆
ݬఀᗮႼበᎰূအहအূᗮအᅼᗮᎰཱུहዐ೬အཱུᗮ͆အᗮहเࡐበበᗮɼ೬ཱུᗮ֍೬ஸȯᗮIɱ|KϮ೬በᗮᅼႼᅼበཱུዐࡐዐ೬ᐕȯᗮצዐᗮ हࡐเเበᗮ4 T͆ዐအᗮዐᅼࡐཱུበเࡐዐᗮዐఀᗮ ᒏႼᅼበበ೬အཱུᗮ͆ ዐఀᗮ ࣓အအเࡐཱུŸᐕࡐเᎰূᗮᒏႼᅼበበ೬အཱུᗮ ዐఀࡐዐᗮ ೬በᗮႼࡐᅼዐᗮ အᗮዐఀᗮ ೬Ÿበዐࡐዐ༌ཱུዐበÂᗮ ࡐཱུূᗮ በࡐᐕበᗮዐఀᗮ ᅼበᎰเዐᗮ ཱུအূᗮ ᅼዐᎰᅼཱུূᗮ ࣓ᒹᗮ4͆
ࡐཱུበเࡐዐ೬အཱུᗮအᗮᒏႼᅼበበ೬အཱུበᗮᑌ೬เเᗮ࣓ᗮূ೬በहᎰበበূᗮበఀအᅼዐเᒹȯᗮ ֍Ꮀཱུहዐ೬အཱུᗮ͆ዐఀཱུᗮ༌೬ዐበᗮࡐᗮ हအཱུূ೬ዐ೬အཱུࡐเᗮෟᎰ༌Ⴜᗮࡐཱུূᗮहࡐเเበᗮ 4T͆ዐအᗮዐᅼࡐཱུበเࡐዐᗮዐఀᗮበᎰ࣓በዐࡐዐ༌ཱུዐᗮ 4͆
ɼ :ɼ ɼ
ߖᗮཱུအᑌᗮ೬เเᎰበዐᅼࡐዐᗮዐఀᗮዐᅼࡐཱུበเࡐዐ೬အཱུᗮအᗮᒏႼᅼበበ೬အཱུበᗮ࣓ᒹᗮहအཱུበ೬ূᅼ೬ཱུஸᗮᒏႼᅼበበ೬အཱུበᗮहအཱུᔳ ዐࡐ೬ཱུ೬ཱུஸᗮ࣓೬ཱུࡐᅼᒹᗮအႼᅼࡐዐအᅼበᗮ ɼ ࡐᅼᅼࡐᒹᗮ ࡐहहበበበÿᗮ ࡐཱུূᗮࡐበበ೬ஸཱུ༌ཱུዐበÿᗮ೬ཱུᗮ ࡐূূ೬ዐ೬အཱུᗮዐအᗮ हအཱུበዐࡐཱུዐበᗮࡐཱུূᗮ೬ূཱུዐ೬୫ᅼበȯᗮ ֍အᅼᗮበ೬༌Ⴜเ೬ह೬ዐᒹÿᗮ೬ཱུᗮࡐཱུᗮࡐᅼᅼࡐᒹᗮࡐहहበበᗮ[ båq ؛ᑌᗮᅼᅑᎰ೬ᅼᗮዐఀࡐዐᗮ [؛࣓ᗮࡐཱུᗮ೬ূཱུዐ೬୫ᅼȯ̎ͱᗮ ֍အᅼᗮࡐᗮূዐࡐ೬เূᗮ ূ೬በहᎰበበ೬အཱུᗮအᗮ೬ཱུዐᅼ༌ূ೬ࡐዐᗮहအূᗮஸཱུᅼࡐዐ೬အཱུᗮ
အᅼᗮᒏႼᅼበበ೬အཱུበÿᗮበᗮܺहዐ೬အཱུᗮÊ|Ϯ
ߖᗮበఀࡐเเᗮዐࡐฅᗮዐఀᗮበ೬༌ႼเᗮࡐႼႼᅼအࡐहఀᗮအᗮஸཱུᅼࡐዐ೬ཱུஸᗮအཱུᗮዐఀᅼǽࡐূূᅼበበᗮ೬ཱུበዐᅼᎰहᕪ ዐ೬အཱུᗮအᅼᗮࡐहఀᗮအႼᅼࡐዐအᅼᗮཱུအূᗮ೬ཱུᗮዐఀᗮበᒹཱུዐࡐᒏᗮዐᅼᗮအᅼᗮࡐཱུᗮᒏႼᅼበበ೬အཱུȯᗮ ڴအᗮहအূᗮ೬በᗮ ஸཱུᅼࡐዐূᗮအᅼᗮ೬ূཱུዐ೬୫ᅼበᗮࡐཱུূᗮहအཱུበࡐཱུበÿᗮበ೬ཱུहᗮዐఀᒹᗮहࡐཱུᗮࡐႼႼࡐᅼᗮࡐበᗮࡐূূᅼበበበᗮ೬ཱུᗮ ೬ཱུበዐᅼᎰहዐ೬အཱུበȯᗮ ᗮࡐᗮཱུအূᗮ͆အᗮहเࡐበበᗮ> ͆ఀࡐበᗮအႼᅼࡐዐအᅼᗮ ÷ɼዐఀཱུᗮࡐཱུᗮ೬ཱུበዐᅼᎰहዐ೬အཱུᗮ೬በᗮ
༌೬ዐዐূᗮዐအᗮहအ༌ႼᎰዐᗮዐఀᗮᐕࡐเᎰᗮࡐዐᗮཱུအূᗮ͆೬ཱུዐအᗮࡐᗮहအ༌Ⴜ೬เᅼᗮஸཱུᅼࡐዐূᗮዐ༌Ⴜအᅼࡐᅼᒹᗮ
ཱུࡐ༌ÿᗮበࡐᒹᗮ͆ ݬఀᎰበÿᗮݵű ë˳͆ዐᅼࡐཱུበเࡐዐበᗮ೬ཱུዐအᗮዐᑌအᗮ೬ཱུበዐᅼᎰहዐ೬အཱུበᗮ
TranslaBon of expressions
• One operaBon at a Bme, using temporaries
26
tl = i - j t2 = tl + k i-j+k !
tl = a[i]
t2 = 2 * tl 2*a[i] !
t3 = j – k
t2 = a [ t3 ] tl = 2 * t2
a [ i ] = t1 a[i]=2*a[j-k] !
• L-‐values in assignements cannot be translated
into temporaries
TranslaBon of expressions: the pseudocode for L-‐value and R-‐value
27
4 ̓ ̓hm̓ ̓ ̓C̓ ̓
N = Ϯ ҿ Ϯ î ű͆
NϮ /Ϯ N = Ϯ ë͆ qϮ
ߖ್ዏఀᗮࡐᅼᅼࡐᒹᗮࡐहहበበበᗮࡐཱུূᗮࡐበበ್ஸཱུ༌ཱུዏበᗮहအ༌በᗮዏఀᗮཱུূᗮዏအᗮূ್በዏ್ཱུஸᎰ್በఀᗮ࣓ዏᑌཱུᗮ ثȋᐟࡐไᏇበᗮࡐཱུূᗮሼŻᐟࡐไᎰበȫᗮ ֍အᅼᗮᒏࡐ༌ႼไčᗮϮ Ϯहࡐཱུᗮ࣓ᗮዏᅼࡐཱུበไࡐዏূᗮ࣓ᒹᗮहအ༌ႼᏇዏ್ཱུஸᗮዏఀᗮ ሼŻᐟࡐไᏇᗮအᗮϮ4Ϯ್ཱུዏအᗮࡐᗮዏ༌Ⴜအᅼࡐᅼᒹčᗮࡐበᗮ್ཱུᗮ
N = Ϯ ҿ Ϯ Ϯ Ϯ Ϯ NϮ /Ϯ Ϯ Ϯ N = Ϯ
ԠᎰዏčᗮᑌᗮ हࡐཱཱུུအዏᗮበ್༌ႼไᒹᗮᎰበᗮࡐᗮዏ༌Ⴜအᅼࡐᅼᒹᗮ್ཱུᗮႼไࡐहᗮအᗮϮ .Ϯ್ᗮϮ ϮࡐႼႼࡐᅼበᗮအཱུᗮ ዏఀᗮไዏᗮበ್ূᗮအᗮࡐཱུᗮࡐበበ್ஸཱུ༌ཱུዏɊᗮ
ݬఀᗮበ್༌ႼไᗮࡐႼႼᅼအࡐहఀᗮᎰበበᗮዏఀᗮዏᑌအᗮᎰཱུहዏೱအཱུበᗮ ͆ࡐཱུূᗮ ͆ᑌఀ್हఀᗮࡐႼႼࡐᅼᗮ
್ཱུᗮ֍್ஸȫᗮ,̓ࡐཱུূᗮă#Æ̓ᅼበႼहዏ್ᐟไᒹȫᗮ ߖఀཱུᗮᏇཱུहዏ್အཱུᗮ ್͆በᗮࡐႼႼไ್ূᗮዏအᗮࡐᗮཱུအཱུไࡐᗮ
ཱུအূᗮ್͆ዏᗮஸཱུᅼࡐዏበᗮ್ཱུበዏᅼᎰहዏ್အཱུበᗮዏအᗮहအ༌ႼᏇዏᗮ್ཱུ͆ዏအᗮࡐᗮዏ༌ႼအᅼࡐᅼᒹčᗮࡐཱུূᗮᅼዏᎰᅼཱུበᗮ ࡐᗮཱུᑌᗮཱུအূᗮᅼႼᅼበཱུዏ್ཱུஸᗮዏఀᗮዏ༌Ⴜအᅼࡐᅼᒹȫᗮ ߖఀཱུᗮᎰཱུहዏ್အཱུᗮ ್͆በᗮࡐႼႼไ್ূᗮዏအᗮࡐᗮ
ཱུအཱུไࡐčᗮ ್ዏᗮ ࡐไበအᗮ ஸཱུᅼࡐዏበᗮ ್ཱུበዏᅼᏇहዏ್အཱུበᗮ ዏအᗮ हအ༌ႼᎰዏᗮ ዏఀᗮ በᎰ࣓ዏᅼበᗮ ࣓ไအᑌᗮ͆ ࡐཱུূᗮ ᅼዏᎰᅼཱུበᗮࡐᗮཱུအূᗮᅼႼᅼበཱུዏ್ཱུஸᗮዏఀᗮ ࡐূূᅼበበᗮအᅼᗮ) /
ߖᗮ ূበहᅼ್࣓ᗮᎰཱུहዏ್အཱུᗮ ͆୫ᅼበዏčᗮ በ್ཱུहᗮ್ዏᗮఀࡐበᗮᑌᅼᗮ हࡐበበȫᗮ ߖఀཱུᗮ ࡐႼႼไ್ূᗮ ዏအᗮࡐᗮཱུအূᗮ͆Ꮀཱུहዏ್အཱུᗮ ͆በ್༌ႼไᒹᗮᅼዏᎰᅼཱུበᗮ್͆ᗮ್ዏᗮ್በᗮዏఀᗮཱུအূᗮအᅼᗮࡐཱུᗮ್ূཱུዏ್୫ᅼᗮ
˕್ɉɉčᗮ್ᗮ್͆በᗮအᗮहไࡐበበᗮ ʖ' x ؛ צཱུᗮအᎰᅼᗮ በ್༌ႼไᗮไࡐཱུஸᎰࡐஸčᗮ ዏఀᗮအཱུไᒹᗮအዏఀᅼᗮहࡐበᗮᑌఀᅼᗮ ࡐཱུᗮᒏႼᅼበበ್အཱུᗮఀࡐበᗮࡐཱུᗮŻᐟࡐไᎰᗮအहहᎰᅼበᗮᑌఀཱུᗮ͆ᅼႼᅼበཱུዏበᗮࡐཱུᗮࡐᅼᅼࡐᒹᗮࡐहहበበčᗮበᏇहఀᗮࡐበᗮ
Ϯ4 Ϯ צཱུᗮዏఀ್በᗮ हࡐበčᗮ͆ᑌ್ไไᗮ ఀࡐᐟᗮዏఀᗮ အᅼ༌ᗮ ᑌఀᅼᗮ हไࡐበበᗮ ್በᗮࡐᗮ በᎰ࣓हไࡐበበᗮအᗮ> ͆ č͆ᅼႼᅼበཱུዏበᗮዏఀᗮཱུࡐ༌ᗮအᗮዏఀᗮࡐहहበበূᗮࡐᅼᅼࡐᒹčᗮࡐཱུূᗮ7͆ᅼႼᅼበཱུዏበᗮ ዏఀᗮအୁበዏᗮ˖್ཱུূᒏñအᗮዏఀᗮहఀအበཱུᗮไ༌ཱུዏᗮ್ཱུᗮዏఀࡐዏᗮࡐᅼᅼࡐᒹȫᗮ ַအ༌ᗮዏఀᗮႼበᎰূအŻहအূᗮ
್ཱུᗮ֍್ஸȫᗮ Ǚ̓Ꮀཱུहዏ್အཱུᗮ ͆हࡐไไበᗮ ?78͆ዏအᗮஸཱུᅼࡐዏᗮ್ཱུበዏᅼᎰहዏ್အཱུበčᗮ್ᗮཱུূূčᗮ ዏအᗮहအ༌ႼᎰዏᗮዏఀᗮሼǛᐟࡐไᎰᗮအᗮ7͆צዏᗮዏఀཱུᗮहအཱུበዏᅼᏇहዏበᗮࡐཱུূᗮᅼዏᎰᅼཱུበᗮࡐᗮཱུᑌᗮ ཱུအূᗮ ᑌ್ዏఀᗮहఀ್ไূᅼཱུᗮအᅼᗮዏఀᗮࡐᅼᅼࡐᒹᗮཱུࡐ༌ᗮč͆ࡐཱུূᗮዏఀᗮሼŻᐟࡐไᎰᗮအᗮ74͆
> ͆ ?͆Ʀ͆> 8͆ ;͆
57
ùǂ͆?್͆͆በᗮࡐཱུᗮʖ'؛ཱུအূ ñ#ɼ#5
ɼùǂ͆?್͆͆በᗮࡐཱུᗮ ཱུအূᗮࡐཱུূᗮč್͆በᗮࡐཱུᗮʖ'؛ཱུအূ ñ ;͆
#ɼ'ɼ
ý؛ɼ DŽɼ
֍್ஸᎰᅼᗮ ¦̓ ۼበᎰূအहအূᗮအᅼᗮᎰཱུहዏ್အཱུᗮ ͆
ɼiȎƁ ȱ̓ ߖఀཱུᗮ ཱུအূᗮ͆ᅼႼᅼበཱུዏበᗮዏఀᗮࡐᅼᅼࡐᒹᗮࡐहहበበᗮ q . Ϯዏఀᗮ हࡐไไᗮ
?͆8͆ஸཱུᅼࡐዏበᗮࡐཱུᗮ್ཱུበዏᅼᎰहዏ್အཱུᗮ
ࡐཱུূᗮ ᅼዏᎰᅼཱུበᗮ ࡐᗮ ཱུᑌᗮ ཱུအূᗮ)/ ᅼႼᅼበཱུዏ್ཱུஸᗮዏఀᗮ ثŻᐟࡐไᎰᗮϮN .Ϯ ᑌఀᅼᗮNϮ ್በᗮ ࡐᗮ ཱུᑌᗮ ዏ༌Ⴜအᅼࡐᅼᒹᗮཱུࡐ༌ȩᗮ
ཱུᗮূዏࡐ್ไčᗮዏఀᗮहအূᗮᅼࡐஸ༌ཱུዏᗮ
hmùm̓ ɱ Ɗɞ̓̓!ɟ̓ 4 ̓
̂X¼w/ö̓öXè̓
೬በᗮᅼࡐहఀূᗮᑡ೬ዏఀᗮ࣒͆೬ཱུஸᗮዏఀᗮཱུအূᗮအᅼᗮϮࡐཱུূᗮ7࣒͆೬ཱུஸᗮዏ౮ᗮཱུအূᗮအᅼᗮᒏႼᅼበበ೬အཱུᗮͮϮ ݫఀᗮहࡐ̿ไᗮ ˍ?78͆ஸཱུᅼࡐዏበᗮहအূᗮအᆶᗮዏಀᗮᒏႼᅼઓበበ೬အཱུᗮqϮ೬ȩ੩ȩčᗮዏఀᗮዏఀᅼŻࡐূূᅼበበᗮ በዏࡐዏ༌ཱུዏᗮϮ Ϯ Ϯ Ϯ q8ϮࡐཱུূᗮᅼዏᎰᅼཱུበᗮዏఀᗮྣᑌᗮཱུအূᗮĶ˽͆ᅼႼᅼઓበཱུዏ೬ཱུஸᗮዏఀᗮዏ༌Ⴜအᅼࡐᅼᓾᗮ
ཱུࡐ༌ᗮaϮ ఀࡐዏᗮཱུအৈᗮĶŵ࣒͆हအ༌በᗮዏఀᗮᐕࡐไᎰᗮအᗮዏఀᗮበहအཱུূᗮไূᗮ೬ཱུᗮዏఀᗮཱུᑌᗮ
ཱུအূᗮ͆ዏఀࡐዏᗮ೬በᗮहᅼࡐዏূȩᗮ 5
> ͆ ?͆͆ ɪ͆> ǵ͆ ;͆
57
Ȩɼ?͆͆೬በᗮࡐཱུᗮ̙'؛အᅼᗮࡐᗮཱུ͆အূ Óᗮ/X¼w/ö̓#5
˝.R˞̓:ɼ ᒙ ೬በᗮࡐཱུᗮĬ ?ĊĘ 78͆အᅼᗮࡐᗮʜ ?ĊĘ 78ཱུ͆အূ Óᗮ;͆
͆=؛ཱུᑌᗮዏ༌Ⴜအᅼࡐᅼᒹ҃ᗮ
57
༌೬ዏᗮበዏᅼ೬ཱུஸᗮအᅼᗮ͆Ϯ ̱?̵8͆ ĊĘ͆ ?78 o͆
/X¼w/ö̓ࡐᗮཱུᑌᗮཱུအূᗮအᅼᗮo͆
X.̅X̓:ɼ?͆͆೬በᗮࡐཱུᗮ ཱུအূ Óᗮ;͆
͆ĬĭĮǂ ཱུᑌᗮዏ༌Ⴜအᅼࡐᅼᒹ҃ᗮ
57
हࡐไไᗮ ?8 ͆ᑌఀ೬हఀᗮᅼዏᎰᅼཱུበᗮ
༌೬ዏᗮበዏᅼ೬ཱུஸᗮအᅼᗮ
/X¼w/˺̓ࡐᗮཱུᑌᗮཱུအূᗮအᅼᗮo͆
X.RX̓:ɼ?͆͆೬በᗮࡐཱུᗮx5͆?͆78ཱུ͆အূ Óᗮ;͆
7͆ .̙ ?͆7͆8 o ͆ 57
༌೬ዏᗮቯዏᅼ೬ཱུஸᗮအᅼᗮ ?8͆/Ϯ7o͆
/X¼w/ö̓7 o͆
֍೬ஸᎰᅼᗮILJ|ʹϮۼበᎰূအहအূᗮအᅼᗮᎰཱུहዏ೬အཱུᗮ ͆
ֻཱུहዏ೬အཱུᗮ ͆೬ཱུᗮ֍೨ஸȴᗮIɲ|Ϯஸཱུᅼࡐዏበᗮ೬྆በዏᅼᎰहዏ೬အཱུበᗮࡐཱུূᗮᅼዏᎰᅼཱུበᗮࣂᗮႼအበበ೬࣒ไᓾᗮ
ཱུᑠᗮཱུအূᗧᗮߖఀཱུᗮ͆ᅼႼᅼበཱུዏበᗮࡐཱུᗮ೬ূཱུዏ೬୫ᅼᗮအᅼᗮࡐᗮॖအཱུበዏࡐཱུዏčᗮ ͆ᅼዏᎰᅼཱུበᗮ#5೬ዏበไȴᗮ
ཱུᗮࡐไไᗮအዏఀᅼᗮहࡐበበčᗮ೬ዏᗮᅼዏᎰᅽཱུበᗮࡐཱུᗮ̙'؛ཱུအূᗮအᅼᗮࡐᗮཱུᑌᗮዏ༌Ⴜအᅽࡐሽᒹᗮ͆ ݫఀᗮলࡐበበᗮࡐᅼᗮ ࡐበᗮအไไအᑌበоᗮ
ǂ ߖఀཱུᗮ7ҿ ᅼႼᅼበཱུዏበᗮ͆ ĊĘ͆ 7͆ዏఀ਼ᗮहအূᗮ୫ᆼበዏᗮ हအ༌ႼᎰዏበᗮ͆=؛ ?8͆ࡐཱུূᗮ
7͆ . ?7Ƕ ͆ ዏᗮ हᅼࡐዏበᗮ ࡐᗮཱུᑌᗮዏ༌Ⴜအᅼࡐᅼᒹᗮ͆ࡐཱུূᗮஸ਼ཱུᅼࡐዢበᗮࡐཱུᗮ වཱུበዱᅼᎰह˛ᗮ ዏ೬အཱུᗮ͆ Ϯ ͆ Ċʐ͆ 7͆ ༌အᅼᗮႼᅼह೬በไᒹčᗮ ࡐཱུᗮ೬ཱུበዏᅼᏬहዏ೬အཱུᗮအᅼ༚ৎᗮᅼအ༌ᗮዏఀᗮበዏᅼ೬ཱུஸᗮ ᅼႼᅼበཱུዏࡐዏ೬အཱུበᗮအᗮ͆ ͆ĊĘ͆ࡐཱུূᗮĶŵ8 ͆ዏᗮᅼዏᎰᅽཱུበᗮࡐᗮཱུအূᗮုᅼᗮ೬ৈཱུዏ೬୫ᅼᗮ͆
ǂ ߖఀཱུᗮ͆ ᅼႼᅼበ਼ཱུዏበᗮࡐཱུᗮࡐᅼᅼࡐᒹᗮࡐहहበበᗮқҿʓ̶ ͆ᑌᗮहࡐཱུᗮ ᅼᎰበᗮᎰཱུहዏ೬အཱུᗮ ͆
ީఀᗮहࢢไไ ඦ īᗨ?ҕ8͆ᅼዏᎰᅼཱུበᗮࡐཱུᗮࡐहहበበᗮ͆ķĶŵ͆͆ᑌᅼᗮ7͆ᅼᅼበཱུዏበᗮࡐཱུᗮ೬ཱུዏ೬୫ᅼᗮ
The Phases of a Compiler
Phase Output Sample
A=B+C;
Scanner (performs lexical analysis) Token string ‘A’, ‘=’, ‘B’, ‘+’, ‘C’, ‘;’
And symbol table with names Parser (performs syntax analysis
based on the grammar of the programming language)
Parse tree or abstract syntax tree ;
| = / \ A + / \ B C
Semantic analyzer (type checking, etc)
Annotated parse tree or abstract syntax tree
Intermediate code generator Three-address code, quads, or RTL (Register Transfer
Language)
int2fp B t1 + t1 C t2 := t2 A
Optimizer Three-address code, quads, or
RTL
int2fp B t1 + t1 #2.3 A
Code generator Assembly code MOVF #2.3,r1
ADDF2 r1,r2 MOVF r2,A
Peephole optimizer Assembly code ADDF2 #2.3,r2
MOVF r2,A 28
Reviewing the EnBre Process
Errors position := initial + rate * 60
lexical analyzer
syntax analyzer
semantic analyzer
intermediate code generator id1 := id2 + id3 * 60
:=
id1 id2
id3 +
*
60 :=
id1 id2
id3 +
*
inttoreal 60
Symbol Table position ....
initial ….
rate….
Reviewing the EnBre Process
Errors intermediate code generator
code optimizer
final code generator t1 := inttoreal(60) t2 := id3 * t1 temp3 := id2 + t2 id1 := t3
t1 := id3 * 60.0 id1 := id2 + t1
MOVF id3, R2 MULF #60.0, R2 MOVF id2, R1 ADDF R1, R2 MOVF R1, id1 position ....
initial ….
rate….
Symbol Table
3 address code
30
