Modern Compiler Implementation in C

©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 13. 11th line from bottom, missing semicolon before close brace; should be:
struct table {string id; int value; Table_ tail;};

Page 54. 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 55. 13th line from bottom: TIMES should not be in Tprime_follow.

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

Page 78. 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 99. The Tiger program shown is actually illegal, since g is declared to return no value but its body returns the value f().

Page 115.
6th line after figure, "UNIT" should be "Void".
Last line, delete the word struct.

Page 138. 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 179. 10th line from bottom, change "whether two expressions commute" to "whether a statement commutes with an expression".

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

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

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

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

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

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

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

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

Page 525. 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 43. 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 47. In the first line, the enumerator list should have braces:


Page 49. Lines 9-18 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 50. 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 53. Table 3.16 caption should refer to Grammar 3.15, not Grammar 3.8.

Page 57. 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 58. 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 65. In the left-hand box, the lookahead for the last two lines should be =, not $.

The last two lines of the page should read,

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

Page 66. 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 66. 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 70. Grammar 3.31, line 4, should be without vertical bars:


Page 75. Grammar 3.35, line 2, should be without vertical bars:


Page 76. Grammar 3.36, line 2, should be without vertical bars:


Page 93. Program 4.4, line 18, should be without vertical bars:


Page 96. Program 4.6, line 7, should be without vertical bars:


Page 99. The first five lines should read,
A_ExpList (A_AssignExp (4, A_SimpleVar (2, S_Symbol ("a")), A_IntExp (7,5)),
A_ExpList (A_OpExp (11, A_plusOp, A_VarExp (A_SimpleVar (10, S_Symbol ("a"))),
A_IntExp (12, 1)),

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

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

Page 110. Program 5.6, sixth line from bottom, Braces are mistakenly omitted around the initializer. Should be:

static struct S_symbol_ marksym = {"<mark>",0};

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

Page 119. In the code fragment (for case A_typeDec) at bottom of the page, the line

struct expty e = transExp(venv,tenv,d->u.var.init);
should be deleted.

Page 120. The tylook function is called here but never explained. It should call S_look, and if the type is not declared, should use its t->pos argument to formulate an error message.

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

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

Page 136. Last three lines, references to F_BoolList should be U_BoolList.

Page 138. Table 6.4, column "Sparc", last two lines should refer to i1 and i2 instead of i0 and i1.
Eighth line from the bottom should refer to "i1 and i2" instead of "i0 and i1".

Page 141. In the temp.h program fragment, the 7th and 11th lines should read,

   typedef struct Temp_tempList_ *Temp_tempList;

   typedef struct Temp_labelList_ *Temp_labelList;
without capitalization immediately after the underscore.

Page 143. Middle of the page, Fr_access should be F_access. 10th line from the bottom, Frame.access should be F_access.

Page 153. Lines 29-30 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 155. 12th line from bottom, delete the word cond.

Page 157. Bottom of the page, last sentence should refer to Tr_nx:

Also, unCx should never expect to see a Tr_exp with a kind of Tr_nx -- such a case should never occur in compiling a well typed Tiger program.

Page 160. 12th line, Translate.simpleVar should be Tr_simpleVar.

Page 166. Fourth line from the bottom, Tree.NAME should be T_Name

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

Page 196. Program 9.3, delete the first line (structure T = Tree).

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

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

Page 211. Figure 9.7, the case for MOVE(TEMP(i), e2) should emit

emit(AS_Move("ADD   `d0 <- `s0 + r0\n", i, munchExp(e2)))
instead of the AS_Oper expression that is shown.

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

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

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

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

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

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

Page 347. 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 365. In the clause labeled "Occurrence of a variable", replace the word generalize with instantiate.

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

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

Page 412. 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 413. Third line from bottom, the two equations D[s0]=... and D[n]=... have been inadvertantly jammed together, and should be on separate lines.

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

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

Page 418. 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 422. 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 424. 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 426. 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 427. Line 3 should have Delta in front of k1 and km:
k>=0 and Deltak1>=0 and . . . and Deltakm>=0

Page 428. 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 437. Figure 19.4 (b,f,g), block 6 should increment k by 2, not by 1.

Page 438. 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 441. 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 441 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 444. 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 456. Figure 19.13 (a), block 6 should increment k2 by 2, not by 1.

Page 466. 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 476. Line 4, "hypothetical machine" should be "MIPS R4000".

Page 477. 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 488. Figure 20.10, steps 2-4 should be as shown:
Figure 20.10, corrected

Page 493. 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 490, 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 495. Exercise 20.2g, "Run Algorithm itermod" should be "Run Algorithm 20.9".

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