Modern Compiler Implementation in Java

©1998 by Andrew W. Appel

Errors in the first edition, first printing (1998):

The following errors also appear in the 1999 reprinting of the book.

Page 20. Figure 2.2, second-to-last line should not have double quotes around \n and \t:
("--"[a-z]*\n)|(" "|\n|\t)+ { /* do nothing */ }

Page 31. Program 2.9, second-to-last line should not have double quotes around \n and \t:
("--"[a-z]*\n)|(" "|\n|\t)+ {}

Page 55. After the sentence, "The resulting productions will not pose a problem for a predictive parser" add:
Although the grammar is still ambiguous -- the parsing table has two entries for the same slot -- we can resolve the ambiguity by using the "else S" action.

Page 57. First line: TIMES should not be in Tprime_follow.

Page 66. First line of left-hand box: change ampersand (&) to $.

Page 79. Lines 11-12 should read,
3. Discard input symbols (if necessary) until a lookahead is reached that has a non-error action in the current state.

Page 83. Line 15, tiger.grm should be Grm.cup.

Page 95. Program 4.6, the identifiers Num, Id, Plus, Minus, Times, Div, Eseq should be NumExp, IdExp, PlusExp, MinusExp, TimesExp, DivExp, EseqExp.
Program 4.6, lines 12,16,20,24, all instances of aa.eval should be a.eval and all instances of bb.eval should be b.eval.

Page 104. The Tiger program shown is actually illegal, since g is declared to return no value but its body returns the value f().

Page 118.
9th line from bottom, "enventry" should be "Entry".
3rd line from bottom, "UNIT" should be "VOID".

Page 119. Figure 5.8, lines 3 and 4 should read,
Symbol.Table venv; // value environment
Symbol.Table tenv; // type environment

Page 120. 7th and 8th lines after figure should read,
Translate.Exp transDec(Absyn.Exp e) { ... }
Types.Type transTy(Absyn.Ty e) { ... }
5th line from bottom and 4th line from bottom should refer to Types.Type, not just Type.

Page 121. line 4 should read,
public abstract class Exp {}

Page 128. Exercise 5.1 (b) should read, "Explain how the object-oriented implementation of HashT allows several different tables to be in use simultaneously."

Page 143. Table 6.4. The MIPS column of the table uses registers r2, r4, r5 for passing parameters. The use of r2 for the "zeroth parameter" is consistent with the MIPS convention of passing the static link in r2; the argument x1, by this point in the compilation, is really the static link.

Page 183. 7th line from bottom, change "whether two expressions commute" to "whether a statement commutes with an expression".

Page 226. Table 10.5 in the 4th iteration, the out set for statement 3 is c, when it should be b.

Page 245. Assignment statements on line 19 should say,
t:=M[bloc]; M[aloc]:=t.

Page 247. Figure 11.7, captions (a) and (b) are missing.

Page 249. Last sentence, swap "afterward" and "beforehand".

Page 252. Delete last bullet item entirely ("When u is coalesced ...").

Page 258. Line 8, change all three occurrences of "nodeMoves" to "moveList".
Insert new line, "EnableMoves(v)".

Page 281. Algorithm 13.5, after second line, insert:
mark x

Page 376. 8th line from bottom, delete the word "not".

Page 529. 4th line from bottom, change both occurrences of "integer" to "int".

The following errors have been corrected in the 1999 reprinting of the book.

Page 29,30. The state labeled 5,6,7,8,15 should be 5,6,8,15.
The state labeled 10,11,12,13,15 should be 10,11,13,15.

Page 44. Figure 3.3, the rightmost semicolon should be a comma. Also, the part of the derivation corresponding to "c +" is missing from the tree.

Page 50. Lines 11-20 should read,

for each production X -> Y1Y2...Yk
    if Y1...Yk are all nullable (or if k=0)
        then nullable[X] = true
    for each i from 1 to k, each j from i+1 to k
        if Y1...Yi-1 are all nullable (or if i = 1)
            then FIRST[X] = FIRST[X] u FIRST[Yi]
        if Yi+1...Yk are all nullable (or if i = k)
            then FOLLOW[Yi] = FOLLOW[Yi] u FOLLOW[X]
        if Yi+1...Yj-1 are all nullable (or if i+1 = j)
            then FOLLOW[Yi] = FOLLOW[Yi] u FIRST[Yj]

