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

The programming exercises in this bookrefer to this directory as $MINIJAVA/ when referring to specific subdirectories and filescontained therein.1.3 DATA STRUCTURES FOR TREE LANGUAGESMany of the important data structures used in a compiler are intermediate representations ofthe program being compiled. Often these representations take the form of trees, with severalnode types, each of which has different attributes.

Such trees can occur at many of the phaseinterfaces shown in Figure 1.1.Tree representations can be described with grammars, just like programming languages. Tointroduce the concepts, we will show a simple programming language with statements andexpressions, but no loops or if-statements (this is called a language of straight-line programs).The syntax for this language is given in Grammar 1.3.GRAMMAR 1.3: A straight-line programming language.Stm → Stm; StmStm → id := ExpStm → print (ExpList)(CompoundStm)(AssignStm)(PrintStm)15Exp → idExp → numExp → Exp Binop ExpExp → (Stm, Exp)(IdExp)(NumExp)(OpExp)(EseqExp)ExpList → Exp, ExpList(PairExpList)ExpList → Exp(LastExpList)Binop →+(Plus)Binop →−(Minus)Binop →×(Times)Binop → /(Div)The informal semantics of the language is as follows.

Each Stm is a statement, each Exp is anexpression. s1; s2 executes statement s1, then statement s2. i :=e evaluates the expression e,then "stores" the result in variable i. print(e1, e2,…, en) displays the values of all theexpressions, evaluated left to right, separated by spaces, terminated by a newline.An identifier expression, suchas i, yields the current contents of the variable i. A numberevaluates to the named integer. An operator expression e1 op e2 evaluates e1, then e2, thenapplies the given binary operator. And an expression sequence (s, e) behaves like the Clanguage "comma" operator, evaluating the statement s for side effects before evaluating (andreturning the result of) the expression e.For example, executing this programa := 5+3; b := (print(a, a-1), 10*a); print(b)prints8 780How should this program be represented inside a compiler? One representation is sourcecode, the characters that the programmer writes.

But that is not so easy to manipulate. Moreconvenient is a tree data structure, with one node for each statement (Stm) and expression(Exp). Figure 1.4 shows a tree representation of the program; the nodes are labeled by theproduction labels of Grammar 1.3, and each node has as many children as the correspondinggrammar production has right-hand-side symbols.16Figure 1.4: Tree representation of a straight-line program.We can translate the grammar directly into data structure definitions, as shown in Program1.5.

Each grammar symbol corresponds to an abstract class in the data structures:Grammar classStmStmExpExpExpListExpListStringidintnumPROGRAM 1.5: Representation of straight-line programs.public abstract class Stm {}public class CompoundStm extends Stm {public Stm stm1, stm2;public CompoundStm(Stm s1, Stm s2) {stm1=s1; stm2=s2;}}public class AssignStm extends Stm {public String id; public Exp exp;public AssignStm(String i, Exp e) {id=i; exp=e;}}public class PrintStm extends Stm {public ExpList exps;public PrintStm(ExpList e) {exps=e;}}public abstract class Exp {}public class IdExp extends Exp {public String id;17public IdExp(String i) {id=i;}}public class NumExp extends Exp {public int num;public NumExp(int n) {num=n;}}public class OpExp extendspublic Exp left, right;final public static intpublic OpExp(Exp l, intExp {public int oper;Plus=1, Minus=2, Times=3, Div=4;o, Exp r) {left=l; oper=o; right=r;}}public class EseqExp extends Exp {public Stm stm; public Exp exp;public EseqExp(Stm s, Exp e) {stm=s; exp=e;}}public abstract class ExpList {}public class PairExpList extends ExpList {public Exp head; public ExpList tail;public PairExpList(Exp h, ExpList t) {head=h; tail=t;}}public class LastExpList extends ExpList {public Exp head;public LastExpList(Exp h) {head=h;}}For each grammar rule, there is one constructor that belongs to the class for its left-hand-sidesymbol.

We simply extend the abstract class with a "concrete" class for each grammar rule.The constructor (class) names are indicated on the right-hand side of Grammar 1.3.Each grammar rule has right-hand-side components that must be represented in the datastructures. The CompoundStm has two Stm's on the right-hand side; the AssignStm has anidentifier and an expression; and so on.These become fields of the subclasses in the Java data structure.

Thus, CompoundStm has twofields (also called instance variables) called stm1 and stm2; AssignStm has fields id and exp.For Binop we do something simpler. Although we could make a Binop class - with subclassesfor Plus, Minus, Times, Div - this is overkill because none of the subclasses would need anyfields. Instead we make an "enumeration" type (in Java, actually an integer) of constants(final int variables) local to the OpExp class.Programming style We will follow several conventions for representing tree data structuresin Java:1. Trees are described by a grammar.2. A tree is described by one or more abstract classes, each corresponding to a symbol inthe grammar.3. Each abstract class is extended by one or more subclasses, one for each grammar rule.4.

