Engineering a Compiler Errata Page Keith D. Cooper and Linda Torczon Rice University, Houston, Texas Published by Morgan Kaufmann, an imprint of Elsevier Science Contact the publisher

Related sites

Errata for the First Printing

• Page 17, Digression:
  The definition of "storeAI" at the bottom of the digression uses inconsistent subscripts on the constant. Both should read "c3", so the "meaning" of "storeAI r1 => r2,c2" is "r1 -> Memory(r2+c3)".
• Page 18, Figure 1.3:
  The final operation should store to address @w, not zero.

• Page 51, Figure 2.6:
  The WorkList should be initialized to {q-sub-0} rather than just q-sub-0
• Page 57, third paragraph:
  "Any state d-sub-a ..." should read "Any state d-sub-k"
• Page 57, fourth paragraph:
  Last line above figure, the subscripts are wrong in the new sets.
  The text should read "new sets {d-sub-i} and {d-sub-j, d-sub-k} ..."
• Page 57, Figure 2.9:
  On the right hand side, the partition containing d-sub-y and d-sub-z should be labelled p-sub-3
  (rather than p-sub-2).
• Page 72:
  The remark about perfect hashing is unclear because of text deleted in the body of the chapter. The following text should appear in place of the final paragraph of notes at the end of Chapter 2.

  Preston Briggs pointed out to us that perfect hashing [248] for reserved words (also called keywords) can have a negative impact on scanner performance unless the table lookup knows that it uses a perfect hash. His argument is simple; if the scanner uses a perfect hash table to identify reserved words, then the failure mechanism in the perfect hash lookup is invoked for every identifier. (Presumably, identifiers are not reserved words.) In the worst case (an open addressing table that is full), the cost of these failures can be linear in the number of reserved words. Adding that cost to each lookup on an identifier could significantly increase the cost for those words.

  The FORTRAN code in Figure 2.14 is taken from a talk given by F.K. Zadeck while he was a graduate student.

• Page 76, Digression on Backus-Naur Form:
  The two occurrences of "baa" in the inset example of BNF should be underlined
  (as mentioned immediately before the example).
• Page 78:
  The equation
  s = { SheepNoise }
  should not have brackets. s is a symbol, not a set.
• Page 82, Inline figure showing two if-then-else constructs:
  The example on the right should have "Assignment2" indented to match the first "then" rather than the second "then."
  That is, the line "else Assignment 2" should be moved eight characters to the left.
• Page 84, diagram at bottom right of page:
  The subtree for num-sub-2 should be a child of Term, not of the multiplication symbol.
• Page 98, near bottom:
  "In this grammar, FOLLOW(Expr') is { eof }." should read
  "In this grammar, FOLLOW(Expr') is { eof, ) }."
• Page 99, Figure 3.5:
  In the computation of the FOLLOW sets, the line that checks if epsilon is an element of the FOLLOW set of beta-sub-i should be checking the FIRST set of beta-sub-i. That is:
  if epsilon is a member of FIRST(beta-sub-i) then
• Page 149, Line 8:
  The citation to article [7] in the bibliography should be a citation to entry [9], Aho and Ullman's 1973 book, The Theory of Parsing, Translation, and Compiling

• Page 174, Figure 4.5:
  The arrows in the dependence graph are placed in a sloppy fashion, particularly those arrows denoting the flow of values between pos and val attributes of a List node. The arrows should show the downward flow of pos values (for example pos:0 --> pos:1 --> pos:2 as the List nodes descend from right to left).
• Page 178, unnumbered figure:
  Each occurrence of an `F' as a type attribute should be an 'I'. Furthermore, the fonts on the type attributes should match the three lines above the drawing.

• Figure 5.5, page 224:
  The final line on the "three-address code" side of the figure should be "t-sub-5 <- t-sub-4 - t-sub-3"
  (rather than "t-sub-5 <- t-sub-4 - t-sub-1").
• Exercise 1 for Section 5.5 (page 739):
  The code contains two typographical problems. The first assignment in procedure "B" should read
  "x = pow(2,k);"
  and the declaration of "p" in procedure "A" should be an "int" rather than an "int *"
• Exercise 3 for Section 5.7 (page 740):
  The program text contains two lines numbered 10. The lines starting with the second 10 should be renumbered accordingly.
  Part (a) of the question refers to line 11 (or, the second line 10 as printed).

• Page 262, Second paragraph:
  "screates" should be "creates"
• Page 288, Second paragraph under "Saving Registers":
  "for which does not." should read "for which it does not."
• Exercise 3 for Section 6.3 (page 743):
  "Consider the following Pascal, in which ..." should read
  "Consider the following Pascal program, in which ...".

• Page 388, line 1:
  "... has been been ..." should be "... has been ..."
• Page 420, Figure 8.8:
  The figure has a number of typographical problems.
  The update to VarKill must occur before the two membership tests.
  The upper bound on the first loop (k) should be the number of operations in the block.
  The "+" in "add y + z" should be "op".
  
  This pdf file gives the corrected text for the figure.

• Page 448, Figure 9.5:
  The code on the left does not match the CFG. The statement "x <- 0" should be exdented to match the first two lines, leaving only the third line indented (and, thus, under control of the "if").
• Page 451, bottom set of displayed equations:
  "VeryBust" should be "VeryBusy", in all three occurrences.
• Page 461, lines 11 and 13:
  In both cases, the line should read "n is not an element of DOM(m) - {m}" rather than "m is not an element of DOM(n) - {n}"
• Exercise 2 for Section 9.4:
  This question is not well formed, because of the definition that it gives of a back edge. The classic three node irreducible graph (S->x, S->y, x->y, y->x) has no back edges under the definition, even though it clearly contains a loop.

  A more reasonable question might be: An alternate definition of reducibility is: "in a reducible graph, any strongly-connected component (SCC) contains one node, h that dominates all other nodes in the SCC." Prove that this definition of reducibility is equivalent to the definition based on the transformations T1 and T2 in Section 9.4.1.

• Page 499, Paragraph at bottom beginning "The definition ...":
  "... if every path from i to the CFG's exit node passes through i"
  should read
  "... if every path from i to the CFG's exit node passes through j"
  (change in the last letter)
• Page 517, Figure 10.10:
  The description of the meet rule (fourth line) uses a capital T twice when it should use the mathematical symbol for the lattice element "top".
• Page 543, Line 30:
  The reference to entry 69 in the bibliography should be a reference to entry 169, Hailpern's 1998 paper on cost-optimal code motion.

• Page 556, Figure 11.4:
  The operator shown as "3" should be a multiplication symbol.
• Page 570, first inline example:
  the left-hand "storeAI" operation should target r-sub-arp instead of r-sub-0
  (as the right-hand one does)
• Page 584, 12th line from bottom:
  Reference to entry 277 should be a reference to 276.

• Description of the cover illustration:
  The cover art is a cropped portion of Outram's drawing "The Landing of the Ark." It has sometimes been referred to in print as "The Birth of Conciousness." The "About the Cover" section of the book uses the correct title.