Translational Semantics

Stack machine for Translational Semantics

The machine has a variable space which is composed of memory locations named by identifiers. The variables and all other data are integers. Processing is facilitated by an internal stack.

The stack machine's language and semantics are as follows:

Machine instruction Semantics of the instruction

PUSH var copy the value of var by pushing onto stack

PUSH const push an actual value onto stack

POP var pop the stack and copy the value to the var

ADD pop two values, then add, push result onto stack

SUB pop first value, pop second value, subtract first value from second, push result

MUL pop two values, then multiply, push result onto stack

DIV pop first value, pop second value, divide second value by first, push integer portion of result

BR label continue program at label line

BEQ label pop the stack, continue program at label line if popped value is zero

Machine instruction	Semantics of the instruction
`PUSH var`	copy the value of var by pushing onto stack
`PUSH const`	push an actual value onto stack
`POP var`	pop the stack and copy the value to the var
`ADD`	pop two values, then add, push result onto stack
`SUB`	pop first value, pop second value, subtract first value from second, push result
`MUL`	pop two values, then multiply, push result onto stack
`DIV`	pop first value, pop second value, divide second value by first, push integer portion of result
`BR label`	continue program at label line
`BEQ label`	pop the stack, continue program at label line if popped value is zero

Consider the following language, defined by the BNF description,

<term> ::= <var>  | 
           <const>
<exp>  ::= <term> | 
           <term> <op> <term>
<op>   ::= + | 
           - | 
           * | 
           /
<stmt> ::= <var> := <exp>       |
           if <exp> then <stmt> |
           while <exp> do <stmt>

We can generate a <stmt> as follows,

<stmt> ->    while <exp> do <stmt>
             while <term> <op> <term> do <stmt>
             while <var> <op> <term> do <stmt>
             while x <op> <term> do <stmt>
             while x + <term> do <stmt>
             while x + <const> do <stmt>
             while x + 2 do <stmt>
             while x + 2 do if <exp> then <stmt>
             while x + 2 do if <term> <op> <term> then <stmt>
             while x + 2 do if <var> <op> <term> then <stmt>
             while x + 2 do if x <op> <term> then <stmt>
             while x + 2 do if x * <term> then <stmt>
             while x + 2 do if x * <var> then <stmt>
             while x + 2 do if x * y then <stmt>
             while x + 2 do if x * y then <var> := <exp> 
             while x + 2 do if x * y then x := <exp> 
             while x + 2 do if x * y then x := <term> <op> <term>
             while x + 2 do if x * y then x := <var> <op> <term>
             while x + 2 do if x * y then x := x <op> <term>
             while x + 2 do if x * y then x := x - <term>
             while x + 2 do if x * y then x := x - <const>
             while x + 2 do if x * y then x := x - 1

So, we can see that while x + 2 do if x * y then x := x - 1 is valid syntax in this language. But what does it mean? That's where the translation into our simple machine comes in. We will define the meaning of the new language by describing how to translate it into the simple machine code. Hopefully, we understand the machine code well enough to know what it means.

Translation rules

high level instruction, x Stack machine equivalent, T(x)

<var> location of variable in memory

<const> an integer value

<term> (type 1) PUSH <var>

<term> (type 2) PUSH <const>

+ ADD

- SUB

* MUL

/ DIV

<exp> (type 1) T(<term>)

<exp> (type 2) T(first <term>) T(second <term>) T(<op>)

<stmt> (type 1) T(<exp>) POP <var>

<stmt> (type 2)
T(<exp>) BEQ label T(<stmt>) label:

<stmt> (type 3)
label1: T(<exp>) BEQ label2 T(<stmt>) BR label1 label2:

The statement that we are trying to understand is a type 3 statement (the while statement) which, following the table, translates as,

Translation rules
high level instruction, x	Stack machine equivalent, T(x)
<var>	location of variable in memory
<const>	an integer value
<term> (type 1)	`PUSH <var>`
<term> (type 2)	`PUSH <const>`
+	`ADD`
-	`SUB`
*	`MUL`
/	`DIV`
<exp> (type 1)	`T(<term>)`
<exp> (type 2)	`T(first <term>) T(second <term>) T(<op>)`
<stmt> (type 1)	`T(<exp>) POP <var>`
<stmt> (type 2)	T(<exp>) BEQ label T(<stmt>) label:
<stmt> (type 3)	label1: T(<exp>) BEQ label2 T(<stmt>) BR label1 label2:

label1:  T(<exp>)
         BEQ label2
         T(<stmt>)
         BR label1
label2:

The expression is x + 2 which is a type 2 expression, so we have,

label1:  T(x + 2)   --->       PUSH x
                               PUSH 2
                               ADD
         BEQ label2
         T(<stmt>)
         BR label1
label2:

Now, the statement of interest is a type 2 statement (the if statement) which, following the table, translates as,

label1:  PUSH x
         PUSH 2
         ADD
         BEQ label2
         T(if x * y then x := x - 1)  --->
         
                      T(x * y)        
                      BEQ label3
                      T(x := x - 1)
              label3:

         BR label1
label2:

Or,

label1:  PUSH x
         PUSH 2
         ADD
         BEQ label2
         T(x * y)      --->   PUSH x
                              PUSH y
                              MUL    
         BEQ label3
         T(x := x - 1) --->   T(<exp>)  --->  PUSH 1
                                              PUSH x
                                              SUB
                              POP <var> --->  POP x
label3:
         BR label1
label2:

which finally leads to our stack machine equivalent for the high level code,

label1:  PUSH x
         PUSH 2
         ADD
         BEQ label2
         PUSH x
         PUSH y
         MUL    
         BEQ label3
         PUSH 1
         PUSH x
         SUB
         POP x
label3:
         BR label1
label2:

Finally, we use this translation to note that the semantics of the while statement is "loop repeatedly until the expression equals zero" and the if statement is "perform the statement unless the expression equals zero."