List of Tables

Chapter 1: Introduction

Figure 1.1: Compilation process phases.

Figure 1.2: Syntax analysis imposes a structure hierarchy on the token string.

Chapter 2: Finite Automata and Regular Expressions

Figure 2.1: Transition diagram for finite automata ( p , a ) = q .

Figure 2.2: Transition diagram for finite automata that handles several transitions.

Figure 2.3: Transition diagram for M = ({q , q ₁ , q ₂ , q ₃ }, {0, 1} , q , {q ₃ }).

Figure 2.4: Finite automata with ˆˆ -moves.

Figure 2.5: Transitioning from an ˆˆ -move NFA to a non- ˆˆ -move NFA.

Figure 2.6: Making the initial state of the NFA one of the final states.

Figure 2.7: Example 2.1 NFA.

Figure 2.8: Example 2.2 DFA equivalent to an NFA.

Figure 2.9: Partitioning down to a single state.

Figure 2.10: Merging nondistinguishable states B and C into a single state B ₁ .

Figure 2.11: Transition diagram for Example 2.3 finite automata.

Figure 2.12: Finite automata containing even number of zeros and odd number of ones.

Figure 2.13: Finite automata containing odd number of zeros and even number of ones.

Figure 2.14: Example 2.6 finite automata considers the set prefix.

Figure 2.15: Finite automata accepts strings containing the substring 101.

Figure 2.16: DFA using the names A-D and q _{ˆ 5} .

Figure 2.17: Complement to Figure 2.16 automata.

Figure 2.18: DFA after minimization.

Figure 2.19: Finite automata that accepts string decimals that are divisible by three.

Figure 2.20: Finite automata accepts strings containing 101.

Figure 2.21: Finite automata identified by the name states A-D and q _{ˆ 5} .

Figure 2.22: Complement to Figure 2.21 automata.

Figure 2.23: Minimization of nondistinguishable states of Figure 2.22.

Figure 2.24: Automata that accepts binary strings that are divisible by three.

Figure 2.25: Transition diagram for ( a + b ).

Figure 2.26: Transition diagram for ( a + b )*.

Figure 2.27: Transition diagram for a . ( a + b )*.

Figure 2.28: Automata for a .( a + b )* . b .

Figure 2.29: Automata for a .( a + b )*. b . b .

Figure 2.30: Deriving the regular expression for a regular set.

Figure 2.31: Transition diagram.

Figure 2.32: Complement to transition diagram in Figure 2.31.

Figure 2.33: Transition diagram of automata M ₁ .

Figure 2.34: Transition diagram of automata M ₂ .

Chapter 3: Context-Free Grammar and Syntax Analysis

Figure 3.1: Derivation tree for the string id + id * id.

Figure 3.2: Parse tree resulting from leaf-node concatenation.

Figure 3.3: Multiple parse trees.

Figure 3.4: Ambiguous grammar parse trees.

Figure 3.5: Parse tree generated by using both the right- and left-most derivation orders.

Figure 3.6: Parse tree generated from both the left- and right-most orders of derivation.

Figure 3.7: Transition diagram for automata that accepts the regular grammar of Example 3.13.

Figure 3.8: Deterministic equivalent of the non-deterministic automata shown in Figure 3.7.

Figure 3.9: Non-deterministic automata.

Figure 3.10: Transition diagram for deterministic automata equivalent shown in Figure 3.9.

Figure 3.11: Regular-grammar automata.

Figure 3.12: Transition diagram of automata that accepts L ( G ₁ ).

Figure 3.13: Transition diagram of automata after removal of state D.

Figure 3.14: Transition diagram for the automata that results from merged states.

Figure 3.15: Non-deterministic automata that accepts L ( G ₂ ).

Figure 3.16: Transition diagram of the equivalent deterministic automata for Figure 3.15.

Figure 3.17: Finite automata accepting the right linear grammar for a regular expression.

Figure 3.18: Transition diagram for a finite automata specified by a reversed regular expression.

Chapter 4: Top-Down Parsing

Figure 4.1: Parser uses the S-production to expand the parse tree.

Figure 4.2: Parser uses the first alternative for A in order to expand the tree.

Figure 4.3: If the parser fails to match a leaf, the point of failure, d, reroutes (backtracks) the pointer to alternative paths from A.

Figure 4.4: The parser first expands S and fails to accept w = acdb.

