Transcript COMP4031 2006-7 Artificial Intelligence for Games and

Show Fig 1.7
• Show Fig 1.7
http://csiweb.ucd.ie/staff/acater/comp30330.html
Compiler Construction
1
Three-address code
• Three-address code is used in this example for “intermediate code”.
• Every pseudo-instruction has at most one operator on RHS of an assignment,
so refers to at most three operands in total.
• Pseudo-instructions may assign to, and may use, imaginary temporary variables
• These pseudo-instructions should be easy to map onto real instructions of any
physical or virtual machine.
http://csiweb.ucd.ie/staff/acater/comp30330.html
Compiler Construction
2
Lexical Analyzer / Scanner
• HLLs usually use a regular grammar to describe the tokens: ids, numbers, etc.
• In such a grammar, the terminal symbols (terminals) are individual characters
• The nonterminal symbols (nonterminals) are either token class names (like ID,
NUM, etc) or helper categories.
• A deterministic finite-state automaton can be used to recognise whether a sequence
of characters is in the language described by the regular grammar.
• Start the automaton at a special distinguished “start state”, follow transitions labelled
with the next input character (if there is one) as long as possible. If there is no such
transition and the current state is an “accepting state”, recognition succeeds.
• Augmenting the RHS of grammar productions with “semantic actions” corresponds
to equipping transitions between states with code to be executed.
http://csiweb.ucd.ie/staff/acater/comp30330.html
Compiler Construction
3
Regular Grammar & DFA Example 1
Grammar:
Digit
NUM
More
0|1|2|3|4|5|6|7|8|9

Digit More


ε | Digit More
(not expressed as regular grammar, but it could be)
(and in regular expression form:
NUM  Digit+)
0
1
2
3
4
5
6
7
8
9
http://csiweb.ucd.ie/staff/acater/comp30330.html
01234 5 6 7 8
Compiler Construction
9
4
Regular Grammar & DFA Example 1
Grammar:
Digit
NUM
More
0|1|2|3|4|5|6|7|8|9

Digit More


ε | Digit More
(not expressed as regular grammar, but it could be)
(and in regular expression form:
NUM  Digit+)
0,1,2,3,4,5,6,7,8,9
http://csiweb.ucd.ie/staff/acater/comp30330.html
0,1,2,3,4,5,6,7,8,9
Compiler Construction
5
Regular Grammar & DFA Example 1
Digit
Grammar: NUM
More



0|1|2|3|4|5|6|7|8|9
Digit {number:=digit-’0’} More
ε | Digit {number:=number*10+digit-’0’} More
Attach “semantic actions” to rule RHSs,
to corresponding state transitions.
0,1,2,3,4,5,6,7,8,9
0
number:=digit-’0
http://csiweb.ucd.ie/staff/acater/comp30330.html
1
0,1,2,3,4,5,6,7,8,9
number:=
number*10+digit-’0’
Compiler Construction
6
Construct Lexer program
state:=0;
ch:=readchar(inputstream);
loop forever
{switch(state):
case 0: if ch=‘0’ or ch=‘1’ or … ch=‘9’
then {number:=ch-’0’; state:=1;
ch:=readchar(inputstream); break}
else {unreadchar(inputstream);
return false}
case 1: if ch=‘0’ or ch=‘1’ or … ch=‘9’
then {number:=number*10+ch-’0’; state:=1;
ch:=readchar(inputstream); break}
else {unreadchar(inputstream);
return true}
}
http://csiweb.ucd.ie/staff/acater/comp30330.html
Compiler Construction
7