CS代考 CSE 11

27 February 2019 OSU CSE 1

BL Compiler Structure
string of characters (source code)

Copyright By PowCoder代写 加微信 powcoder

string of tokens (“words”)
abstract program
integers (object code)
27 February 2019
A BL program consists of some statements …
Code Generator

• The Statement component family allows you to manipulate values that are ASTs for
BL statements
• The mathematical model of a Statement value is a tree of STATEMENT_LABEL with some constraints
27 February 2019 OSU CSE 3

IF condition
27 February 2019
CALL instruction
WHILE condition
IF_ELSE condition

IF condition
A Statement variable’s value is a
STATEMENT_LABEL
IF_ELSE condition
with some constraints, so we use rather than
to illustrate its recursive structure.
WHILE condition
27 February 2019 OSU CSE

The kind of statement
(based on the root)
determines how many
and which kinds of
children it may have.
IF condition
27 February 2019
CALL instruction
WHILE condition
IF_ELSE condition

The children of a BLOCK statement may not be BLOCK statements.
IF condition
27 February 2019
CALL instruction
WHILE condition
IF_ELSE condition

The child of an IF or WHILE statement must be a BLOCK statement.
IF condition
27 February 2019
CALL instruction
WHILE condition
IF_ELSE condition

The two children of an IF_ELSE statement must be BLOCK statements.
IF condition
27 February 2019
CALL instruction
WHILE condition
IF_ELSE condition

A CALL statement has no children.
IF condition
27 February 2019
CALL instruction
WHILE condition
IF_ELSE condition

Interfaces and Classes
Statement- Kernel
implements
Statement1
27 February 2019
OSU CSE 11

Interfaces and Classes
Statement- Kernel
implements
Statement1
StatementKernel
has contracts for 12 methods that involve “assembling” and “disassembling” the various BL statements (similar to Tree methods).
27 February 2019
OSU CSE 12

Interfaces and Classes
has these additional methods (not
discussed here):
parseBlock
prettyPrint
Statement- Kernel
implements
Statement1
27 February 2019
OSU CSE 13

Enumerations
• Java has a special construct, enum (short
for “enumeration”), that easily allows you
to use meaningful symbolic names where
you might otherwise be inclined to declare int variables and give them arbitrary
values to participate just in equality tests
27 February 2019 OSU CSE 14

