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.
  1. Re-implement the symbol table as a binary search tree.
  2. Re-implement the symbol table as a hash table.
  3. Re-implement the symbol table, the code generator and the stack machine as C++ classes.
  4. 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.
    1. Declarations: Change the semantic processing of identifier references to require previous declaration.
    2. Real literals and variables: Extend the symbol-table 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.
    3. Multiplication and division: Make appropriate changes to the semantic routines to handle code generation based on the new tokens.
    4. if and while statements: Semantic routines must generate the proper tests and jumps.
    5. 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:
    1. An interpreter for the code produced by the compiler
    2. Substitution of a table-driven parser for the recursive descent parser in the Micro compiler.
  5. Extend the Micro-II compiler. A self-contained description of Macro is included in the cs360/compiler\_tools directory. In brief, the following extensions are required.
    1. Scanner extensions to handle the new tokens, use of parser generator to produce new tables(20 points).
    2. Declarations of integer and real variables(10 points).
    3. Integer literals, expressions involving integers, I/O for integers, and output for strings(10 points).
    4. The loop and exit statements and addition of the else} and elsif parts to the if statement (20 points).
    5. Recursive procedures with parameters(8 points for simple procedures, 8 points for recursion, 12 points for parameters).
    6. Record declarations and field references(8 points).
    7. Array declarations and element references(12 points).
    8. Package declarations and qualified name references(12 points).
    The total number of points is 120.
  6. 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.
    7. Basic Subset(130 points)
    1. (100 points)
      1. Integer, Real, Boolean types (5 points)
      2. Basic expressions involving Integer, Real and Boolean types (+, -, *, /, not, and, or, abs, mod, **, <, <=, >, >=, =, /=) (30 points).
      3. Input/Output
        1. Input of Integer, Real, Boolean scalars(5 points).
        2. Output of String literals and Integer, Real and Boolean expressions(excluding formatting)(5 points).
      4. Block structure (including declaration of local variables and constants) (20 points).
      5. Assignment statement (10 points).
      6. if, loop, and exit statements (10, 5, 10 points respectively)
    2. (30 points) Procedures and scalar-valued functions of no arguments (including nesting and non-local variables).
    Optional Features(336 points possible)
    1. loop statements (15 points total)
      1. in and in reverse forms (10 points)
      2. while form (5 points)
    2. Arrays (30 points total)
      1. One-dimensional, compile-time bounds, including First and Last attributes (10 points)
      2. Multi-dimensional, compile-time bounds, including First and Last attributes (5-points)
      3. Elaboration-time bounds (9 points)
      4. Subscript checking (3 points)
      5. Record base type (3 points)
    3. Boolean short-circuit operators (and then, or else) (12 points)
    4. Strings (23 points total)
      1. Basic string operations (string variables, string assigns, all string operators (&, Substr, etc), I/O of strings) (10 points)
      2. Unbounded-length strings (5 points)
      3. Full garbage collection of unbounded-length strings (8 points)
    5. Records (15 points total)
      1. Basic features (10 points)
      2. Fields that are compile-time bounded arrays (2 points)
      3. Fields that are elaboration-time sized (both arrays and records) (3 points)
    6. Procedures and functions(53 points total)
      1. Scalar parameters (15 points)
      2. Array arguments and array-valued functions (compiler-time bounds) (7 points )
      3. Array arguments and array-valued functions (elaboration-time bounds) (5 points)
      4. Record arguments and record-value functions (4 points)
      5. Conformant array parameters (i.e. array declarations of the form {type array ( T range <>) of T2}) (8 points)
      6. Array-valued functions (elaboration-sized bounds) (3 points)
      7. Array-valued functions (conformant bounds) (4 points)
      8. Forward definition of procedures and functions (3 points)
      9. String arguments and string-valued functions (4 points)
    7. case}statement (20 points total)
      1. Jump code (10 points)
      2. If-then-else code (4 points)
      3. Search-table code (6 points)
    8. Constrained subtypes (including First and Last attributes) (10 points total)
      1. Run-time range checks (7 points)
      2. Compile-time range checks (3 points)
    9. Folding of scalar constant expressions (8 points)
    10. Initialized variables (10 points total).
      1. Compile-time values, global (without run-time code) (3 points)
      2. Compile-time values, local (2 points)
      3. Elaboration-time values (2 points)
      4. Record fields (3 points)
    11. Formatted writes (3 points).
    12. Enumerations (18 points total).
      1. Declaration of enumeration types; variables, assignment, and comparison operations (9 points)
      2. Input and Output of enumeration values (5 points)
      3. Succ, Pred, Char, and Val attributes (4 points)
    13. Arithmetic type conversion (3 points).
    14. Qualified names (from blocks and subprograms) (3 points).
    15. Pragmata (2 points).
    16. Overloading (25 points total)
      1. Subprogram identifier (18 points)
      2. Operators (7 points)
    17. Packages (55 points total).
      1. Combined packages (containing both declaration and body parts); qualified access to visible part (20 points)
      2. Split packages (with distinct declaration and body parts) (5 points)
      3. Private types (10 points)
      4. Separate compilation of package bodies (20 points)
    18. Use statements (11 points)
    19. Exceptions (including exception declarations, raise statements, exception handlers, predefined exceptions) (20 points).
    Extra credit project extensions: