Compilers

====== Course Description ====== A compiler translates a computer program from a high level language, such as C, Python or Java, to machine code, the internal representation in the computer. Compilation takes several steps. The first step is lexical analysis, to separate the program into "words". Syntactic analysis finds the structures. Code generation is often done in two steps, via an intermediate code to machine code. Often the code is improved through code optimization. The methods and tools from compiler design are useful for other forms of translation, for example from XML to a data structure. The course is taught in English (and the exams should be written in English too). In order to pass the course, you should pass the assignments (all of them) as well as the written exam. **Please make it your habit to visit this page frequently, since everything related to this course is put here (and the news section will be updated almost daily).** ====== News Section ====== * 15 Sep 2012 - The answers (and the exam paper) of your final year exam (second attempt) has been uploaded, see it [[http://amanj.me/wiki/doku.php?id=teaching:su:compilers&#previous_exams_and_solutions | here]] * 7 Jun 2012 - The answers (and the exam paper) of your final year exam (first attempt) has been uploaded, see it [[http://amanj.me/wiki/doku.php?id=teaching:su:compilers&#previous_exams_and_solutions | here]] * 24 May 2012 - The Annual Assessment (40%) is out, please see it [[http://amanj.me/wiki/doku.php?id=teaching:su:compilers:annual_assessment | here]] * 21 May 2012 - Last week's lecture notes have been uploaded * 19 May 2012 - Assignment 4 has been corrected, please see your results here: [[http://amanj.me/wiki/doku.php?id=teaching:su:compilers:results]] * 10 May 2012 - Assignment 4 is ready please see it [[http://amanj.me/wiki/doku.php?id=teaching:su:compilers&#assignments | here]] * 9 May 2012 - Uploaded the exam paper and the answers sheet * 24 Apr 2012 - Uploaded a set of examples on translating C to Assembly, [[http://amanj.me/wiki/doku.php?id=teaching:su:compilers&#examples | here]] * 27 Mar 2012 - Uploaded the 17th and 18th lecture notes * 7 Mar 2012 - Uploaded the 16th lecture notes, and a tutorial to get started with a compiler front-end * 29 Feb 2012 - Slightly updated the 15th lecture notes * 28 Feb 2012 - Assignment 3 is ready, please see it [[http://amanj.me/wiki/doku.php?id=teaching:su:compilers&#assignments | here]] * 28 Feb 2012 - The 14th and 15th lecture notes have been uploaded * 21 Feb 2012 - The 13th lecture notes have been uploaded * 17 Feb 2012 - Added the exam paper (and answers) + a complete front end of a simple compiler (under the links section) * 12 Feb 2012 - The 12th lecture notes have been uploaded * 24 Dec 2011 - The assignment 2 has been corrected, please come to my office to collect them, the degrees are published [[teaching:su:compilers:results|here]] * 13 Dec 2011 - The 9th, 10th and 11th lecture notes are ready * 6 Dec 2011 - The 8th and 7th lecture notes are ready * 3 Dec 2011 - Assignment 2 is ready, please see it [[http://amanj.me/wiki/doku.php?id=teaching:su:compilers&#assignments | here]] * 21 Nov 2011 - Added the lecture notes for the upcoming lecture (bottom-up parsing) and an example of YACC specification * 13 Nov 2011 - For the students who have not submitted the first assignment yet, please do so as soon as possible. * 13 Nov 2011 - The assignments have been corrected, please come to my office tomorrow to collect them. NOTE: if you have solved it in group then the whole group should come together. * 1 Nov 2011 - Added the lecture notes for the upcoming lecture (top-down parsing) * 27 Oct 2011 - Added an example of converting RE to DFA, [[http://amanj.me/wiki/doku.php?id=teaching:su:compilers#examples | here]] * 23 Oct 2011 - Added an example of Lexical Analysis, [[http://amanj.me/wiki/doku.php?id=teaching:su:compilers#examples | here]] * 19 Oct 2011 - Added a link to the lex specification of ANSI C grammar, [[http://amanj.me/wiki/doku.php?id=teaching:su:compilers&#links | here]] * 12 Oct 2011 - Assignment 1 is ready, please see it [[http://amanj.me/wiki/doku.php?id=teaching:su:compilers&#assignments | here]] * 12 Oct 2011 - Slightly updated the third lecture * 5 Oct 2011 - Updated the second lecture (corrected the errors) * 27 Sep 2011 - Added the reading list and the first four lecture notes * 27 Aug 2011 - The page went alive. ====== Syllabus and Lectures ====== **This course is highly influenced by the ([[https://studentportalen.uu.se/portal/portal/uusp/student/student-course?uusp.portalpage=true&entityId=84473&toolMode=studentUse | Compiler Design I]], 1DL320) from Uppsala University** - [[http://www.amanj.me/lectures/su/compilers/01-TheIntroductoryLecture.pdf | Introduction]] - [[http://www.amanj.me/lectures/su/compilers/02-Overview.pdf | Overview]] - [[http://www.amanj.me/lectures/su/compilers/03-LexicalAnalysis.pdf | Lexical Analysis]] and [[http://www.amanj.me/lectures/su/compilers/lex-example.l | an Example of LEX Specification]] - [[http://www.amanj.me/lectures/su/compilers/04-ContextFreeGrammars.pdf | Context-Free Grammars]] - [[http://www.amanj.me/lectures/su/compilers/05-Top-DownParsing.pdf | Top-Down Parsing]] - [[http://www.amanj.me/lectures/su/compilers/06-Bottom-UpParsing.pdf | Bottom-Up Parsing]] and [[http://www.amanj.me/lectures/su/compilers/yacc-example.y |an Example of Bison (or YACC) Specification]] - [[http://www.amanj.me/lectures/su/compilers/07-AttributeGrammars.pdf | Attribute Grammars]] - [[http://www.amanj.me/lectures/su/compilers/08-AbstractSyntaxTrees.pdf | Abstract Syntax Trees]] - [[http://www.amanj.me/lectures/su/compilers/09-SemanticAnalysis.pdf | Semantic Analysis]] - [[http://www.amanj.me/lectures/su/compilers/10-TargetMachine.pdf | Target Machine]] - [[http://www.amanj.me/lectures/su/compilers/11-RecursionAndCallStacks.pdf | Recursion and Call Stacks]] - [[http://www.amanj.me/lectures/su/compilers/12-IntermediateRepresentation.pdf | Intermediate Representation]] - [[http://www.amanj.me/lectures/su/compilers/13-AST-to-RTL-Basics.pdf | AST to RTL Translation: Basics]] - [[http://www.amanj.me/lectures/su/compilers/14-DataLayout.pdf | Data Layout]] - [[http://www.amanj.me/lectures/su/compilers/15-AST-to-RTL-Data.pdf | AST to RTL Translation: Data]] - [[http://www.amanj.me/lectures/su/compilers/16-RTL-toMachineCode.pdf | Translating RTL to Machine Code]]. [[http://www.amanj.me/lectures/su/compilers/Tutorial-01.pdf | A tutorial for a compiler front-end]] - [[http://www.amanj.me/lectures/su/compilers/17-Runtime.pdf | Runtime Environment]] - [[http://www.amanj.me/lectures/su/compilers/18-BB, CFG, Liveness, GraphColoring.pdf | Basic Blocks, CFG, Liveness, Graph-Coloring Register Allocation]] - [[http://www.amanj.me/lectures/su/compilers/20-InsideTheJavaCompilerAndVM.pdf | Guest Lecture - Inside the Java Compiler and Java Virtual Machine]] - [[http://www.amanj.me/lectures/su/compilers/19-PluggableTypeCheckers.pdf | Pluggable Type Checkers]] ====== Reading List ====== (Note: The reading list is for the **Purple Dragon Book** only, I can put other books' reading lists if you are interested) **The Purple Dragon Book:** ^ Chapters ^ What ^ | Ch1, Ch2 | Overview | | Ch3.1-Ch3.8 | Lexical analysis. 3.2, 3.5, and 3.8 not in detail. | | Ch4-Ch4.6,Ch4.8 | Syntactic analysis. LL(1), LR(0), SLR in detail. LR(1) and LALR(1) not in detail. Error recovery can be skipped. | | Ch5-Ch5.3 | Overview of attribute grammars. Constructing Syntax trees. | | Ch6.5-Ch6.5.3 | Type checking. | | Ch7-Ch7.2,Ch7.4 | Runtime environment. 7.4 not in detail. | | Ch6, not Ch6.7 | Intermediate code generation. Concentrate on the semantics of the programming language constructs and disregard the book's emphasis on doing the translation during parsing: the translation is instead to be done by traversing an explicit syntax tree. | | Ch8-Ch8.4,Ch8.7,Ch8.8 | Code generation. | ====== Assignments ====== * [[http://www.amanj.me/lectures/su/compilers/Assignment1.pdf | Assignment 1]] * [[http://www.amanj.me/lectures/su/compilers/Assignment2.pdf | Assignment 2]] * [[http://www.amanj.me/lectures/su/compilers/Assignment3.pdf | Assignment 3]] * [[http://www.amanj.me/lectures/su/compilers/Assignment4.pdf | Assignment 4]] ====== The Results of the Assignments ====== Can be found [[teaching:su:compilers:results | here]] ====== The Annual Assessment (40%) ====== Can be found [[teaching:su:compilers:annual_assessment | here ]] ====== Formal Description ====== The formal description of the course can be found [[http://www.amanj.me/lectures/su/compilers/coursebook-compilers.pdf | here]] ====== Previous Exams (and Solutions) ====== * First term exam (2011-2012) 1 Feb 2012: the [[http://www.amanj.me/lectures/su/compilers/midYear.pdf | exam paper]] and the [[http://www.amanj.me/lectures/su/compilers/midYear-answers.pdf | answers]] * Second term exam (2011-2012) 5 May 2012: the [[http://www.amanj.me/lectures/su/compilers/secondTerm.pdf | exam paper]] and the [[http://www.amanj.me/lectures/su/compilers/secondTerm-Answers.pdf | answers]] * Final exam - first attempt (2011-2012) 7 Jun 2012: the [[http://www.amanj.me/lectures/su/compilers/finalExam1.pdf | exam paper]] and the [[http://www.amanj.me/lectures/su/compilers/finalExam1-answers.pdf | answers]] * Final exam - second attempt (2011-2012) 15 Sep 2012: the [[http://www.amanj.me/lectures/su/compilers/finalExam2.pdf | exam paper]] and the [[http://www.amanj.me/lectures/su/compilers/finalExam2-answers.pdf | answers]] ====== Links ====== * Enjoy [[http://en.wikipedia.org/wiki/Hacker_(programmer_subculture) | hacking]] the ANSI C compiler, the lex specification of C grammar [[http://www.lysator.liu.se/c/ANSI-C-grammar-l.html | here]] * A complete front-end of a simple compiler, from the purple dragon book: [[http://dragonbook.stanford.edu/dragon-front-source.tar | here]] ====== Examples ====== * [[http://www.amanj.me/lectures/su/compilers/LexicalAnalysis.pdf | Lexical Analysis]] * [[http://www.amanj.me/lectures/su/compilers/RE2DFA.pdf | An example on converting RE to DFA]] * [[http://www.amanj.me/lectures/su/compilers/AssemblyExamples.zip | A set of examples on translating C to Assembly]] ====== Literature ====== * Purple Dragon Book (Aho, Lam, Sethi, Ullman, "Compilers principles, techniques and tools", 2007 edition), [[http://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811/ref=dp_ob_title_bk/183-5167380-2429712 | link]] * Red Dragon Book (Aho, Sethi, Ullman, "Compilers principles, techniques and tools", 1986 edition), [[http://www.amazon.com/Compilers-Principles-Techniques-Alfred-Aho/dp/0201100886 | link]] * Appel's Tiger Book (Andrew W. Appel, "Modern Compiler Implementation in C", 1998 edition) [[http://www.cs.princeton.edu/~appel/modern/ | link]] ====== Teaching Staff ====== * The course is given by [[http://www.amanj.me | Amanj Sherwany]], you can click on the name for more information (including contact information and office hours).