- 微博 QQ QQ空间 贴吧
1 .CS 153: Concepts of Compiler Design August 23 Class Meeting Department of Computer Science San Jose State University Fall 2018 Instructor: Ron Mak www.cs.sjsu.edu/~mak 1
2 .Reminder: By Sunday, August 26 Form teams. Email me your team information. team name team members and email addresses 2
3 .3 Conceptual Design (Version 1) Parser Controls the translation process. Repeatedly asks the scanner for the next token . Scanner Repeatedly reads characters from the source to construct tokens for the parser. Token A source language element identifier (name) number special symbol (+ - * / = etc.) reserved word Also reads from the source Source The source program
4 .4 Conceptual Design (Version 2) We can architect a compiler with three major parts:
5 .5 Major Parts of a Compiler Front end Parser, Scanner, Source, Token Intermediate tier Intermediate code ( icode ) “ Predigested ” form of the source code that the back end can process efficiently. Example: parse trees AKA intermediate representation (IR) Symbol table ( symtab ) Stores information about the symbols (such as the identifiers) contained in the source program. Back end Code generator Processes the icode and the symtab in order to generate the object code. Only the front end needs to be source language-specific . The intermediate tier and the back end can be language-independent!
6 .6 What Else Can Compilers Do? Compilers allow you to program in a high-level language and think about your algorithms, not about machine architecture. Compilers provide language portability . You can run your C++ and Java programs on different machines because their compilers enforce language standards .
7 .7 What Else Can Compilers Do ? cont’d Compilers can optimize and improve the execution of your programs. Optimize the object code for speed . Optimize the object code for size . Optimize the object code for power consumption .
8 .8 What about Interpreters? An interpreter executes a source program instead of generating object code. It executes a source program using the intermediate code and the symbol table.
9 .9 Conceptual Design (Version 3) A compiler and an interpreter can both use the same front end and intermediate tier .
10 .10 Comparing Compilers and Interpreters A compiler generates object code, but an interpreter does not. Executing the source program from object code can be several orders of magnitude faster than executing the program by interpreting the intermediate code and the symbol table. But an interpreter requires less effort to get a source program to execute faster turnaround time Demo
11 .11 Comparing Compilers and Interpreters , cont’d An interpreter maintains control of the source program ’ s execution. Interpreters often come with interactive source-level debuggers that allow you to refer to source program elements, such as variable names. AKA symbolic debugger
12 .12 Therefore ... Interpreters are useful during program development. Compilers are useful to run released programs in a production environment. In this course, you will ... Modify an interpreter for the Pascal language. Develop a compiler for a language of your choice. You can invent your own programming language! Comparing Compilers and Interpreters , cont’d
13 .13 Take roll!
14 .14 Key Steps for Success Whenever you develop a complex program such as a compiler or an interpreter, key first steps for success are: Design and implement a proper framework . Develop initial components that are well-integrated with the framework and with each other. Test the framework and the component integration by running simple end-to-end tests. Early component integration is critical , even if the initial components are greatly simplified and don ’ t do very much.
15 .15 Key Steps for Success, cont ’ d Test your framework and components. Get them working together as early as possible . The framework and the initial components then form the basis upon which you can do further development. You should always be building on code that already works.
16 .16 Three Java Packages TO : UML package and class diagrams. Package Class FROM :
17 .17 Front End Class Relationships + public - private # protected ~ package “ has a ” transient relationship abstract class These four framework classes should be source language-independent . class field
18 .18 Current Character vs. Next Character Suppose the source line contains ABCDE and we ’ ve already read the first character. currentChar() A nextChar() B nextChar() C nextChar() D currentChar() D currentChar() D nextChar() E nextChar() eol
19 .19 Messages from the Front End The Parser generates messages. Syntax error messages Parser summary number of source lines parsed number of syntax errors total parsing time The Source generates messages. For each source line: line number contents of the line
20 .20 Front End Messages, cont ’ d We want the message producers ( Parser and Source ) to be loosely-coupled from the message listeners . The producers shouldn’t care who listens to their messages. The producers shouldn’t care what the listeners do with the messages. The listeners should have the flexibility to do whatever they want with the messages.
21 .21 Front End Messages, cont ’ d Producers implement the MessageProducer interface. Listeners implement the MessageListener interface. A listener registers its interest in the messages from a producer. Whenever a producer generates a message, it “ sends ” the message to all of its registered listeners.
22 .22 Front End Messages, cont ’ d A message producer can delegate message handling to a MessageHandler . This is the Observer Design Pattern .
23 .23 Two Message Types SOURCE_LINE message the source line number text of the source line PARSER_SUMMARY message number of source lines read number of syntax errors total parsing time By convention , the message producers and the message listeners agree on the format and content of the messages.
24 .24 Good Framework Symmetry
25 .Detailed UML Diagrams From the textbook: Front end fields and methods The abstract parser class The abstract scanner class The token class The source class Message implementation 25 Why should the parser and scanner classes be abstract?
26 .26 Front End Fields and Methods “ subclass of ” or “is a” abstract method
27 .27 The Abstract Parser Class Fields iCode and symTab refer to the intermediate code and the symbol table. Field scanner refers to the scanner. Abstract parse() and getErrorCount () methods. To be implemented by language-specific parser subclasses. “ Convenience methods ” currentToken () and nextToken () simply call the currentToken () and nextToken () methods of Scanner .
28 .28 The Abstract Scanner Class Private field currentToken refers to the current token, which protected method currentToken () returns. Method nextToken () calls abstract method extractToken () . To be implemented by language-specific scanner subclasses. Convenience methods currentChar () and nextChar () call the corresponding methods of Source .
29 .29 The Token Class Field text is the string that comprises the token. Field value is for tokens that have a value, such as a number. Field type is the token type. Fields lineNum and position tell where the token is in the source file. Default method extract() will be overridden by language-specific token subclasses. Convenience methods currentChar () , nextChar () , and peekChar () call the corresponding methods of the Source class.