Tutorial 4

This tutorial implements the repeat statement and logical operators from the previous tutorial in the PL0 compiler.

Question 1

Extend the parser (Parser.java) to include a Pascal-like repeat-until statement; i.e.: $\text{RepeatStatement}\rightarrow \text{KW\_REPEAT StatementList KW\_UNTIL Condition}$ You may assume that the scanner supplies the tokens KW_REPEAT and KW_UNTIL for the keywords "repeat" and "until.

Q1 Part A

Extend the comments in Parser.java describing the grammar to include the repeat-until statement

/*
 * Statement -> WhileStatement | IfStatement | CallStatement | Assignment |
 *          RepeatStatement | ReadStatement | WriteStatement | CompoundStatement 
 * RepeatStatement -> KW_REPEAT StatementList KW_UNTIL Condition
 */

Q1 Part B

Extend the STATEMENT_START_SET

The token KW_REPEAT can start a RepeatStatement.

private final static TokenSet STATEMENT_START_SET =
            LVALUE_START_SET.union(Token.KW_WHILE, Token.KW_IF,
                    Token.KW_READ, Token.KW_WRITE, Token.KW_REPEAT 
                    Token.KW_CALL, Token.KW_BEGIN);

Q1 Part C

Modify method parseStatement to allow for a repeat-until statement

private StatementNode parseStatement(TokenSet recoverSet) {
  return stmt.parse("Statement", STATEMENT_START_SET, recoverSet,
    () -> {
    /* The current token is in STATEMENT_START_SET.
      * Instead of using a cascaded if-the-else, as indicated in
      * the recursive descent parsing notes, a simpler approach
      * of using a switch statement can be used because the
      * start set of every alternative contains just one token. */
    switch (tokens.getKind()) {
      case IDENTIFIER:
        return parseAssignment(recoverSet);
      case KW_WHILE:
        return parseWhileStatement(recoverSet);
      case KW_IF:
        return parseIfStatement(recoverSet);
      case KW_READ:
        return parseReadStatement(recoverSet);
      case KW_WRITE:
        return parseWriteStatement(recoverSet);
      case KW_CALL:
        return parseCallStatement(recoverSet);
      case KW_BEGIN:
        return parseCompoundStatement(recoverSet);
      case KW_REPEAT:
        return parseRepeatStatement(recoverSet);
      default:
        fatal("parseStatement");
        // To keep the Java compiler happy - can't reach here
        return new StatementNode.ErrorNode(tokens.getLocation());
    }
    });
    }

Q1 Part D

Add a method parseRepeatStatement to Parser.java

/*
 * Rule: RepeatStatement -> KW_REPEAT StatementList KW_UNTIL Condition
 * @param recoverSet is a set of terminal symbols used for error recovery. On 
 * completion, the current torken will normally be the first symbol after the repeat
 * statement, and will always contain a symbol in the recoverSet.
 * @return an abstract syntax tree for a repreat statement
 */
