package typecheck; import java.util.Hashtable; import rebelsky.compiler.lexer.Token; import rebelsky.compiler.misc.Symbol; import rebelsky.compiler.parser.Node; import rebelsky.compiler.pascal.PascalIdentifier; import rebelsky.compiler.pascal.PascalInteger; import rebelsky.compiler.pascal.PascalReal; import rebelsky.compiler.pascal.PascalNonterminals; import rebelsky.compiler.pascal.PascalTokens; /** * A simple example of a program that walks a parse tree and does * type checking. This particular example uses the assignment * language described in AssignLangParser.java. * * @author Samuel A. Rebelsky * @version 0.5 of October 2002. */ public class AssignLangTyper { // +----------------------+---------------------------------------------- // | Implementation Notes | // +----------------------+ /* I've used a "quick and dirty" technique that works well for this kind of grammar. Rather than associating a symbol table with each node in the tree, I have one global symbol table that I keep track of as I step through the tree. The symbol table is implemented as a hash table. The symbol table gives a type for each symbol. I've defined each type as an object constant. I'll use pointer comparison (==) when I need to compare types. I use objects rather than integers because (1) objects are easier to store in hash tables; (2) objects are easier to print. */ // +-----------+--------------------------------------------------------- // | Constants | // +-----------+ /** The type used for integers. */ private static Object TYPE_INTEGER = "integer"; /** The type used for real numbers. */ private static Object TYPE_REAL = "real"; /** The type used for single characters. */ private static Object TYPE_CHAR = "char"; /** The type used for boolean values. */ private static Object TYPE_BOOLEAN = "boolean"; /** The type used for undefined values. */ private static Object TYPE_UNDEFINED = "undefined"; // +-----------------+--------------------------------------------------- // | Private Methods | // +-----------------+ /** * Report an error. A more concise way to say * "throw new Exception(...)". */ public static void boom(String msg) throws Exception { throw new Exception(msg); } // boom(String) /** * Type check the parse tree for a series of declarations. * Update the symbol table while doing so. * * @exception Exception * If the tree does not type check. */ public static void checkDeclarations(Node declarations, Hashtable symbols) throws Exception { // Make sure that it's a collections of declarations if (declarations.getSymbol() != PascalNonterminals.VARIABLE_DECLARATIONS) boom("Didn't find declarations"); // Deal with each declaration in turn. int numDeclarations = declarations.numChildren(); for (int decNum = 0; decNum < numDeclarations; ++decNum) { Node dec = declarations.getChild(decNum); if (dec.getSymbol() != PascalNonterminals.VARIABLE_DECLARATION) boom("Didn't find declaration where I expected it in " + dec.getSymbol()); int numIds = dec.numChildren() - 1; Object type = getType((Token) dec.getChild(numIds).getSymbol()); for (int idNum = 0; idNum < numIds; idNum++) { Token identifier = (Token) dec.getChild(idNum).getSymbol(); if (getType(identifier, symbols) != TYPE_UNDEFINED) boom("Attempt to redifine " + identifier.toString()); symbols.put(identifier, type); } // for (idNum) } // for (decNum) } // checkDeclarations(Node) /** * Type check the parse tree for a series of assignment statements. * * @exception Exception * If the tree does not type check. */ public static void checkAssignments(Node assignments, Hashtable symbols) throws Exception { // Make sure that it's actually a list of assignments. if (assignments.getSymbol() != PascalNonterminals.ASSIGNMENT_LIST) boom("Didn't find assignment list!"); // Check each assignment in turn. int numAssignments = assignments.numChildren(); for (int assignment = 0; assignment < numAssignments; ++assignment) { Node variable = assignments.getChild(assignment).getChild(0); Node expression = assignments.getChild(assignment).getChild(1); Object vtype = getType(variable,symbols); Object etype = getType(expression,symbols); if (vtype != etype) throw new Exception("Types " + vtype + " and " + etype + " don't match in assignment to " + variable.getSymbol().toString()); } // for } // checkAssignments(Node) /** * Check and then get the type of the parse tree for an expression. */ public static Object getType(Node expression, Hashtable symbols) throws Exception { Symbol sym = expression.getSymbol(); // Case 1: Operator applied to two symbols if (expression.numChildren() == 3) { // Look: Fun work for you to do. return TYPE_UNDEFINED; } // Case 1: Operator // Case 2: Identifier else if (sym instanceof PascalIdentifier) { Object type = getType((Token) sym,symbols); if (type == TYPE_UNDEFINED) boom("Identifier " + sym + " is undefined."); return type; } // Case 2: Identifier // Case 3: Integer else if (sym instanceof PascalInteger) { return TYPE_INTEGER; } // Case 3: Integer // Case 4: Real else if (sym instanceof PascalReal) { return TYPE_REAL; } // Case 4: Real // Case 5: Unknown else { return TYPE_UNDEFINED; } } // getType(Node,Hashtable) /** * Convert an identifier token that describes a type to the * corresponding type. */ public static Object getType(Token t) throws Exception { if (t == PascalTokens.TBOOLEAN) return TYPE_BOOLEAN; if (t == PascalTokens.TCHAR) return TYPE_CHAR; if (t == PascalTokens.TINTEGER) return TYPE_INTEGER; if (t == PascalTokens.TREAL) return TYPE_REAL; throw new Exception("Invalid type: " + t.toString()); } // getType(token) /** * Get the type of an identifier. */ public static Object getType(Token tok, Hashtable symbols) { Object type = symbols.get(tok); if (type == null) return TYPE_UNDEFINED; else return type; } // getType(Token, Hashtable) // +----------------+---------------------------------------------------- // | Public Methods | // +----------------+ /** * Type check the parse tree for a program. What fun. * * @exception Exception * If the tree does not type check. */ public static void check(Node program) throws Exception { // Make sure that it's a program. if (program.getSymbol() != PascalNonterminals.PROGRAM) boom("Not a program!"); // Initialize the symbol table Hashtable symbols = new Hashtable(); symbols.put(PascalTokens.TTRUE, TYPE_BOOLEAN); symbols.put(PascalTokens.TFALSE, TYPE_BOOLEAN); // Check the variable declarations and update the symbol table. checkDeclarations(program.getChild(0), symbols); // Check the assignments using the updated symbol table. checkAssignments(program.getChild(1), symbols); } // check(Node) } // class AssignLangTyper