CSE 401 Autumn 1997 (Henry): Compilers

Details / Project Description

The number of points for each modification roughly reflects the amount of effort that I expect it will take to implement the modification.

Comments (10 points)

Extend the PL/0 language to allow comments. A comment begins with two adjacent minus signs ("-") and extends to the end of the line. Comments are treated as whitespace (not tokens). The following code illustrates some comments:

    i := x + y; -- this is a comment
    j := a - b; -- this computes "a + (-b)"
    -- a comment; still in the comment -- and more comment

Test Operators (10 points)

Add two new left associative binary operators and and or. The and operator has higher precedence than or, but and has lower precedence than all other operators. Both operators take test values as operands and return a new test value, using the obvious semantics. Both operators are strict, in that they will evaluate both operands.

If-Then-Else Statements (10 points)

Replace the if statement with an if-then-else statement with the following syntax:

    <if stmt> ::= if <test> then <stmt list-1> [else <stmt list-2>] end

The semantics are as expected: if the <test> evaluates to true, execute the statements in <stmt list-1>; otherwise, execute the statements in <stmt list-2>, if any. (Note: the -1 and -2 do not represent new syntactic entitites, but rather distinguish two entities that have the same syntax.)

Richer First Class Typing (0 points)

Add two differerent first class types to the language. These new types are ranges, and sets, and will be described in detail in the next sections. The built in integer type and ranges are termed scalar types; sets are composed types.

These extensions mean that the PL/0 programmer can declare variables or formal parameters to be ranges or sets and use them in essentially all the ways in which integers (the only previously available first-class type) can be used, except:

• only integers or ranges are allowed in input and output statements;
• strong static typing is to be enforced at all times;
• as otherwise specified in the following sections.

This extension will require extending the base language to support type declarations. Type declarations can appear anywhere variable declarations can appear. A name can only be used once in a scope, either to denote a type, variable, procedure or constant.

There are no points for this extension, since you actually will do the work for this extension in other extensions.

Scalar Constant Expressions (15 points)

A scalar constant expression is one that can be fully evaluated by the compiler. Scalar constant expressions may may not involve composed types, procedure parameters, function calls, nor the input primitive.

The following examples illustrate some legal scalar constant expressions:

    3 + -4

Ranges (25 points)

Range types are declared in a type declaration. A range type declaration is described with this pseudo-syntax:

    type Id = <constant expression> .. <constant expression>

The name of the range type is given by the identifier after the type keyword; this identifier must not have been previously declared in the scope of the declaration.

The constant expressions must be scalar constant expressions. The first constant expression is called the lower bound and must be less than or equal to the second constant expression, called the upper bound. The lower bound may not be less than -(2^9) and the upper bound may not be greater than (2^9)-1. (The range is made rather narrow so that the set data type may be implemented efficiently and naively.)

A legal value of a range type is an integer that is between the lower and upper bond, inclusive.

A variable or formal that is a range type can be used any place that an integer can be used. An value may be assigned to a range variable (alternatively, used as an actual parameter) only if the value is in the variable's (alternatively, formal parameter's) declared range. Any other value outside of the range is to result in either a compile time error or a run time abort, with some kind of appropriate error indication.

Here are some examples of range declarations and uses:

  type UCode3 = 0..8;
  type UCode4 = 0..15;
  type SCode4 = -8..7;
  var b3 : UCode3;
  var b4 : UCode4;

  b4 := 5;		-- assignment OK
  b4 := 17;		-- assignment will cause error/abort
  b4 := b3;		-- assignment will always succeed

Set Types (40 points)

Set types are declared in a type declaration.

The type of a set is described using this pseudo-syntax:

    type Id = set of Id

The first identifier is the name of the set type. The second identifier must name a range type; this type is called the base type of the set.

A set type describes the set of values that is the powerset of its base type, i. e. the set of all subsets of values of the base type, including the empty set. The base type must be a subrange type.

Set types are useful for writing programs that deal with sets of data, and can be thought of as arrays of bits, bit vectors or bit maps. Sets that can hold only a small number of elements can be efficiently implemented using arrays of bits, but this may be inefficient in both space and time for sparse sets.

Some unary and binary operators are overloaded to combine set values of two identical types yielding a new set value of that type.

• binary + (set union)
• binary - (set difference)
• binary * (set intersection)
• prefix unary - (set complement)

Each of the 6 relational operators are overloaded to compare set values of two identical types yielding a value suitable for use as a test. For example, the operator < checks if the left operand is a strict subset of the right operand, and so forth.

The new unary prefix operator card takes a set value and returns the cardinality of the set as a value of type integer.

The new binary operator in checks if the left operand is a member of the set given by the right operand. The left operand must be a value that is of the base type of the set which is the right operand. The value returned is suitable for use as a test.

