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

1962]. The abstract syntax was intended to be used for writingprograms until designers could get around to creating a concrete syntax with human-readablepunctuation (instead of Lots of Irritating Silly Parentheses), but programmers soon got usedto programming directly in abstract syntax.92The search for a theory of programming-language semantics, and a notation for expressingsemantics in a compiler-compiler, led to ideas such as denotational semantics [Stoy 1977].The semantic interpreter shown in Programs 4.4 and 4.5 is inspired by ideas from denotationalsemantics, as is the idea of separating concrete syntax from semantics using the abstractsyntax as a clean interface.EXERCISES4.1 Write a package of Java classes to express the abstract syntax of regular expressions.4.2 Extend Grammar 3.15 such that a program is a sequence of either assignment statementsor print statements.

Each assignment statement assigns an expression to an implicitlydeclared variable; each print statement prints the value of an expression. Extend theinterpreter in Program 4.1 to handle the new language.4.3 Write a JavaCC version of the grammar from Exercise 4.2. Insert Java code forinterpreting programs, in the style of Program 4.2.4.4 Modify the JavaCC grammar from Exercise 4.3 to contain Java code for building syntaxtrees, in the style of Program 4.4. Write two interpreters for the language: one in objectoriented style and one that uses visitors.4.5 In $MINIJAVA/chap4/handcrafted/visitor, there is a file with a visitorPrettyPrintVisitor.java for pretty printing syntax trees.

Improve the pretty printingof nested if and while statements.4.6 The visitor pattern in Program 4.7 has accept methods that return int. Ifone wanted towrite some visitors that return integers, others that return class A, and yet others thatreturn class B, one could modify all the classes in Program 4.7 to add two more acceptmethods, but this would not be very modular. Another way is to make the visitor returnObject and cast each result, but this loses the benefit of compile-time type-checking. Butthere is a third way.Modify Program 4.7 so that all the accept methods return void, and write twoextensions of the Visitor class: one that computes an int for each Exp, and the otherthat computes a float for each Exp.

Since the accept method will return void, thevisitor object must have an instance variable into which each accept method can place itsresult. Explain why, if one then wanted to write a visitor that computed an object of classC for each Exp, no more modification of the Exp subclasses would be necessary.93Chapter 5: Semantic AnalysisOVERVIEWse-man-tic: of or relating to meaning in languageWebster's DictionaryThe semantic analysis phase of a compiler connects variable definitions to their uses, checksthat each expression has a correct type, and translates the abstract syntax into a simplerrepresentation suitable for generating machine code.5.1 SYMBOL TABLESThis phase is characterized by the maintenance of symbol tables (also called environments)mapping identifiers to their types and locations.

As the declarations of types, variables, andfunctions are processed, these identifiers are bound to "meanings" in the symbol tables. Whenuses (nondefining occurrences) of identifiers are found, they are looked up in the symboltables.Each local variable in a program has a scope in which it is visible. For example, in a MiniJavamethod m, all formal parameters and local variables declared in m are visible only until the endof m. As the semantic analysis reaches the end of each scope, the identifier bindings local tothat scope are discarded.An environment is a set of bindings denoted by the ↦ arrow.

For example, we could say thatthe environment σ0 contains the bindings {g ↦ string, a ↦ int}, meaning that the identifiera is an integer variable and g is a string variable.Consider a simple example in the Java language:1 class C {2int a; int b; int c;3public void m(){4System.out.println(a+c);5int j = a+b;6String a = "hello";7System.out.println(a);8System.out.println(j);9System.out.println(b);10}11 }Suppose we compile this class in the environment σ0.

The field declarations on line 2 give usthe table σ1 equal to σ0 + {a ↦ int, b ↦ int, c ↦ int}, that is, σ0 extended with newbindings for a, b, and c. The identifiers in line 4 can be looked up in σ1. At line 5, the table σ2= σ1 + {j ↦ int} is created; and at line 6, σ3 = σ2 + {a ↦ String} is created.How does the + operator for tables work when the two environments being "added" containdifferent bindings for the same symbol? When σ2 and {a ↦ String} map a to int and94String, respectively? To make the scoping rules work the way we expect them to in realprogramming languages, we want {a ↦ String} to take precedence.

So we say that X + Y fortables is not the same as Y + X; bindings in the right-hand table override those in the left.The identifiers in lines 7, 8, and 9 can be looked up in σ3. Finally, at line 10, we discard σ3and go back to σ1. And at line 11 we discard σ1 and go back to σ0.How should this be implemented? There are really two choices. In a functional style, we makesure to keep σ1 in pristine condition while we create σ2 and σ3. Then when we need σ1 again,it's rested and ready.In an imperative style, we modify σ1 until it becomes σ2.

