Symbol-Table ManagementThe symbol table stores information about program variables that will be used across phases. Typically, this includes type information and storage location.A possible point of confusion: the storage location does not give the location where the compiler has stored the variable. Instead, it gives the location where the compiled program will store the variable.The Grouping of Phases into PassesLogically each phase is viewed as a separate program that reads input and produces output for the next phase, i.e., a pipeline. In practice some phases are combined into a pass.For example one could have the entire front end as one pass.The term pass is used to indicate that the entire input is read during this activity. So two passes, means that the input is read twice. We have discussed two pass approaches for both assemblers and linkers. If we implement each phase separately and use multiple passes for some of them, the compiler will perform a large number of I/O operations, an expensive undertaking.As a result techniques have been developed to reduce the number of passes. We will see in the next chapter how to combine the scanner, parser, and semantic analyzer into one phase. Consider the parser. When it needs another token, rather than reading the input file (presumably produced by the scanner), the parser calls the scanner instead. At selected points during the production of the syntax tree, the parser calls the intermediate-code generatorwhich performs semantic analysis as well as generating a portion of the intermediate code.For pedagogical reasons, we will not be employing this technique. Thus your compiler will consist of separate programs for the scanner, parser, and semantic analyzer / intermediate code generator. 

Reducing the number of passes

One problem with combining phases, or with implementing a single phase in one pass, is that it appears that an internal form of the entire program will need to be stored in memory. This problem arises because the downstream phase may need early in its execution, information that the upstream phase produces only late in its execution. This motivates the use of symbol tables and a two pass approach. However, a clever one-pass approach is often possible.

Consider the assembler (or linker). The good case is when the definition precedes all uses so that the symbol table contains the value of the symbol prior to that value being needed. Now consider the harder case of one or more uses preceding the definition. When a not-yet-defined symbol is first used, an entry is placed in the symbol table, pointing to this use and indicating that the definition has not yet appeared. Further uses of the same symbol attach their addresses to a linked list of “undefined uses” of this symbol. When the definition is finally seen, the value is placed in the symbol table, and the linked list is traversed inserting the value in all previously encountered uses. Subsequent uses of the symbol will find its definition in the table.

This technique is called backpatching.