private StatementNode parseRepeatStatement(TokenSet recoverSet) {
		return stmt.parse("Repeat Statement", Token.KW_REPEAT, recoverset, 
				() -> { 
						// Current token is KW_REPEAT
						Location loc = tokens.getLocation(); // Location of KW_REPEAT
						// Cannot fail as current token is KW_REPEAT
						tokens.match(Token.KW_REPEAT); 
						StatementNode statement = 
								parseStatementList(recoverSet.union(Token.KW_UNTIL);
						tokens.match(Token.KW_UNTIL, CONDITION_START_SET);
						ExpNode cond = parseCondition(recoverSet);
						return new StatementNode.RepeatNode(loc, statement, cond);
				});
}

Q1 Part E

Add a class StatementNode.RepeatNode representing the abstract syntax tree for a repeat-until statement. This should be similar to the StatementNode.WhileNode but initially you will want to comment out the accept method (until we do static checking for the repeat-until statement)

In the StatementNode class, we add the following as an implementing subclass of StatementNode:

public abstract class StatementNode {
  ...
  public static class RepeatNode extends StatementNode {
    private final StatementNode loopStmt;
    private ExpNode condition;

    public RepeatNode(Location loc, StatementNode loopStmt, ExpNode condition) {
      super(loc); // Call to StatmentNode constructor
      this.loopStmt = loopStmt;
      this.condition = condition;
    }

    /**
    * Provides access to the visitor pattern over trees.
    * Used for static checking and interpreting
    */
    @Override
    public void accept(StatementVisitor visitor) {
      visitor.visitRepeatNode(this);
    }

    public ExpNode getCondition() {
      return condition;
    }

    public void setCondition(ExpNode cond) {
      this.cond = cond;
    }

    public StatementNode getLoopStmt() {
      return loopStmt;
    }

    @Override
    public String toString(int level) {
      return "REPEAT" + newLine(level + 1) + loopStmt.toString(level + 1) +
        newLine(level) + "UNTIL" + condition.toString();
    }
  }
}

Question 2

Extend the type checking in the static semantics to handle the repeat statement introduced above. The static checker is implemented using the Visitor pattern over the tree structure. In interface StatementVisitor, every kind of statement tree has a visited method, which is called in a traversal of the AST that is checking the static semantics for that tree.

Q2 Part A

Extend the interface StatementVisitor to include a visit method for the repeatNode

/**
 * interface StatementVisitor - Provides the interface for the 
 * visitor pattern to be applied to an abstract syntax tree node
 * for a statement.
 * A class implementing this interface must provide 
 * implementations for visit methods for each of the statement 
 * node type.
 */
public interface StatementVisitor {
    void visitBlockNode(StatementNode.BlockNode node);
    void visitStatementErrorNode(StatementNode.ErrorNode node);
    void visitStatementListNode(StatementNode.ListNode node);
    void visitAssignmentNode(StatementNode.AssignmentNode node);
    void visitReadNode(StatementNode.ReadNode node);
    void visitWriteNode(StatementNode.WriteNode node);
    void visitCallNode(StatementNode.CallNode node);
    void visitIfNode(StatementNode.IfNode node);
    void visitWhileNode(StatementNode.WhileNode node);
		void visitRepeatNode(StatementNode.RepeatNode node);
}

Q2 Part B

Uncomment the accept method to StatementNode.RepeatNode

Done - see Question 1 Part E

Q2 Part C

Add a method visitRepeatNode to StaticChecker.java to implement the StatementVisitor interface. It is responsible for checking that the statement part is valid and that the condition is valid and of type boolean. Hints: have look at the visit method for a while loop. Make use of the no interpret ("-i") option (instead of "-s") for the PL0_RD compiler to parse and static check your program (but not execute it). You an use the "-d" option as well to generate (lots of) extra debugging output. For static checking, the files of interest are StaticChecker.java, ExpTransform.java, StatementVisitor.java and Type.Java

/**
 * class StaticSemantics - Performs the static semantic checks on
 * the abstract syntax tree using a visitor pattern to traverse 
 * the tree.
 * See the notes on the static semantics of PL0 to understand 
 * the PL0 type system in detail.
 */
public class StaticChecker implements DeclVisitor, 
  StatementVisitor, ExpTransform<ExpNode> {
  ...
  /*
  * Perform static checking on Repeat Nodes. Must:
  *  1. Check statement component is valid
  *  2. Check that the condition is valid and returns boolean.
  */
  public void visitRepeatNode(StatementNode.RepeatNode node) {
    beginCheck("Repeat");
    node.setCondition(checkCondition(node.getCondition()));
    node.getLoopStmt().accept(this);
    endCheck("While");
  }
}

We can check if a statement is valid by calling the accept method of the statement tree node (passing it the static checker itself) this
```
node.getLoopStmt().accept(this);
```
- This accept method then calls the static checker visit method for the actual statement
- Which exact static checker method is called depends on the form of the statement (statement list, assignment, call, nested repeat statement etc)
Because the condition in a repeat statement must be of type Boolean, we coerce the condition to the boolean.
- May involve e.g. dereferencing a variable of type ref(boolean) → boolean
- AST of coerced condition replaces the condition node of the repeat statement node.
- If coercion is not possible, an error is reported.
The check that the condition returns a Boolean has to be performed after visiting the condition because the visit is responsible for determining its type.
The above checking is performed by the existing method checkCondition that returns a transformed expression node, which is then used to replace the original condition node.

Question 3

Extend Interpreter.java to include an interpreter method for a repeat-until statement.

Q3 Part A

The interpreter class implements the interface StatementVisitor to interpret statements at runtime. Your task is to add a method visitRepeatNode to the interpreter. Hint: Look at the interpreter for the while loop. For the interpreter, you’ll need to look at the notes describing the interpreter as well as Interpreter.java. Remove the "-i", to allow the code interpretation phase to occur. You can still use the "-d" option for additional debugging output.

/*
 * Execute code for a repeat statement (from the AST)
 */
public void visitRepeatNode(StatementNode.RepeatNode node) {
  beginExec("Repeat");
  ExpNode condition = cnode.getCondition();
  /* Execute loop statement until the condition is true */
  do {
    node.getLoopStmt().accept(this);
  } while (condition.evaluate(this).getInteger == Type.FALSE_VALUE);
  endExec("Repeat");
}

Question 4

Add your implementation of parsing logical operators from the previous tutorial to the PL0 compiler, and test it thoroughly.

private ExpNode parse(String rule, TokenSet expected, TokenSet recoverSet,
  ParseNonterminal<ExpNode> parser);
private ExpNode parse(String rule, Token expected, TokenSet recoverSet,
  ParseNonterminal<ExpNode> parser);

/**
  * We add a set of the logical binary operator tokens and defined symbols that 
  * can start a logical termn and hence a condition. 
  */
private final static TokenSet CONDITION_OPS_SET = 
  new TokenSet(Token.LOG_AND, Token.LOG_OR);
private final static TokenSet LOG_TERM_START_SET = 
  REL_CONDITION_START_SET.union(Token.LOG_NOT);
private final static TokenSet CONDITION_START_SET = LOG_TERM_START_SET;

/**
 * Rule: Condition -> LogTerm {(LOG_AND | LOG_OR) LogTerm}
 * Accepts a Condition from the input and proesses the corresponding 
 * Abstract Syntax Tree.
 * @param recoverSet is a set of terminal symbols used for error recovery.
 *@ return an abstract syntaxtree for a condition.
 *
 */
private ExpNode parseCondition(TokenSet recoverSet) {
  return exp.parse("Condition", CONDITION_START_SET, recoverSet, 
    () -> {
      // The current token is in the CONDITION_START_SET
      // Extend the syntax recovery sert with logical operators.
      ExpNode cond = parseLogTerm(recoverSet.union(CONDITION_OPS_SET);
      while (tokens.isIn(CONDITION_OPS_SET)) {
        Operator binaryOp = Operator.INVALID_OP; // Initially set sentinel
        Location opLocation = tokens.getLocation();
        if (tokens.isMatch(Token.LOG_AND)) {
          binaryOp = Operator.LOG_AND;
          tokens.match(Tokens.LOG_AND); // Cannot fail.
        } else if (tokens.isMatch(Token.LOG_OR)) {
          binaryOp = Operator.LOG_OR;
          tokens.match(Token.LOG_OR);
        } else {
          fatal("Unreachable branch in parseCondition");
        }

        /**
          * The recovery set needs to include teh CONDITION_OPS_SET
          * because there nay be another logical opeartor 
          * (LOG_AND or LOG_OR) following which will be matched on the 
          * next iteration of the while loop.
          */
        ExpNode right = parseLogTerm(recoverSet.union(CONDITION_OPS_SET));
        /**
          * cond becomes a new binary operator node, with the old value 
          * of cond as its first argument, and right as its 
          * second argument.*/
        cond = new ExpNode.BinaryNode(opLocation, binaryOp, cond, right);
      }
      return cond;
    });
}

/**
  * Rule: LogTerm -> LOG_NOT LogTerm | RelCondition
  */
private ExpNode parseLogTerm(TokenSet recoverSet) {
  return exp.parse("LogTerm", LOG_TERM_START_SET, recoverSet, 
  () -> {
    ExpNode result = null;
    if (tokens.isMatch(Token.LOG_NOT)) {
      Location opLocation = tokens.getLocation(); // Location of LOG_NOT
      tokens.match(Token.LOG_NOT); // Cannot fail
      result = parseLogTerm(recoverSEt);
      result = new ExpNode.UnaryNode(opLocation, Operator.NOT_OP, result);
    } else if (tokens.isIn(REL_CONDITION_START_SET)) {
      result = parseRelCondition();
    } else {
      fatal("Unreachable breanch in parseLogTerm");
    }
    return result;
  });
}

Question 5

Because the type checking for operators is handled in a general way, the only thing that needs be done for static checking is to ensure the logical operators are correctly typed. This is done in syms.Predefined.java by defining the types of the operators in the predefined scope.

// The types for logical binary and unary operators are 
// already defined in Predefined.java
predefined.addOperator(Operator.AND_OP, ErrorHandler.NO_LOCATION,
  LOGICAL_BINARY);
predefined.addOperator(Operator.OR_OP, ErrorHandler.NO_LOCATION,
  LOGICAL_BINARY);
predefined.addOperator(Operator.NOT_OP, ErrorHandler.NO_LOCATION,
  LOGICAL_UNARY);

Question 6

Extend Interpreter.java to handle binary logical operators "&&" and "||" and the unary logical operator "!" introduced in the previous tutorial. These operators use the existing ExpNode.BinaryNode and ExpNode.UnaryNode tree structures, but with the additional binary operators AND_OP and OR_OP and th unary operator NOT_OP in Operator.

For this question (but not the next) the code generated for the binary operators may evaluate both its arguments. Because the Boolean true and false are represented in the compiler by the integer values Type.TRUE_VALUE (1) and Type.FALSE_VALUE (0) respectively, you cannot use Java logical operators on them in the interpreter code but you can just Java bitwise operators "&" and"|" but you cannot use the bitwise complement operator "~" because the latter when applied to 1 (representing TRUE) gives the hexadecimal number 0xFFFFFFFFE which is not the representation of false (it should be 0), and ~ applied to 0 gives 0xFFFFFFFF which is not the representation of true (it should be 1)

In the method visitBinaryNode within Interpreter.java, we add cases for each of the operators AND_OP and OR_OP to the switch statement:

public Value visitBinaryNode(ExpNode.BinaryNode node) {
	beginExec("Binary");
	int result = -1;
	/* Evaluate the left and right sides of the operator expression */
	int left = node.getLeft().evaluate(this).getInteger();
	int right = node.getRight().evaluate(this).getInteger();
	/* Perform the operation on the left and right side of the expression */
	switch (node.getOp()) {
    /* Mathematical operations */
    case ADD_OP:
      result = left + right;
      break;
    case SUB_OP:
      result = left - right;
      break;
    case MUL_OP:
      result = left * right;
      break;
    case DIV_OP:
      /* Error when division by zero occurs */
      if (right == 0) {
          runtime("Division by zero", node.getRight().getLocation(),
                  currentFrame);
      }
      result = left / right;
      break;
    /* Logical operations - resulting in 1 for true and 0 for false */
    case EQUALS_OP:
      result = (left == right ? Type.TRUE_VALUE : Type.FALSE_VALUE);
      break;
    case NEQUALS_OP:
      result = (left != right ? Type.TRUE_VALUE : Type.FALSE_VALUE);
      break;
    case GREATER_OP:
      result = (left > right ? Type.TRUE_VALUE : Type.FALSE_VALUE);
      break;
    case LESS_OP:
      result = (left < right ? Type.TRUE_VALUE : Type.FALSE_VALUE);
      break;
    case LEQUALS_OP:
      result = (left <= right ? Type.TRUE_VALUE : Type.FALSE_VALUE);
      break;
    case GEQUALS_OP:
      result = (left >= right ? Type.TRUE_VALUE : Type.FALSE_VALUE);
      break;
		case AND_OP:
			result == left & right;
			break;
		case OR_OP:
			result = left | right;
			break;
    case INVALID_OP:
    default:
      errors.fatal("PL0 Internal error: Unknown operator",
              node.getLocation());
			}
	endExec("Binary");
	return new IntegerValue(result);
}

And we do the same for logical not within visitUnaryNode

/**
 * Expression evaluation for a unary operator expression
 **/
public Value visitUnaryNode(ExpNode.UnaryNode node) {
  beginExec("Unary");
  /* Handle unary operators */
  int result = node.getArg().evaluate(this).getInteger();
  //noinspection SwitchStatementWithTooFewBranches
  switch (node.getOp()) {
    case NEG_OP:
      result = -result;
      break;
		case NOT_OP:
			result = (result == Type.TRUE_VALUE ? Type.FALSE_VALUE : Type.TRUE_VALUE);
    default:
        // Never reached
        errors.fatal("PL0 Internal error: Unknown operator", node.getLocation());
  }
  endExec("Unary");
  return new IntegerValue(result);
}