sT: A Simple Turing Programming Language Programming Assignment 3
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
sT: A Simple Turing Programming Language
Programming Assignment 3
Code Generation
Due Date: 1:20PM, Tuesday, June 20, 2023
Your assignment is to generate code (in Java assembly language) for the sT language. The generated code will then be translated to Java bytecode by a Java assembler.
1 Assignment
Your assignment will be divided into the following parts:
• initialization
• parsing declarations for constants and variables
• code generation for expressions and statements
• code generation for conditional statements and loops
• code generation for procedure calls
1.1 Language Restrictions
In order to keep the code generation assignment simple that we can implement most of the features of the language, only a subset set of sT language will be considered in this assignment:
• No GET statements.
• No declaration or use of arrays.
• No string variables, i.e. no assignments to string variables. Only string constants and string literals are provided for use in PUT statements.
1.2 What to Submit
You should submit the following items:
• your compiler
• a file describing what changes you have to make to your scanner and parser since the previous version you turned in
• Makefile
• test programs
1.3 Java Assembler
The Java Bytecode Assembler (or simply Assembler) is a program that converts code written in ”Java As- sembly Language”into a valid Java .class file.
2 Generating Java Assembly Code
This section describes the major pieces (see Section 1) of the translation of sT programs into Java assembly code. This document presents methods for code generation in each piece and gives sample sT along with the Java assembly code. Please note the label numbers in the examples are arbitrarily assigned.
2.1 Initialization
A sT program is translated into a Java class. An empty sT program example .st
will be translated into the following Java assembly code
class example
{
method public static void main(java .lang .String[])
max_stack 15
max_locals 15
{
return
}
}
Consequently, once the file name is read, a declaration of the corresponding class name must be generated. Furthermore, a method main that is declared public and static must be generated.
2.2 Declarations for Variables and Constants
Before generating Java assembly commands for sT statements, you have to allocate storage for declared variables and store values of constants.
2.2.1 Allocating Storage for Variables
Variables can be classed into two types: global and local. All variables that are declared inside compound statements are local, while other variables are global.
Global Variables
Global variables will be modeled as fields of classes in Java assembly language. Fields will be declared right after class name declaration. Each global variable var will be declared as a static field by the form
field static type var < = const_value >
where type is the type of variable var, and < = const value > is an optional initial constant value. For example,
var b := 10
var c :int
will be translated into the following declaration statements in Java assembly
field static int b = 10
field static int c
Local Variables
Local variables in sT will be translated into local variables of methods in Java assembly. Unlike fields (i.e. global variables of sT), local variables will not be declared explicitly in Java assembly programs. Instead, local variables will be numbered and instructions to reference local variables take an integer operand indicating which variable to use. In order to number local variables, symbol tables should maintain a counter to specify“the next available number”. For example, consider the following program fragment:
begin var var
i :int
j :int
begin var
end
begin var var var
end
end
k :int
i :int
j :int
k :int
the symbol table information will be
entering block, next number 0
i = 0, next number 1
j = 1, next number 2
entering block, next number 2
k = 2, next number 3
leaving block, symbol table entries:
<"k", variable, integer, 2>
entering block, next number 3
i = 3, next number 4
j = 4, next number 5
k = 5, next number 6
leaving block, symbol table entries:
<"i", variable, integer, 3>
<"j", variable, integer, 4>
<"k", variable, integer, 5>
leaving block, symbol table entries:
<"i", variable, integer, 0>
<"j", variable, integer, 1>
In addition, if an initialization value is given, statements must be generated to put the value onto the operand stack and then store it to the local variable. For instance, if the last statement of the above example is changed to
var k :int := 100
a store statement must be generated as well:
sipush 100
istore 2 // local variable number of k is 2
2.2.2 Storing Constants in Symbol Table
Constant variables in sT will not be transformed into fields or local variables in Java assembly. The values of constant variables will be stored in symbol tables.
2.3 Expressions and Statements
2.3.1 Expressions
An expression can be either an variable, a constant variable, an arithmetic expression, or a boolean expres- sion.
Variables
Since string variables are not considered in this project and furthermore Java Virtual Machine does not have instructions for boolean, a variable will be loaded to the operand stack by iload instruction if it is local or getstatic if it is global. Consider the following program fragment
var a :int
procedure foo
var b :int
:= a . . .
:= b . . .
end foo
The translated program will contain the following Java assembly instructions
getstatic int example .a
...
iload 1 / * local variable number of b is 1 */
Constants
The instructions to load a constant in Java Virtual Machine is iconst value or sipush value if the constant is a boolean or an integer, or ldc string is the constant is a string. Consider the following program fragment
const a :int := 10
const b :bool := true
const s :string := "string"
...
:= a . . .
:= b . . .
put s
:= 5 . . .
...
The translated program will contain the following Java assembly instructions
sipush 10 / * := a . . . */
...
iconst_1 / * := b . . . */
...
ldc "string" / * put s */
...
sipush 5 / * := 5 . . . */
Arithmetic and Boolean Expressions
Once the compiler performs a reduction to an arithmetic expression or a boolean expression, the operands of the operation will already be on the operand stack. Therefore, only the operator will be generated. The following table lists the mapping between operators in sT and corresponding instructions in Java assembly language.
sT Operator |
Integer |
sT Operator |
Boolean |
+ |
iadd |
and |
iand |
- |
isub |
or |
ior |
* |
imul |
not |
ixor |
/ |
idiv |
|
|
mod |
irem |
|
|
- (neg) |
ineg |
|
|
Boolean expressions with relational operators will be modeled by a subtraction instruction followed by a conditional jump. For instance, consider a < b.
iflt L 1
iconst_0 / * false = 0 */
goto L2
L1: iconst_1 / * true = 1 */
L2:
The following table summarizes the conditional jumps for each relational operator:
sT relop |
ifcond |
sT relop |
ifcond |
< |
iflt |
<= |
ifle |
> |
ifgt |
=> |
ifge |
= |
ifeq |
not= |
ifne |
2.3.2 Statements
Assignments id := expression
The right side, i.e. expression, will be on the operand stack when this production is reduced. As a result, the code to generate is to store the value at stack top in id. If id is a local variable, then the instruction to store the result is
istore 2 / * local variable number is 2 */
On the other hand, if id is global, then the instruction will be
putstatic type example.id
where type is the type of id.
PUT Statements put expression
The PUT statements in sT are modeled by invoking the print method injava.io package using the following format
getstatic java.io.PrintStream java.lang.System.out
. . . / * compute expression */
invokevirtual void java.io.PrintStream.print (java.lang.String)
if the type of expression is a string. Types int or boolean will replace java.lang.String if the type of expres- sion is integer or boolean.
getstatic java.io.PrintStream java.lang.System.out
. . . / * compute expression */
invokevirtual void java.io.PrintStream.print (int)
SKIP Statements
A SKIP statement will be compiled to the following java assembly code:
getstatic java.io.PrintStream java.lang.System.out
invokevirtual void java.io.PrintStream.println ()
2.4 If Statements
It is fairly simple to generate code for IF and loop statements. Consider this if-then-else statement:
i := 5
else
i := 10
end if
The following code will be generated
iconst_0
ifeq Lfalse
sipush 5
istore 2 / * local variable number of i is 2 */
goto Lexit
Lfalse:
sipush 10
istore 2
Lexit:
2.5 Loops
For each loop, a start label is inserted before the first statement and a jump instruction back to the start label will be added at the end of loop. If an optional exit statement is encountered, a test will be performed on the boolean expression and a conditional jump will be executed if the condition is met. Consider the following loop
i := 1
loop
exit when (i > 10)
i := i + 1
end loop
The following instructions will be generated:
sipush 1 / * constant 1 */
istore 1 / * local variable number of i is 1 */
iload 1
sipush 10
isub
ifgt Ltrue
iconst_0
goto Lfalse
Ltrue:
iconst_1
ifne Lexit
iload 1
sipush 1
istore 1
goto Lbegin
Lexit:
A for loop can be translated in the same way as a loop, as a for loop
for i : 1 . . 10
...
end for
is equivalent to
i := 1
loop
exit when (i > 10)
...
i := i + 1
end loop
2.6 Function Declaration and Invocation
Functions in sT will be modeled by static methods in Java assembly language.
2.6.1 Function Declaration
If n arguments are passed to a static Java method, they are received in the local variables numbered 0 through n − 1. The arguments are received in the order they are passed. For example
function add(a :int, b :int) :int
result a+b
end add
will be compiled to
method public static int add(int, int)
max_stack 15
max_locals 15
{
iload 1
iadd
ireturn
}
A procedure is translated in the same way, with the difference that the type of its corresponding method will be void and the return instruction will be return.
2.6.2 Function Invocation
To invoke a static method, the instruction invokestatic will be used. The following function invocation
:= add(a, 10) . . .
will be compiled into
...
iload 1 / * local variable number of a is 1 */
sipush 10 / * constant 10 */
invokestatic int example .add(int, int)
...
where the first int is the return type of the function and the second and last int are the types of formal parameters.
3 Implementation Notes
3.1 Local Variable Numbers
Formal parameters of a function are numbered starting from 0. Local variables in the function are placed right after the formal parameters of the function. For example, if a function has n formal parameters, then the parameters are numbered from 0 to n − 1, while the first local variable will be numbered n.
3.2 Java Virtual Machine
Once an sT program is compiled, the resulted Java assembly code can then be transformed into Java byte- code using the Java assembler javaa. The output of javaa will be a class file of the generated bytecode, which can be executed on the Java Virtual Machine. For example, if the generated class is example.class, then type the following command to run the bytecode
% java example
The structure of Java Virtual Machine is described in the book“Java Virtual Machine Specification”, which can be found at https://docs.oracle.com/javase/specs/jvms/se8/html/index.html.
Example
Source sT program example.st:
{%
% Example with Functions
%}
const a :int := 5
var c :int
% function declaration
function add (a :int, b :int) :int
result a+b
end add
% main block
c := add(a, 10)
if (c > 10) then
put -c
else
put c
end if
put "Hello World"
Generated Java assembly program:
/ *------------------------------------------------- */
/ * Java Assembly Code */
/ *------------------------------------------------- */
class example
{
/ * 6: const a :int := 5 */
field static int c
/ * 7: var c :int */
/ * 8: */
method public static int add(int, int)
max_stack 15
max_locals 15
{
iload 0
iload 1
iadd
ireturn
/ * 11: result a+b */
}
/ * 12: end add */
/ * 13: */
method public static void main(java .lang .String[])
max_stack 15
max_locals 15
{
sipush 5
sipush 10
invokestatic int example .add(int, int)
putstatic int example .c
/ * 15: c := add(a, 10) */
getstatic int example .c
sipush 10
isub
ifgt L0
iconst_0
goto L1
L0:
iconst_1
L1:
ifeq L2
/ * 16: if (c > 10) then */
getstatic java.io.PrintStream java.lang.System.out getstatic int example .c
ineg
invokevirtual void java.io.PrintStream.print (int)
/ * 17: put -c */
goto L3
L2:
/ * 18: else */
getstatic java.io.PrintStream java.lang.System.out
getstatic int example .c
invokevirtual void java.io.PrintStream.print (int)
/ * 19: put c */
L3:
/ * 20: end if */
getstatic java.io.PrintStream java.lang.System.out
ldc "Hello World"
invokevirtual void java.io.PrintStream.println (java.lang.String) / * 21: put "Hello World" */
return
}
}
2023-05-28
Code Generation