Computer Science @ UC Davis | Course Descriptions

ECS 142 COMPILERS (4) III

Lecture: 3 hours

Discussion: 1 hour

Prerequisite: Course ECS 20, ECS 140A; course ECS 120 recommended

Grading: Letter; project (50%), midterm (20%), final (30%)

Catalog Description:
Principles and techniques of lexical analysis, parsing, semantic analysis, and code generation. Implementation of compilers.

Goals:
This course introduces the students to the principles of compiler writing. It focuses on lexical analysis, parsing, and simple code generation. The students are expected to write a complete compiler for a very simple high level programming language.

Expanded Course Description:

Introduction to Translators
1. Assemblers, Interpreters, Compilers
2. Basic Techniques
3. Symbol Tables
4. One Pass vs. Two Pass
Lexical Analysis
1. Role of lexical analyzer, Regular expressions, DFA and NFA, Lexical analyzer generators
Syntax Analysis
1. Context free grammar
2. Top-down parsers
3. Bottom-up parsers, including LR(1), SLR(1), and LALR(1)
4. Error recovery
Semantic Analysis
1. Syntax-directed definitions
2. Attributed grammar
3. Type checking
Run-time Environment
1. Storage organization
Code Generation
1. Intermediate code generation
2. B. Code-generation algorithms
Code Optimization
1. Machine-independent code optimization
2. Machine-specific code optimization

Textbook:
A.V. Aho, R. Sethi, and J.D. Ullman, Compilers: Principles, Techniques, and Tools,, Addison-Wesley, 1988. ISBN 0-201-10088-6.

Computer Usage:
I. Students write their compilers in C++ or Java.

II. Programs are developed on DEC, HP, or SGI workstations running corresponding UNIX operating systems. Students use editors such as vi and emacs, and are exposed to debuggers, compiler-generator tools such as Lex and Yacc, and other UNIX tools.

Laboratory Projects:
The programming project involves writing a compiler for a simplified, Pascal-like language, to produce assembly language code for RISC architectures (such as MIPS or SPARC). The emphasis is on giving students experience in applying concepts discussed in lecture to a specific case. The project is evaluated by running the student's compiler against a set of source programs whose exact make-up is not known to the student. Students are expected to design the solution to this project individually.

Engineering Design Statement:
The students are given a set of basic principles in class, but need to exercise a considerable amount of judgment in their design and implementation. Design factors include choice of appropriate data structures and algorithms, error message design and error-recovery procedures, and questions affecting implementation efficiency. Students are graded on correctness of the compiler as well as the efficiency of the implementation. Examinations include design material.

ABET Category Content:
Engineering Science: 2 units
Engineering Design: 2 units

Goals:
Students will:

be introduced to the theoretical underpinnings and implementation details of a modern complier
learn the theoretical foundation and algorithms for syntactic analysis (including lexical analysis, parsing and semantic analysis)
develop broad understanding of the theoretical basis for code generation and code optimization
design and implement a full compiler for a high level programming language

Student Outcomes:

An ability to apply knowledge of mathematics, science, and engineering
An ability to design a system, component, or process to meet desired needs within realistic constraints such as economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability
An ability to identify, formulate, and solve engineering problems
An ability to use the techniques, skills, and modern engineering tools necessary for engineering practice

Instructors:R. Pandey, Z. Su

Prepared by: R. Pandey (October 1997)

Overlap Statement:
This course does not duplicate any existing course.

Back to Course Descriptions