CMSC 430, Spring 2009

Theory of Language Translation

Project 2 - C-- : Type Checker & AST

Due 11:59pm Fri, April 3rd, 2009


In this project you will add syntax-directed translation to your C-- parser in order to build symbol tables, perform type checking, and construct an abstract syntax tree (AST) intermediate representation of the input program.

Getting Started

Project 3 will be implemented in Java in Eclipse. Download the following file:
  • Eclipse project archive file
You can import the project into Eclipse as an existing project in an archive file.


See project 2 description for description of project files and syntax/semantics of C--. Compared to project 2, there have been a few minor changes:

  • mycc.cup
    • Uncommented calls for building AST and classFile.
    • Renamed error message from "undefined variable " to "undeclared variable ".
    • Changed some calls to expNode constructor.
    • Constructors have been modified.
    • Switched to TreeMap-based implementation.
    • Print out "{" and "}" before and after symbols in each local table.
    • Newly added.
You should replace the skeleton mycc.lex file with your mycc.lex file from project 2. You should compare the skeleton mycc.cup file with your mycc.cup file from project 2 and integrate the changes. Otherwise use files from project 3, not project 2.


All your changes for project 3 should be to action routines in mycc.cup.

You may assume that all input C-- programs are syntactically correct.

Symbol Tables

Symbol tables are used to collect and store information on all identifiers (variables, functions) in the program. A variable can be local, global, or passed as a parameter. To support nested lexical scoping, you must link together multiple symbol tables in a hierarchical manner. Use the symTab and symTabEntry classes to construct symbol tables in the C-- compiler. Each nested scope must have its own symbol table. References to symbol tables for each function are stored in its symTabEntry.


  • Build a symbol table for each lexical scope
  • Link up symbol tables appropriately
    • Functions and global variables in top-level symbol table
    • Symbol table for function in its symTabEntry
    • Symbol tables for local scopes in program order (order seen in program text)
  • Have your symbol tables print out in the manner expected in the test*.out files

Abstract Syntax Tree

An abstract syntax tree (AST) is an intermediate representation of a program. It can be constructed during a bottom-up parse. Use the expNode, astNode, and astNodeList classes to construct ASTs in the C-- compiler.

You may assume ASTs will be examined only for C-- programs with no type errors.


  • Build the AST for the input program
  • Have your AST print out in the manner expected in the test*.out files

Type Checker

The type checker makes sure that all variables accessed are legally declared and have proper types. It also provides warning of undeclared and redeclared variables. Use information from symbol tables to perform type checking in the C-- compiler.

Most type errors are straightforward. One tricky case in C-- is handling type errors for the "==" and "!=" operators, which can take either two integer operands, or two boolean operands. If types of the two operands differ, assume the type of the first operand is the intended type (i.e., "if (a < b) == 2" would assume "2" should be a boolean, while "if (2 == (a < b)" would assume "a < b" should be an integer.

If the forward declaration for a function does not match the actual function definition, go with the function definition once it is compiled.


  • Report the following type errors using parser.msg():
    • "undeclared variable x" // x is used before it is declared
    • "redeclaration of x" // x is declared more than once in same scope
    • "requires integer" // for operators such as + * < ...
    • "requires boolean" // for operators such as &&, ||, IF, WHILE
    • "misuse of x" // misuse x[i], x(i), x
    • "illegal subscript" // non-integer array subscript
    • "parameter mismatch" // e.g., declared as void foo(int x), invoked as foo()
    • "return mismatch" // return type different from function declaration
    • "forward decl mismatch x" // mismatched return type or parameter

Main Classes


Generated by CUP, this is the class which performs the actual parse. All action code in your CUP grammar are executed as methods of class "parser". Important public fields include globalSymTab, currSymTab, and curType. These fields are used to store information to be transferred between different actions in CUP. The "parser" class also contains main(), the starting point of the user code.


Stores information for individual instructions. Basic unit of abstract syntax tree. Contains a number of fields whose contents vary depending on node type.
  • Fields:
    • int nodeType; // type of the node: Const.INSTRUCTION, Const.IDENTIFIER, Const.INTEGER, Const.STRING, Const.ARRAY, Const.CALL
    • int expType; // type of the variable: sym.INT, sym.VOID, sym.BOOL
    • int val; // value of integer constant
    • String str; // content of literal string
    • symTabEntry ident; // pointer to the symbol table entry
    • int opcode; // opcode of the instruction
    • expNode op1; // operand 1
    • expNode op2; // operand 2
  • Node types:
    • Const.INTEGER // expType = sym.INT; val = value
    • Const.STRING // expType = sym.VOID; str = literal string
    • Const.ARRAY // expType = sym.INT; op1 = array subscript
    • Const.IDENTIFIER // expType = sym.INT or sym.VOID; ident = symTabEntry for identifier
    • Const.CALL // expType = sym.INT or sym.VOID; op1 = name of function; op2 = function argument (may be null)
    • Const.INSTRUCTION // expType = sym.INT, sym.VOID, or sym.BOOL; opcode = code for instruction ; op1 = first operand ; op2 = 2nd operand


Node of the abstract syntax tree. Contains a number of fields whose contents vary depending on node type.
  • Fields:
    • int treeType; // type of the tree
    • expNode treeExp; // useful for if, while, instructions
    • astNode node1; // useful for if and while
    • astNode node2; // useful for else
    • astNodeList nlist; // useful for block stmt
  • Node types:
    • TREE_INSTR // treeType = Const.TREE_INSTR expNode = instruction
    • TREE_IF // treeType = Const.TREE_IF treeExp = condition node1 = if block statement node2 = else block statement
    • TREE_WHILE // treeType = Const.TREE_WHILE treeExp = condition node1 = loop body
    • TREE_BLK // treeType = Const.TREE_BLK nlist = list of block statements
    • TREE_PROC // treeType = Const.TREE_PROC treeExp = name of function node1 = block statement body


You can submit your project in two ways:
  • Submit your mycc.lex and mycc.cup files by first putting both files in a single .zip or .jar archive. The files should be at the top level of the archive, not in a subdirectory.

    You may create a jar archive containing mycc.cup & mycc.lex by going to the directory containing your project, then either execute goJar (or goJar.bat) or type the following command directly:

    jar cf p3.jar mycc.cup mycc.lex

    You can submit the resulting p3.jar archive to to the submit server by clicking on the submit link in the column "web submission".

    Select the p3.jar archive using the "Browse" button, then press the "Submit project!" button.

  • Submit directly by executing a Java program on a computer with Java and network access. Use the submit.jar file from the archive, To submit, go to the directory containing your project, then either execute goSubmit (or goSubmit.bat) or type the following command directly:

    java -jar submit.jar

    You will be asked to enter your class account and password, then all files in the directory (and its subdirectories) will be put in a jar file and submitted to the submit server. If your submission is successful you will see the message:

    Successful submission # received for project 3

Academic Integrity

Please carefully read the academic honesty section of the course syllabus. In particular, remember that you are not allowed to show or copy any code for your project, either from the web or other students. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, will be submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus---please review it at this time.