CPS 1 - Spring, 1999 - Ramm 3/22/99 #25

Announce
- Continue to Read Chapter 9, Language Translation

Chapter 9. Language Translation

Importance of language:
- Levels of the machine: Multi-level model

Goal (Example)

Translate Java:

z = (x + y);

To Assembler:

copy 	ax, x
add	ax, y
copy 	cn1, ax 
copy	ax, cn1
copy	z, ax

"Meaning"
For our purposes, assembler give the meaning because the machine knows what to do with it (after trivial translation to binary)
Revise Syntactic Production Rules (seen before)
- R1: j -> //as sequence of letters and/or digits that begins with a letter//
 replaces
 R1: <identifier> -> //a sequence of letters and/or digits that begins with a letter//
 The new R1 says
 "change j into a sequence of letters and/or digits that begins with a letter."
Use Rules to Modify Strings
For syntactic productions, want to end up with valid Java programs.
Examples using R1:
3 -> x
or
6 -> data
where "i" stands for identifier
indices or subscripts: 3 and 6 keep items unique
Further use of R1:
(3 + 6)
use 3 and 6 above to get
(x + data)
More Rules:
- R2: <e>i -> j
 where "e" stands for expression
 
 Example <e>1 -> 3 -> x
 or <e>1 ->* x
- R3: <s>k -> j = <e>i
 where "s" stands for statement
 It says <s>k can be replace by
 "j = <e>i"

Can now do
ans = data;

derivation	rule

<s>1		R3: <s>1 -> <i>2 = <e>3;
<i>2 = <e>3;	R1: <i>2 -> ans
ans = <e>3;	R2: <e>3 -> <i>4
ans = <i>4;	R1: <i>4 -> data
ans = data;

Need two more to make it worthwhile
- R5: <e>i -> ( <e>j * <e>k )

Can now handle (note shorthand):

ANS = (X + (Y * Z));



derivation		rule

s1			R3: s1 -> i2 = e3;
i2 = e3;		R1: i2 -> ANS
ANS = e3;		R4: e3 -> (e4 + e5)
ANS = (e4 + e5);	R2: e4 -> i6
ANS = (i6 + e5);	R1: i6 -> X
ANS = (X + e5);		R5: e5 -> (e7 * e8)
ANS = (X + (e7 * e8);	R2: e7 -> i9
ANS = (X + (i9 * e8);	R1: i9 -> Y
ANS = (X + (Y * e8);	R2: e8 -> i10
ANS = (X + (Y * i10);	R1: i10 -> Z
ANS = (X + (Y * Z));

Need to Add Semantics
Add Semantic Components to our Rules
Augment R1
- Syntax Rule Semantic Rule
 R1: j->w M(j)=w
- M ... Meaning of ... Name ... Memory location
- In other words, use same identifier name in both Java and Assembler
Revise R2

Syntax Rule Semantic Rules

R2: <e>i -> j

M(<e>i) = M(j)
code(<e>i) = //nothing//

No code generated!
Revise R3

Syntax Rule Semantic Rules

R3: <s>k -> j=<e>i;

code(<s>k) = code(<e>i)
COPY AX,M(<e>i)
COPY M(j),AX

Says code for statement is code to calculate expression <e>i and code to copy it into Memory associated with j

Syntax Rule	Semantic Rule
`R1: <i>j->w`	`M(<i>j)=w`

Demonstrate use of Rules
Use Syntactic Derivation to Generate Semantic Rules; Use Semantic rules to Generate Code

X = Y;

Derivation Syntax Rules	    Semantic Rules
s1	   R3: s1 -> i2=e3; code(s1) =	code(e3)
			   	      	COPY AX,M(e3)
				      	COPY M(i2),AX

		MEANING:    code(s1) =	code (e3)
					COPY AX,M(e3)
					COPY M(i2), AX

i2 = e3;   R1: i2 -> X	    M(i2) = X

		MEANING:    code(s1) =	code (e3)
					COPY AX,M(e3)
					COPY X, AX

X = e3;	   R2: e3 -> i4	    M(e3) = M(i4)
	 		    code(e3) =  //nothing//

		MEANING:    code(s1) =	//nothing// 
					COPY AX,M(i4)
					COPY X, AX

X = i4;	   R1: i4 -> Y	    M(i4) = Y

		MEANING:    code(s1) =	COPY AX,Y
					COPY X, AX

X = Y;

Now Rules R4 and R5

Syntax Rule Semantic Rules

 R4: <e>i->(<e>j+<e>k)

`M(<e>i) = createname`
	`code(<e>i)=`	`code(<e>j)`
	`code(<e>k)`
	`COPY AX,M(<e>j)`
	`ADD AX,M(<e>k)`
	`COPY M(<e>i),AX`

Says code for <e>i is code to calculate expression <e>j followed by code to calculate expression <e>k and code to add them together and store that sum into Memory associated with <e>i

Syntax Rule Semantic Rules

 R5: <e>i->(<e>j*<e>k)

`M(<e>i) = createname`
	`code(<e>i)=`	`code(<e>j)`
	`code(<e>k)`
	`COPY AX,M(<e>j)`
	`MUL AX,M(<e>k)`
	`COPY M(<e>i),AX`

Says code for <e>i is code to calculate expression <e>j followed by code to calculate expression <e>k and code to multiply them together and store that sum into Memory associated with <e>i

Basically rules R4 and R5 are identical except that the + and ADD in one are replace by the * and MUL in the other.

Look at Example from Pages 276, 277 of book
It does Z = (X + Y)

More complicated example for U1 = (X + (Y * Z)) also in book. Look at it.

Rules for Looping
Sequence of statements

Syntax Rule Semantic Rules

`R6: <q>i ->`	`<s>j`
	`<q>k`

`code(<q>i) =`	`code(<s>j)`
	`code(<q>k)`

Syntax Rule	Semantic Rules
`R7: <q>i -> <s>j`	`code(<q>i) = code(<s>j)`

Says code for a sequence of statements is the code for the first statement followed by the code for the next statement, etc.

Compound Statement

Syntax Rule Semantic Rules

`R8: <c>i ->`	`{`
	`<q>j`
	`}`

 code(<c>i) = code(<q>j)

While Statement

Syntax Rule Semantic Rules

`R9: <s>i->`	`while (<i>j < <e>k)`
	`<c>h`

`M(<s>i) = createname`
`M'(<s>i) = createname`
`code(<s>i) =`
`M(<s>i)`	`code(<e>k)`
	`COPY AX,M(<i>j)`
	`CMP AX,M(<e>k)`
	`JNB M'(s<i>)`
	`code(<c>h)`
	`JMP M(<s>i)`
`M'(<s>i)`	`NO-OP`

Cleanup Translation
Some code generated that can be removed.
Important: Everything done by simple substitution
Everything "adds up"

code( { <s>1;<s>2;<s>3 } )
is
code(<s>1)
code(<s>2)
code(<s>3)