A set of type Id may be constructed using this pseudo-syntax:

  Id { <optional comma separated expression list> }

(Note that the curly braces are to appear literally in the pl/0 program; they are not used here as meta characters to express meaning to the BNF grammar.)

The types of the expressions must be the base type of set named by Id. In the case of sets whose base types are ranges the expressions must evaluate to values that are in the range. Any other values outside of the range are to result in either a compile time error or a run time abort, with some kind of appropriate error indication.

You should use whatever runtime data structure(s) is(are) appropriate to implement sets. There is a lot of room for cleverness in the implementation, but you should first implement the easiest most general data structure, and then refine it as time permits. You will get extra credit for more clever implementations.

Here is are some sample declarations and uses of sets:

  type UCode4 = 0..15;
  type SUCode4 = set of UCode4;
  var s1: SUCode4, s2:SUcode4;
  s1 := SUCode4{0,15};
  s2 := - s1;		-- set with elements 1..14 inclusive
  s2 := s1 - s1;	-- set with no elements
  s2 := s1 + s1;
  if s2 = s1 then ...	-- if test succeeds

Functions (20 points)

A procedure may optionally return a result; such a value-returning procedure is called a function. To indicate that a procedure returns a result, a result type declaration is added after the list of formal parameters in the procedure declaration. (This is optional, since procedures are still supported as well as functions.)

For example, the following are legal function declarations:

    procedure foo(x:int, y:color): int;
    begin
       <stmt list>
    end foo;

    procedure bar(): color;
    var x:int;
    begin
       <stmt list>
    end bar;

Function calls can be used anywhere that an expression of the appropriate type can be used. Syntactically, function call expressions have higher precedence than other operators. Functions may also be called like procedures, as a separate statement; in this case the value returned from the function is discarded. The type of the result of a function can be any first class type, including sets. The result is returned by value.

Return Statements (25 points)

The return statement can be used to exit a procedure, immediately transferring control to the end of the procedure body. It is legal for a procedure (but not a function) to return by "falling off" the procedure body without encountering an explicit return statement.

To return a value from a function, the return statement is used with an expression. Both forms are captured by

    <return stmt> ::= return [ <expr> ]

The type of the expression returned must match the type declared for the enclosing function. It is illegal for a value-returning return statement to appear in a procedure not declared to return a result. It is similarly illegal for a non-value-returning return statement to appear in a function. It is an error if it is possible for execution to reach the end of a function's body without executing a return statement. In particular, a function whose only return statement is in a then clause of an if statement is invalid, since if the then clause is not taken then the function will not return anything.

The following illustrates some legal uses of return statements:

procedure foo(x:int,y:color):int;
begin
  if y then return x; end;
  return x * 5;
end foo;

Iteration/Generation (20 points)

The extended language is to implement a for statement with the pseudo syntax:

    <for stmt> ::= for <Id> in <expr> do <stmt list> end

The expression after the in keyword is called the control expression and must be of some set type. The expression is evaluated only once. The identifier must be previsously declared as a variable with the base type of the expression; this is the loop control variable. The control variable is assigned with any member of the control set not previously chosen, and the statement list forming the body is executed. This process of assignment and execution repeats until all members of the control expression have been assigned to the control variable. The control variable may be re-assigned during the course of executing the statement list body.

The following illustrates some legal uses of for statements:

  type UCode4 = 0..15;
  type SUCode4 = set of UCode4;
  var s1: SUCode4, s2:SUcode4;
  var i: int;
  s1 := SUCode4{0,15};
  for i in s1 do ... end;		-- i has value 0 and 15
  for i in SUCode4{0,2,4,6,8} do ... end;

Empty Statements (5 points)

Add empty statements to the language. An empty statement consists of nothing, and does nothing when executed.

The practical impact of empty statements is that `;' can be used as both separators and terminators.

Switch Statements (30 points)

The extended language is to support a switch statement. The pseudo syntax is:

    <switch stmt> ::= switch <Expr> of <switch labels> end
    <switch labels> ::=
	{ case <case label> : <statement list> end optional ;}
    <case label> ::= default | <constant expression>

The first expression is the control expression. The control expression must be a scalar type. The constant expression case labels must be the same type as the control expresssion. Either zero or one case label must be the special label default. The constant expression case labels must have values that are mutually exclusive.

The control expression is evaluated exactly once. If a case label expression has the same value as the control expression, then the corresponding statement is executed; otherwise, the statement labeled with the special label default is executed if there is one.

Here is an example switch statement, of dubious stylistic quality. I have used the optional ';' after some, but not all, of the occurances of the end keyword.

  switch i of
    case 4:	j := 7; end
    case default:	l := 11; end;
    case 4+3:	k := 10; end
  end