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

One way to do this is for theparser to produce a parse tree - a data structure that later phases of the compiler can traverse.Technically, a parse tree has exactly one leaf for each token of the input and one internal nodefor each grammar rule reduced during the parse.Such a parse tree, which we will call a concrete parse tree, representing the concrete syntaxof the source language, may be inconvenient to use directly. Many of the punctuation tokensare redundant and convey no information - they are useful in the input string, but once theparse tree is built, the structure of the tree conveys the structuring information moreconveniently.Furthermore, the structure of the parse tree may depend too much on the grammar! Thegrammar transformations shown in Chapter 3 - factoring, elimination of left recursion,83elimination of ambiguity - involve the introduction of extra nonterminal symbols and extragrammar productions for technical purposes.

These details should be confined to the parsingphase and should not clutter the semantic analysis.An abstract syntax makes a clean interface between the parser and the later phases of acompiler (or, in fact, for the later phases of other kinds of program-analysis tools such asdependency analyzers). The abstract syntax tree conveys the phrase structure of the sourceprogram, with all parsing issues resolved but without any semantic interpretation.Many early compilers did not use an abstract syntax data structure because early computersdid not have enough memory to represent an entire compilation unit's syntax tree. Moderncomputers rarely have this problem. And many modern programming languages (ML,Modula-3, Java) allow forward reference to identifiers defined later in the same module; usingan abstract syntax tree makes compilation easier for these languages.

It may be that Pascaland C require clumsy forward declarations because their designers wanted to avoid an extracompiler pass on the machines of the 1970s.Grammar 4.3 shows an abstract syntax of the expression language is Grammar 3.15. Thisgrammar is completely impractical for parsing: The grammar is quite ambiguous, sinceprecedence of the operators is not specified.GRAMMAR 4.3: Abstract syntax of expressions.•E→E+E•E→E−E•E→E*E•E→E/E•E → id•E → numHowever, Grammar 4.3 is not meant for parsing. The parser uses the concrete syntax to builda parse tree for the abstract syntax.

The semantic analysis phase takes this abstract syntaxtree; it is not bothered by the ambiguity of the grammar, since it already has the parse tree!The compiler will need to represent and manipulate abstract syntax trees as data structures. InJava, these data structures are organized according to the principles outlined in Section 1.3: anabstract class for each nonterminal, a subclass for each production, and so on. In fact, theclasses of Program 4.5 are abstract syntax classes for Grammar 4.3.

An alternate arrangement,with all the different binary operators grouped into an OpExp class, is also possible.Let us write an interpreter for the expression language in Grammar 3.15 by first buildingsyntax trees and then interpreting those trees. Program 4.4 is a JavaCC grammar withsemantic actions that produce syntax trees. Each class of syntax-tree nodes contains an evalfunction; when called, such a function will return the value of the represented expression.PROGRAM 4.4: Building syntax trees for expressions.84Exp{{}Exp{{Start() :Exp e; }e=Exp() { return e; }Exp() :Exp e1,e2; }e1=Term()( "+" e2=Term() { e1=new PlusExp(e1,e2); }| "-" e2=Term() { e1=new MinusExp(e1,e2); })*{ return e1; }}Exp Term() :{ Exp e1,e2; }{ e1=Factor()( "*" e2=Factor() {| "/" e2=Factor() {)*{ return e1; }}Exp Factor() :{ Token t; Exp e; }{ ( t=<IDENTIFIER>t=<INTEGER_LITERAL>"(" e=Exp() ")"}e1=new TimesExp(e1,e2); }e1=new DivideExp(e1,e2); }{ return new Identifier(t.image); } |{ return new IntegerLiteral(t.image); } |{ return e; } )POSITIONSIn a one-pass compiler, lexical analysis, parsing, and semantic analysis (typechecking) are alldone simultaneously.

If there is a type error that must be reported to the user, the currentposition of the lexical analyzer is a reasonable approximation of the source position of theerror. In such a compiler, the lexical analyzer keeps a "current position" global variable, andthe errormessage routine just prints the value of that variable with each message.A compiler that uses abstract-syntax-tree data structures need not do all the parsing andsemantic analysis in one pass.

This makes life easier in many ways, but slightly complicatesthe production of semantic error messages. The lexer reaches the end of file before semanticanalysis even begins; so if a semantic error is detected in traversing the abstract syntax tree,the current position of the lexer (at end of file) will not be useful in generating a line numberfor the error message. Thus, the source-file position of each node of the abstract syntax treemust be remembered, in case that node turns out to contain a semantic error.To remember positions accurately, the abstract-syntax data structures must be sprinkled withpos fields.

