CPSC411: COMPILER CONSTRUCTION I
(Winter 2018, 9:30-10:45am, MS 217)
Lecturer: Robin Cockett (ICT 652)
COURSE OUTLINE:
Overview of the tasks of a compiler: lexical analysis,
parsing, semantic analysis, code generation.
Lexical analysis: regular languages and automata
Context free grammars: LL(n), LR(n), LALR(1).
Attribute grammars: inherited and synthesized attributes,
circularity.
Compiling to a stack machine.
Who should take this course?
Have you ever wondered how a compiler works? This course is an
introduction to compiler construction which concentrates on the
front-end issues: parsing, generating the appropriate internal data
structures (abstract syntax tree), and basic "ad hoc" code
generation. The problem of parsing input led to some of
the earliest theoretical developments in computer science: the
theory of regular and context free languages. The parsing
algorithms which resulted for context free languages are
useful far beyond the specific task of generating a compiler.
These techniques provide the basis for the front-end of almost all
major systems. Modern compilers and other systems use software
tools for facilitating the construction of these front-ends.
The course will introduce the basic tools of Lex and Yacc and end by
building a compiler (to stack machine code or -- possibly -- an ARM
emulator) for a simple language.
This course is centered round the organization of the "front-end"
of a compiler. The "back-end" issues (code
optimization, dataflow analysis, instruction selection, register
allocation etc.) will only be briefly discussed in this course --
they are the main subject of the follow on course
510/611.
Assignments may be written in a language of your choice.
The choice must be discussed and agreed upon with your TA.
The language you choose must support LEX and YACC (an
LALR(1) parser generator tool). Your assignment marks will
depend on
on correctness and completeness of your code;
clear succinct documentation;
your coding techniques;
your performance on test examples and the test examples you
provide.
The main language of instruction will be the functional programming
language Haskell.
Discussion of comparison between implementation techniques in
different paradigms will take place in the labs and students are
encouraged to share their observations. Here are some possible
languages and the available tools:
Due April 4: Symbol
table and semantic analysis here (10%).
Due April (end of classes):
Stack based code generation here (10%).
EXAMS:
March 8: Midterm
(25%) past exams are here:
this is mostly on context free languages (if you have not done
so already check out the Context Free Grammar
Checker).
Late policy: for each 24 hours latethe maximum
mark you can obtain will be reduced by 20%. After two
working days we will not accept a late submissions.
Cheating: Any cases will automatically receive the
following treatment :
[First offense:] You will receive a letter notifying you that
you were involved in such behavior. This letter will
be kept in your file for the remainder of your stay at the
university.
[Second offense:] You will be subject to disciplinary action:
usually removal from your program.
My main concern is that you should be learning in this class: if you
are cheating you are not learning! Furthermore, you may be
setting an unfortunate trend for your future work habits. I regard
it as an integral part of my job, as a teacher, to ensure that you
approach your work with the right attitude and will muster all the
resources at my disposal to achieve this.
When you hand in work to be graded you are saying that it is your
work. For programs this means that you typed in the program,
developed it, and debugged it yourself. If you use
routines from a book or another source you must clearly document
your source. Furthermore, before handing in some
code, you should spend a moment to consider how you had arrived at
that code. If you realize that some of the code which should
have been yours is not then this is the time to come and talk to
me or the TA before you get into trouble. This allows
us to apportion credit appropriately.
Discuss the course material! I strongly encourage
you to discuss all aspect of the course material! Form study
groups for the exams. Your peers are probably your
best learning resource. When you discuss programming
projects do so "off line" and away from the terminals: a good idea
is to do so on a blackboard which you clean carefully after the
discussion. The golden rule is: after you have
finished such a discussion you must walk away only with what
is in your head!
(Required) Compiler construction: principles and
practice. K.C. Louden.
(Recommended - and a useful book) Lex & Yacc. J.R. Levine,
T. Mason, D. Brown.
(Recommended) Compilers: principles techniques, and
tools. Aho, Sethi, Ullman.
PARSING LINKS:
A web based tool for
investigating context free grammars (developed by Mike Burrell a
former CPSC411 student!). It allows you to:
transform grammars into LL(1) (when possible) to look at
LL(1), LR(0), SLR(1), LALR(1), and LR(1) parsing tables
and automata. It also has examples of context free
grammars belonging to most of the different classes considered
in the course.
A downloadable tool for (Early) parsing called Kakuy
(it is free and for windows platforms).
"A Practical Guide to Parsing" by Dick Grune and Ceriel
Jacobs (search on web!).
