编译器设计06

1 .CS 153: Concepts of Compiler Design September 6 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 FROM: TO: Next topic: Parsing assignment statements and expressions, and generating parse trees. Chapter 5

3 .3 Pascal Expression Syntax Diagrams

4 .4 Expression Syntax Diagrams, cont ’ d

5 .5 Expression Syntax Diagrams, cont ’ d

6 .6 Pascal ’ s Operator Precedence Rules Level Operators 1 (factor: highest ) NOT 2 (term) multiplicative: * / DIV MOD AND 3 (simple expression) additive: + - OR 4 (expression: lowest ) relational: = <> < <= > >= If there are no parentheses: Higher level operators execute before the lower level ones . Operators at the same level execute from left to right. Because the factor syntax diagram defines parenthesized expressions, parenthesized expressions always execute first, from the most deeply nested outwards .

7 .7 Example Decomposition alpha + 3/(beta – gamma) + 5

8 .8 Parsing Expressions Pascal statement parser subclass ExpressionParser has methods that correspond to the expression syntax diagrams: parseExpression () parseSimpleExpression () parseTerm () parseFactor () Each parse method returns the root of the subtree that it builds. Therefore, ExpressionParser ’ s parse() method returns the root of the entire expression subtree.

9 .9 Parsing Expressions, cont ’ d Pascal ’ s operator precedence rules determine the order in which the parse methods are called. The parse tree that ExpressionParser builds determines the order of evaluation. Example: 32 + centigrade/ratio Do a postorder traversal of the parse tree. Visit the left subtree , visit the right subtree , then visit the root .

10 .10 Example: Method parseExpression() First, we need to map Pascal token types to parse tree node types . Node types need to be language-independent. We ’ ll use a hash table. // Map relational operator tokens to node types. private static final HashMap < PascalTokenType , ICodeNodeType > REL_OPS_MAP = new HashMap < PascalTokenType , ICodeNodeType >(); static { REL_OPS_MAP.put ( EQUALS , EQ ); REL_OPS_MAP.put ( NOT_EQUALS , NE ); REL_OPS_MAP.put ( LESS_THAN , LT ); REL_OPS_MAP.put ( LESS_EQUALS , LE ); REL_OPS_MAP.put ( GREATER_THAN , GT ); REL_OPS_MAP.put ( GREATER_EQUALS , GE ); }; wci.frontend.pascal.parsers.ExpressionParser