Page 51. Algorithm 3.13, lines 6-15 should read,

for each production X -> Y1Y2...Yk
    if Y1...Yk are all nullable (or if k=0)
        then nullable[X] <- true
    for each i from 1 to k, each j from i+1 to k
        if Y1...Yi-1 are all nullable (or if i = 1)
            then FIRST[X] <- FIRST[X] u FIRST[Yi]
        if Yi+1...Yk are all nullable (or if i = k)
            then FOLLOW[Yi] <- FOLLOW[Yi] u FOLLOW[X]
        if Yi+1...Yj-1 are all nullable (or if i+1 = j)
            then FOLLOW[Yi] <- FOLLOW[Yi] u FIRST[Yj]

Page 54. Table 3.16 caption should refer to Grammar 3.15, not Grammar 3.8.

Page 58. Figure 3.18, 7th line from the bottom, the second occurrence of id should have subscript 20, not 4.
Figure 3.18, 5th line from the bottom, "(S;E)" should be "(S,E)" at the end of the line.

Page 59. Table 3.19, row 9, is missing some entries. In column "id" the entry should be "s20", in column "num" the entry should be "s10", and in column "(" the entry should be "s8".

Page 66. In the left-hand box, the lookahead for the last two lines should be =, not $.

Page 67. Figure 3.27 shows the LR(1) states for Grammar 3.23, not for Grammar 3.26.
In Figure 3.27, states 4 and 7, the lookahead for T->x should be "$,+" and not just "$".

The LR(1) states for Grammar 3.26 are as follows:
LR(1) states for Grammar 3.26

Page 67. Table 3.28a, the last entry in row 13 should be g7, not f7.
Table 3.28b, the entry in row 7, column "=", should be r3 instead of blank.

Page 68. The second paragraph should begin,

For some grammars, the LALR(1) table contains reduce-reduce conflicts where the LR(1) table has none, but in practice the difference matters little.

Page 76. Grammar 3.35 and Grammar 3.36, the start with directive should come after the precedence directives.

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

exps ::= exps COMMA exp:e               {: System.out.print(e); :};

Page 105. After the line "statements, we must use a seqExp.", Add the following sentence: "An empty statement () is represented by SeqExp(null).

Page 109. Line 5 of the program fragment, delete the semicolon after print_int(j).

Page 117. The second program fragment should use := instead of = in the var declarations of a and b.

Page 120. First program fragment after the table, line 7, should be

   Exp transDec(Absyn.Dec e) { ... }

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

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