For each nontrivial symbol in the right-hand side of a rule, there will be one field inthe corresponding class. (A trivial symbol is a punctuation symbol such as thesemicolon in CompoundStm.)5. Every class will have a constructor function that initializes all the fields.6. Data structures are initialized when they are created (by the constructor functions), andare never modified after that (until they are eventually discarded).18Modularity principles for Java programs A compiler can be a big program; carefulattention to modules and interfaces prevents chaos. We will use these principles in writing acompiler in Java:1. Each phase or module of the compiler belongs in its own package.2. "Import on demand" declarations will not be used.

If a Java file begins with3.import A.F.*; import A.G.*; import B.*; import C.*;then the human reader will have to look outside this file to tell which package definesthe X that is used in the expression X.put().4. "Single-type import" declarations are a better solution. If the module begins5.import A.F.W; import A.G.X; import B.Y; import C.Z;then you can tell without looking outside this file that X comes from A.G.6. Java is naturally a multithreaded system.

We would like to support multiplesimultaneous compiler threads and compile two different programs simultaneously,one in each compiler thread. Therefore, static variables must be avoided unless theyare final (constant). We never want two compiler threads to be updating the same(static) instance of a variable.PROGRAM STRAIGHT-LINE PROGRAM INTERPRETERImplement a simple program analyzer and interpreter for the straight-line programminglanguage. This exercise serves as an introduction to environments (symbol tables mappingvariable names to information about the variables); to abstract syntax (data structuresrepresenting the phrase structure of programs); to recursion over tree data structures, usefulin many parts of a compiler; and to a functional style of programming without assignmentstatements.It also serves as a "warm-up" exercise in Java programming. Programmers experienced inother languages but new to Java should be able to do this exercise, but will needsupplementary material (such as textbooks) on Java.Programs to be interpreted are already parsed into abstract syntax, as described by the datatypes in Program 1.5.However, we do not wish to worry about parsing the language, so we write this program byapplying data constructors:Stm prog =new CompoundStm(new AssignStm("a",new OpExp(new NumExp(5),OpExp.Plus, new NumExp(3))),new CompoundStm(new AssignStm("b",new EseqExp(new PrintStm(new PairExpList(new IdExp("a"),new LastExpList(new OpExp(new IdExp("a"),OpExp.Minus,new NumExp(1))))),new OpExp(new NumExp(10), OpExp.Times,new IdExp("a")))),new PrintStm(new LastExpList(new IdExp("b")))));19Files with the data type declarations for the trees, and this sample program, are available inthe directory $MINIJAVA/chap1.Writing interpreters without side effects (that is, assignment statements that update variablesand data structures) is a good introduction to denotational semantics and attribute grammars,which are methods for describing what programming languages do.

It's often a usefultechnique in writing compilers, too; compilers are also in the business of saying whatprogramming languages do.Therefore, in implementing these programs, never assign a new value to any variable orobject field except when it is initialized. For local variables, use the initializing form ofdeclaration (for example, int i=j+3;)andfor each class, make a constructor function (like theCompoundStm constructor in Program 1.5).1. Write a Java function int maxargs(Stm s) that tells the maximum number ofarguments of any print statement within any subexpression of a given statement. Forexample, maxargs(prog) is 2.2.

Write a Java function void interp(Stm s) that "interprets" a program in thislanguage. To write in a "functional programming" style - in which you never use anassignment statement - initialize each local variable as you declare it.Your functions that examine each Exp will have to use instanceof to determine whichsubclass the expression belongs to and then cast to the proper subclass. Or you can addmethods to the Exp and Stm classes to avoid the use of instanceof.For part 1, remember that print statements can contain expressions that contain other printstatements.For part 2, make two mutually recursive functions interpStm and interpExp.

Represent a"table", mapping identifiers to the integer values assigned to them, as a list of id × int pairs.class Table {String id; int value; Table tail;Table(String i, int v, Table t) {id=i; value=v; tail=t;}}Then interpStm is declared asTable interpStm(Stm s, Table t)taking a table t1 as argument and producing the new table t2 that's just like t1 except that someidentifiers map to different integers as a result of the statement.For example, the table t1 that maps a to 3 and maps c to 4, which we write {a ↦ 3, c ↦ 4} inmathematical notation, could be represented as the linked list.Now, let the table t2 be just like t1, except that it maps c to 7 instead of 4.

Mathematically, wecould write,t2 = update (t1, c, 7),where the update function returns a new table {a ↦ 3, c ↦ 7}.20On the computer, we could implement t2 by putting a new cell at the head of the linked list:, as long as we assume that the first occurrence of c in the listtakes precedence over any later occurrence.Therefore, the update function is easy to implement; and the corresponding lookup functionint lookup(Table t, String key)just searches down the linked list. Of course, in an object-oriented style, int lookup(Stringkey) should be a method of the Table class.Interpreting expressions is more complicated than interpreting statements, becauseexpressions return integer values and have side effects.