These indicate the position, within the original source file, of the characters fromwhich these abstract-syntax structures were derived. Then the type-checker can produceuseful error messages. (The syntax constructors we will show in Figure 4.9 do not have posfields; any compiler that uses these exactly as given will have a hard time producingaccurately located error messages.)package syntaxtree;Program(MainClass m, ClassDeclList cl)MainClass(Identifier i1, Identifier i2, Statement s)85abstract class ClassDeclClassDeclSimple(Identifier i, VarDeclList vl, MethodDeclList ml)ClassDeclExtends(Identifier i, Identifier j,VarDeclList vl, MethodDeclList ml) seeCh.14VarDecl(Type t, Identifier i)MethodDecl(Type t, Identifier i, FormalList fl, VarDeclList vl,StatementList sl, Exp e)Formal(Type t, Identifier i)abstract class TypeIntArrayType() BooleanType() IntegerType() IdentifierType(String s)abstract class StatementBlock(StatementList sl)If(Exp e, Statement s1, Statement s2)While(Exp e, Statement s)Print(Exp e)Assign(Identifier i, Exp e)ArrayAssign(Identifier i, Exp e1, Exp e2)abstract class ExpAnd(Exp e1, Exp e2)LessThan(Exp e1, Exp e2)Plus(Exp e1, Exp e2) Minus(Exp e1, Exp e2) Times(Exp e1, Exp e2)ArrayLookup(Exp e1, Exp e2)ArrayLength(Exp e)Call(Exp e, Identifier i, ExpList el)IntegerLiteral(int i)True()False()IdentifierExp(String s)This()NewArray(Exp e)NewObject(Identifier i)Not(Exp e)Identifier(String s)list classes ClassDeclList() ExpList() FormalList() MethodDeclList()StatementList() VarDeclList()Figure 4.9: Abstract syntax for the MiniJava language.The lexer must pass the source-file positions of the beginning and end of each token to theparser.

We can augment the types Exp, etc. with a position field; then each constructor musttake a pos argument to initialize this field. The positions of leaf nodes of the syntax tree canbe obtained from the tokens returned by the lexical analyzer; internal-node positions can bederived from the positions of their subtrees. This is tedious but straightforward.4.3 VISITORSEach abstract syntax class of Program 4.5 has a constructor for building syntax trees, and aneval method for returning the value of the represented expression. This is an object-orientedstyle of programming. Let us consider an alternative.PROGRAM 4.5: Exp class for Program 4.4.86public abstract class Exp {public abstract int eval();}public class PlusExp extends Exp {private Exp e1,e2;public PlusExp(Exp a1, Exp a2) { e1=a1; e2=a2; }public int eval() {return e1.eval()+e2.eval();}}public class MinusExp extends Exp {private Exp e1,e2;public MinusExp(Exp a1, Exp a2) { e1=a1; e2=a2; }public int eval() {return e1.eval()-e2.eval();}}public class TimesExp extends Exp {private Exp e1,e2;public TimesExp(Exp a1, Exp a2) { e1=a1; e2=a2; }public int eval() {return e1.eval()*e2.eval();}}public class DivideExp extends Exp {private Exp e1,e2;public DivideExp(Exp a1, Exp a2) { e1=a1; e2=a2; }public int eval() {return e1.eval()/e2.eval();}}public class Identifier extends Exp {private String f0;public Identifier(String n0) { f0 = n0; }public int eval() {return lookup(f0);}}public class IntegerLiteral extends Exp {private String f0;public IntegerLiteral(String n0) { f0 = n0; }public int eval() {return Integer.parseInt(f0);}}Suppose the code for evaluating expressions is written separately from the abstract syntaxclasses.

We might do that by examining the syntax-tree data structure by using instanceofand by fetching public class variables that represent subtrees. This is a syntax separate frominterpretations style of programming.The choice of style affects the modularity of the compiler. In a situation such as this, we haveseveral kinds of objects: compound statements, assignment statements, print statements, andso on. And we also may have several different interpretations of these objects: type-check,translate to Pentium code, translate to Sparc code, optimize, interpret, and so on.Each interpretation must be applied to each kind; if we add a new kind, we must implementeach interpretation for it; and if we add a new interpretation, we must implement it for eachkind.

Figure 4.6 illustrates the orthogonality of kinds and interpretations - for compilers, and87for graphic user interfaces, where the kinds are different widgets and gadgets, and theinterpretations are move, hide, and redisplay commands.Figure 4.6: Orthogonal directions of modularity.If the syntax separate from interpretations style is used, then it is easy and modular to add anew interpretation: One new function is written, with clauses for the different kinds allgrouped logically together. On the other hand, it will not be modular to add a new kind, sincea new clause must be added to every interpretation function.With the object-oriented style, each interpretation is just a method in all the classes. It is easyand modular to add a new kind: All the interpretations of that kind are grouped together asmethods of the new class.