------------------------------------------------ INF5110 - Spring 2005 Errata and comments for Kenneth C. Louden: COMPILER CONSTRUCTION, Principles and Practice Further comment may still be added ------------------------------------------------ The corrections/comments below are considered part of the REQUIRED READING FOR INF 5110 Page 159: (Not in the required reading, spring 2002) ---------------------------------------------------- In Figure 4.3 a second step doing substitution is missing. Page 168/169: ------------- We used a more basic definition of First(X), when X is a nonterminal: First(X) is the set of terminals that can start a string derived from X. In addition, epsilon is in First(X) if the empty string can be derived from X. First(alfa) is defined accordingly. Thus the theorem at page 169 is correct by definition. As an algorithm for finding First(X), we simply used the definition given at the middle of page 168, with the addition that step 2 is repeated until nothing more happens (and we did not look at the details of figure 4.6). Page 173/174: ------------- We used a more basic definition of Follow(X) (X a nonterminal): Follow(X) is the set of terminals that can follow X in a string derived from (the string) "S$", where S is the start symbol. Here the set of terminals should be extended with the "end-of-input marker" '$'. As an algorthim for finding Follow(X), we used the definition at the middle of page 173, where steps 2 and 3 are repeted until nothing more happens (and we did not look at the details of Figure 4.8). Page 202: --------- Line 4 from bottom. Add the following: An item where alfa is the empty string ("A -> . ") is both an initial item and a complete item. Page 277/278: ------------- Addition to the definition of synthesized attributes: A synthesized attribute A.a is also allowed to depend on inherited attributes of A. (Note, however, that such dependencies will not occur in S-attributed grammars, as they only have synthesized attributes). Page 290: --------- Additional requirement in the definition of L-attributed grammars: In the associated equiations for a_j, the attributes a_1, ..., a_k of X_0 must all be INHERITED attributes. That is, a_j can not depend on synthesized attributes of X_0. Page 295: --------- In section 6.3 we stressed that one could also use (part of) the syntax-tree itself as the symbol table. Then the 'lookup' operation will be a search process "upwards" in the tree, from where you currently are in the tree/program. This search should be done according to the visibility rules of the language. The 'insert' and 'delete' operations will then normally not be used, and they will be replaced by adding declaration nodes to the tree during buildup, and by changing the current position in the tree. Figure 6.17 can be seen as a version of this, where the declaration list of each block in the syntax tree is taken out as a (hash) table of its own. Page 329/330: ------------- As indicated at the middle of page 329, Table 6.10 is not an attribue grammar in the nomal sense, in that e.g. ":=" is used, indicating that it is more like an algorithm. In this connection it should also be added that the computation of the attributes should be done from left to right in the tree, so that e.g. the insert-operation (in the first rule) is called for exactly the right declarations whenever the lookup-operation is called. All together it would probably have been better to express this table as a recursive procedure going through the tree from left to right. Page 359: --------- Comments to the the given "calling sequence": 1. At the start of the code for the procedure itself (that is, in the code executed after step 5), space should be allocted for the local varibles of the procedure (and if necessary they should be initialized). 2. Steps 1, 2, and 3 of the exit steps should be done at the end of the code for the procedure, while step 4 should be done by the caller (probably immediately after the call instruction). 3. If an "access link" is included (see page 367), this should be computed and pushed on the stack between step 1 and 2 of the calling sequence. It should be computed as "fp.al.al....al", where the number of "al-steps" (al = access link) is the number of block levels between the caller and the block enclosing the called procedure. Page 380/381: ------------- In section 7.4.4 we stressed that in the algorithms discussed there it is an underlying assumption that when arriving at an object through a pointer (or during a sequential sweep through memory) it is always possible to find the SIZE of the object and at WHICH RELATIVE ADDRESSES IT CONTAINS POINTERS (as opposed to intergers, reals etc.). One way to arrange for this is to have a pointer at a fixed relative address in all objects, pointing to a statically allocted package containing information common to e.g. all objecs of a given class. This package could contain the size and pointer-positions in the objects of this class. (Then, also the virtual function table discussed at page 376 could be included in this package of information). - - - o o o - - -