CSCI 439: Lab 5 (Spring 2025)

Lab 5 is a little different, being a more old-school paper/pencil style of assignment.

It will be due by the start of the lecture on Wednesday April 2nd, and can be submitted either on paper in person or as a .pdf emailed to David.Wessels@viu.ca.

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:

  1. Sketch the parse tree for the input.

  2. 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).

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

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.

indexnode/leafoperand1operand2
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) (index for 5)
...

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

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.