User Request:

Create a scanner, parser, and type checking for a given toy language.

Objectives:

1.	Use redirected standard Java I/O to read a file and produce output.	10 points
2.	Develop Scanner.	15 points
3.	Develop Parser functions in the program for each Non-terminal.	20 points
4.	Type checking and of AST Graphiz representation. Extra Extension: MIPS output	20 points 50 points
	Develop and use an appropriate design.	15 points
	Use proper documentation and formatting.	20 points

Description:

For the compiler project, you will complete a non-optimizing partial compiler for the TL language as described by the TL 18.0 Specification. The resulting compiler should translate TL source code, producing output at several intermediate stages, into MIPS assembly code executable in a simulator. MIPS part is extra and accepted as extensions. The extension part will bring you extra 50 points. Note that this documented is revised from the previous Programming Languages course document generated by Jeff Von Ronne and Xiaoyin Wang.

Make sure you pay attention to the requirements listed under specifications below. Submitted programs must comply with those specifications to receive full credit.

Scanner:

The first deliverable is a Scanner for the TL language. A BNF (Backus-Naur Form) grammar and a list of lexical items for the TL language is provided. The output of the scanner will be a list of tokens. In the output file, tokens should be listed in sequence, one token each line. All the tokens should be in the form as they are defined in the BNF grammar. For tokens with attributes or multiple values, please print the tokens in the form of: TOKEN(value). For example, the output token stream of

while SQRT * SQRT <= N do

is:

WHILE

ident(SQRT)

MULTIPLICATIVE(*)

ident(SQRT)

COMPARE(<=)

ident(N)

DO

Parser:

You are required to write a parser for it. Your parser should have one method or function corresponding to each non-terminal in TL's BNF grammar. For a lexically or syntactically invalid program, your scanner or parser should output an appropriate error message. For a syntactically valid input program, the your parser should output a Graphviz DOT file.

Type Checking and Type Annotated AST:

Once you have generated the AST. The compiler should traverse the AST to find the type of each sub-expression and determine whether there are any violations of the language's type rules. In order to type check the program, you will need to create a symbol table to associate each appearance of a variable with that variables declared type. The best way to do this, is probably to create an entry in a hash table indexed by name and containing information about each declared entity. (For TL, it is sufficient to just track the name and type of each declared variable.) And then when the AST generation code comes across a variable in a procedure body, it can look that name up in the symbol table and store a pointer/reference to that symbol table entry in the AST node. Please see example files.

Input/Output Specification:

The compiler program's main method should expect a TL input file, .tl, to be specified as command-line argument when it is invoked. If the input file is not a syntactically-valid program (i.e., if the program contains a lexical element that is not a legal token or does not match the BNF grammar), the compiler should output an error message to standard error stream containing the text "SCANNER ERROR", the text "PARSER ERROR", or the text "SYNTAX ERROR". If there is no syntax error, the compiler should output an abstract syntax tree in graphviz dot format to the AST output file,.ast.dot. If there is a type error, the compiler should output an error message to standard error that contains the text "TYPE ERROR". If there is no error, the program should print "VALID PROGRAM". If you are implementing the extra part, your program should print out a file with the extension of ".s", and the contents or ".s" file should be evaluated by SPIM.