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:
  1. Lexing (tokenizing)
  2. Parsing (AST generation)
  3. Symbol Table construction
  4. Symantic Actions
  5. Static Checking (for correct # args, re-declarations, a main() proc, etc.)
  6. Code Generation (see target tuple language below)
  7. 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*