CS 3723/3721 -- Tiny Compiler 2: Semantic Actions

(Click or use local copy.)

CS 3721, Spring 2004
Programming Languages

Recitation 6: February 16, 18
Tiny Compiler 1: Translate Assignments
MW 09:00-09:50 pm, SB 3.01.04
Due: 2004-02-23 23:59:59

Recitation 6 must be submitted following directions at: submissions on or before

2004-02-23 23:59:59 (that's Monday, 23 February 2004, 11:59:59 pm) for full credit.
2004-02-27 23:59:59 (that's Friday, 27 February 2004, 11:59:59 pm) for 75% credit.

Overview: The term semantic action refers to extra code added to a parser so that it will carry out some task, often translating from the language the grammar describes to some other language. During the course of the parse, the function calls implicitly carry out a complete traversal of the parse tree, though the actual parse tree is not constructed. During this traversal, extra code can be inserted to do the translation task. This process is known as syntax-directed translation.

Initial Examples of Semantic Actions: Consider a recursive descent parser for the grammar giving arithmetic expressions.

Arithmetic Expressions
*P ---> E '$' E ---> T {('+'\|'-') T} T ---> S {(''\|'/') S} S ---> F '^' S \| F F ---> '(' E ')' \| char**

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.

Translator (in C) of arithmetic expressions to RPN (Reverse Polish Notation):
- C source file: .c
- File showing a run: .txt, .html, .ps, .pdf
Same translator (in Java) of arithmetic expressions to RPN (Reverse Polish Notation):
- Java source file: .java
- File showing a run: .txt, .ps, .pdf

Here is another example of semantic actions: an evaluator of arithmetic expressions:

Evaluator (in C) of arithmetic expressions, producing a double:
- C source file: .c
- File showing a run: .txt, .html, .ps, .pdf

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:

Use a large array for storage, say


        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

(Instead you could handle the constants one-by-one as they arise, and you could use a symbol table, allocating storage for the identifiers that you actually use.)

The code g = 2; might be translated to:


        lw      $t1,    8($s1)       # load constant 2 into $t1
        sw      $t1,    64($s1)      # store into g (which is M[16]

Similarly, h = f + g; might be translated to:


        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])

Output < g; might be translated to:


        li	$v0,    1            # 1 to print an int
        lw	$a0,    64($s1)      # load g's value (M[16]) into $a0
        syscall                      # now print

Finally < B; (print a blank) might be translated to:


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

You can combine all the data together, and you will need the framework of a main function.

How to do the actual translation: This first part of the recitation is only using part of the grammar (just for assignments and output):

Simplified Tiny Grammar
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

Simplified Tiny Grammar

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.

Sample Inputs:

Sample Input 1 (simple):

     f = 5 + 8;
     g = f + 8;
     h = f + g;
     < h; < N;
     $

Possible output spim code (many 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 "*"

Output when MIPS executed by spim:

Sample Input 2 (intermediate):

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; $

Output when MIPS executed by spim:

3524578

Sample Input 3 (complicated):

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; $

Output when MIPS executed by spim:

31333334 31414225 31415874 31415924

What you should submit: Refer to the submissions directions and to deadlines at the top of this page. The text file that you submit should first have Your Name, the Course Number, and the Recitation Number. The rest of the file should have the following in it, in the order below, and clearly labeled, including at the beginning the appropriate item letters: a, b, and c.

Contents of submission for Recitation 6:
Last Name, First Name; Course Number; Recitation Number (6).
a. Java or C++ code for your translator, perhaps in multiple files.
b. Results of a run of your program using Sample Input 1 above, giving the complete resulting MIPS code.
c. Results of executing the MIPS code in b using the SPIM simulator.
d. Results of a run of your program using Sample Input 2 above, giving the complete resulting MIPS code.
e. Results of executing the MIPS code in d using the SPIM simulator.
f. Results of a run of your program using Sample Input 3 above, giving the complete resulting MIPS code.
g. Results of executing the MIPS code in f using the SPIM simulator.

Key ideas: It is relatively easy to add code to the recursive-descent parser that will carry out tasks, such as translating input assignment statements into MIPS assembler code. This process is known as syntax-directed traslation. It is an extremely powerful technique for writing compilers and for other similar tasks.

Revision date: 2004-01-04. (Use ISO 8601, an International Standard.)

CS 3721, Spring 2004 Programming Languages

Recitation 6: February 16, 18 Tiny Compiler 1: Translate Assignments MW 09:00-09:50 pm, SB 3.01.04 Due: 2004-02-23 23:59:59

CS 3721, Spring 2004
Programming Languages

Recitation 6: February 16, 18
Tiny Compiler 1: Translate Assignments
MW 09:00-09:50 pm, SB 3.01.04
Due: 2004-02-23 23:59:59