Up to this point, we have looked fairly informally at how a person can hand translate high-level-language code to assembly language. The time has come to take a more formal look at this problem. We will look at this problem through the perspective of a very simple example language, the language of a simple RPN calculator. This calculator has the following commands:
input: E stack: 0 input: E stack: 0 0 input: 123 stack: 0 123 input: + stack: 123 input: E 12 E 123 + E 12 E 123 - stack: 123 135 -111 input: + stack: 123 24A Pascal implementation of this calculator is trivial, assuming that the ends of strings are marked by a distinctive character, endofstring:
{ global variables }
const stacksize = 80;
var stack: array[0..stacksize] of integer;
sp: integer;
procedure initstack;
begin
sp := -1;
end
procedure calculate(var line: string);
var i: 0..stringsize;
begin
i := 0;
while s[i] <> endofstring do begin
case s[i] of
'E':begin
sp := sp + 1;
stack[sp] := 0;
end;
'0'..'9':
stack[sp] := stack[sp] * 10
+ (ord(s[i]) - ord('0'));
'+':begin
stack[sp-1] := stack[sp-1] + stack[sp];
sp := sp - 1;
end;
'-':begin
stack[sp-1] := stack[sp-1] - stack[sp];
sp := sp - 1;
end;
end;
i := i + 1;
end;
end;
procedure printstack;
var i: 0..stacksize;
begin
for i = 0 to sp do write( stack[sp] );
writeln;
end;
The above routines do no error checking, something that should be remedied
in any practical implementation! The above code rests on the following
main program:
program Calculator(input,output)
var line: string;
begin { main program }
initstack;
repeat
write('Input:'); { output a prompt }
readln(line);
calculate(line);
printstack;
forever;
end;
The biggest problem in translating this program to the Hawk environment
is that our low-level input/output routines do not follow the model of
Pascal (or C), both of which were designed in the era of printing input/output
devices. So, we must explicitly move the output position around on the display
screen instead of relying on the "printer carriage" to keep track of the
position. In the following version of the code, we have rewritten it in
terms of the Hawk system's I/O routines.
program Calculator(input,output)
var line: string;
lineno: integer;
begin { main program }
sp := 0;
lineno := 0
repeat
DSPAT(lineno, 0);
lineno := lineno + 1;
DSPST('Input:'); { output a prompt }
KBDGETS(line);
calculate(line);
DSPAT(lineno, 0);
lineno := lineno + 1;
printstack;
forever;
end;
Let's look at the printstack routine before continuing to look at the main
program. This routine contained the code:
for i = 0 to sp do write( stack[sp] );Note that this requires that the array addressing for stack[sp] be re evaluated with each iteration of the loop. C (and C++) allows this to be avoided by rewriting the loop as follows:
for (i = &stack[0]; i < &stack[sp]; i++ ) write( *i );In English, this says, "initialize i to the address of stack[0], and then, so long as i is less than the address of stack[sp], write the integer that i points to and then increment i by the size of one integer." Note that the operator ++ in C does not mean increment by one in this context, it means increment by the size of one integer!
We can make one further improvement. Instead of declaring sp as an integer and initializing it as -1, we can declare sp as a pointer to an integer and initialize it as &stack[-1].
This lets us rewrite the above for loop as:
for (i = &stack[0]; i < sp; i++ ) write( *i );Before finishing the translation of printstack to assembly language, it is important that we agree on a representation of the stack. We will use the following declarations for this:
; include file rpnstack.h STACKSIZE = 20 ; size of the stack COMMON RPN,STACKSIZE+4 PRPN W: RPN ; PRPN points to a record with the following format RPNSP = 0 ; the stack pointer in the RPN stack RPNSTK = 4 ; the first word of the stackOur convention is that RPNSP points to the current word on the stack top, so we can initialize the stack as follows:
INITSTK: LOAD R3,PRPN LEA R4,R3,RPNSTK-4 ; the address of stack[-1] STORE R4,R3,RPNSP ; initialize the stack pointer JUMPS R1Now, we are ready to rewrite printstack in assembly language:
PRINTSTACK: ; procedure to print the stack ; Activation record format ;RA = 0 ; return address INDEX = 4 ; loop index pointer LIMIT = 8 ; loop limit pointer AR = 12 ; activation record size ; no parameters, no returned result, wipes out R3-7 STORES R1,R2 ; save return address LOAD R3,PRPN LEA R4,R3,RPNSTK ; the index is address of stack[0] LOAD R5,R3,RPNSP ; the address of stack[sp] STORE R5,R2,LIMIT ; save loop limit PRLP: CMP R4,R5 ; check if loop done BGT PRLPQ ; quit if so LOADS R3,R4 ; get contents of stack[index] STORE R4,R2,INDEX ; save loop index while printing LIS R4,1 ADDI R2,AR ; push AR CALL DSPDEC ; output the number LIS " " CALL DSPCH ; output blank ADDI R2,-AR ; pop AR LOAD R4,R2,INDEX ; recover loop index LOAD R5,R2,LIMIT ; recover loop limit ADDSI R4,4 ; increment loop index BR PRLP ; continue loop PRLPQ: LOADS R1,R2 ; recover return address JUMPS R1 ; return