Modern Compiler Implementation in ML: 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 19. 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 24. Figure 2.6, the automaton for M* should be

Page 26. 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 28. The first noncomment line of Program 2.9 should be 

type lexresult = Tokens.token

Page 32. Reference to toy.lex should be tiger.lex.

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

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

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

Page 52. Third line of text should refer to "same nonterminal S", not "same nonterminal X".
The second 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 54. 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 58. In the state 3 box, the first line should read S->(.L), not L->(.L)

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

Page 61. 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 63. 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 63. 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 64. 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 65."As explained on page 52, factoring the grammar will eliminate the ambiguity." This is incorrect; factoring does not eliminate the ambiguity, but a different grammar transformation does.

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

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

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

Page 79. Second line, first word, should be fun not and.

Page 84. Program 4.5, after the fourth line, insert in f(!table) end

Page 90. Line 14 should be 

body=CallExp{func=symbol"f",pos=71,args=nil} }]],
not body=SeqExp nil}]], as shown, and some of the pos numbers are inaccurate.

Page 91. prabsyn.[ch] should be printabsyn.sml

Page 91. In Exercise 4.2, the program should be 

  a := 6; a := (a := a+1, a+4) + a; print(a)

Page 96. 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 107. 15th line from bottom, SOME(E.VarEntry{access,ty}) should be SOME(E.VarEntry{ty}).

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

Page 127. Sentence after function m... should start with ``If x stays in parameter register 1 throughout m, ...''

Page 135. (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 141.Line 11 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 172.The last sentence of the second paragraph should begin, "But 8.3c shows a better trace covering..."

Page 181. 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 187. In the "Two-address instructions" paragraph, the instructions should read, 

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

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

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

Page 221. (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 224.First line should read, Degree(T)<K. Since T will lose the neighbor X and gain the neighbor R, ...

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

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

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

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

Page 312. 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 316. Last line should refer to h(i), not i.

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

Page 332. 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 333. In the table, in the column headed gen[s], delete each of the three instances of "-kill[s]".

Page 337. 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 338. Algorithm 16.6, the first line should read,
W := the set of all nodes

Page 347. 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 354. 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 357. 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 359. 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, Doug Morgan, and others for reporting these errors.