A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition), страница 21

Consider, for example, the search tree in Figure 5.4, which represents the mappingFigure 5.4: Binary search trees.We can add the binding mouse ↦ 4, creating the mapping m2 without destroying the mappingm1, as shown in Figure 5.4b. If we add a new node at depth d of the tree, we must create dnew nodes - but we don't need to copy the whole tree. So creating a new tree (that sharessome structure with the old one) can be done as efficiently as looking up an element: in log(n)time for a balanced tree of n nodes. This is an example of a persistent data structure; apersistent red-black tree can be kept balanced to guarantee log(n) access time (see Exercise1.1c, and also page 276).SYMBOLSThe hash table of Program 5.2 must examine every character of the string s for the hashoperation, and then again each time it compares s against a string in the ith bucket.

To avoidunnecessary string comparisons, we can convert each string to a symbol, so that all thedifferent occurrences of any given string convert to the same symbol object.The Symbol module implements symbols and has these important properties:•••Comparing symbols for equality is fast (just pointer or integer comparison).Extracting an integer hash key is fast (in case we want to make a hash table mappingsymbols to something else).Comparing two symbols for "greater-than" (in some arbitrary ordering) is fast (in casewe want to make binary search trees).Even if we intend to make functional-style environments mapping symbols to bindings, wecan use a destructive-update hash table to map strings to symbols: We need this to make sure98the second occurrence of "abc" maps to the same symbol as the first occurrence.

Program 5.5shows the interface of the Symbol module.PROGRAM 5.5: The interface of package Symbol.package Symbol;public class Symbol {public String toString();public static Symbol symbol(String s);}public class Table {public Table();public void put(Symbol key, Object value);public Object get(Symbol key);public void beginScope();public void endScope();public java.util.Enumeration keys();}Environments are implemented in the Symbol.Table class as Tables mapping Symbols tobindings. We want different notions of binding for different purposes in the compiler - typebindings for types, value bindings for variables and functions - so we let the bindings beObject, though in any given table every binding should be a type binding, or every bindingshould be a value binding, and so on.To implement the Symbol class (Program 5.6), we rely on the intern() method of thejava.lang.String class to give us a unique object for any given character sequence; we canmap from Symbol to String by having each symbol contain a string variable, but the reversemapping must be done using a hash table (we use java.util.Hashtable).PROGRAM 5.6: Symbol table implementation.package Symbol;public class Symbol {private String name;private Symbol(String n) {name=n; }private static java.util.Dictionary dict = new java.util.Hashtable();public String toString() {return name;}public static Symbol symbol(String n) {String u = n.intern();Symbol s = (Symbol)dict.get(u);if (s==null) {s = new Symbol(u); dict.put(u,s); }return s;}}To handle the "undo" requirements of destructive update, the interface function beginScoperemembers the current state of the table, and endScope restores the table to where it was atthe most recent beginScope that has not already been ended.99An imperative table is implemented using a hash table.

When the binding x ↦ b is entered(table.put(x,b)), x is hashed into an index i, and a Binder object x ↦ b is placed at thehead of the linked list for the ith bucket. If the table had already contained a binding x ↦ b′,that would still be in the bucket, hidden by x ↦ b. This is important because it will support theimplementation of undo (beginScope and endScope).The key x is not a character string, but is the Symbol object itself.There must also be an auxiliary stack, showing in what order the symbols were "pushed" intothe symbol table. When x ↦ b is entered, then x is pushed onto this stack. A beginScopeoperation pushes a special marker onto the stack. Then, to implement endScope, symbols arepopped off the stack down to and including the topmost marker. As each symbol is popped,the head binding in its bucket is removed.The auxiliary stack can be integrated into the Binder by having a global variable top showingthe most recent Symbol bound in the table.

