small lecturenumber - hepage : Stages of Compilationsmall lecturenumber - hepage : Stages of Compilationsmall lecturenumber - hepage : Lexersmall lecturenumber - hepage : Tokenssmall lecturenumber - hepage : Lexingsmall lecturenumber - hepage : Parsingsmall lecturenumber - hepage : Parsingsmall lecturenumber - hepage : Assemblysmall lecturenumber - hepage : Interpretersmall lecturenumber - hepage : Designing a Programsmall lecturenumber - hepage : Requirementssmall lecturenumber - hepage : Designsmall lecturenumber - hepage : Structure Chartssmall lecturenumber - hepage : Example: student databasesmall lecturenumber - hepage : Top-down structure chartsmall lecturenumber - hepage : Top-down structure chartsmall lecturenumber - hepage : Choosing Objectssmall lecturenumber - hepage : Bottom-up-designsmall lecturenumber - hepage : Unit testingIntroduction to Programming IICompilers and DesignChris BrooksDepartment of Computer ScienceUniversity of San FranciscoDepartment of Computer Science — University of San Francisco – p.1/??6-2: Stages of Compilation•What are the stages of the compilation of a program?Department of Computer Science — University of San Francisco – p.2/??6-3: Stages of Compilation•What are the stages of the compilation of a program?•Lexing - separate source code into tokens.•Parsing - evaluate statements and generate assembly code•Assembly - transform assembly code into binary code.◦In Java, these are .class files.◦Java stops here and uses an interpreter to control runtimeexecution.•Other languages produce a single executable. This requires afourth stage:◦Linking - Multiple object files are merged into a singleexecutable.Department of Computer Science — University of San Francisco – p.3/??6-4: Lexer•The program can initially be seen as a really long string.◦Sequence of characters.•The first step is to break this string into a set of program’building blocks’◦Numbers, variables, keywords, operators, etc◦These building blocks are called tokens.Department of Computer Science — University of San Francisco – p.4/??6-5: Tokens•Tokens are the basic building blocks of a program.◦x1, 12345, =, for, while•Tokens have a value and a type.◦(’123’, Token.INTEGER), (’+’, Token.PLUSSIGN), (’x1’,Token.IDENTIFIER)•Tokens can be combined to produce statements.Department of Computer Science — University of San Francisco – p.5/??6-6: Lexing•The lexer reads an input stream from left to right and pulls offtokens as it identifies them.•Unrecognized tokens get the type ’Token.UNKNOWN’•Some tokens have one character and can be recognizedimmediately.◦+,-,=•Other tokens have multiple characters.•This means that the lexer must be able to recognize the end ofa token.◦variables, numbers, keywordsDepartment of Computer Science — University of San Francisco – p.6/??6-7: 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” isthe job of the parser.•This is what you’ll build in Project 2.Department of Computer Science — University of San Francisco – p.7/??6-8: Parsing•the parser does this by using a set of rules that describe legalstatements.◦expression: term◦expression: term (plus | minus) (term | expression)◦term: (number | variable)•These rules are referred to as a grammar•The parser finds a set of rules that match a sequence of inputtokens.◦This is called a parse◦This tells how to interpret the meaning of a statement.Department of Computer Science — University of San Francisco – p.8/??6-9: Assembly•In assembly, tokens or sets of tokens are replaced withbytecodes.•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 withDepartment of Computer Science — University of San Francisco – p.9/??6-10: Interpreter•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.10/??6-11: Designing a Program•Knowing the syntax of how to build a class is only thebeginning.•The bigger challenge is figuring out how to fit the piecestogether.•The software development process consists of the followingsteps:◦Establishing requirements◦Creating a design◦Implementing the design◦Testing•Usually, this is an iterative, repeated process.Department of Computer Science — University of San Francisco – p.11/??6-12: Requirements•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.Department of Computer Science — University of San Francisco – p.12/??6-13: Design•This is the ’how’ part of the program.•Specifies the classes that are needed and how they interact.•What methods are called, what data is returned.•Skipping this step can lead to serious, unpleasant bugs.•A good design should make implementation straightforward.Department of Computer Science — University of San Francisco – p.13/??6-14: Structure Charts•A structure chart is a helpful tool for doing design.•Helps to divide and conquer•Divide the problem into smaller pieces until you reach piecesthat can be tackled directly.•This is called top-down design.Department of Computer Science — University of San Francisco – p.14/??6-15: Example: student database•Let’s say we’ve been hired by USF to build an application fortracking students.•It should be able to do the following:◦Add new students to the database◦Delete a student from the database◦Enter a student’s test scores◦Print out the average of a student’s scores•These are our requirementsDepartment of Computer Science — University of San Francisco – p.15/??6-16: Top-down structure chart•main is at the top of the chart•Nodes below this represent portions of the program that arecalled.•Arrows indicate input and output of
View Full Document
Unlocking...