编译器设计05

1 .CS 153: Concepts of Compiler Design September 4 Class Meeting Department of Computer Science San Jose State University Fall 2018 Instructor: Ron Mak www.cs.sjsu.edu/~mak 1

2 .2 Quick Review of the Framework TO: FROM: Our next topic: The symbol table Chapter 4

3 .3 The Symbol Table: Conceptual Design Each entry in the symbol table has a name attributes At the conceptual level, we don ’ t worry about implementation. Goal: The symbol table should be source language independent.

4 .4 What to Store in Each Symbol Table Entry Each symbol table entry is designed to store information about an identifier . The attribute keys indicate what information we will store for each type of identifier. Store common information in fixed fields (e.g., lineNumbers ) and store identifier type-specific information as attributes. public enum SymTabKeyImpl implements SymTabKey { // Constant. CONSTANT_VALUE, // Procedure or function. ROUTINE_CODE, ROUTINE_SYMTAB, ROUTINE_ICODE, ROUTINE_PARMS, ROUTINE_ROUTINES, // Variable or record field value. DATA_VALUE } wci.intermediate.symtabimpl.SymTabKeyImpl

5 .5 What Needs a Symbol Table? A Pascal program Identifiers for constant, type, variable, procedure, and function names. A Pascal procedure or function Identifiers for constant, type, variable, procedure, and function names. Identifiers for formal parameter (argument) names. A Pascal record type Identifiers for field names.

6 .6 The Symbol Table Stack Language constructs can be nested . Procedures and functions are nested inside a program. Procedures and functions can be nested inside of each other. Record types are defined within programs, procedures, and functions. Record types can be nested inside of each other. Therefore, symbol tables need to be kept on a symbol table stack .

7 .7 The Symbol Table Stack, cont ’d Whichever symbol table is on top of the stack is the local symbol table . The first symbol table created (the one at the bottom of the stack) is the global symbol table . It stores the predefined information, such as entries for the names of the standard types integer , real , char , and boolean . During the translation process, symbol tables are pushed onto and popped off the stack … … as the parser enters and exits nested procedures, functions, record types, etc. Global symbol table

8 .8 The Symbol Table Stack, cont ’ d For now, we ’ ll have only have a single symbol table. Therefore, the local symbol table is the global symbol table. We won’t need multiple symbol tables until we start to parse declarations. Implementing the symbol table stack now will make things easier for us later. Global symbol table

9 .8 The Symbol Table Stack, cont ’ d For now, we ’ ll have only have a single symbol table. Therefore, the local symbol table is the global symbol table. We won’t need multiple symbol tables until we start to parse declarations. Implementing the symbol table stack now will make things easier for us later. Global symbol table

10 .10 Cross-Reference Listing A cross-reference listing verifies the symbol table code: java - classpath classes Pascal compile -x newton.pas Modifications to the main Pascal class: parser.parse (); iCode = parser.getICode (); symTabStack = parser.getSymTabStack (); if ( xref ) { CrossReferencer crossReferencer = new CrossReferencer (); crossReferencer.print ( symTabStack ); } backend.process ( iCode , symTabStack ); source.close (); A new utility class CrossReferencer generates the cross-reference listing. Demo

11 .11 Quick Review of the Framework FROM: TO: Next topic: Parsing assignment statements and expressions, and generating parse trees. Chapter 5

12 .12 Pascal Statement Syntax Diagrams

13 .13 Pascal Statement Syntax Diagrams, cont’d For now, greatly simplified!

14 .14 Parse Tree: Conceptual Design BEGIN alpha := -88; beta := 99; result := alpha + 3/(beta – gamma) + 5 END More accurately called an abstract syntax tree (AST) .

15 .15 Parse Tree: Conceptual Design At the conceptual design level, we don ’ t care how we implement the tree . This should remind you of how we first designed the symbol table.

16 .16 Parse Tree: Basic Tree Operations Create a new node. Create a copy of a node. Set and get the root node of a parse tree. Set and get an attribute value in a node. Add a child node to a node. Get the list of a node ’ s child nodes. Get a node ’ s parent node.

17 .17 Intermediate Code Interfaces Goal: Keep it source language-independent.

18 .18 Intermediate Code Implementations

19 .19 An Intermediate Code Factory Class public class ICodeFactory { public static ICode createICode () { return new ICodeImpl (); } public static ICodeNode createICodeNode ( ICodeNodeType type) { return new ICodeNodeImpl (type); } } wci.intermediate.ICodeFactory

20 .20 Coding to the Interfaces (Again) // Create the ASSIGN node. ICodeNode assignNode = ICodeFactory.createICodeNode (ASSIGN); ... // Create the VARIABLE node (left-hand side). ICodeNode variableNode = ICodeFactory.createICodeNode (VARIABLE); ... // Adopt the VARIABLE node as the first child. assignNode.addChild ( variableNode ); wci.frontend.pascal.parsers.AssignmentStatementParser

21 .21 Intermediate Code (ICode) Node Types public enum ICodeNodeTypeImpl implements ICodeNodeType { // Program structure PROGRAM, PROCEDURE, FUNCTION, // Statements COMPOUND, ASSIGN, LOOP, TEST, CALL, PARAMETERS, IF, SELECT, SELECT_BRANCH, SELECT_CONSTANTS, NO_OP, // Relational operators EQ, NE, LT, LE, GT, GE, NOT, // Additive operators ADD, SUBTRACT, OR, NEGATE, // Multiplicative operators MULTIPLY, INTEGER_DIVIDE, FLOAT_DIVIDE, MOD, AND, // Operands VARIABLE, SUBSCRIPTS, FIELD, INTEGER_CONSTANT, REAL_CONSTANT, STRING_CONSTANT, BOOLEAN_CONSTANT, } Do not confuse node types ( ASSIGN , ADD , etc.) with data types (integer, real, etc.). We use the enumerated type ICodeNodeTypeImpl for node types which is different from the enumerated type PascalTokenType to help maintain source language independence. wci.intermediate.icodeimpl.ICodeNodeTypeImpl

22 .22 Intermediate Code Node Implementation Each node is a HashMap<ICodeKey, Object > . Each node has an ArrayList<ICodeNode> of child nodes. public class ICodeNodeImpl extends HashMap < ICodeKey , Object> implements ICodeNode { private ICodeNodeType type; // node type private ICodeNode parent; // parent node private ArrayList < ICodeNode > children; // children array list public ICodeNodeImpl ( ICodeNodeType type) { this.type = type; this.parent = null; this.children = new ArrayList < ICodeNode >(); } ... } wci.intermediate.icodeimpl.ICodeNodeImpl

23 .23 A Parent Node Adopts a Child Node When a parent node adds a child node, we can say that the parent node “ adopts ” the child node. Keep the parse tree implementation simple! public ICodeNode addChild ( ICodeNode node) { if (node != null) { children.add (node); (( ICodeNodeImpl ) node).parent = this; } return node; } wci.intermediate.icodeimpl.ICodeNodeImpl.cpp

24 .24 What Attributes to Store in a Node? Not much! Not every node will have these attributes. LINE : statement line number ID : symbol table entry of an identifier VALUE : data value Most of the information about what got parsed is encoded in the node type and in the tree structure . enum class ICodeKeyImpl {     LINE, ID, LEVEL, VALUE, }; wci.intermediate.icodeimpl.ICodeKeyImpl

25 .25 Statement Parser Class Class StatementParser is a subclass of PascalParserTD which is a subclass of Parser . Its parse() method builds a part of the parse tree and returns the root node of the newly built subtree .

26 .26 Statement Parser Subclasses StatementParser itself has subclasses: CompoundStatement -Parser AssignmentStatement -Parser ExpressionParser The parse() method of each subclass returns the root node of the subtree that it builds. Note the dependency relationships among StatementParser and its subclasses.

27 .27 Building a Parse Tree Each parse() method builds a subtree and returns the root node of the new subtree . The caller of the parse() method adopts the subtree ’ s root node as a child of the subtree that the caller is building. The caller then returns the root node of its subtree to its caller. This process continues until the entire source has been parsed and we have the entire parse tree.

28 .28 Building a Parse Tree Example: BEGIN alpha := 10; beta := 20 END CompoundStatementParser ’s parse() method creates a COMPOUND node. 2. AssignmentStatementParser ’ s parse() method creates an ASSIGN node and a VARIABLE node, which the ASSIGN node adopts as its first child.

29 .29 Building a Parse Tree 3. ExpressionParser ’ s parse() method creates an INTEGER CONSTANT node which the ASSIGN node adopts as its second child. 4. The COMPOUND node adopts the ASSIGN node as its first child. BEGIN alpha := 10; beta := 20 END