Compilers I (CS4430) final project specification

Overview

For the final project, I had to implement (from scratch) a compiler for the source language and target language below. The language features c-style procedures and scoping. I organized the compiling process into stages as follows:

Lexing (tokenizing)
Parsing (AST generation)
Symbol Table construction
Symantic Actions
Static Checking (for correct # args, re-declarations, a main() proc, etc.)
Code Generation (see target tuple language below)
Code Optimization (nothing too complex though)

The professor did allow the use of tools such as lex/flex and yacc/bison for the initial stages. I'm not sure how my implementation stacked up against the rest of the class, but I think it turned out very good. I made a couple refinements to it after submitting it to the professor, just for fun. It seems to always produce correct output, and it has not seg-faulted in forever.

The Source Language (Toy++) BNF/CFC


		<program> —> <decl_list> <procdecl_list>

		<decl_list> —> <decl> ; <decl_list>

		<decl_list> —> Lambda

		<decl> —> declare NAME

		<procdecl_list> —> <procdecl> <procdecl_list>

		<procdecl_list> —> Lambda

		<procdecl> —> proc NAME (<var_list>) { <decl_list> <stmt_list> }

		<var_list> —> <var> <var_list_tail>

		<var_list_tail> —> , <var_list>

		<var_list_tail> —> Lambda

		<var> —> NAME

		<stmt_list> —> <stmt> ; <stmt_list>

		<stmt_list> —> Lambda

		<stmt> —> <assign_stmt> | <read_stmt> | <write_stmt> | call NAME ( arg_list )

		<arg_list> —> <expr> <arg_list_tail>

		<arg_list_tail> —> , <arg_list>

		<arg_list_tail> —> Lambda

		<assign_stmt> —> <var> = <expr> 

		<read_stmt> —> read <var>

		<write_stmt> —> write <expr>

		<expr> —> <term> | <term> + <term> | <term> - <term>

		<term> —> NUMBER | <var> | ( <expr> )

The Target Language


		Tuple —> Asn | Add | Sub | Jmp | Label | Read | Write | Exit

		Asn —> (ASSIGN,RegArg,Arg)

		Add —> (ADDI,RegArg,Arg,Arg)

		Sub —> (SUBI,RegArg,Arg,Arg)

		Jmp —> (JUMP,Arg)

		Label —> (LABEL,Num) /* n.b., labels are Num's */

		Read —> (READI,RegArg)

		Write —> (WRITEI,Arg)

		Exit —> (EXIT)

		Arg —> RegArg | Num

		Register —> 'R' Num | SP | FP | BP

		RegArg —> Register | M[Register] | M[Register + Num]

		Num —> [1-9] Digit*