Compiler Design Assignments

Assignment 1

Provide regular expressions to characterize the following lexical items:

  1. Identifiers: alphanumeric strings starting with an alphabet, and can also contain special character '_' where you allow it is up to you, but state your decisions in your documentation. Examples x, ab_2y, c2 etc.
  2. Numbers, which include integers, fixed point and floating point numbers. Leading zeros and redundant trailing zeros are disallowed; e.g., 002 is invalid, 2.00 is invalid but 2.0 is valid. Real numbers can be represented in the E (exponential) format as well (e.g. 2.0E-2 is valid and represents 0.002). Decisions whether 2.0E+2 is valid are up to you.  
  3. white space (sequences of blank, tab, newline)
  4. Arithmetic operators: +, -, /, *, div, mod
  5. Logical constants: true, false
  6. Logical operators: not, and, or
  7. Comparison operators: <=, >=, <, > , =
  8. Parentheses: (, )
  9. Any add-ons are welcome.

Generate tokens from the regular expression using ML-Lex

Note

  1. Use noweb as a literate programming tool. Make the documentation such that your code is easily understandable. State all your decisions clearly.
  2. Write a Makefile to separate out the documentation and code.

Assignment 2

The task in this assignment is to build a recursive descent parser, based on the LL(1) parsing table developed in class, for the following grammar. Your recursive descent parser should interface with the lexical tokenizer developed in assignment 1 (corrections and improvements to what you did then are allowed). In fact, you should also try to see if your parser program interfaces correctly with someone else's tokenizer. (Hint: develop the parser as a functor).

You may have to massage this grammar into a suitable form before it is LL(1). I require you to present the modified grammar and the first and follow sets, as well as the parsing table (hone your noweb and LaTeX skills).

Please be careful with your error-handling routines

The output from the parser (at this stage) can be parse trees. These are isomorphic to a term of a suitable data type. So you can output these terms and write suitable print routines to display them as strings.

The following grammar is deliberately ambiguous. You need to disambiguate it in the standard way, and give precedences according to the following conventions:

  1. parentheses bind tightest.
  2. In expressions all binary operations are left associative.
  3. *, /, div, mod bind tighter than
  4. +, -.
  5. arithmetic operators bind tighter than comparison operators
  6. <=, >=, <, > , =.
  7. The comparison operators are non-associative and of equal precedence.
  8. The comparison operators bind tigher than logical operators
  9. not, wich binds tighter than and, which binds tighter than or.

The grammar is as follows:

Note: Corrected the grammar by deleting the production B -> (B) which causes problems
Also, start symbol is B

Assignment 4

Assume you are given any IR code trees belonging to the datatype defined in module TREE of Appel's book. Your task is to make the tree canonical (i.e., massage away any SEQ or ESEQ constructions, and ensure that any CALL is the child of a MEM, EXP ... and not of another CALL. Next ensure that you build basic blocks and ensure that conditional jump instructions are turned into a form where false branches are eliminated ("fall through if false"). Finally you have to choose any RISC architecture instruction set (easiest is the Jouette architecture in Appel's book), and implement the maximal munch tiling algorithm. Please generate assembly level commentary to describe the tile that has been replaced.