编译器设计08

1 .CS 153: Concepts of Compiler Design September 13 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 control statements, and generating parse trees. Chapter 7

3 .3 CASE Statement Example: CASE i+1 OF 1 : j := i ; 4 : j := 4* i ; 5 , 2 , 3 : j := 523* i ; END Note that Pascal ’ s CASE statement does not use BREAK statements.

4 .4 CASE Statement, cont ’ d Example: CASE i+1 OF 1 : j := i ; 4 : j := 4* i ; 5 , 2 , 3 : j := 523* i ; END

5 .5 Pascal Syntax Checker II: CASE Demo. java - classpath classes Pascal compile - i case.txt java - classpath classes Pascal compile - i caseerrors.txt

6 .6 Top Down Recursive Descent Parsing The term is very descriptive of how the parser works. Start by parsing the topmost source language construct. For now it ’ s a statement . Later, it will be the program.

7 .7 Top Down Recursive Descent Parsing “ Drill down ” (descend) by parsing the sub-constructs. statement →assignment statement → expression →variable → etc . Use recursion on the way down. statement → WHILE statement → statement → etc .

8 .8 Top Down Recursive Descent Parsing, cont ’ d This is the technique for hand-coded parsers. Very easy to understand and write. The source language grammar is encoded in the structure of the parser code. Close correspondence between the parser code and the syntax diagrams. Disadvantages Can be tedious coding. Ad hoc error handling. Big and slow!

9 .9 Top Down Recursive Descent Parsing, cont ’ d Bottom-up parsers can be smaller and faster. Error handling can still be tricky. To be covered later this semester.

10 .10 Syntax and Semantics Syntax refers to the grammar rules of a source language. The rules prescribe the proper form of its programs. Rules can be described by syntax diagrams. Syntax checking: Does this sequence of tokens follow the syntax rules? Chapter 8

11 .11 Syntax and Semantics , cont’d Semantics refers to the meaning of the token sequences according to the source language. Example: Certain sequences of tokens constitute an IF statement according to the syntax rules. The semantics of the statement determine How the interpreter will execute the statement, or How the compiler will generate object code for the statement.

12 .12 Syntax and Semantics, cont ’ d Semantic actions by the front end parser: Building symbol tables . Type checking (which we’ll do later). Building proper parse trees . The parse trees encode type checking and operator precedence in their structures. Semantic actions by the back end : Interpreter: The executor runs the program . Compiler: The code generator emits object code .

13 .13 Interpreter Design Recall the design of our interpreter in the back end:

14 .14 Control Statement Executor Classes New StatementExecutor subclasses: LoopExecutor IfExecutor SelectExecutor The execute() method of each of these new subclasses executes the parse tree whose root node is passed to it. Each returns null. Only the execute() method of ExpressionExecutor returns a value.

15 .15 Executing a LOOP Parse Tree Pascal REPEAT loop Pascal WHILE loop Pascal FOR loop Note that we have the flexibility in the LOOP tree to have the TEST child be a middle child.

16 .15 Executing a LOOP Parse Tree Pascal REPEAT loop Pascal WHILE loop Pascal FOR loop Note that we have the flexibility in the LOOP tree to have the TEST child be a middle child.