Page 125. The 7th line of the first code fragment should read,

     env.venv.put(, new VarEntry(

Page 139. Program 6.3, line 14 should be indented one space less; and should read,

            output := concat(output, s);  write("\n"))

Page 143. Table 6.4, column "Sparc", last two lines should refer to i1 and i2 instead of i0 and i1.
Fourth line after the figure should refer to "i1 and i2" instead of "i0 and i1".

Page 149. Last sentence before "KEEPING TRACK OF LEVELS" should read, "When Semant looks at level.formals, it will get these two offsets, suitably converted into Access values."

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

Page 158. Middle of the page, the 7th line in the entry for JUMP should refer to LabelList instead of ExpList.

Page 191. Algorithm 8.4, delete the comment "(All the successors of b are marked)" which is false (the algorithm is still correct).

Page 203. Figure 9.4, the third tree for STORE uses a where it should use d.

Page 207. The program shown under 2. Classes of registers implements t3<-t1*t2, not t1<-t2*t3 as claimed.

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

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

Page 230. 7th line after figure, "prove that b*b>0" should be "prove that b*b>=0".

Page 262. Algorithm 11.11, line 8, should be:
unspill: reg[tright]:=`r(n+1)'; emit instruction to fetch reg[tright]

Page 334. Algorithm 15.10, box on the right: the formal parameters of f ' should be (a1,...,ai-1,ai+1,

Page 344. Lines 13 and 14, the two assignments to th.memo and th.func should be to mythunk.memo and mythunk.func.

Page 347. "It is wasteful to build all three lists" should be "It is wasteful to build these lists."

Page 349. Line 2 of the main text, "(string of integer)" should be "(string or integer)".

Page 351. First paragraph should read, "If (f,(1,1,0)) is in the set H, then we know that f is non strict in its third argument. If (f,(1,1,0)) is never put into H, then f must be strict in its third argument."

Page 369. In the clause labeled "Occurrence of a variable", replace the word generalize with instantiate.

Page 370. Last line of the page should read, "Variable declaration with implicit type clause of Algorithm 16.10."

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

Page 416. Figure 18.2b is misleading because the graph shown has two "start" nodes. It is intended as a subgraph of some larger graph with a single entry node.

Page 417. Third line from bottom, the two equations D[s0]=... and D[n]=... have been inadvertantly jammed together, and should be on separate lines.

Page 420. Lines 7-9, 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 420. Line 18 should be,
h2 if h2 is in loop[h1].

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

Page 422. Seventh line from bottom, "1. d dominates all loop exits, or t is not live-out of any loop exit node" is correct, but a better criterion is,
"1. d dominates all loop exits at which t is live-out;"

Page 426. Line 13-14 should be,
Assuming j is characterized by (i,a,b), then k is described by (i,a.c,b.c) or (i,a+d,b), depending on whether k's definition was j.c or j+d.

Page 428. Line 14, "invariant values" should be "invariant values and in definitions of itself,"
Line 19, "so therefore the comparison j<n can be written as" should be "so therefore the comparison k<n can be written as".

Page 430. Lines 13 and 14, labels L1 and L2 should be swapped:
if u>j goto L1 else goto L2
if u<=j goto L2 else goto L1

Page 431. Line 3 should have Delta in front of k1 and km:
k>=0 and Deltak1>=0 and . . . and Deltakm>=0

Page 432. Lines 24 and 25, labels L1 and L2 should be swapped:
if u'>=j goto L1 else goto L2
if u'<j goto L2 else goto L1

Page 441. Figure 19.4 (b,f,g), block 6 should increment k by 2, not by 1.

Page 442. Lines 10-11 should read,
1. If x is the ith argument of a phi function in block n, then the definition of x dominates the ith predecessor of n.

Page 445. Algorithm 19.6, lines 10 and 14, all references to Aphi[n] should refer to Aphi[Y].
Algorithm 19.6, line 15 should read "if a not in Aorig[Y]".
First full paragraph on page 445 should read,

Algorithm 19.6 starts with a set V of variables, a graph G of control-flow nodes -- each node is a basic block of statements -- and for each node n a set Aorig[n] of variables defined in node n. The algorithm computes Aphi[a], the set of nodes that must have phi-functions for variable a. Note that sometimes a node may contain an ordinary definition and a phi-function for the same variable; for example, in Figure 19.3b, a is in Aorig[2] and node 2 is in Aphi[a].

Page 448. Last paragraph should read,

Suppose there is a CFG path from a to b but a is not an ancestor of b. This means that some edge on the path is not a spanning-tree edge, so b must have been reached in the depth-first search before a was (otherwise, after visiting a the search would continue along tree-edges to b). Thus, dfnum(a) > dfnum(b).

Page 460. Figure 19.13 (a), block 6 should increment k2 by 2, not by 1.

Page 470. Figure 19.19, block 6 (on left), and else clause of if-statement (on right) should increment k2 by 2, not by 1.
Figure 19.19, right-hand side, line 8 should refer to j2, not j1.

Page 480. Line 4, "hypothetical machine" should be "MIPS R4000".

Page 481. Figure 20.2, lines 5-6 of the caption should read,

nor four cycles later (because of Add and Round hazards). But if there were two adders and two rounding units, then an ADD could be started four

Page 492. Figure 20.10, steps 2-4 should be as shown:
Figure 20.10, corrected

Page 497. The first full sentence should read,

A mispredict rate of 10% can result in very many stalled instructions -- if each mispredict stalls 11 instruction slots, as described in the example on page 494, and there is one mispredict every 10 branches, and one-sixth of all instructions are branches, then 18% of the processor's time is spent waiting for mispredicted instruction fetches.

Page 499. Exercise 20.2g, "Run Algorithm itermod" should be "Run Algorithm 20.9".

Page 529. 4th line from bottom, change both occurrences of "integer" to "int".