Modern Compiler Implementation in C: Basic Techniques

©1997 by Andrew W. Appel

Report an error in the book or software

Errors in first printing

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

Page 9. The definition of A_CompoundStm should be:

A_stm A_CompoundStm(A_stm stm1, A_stm stm2) {
  A_stm s = checked_malloc(sizeof(*s));
  s->kind = A_compoundStm;
  s->u.compound.stm1=stm1; s->u.compound.stm2=stm2;
  return s;
}

Page 10. In Program 1.5, two occurrences of String should be string, typdef should be typedef, and the definition of A_binop should be moved up. A corrected version is available as part of the software for Chapter 1.

Page 13. The 11th line from the bottom (2nd line of the program example), should read,
struct table {string id; int value; Table_ tail};

Page 15.The insert function should use strcmp(key,t->key)<0 instead of key<t->key, and similarly use strcmp(key,t->key)>0 instead of key>t->key.
Line 5 of the program should contain t->right=r; and not T->right=r;

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 34. Reference to toy.lex should be tiger.lex.

Page 47. In the first line, the enumerator list should have braces:

enum token {IF, THEN, ELSE, BEGIN, END, PRINT, SEMI, NUM, EQ};

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

Page 53. Last line of text should refer to "same nonterminal S", not "same nonterminal X".
Grammar 3.14, both occurrences of F' should be T'.

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

Page 54. First 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 57. 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 60. In the state 3 box, the first line should read S->(.L), not L->(.L)

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

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

Page 68. 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 77. Exercise 3.5, production 4's left-hand side should be E, not B.

Page 81. The NUM case of the F function should return tokval.num, not val.num.
There should be no = sign after int Tprime(int a).

Page 91. The abstract syntax fragment at the bottom of the page should read,

A_LetExp(
  A_DecList(A_VarDec(S_Symbol("a"),NULL,A_IntExp(5)),
  A_DecList(A_FunctionDec(
    A_FundecList(A_Fundec(
      S_Symbol("f"),NULL,S_Symbol("int"),
      A_CallExp(S_Symbol("g"), ...)),
    A_FundecList(A_Fundec(
      S_Symbol("g"),
        A_FieldList(S_Symbol("i"),S_Symbol("int"),NULL),
        NULL,
        A_CallExp(S_Symbol("f"), ...)),
    NULL))),
  NULL)),
  A_CallExp(S_Symbol("f"), NULL))

Page 92. The abstract syntax fragment in the middle of the page should read,

A_TypeDec(
  A_NametyList(A_Namety(S_Symbol("tree"),
      A_RecordTy(
         A_FieldList(A_Field(S_Symbol("key"),S_Symbol("int")),
         A_FieldList(A_Field(S_Symbol("children"),S_Symbol("treelist")),
         NULL)))),
  A_NametyList(A_NameTy(S_Symbol("treelist"),
      A_RecordTy(
         A_FieldList(A_Field(S_Symbol("head"),S_Symbol("tree")),
         A_FieldList(A_Field(S_Symbol("tail"),S_Symbol("treelist")),
         NULL)))),
  NULL)))

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

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 97. Program 5.2, fourth line from bottom, should be void pop(string key){ with no star.

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

static struct S_symbol_ marksym = {"",0};

Page 102. Table 5.7: the return type of TAB_enter should be void, not TAB_table.
In the first line of text, table.put(x,b) should be S_enter(table, x, b)

Page 108. In bottom half of page, 4th line of program example, S_look(env,...) should be S_look(venv,...).

Page 109. Near bottom of page, transDec(venv,tenv,d); should be transDec(venv,tenv,d->head);

Page 110. 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 111. The functionDec clause of transDec shown on this page has several errors. Here is a correct version:

void transDec(S_table venv, S_table tenv, A_dec d) {
 switch(d->kind) {
     .
     .
     .
  case A_functionDec: {
   A_fundec f = d->u.function->head;
   Ty_ty resultTy = tylook(tenv,f->result,f->pos);
   Ty_tyList formalTys = makeFormalTyList(tenv,f->params);
   S_enter(venv,f->name,E_FunEntry(formalTys,resultTy));
   S_beginScope(venv);
   {A_fieldList l; Ty_tyList t; 
    for(l=f->params, t=formalTys; l; l=l->tail, t=t->tail) 
       S_enter(venv,l->head->name,E_VarEntry(t->head));
   }
   transExp(venv, tenv, d->u.function->body);
   S_endScope(venv);
   break;
  }
The function tylook should call S_look, and if the type is not declared, should use its t->pos argument to formulate an error message.

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

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

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

Page 134. 7th line from bottom, Fr_access should be F_access. Last line, Frame.access should be F_access.

Page 137. (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 143.The 13th line from the bottom 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 145. 12th line from bottom, delete the word cond.

Page 146. Each time PatchList is used in the code example at the top of the page, the first argument should have an & before it.

Page 147. Program 7.3, in the return statement, false and true should be f and t.

Page 147. 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 148. First sentence should refer to tenv and venv, not tenv and env.

Page 150. 7th line, Translate.simpleVar should be Tr_simpleVar.

Page 156. Eleventh line from the bottom, Tree.NAME should be T_Name

Page 160. Section 7.3, second paragraph: transDec does not return a result record containing new environments, it just returns a Tr_Exp.

Page 178.The last sentence of the third paragraph should begin, "But 8.3c shows a better trace covering..."

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

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

Page 199-200. Calls to munchStm and munchExp are missing parentheses around the argument parameter, operators + and ^ are used (inconsistently!) for string concatenation, and lab.toString() should be Temp_labeLstring(lab).

Page 200. 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 210. In Table 10.5, 4th iteration, row 3, change c to b.

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

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

Page 239. 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, Doug Morgan, and others for reporting these errors.