17 .17 boolean exitLoop = false ; ICodeNode exprNode = null; ArrayList< ICodeNode > loopChildren = node.getChildren () ; ExpressionExecutor expressionExecutor = new ExpressionExecutor (this); StatementExecutor statementExecutor = new StatementExecutor (this); while ( ! exitLoop ) { ++ executionCount ; // count the loop statement itself for ( ICodeNode child : loopChildren ) { ICodeNodeTypeImpl childType = ( ICodeNodeTypeImpl ) child.getType (); if ( childType == TEST ) { if ( exprNode == null) { exprNode = child.getChildren ().get(0); } exitLoop = (Boolean) expressionExecutor.execute ( exprNode ); } else { statementExecutor.execute (child); } if ( exitLoop ) break; } } Executing a LOOP Parse Tree , cont’d Keep looping until exitLoop becomes true. Execute all the subtrees. TEST node: Evaluate the boolean expression and set exitLoop to its value. Statement subtree: Execute it. Break out of the for loop if exitLoop is true. wci.backend.interpreter.executors.LoopExecutor

18 .18 Simple Interpreter II: Loops Demos java – classpath classes Pascal execute repeat.txt java – classpath classes Pascal execute while.txt java – classpath classes Pascal execute for.txt

19 .19 Executing an IF Parse Tree Evaluate the first child ’ s expression subtree . If the expression value is true ... Execute the second child ’ s statement subtree. If the expression value is false … If there is a third child statement subtree, then execute it. If there isn ’ t a third child subtree, then we ’ re done with this tree.

20 .20 public Object execute( ICodeNode node) { ArrayList < ICodeNode > children = node.getChildren (); ICodeNode exprNode = children.get (0); ICodeNode thenStmtNode = children.get (1); ICodeNode elseStmtNode = children.size () > 2 ? children.get (2) : null; ExpressionExecutor expressionExecutor = new ExpressionExecutor (this); StatementExecutor statementExecutor = new StatementExecutor (this); boolean b = (Boolean) expressionExecutor.execute ( exprNode ); if ( b ) { statementExecutor.execute ( thenStmtNode ); } else if ( elseStmtNode != null) { statementExecutor.execute ( elseStmtNode ); } ++ executionCount ; // count the IF statement itself return null; } Executing an IF Parse Tree , cont’d Get the IF node ’ s two or three children. Execute the boolean expression to determine which statement subtree child to execute next. wci.backend.interpreter.executors.IfExecutor

21 .21 Simple Interpreter II: IF Demo java – classpath classes Pascal execute if.txt

22 .22 Executing a SELECT Parse Tree Evaluate the first child expression subtree to get the selection value . Examine each SELECT BRANCH subtree. Look for the selection value in the SELECT CONSTANTS list of each SELECT BRANCH. If there is a match, then execute the SELECT BRANCH ’ s statement subtree. CASE i+1 OF 1: j := i ; 4: j := 4* i ; 5, 2, 3: j := 523* i ; END Is this a good way to do it?

23 .23 Executing a SELECT Parse Tree , cont’d Why is searching for a matching selection value among all the SELECT BRANCHes bad? It ’ s inefficient. Selection values that appear earlier in the parse tree are found faster. The Pascal programmer should not have to consider the order of the selection values.

24 .24 Executing a SELECT Parse Tree , cont’d A better solution: For each SELECT tree, create a jump table implemented as a hash table. Build the table from the SELECT parse tree. Each jump table entry contains: Key: A constant selection value . Value: The root node of the corresponding statement subtree .

25 .25 Executing a SELECT Parse Tree , cont’d During execution, the computed selection value is the key that extracts the corresponding statement subtree to execute.

26 .26 SELECT Jump Table Key: constant selection value Value: root node of the corresponding statement 1 1 1 2 1 3 1 4 1 5 CASE i+1 OF 1: j := i ; 4: j := 4* i ; 5, 2, 3: j := 523* i ; END Jump table This is an example of optimization for faster execution .

27 .27 Multiple CASE Statements If a Pascal source program contains multiple CASE statements, there will be multiple SELECT parse trees. Create a global jump cache , a hash table of jump tables . Each jump cache entry contains: Key : The SELECT node of a SELECT parse tree. Value: The jump table created for that SELECT parse tree.

28 .28 Jump Cache of Jump Tables Key: SELECT node Value: Corresponding jump table 1 1 1 1 1 1 2 1 3 1 4 1 5 1 1 1 2 1 1 1 2 1 3 Jump cache Jump tables SELECT parse trees

29 .29 Class SelectExecutor The global jump cache , which contains a jump table for each SELECT tree in the Pascal source program. // Jump cache : entry key is a SELECT node, // entry value is the jump table. // Jump table: entry key is a selection value, // entry value is the branch statement root node. private static HashMap < ICodeNode , HashMap <Object, ICodeNode > > jumpCache = new HashMap < ICodeNode , HashMap <Object, ICodeNode > >(); wci.backend.interpreter.executors.SelectExecutor