Then "pushing" is accomplished by copying topinto the prevtop field of the Binder. Thus, the "stack" is threaded through the binders.If we wanted to use functional-style symbol tables, the Table interface might look like this:public class Table {public Table();public Table put(Symbol key, Object value);public Object get(Symbol key);public java.util.Enumeration keys();}The put function would return a new table without modifying the old one. We wouldn't needbeginScope and endScope, because we could keep an old version of the table even as we usethe new version.5.2 TYPE-CHECKING MiniJavaWith what should a symbol table be filled - that is, what is a binding? To enable typechecking of MiniJava programs, the symbol table should contain all declared typeinformation:•••each variable name and formal-parameter name should be bound to its type;each method name should be bound to its parameters, result type, and local variables;andeach class name should be bound to its variable and method declarations.For example, consider Figure 5.7, which shows a program and its symbol table.

The two classnames B and C are each mapped to two tables for fields and methods. In turn, each method ismapped to both its result type and tables with its formal parameters and local variables.100Figure 5.7: A MiniJava Program and its symbol tableThe primitive types in MiniJava are int and boolean; all other types are either integer array,written int [], or class names. For simplicity, we choose to represent each type as a string,rather than as a symbol; this allows us to test type equality by doing string comparison.Type-checking of a MiniJava program proceeds in two phases. First, we build the symboltable, and then we type-check the statements and expressions.

During the second phase, thesymbol table is consulted for each identifier that is found. It is convenient to use two phasesbecause, in Java and MiniJava, the classes are mutually recursive. If we tried to do typechecking in a single phase, then we might need to type-check a call to a method that is not yetentered into the symbol table. To avoid such situations, we use an approach with two phases.The first phase of the type-checker can be implemented by a visitor that visits nodes in aMiniJava syntaxtree and builds a symbol table.

For instance, the visit method in Program 5.8handles variable declarations. It will add the variable name and type to a data structure for thecurrent class which later will be added to the symbol table. Notice that the visit methodchecks whether a variable is declared more than once and, if so, then it prints an appropriateerror message.PROGRAM 5.8: A visit method for variable declarationsclass ErrorMsg {boolean anyErrors;void complain(String msg) {anyErrors = true;System.out.println(msg);}}// Type t;// Identifier i;public void visit(VarDecl n) {Type t = n.t.accept(this);String id = n.i.toString();if (currMethod == null) {if (!currClass.addVar(id,t))error.complain(id + "is already defined in " + currClass.getId());101} else if (!currMethod.addVar(id,t))error.complain(id + "is already defined in "+ currClass.getId() + "." + currMethod.getId());}The second phase of the type-checker can be implemented by a visitor that type-checks allstatements and expressions.

The result type of each visit method is String, for representingMiniJava types. The idea is that when the visitor visits an expression, then it returns the typeof that expression. If the expression does not type-check, then the type-check is terminatedwith an error message.Let's take a simple case: an addition expression e1 + e2. In MiniJava, both operands must beintegers (the type-checker must check this) and the result will be an integer (the type-checkerwill return this type).

The visit method for addition is easy to implement; see Program 5.9.PROGRAM 5.9: A visit method for plus expressions// Exp e1,e2;public Type visit(Plus n) {if (! (n.e1.accept(this) instanceof IntegerType) )error.complain("Left side of LessThan must be of type integer");if (! (n.e2.accept(this) instanceof IntegerType) )error.complain("Right side of LessThan must be of type integer");return new IntegerType();}In most languages, addition is overloaded: The + operator stands for either integer addition orreal addition.

If the operands are both integers, the result is integer; if the operands are bothreal, the result is real. And in many languages if one operand is an integer and the other isreal, the integer is implicitly converted into a real, and the result is real. Of course, thecompiler will have to make this conversion explicit in the machine code it generates.For an assignment statement, it must be checked that the left-hand side and the right-hand sidehave the same type. When we allow extension of classes, the requirement is less strict: It issufficient to check that the right-hand side is a subtype of the left-hand side.For method calls, it is necessary to look up the method identifier in the symbol table to get theparameter list and the result type.