CSCI 439 lab 5 Sample Solutions

CSCI 439: Lab 5 Sample Solutions (Spring 2025)

The lab exercise consists of four equally-weighted questions worth a total of 18 marks.

All four questions are based on the following grammar:

Tokens
SEMI:   ";"
OPEN:   "("
CLOSE:  ")"
ADD:    "+"
SUB:    "-"
DIV:    "/"
MUL:    "*"
ASN:    "="
ADDASN: "+="
SUBASN: "-="
IDENT: [a-z]+
NUMLIT: [0-9]+

Grammar
 1. statements: assign statements
 2. statements: assign
 3. assign: IDENT assignop addexpr SEMI
 4. assignop: ASN
 5. assignop: ADDASN
 6. assignop: SUBASN
 7. addexpr: addexpr addop multexpr
 8. addexpr: multexpr
 9. multexpr: multexpr multop brackexpr
10. multexpr: brackexpr
11. brackexpr: OPEN addexpr CLOSE
12. brackexpr: value
13. value: NUMLIT
14. value: IDENT
15. addop: ADD
16. addop: SUB
17. multop: MUL
18. multop: DIV
*rules numbered to allow easier referencing in discussions

Questions 1-3 are all based on the following input:

x = a * 5 * ( x * y ) / ( a * 5 ) - ( x + y )

Question 1: Syntax graphs [4.5 marks]

Based on the grammar and input given above:

Sketch the parse tree for the input.

Sample Solution:
 ... assuming everyone is fine with sketching parse trees by now,
     the only real trick was spotting the initial addexpr captures the - op
     (see simplified AST below for confirmation on the expression structure)

Sketch an abstract syntax tree corresponding to your parse tree (i.e. with nodes corresponding to the operators and leaves corresponding to the identifiers/numbers).

Sample Solution:
Just the raw expression tree, none of the syntactic fluff, e.g.
              =
            /  \
           x    -
               / \
              /   \
             /     \
         (div)/     +
           / \     / \
          /   \   x   y
         /     \
        *       *
       / \     / \
      /   \   a   5
     *     +
    / \   / \
   a   5 x   y

Sketch a directed acyclic syntax graph corresponding to your syntax tree but with common subtrees collapsed.

Sample Solution:
This is just collapsing the common arcs for the tree above, notably
  (i) having a single a*5 subtree that is referenced twice
  (ii) having a single leaf for each of a, x, y, 5
       (x and y getting referenced once each from the x*y plus once each from the x+y)

Question 2: Value-number systems [4.5 marks]

Produce a value-number table corresponding to your syntax graph.

The first five rows of the table are provided below.

index	node/leaf	operand1	operand2
0	leaf: a	symbol table ref to a	n/a
1	leaf: x	symbol table ref to x	n/a
2	leaf: y	symbol table ref to y	n/a
3	leaf: 5	literal 5	n/a
4	node: *	0 (index for a)	3 (index for 5)
*Sample solution*
5	node: *	1 (index for x)	2 (index for y)
6	node: *	4 (a*5)	5 (x*y)
7	node: /	6 ((a5)(x*y))	4 (a*5)
8	node: +	1 (index for x)	2 (index for y)
9	node: -	7 (whole numerator)	8 (x+y)
10	node: =	1 (index for x)	9 (expression result)

Node 7 is where we see the value come in, being able to re-use the a*5 computation without actually re-computing it. Algorithms to determine what values are maintained in registers could make a pass through the table and identify the last point where an entry is referenced, then treat that as the last point at which its register is actually needed.

Question 3: Three-address codes [4.5 marks]

Assuming you have an unlimited set of registers available (R1, R2, R3, ...), rewrite the statement using a sequence of ^*three-address codes and briefly explain your choice of 'core' operations. (^*Three is just the upper limit: you can include some operations that use just two operands.)

The first five statements are provided below.

R1 = a
R2 = x
R3 = y
R4 = 5
R5 = R1 * R4
...

Sample Solution:
The choice of core operations seems pretty basic, just assignment
and the usual basic math ops (+ - * /)
R1 = a
R2 = x
R3 = y
R4 = 5
R5 = R1 * R4 (a*5)
R6 = R2 * R3 (x*y)
R7 = R5 * R6 (a*5)*(x*y)
R8 = R7 / R5 ((a*5)*(x*y))/(a*5)
R9 = R2 + R3 (x+y)
R10 = R8 - R9 full RHS expression
R2 = R10 (or use R2 as LHS in prev step?)
x = R2

Question 4: Single-static assignment (SSA) [4.5 marks]

The following sequence of statements represents a program in our grammar.

a = 200 ;
b = a + 1 ;
x = a * 7 ;
y = 23 * x ;
a += b ;
a = x + y ;
b = a + 1 ;
a += b ;
b = x + y ;
y -= 200 ;
x = x + y

Rewrite the sequence using single-static aassignment and briefly explain where/why you chose to introduce new intermediate variables.

Sample Solution:
Here I assumed our 'variables' are likely to be register based,
so added variables for the literal values as well (V1, V7, V23, V200),
then introduced a new variable each time we changed the computed value
for a, b, x, or y (to hold the newly computed value separate from earlier
stored values)

v1 = 1
v7 = 7
v23 = 23
v200 = 200
a1 = 200 ;
b1 = a1 + v1 ;
x1 = a1 * v7 ;
y1 = v23 * x1 ;
a2 = a1 + b1 ;
a3 = x1 + y1 ;
b2 = a3 + v1 ;
a4 = a3 + b2 ;
b3 = x1 + y1 ;
y2 = y1 - v200 ;
x2 = x1 + y2