Computer Science

ECS 142 Compilers

ECS 142 COMPILERS (4 units)

Format
Lecture: 3 hours
Discussion: 1 hour

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

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

Credit restrictions, cross listings: None

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.

Summary of course contents

The lecture topics include the following, not necessarily listed in chronological order:

  1. Introduction
    1. Interpreters and compilers
    2. Phases of a compiler
    3. Symbol tables
  2. Lexical Analysis
    1. Role of lexical analyzers
    2. Regular expressions
    3. DFAs and NFAs
    4. Lexical-analyzer generators
  3. Syntax Analysis
    1. Context-free grammars
    2. Top-down parsing
    3. Bottom-up parsing, including LR(1), SLR(1), and LALR(1)
    4. Error recovery
  4. Semantic Analysis
    1. Syntax-directed definitions
    2. Attributed grammar
    3. Type checking
    1. Run-time Environments
    2. Storage organization
    3. Activation records
  5. Code Generation
    1. Intermediate code generation
    2. Code-generation algorithms
  6. Code Optimization
    1. Local optimizations
    2. Global optimizations

The programming project involves the writing of an operational compiler for a small object-oriented language to produce MIPS assembly code. Its emphasis is on giving students experience in applying concepts discussed in lecture. The project is evaluated by running the students’ compilers against a set of source programs unknown to the students. Students are expected to design their solutions to the project either in small groups or individually.

Goals: This course introduces students to the principles and techniques of compiler construction. It focuses on lexical analysis, parsing, semantic analysis, and basic code generation and optimization. The students are expected to write a complete, operational compiler for a small high-level programming language. Students will (1) be introduced to the theoretical underpinnings and implementation details of a modern complier, (2) learn the theoretical foundation and algorithms for syntactic (including lexical analysis and parsing) and semantic analysis, (3) develop a broad understanding of the theoretical basis for code generation and optimization, and (4) design and implement a full, functioning compiler for a high-level programming language.

Illustrative reading
A. Aho, M. Lam, R. Sethi, and J. Ullman, Compilers: Principles, Techniques, and Tools (2nd Edition), Prentice Hall, 2006. ISBN 0-321-48681-1.

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.

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

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

GE3
Science & Engineering

Overlap: None

Instructors: R. Pandey and Z. Su

History: 2012.10.20 (Z. Su): (1) added “code optimization” to catalog description, (2) made various small edits in the course outline to be closer to what we actually do, e.g., using object-oriented language, generating MIPS code, and working in groups (I usually require/recommend students to work in groups of two), and (3) updated the suggested reading to use a newer version of the book. Added to ICMS archive 2007.06.20. Original course description dates to October 1997 (R. Pandey).

Outcomes

1

X

an ability to apply knowledge of mathematics, science, computing, and engineering

2

 

an ability to design and conduct experiments, as well as to analyze and interpret data

3

X

an ability to design, implement, and evaluate a system, process, component, or program to meet desired needs, within realistic constraints such as economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability

4

 

an ability to function on multi-disciplinary teams

5

X

an ability to identify, formulate, and solve computer science and engineering problems  and define the computing requirements appropriate to their solutions

6

 

an understanding of professional, ethical, legal, security and social issues and responsibilities

7

 

an ability to communicate effectively with a range of audiences

8

 

the broad education necessary to understand the impact of computer science and engineering solutions in a global and societal context

9

 

a recognition of the need for, and an ability to engage in life-long learning

10

 

knowledge of contemporary issues

11

X

an ability to use current techniques, skills, and tools necessary for computing and engineering practice

12

X

an ability to apply mathematical foundations, algorithmic principles, and computer science and engineering theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices

13

X

an ability to apply design and development principles in the construction of software systems or computer systems of varying complexity

border