This destructive update "destroys"σ1; while σ2 exists, we cannot look things up in σ1. But when we are done with σ2, we canundo the modification to get σ1 back again. Thus, there is a single global environment σwhich becomes σ0, σ1, σ2, σ3, σ1, σ0 at different times and an "undo stack" with enoughinformation to remove the destructive updates. When a symbol is added to the environment, itis also added to the undo stack; at the end of scope (e.g., at line 10), symbols popped from theundo stack have their latest binding removed from σ (and their previous binding restored).Either the functional or imperative style of environment management can be used regardlessof whether the language being compiled or the implementation language of the compiler is a"functional" or "imperative" or "objectoriented" language.MULTIPLE SYMBOL TABLESIn some languages there can be several active environments at once: Each module, or class, orrecord in the program has a symbol table σ of its own.In analyzing Figure 5.1, let σ0 be the base environment containing predefined functions, andletstructure M = structstructure E = structval a = 5;endstructure N = structval b = 10val a = E.a + bpackage M;class E {static int a = 5;}class N {static int b = 10;static int a = E.a + b;95}endclass D {structure D = structstatic int d = E.a +val d = E.a + N.aN.a;end}end(a) An example in ML(b) An example in JavaFigure 5.1: Several active environments at once.In ML, the N is compiled using environment σ0 + σ2 to look up identifiers; D is compiledusing σ0 + σ2 + σ4, and the result of the analysis is {M ↦ σ7}.In Java, forward reference is allowed (so inside N the expression D.d would be legal), so E, N,and D are all compiled in the environment σ7; for this program the result is still {M ↦ σ7}.EFFICIENT IMPERATIVE SYMBOL TABLESBecause a large program may contain thousands of distinct identifiers, symbol tables mustpermit efficient lookup.Imperative-style environments are usually implemented using hash tables, which are veryefficient.

The operation σ′ = σ + {a ↦ τ} is implemented by inserting τ in the hash tablewith key a. A simple hash table with external chaining works well and supports deletioneasily (we will need to delete {a ↦ τ} to recover σ at the end of the scope of a).Program 5.2 implements a simple hash table. The ith bucket is a linked list of all the elementswhose keys hash to i mod SIZE.PROGRAM 5.2: Hash table with external chaining.class Bucket {String key; Object binding; Bucket next;Bucket(String k, Object b, Bucket n) {key=k; binding=b; next=n;}}class HashT {final int SIZE = 256;Bucket table[] = new Bucket[SIZE];private int hash(String s) {int h=0;for(int i=0; i<s.length(); i++)h=h*65599+s.charAt(i);return h;}void insert(String s, Binding b) {int index=hash(s)%SIZEtable[index]=new Bucket(s,b,table[index]);}Object lookup(String s) {int index=hash(s)%SIZEfor (Binding b = table[index]; b!=null; b=b.next)if (s.equals(b.key)) return b.binding;return null;}96void pop(String s) {int index=hash(s)%SIZEtable[index]=table[index].next;}}Consider σ + {a ↦ τ2} when σ contains a ↦ τ1 already.

The insert function leaves a ↦ τ1in the bucket and puts a ↦ τ2 earlier in the list. Then, when pop(a) is done at the end of a'sscope, σ is restored. Of course, pop works only if bindings are inserted and popped in astacklike fashion.An industrial-strength implementation would improve on this in several ways; see Exercise5.1.EFFICIENT FUNCTIONAL SYMBOL TABLESIn the functional style, we wish to compute σ′ = σ + {a ↦ τ} in such a way that we still haveσ available to look up identifiers. Thus, instead of "altering" a table by adding a binding to itwe create a new table by computing the "sum" of an existing table and a new binding.Similarly, when we add 7 + 8 we don't alter the 7 by adding 8 to it; we create a new value, 15− and the 7 is still available for other computations.However, nondestructive update is not efficient for hash tables.

Figure 5.3a shows a hashtable implementing mapping m1. It is fast and efficient to add mouse to the fifth slot; justmake the mouse record point at the (old) head of the fifth linked list, and make the fifth slotpoint to the mouse record. But then we no longer have the mappingm1:Wehavedestroyedittomake m2. The other alternative is to copy the array, but still share allthe old buckets, as shown in Figure 5.3b. But this is not efficient: The array in a hash tableshould be quite large, proportional in size to the number of elements, and we cannot afford tocopy it for each new entry in the table.Figure 5.3: Hash tables.97By using binary search trees we can perform such "functional" additions to search treesefficiently.