HW 9 and 10

CS 451-651 Homework 9 and 10

The first installment is due Monday, Nov 9
The rest is due Monday, Nov 16

You may do the work in any order; but you must submit a good chunk by the first due date.
(The initially assigned piece, arrays, is sufficient for the first half. But you might want to do a bit more so there's not too much left for the next week!)

1. Arrays

process an array declaration
determine its size (as a compile-time value, i.e. a Java int value) <<unless: you want to implement dynamic allocation>>
allocate it in memory
manage "array of int" type representation and checking
implement arrayRef's as values that can appear in expressions and on the left side of an assignment statement;
type checking should catch the error in which an array name is used in an expression without being subscripted.

You are not required or expected to implement bounds checking on array references. (It wouldn't hurt to think about how this might be done, at least within the same piece of program that declares the array.)

2. Booleans and Relationals

If we're to implement IF and WHILE, we'll need to be able to compare two expressions. There are various pieces to this.

Add another layer to the expression grammar to account for relational operators, which have a lower precedence than + or -.
(It's sufficient to just do "==" and "<" ... though see "hint", below)
You can add the new operations into BinOp -- it doesn't require a new node.
The result type is "boolean", so you'll need to create that type.
(declaring boolean variables is not required, but it should be pretty trivial. Why not?)

Note that the ILOC compare instructions, like CMP_LE, have a target register which will hold a boolean value, in our case either 0 (false) of 1 (true). This can be used directly in the CBR and CBRN instructions.

Hint: As you know, there can be three arguments to newSymbol in the jflex (scanner) portion: here's an example.

"+" { System.out.println(" Scan: '"+yytext()+"'"); return sf.newSymbol("Plus", sym.PLUS, sym.PLUS);

The second argument is used by the parser in determining which rule to apply, whether to shift or reduce, etc. The third argument is the VALUE returned from the scanner -- what's accessible via the colon variable.

To save work with the 6 relationals, you can define a terminal symbol RELOP, as well as LT EQUALS etc. Have the scanner return type sym.RELOP, but value sym.LT etc -- the latter corresponding to the particular symbol. Presto! now you only need one rule and one action routine to get all 6 relops.

(p.s.: if you want to have sym.EQUALS defined, then simply declare it as a terminal in parser.cup. )

Why not do this all the time? Well, often it works: we could have ADDOP including PLUS and MINUS, MULOP including TIMES and DIVIDE. But -- with that definition, we'd have trouble implementing "*" as the C "dereference" operator, because the parser would not be able to distinguish between "*" and "/".

3. IF and WHILE

As discussed in class.

IF need not include ELSE.
It would be good to have the body of the IF or WHILE be a block -- { StmtList }. Optionally, it can also be a single statement. (you could start with a single stmt, of course, for simplicity.)
WHILE is so much like IF, it's tree rep. can probably live in the same class.

With all this in place, you should be able to compute an interesting value, like 6! (6 factorial). There's a simple way to do that in a loop; we'll do the recursive form once we've implemented functions. You could also sum an array, find the max element of an array ... all kinds of exciting things.