Exercises
The exercises which follow vary in difficulty. In each case, determine
what modifications must be made to the grammar, the symbol table and to
the stack machine code.

Reimplement the symbol table as a binary search tree.

Reimplement the symbol table as a hash table.

Reimplement the symbol table, the code generator and the stack machine
as C++ classes.

Extend the Micro Compiler with the extensions listed below. The extensions
require the modification of the scanner to handle the new tokens and modifications
to the parser to handle the extended grammar.

Declarations: Change the semantic processing of identifier references to
require previous declaration.

Real literals and variables: Extend the symboltable routines to store
a type attribute with each identifier. Extend the semantic routines that
generate code to consider the types of literals and variables they receive
as parameters.

Multiplication and division: Make appropriate changes to the semantic routines
to handle code generation based on the new tokens.

if and while statements: Semantic routines must generate
the proper tests and jumps.

Parameterless procedures: The symbol table must be extended to handle nested
scopes and the semantic routines must be extended to generate code to manage
control transfer at each point of call and at the beginning and end of
each procedure body.
Optional additions include:

An interpreter for the code produced by the compiler

Substitution of a tabledriven parser for the recursive descent parser
in the Micro compiler.

Extend the MicroII compiler. A selfcontained description of Macro is
included in the cs360/compiler\_tools directory. In brief, the following
extensions are required.

Scanner extensions to handle the new tokens, use of parser generator to
produce new tables(20 points).

Declarations of integer and real variables(10 points).

Integer literals, expressions involving integers, I/O for integers, and
output for strings(10 points).

The loop and exit statements and addition of the else}
and elsif parts to the if statement (20 points).

Recursive procedures with parameters(8 points for simple procedures, 8
points for recursion, 12 points for parameters).

Record declarations and field references(8 points).

Array declarations and element references(12 points).

Package declarations and qualified name references(12 points).
The total number of points is 120.

The compiler is to be completely written from scratch. The list below assigns
points to each of the features of the language, with a basic subset required
of all students identified first. All of the other features are optional.

Basic Subset(130 points)

(100 points)

Integer, Real, Boolean types (5 points)

Basic expressions involving Integer, Real and Boolean types (+, , *, /,
not, and, or, abs, mod, **, <, <=,
>, >=, =, /=) (30 points).

Input/Output

Input of Integer, Real, Boolean scalars(5 points).

Output of String literals and Integer, Real and Boolean expressions(excluding
formatting)(5 points).

Block structure (including declaration of local variables and constants)
(20 points).

Assignment statement (10 points).

if, loop, and exit statements (10, 5, 10 points respectively)

(30 points) Procedures and scalarvalued functions of no arguments (including
nesting and nonlocal variables).

Optional Features(336 points possible)

loop statements (15 points total)

in and in reverse forms (10 points)

while form (5 points)

Arrays (30 points total)

Onedimensional, compiletime bounds, including First and Last attributes
(10 points)

Multidimensional, compiletime bounds, including First and Last attributes
(5points)

Elaborationtime bounds (9 points)

Subscript checking (3 points)

Record base type (3 points)

Boolean shortcircuit operators (and then, or else) (12 points)

Strings (23 points total)

Basic string operations (string variables, string assigns, all string operators
(&, Substr, etc), I/O of strings) (10 points)

Unboundedlength strings (5 points)

Full garbage collection of unboundedlength strings (8 points)

Records (15 points total)

Basic features (10 points)

Fields that are compiletime bounded arrays (2 points)

Fields that are elaborationtime sized (both arrays and records) (3 points)

Procedures and functions(53 points total)

Scalar parameters (15 points)

Array arguments and arrayvalued functions (compilertime bounds) (7 points
)

Array arguments and arrayvalued functions (elaborationtime bounds) (5
points)

Record arguments and recordvalue functions (4 points)

Conformant array parameters (i.e. array declarations of the form {type
array ( T range <>) of T2}) (8 points)

Arrayvalued functions (elaborationsized bounds) (3 points)

Arrayvalued functions (conformant bounds) (4 points)

Forward definition of procedures and functions (3 points)

String arguments and stringvalued functions (4 points)

case}statement (20 points total)

Jump code (10 points)

Ifthenelse code (4 points)

Searchtable code (6 points)

Constrained subtypes (including First and Last attributes) (10 points
total)

Runtime range checks (7 points)

Compiletime range checks (3 points)

Folding of scalar constant expressions (8 points)

Initialized variables (10 points total).

Compiletime values, global (without runtime code) (3 points)

Compiletime values, local (2 points)

Elaborationtime values (2 points)

Record fields (3 points)

Formatted writes (3 points).

Enumerations (18 points total).

Declaration of enumeration types; variables, assignment, and comparison
operations (9 points)

Input and Output of enumeration values (5 points)

Succ, Pred, Char, and Val attributes (4 points)

Arithmetic type conversion (3 points).

Qualified names (from blocks and subprograms) (3 points).

Pragmata (2 points).

Overloading (25 points total)

Subprogram identifier (18 points)

Operators (7 points)

Packages (55 points total).

Combined packages (containing both declaration and body parts); qualified
access to visible part (20 points)

Split packages (with distinct declaration and body parts) (5 points)

Private types (10 points)

Separate compilation of package bodies (20 points)

Use statements (11 points)

Exceptions (including exception declarations, raise statements,
exception handlers, predefined exceptions) (20 points).
Extra credit project extensions:

Language extensions  array I/O, external procedures, sets, procedures
as arguments, extended data types.

Program optimizations  eliminating redundant operations, storing frequently
used variables or expressions in registers, optimizing Boolean expressions,
constantfolding.

Highquality compiletime and runtime diagnostincs  ``Syntax error:
operator expected", or ``Subscript out of range in line 21; illegal value:
137". Some form of syntactic error repair might be included.