CPS 1 - Spring, 1997 - Ramm 4/7/97 #31

Announce
- Quiz Wednesday

Chapter 10. Language Translation

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

Goal (Example)

Translate Pascal:

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 Pascal 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