Who - Anyone with an interest in understanding and applying compiler techniques. This course satisfies the Computer Science requirement for a C3xx or C4xx course.
What (CC2001 Computer Science) - The course follows the Association of Computing Machinery's Curriculum 2001 guide for university computer science programs.
Introduces the theory and practice of programming language translation. Topics include compiler design, lexical analysis, parsing, symbol tables, declaration and storage management, code generation, and optimization techniques.
This course has two distinct but interrelated goals. First, it explores the theory of language translation. Second, it shows how to apply this theory to build compilers and interpreters, as well as compiler generators. It covers the building of translators both from scratch and using compiler generators. In the process, the course also identifies and explores the main issues of the design of translators.
As is the case in many computer science courses with a significant theoretical component, visualization tools can improve the quality of lectures and serve as animated lecture notes. The most useful kind of algorithm animations are those that show in a synchronized way both an operational view and a conceptual view of the algorithm steps. The construction of a compiler/interpreter is a necessary component of this course, so students can obtain the necessary skills. Compiler programming projects, however, are often problematic for the following reasons:
• The size of a compiler implementation is usually much larger than that of the projects
students have undertaken in earlier courses.
• Most compiler generators are tabular, which makes the resulting compiler more
difficult to debug.
The severity of these problems will be reduced by using declarative scanners and
parser generators that produce recursive-descent parsers.
Syllabus:
• Overview of programming languages: History of programming languages; brief survey
of programming paradigms; the role of language translation in the programming
process
• Fundamental issues in language design: General principles of language design; design goals; typing regimes; data structure models; control structure models; abstraction mechanisms
• Virtual machines: The concept of a virtual machine; hierarchy of virtual machines; intermediate languages
• Introduction to language translation: Comparison of interpreters and compilers; language translation phases; machine-dependent and machine-independent aspects of translation; language translation as a software engineering activity
• Lexical analysis: Application of regular expressions in lexical scanners; hand-coded vs. automatically-generated scanners; formal definition of tokens; implementation of finite-state automata
• Syntactic analysis: Formal definition of grammars; BNF and EBNF; bottom-up vs. top-down parsing; tabular vs. recursive-descent parsers; error handling; automatic generation of tabular parsers; symbol table management; the use of tools in support of
the translation process
• Models of execution control: Order of evaluation of subexpressions; exceptions and exception handling; runtime systems
• Declaration, modularity, and storage management: Declaration models; parameterization mechanisms; type parameterization; mechanisms for sharing and restricting visibility of declarations; garbage collection
• Type systems: Data type as set of values with set of operations; data types; typechecking models; semantic models of user-defined types; parametric polymorphism; subtype polymorphism; type-checking algorithms
• Interpretation: Iterative vs. recursive interpretation; iterative interpretation of intermediate code; recursive interpretation of a parse tree
• Code generation: Intermediate and object code; intermediate representations; implementation of code generators; code generation by tree walking; context-sensitive translation; register use
• Optimization: Machine-independent optimization; data-flow analysis; loop optimizations; machine-dependent optimization
Curriculum 2001 Units covered:
PL1 Overview of programming languages 2 core hours
PL2 Virtual machines 1 core hour
PL3 Introduction to language translation 2 core hours
PL8 Language translation systems 15 hours
PL9 Type systems 4 hours
Elective topics 16 hours
Small exercises serve to highlight key course topics while homeworks provide
practice with and exposure to standard compiler methods. The homeworks include the design and
implementation of solutions using common compiler methods such as type checking,
parsers and parser generators, visitor patterns, register allocation using graph
coloring and translation from a high level to a low level computer language. More specific information can be
obtained by reading the following discussion of course goals or by examining
exercises listed as homeworks on the course syllabus.
CSCI C431 Learning Goals
The learning goals of each computer science course strive to capture intended learning outcomes. The goals are expressed using the terms that follow. These terms describe the level of familiarity (most to least) with respect to various kinds of material and procedures.
The C463 learning goals cover important areas recommended jointly in a report by the Association of Computing Machinery (ACM) and the Computer Society of the IEEE in 2001 for university computing curricula. These international organizations were established to promote academic and professional excellence in the computer sciences. The complete baccalaureate curricula list consists of fourteen subject areas, of which a portion are covered in this course, primarily those areas which better prepare the student to succeed in subsequent Indiana University Southeast computer science courses and as professional computer scientists. Certain of these subjects listed below have been presented in previous courses or will recur in subsequent courses.
Design of C431 to Achieve These Goals
Computer science demands competency in a range of skills. Therefore, students benefit from the guided practice in the environment of a university class. To facilitate this, C431 includes the following:
Document last modified: