[Template fetch failed for http://spivey.oriel.ox.ac.uk/corner/Template:Sitenotice?action=render: HTTP 404]

Compilers: Difference between revisions

From Compilers
Jump to navigation Jump to search
(Removed redirect to corner:Compilers)
Tags: Removed redirect Manual revert
 
(18 intermediate revisions by the same user not shown)
Line 1: Line 1:
[[Image:optree.png|thumb|300px|right|An operator tree for @x := a[i]@]]
{{DISPLAYTITLE:Compilers (The Farewell Tour)}}[[Image:optree.png|thumb|300px|right|An operator tree for @x := a[i]@]]
This course will show you '''one way''' to build a compiler for an ordinary programming language (like Pascal or C) that generates reasonably good code for a modern machine (the ARM).
''This part of Spivey's Corner contains materials for a course on Compilers.  Some pages will contain course material, and I will protect those pages from editing, so that everyone can see the material as I presented it.  Each protected page will have an associated discussion page, and you are welcome to add comments there, or to make corrections or additions to any of the other pages.  To make edits, you will need to create an account for yourself, but anyone with an Oxford e-mail address is welcome to participate, in a way consistent with the [[project:code of conduct|code of conduct]].''


To make the task manageable, we will write the compiler in a functional style in quite a high-level language (OCaml), and we will use power tools (Lex and Yacc) to automate the easy part -- analysing the syntax of the input language.  The designs we create can also be used to implement hand-crafted compilers without the benefit of these power tools.
{{Dropcap|T|his course}} will show you {{Doc|compilers|book|'''one way'''}} to build a compiler for an ordinary programming language (like Pascal or C) that generates reasonably good code for a modern machine (the ARM).  To make the task manageable, we will write the compiler in a functional style in quite a high-level language (OCaml), and we will use power tools (Lex and Yacc) to automate the easy part -- analysing the syntax of the input language.  The designs we create can also be used to implement hand-crafted compilers without the benefit of these power tools.


Our compiler will be organised for clarity, being structured as the functional composition of many small passes, each carrying out one part of the compiling task.  This organisation allows us to focus on the representations of the program being compiled that are handed from one pass to the next, understanding each pass in terms of the transformation it must achieve.
Our compiler will be organised for clarity, being structured as the functional composition of many small passes, each carrying out one part of the compiling task.  This organisation allows us to focus on the representations of the program being compiled that are handed from one pass to the next, understanding each pass in terms of the transformation it must achieve. The course doesn't aim to be a survey of all the ways the task might be done, though occasionally we will pause to mention other choices we might have made.  Because we will be building a big-ish program, we will naturally want to deploy some of the technical means to deal with large-scale software development: a version control system to keep track of the changes we make, automated building (using Make), and automated testing against a stored corpus of test cases.
 
The course doesn't aim to be a survey of all the ways the task might be done, though occasionally we will pause to mention other choices we might have made.  Because we will be building a big-ish program, we will naturally want to deploy some of the technical means to deal with large-scale software development: a version control system to keep track of the changes we make, automated building (using Make), and automated testing against a stored corpus of test cases.


The course will bring us into contact with some of the major theoretical and practical ideas of Computer Science.  On the theoretical side, we will be using regular expressions and context free grammars to describe the structure of source programs (though relying on automated tools to construct recognisers for us), and we will find a use for many algorithms and data structures.  Practically speaking, we will need to deal with the target machine at the level of assembly language, using registers, addressing modes and calling conventions to make a correct and efficient translation of source language constructs.
The course will bring us into contact with some of the major theoretical and practical ideas of Computer Science.  On the theoretical side, we will be using regular expressions and context free grammars to describe the structure of source programs (though relying on automated tools to construct recognisers for us), and we will find a use for many algorithms and data structures.  Practically speaking, we will need to deal with the target machine at the level of assembly language, using registers, addressing modes and calling conventions to make a correct and efficient translation of source language constructs.


==The coursebook==
==Course materials==
Everything you need to follow the course is contained in one handy {{Doc|compilers|book|coursebook}}, including
* Notes for the lectures, instructions for the practicals, and problems for the tutorials are collected in a single '{{Doc|compilers|book|coursebook}}'. There are appendices giving extra information about the OCaml language we will use to write compilers, and the Keiko and ARM machines we will use as targets.
* Notes for the lectures.
* A separate [[course outline]] lists the subject of each lecture.
* Problems for the classes.
* For convenience, the tutorial exercises are provided in a separate document on [[Problem sheets|another page]], with some advice about what problems are appropriate for each tutorial.
* Instructions for the lab exercises.
* Arrangements for the lab sessions are also set out on [[Laboratory exercises|their own page]].
* Appendices containing extra information about the OCaml language and the Keiko and ARM machines.
* There is a page of [[frequently asked questions]] that contains the answers to all your questions (or will do so shortly after you ask them), and a [[glossary]] with definitions of terms used in the course.  Feel free to suggest new entries!
* Listings of relevant parts of the compilers used for the lab exercises.
* The course culminates in a practical assignment done over Christmas.  A [[Christmas assignment|separate page]] has the instructions and some partial solutions to assignments set in the past, plus practical hints for carrying out the task and presenting the results.
 
* A [[reading list]] suggests books that might be helpful, and background reading for the Christmas assignment.
==The lectures==
 
* A [[course outline]] with the subject of each lecture.
 
==The tutorials and labs==
As a Core course, Compilers will be supported by tutorials organised by colleges.  There will also be a sequence of four lab exercises, leading up to a practical assessment carried out during the Christmas vacation.
* The tutorial exercises are contained in the coursebook, and for convenience they are also accessible as a separate document on [[Problem sheets|another page]], with some advice about what problems are appropriate for each tutorial.
* Instructions for the labs are also contained in the coursebook, and practical arrangements are set out on [[Laboratory exercises|their own page]].
 
==The Christmas assignment==
To encourage participants to develop practical skills, and to give them an opportunity to demonstrate them, the course culminates in a practical assignment done over the Chritmas vacation.  [[Christmas assignment|Another page]] has a sample write-up, the assignments set in previous years, and Mike's solutions to each of them.
 
==The burning questions==
 
There is a page of [[frequently asked questions]] that contains the answers to all your questions (or will do so shortly after you ask them).
 
* In addition, a [[glossary]] gives definitions of terms used in the course.  Feel free to suggest new entries!
 
==The reading list==
* The {{Doc|compilers|book|coursebook}} contains most of what you need to know to follow the course, including notes on the lectures, instructions for the practical exercises, and appendices describing the instruction sets of the Keiko machine and the ARM, together with listings of relevant modules of the lab compilers.
Some other books:
* The book ''Modern Compiler Implementation in ML'' by Andrew Appel (Cambridge) is closest to this course, except that the ML dialect he uses is Standard ML, and not OCaml.  There are two translations of the book that use respectively Java and C as the implementation language, but in each case something is lost in the translation.
* The classic text ''Compilers: principles, techniques and tools'' by Aho, Hopcroft and Ullman (Addison–Wesley).  Either the original 1977 edition or the second edition of 2006 (with Monica Lam) will do.  ''I've been referring to the 1977 edition, but as far as I can see, little of the common material has changed in the second edition.''
* Although it differs in many details, Richard Bornat's classic {{Doc|compilers|bornat|book}} is close to the course in spirit.  I recommend it for supplementary reading.
* In later parts of the course, you might like to look at the {{Doc|compilers|ARMv6|reference manual}} for the ARM architecture.  (This edition is not the latest, but it is the first to describe the ARMv6 instruction set we shall target.  Later editions have become steadily more complicated as they describe more different variants of the ARM.)
* The [https://academic.oup.com/comjnl/article-pdf/5/4/349/899594/050349.pdf Revised Report on Algol 60] is the first significant language description to use context free grammars to define the syntax of a programming language.  Knuth's paper [https://www.cs.virginia.edu/~asb/teaching/cs415-fall05/docs/algol-3.pdf The remaining trouble spots in Algol 60] fixes the very few problems in the Revised Report.
* For tutorial material on OCaml, there is a copy online of the O'Reilly book [https://realworldocaml.org Real World OCaml] by Yaron Minsky, Anil Madhavapeddy and Jason Hickey.

Latest revision as of 20:44, 7 March 2024

An operator tree for x := a[i]

This part of Spivey's Corner contains materials for a course on Compilers. Some pages will contain course material, and I will protect those pages from editing, so that everyone can see the material as I presented it. Each protected page will have an associated discussion page, and you are welcome to add comments there, or to make corrections or additions to any of the other pages. To make edits, you will need to create an account for yourself, but anyone with an Oxford e-mail address is welcome to participate, in a way consistent with the code of conduct.

This course will show you one way to build a compiler for an ordinary programming language (like Pascal or C) that generates reasonably good code for a modern machine (the ARM). To make the task manageable, we will write the compiler in a functional style in quite a high-level language (OCaml), and we will use power tools (Lex and Yacc) to automate the easy part – analysing the syntax of the input language. The designs we create can also be used to implement hand-crafted compilers without the benefit of these power tools.

Our compiler will be organised for clarity, being structured as the functional composition of many small passes, each carrying out one part of the compiling task. This organisation allows us to focus on the representations of the program being compiled that are handed from one pass to the next, understanding each pass in terms of the transformation it must achieve. The course doesn't aim to be a survey of all the ways the task might be done, though occasionally we will pause to mention other choices we might have made. Because we will be building a big-ish program, we will naturally want to deploy some of the technical means to deal with large-scale software development: a version control system to keep track of the changes we make, automated building (using Make), and automated testing against a stored corpus of test cases.

The course will bring us into contact with some of the major theoretical and practical ideas of Computer Science. On the theoretical side, we will be using regular expressions and context free grammars to describe the structure of source programs (though relying on automated tools to construct recognisers for us), and we will find a use for many algorithms and data structures. Practically speaking, we will need to deal with the target machine at the level of assembly language, using registers, addressing modes and calling conventions to make a correct and efficient translation of source language constructs.

Course materials

  • Notes for the lectures, instructions for the practicals, and problems for the tutorials are collected in a single 'coursebook'. There are appendices giving extra information about the OCaml language we will use to write compilers, and the Keiko and ARM machines we will use as targets.
  • A separate course outline lists the subject of each lecture.
  • For convenience, the tutorial exercises are provided in a separate document on another page, with some advice about what problems are appropriate for each tutorial.
  • Arrangements for the lab sessions are also set out on their own page.
  • There is a page of frequently asked questions that contains the answers to all your questions (or will do so shortly after you ask them), and a glossary with definitions of terms used in the course. Feel free to suggest new entries!
  • The course culminates in a practical assignment done over Christmas. A separate page has the instructions and some partial solutions to assignments set in the past, plus practical hints for carrying out the task and presenting the results.
  • A reading list suggests books that might be helpful, and background reading for the Christmas assignment.
Retrieved from "https://spivey.oriel.ox.ac.uk/cxwiki/index.php?title=Compilers&oldid=574"