Example: The Kind Enum
• TheinterfaceStatementKernel contains this code:
* The kinds of statements.
enum Kind {
BLOCK, IF, IF_ELSE, WHILE, CALL
27 February 2019 OSU CSE 15

Kind Enum m:
final int BLOCK = 1; final int IF = 2;
You may not do arithmetic with the contains this code:
enum constants, where you could /**
• TheinterfaceStatementKernel …
with the int constants above.
* The kinds of statements.
enum Kind {
BLOCK, IF, IF_ELSE, WHILE, CALL
27 February 2019 OSU CSE 16

Example: The Condition Enum
* The possible conditions for IF, IF_ELSE, * and WHILE statements.
enum Condition {
NEXT_IS_EMPTY, NEXT_IS_NOT_EMPTY, NEXT_IS_WALL, NEXT_IS_NOT_WALL, NEXT_IS_FRIEND, NEXT_IS_NOT_FRIEND, NEXT_IS_ENEMY, NEXT_IS_NOT_ENEMY, RANDOM, TRUE
27 February 2019 OSU CSE 17

Mathematical Model (1)
IDENTIFIER is string of character exemplar id
constraint
[id starts with a letter ‘a’-‘z’, ‘A’-‘Z’] and
[id contains only letters, digits ‘0’-‘9’, and ‘-‘] and
[id is not one of the keywords or
conditions in the BL language]
27 February 2019 OSU CSE 18

Mathematical Model (2)
STATEMENT_LABEL is ( kind: Kind,
test: Condition,
call: IDENTIFIER) exemplar sl constraint
[if sl.kind = BLOCK then sl.test and sl.call are irrelevant] and
[if sl.kind = IF or sl.kind = IF_ELSE or
sl.kind = WHILE then sl.call is irrelevant] and
[if sl.kind = CALL then sl.test is irrelevant]
27 February 2019 OSU CSE 19

Mathematical Model (2) Notice the use of the enums
STATEMENT_LABEL is ( kind: Kind,
test: Condition,
call: IDENTIFIER) exemplar sl constraint
in this model, as well as the previously defined IDENTIFIER.
[if sl.kind = BLOCK then sl.test and sl.call are irrelevant] and
[if sl.kind = IF or sl.kind = IF_ELSE or
sl.kind = WHILE then sl.call is irrelevant] and
[if sl.kind = CALL then sl.test is irrelevant]
27 February 2019 OSU CSE 20

Mathematical Model (3)
STATEMENT_MODEL is tree of STATEMENT_LABEL exemplar s
constraint
|s| > 0 and
[BLOCK can have 0 or more children, but
not another BLOCK as a child] and
[IF must have exactly one BLOCK child] and [IF_ELSE must have exactly two BLOCK
children] and
[WHILE must have exactly one BLOCK child] and [CALL must have no children (must be a leaf)]
27 February 2019 OSU CSE 21

Mathematical Model (4)
type StatementKernel is modeled by STATEMENT_MODEL
27 February 2019 OSU CSE 22

No-argument Constructor • Ensures:
this = compose((BLOCK, ?, ?), <>)
27 February 2019 OSU CSE 23

No-argument Constructor • Ensures:
this = compose((BLOCK, ?, ?), <>) The use of ? here means we do not know—and,
frankly, do not care about—the values of the 2nd and 3rd tuple components (test and call); the
model says they are irrelevant if the 1st tuple component (kind) is BLOCK.
27 February 2019 OSU CSE 24

Statement s =
new Statement1();
27 February 2019 OSU CSE 25

Statement s =
new Statement1();
27 February 2019 OSU CSE 26

Statement.Kind kind()
• Reports the kind of statement this is. • Ensures:
kind = [the statement kind of this]
27 February 2019 OSU CSE

Kind k = s.kind();
27 February 2019 OSU CSE 28

Kind k = s.kind();
s = BLOCK k = BLOCK
27 February 2019 OSU CSE 29

addToBlock
void addToBlock(int pos, Statement s)
• Adds the statement s at position pos in this BLOCK statement.
• Updates: this
• Clears: s
• Requires:
[this is a BLOCK statement] and [s is not a BLOCK statement] and 0 <= pos <= [length of this BLOCK] • Ensures: this = [#this with child #s inserted at position pos] 27 February 2019 s = BLOCK ns = s.addToBlock(1, 27 February 2019 OSU CSE 31 s = BLOCK ns = s.addToBlock(1, 27 February 2019 OSU CSE 32 removeFromBlock Statement removeFromBlock(int pos) • Removes and returns the statement at position pos of this BLOCK statement. • Updates:this • Requires: [this is a BLOCK statement] and 0 <= pos < [length of this BLOCK] • Ensures: this = [#this with child at position pos removed and returned as result] 27 February 2019 OSU CSE Statement ns = s.removeFromBlock(1); 27 February 2019 OSU CSE 34 Statement ns = s.removeFromBlock(1); 27 February 2019 OSU CSE 35 lengthOfBlock int lengthOfBlock() • Reports the number of statements in this BLOCK statement. • Requires: [this is a BLOCK statement] • Ensures: lengthOfBlock = [the number of children of this] 27 February 2019 OSU CSE assembleIf void assembleIf(Statement.Condition c, Statement s) • Assembles in this a statement with root label (IF, c , ?) and only subtree the BLOCK s; the declaration notwithstanding, the dynamic type of s must be the same as the dynamic type of this. • Replaces: this • Clears: s • Requires: [s is a BLOCK statement] • Ensures: this = compose((IF, c, ?), <#s>) 27 February 2019 OSU CSE

s = ? ns =
s.assembleIf(
RANDOM, ns);
27 February 2019 OSU CSE 38

s = ? ns =
s.assembleIf(
RANDOM, ns);
s= RANDOM ns=
27 February 2019 OSU CSE 39

disassembleIf
Statement.Condition disassembleIf(
Statement s)
• Disassembles IF statement this into its test Condition, which is
returned as the value of the function, and its only subtree, the BLOCK statement s; the declaration notwithstanding, the dynamic type of s must be the same as the dynamic type of this.
• Replaces: s
• Clears: this
• Requires:
[this is an IF statement]
• Ensures:
#this = compose((IF, disassembleIf, ?), ) 27 February 2019 OSU CSE