CSc 453Compilers and Systems Software0 : AdministriviaDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergIntroductionContact InformationClass : 453 — Compilers and Systems SoftwareInstructor :Christian CollbergWWW : http://www.cs.arizona.edu/classes/cs453/fall09/index.htmlOffice : Gould-Simpson 758Office Hours : MF 10:30-11:30Phone : 621-6612Lectures : MF 9:00-10:15, F 9:00-9:50, GLDS 906Honor’s section : M 2:00-2:50, GLDS 942Course CommunicationHere are ways to communicate with me and the rest of the class:Email: [email protected] up for the class on d2l.arizona.edu.Teaching AssistantsPankhuriEmail: [email protected]: ?Office hours: Friday 4-5pm, Tuesday 4-5pm.Exam-schedule1The midterm exam is scheduled for Fri Oct 16. This maychange, so pay attention in class and check the web site.2The final exam is scheduled for Fri Dec 18, 8-10am.SyllabusYou are responsible for readingand understanding this syllabus.If you have any concerns or issuesabout the information in this documentyou should bring them up during thefirst week of class.Course DescriptionTopicsWe will...learn how compilers are constructed,learn how programming languages are designed,learn how to compile procedural and object-orientedlanguages,learn how interpreters work,learn how garbage collectors work,learn how debuggers work (if there’s time).SyllabuslexingThe Chomsky hierarchy,regular expressions,DFAs,scanner implementation.parsingContext-free grammars, BNF,parse trees,abstract syntax trees,Recursive Descent parsing.Syllabus. . .semantic analysisAttribute grammars,environments,type-checking.intermediate representationsstacks,tuples,trees,intermediate-code generation from abstractsyntax trees.Syllabus. . .code generationcontrol-flow graphs,code generation for arithmetic expressions,data-structure access, control-flow, andprocedure calls.code optimizationsurvey of techniques,peephole optimization.Syllabus. . .Advanced topics will be covered as time permits:code optimizationdata-flow analysis,common sub-expression elimination,inlining.object-orientationcompiling Java-like languages,run-time class templates,inheritance.Syllabus. . .garbage collectionreference counting,pointer-maps,mark-and-sweep.systems softwaredebuggers,profilers.Course WorkCourse Work (Subject to Change)Assignment 1 Lexical analysis.Tokenize the Luca language.input: Luca programoutput: Lexical error messages, sequence oftokens.Algorithm: Finite state automaton.Course Work (Subject to Change)Assignment 2 Syntactic AnalysisParse a subset of the Luca language.input: Sequence of tokens.output: Syntactic error messages, AST.Algorithm: recursive descent.Assignment 3 Semantic analysis.Perform type-checking for a subset of the Lucalanguage.input: Luca ASToutput: Semantic error messages,decorated tree.Algorithm: recursive attribute evaluation.Assignment 4 Interpretation, part I.Luca interpreter.input: Luca stack codeoutput: noneImplementation language: gcc.Algorithm: indirect threaded code.Assignment 5 Interpretation, part II.Extend the interpreter from assignment 4 tohandle procedures.input: Luca stack codeoutput: noneAlgorithm: any.Course ObjectivesCourse ObjectivesAt the end of the course you should be familiar the overalldesign of compilers.You should know how to build lexers, parsers, semanticanalyzers, code generators, interpreters, and runtime systems.Course MethodologyYou can expect to spend a lot of time outside class onimplementing a compiler.Each assignment builds on the previous ones — it’s impossibleto fall behind in this class and still pass it.The assignments are best done in pairs of two — you need towork on being a good collaborator and to organize your timeand work appropriately.Required extracurricular activitiesProgramming assignments.Working programming exercises on your own.Special materials required for the classNone.Assignment FormatAssignments will be mostly in the form of programmingproblems.You may work the assignments on any machine you want, butbefore you hand them inyou should test the code on lectura!The TA(s) will grade the assignments on lectura, and if theydon’t work there, he/she won’t debug them for you! Therecan be subtle problems with code that’s developed on aWindows machine, for example, when it is run on a Unixmachine. For example, the two systems use different newlinecharacters.Prerequisites, Required KnowledgePrerequisites: C SC 345, C SC 352, C SC 372 recommended.You need to be a competent programmer in aprocedural/object-oriented language, such as Java or C.Assessment SchemeTests, Quizzes, and AssignmentsThere will be1one mid-term test worth a total of 10%;2one comprehensive final exam, worth a total of 40%;3five assignments worth a total of 50%;Late AssignmentsAssignments handed in no more than 24 hours late will incur a10% penalty.Assignments handed in more than 24 but no more than 48hours late will incur a 20% penalty.Assignments handed more than 48 hours after the deadlinewill receive a grade of 0.Making up TestsYou cannot make up the midterm or final exam unless1you have notified the instructor in writing (email is fine) or byphone prior to the test that you will be absent, and2you receive permission from the instructor to take the test ata later date.CurvingAll grades (for exams assignments) will be curved up bythrowing away the highest grade in the class and scaling upsuch that the second highest grade is 100.The curving is done to adjust for particularly difficulttests/assignments, and to prevent an outlier from skewing thegrade distribution.You cannot, after scaling, receive more than 100 on any examor assignment.Grade AssignmentYou will fail the class if you get less than 50 (after curving) onthe final exam.Otherwise, a curved total grade of [90,100] gives you an A,[80,89] a B, [70,79] a C, [60,69] a D, and 59 and below an E.Incomplete work policyExcept under exceptional circumstances I will not assignincomplete grades.I decide what is an exceptional circumstance.Detailed Grading SchemeTo avoid any ambiguities, I have formalized the informal rulesgiven above.The rules below should be considered minimum requirementsto achieve a particular grade. The instructor reserves the rightto do additional adjustments, as necessary.Any contradictions, omissions, errors, or ambiguities in thegrading scheme will be resolved by the instructor.Any issues or concerns regarding the grading scheme shouldbe brought to the attention