Figure 4.5: The parser advances to c and considers nonterminal A for expension.

Figure 4.6: The parser first expands S.

Figure 4.7: The parser advances the pointer to a second occurrence of a.

Figure 4.8: The parser expands the next leaf labeled S.

Figure 4.9: The parser finds no match, so it backtracks.

Figure 4.10: The parser tries an alternate aa.

Figure 4.11: There is no further alternate of S that can be tried, so the parser will backtrack one more step.

Figure 4.12: The parser again finds a mismatch; hence, it backtracks.

Figure 4.13: The parser tries an alternate aa.

Figure 4.14: Since no alternate of S remains to be tried, the parser backtracks one more step.

Figure 4.15: The parser tries an alternate aa.

Figure 4.16: The parser arrives at the required parse tree.

Figure 4.17: The parser first expands S.

Figure 4.18: The parser advances the pointer to a second occurrence of a.

Figure 4.19: The parser considers the next leaf labeled by S.

Figure 4.20: The parser matches the third input symbol and moves on to the next leaf labeled by S.

Figure 4.21: The parser considers the fourth occurrence of the input symbol a.

Figure 4.22: The parser finds no match, so it backtracks.

Figure 4.23: The parser tries an alternate aa.

Figure 4.24: No alternate of S can be tried, so the parser will backtrack one more step.

Figure 4.25: Again finding a mismatch, the parser backtracks.

Figure 4.26: The parser then tries an alternate.

Figure 4.27: No alternate of S remains to be tried, so the parser will backtrack one more step.

Figure 4.28: The parser again finds a mismatch; therefore, it backtracks.

Figure 4.29: The parser tries an alternate aa.

Figure 4.30: The parser then tries an alternate aa.

Figure 4.31: The parser successfully generates the parse tree for aaaa.

Figure 4.32: The parser expands S.

Figure 4.33: The parser matches the first symbol, advances to the second occurrence of a, and considers S for expansion.

Figure 4.34: The parser finds a match for the second occurrence of a and expands S.

Figure 4.35: The parser matches the third input symbol, considers the next leaf, and expands S.

Figure 4.36: The parser matches the fourth input symbol, considers the next leaf, and expands S.

Figure 4.37: A match is found for the fifth input symbol, so the parser considers the next leaf, and expands S.

Figure 4.38: The sixth input symbol also matches. So the next leaf is considered , and S is expanded.

Figure 4.39: No match is found, so the parser backtracks to S.

Figure 4.40: The parser backtracks one more step.

Figure 4.41: The parser tries the alternate aa.

Figure 4.42: Again, a mismatch is found. So, the parser backtracks.

Figure 4.43: No alternate of S remains, so the parser will back-track one more step.

Figure 4.44: The parser tries an alternate aa.

Figure 4.45: Again, a mismatch is found. The parser backtracks.

Figure 4.46: The parser then tries an alternate aa.

Figure 4.47: A mismatch is found, and the parser backtracks.

Figure 4.48: The parser tries for the alternate aa, fails to find a match, and cannot generate the parse tree for six occurrences of a.

Chapter 5: Bottom-up Parsing

Figure 5.1: NFA transition diagram recognizes viable prefixes.

Figure 5.2: Using subset construction, a DFA equivalent is derived from the transition diagram in Figure 5.1.

Figure 5.3: DFA transition diagram showing four iterations for a canonical collection of sets.

Figure 5.4: Transition diagram for Example 5.2 DFA.

Figure 5.5: DFA Transition diagram.

Figure 5.6: Transition diagram for the canonical collection of sets of LR(1) items.

Figure 5.7: Transition diagram for a DFA using a reduced collection.

Figure 5.8: LR(0) underlying set representations that can cause SLR parser conflicts.

Figure 5.9: LR(1) underlying set representations that can cause CLR/LALR parser conflicts.

Figure 5.10: LR(0) underlying set representations that can cause an SLR parser reduce-reduce conflict .

Figure 5.11: LR(1) underlying set representations that can cause an CLR/LALR parser.

Figure 5.12: Sets of LR(1) items represent two different CLR(1) parser states.

Figure 5.13: States are combined to form an LALR.

Figure 5.14: LR(1) items represent two different states of the CLR(1) parser.

Figure 5.15: LALR state set resulting from the combination of CLR(1) state sets.

Figure 5.16: Transition diagram for augmented grammar DFA.

