Modern Compiler Implementation in Java: Basic Techniques

©1997 by Andrew W. Appel

Errors in 1997 edition

All of these errors are fixed in the 1998 edition. Please do not continue to report errors in the 1997 (preliminary) edition.

Page 13. Line 13, there should be no underscores in the declaration of interpStm.

Page 14. Class Tree is declared incorrectly: right is missing its Tree class declarator. The insert method is not inside any class; it may reasonably be put inside the Tree class. Finally, insert must use the compareTo method instead of key<t.key to compare strings.

Page 22. Second-to-last paragraph and last paragraph should refer to six automata in the figure, not four.
Figure 2.4, the edge from state 2 to state 4 should be labeled a-e,g-z,0-9; state 5 should be a final state recognizing error.

Page 27. Figure 2.6, the automaton for M* should be

Page 29. The last statement of the algorithm (j <- j+1) should not be indented so far; it should be at the same level as the foreach.

Page 31. Last line should refer to sym.IF and sym.ID, not Syms.IF and Syms.ID.

Page 32. In Program 2.9:

Page 32. The constructor for class Symbol should read, 

  Symbol(int s, int l, int r, Object v) {
    sym=s; left=l; right=r; value=v;
  }
but in the text the type of v was given incorrectly as int.

Page 34. The JavaLex directive to declare COMMENT as a start-state should be: 

%state COMMENT
and the command to re-enter the initial state should be: 
<COMMENT>"*)"       {yybegin(YYINITIAL);}

Page 35. Reference to Toy.lex should be Tiger.lex.

Page 50. The last if statement should be indented to the same position as the others.

Page 54. Grammar 3.14, both occurrences of F' should be T'.

