辅导CSE 340留学生、讲解C/C++、Java编程语言、辅导data structure
讲解留学生Processing|调试Matlab程序
CSE 340 Fall 2018 – Project 4
Due on November 30, 2018 by 11:59 pm
Abstract
The goal of this project is to give you some hands-on experience with implementing a
small compiler. You will write a compiler for a simple language. You will not be generating
assembly code. Instead, you will generate an intermediate representation (a data structure
that represents the program). The execution of the program will be done after compilation by
interpreting the generated intermediate representation.
1 Introduction
You will write a small compiler that will read an input program and represent it in an internal
data structure. The data structure consists of two parts: (1) a representation of instructions
to be executed and (2) a representation of the memory of the program (locations for variables).
Instructions are represented by a data structure that includes the operand(s) of the instruction (if
any) and that specify the next instruction to be executed. After the data structures are generated by
your compiler, your compiler will execute the generated instructions representation by interpreting
it. This means that the program will traverse the data structure and at every node it visits, it
will execute the node by changing the content of memory locations corresponding to operands and
deciding what is the next instruction to execute (program counter). The output of your compiler
is the output that the input program should produce. These steps are illustrated in the following
figure
1The remainder of this document is organized as follows:
1. Grammar Defines the programming language syntax including grammar.
2. Execution Semantics Describe statement semantics for if, while, switch and print statements.
3. How to generate the intermediate representation Explains step by step how to generate
the intermediate representation (data structure). You should read this sequentially and
not skip around.
4. Executing the intermediate representation Basically, you have two options: (1) If you
are using C/C++, you should use the code we provide to execute the intermediate representation;
(2) If you are using Java, this section describes the strict rules to follow in executing
the intermediate representation. Those rules will be enforced by inspecting your code.
5. Requirements Lists the programming languages you are allowed to use in your solution
(C/C++ or Java) and other requirements.
6. Grading Describes the grading scheme.
7. Second Chance Project Describes the requirements for a bonus project.
2 Grammar
The grammar for this project is a simplified form of the grammar from the previous project, but
there are a couple extensions.
program → var section body
var section → id list SEMICOLON
id list → ID COMMA id list | ID
body → LBRACE stmt list RBRACE
stmt list → stmt stmt list | stmt
stmt → assign stmt | print stmt | while stmt | if stmt | switch stmt | for stmt
assign stmt → ID EQUAL primary SEMICOLON
assign stmt → ID EQUAL expr SEMICOLON
expr → primary op primary
primary → ID | NUM
op → PLUS | MINUS | MULT | DIV
print stmt → print ID SEMICOLON
while stmt → WHILE condition body
if stmt → IF condition body
condition → primary relop primary
relop → GREATER | LESS | NOTEQUAL
switch stmt → SWITCH ID LBRACE case list RBRACE
switch stmt → SWITCH ID LBRACE case list default case RBRACE
2for stmt → FOR LPAREN assign stmt condition SEMICOLON assign stmt RPAREN body
case list → case case list | case
case → CASE NUM COLON body
default case → DEFAULT COLON body
Some highlights of the grammar:
1. Expressions are greatly simplified and are not recursive.
2. There is no type declaration section.
3. Division is integer division and the result of the division of two integers is an integer.
4. if statement is introduced. Note that if stmt does not have else.
5. for statement is introduced. Note that for has a very general syntax similar to that of the C
language for loop.
6. A print statement is introduced. Note that the print keyword is in lower case, but other
keywords are all upper-case letters.
7. There is no variable declaration list. There is only one id list in the global scope and that
contains all the variables.
8. There is no type specified for variables. All variables are int by default.
3 Execution Semantics
All statements in a statement list are executed sequentially according to the order in which they
appear. Exception is made for body of if stmt, while stmt and switch stmt as explained below. In
what follows, I will assume that all values of variables as well as constants are stored in locations.
This assumption is used by the execution procedure that we provide. This is not a restrictive
assumption. For variables, you will have locations associated with them. For constants, you can
reserve a location in which you store the constant (this is like having an unnamed immutable
variable).
3.1 Assignment Statement
To execute an assignment statement, the expression on the lefthand side of the equal sign is evaluated
and the result is stored in the location associated with the righthand side of the expression.
3.2 Expression
To evaluate an expression, the values in the locations associated with the two operands are obtained
and the expression operator is applied to these values resulting in a value for the expression.
33.3 Boolean Condition
A boolean condition takes two operands as parameters and returns a boolean value. It is used to
control the execution of while and if statements. To evaluate a condition, the values in the locations
associated with the operands are obtained and the relational operator is applied to these values
resulting in a true or false value. For example, if the values of the two operands a and b are 3 and
4 respectively, a < b evaluates to true.
3.4 If statement
if stmt has the standard semantics:
1. The condition is evaluated.
2. If the condition evaluates to true, the body of the if stmt is executed, then the next statement
(if any) following the if stmt in the stmt list is executed.
3. If the condition evaluates to false, the statement following the if stmt in the stmt list is
executed
These semantics apply recursively to nested if stmt.
3.5 While statement
while stmt has the standard semantics.
1. The condition is evaluated.
2. If the condition evaluates to true, the body of the while stmt is executed. The next statement
to execute is the while stmt itself.
3. If the condition evaluates to false, the body of the while stmt is not executed. The next
statement to execute is the next statement (if any) following the while stmt in the stmt list.
These semantics apply recursively to nested while stmt. The code block:
WHILE condition
{
stmt list
}
is equivalent to:
label: IF condition
{
stmt list
goto label
}
4Note that goto statements do not appear in the input program, but our intermediate representation
includes GotoStatement which is used in conjunction with IfStatement to represent while
and switch statements.
3.6 For statement
The for stmt is very similar to the for statement in the C language. The semantics are defined by
giving an equivalent construct.
FOR ( assign stmt 1 condition ; assign stmt 2 )
{
stmt list
}
is equivalent to:
assign stmt 1
WHILE condition
{
stmt list
assign stmt 2
}
For example, the following snippet of code:
FOR ( a = 0; a < 10; a = a + 1; )
{
print a;
}
is equivalent to:
a = 0;
WHILE a < 10
{
print a;
a = a + 1;
}
3.7 Switch statement
switch stmt has the following semantics1
:
1The switch statement in the C language has different syntax and semantics. It is also dangerous!
51. The value of the switch variable is checked against each case number in order.
2. If the value matches the number, the body of the case is executed, then the statement following
the⁷††⁴㩴㱥㸼″⁉††㍬⁵㱰㹶⁴⁴㕥‼‾⁹㱥㹣†㍴⁴㕡⁴⁴⁷⁷⁴‼†ⵥ‾㱴㹲㍥†㕯†⁵†⁶†⁴⁴⁴⡨⁴䍨⽥䌼⭢⭲⤾⁴㱴㹯⁷⁴⡴䩴⥩䕮㱭㹬ⱨ⁴†⁹⁵⁴††㱲㹗††‾⸠㱮㸺㐠㈠䡴†㱓㹮†⁴‼‾䥴⁴⁉†㱢㹳㱢㸼㱲㸼‼⨠‽㭮㱫㸼㱲㹴㡭Ⱪ㨾†⁴㱤㹢⁓⡗⁃†⁃⁅⥭㽴†⁽⁃†⁴†‼⁅⁌㰠㹳††‾ⱆ†‾⁴⁴‼㩯⁴†㱽㹲⸼⁆†‼䥢‾†㱳㹴⁴‼‾⸠⁶䥡⁵⁶㨠㱡㹴⁴㱯㹯⁴㭥⽴⼮‼䵷ⱴ䜠䵴Ⱐ⁴䅨䥣䝯䵲ⱔ䥥䘠䵥Ɑ䥡䵤㰠㹬㱤㹡⁴䅵⩩㭴㱥㹲†⩷㭹㰠㹳䤠⩲㭳㰠㹲䜠⩴㬠㱥㹬㭩㱮㹯⩩㭡㱴㹥㱴㸼⁴⁴†⁷⁴⁵⁉㱢㹷ⱡ䥭†䥤䴠ⱨ⁴‱ⱬ㰠㹭†䅮䤼䝢‾䵳Ɑ⁰†⁹›⁰Ɽ†㰠㹥⁴†䅡⡮†⥮Ɐⱴ㱲㹴⁴⁻⁎⸠㱬㹴‼ⱴ†⁎‱⁴⁵⁰‾⁏⁴⁔㱥㹰†‼††⵰⸠㱳㸠䙴⁏†⁅Ⱐ⁹†⁸⡳†⥨㩥㰠㹬†⨩⡰⥥㱲㹯㰬㹦⁴⩳†㭤†⽡⽳㱥㹬⩧㭡⽤⼠†㱬㹴㵮⠠⥬㭩㱴㹡†⠨†㵶㵡†⁶⥭㱢㸮㱆㸠㵡⡵⥥㬠㱩㹴⁴†㭯⽥⽤†㱳㹩㬠㱴㸠㱡㹡㰠㹩㱩㹬⡩⥡㭢㱬㸼†㭩㱴㹬㱺㸠㱯㸮㤠䅉⁴㩩㱴㹶⩴⡴⥩㱯㸠㱮㹨⩯㭡㱲㹶䱯䉤䅳䌠䔨㰠㹲†㵶⡥⤠㭴㱨㸠䉳䅢䍲䔾㱡㹡㭳㱳㹮㱥㸠㑳㍡⁴䡥⁰㱡㹥䴠‼⁴‾⁴†††㱴㸠㩯㰬㹥⁴䥯⁴㱰㸠䍡㭥㱡㸠†⩢ㅯ㭷㱳㹢⩥㉴㭲㱵㸠⩟㭵㱣㹖⩢㭥㱎㹥㰠㹥⁴ⱥ⁴ㄻ†㈠⁁⁴⁴㱲㸼⁵⁴†Ⱜ†⁵㱲㹯Ⱐ†⁶††⸼㱢㹶⁺䤠㱩㸠⁰⁷††⁵㱳㹴⁴⁴†††㱹㹳⸠⁴䝨㱲㹥⁴䝥⁴㱮㹴⩮†㭥㰭㹭㰠㹩††ⱥ⁴⁰‾†㰠㸵⁽⁴⁴⠠⁰⁶⁵‾㱥㹡⥥⸠㱴㹥ㅸづ⩯⁵⡩⥴㰮㹨㱲㹡⸠㱴㸠‼㱣㹰䤠䙴㱯㹲㱴㹹㸠†㵩䤠䙳䵲㭴㱥㹩ⴠ㭬⁵⽤⽥†ⵔ†㱥㹳⼠⽡†⁵䍯Ɑ⁰䍩⭬⭥›䨼㱳㹵ⴠ㹓⁴㵎㭳㱥㹥⁴ 㸻Ⱐ⁴㹥ㄼ㸠㉤㱥㹩ⵣ㹥⁴㴠⠼⥢㭲‾⽳⽴⁰‼‾†㱲㹥⽥⽳
※⁴㱡㸻⼼⽢‾⁉㱬㹴ⵯ⁴⁹†⁷⽨⼠⁰†⁴†‾㱮㹡⽴⽥†ⵥⵥ㹲⁴†㱨㹥⽸⽥††⁵†䱡䱭㰮㹯⽵⼠⁵††㰠㹵⼠⽷ †㰠㹬⽹⼠⁴㱵㹯ⵥⴠ㹷⁰㱭㹬ⵣ㹯⁴ⵉ⁹㱲㹥⸠㱵㹰†⸠㱊㹡㰠㹵⁴⁴㩴㱥㹥ㅰㅲ⁁⁴†⁴㩡㰬㹸⩯⁵⡯⥮㰭㹣㱲㹶⩦⁵㭴⽯⽮†㱥㹨⩮㭲‾⼱⼴㰠㹥⁴㵩⡲⥡㭰㱨㹔⠠㵲㵥†⥢㱹㹲㱩㹰㵮⡴⥬㭥㰠㹥⁴㹬†㵡㵳䥩䙧䴠㱦㹨㱳㹥㰮㹲⽩⽴㰠㹭⽰⽩㱲㹨⽡⽴†㱥㹲⽡⽴㱥㹥⽤⽩㱥㹥⽰⽲㱥㹡⽴⽩㱯㹴㱥㹯㱮㹷㱩㸠㭲㰾㸠⽥⽸㱴㹴⽨⽥†㱮㹲⽭⽥㱡㸠⽲⽥⁰㱥㹡㱩㸮㭲㱰㹴㱲㹳㱶㹥㰠㹲⡩⥭㭰㱬㹥㬼㱢㸲㰠㹮㱵㹥䠺⁊䡳⁴††⁴†㱮㸠㨼㱢㸴⸮⸠⹉㱦㹯⁃⁴⁰㱪㹴⁹⁵†䡨䥥䰠䕰㱲㹩㱥㹣ⵥ㸠㵮䥹䘠䵬㭭⽮⽴†䡵䥩䱲䕥⁴†㱵㹳ⵯ⽬⼠ⵤ⁷⁴⁶㱴㸠⽲⽥ⁱ㱵㸠ⵥ㸠㵩ⴠ㱥㹮㸠ⰶ㹭ㅪⵦ㹥㈠㱃㹴ⴠⵢ㹲†㵡⡴⥨㭥㱲㹡†⼠⽩†⁰†㱩㸼ⴾ㹔㵳⁴䜠䵰㭯㱶㹥†ⵡ⽭⽥䝮㱳㹦ⴠ㹳†㵦ⴾ㭥㱭㹴ⵯ㸬㵡㬠⁷⽩⽴⁷†⁴⁷㱥㹤⽤⽥⁴㱲㹲ㅯ㉪†⁹†⽸⽴⁹†⁵⁴㱯㹡⽩⽮†⁴㱳㹣⽡⽳⁴⸠㱭㹴ⴠ㱮㹡ⵥ㸠⁵†⁴⁷㱢㹫㸠†㱦㸰㰠㹩㰩㹢⁁†‰‾⁴‵‾㨳㰰㹲㐾⸠㑓⁷䡩‼㱣㹤†††††⁴Ⱐ⁔‰⁴†㱰㹤䥰†䝰†㱣㹲⸩㍭㝮⁴㍴㙭††⸠㱴㹴㔠䕡㰼㸾䄱⁴Ɒ⁴†⁶䔠⁴†㰲㹔⁵䑮‾†⁵″ⱥ⁰⁹††㱪㹴†㱲㹲ㅡ㍤㵯㱣㹥†⠹†ⅴ㵨䱲䱡⥤㱥㹯㰠㹯‼⡢㹩⥥㰠㹡㱧㸠†䄲䥴䝯䴵㨨‵⼸⼮‵‰⁹ⴰ㸥㱥㹯⁴㵨ⵥ㹰㱭㹴䥡䙮䴠㩯⁵⽮⽴†‥㱣㹧⽲⽡†㰱㸠⽯⽦†㴠⁰㹥ⵥ㸮㰀㸀⼀⼀ 㰀㸀⼀⼀ 㴀 ⴀ㸀ⴀ㸀㰀㸀 䴀㨀 㴀 ⴀ㸀㰀㸀 䜀䴀㨀 㴀 ⴀ㸀ⴀ㸀㰀㸀 䤀䴀㨀 ⼀⼀ ⴀ㸀 ⸀⸀⸀㰀㸀 㴀 ⴀ㸀㰀㸀㰀㸀㰀㸀䌀⼀䌀⬀⬀ 䤀 䌀⼀䌀⬀⬀Ⰰ