Figure 5.17: States with actions in common point to the same location via an array.

Figure 5.18: List that incorporates the ability to append actions.

Figure 5.19: Transition diagram for the canonical collection of sets of LR(0) items in Example 5.3.

Figure 5.20: DFA transition diagram for Example 5.4.

Figure 5.21: Collection of nonempty sets of LR(1) items for Example 5.7.

Chapter 6: Syntax-Directed Definitions and Translations

Figure 6.1: The attribute value of node X is inherently dependent on the attribute value of node Y.

Figure 6.2: An annotated parse tree.

Figure 6.3: Parse tree with node attributes for the string int id1,id2,id3.

Figure 6.4: Dependency graph with four nodes.

Figure 6.5: Parse tree for the string id+id*id.

Figure 6.6: Syntax tree for id+id*id.

Figure 6.7: Values of attributes at the parse tree node for the string a + b * c .

Figure 6.8: Values of the attributes at the parse tree nodes for a + b * c , id.place = addr(symtab rec of a).

Figure 6.9: Values of the attributes at the parse tree nodes for a + b * c, id.place = addr(sumtab rec of a).

Figure 6.10: Translation scheme for a Boolean expression containing and, not, and or.

Figure 6.11: The addition of the nullable nonterminal N facilitates an unconditional jump.

Figure 6.12: A nullable nonterminal M provisions the translation of if-then.

Figure 6.13: The translation of the Boolean while statement is facilitated by a nullable nonterminal M.

Figure 6.14: Translation of the Boolean do-while.

Figure 6.15: Translation of Boolean repeat-until .

Figure 6.16: Handling the translation of the Boolean for.

Figure 6.17: A switch/case three-address translation.

Figure 6.18: Nullable nonterminals are introduced into a switch statement translation.

Figure 6.19: Contents of queue during the translation.

Chapter 7: Symbol Table Management

Figure 7.1: A pointer steers the symbol table to remotely stored information for the array a.

Figure 7.2: Symbol table names are held either in the symbol table record or in a separate string table.

Figure 7.3: A new record is added to the linear list of records.

Figure 7.4: The search tree organization approach to a symbol table.

Figure 7.5: Hash table method of symbol table organization.

Figure 7.6: Symbol table organization that complies with static scope information rules.

Chapter 8: Storage Management

Figure 8.1: Heap memory storage allows program-controlled data allocation.

Figure 8.2: Typical format of an activation record.

Figure 8.3: The CEP pointer is used to access the contents of the activation record.

Figure 8.4: Typical callee code segment.

Figure 8.5: An activation record that deals with nonlocal name references.

Figure 8.6: A typical callee segment.

Figure 8.7: Storage for declared names.

Chapter 10: Code Optimization

Figure 10.1: Program flow graph.

Figure 10.2: The flow graph back edges are identified by computing the dominators.

Figure 10.3: A flow graph with no back edges.

Figure 10.4: Flow graph with GEN and KILL block sets.

Figure 10.5: Nonunique solution to a data flow equation, where B is a predecessor of itself.

Figure 10.6: A flow graph containing a loop invariant statement.

Figure 10.7: Moving a loop invariant statement changes the semantics of the program.

Figure 10.8: Moving the preheader changes the meaning of the program.

Figure 10.9: Moving a value to the preheader changes the original meaning of the program.

Figure 10.10: Flow graph where I is a basic induction variable.

Figure 10.11: Modified flow graph.

Figure 10.12: Flow graph preheader modifications.

Figure 10.13: DAG representation of a basic block.

Chapter 11: Code Generation

Figure 11.1: DAG Representation.

Figure 11.2: DAG Representation with heuristic ordering.

Figure 11.3: DAG representation of three-address code for Example 11.3.

Figure 11.4: DAG representation tree after labeling.

Figure 11.5: The node n is an operand and not a subtree root.

Figure 11.6: The node n is an operator, and n ₁ and n ₂ are subtree roots.

Figure 11.7: A nontree DAG.

Figure 11.8: A DAG that has been partitioned into a set of trees.

Figure 11.9: Labeled tree for Example 11.4.

Figure 11.10: Tree with a label of two.

Figure 11.11: The left and right subtrees have been interchanged, reducing the register requirement to one.

Figure 11.12: Associativity is used to reduce a tree's register requirement.

Chapter 12: Exercises

Figure 12.1: State transition diagram.