Page 55. Table 3.16: Entries in rows E and T should not have $ symbol; entry for row F, column ( should be F->(E).

Page 55. First line of text should refer to "same nonterminal S", not "same nonterminal X".
First full paragraph should read, "In such a case, we can left factor the grammar -- that is, take the allowable endings and make a new nonterminal X to stand for them."

Page 58. On the 5th line of the figure, E should have the subscript 11. On the 7th line from the bottom of the figure, the second occurrence of id should have subscript 20, not 4.

Page 61. In the state 3 box, the first line should read S->(.L), not L->(.L)

Page 63. Figure 3.20 should have an arrow from state 3 to state 2, labeled by x.
Grammar 3.22,

Page 64. Figure 3.23, third item in state 1 should read E->.T and the edge from state 3 to state 4 should be labeled with + instead of comma.

Page 66. Figure 3.25,

State 1:
Fourth and fifth items should read T -> .x instead of E -> .x
State 4:
There should be fifth item, T -> .x with lookahead +, and the edge labelled x should go to state 5, not 7.
State 7:
There should be no state 7.
Table row 4:
should have s5 instead of s7.
Table row 7:
should be deleted.

Page 66. Paragraph beginning "Merging states 5 and 7" should be deleted. For Grammar 3.22 the LR(1) table, the LALR(1) table, and the SLR table are all the same.

Page 67. Figure 3.26 incorrectly shows LL(1) as a subset of SLR. In fact, LL(1) is not even a subset of LALR(1): there is an LL(1) grammar that is not LALR(1).

Page 68."As explained on page 54, factoring the grammar will eliminate the ambiguity." This is incorrect; factoring does not eliminate the ambiguity, but a different grammar transformation does.

Page 69. Grammar 3.27, production 4 should read S --> begin L end

Page 74. 5th line from the bottom should read S --> id := E, not S --> id := id.

Page 78. Exercise 3.5, production 4's left-hand side should be E, not B.

Page 81. There should be no = sign after int Tprime(int a). In the F() function, the ID and NUM cases should be, 

         case ID:   int i=lookup((String)(tok.val)); advance(); return i;
         case NUM:  int i=((Integer)(tok.val)).intValue(); 
                    advance(); return i;

Page 86. Program 4.5 should intern strings before putting them in the table, and before looking them up: 

   class Update extends Table {
       private Table base; String id; int val;
       Update(Table b, String i, int v) {base=b; id=i.intern(); val=v;}
       int lookup(String i) {
          if (i.intern()==id) return val;
          else return base.lookup(i);
       }
   }
Program 4.6 should use -,*,/ in the eval methods of Minus, Times, and Div instead of using + everywhere.

Page 87.

Page 88. The rule exps ::= exps COMMA exp should have the following semantic action: 

exp ::= exps COMMA exp:e               {: System.out.print(e); :}
The second-to-last action should read 
exp ::= stm:s COMMA exp:e              {:RETURN=e;:}

Page 98. In exercise 4.3, "cdots" should be ". . .".

Page 101. The 7th line from the bottom should read, "D is compiled using 0 + 2 + 4, and the result of the analysis is ..." (the subscripts are incorrect in the book).

Page 113. Code lines near top of page for calls to checkInt should read: 

checkInt(transExp(e.left), e.left.pos);
checkInt(transExp(e.right), e.right.pos);
instead of: 
checkInt(transExp(e.left, e.left.pos));
checkInt(transExp(e.right, e.left.pos));

Page 115-116. The functions Exp transDec(Absyn.TypeDec d) and Exp transDec(Absyn.FunctionDec d) should return null as a placeholder.

Page 119. Exercise 5.2, The line beginning s4 should be, s4=s1 union s3.

Page 115. The second line of the first code fragment should read, 

   env.venv.put(d.name, new VarEntry(transExp(d.init).ty));

Page 116. The 8th line of the first code fragment should read, 

               new VarEntry(

Page 131. In class Frame, the name and formals fields should not be prefixed by the abstract modifier.

Page 133. Sentence after function m... should start with "If x stays in parameter register 1 throughout m, ..."

Page 135. In class FormalEscape, the body of the setEscape() function should be {fl.escape=true;} and in class VarEscape the body of setEscape() should be {vd.escape=true;}

Page 140. The book recommends making a file called Sparc/Frame.java or Mips/Frame.java, etc. This confuses JDK 1.1 (though not JDK 1.0 or other Java compilers); a simple solution is to create Sparc/SparcFrame.java or Mips/MipsFrame.java etc.

Page 141. (Not a bug, but a clarification): Exercise 6.2. If the machine passes parameter 1 in r1 and parameter 2 in r2 (for example), then clearly x arrives in r1. But it cannot stay there during the call to h(y,y); so where does the compiler arrange to keep it?

Page 146. Figure 7.2, last two lines, each occurrence of RELOP should be CJUMP. (Thanks to Daehak Kim for reporting this.)

Page 147. Line 16 should read, "MOVE(MEM(e1),e2) Evaluate e1, yielding address a. Then evaluate e2, and store the result into wordSize bytes of memory starting at a."

Page 164. Third paragraph: transDec does not return a result record containing new environments, it just returns a Translate.Exp.

Page 179. The last sentence of the page should begin, "But 8.3c shows a better trace covering..."

Page 188. In the table, the second tile shown matching the MEM node does not correspond to any instruction of the Jouette machine, and should not be listed.

Page 194. In the "Two-address instructions" paragraph, the instructions should read, 

mov t1,t2       t1 <- t2
add t1,t3       t1 <- t1 + t3

Page 197. The third line of the second code fragment should read, 

             new TempList(frame.FP(),null));

Page 199-200. Calls to munchStm and munchExp are missing parentheses around the argument parameter, and all uses of the ^ operator should be + instead.

Page 211. In Table 10.5, 4th iteration, row 3, change c to b.

Page 230. In Figure 11.6, the graph-node d should have the color 1, not 4.

Page 230. (Not a bug, but a clarification): Precolored nodes should be considered to have infinite degree. Therefore, simplify, freeze, and spill cannot be performed on them. However, an ordinary (non-precolored) node may be coalesced with a precolored node. Click here for a detailed example.

Page 233.First line should read, Degree(T)<K. Since T will lose the neighbor X and gain the neighbor R, ...

Page 240. In procedure FreezeMoves, before the second if statement, insert the statement v:=GetAlias(v).

Page 265. Figure 13.7b, arrows should come from first and third elements of root set, not first and second elements.

Page 296. 14th line from the bottom, delete "a classless language".

Page 301. Third line from bottom should say, "Thus, addTen is a function g(x)=addFive(addFive(x))".

Page 320. In the program fragment on the right, the third line from the bottom should read, 

 in if y>8 then loop(y)
Second line from the bottom of the page should read:
program on the right will return 0, but the program on the left will first get

Page 324. Last line should refer to h(i), not i.

Page 339. On the 8th line from the bottom, delete first two words.

Page 340. In Table 16.4, the last two rows should read,
f(a1,...,an){} All expressions of the form M[x]
t := f(a1,...,an){} expressions containing t + all expressions of the form M[x]
Also, the paragraph beginning "Given gen and kill" says the word "successors" when it should say "predecessors".

Page 341. In the table, in the column headed gen[s], delete each of the three instances of "-kill[s]".

Page 345. Algorithm 16.5 should read, 

Topological-sort:
    N := number of nodes
    for all nodes i
        mark[i] := false
    DFS(start-node)

function DFS(i)
   if mark[i]=false
        mark[i] := true
        for each successor s of node i
              DFS(s)
        sorted[N] := i
        N := N-1

Page 346. Algorithm 16.6, the first line should read,
W := the set of all nodes

Page 355. The one-line table under "USING MAY-ALIAS INFORMATION" should read,
Statement s gen[s] kill[s]
M[a] := b {} {M[x] | a may-alias x at s}
The example beginning "Now we can analyze the following program fragment", though technically correct, does not properly illustrate the use of may-alias information. Here's a better example.

Page 362. The set equation for D[n] applies to all nodes except the start node s0; the equation for the start node is D[s0]={s0}.

Page 365. Lines 5-7, definition of Nested loops should be: If A and B are loops with headers a and b respectively, such that a not-equal b and b is in A, then the nodes of B are a proper subset of the nodes of A.

Page 367. In the paragraph headed by HOISTING, 5th line, replace "a<b" by "i>=N initially."

Acknowledgments

Thanks to Jeffrey Hsu, Max Hailperin, Torben Mogensen, Mikael Petterson, Luca Cristoforetti, Doug Morgan, and others for reporting these errors.