11 .11 Method parseExpression () , cont ’ d private ICodeNode parseExpression (Token token) throws Exception { ICodeNode rootNode = parseSimpleExpression (token); token = currentToken (); TokenType tokenType = token.getType (); if ( REL_OPS.contains ( tokenType )) { ICodeNodeType nodeType = REL_OPS_MAP.get ( tokenType ); ICodeNode opNode = ICodeFactory.createICodeNode ( nodeType ); opNode.addChild ( rootNode ); token = nextToken (); // consume the operator opNode.addChild ( parseSimpleExpression (token)); rootNode = opNode ; } return rootNode ; } wci.frontend.pascal.parsers.ExpressionParser

12 .12 Printing Parse Trees Utility class ParseTreePrinter prints parse trees. Prints in an XML format. <COMPOUND line="11"> <ASSIGN line="12"> <VARIABLE id="alpha" level="0" /> <INTEGER_CONSTANT value="10" /> </ASSIGN> <ASSIGN line="13"> <VARIABLE id="beta" level="0" /> <INTEGER_CONSTANT value="20" /> </ASSIGN> </COMPOUND>

13 .Pascal Syntax Checker I The - i compiler option prints the intermediate code: Add to the constructor of the main Pascal class: 13 java - classpath classes Pascal execute - i assignments.txt if (intermediate) { ParseTreePrinter treePrinter = new ParseTreePrinter ( System.out ); treePrinter.print ( iCode ); } Pascal

14 .Pascal Syntax Checker I , cont’d Demo (Chapter 5) For now, all we can parse are compound statements, assignment statements, and expressions. More syntax error handling. 14

15 .15 What Have We Accomplished So Far? A working scanner for Pascal. A set of Pascal token classes. Symbol table and intermediate code classes. A parser for Pascal compound and assignment statements and expressions. Generate parse trees. Syntax error handling. A messaging system with message producers and message listeners. Placeholder classes for the back end code generator and executor. So … we are ready to put all this stuff into action!

16 .16 Temporary Hacks for Now Only one symbol table in the stack. Variables are scalars (not records or arrays) but otherwise have no declared type. We haven ’ t parsed any Pascal declarations yet! We consider a variable to be “ declared ” (and we enter it into the symbol table) the first time it appears on the left-hand-side of an assignment statement (it ’ s the target of the assignment).

17 .17 A New Temporary Hack Today, we ’ re going to store runtime computed values into the symbol table. As attribute DATA_VALUE

18 .18 Quick Review of the Framework Executing compound statements, assignment statements, and expressions. Chapter 6

19 .19 The Statement Executor Class Class StatementExecutor is a subclass of Executor which is a subclass of Backend . Its execute() method interprets the parse tree whose root node is passed to it. The return value is either the value of a computed expression, or null.

20 .20 The Statement Executor Subclasses StatementExecutor itself has subclasses: CompoundExecutor AssignmentExecutor ExpressionExecutor The execute() method of each subclass also interprets the parse tree whose root node is passed to it. Note the dependency relationships among StatementExecutor and its subclasses.

21 .21 More Architectural Symmetry The statement executor classes in the back end are symmetrical with the statement parser classes in the front end.

22 .22 Runtime Error Handling Just as the front end has an error handler for syntax errors , the interpreter back end has an error handler for runtime errors . Similar flag() method. Here, run time means the time when the interpreter is executing the source program . Runtime error message format Error message Source line number where the error occurred

23 .23 Runtime Error Messages Here are the errors and their messages that our interpreter will be able to detect and flag at run time. public enum RuntimeErrorCode { UNINITIALIZED_VALUE(" Uninitialized value "), VALUE_RANGE(" Value out of range "), INVALID_CASE_EXPRESSION_VALUE(" Invalid CASE expression value "), DIVISION_BY_ZERO(" Division by zero "), INVALID_STANDARD_FUNCTION_ARGUMENT(" Invalid standard function argument "), INVALID_INPUT(" Invalid input "), STACK_OVERFLOW(" Runtime stack overflow "), UNIMPLEMENTED_FEATURE(" Unimplemented runtime feature "); ... }

24 .24 public Object execute ( ICodeNode node ) { ICodeNodeTypeImpl nodeType = ( ICodeNodeTypeImpl ) node .getType (); switch ( nodeType ) { case COMPOUND : { CompoundExecutor compoundExecutor = new CompoundExecutor (this); return compoundExecutor.execute (node); } case ASSIGN : { AssignmentExecutor assignmentExecutor = new AssignmentExecutor (this); return assignmentExecutor.execute (node); } ... } } Class StatementExecutor The node type tells which executor subclass to use. wci.backend.interpreter.executors.StatementExecutor The nodeType tells which executor subclass to use.

25 .25 public Object execute ( ICodeNode node ) { StatementExecutor statementExecutor = new StatementExecutor (this); ArrayList < ICodeNode > children = node .getChildren (); for ( ICodeNode child : children) { statementExecutor.execute (child); } return null; } Class CompoundExecutor Get the list of all the child nodes of the COMPOUND node. Then call statementExecutor.execute () on each child. wci.backend.interpreter.executors.CompoundExecutor

26 .26 public Object execute ( ICodeNode node ) { ArrayList < ICodeNode > children = node .getChildren (); ICodeNode variableNode = children.get (0); ICodeNode expressionNode = children.get (1); ExpressionExecutor expressionExecutor = new ExpressionExecutor (this); Object value = expressionExecutor.execute ( expressionNode ); SymTabEntry variableId = ( SymTabEntry ) variableNode.getAttribute (ID); variableId.setAttribute (DATA_VALUE, value); sendMessage (node, variableId.getName (), value); ++ executionCount ; return null; } Class AssignmentExecutor Temporary hack: Set the computed value into the symbol table. Send a message about the assignment. wci.backend.interpreter.executors.AssignmentExecutor

27 .27 The Assignment Message Very useful for debugging. Necessary for now since we don ’ t have any other way to generate runtime output. Message format Source line number Name of the variable Value of the expression

28 .28 Executing Expressions Recall that Pascal ’ s operator precedence rules are encoded in the structure of the parse tree. At run time , we do a postorder tree traversal. alpha + 3/(beta - gamma) + 5

29 .29 Class ExpressionExecutor , cont ’ d Does not do type checking. It ’ s the job of the language-specific front end to flag any type incompatibilities. Does not know the operator precedence rules. The front end must build the parse tree correctly. The executor simply does a post-order tree traversal .