Code Generation
22 November 2019 OSU CSE 1
string of characters (source code)
Copyright By PowCoder代写 加微信 powcoder
string of tokens (“words”)
abstract program
22 November 2019
BL Compiler Structure
Code Generator
The code generator is the last step.
integers (object code)
Executing a BL Program
• There are two qualitatively different ways
one might execute a BL program, given a value of type Program that has been
constructed from BL source code:
– Interpret the Program directly
– Compile the Program into object code (“byte code”) that is executed by a virtual machine
22 November 2019 OSU CSE 3
Executing a BL Program
value of type Program that has been constructed from its source code:
– Interpret the Program directly
This is what the BL compiler will actually do;
• There are two qualitatively different ways
and this is how Java itself one might execute awBoLrkpsr(orgecralml t,hegiJvVeMn a
– Compile the Program into object code (“byte code”) that is executed by a virtual machine
22 November 2019 OSU CSE 4
and its “byte codes”).
Executing a BL Program
• There are two qualitatively different ways one might execute a BL program, given a
value of type Program that has been constructed from its source code:
– Interpret the Program directly
– Compile the Program into object code (“byte code”) that is executed by a virtual machine
22 November 2019 OSU CSE 5
Let’s first see how this might be done …
Time Lines of Execution • Directly interpreting a Program:
Tokenize Parse
Execute by interpreting the Program directly
• Compiling and then executing a Program:
Tokenize Parse
Generate code
Execute by interpreting generated code on VM
22 November 2019 OSU CSE
Time Lines of Execution • Directly interpreting a Program:
Tokenize Parse
Execute by interpreting the Program directly
• Compiling and then executing a Program:
Tokenize Parse
Generate Execute by interpreting code generated code on VM
22 November 2019
At this point, you have a Program value to use.
Time Lines of Execution
“run-time” means here. • Directly interpreting a Program:
Tokenize Parse
Execute by interpreting the Program directly
• Compiling and then executing a Program:
Tokenize Parse
Generate Execute by interpreting
22 November 2019
“run-time” means here. OSU CSE 8
generated code on VM “Execution-time” or
“Execution-time” or
Interpreting a Program
• The structure of a Program and, within it, the recursive structure of a Statement, directly dictate how to execute a Program
by interpretation
• Without contracts and other details, the following few slides indicate the structure of such code
22 November 2019 OSU CSE 9
executeProgram
public static void executeProgram(Program p) { Statement body = p.newBody();
Map
p.swapContext(context);
executeStatement(body, context);
p.swapBody(body);
p.swapContext(context);
22 November 2019 OSU CSE 10
22 November 2019
CALL instruction
WHILE condition
IF_ELSE condition
IF condition
22 November 2019
OSU CSE 12
It’s recursive just like everything else to do with Statement; context is needed for case CALL.
executeStatement
public static void executeStatement(Statement s, Map
switch (s.kind()) { case BLOCK: {
for (int i = 0; i < s.lengthOfBlock(); i++) { Statement ns = s.removeFromBlock(i); executeStatement(ns, context); s.addToBlock(i, ns);
case IF: {...}
executeStatement
• Non-BLOCK cases are different in kind:
– For IF, IF_ELSE, and WHILE, you need to decide whether the condition being tested as the BL program executes is (now) true or false
• This requires a call to some method that knows the state of BugsWorld, i.e., what the bug “sees”
– For CALL, you need to execute a primitive instruction, e.g., MOVE, INFECT, etc.
• This requires a call to some method that updates the state of BugsWorld
22 November 2019 OSU CSE 13
The State of BugsWorld
22 November 2019 OSU CSE 14
The State of BugsWorld
For example, when executing this bug’s Program in this state,
next-is-empty is true.
22 November 2019 OSU CSE 15
Where Is The State of BugsWorld?
A client executes a particular bug’s program, and tells the server to execute primitive instructions.
The server knows about all the bugs, and can report to a client what a particular bug “sees”.
22 November 2019 OSU CSE 16
executeStatement
• Surprisingly, perhaps, executing a call to a user-defined instruction is straightforward:
– You simply make a recursive call to executeStatement and pass it the body of
that user-defined instruction, which is obtained from the context
22 November 2019 OSU CSE 17
Compiling a Program
• As noted earlier, we are instead going to
compile a Program, and the last step for a BL compiler is to generate code
• The structure of a program to do this is similar to that of an interpreter of a
Program, except that it processes each Statement once rather than once every
time it happens to be executed at run-time
22 November 2019 OSU CSE 18
Code Generation • Code generation is translating a
Program to a linear (non-nested)
structure, i.e., to a string of low-level instructions or “byte codes” of a BL virtual machine that can do the following:
– Update the state of BugsWorld
– “Jump around” in the string to execute the right “byte codes” under the right conditions, depending on the state of BugsWorld
22 November 2019 OSU CSE 19
Code Generation
• Code generation is translating a
these “byte codes”.
Program to a linear (non-nested)
Primitive BL instructions are translated into
structure, i.e., to a string of low-level instructions or “byte codes” of a BL virtual machine that can do the following:
– Update the state of BugsWorld
– “Jump around” in the string to execute the right “byte codes” under the right conditions, depending on the state of BugsWorld
22 November 2019 OSU CSE 20
Code Generation
• Code generation is translating a
these “byte codes”.
Program to a linear (non-nested)
structure, i.e., to a string of low-level instructions or “byte codes” of a BL virtual machine that can do the following:
– Update the state of BugsWorld
– “Jump around” in the string to execute the right “byte codes” under the right conditions, depending on the state of BugsWorld
22 November 2019 OSU CSE 21
BL control constructs
that check conditions
are translated into
IF next-is-wall THEN turnleft
Loc 0 1 2 3 4 5 6
Instruction (symbolic name)
JUMP_IF_NOT_NEXT_IS_WALL
IF_ELSE NEXT_IS_WALL
22 November 2019
Example Statement
6 MOVE ...
CALL CALL turnleft move
IF next-is-wall THEN turnleft
Loc 0 1 2 3 4 5 6
Instruction (“byte code”)
9 5 1 6 6 0 ...
IF_ELSE NEXT_IS_WALL
22 November 2019
Example Statement
CALL CALL turnleft move
BugsWorld Virtual Machine
• The virtual machine for BugsWorld has three main features:
– Instruction set
– Program counter
22 November 2019 OSU CSE 24
BugsWorld Virtual Machine
three main features:
– Instruction set
– Program counter
A string of integers that contains the “byte codes”
• The virtual machine for BugsWorld has generated from a Program.
22 November 2019 OSU CSE 25
BugsWorld Virtual Machine
three main features: – Memory
– Instruction set
– Program counter
BugsWorld VM.
A finite set of integers
that are the “byte codes” for
the primitive instructions of the
• The virtual machine for BugsWorld has
22 November 2019 OSU CSE 26
BugsWorld Virtual Machine
three main features: – Memory
– Instruction set
– Program counter
Each instruction is given a
symbolic name here, for ease
of reading, but the VM knows
• The virtual machine for BugsWorld has only about integer “byte codes”.
22 November 2019 OSU CSE 27
BugsWorld Virtual Machine
– Instruction set
– Program counter
An integer that designates
the location/position/address in
memory of the “byte code” to
• The virtual machine for BugsWorld has three main features: be executed next.
22 November 2019 OSU CSE 28
BugsWorld Virtual Machine
three main features: – Memory
– Instruction set
– Program counter
Normal execution increments
the program counter by 1 or 2
after each instruction, so
• The virtual machine for BugsWorld has execution proceeds sequentially.
22 November 2019 OSU CSE 29
– Primitive instructions – Jump instructions
Instruction Set
• The instruction set, or target language, for code generation has two types of instructions:
22 November 2019 OSU CSE 30
– Primitive instructions – Jump instructions
Instruction Set
• The instruction set, or target language, for code generation has two types of instructions:
22 November 2019 OSU CSE 31
Each of these occupies one memory location.
– Primitive instructions – Jump instructions
22 November 2019
Instruction Set
• The instruction set, or target language, for code generation has two types of instructions:
Each of these occupies two memory locations: the second one is the location to jump to.
Primitive Instructions
• MOVE (0)
• TURNLEFT (1) • TURNRIGHT (2) • INFECT (3)
• SKIP (4)
• HALT (5)
22 November 2019
OSU CSE 33
Primitive Instructions
• MOVE (0)
• TURNLEFT (1) • TURNRIGHT (2) • INFECT (3)
• SKIP (4)
• HALT (5)
This is the “byte code” corresponding to the symbolic name for each instruction code.
22 November 2019
Primitive Instructions
• MOVE (0)
• TURNLEFT (1) • TURNRIGHT (2) • INFECT (3)
• SKIP (4)
• HALT (5)
This instruction halts program execution, and is the last instruction to be executed.
22 November 2019
Jump Instructions
• JUMP (6)
• JUMP_IF_NOT_NEXT_IS_EMPTY (7)
• JUMP_IF_NOT_NEXT_IS_NOT_EMPTY (8)
• JUMP_IF_NOT_NEXT_IS_WALL (9)
• JUMP_IF_NOT_NEXT_IS_NOT_WALL (10)
• JUMP_IF_NOT_NEXT_IS_FRIEND (11)
• JUMP_IF_NOT_NEXT_IS_NOT_FRIEND (12) • JUMP_IF_NOT_NEXT_IS_ENEMY (13)
• JUMP_IF_NOT_NEXT_IS_NOT_ENEMY (14) • JUMP_IF_NOT_RANDOM (15)
• JUMP_IF_NOT_TRUE (16)
22 November 2019 OSU CSE 36
Jump Instructions
• JUMP (6)
• JUMP_IF_NOT_NEXT_IS_EMPTY (7)
This unconditional jump instruction causes the program
• JUMP_IF_NOT_NEXT_IS_NOT_EMPTY (8)
counter to be set to the value in
• JUMP_IF_NOT_NEXT_IS_WALL (9)
the memory location following
• JUMP_IF_NOT_NEXT_IS_NOT_WALL (10) the JUMP code.
• JUMP_IF_NOT_NEXT_IS_FRIEND (11)
• JUMP_IF_NOT_NEXT_IS_NOT_FRIEND (12) • JUMP_IF_NOT_NEXT_IS_ENEMY (13)
• JUMP_IF_NOT_NEXT_IS_NOT_ENEMY (14) • JUMP_IF_NOT_RANDOM (15)
• JUMP_IF_NOT_TRUE (16)
22 November 2019 OSU CSE 37
• JUMP (6)
Jump Instructions
• JUMP_IF_NOT_NEXT_IS_EMPTY (7)
• JUMP_IF_NOT_NEXT_IS_NOT_EMPTY (8)
• JUMP_IF_NOT_NEXT_IS_WALL (9)
• JUMP_IF_NOT_NEXT_IS_NOT_WALL (10)
This conditional jump instruction
• JUMP_IF_NOT_NEXT_IS_FRIEND (11)
causes the program counter to be
• JUMP_IF_NOT_NEXT_IS_NOT_FRIEND (12)
set to the value in the memory
• JUMP_IF_NOT_NEXT_IS_ENEMY (13)
location following the instruction
• JUMP_IF_NOT_NEXT_IS_NOT_ENEMY (14)
code iff it is not the case that the
• JUMP_IF_NOT_RANDOM (15)
cell in front of the bug is a wall.
• JUMP_IF_NOT_TRUE (16)
22 November 2019 OSU CSE 38
JUMP_IF_NOT_condition
block (n instructions)
22 November 2019
Handling an IF Statement
IF condition THEN block
Loc k k+1 k+2 ... k+n+1 k+n+2
Instruction (symbolic name)
Handling an IF_ELSE Statement
IF condition THEN block1
... k+n1+2 k+n1+3 k+n1+4 ... k+n1+n2+4
Instruction (symbolic name)
ELSE block2
JUMP_IF_NOT_condition
block1 (n1 instructions)
22 November 2019
block2 (n2 instructions)
Handling a WHILE Statement
WHILE condition DO block
Loc k k+1 k+2 ... k+n+2 k+n+3 k+n+4
Instruction (symbolic name)
JUMP_IF_NOT_condition
block (n instructions)
22 November 2019
JUMP k ...
Handling a CALL Statement
move turnleft
Instruction (symbolic name)
22 November 2019
Instruction (symbolic name)
Handling a CALL Statement
INSTRUCTION my-instruction IS
Loc k ... k+n-1 k+n
Instruction (symbolic name)
END my-instruction
my-instruction
22 November 2019
block (of n instructions)
Handling a CALL Statement
INSTRUCTION my-instruction IS
Loc Instruction (symbolic name)
END my-instruction
my-instruction
22 November 2019
OSU CSE 44
k ... k+n-1 k+n
block (of n instructions)
A call to my-instruction generates a block of “byte codes” for the body of my-instruction.
Handling a CALL Statement
INSTRUCTION my-instruction IS
Loc Instruction (symbolic name)
END my-instruction
my-instruction
22 November 2019
OSU CSE 45
k ... k+n-1 k+n
block (of n instructions)
This way of generating code for a call to a user-defined instruction is called in-lining.
Handling a CALL Statement
INSTRUCTION my-instruction IS
Loc Instruction (symbolic name)
END my-instruction
my-instruction
What would happen with in-lining if BL allowed recursion?
22 November 2019
OSU CSE 46
k ... k+n-1 k+n
block (of n instructions)
How else might you handle calls to user-defined instructions?
Handling a BLOCK Statement • The “byte codes” generated for individual
Statements in a block (a sequence of Statements) are placed sequentially, one
after the other, in memory
• Remember: at the end of the body block of
the Program, there must be a HALT instruction
22 November 2019 OSU CSE 47
Aside: More On Java enum
• Recall: the Java enum construct allows
you to give meaningful symbolic names to
values for which you might instead have used arbitrary int constants
• This construct has some other valuable
features that allow you to associate
symbolic names (e.g., for VM instructions) with specific int constants (e.g., their
“byte codes”)
22 November 2019 OSU CSE 48
The Instruction Enum
• The interface Program contains this code:
* BugsWorld VM instructions and "byte codes".
enum Instruction {
plus 15 more instructions
An instance variable, a constructor, and an accessor method ...
22 November 2019
OSU CSE 49
MOVE(0), TURNLEFT(1), ... ; ...
The Instruction Enum
• The interface Program contains this code:
enum Instruction {
MOVE(0), TURNLEFT(1), ... ;
private int blByteCode;
private Instruction(int code) { this.blByteCode = code;
public int byteCode() { return this.blByteCode;
22 November 2019 OSU CSE 50
Every Instruction The Instruction Enum
private Instruction(int code) { this.blByteCode = code;
public int byteCode() { return this.blByteCode;
(e.g., MOVE) has an int instance variable called
• The interface Program contains this code:
blByteCode. MOVE(0), TURNLEFT(1), ... ;
enum Instruction {
private int blByteCode;
22 November 2019 OSU CSE 51
This constructor makes The Instruction Enum
private int blByteCode;
private Instruction(int code) { this.blByteCode = code;
public int byteCode() { return this.blByteCode;
each Instruction’s “argument” (in parens) the
• The interface Program contains this code:
enum Instruction {
MOVE(0), TURNLEFT(1), ... ;
22 November 2019 OSU CSE 52
value of its associated blByteCode.
This accessor method The Instruction Enum
• The interface Program contains this code:
enum Instruction {
MOVE(0), TURNLEFT(1), ... ;
private int blByteCode;
private Instruction(int code) { this.blByteCode = code;
public int byteCode() { return this.blByteCode;
(an instance method) allows a client to access
22 November 2019 OSU CSE 53
an Instruction’s associated
blByteCode.
Using This Feature
• In client code using Instruction, one
might write something like this:
Instruction i = Instruction.TURNLEFT; ...
int code = i.byteCode();
... Instruction.TURNLEFT.byteCode() ...
• The “byte code” thus obtained is what needs to be put into the generated code
22 November 2019 OSU CSE 54
• OSU CSE Components API: Program, Program.Instruction
– http://cse.osu.edu/software/common/doc/ • Java Tutorials: Enum Types
– http://docs.oracle.com/javase/tutorial/java/javaOO/enum.html
22 November 2019 OSU CSE 55
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com