Consider the recursive descent parser for the grammar giving arithmetic expressions.
P ---> E '#'
E ---> T {('+'|'-') T}
T ---> S {('*'|'/') S}
S ---> F '^' S | F
F ---> '(' E ')' | char
Initial Examples of Semantic Actions Based on the Above Grammar:It is easy to add extra code to this parser so that it will translate arithmetic expressions in to reverse Polish notation (RPN). So little additional code is needed that this example illustrates the power of this approach.
Here is another example of semantic actions: an evaluator of arithmetic expressions:
Initial Recitation work: For this recitation and the next one, you are to translate the language described in the previous recitation into MIPS assembly code.
For this recitation you should ignore all statements except assignments and output statements, which are of the form:
< expression ; (print an expression) < B ; (print a blank) < N ; (print a newline) < T ; (print a tab)
The recitation is also ignoring the ^ operator. These are what you should translate.
Form of assembler output: There are many forms the output could take. I am suggesting one form here:
la $s1, M
.data
M: .word 0,1,2,3,4,5,6,7,8,9 # constants
.space 104 # 26 variables a to z
.space 200 # 50 temporaries
lw $t1, 8($s1) # load constant 2 into $t1 sw $t1, 64($s1) # store into g (which is M[16]
lw $t1, 60($s1) # load f (= M[15]) into $t1 lw $t2, 64($s1) # load g (= M[16]) into $t2 add $t3, $t1, $t2 # form sum in $t3 sw $t3, 176($s1) # store $t3 into temporary M[44] lw $t1, 176($s1) # load temporary M[44] into $t1 sw $t1, 68($s1) # store $t1 into h (= M[17])
li $v0, 1 # 1 to print an int lw $a0, 64($s1) # load g's value (M[16]) into $a0 syscall # now print
li $v0, 4 # 4 to print a string la $a0, Blank # load address of string syscall # now print
where elsewhere you need:
.data
Blank: .asciiz " "
How to do the actual translation: This first part of the recitation is only using part of the grammar (just for assignments and output):
M ---> { S } '#'
S ---> A | P | C
A ---> lower-case '=' E ';'
P ---> '<' E ';'
C ---> '<' upper-case ';'
E ---> T {('+' | '-') T}
T ---> U {('*' | '/' | '%') U}
U ---> F
F ---> '(' E ')' | lower-case | digit
As a hint for completing the recitation, you can work with the evaluator code above, since the code you need is actually quite similar. Each of the various functions of the parser must return an integer giving the location in memory where the given operand or expression is to be found: memory locations 0 to 9 for constants 0 to 9, locations 10 to 35 for variables a to z, and locations 36 to 85 for 50 temporaries.
What to turn in to the recitation instructor:
f = 5 + 8;
g = f + 8;
h = f + g;
< h; < N;
#
The output spim code might be (but lots of other forms):
### Compiled on: Fri Sep 27 11:39:34 CDT 2002 main: addu $s7, $ra, $zero la $s1, M ### Start of compiled code # M[36] = M[5] + M[8] lw $t1, 20($s1) lw $t2, 32($s1) add $t3, $t1, $t2 sw $t3, 144($s1) # M[15] = M[36] lw $t1, 144($s1) sw $t1, 60($s1) # M[37] = M[15] + M[8] lw $t1, 60($s1) lw $t2, 32($s1) add $t3, $t1, $t2 sw $t3, 148($s1) # M[16] = M[37] lw $t1, 148($s1) sw $t1, 64($s1) # M[38] = M[15] + M[16] lw $t1, 60($s1) lw $t2, 64($s1) add $t3, $t1, $t2 sw $t3, 152($s1) # M[17] = M[38] lw $t1, 152($s1) sw $t1, 68($s1) # Print M[17] li $v0, 1 lw $a0, 68($s1) syscall # Print NewL as ASCII char li $v0, 4 la $a0, NewL syscall ### End of complied code addu $ra, $s7, $zero jr $ra .data M: .word 0,1,2,3,4,5,6,7,8,9 # constants .space 104 # variables a to z .space 500 # temporaries Blank: .asciiz " " NewL: .asciiz "\n" Tab: .asciiz "\t" Colon: .asciiz ":" SemiC: .asciiz ";" Star: .asciiz "*"
With output (when the spim code is executed):
34
f = 5 + 8;
g = f + 8;
h = f + g;
a = f*f + g*g;
b = g*h + f*g;
c = g*g + h*h;
f = a*a + b*b;
g = b*c + a*b;
h = c*c + b*b;
< h; < N;
#
With output equal to the 33rd Fibonacci number (when the spim code is executed):
3524578
d = 5*2;
c = d*d*d*d*d*d*d;
b = 2*c;
a = 4*c;
k = 0;
x = 8*2;
t = a/(8*k+1) - b/(8*k+4) - c/(8*k+5) - c/(8*k+6);
s = t; < s; < N;
k = 1;
t = a/(8*k+1) - b/(8*k+4) - c/(8*k+5) - c/(8*k+6);
s = s + t/x; < s; < N;
k = 2;
t = a/(8*k+1) - b/(8*k+4) - c/(8*k+5) - c/(8*k+6);
s = s + t/(x*x); < s; < N;
k = 3;
t = a/(8*k+1) - b/(8*k+4) - c/(8*k+5) - c/(8*k+6);
s = s + t/(x*x*x); < s; < N;
#
Here is the output that should be produced by this:
31333334 31414225 31415874 31415924
Key ideas: