Many interpreters use an annotated syntax tree to represent the running pro- gram: "execution" then amounts to tree traversal. In our GCD program, an inter- preter would start at the root of Figure 1.6 and visit, in order, the statements on the main spine of the tree. At the first"node, the interpreter would notice that the right child is a call: it would therefore call the getint routine (found in slot 3 of the symbol table) and assign the result into i (found in slot 5 of the symbol table). At the secondnode the interpreter would similarly assign the result of getint intoj. At the while node it would repeatedly evaluate the left(") child and, if the result was true, recursively walk the tree under the right (if) child. Finally, once the while node's left child evaluated to false, the interpreter would EXAMPLE 1.25 Inter preting the syntax tree move on to the final call node, and output its result. In many compilers, the annotated syntax tree constitutes the intermediate form that is passed from the front end to the back end. In other compilers, se- mantic analysis ends with a traversal of the tree (typically single pass) that gener- ates some other intermediate form. One common such form consists of a control flow graph whose nodes resemble fragments of assembly language for a simple 10 As we shall see in Section 6.1.3, Java and C# actually do enforce initialization at compile time but only by adopting a conservative set of rules for "definite assignment," outlawing programs for which correctness is difficult or impossible to verify at compile time 34 Chapter 1 Introduction program while (5) cal 6) call (4) (5 Index Symbol T void type type 2 int 3 getint func: (1)(2) putint c: (2) (1) (5) 6) 6) (5) 2 igure 1.6 Syntax tree and symbol table for the GCD program. Note the contrast to Fig- ure 15: the syntax tree retains just the essential structure of the program, omitting details that were needed only to drive the parsing algorithm. 5 Expanding on Example 1.25, trace an interpretation of the ged program on the inputs 12 and 8. Which syntax tree nodes are visited, in which order