6 2 Stages of Compilation What are the stages of the compilation of a program Introduction to Programming II Compilers and Design Chris Brooks Department of Computer Science University of San Francisco Department of Computer Science University of San Francisco p 1 Department of Computer Science University of San Francisco p 2 6 4 Lexer 6 3 Stages of Compilation Lexing separate source code into tokens The program can initially be seen as a really long string Sequence of characters Parsing evaluate statements and generate assembly code The first step is to break this string into a set of program What are the stages of the compilation of a program Assembly transform assembly code into binary code In Java these are class files Java stops here and uses an interpreter to control runtime building blocks Numbers variables keywords operators etc These building blocks are called tokens execution Other languages produce a single executable This requires a fourth stage Linking Multiple object files are merged into a single executable Department of Computer Science University of San Francisco p 3 6 5 Tokens Department of Computer Science University of San Francisco p 4 6 6 Lexing Tokens are the basic building blocks of a program x1 12345 for while The lexer reads an input stream from left to right and pulls off Tokens have a value and a type 123 Token INTEGER Token PLUSSIGN x1 Unrecognized tokens get the type Token UNKNOWN Token IDENTIFIER Tokens can be combined to produce statements tokens as it identifies them Some tokens have one character and can be recognized immediately Other tokens have multiple characters This means that the lexer must be able to recognize the end of a token variables numbers keywords Department of Computer Science University of San Francisco p 5 Department of Computer Science University of San Francisco p 6 6 7 Parsing 6 8 Parsing The job of the lexer is just to break the input stream into tokens Doesn t figure out what a statement means Doesn t try to determine whether an expression is legal Determining whether a sequence of tokens makes sense is the job of the parser the parser does this by using a set of rules that describe legal statements expression term expression term plus minus term expression term number variable These rules are referred to as a grammar This is what you ll build in Project 2 The parser finds a set of rules that match a sequence of input tokens This is called a parse This tells how to interpret the meaning of a statement Department of Computer Science University of San Francisco p 7 6 9 Assembly Department of Computer Science University of San Francisco p 8 6 10 Interpreter In assembly tokens or sets of tokens are replaced with bytecodes This is the language that is used by the Java interpreter Lower level language closer to the machine level High level languages are easier for people to work with Java uses a separate program known as an interpreter The interpreter is responsible for Executing statements Keeping track of variables and their values Managing memory In project 2 we ll worry about this Department of Computer Science University of San Francisco p 9 6 11 Designing a Program Department of Computer Science University of San Francisco p 10 6 12 Requirements Knowing the syntax of how to build a class is only the beginning The bigger challenge is figuring out how to fit the pieces together The software development process consists of the following steps Establishing requirements Creating a design Implementing the design Testing Requirements indicate what a program is supposed to do Expressed as a functional specification What is the input like What must the output look like Are there other programs it must interact with How quickly must the program run Often this comes from a client Usually not as precise as you d like Usually this is an iterative repeated process Department of Computer Science University of San Francisco p 11 Department of Computer Science University of San Francisco p 12 6 13 Design 6 14 Structure Charts This is the how part of the program A structure chart is a helpful tool for doing design Specifies the classes that are needed and how they interact Helps to divide and conquer What methods are called what data is returned Divide the problem into smaller pieces until you reach pieces Skipping this step can lead to serious unpleasant bugs A good design should make implementation straightforward that can be tackled directly This is called top down design Department of Computer Science University of San Francisco p 13 6 15 Example student database Department of Computer Science University of San Francisco p 14 6 16 Top down structure chart Let s say we ve been hired by USF to build an application for tracking students main is at the top of the chart Nodes below this represent portions of the program that are It should be able to do the following Add new students to the database called Arrows indicate input and output of data Delete a student from the database Enter a student s test scores Nodes at the next level are then decomposed in the same way Print out the average of a student s scores Eventually we get to methods we know how to implement These are our requirements Department of Computer Science University of San Francisco p 15 6 17 Top down structure chart Department of Computer Science University of San Francisco p 16 6 18 Choosing Objects The structure chart indicates the calling sequence of the program Each object should have one well defined responsibility A common mistake is to cram too much into a single object or Serves as a template for the actual program method Annotate parameters as in out or in out Methods are typically 1 2 screens of code Objects called with methods on them are parameters too Before making a new class does what you need already exist Department of Computer Science University of San Francisco p 17 Department of Computer Science University of San Francisco p 18 6 19 Bottom up design 6 20 Unit testing To implement the program in our structure chart start at the leaves and work upward As you code each method you should test it in isolation Write a small program that calls this method with all expected Bottom level methods can be implemented directly Methods at the next level up are implemented in terms of those methods inputs Testing each method seems tedious but it s very important A simple bug missed at a lower level can be very difficult to find later on Eventually you make it back up
View Full Document
Unlocking...