Announcement

• The user manuals for flex, yacc and bison can be found here.
• Project 2 Available (April/1/2016).

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 | fstmt | cmpdstmt | writestmt
wstmt	::=	while condexp do stmt
fstmt	::=	for ID := constant , constant do stmt
ifstmt	::=	ifhead then stmt else stmt | ifhead then stmt
ifhead	::=	if condexp
cmpdstmt	::=	begin stmtlist end
writestmt	::=	writeln ( exp )
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
integer_constant	::=	ICONST
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 , for , 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"
  
  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 (read the bison manual here).
  
  
• 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"
  • for statement
    "\n***Error: lower bound not integer constant\n"
    "\n***Error: upper bound not integer constant\n"
    "\n***Error: lower bound exceeds upper bound\n"
    "\n***Error: induction variable not scalar integer variable\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 use 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.

Getting Started

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.
7. ReadMe files contains a few reminders

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