CS405 Assignment 8

Due Dec 10, 2004 (hard deadline)

Design and implement an interpreter for the matrix programs. The interpreter should traverse the syntax tree and execute the statements of the program. The interpreter will consist of the following components:

1. Construct a set of interpretation routines for each general root symbol in the syntax trees. For example,

• if statement -to evaluate the condition and then either to skip the if-part or to interpret the if-part depending on whether the condition is true one for arithmetic operators, etc.
• arithmetic expression- to calculate based on matrix arithmetic# and return the result.
• call –to interpret the syntax tree associated with the procedure
• assignment - update the value for the left-hand side valuable (after evaluating the right-hand side) in the corresponding symbol table (local or global, dependent on the scope of the left-hand side variable)
• ….

2. Type-checking-- Interpretation process is performed over the syntax tree directly, as opposed to compilation process, where program execution is performed after executable code is generated. Therefore, we need to integrate the type-checking process into the interpretation process, to be specific--

• for an assignment statement, the left-hand side type should be the same as the type of the result returned in the right-hand side expression.#
• for arithmetic operator, only int, vector, matrix type operand can be involved, otherwise there should throw an error:
  for +, -,* the associated data type should be the same, and the resultant expression type is of the same type—there is one except with *, where integer could be associated with vector (matrix) too , and the resultant type in this case is vector (matrix). For vector or matrix type, type checking also involves to check the consistency of dimension size as is noted in the bottom.
• for relational expression, both operand should be int type.
• …--think about any other type checking wherever you feel necessary.

In the case of any errors, your interpreter need only print an appropriate error message and halt.

3. The final output of program interpretation process are the global variable and their value..

4. In summary, your output should consist of the source program, the output as required in previous assignment (assign7) and the evaluated value for the global variables.

Suggestion: Develop this incrementally over the following steps.

• Make your interpreter work first for expressions without statements or function calls.
• Next handle statements.
• Then handle expressions calling functions.

---

# It is assumed that you have basic knowledge of linear algebra. If not, the vector and matrix expression semantics is briefly introduced here:

below in the italicized expression, we use m, n, k to represent the declared size for the corresponding dimension in vector/matrix—e.g., v1[m] represents a vector

of size m, M1[m][n] represents a matrix of m rows, n columns; they are not referencing individual element in vector/matrix. However, please note we use h, i, j to

index into the individual element in the vector/matrix to indicate how each element in the resultant vector/matrix is calculated.

vector +/- vector : v1[m]+v2[m]-> v3[m], where each v3[i]=v1[i]+v2[i], 0<=i<m ; so is the “-“ operator.

matrix +/- matrix: M1[m][n]+M2[m][n]->M3[m][n], where for each I,j, 0<= i <m, 0<= j <n, M3[i][j]=M1[i][j]+M2[i][j]

int* vector or int*matrix or vector*int or matrix *int: denotes to multiple each element inside the vector/matrix with the integer.

vector * vector : v1[m] *v2[n] ->M[m][n], where for 0<=i<m, 0<=j<n , M[i][j]=v1[i]* v2[j]

matrix * matrix: M1[m][n]*M2[n][k]->M3[m][k], where for 0<=i<m, 0<=j<k, M3[i][j]=S_h=0..n-1(M1[i][h]*M2[h][j])