Pascal Subset

start	::=	program ID ; block .
block	::=	variables cmpdstmt
variables	::=	var vardcls | empty string
vardcls	::=	vardcls vardcl ; | vardcl ;
vardcl	::=	IDlist : type
IDlist	::=	IDlist , ID | ID
type	::=	array [ integer_constant .. integer_constant ] of stype
	|	stype
stype	::=	integer | boolean
stmtlist	::=	stmtlist ; stmt | stmt
stmt	::=	ifstmt | astmt | wstmt | cmpdstmt | writestmt | breakstmt
wstmt	::=	while condexp do stmt
ifstmt	::=	ifhead then stmt else stmt | ifhead then stmt
ifhead	::=	if condexp
cmpdstmt	::=	begin stmtlist end
writestmt	::=	writeln ( exp )
breakstmt	::=	break
astmt	::=	lvalue := exp
exp	::=	rvalue | exp + exp | exp - exp | exp * exp
	|	exp and exp | exp or exp | exp exor exp | not exp
	|	( exp ) | constant
condexp	::=	exp != exp | exp == exp | exp < exp | exp <= exp | ID | boolean_constant
lvalue	::=	ID | ID [ exp ]
rvalue	::=	ID | ID [ exp ]
constant	::=	integer_constant | boolean_constant
boolean_constant	::=	true | false

Front-End: Project Description

As part of this project, you will

• Augment the scanner to recognize the key words (tokens) while , do , break , and boolean ,
  
  
• Write the parser and detect and report at least the following syntax errors by inserting appropriate error productions :
  • "\n***Error: illegal variable declaration\n"
  • "\n***Error: illegal statement\n"
  • "\n***Error: illegal expression\n"
  • "\n***Error: illegal conditional expression\n"
  
  A reference parser for this project (without semantic analysis) will be make available as an executable on the undergraduate network. We hope to post this reference parser during the second week of the project. Note: Reporting the same error occurrence multiple times is okay. The grammar given above is ambiguous. However, we used features of bison to deal with operator precedence and associativity to resolve the ambiguity.
  
  
• Augment your parser to perform semantic analysis, in particular type checking. This will include the implementation a single-level symbol table. Your type checker has to detect and report at least the following semantic errors:
  
  
  • Declarations
    "\n***Error: duplicate declaration of %s\n"
  • Array declaration
    \n***Error: lower bound exceeds upper bound\n"
  • If stmt
    "\n***Error: exp in if stmt must be boolean\n"
  • While stmt:
    "\n***Error: exp in while stmt must be boolean\n"
  • Writeln stmt (Note: accepts only integer values
    "\n***Error: illegal type for write\n"
  • Assignment stmt
    "\n***Error: assignment types do not match\n"
    "\n***Error: assignment to whole array\n"
  • Array subscript operation id[exp] in exp
    "\n***Error: subscript exp not type integer\n"
    "\n***Error: id %s is not an array\n"
  • break statement
    "\n***Error: break statement outside of a while loop \n"
  • Identifier
    "\n***Error: undeclared identifier %s\n"
  • Arithmetic, logical, and relational operators in exp
    "\n***Error: types of operands for operation %s do not match\n";
    

Specific Details

Names are case sensitive .

Efficiency is not the main concern of this project. You may a simple unordered list to implement your symbol table. If you design your symbol table interface well, it should be simple to replace the underlying table implementation with a hashing scheme later.

Logical operators (and, or, exor, not) require boolean arguments. The arithmetic and relational operators (e.g., +) require integer arguments. Integer and boolean arguments cannot be mixed. The equality/inequality operators (==, !=) apply to any type, as long as the two argument types match.

Provided Code

1. declaration of types and attribute operations: attr.h and attr.c
   There is nothing useful yet in these files.
2. declaration of symbol table and symbol table operations: symtab.h and symtab.c
   There is nothing useful yet in these files.
3. Scanner: scan.l (flex)
4. Parser: parse.y (bison)
5. Makefile
6. demo-simple , a program that can be successfully parsed with the partial parser that can be generated from the provided code.

1. Parser and syntax error testing (more codes will be posted later):
   demo-simple; this test case actually works with the dummy parser provided;
   
   • nothing yet
2. Semantic error / type error testing:
   
   • nothing yet

Due Date

If you have specific, overriding, personal reasons why these dates are unreasonable, you should discuss them directly with the instructor before the deadline.

Submission Procedure

Grading Criteria

Code Generator: Project Description

Code Shape Requirements

• Your code should use the register-register model that exposes the maximal opportunities for register allocation. In other words, each new value should reside in a separate virtual register, if possible. The function NextRegister will return a new (fresh) register number. There are two versions of this project, the required version , and the advanced version .
  
  
  • required version: Every read and write of a scalar variable leads to a memory reference. In other words, scalar variables are treated the same way as array variables, i.e., are assumed to be potentially aliased.
    
    
  • advanced version: A read and write of a scalar variable within a single basic block may lead to a reference to a corresponding virtual register. The same scalar variable may be assigned to different virtual registers across different basic blocks. The first reference to a scalar variable in a basic block will result in generating a LOAD or STORE instruction. After that, the scalar variable "lives" in its virtual register, and the virtual register needs to be written back to the memory location of its scalar variable at the end of the basic block if the variable has been modified. Assignments to scalar variables that live in registers are implemented as register-register transfers (use the i2i ILOC instruction ).
    
    There is no extra credit for this project, just the enjoyment of doing it :-)
    
    
• All variables are statically allocated, i.e., there is no need for activation records. The static area starts at memory location 1024. Addresses above are reserved for register spilling. This convention will allow you to run your project 1 register allocator on each basic block of your generated code. The register r0 should contain the starting address (namely 1024) of the static area.
  
  
• You may only use the following ILOC instructions. All these instructions are implemented in our ILOC simulator.
  
  • no operation: nop .
  • arithemtic: add, sub, mult .
  • logical: and, or, xor .
  • memory: load, loadI, loadAO, loadAI, store, storeAO, storeAI .
  • control flow: br, cbr, cmp_LT, cmp_LE, cmp_EQ, cmp_NE .
  • register transfer: i2i .
  • I/O: output .
  Pleas see files instrutil.h and instrutil.c for details about the required formats. Procedures emit, NextRegister, and NextLabel are also defined within these files.
  
  li> You may want to generate nop instructions as targets of branches and conditional branches, e.g., L1: nop .
  
  
• Boolean values are represented as 4 bytes entities with 0 == FALSE and 1 == TRUE. Therefore, regular load and store instruction can be used.
  
  
• The evaluation of an exp will always result in an integer value, while the evaluation of an condexp will always result in a boolean (0 or 1) value. An ILOC cmp_ instruction writes a boolean value into its target register.
  
  
• The function NextLabel will generate a new (fresh) label each time it is called.

Provided Code

1. Parser/Code Generator: parse.y Here is where most of your code will go, as in the first part of the project. Use calls to procedure emit to generate code. This will write the resulting ILOC code into file iloc.out. Please modify your own version of parse.y from part1 of this project accordingly .
2. instrutil.h and instrutil.c . *** DO NOT MODIFY ***
3. You may modify your own Makefile of the first part of the project to include the files instrutil.h and instrutil.c , or use Makefile

Due Date

If you have specific, overriding, personal reasons why these dates are unreasonable, you should discuss them directly with the instructor before the deadline.

Submission Procedure

Grading Criteria