Current Catalog Description

Principles of artificial language description and design. Sentence parsing techniques, including operator precedence, bounded-context, and syntax-directed recognizer schemes. The semantic problem as it relates to interpreters and compilers. Dynamic storage allocation, table grammars, code optimization, compiler-writing languages. Prerequisites: CSE 109


"Compilers: Principles, Techniques and Tools" (2nd edition) by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffery D. Ullman. Addison Wesley, Boston, MA, 2006. ISBN 0321486811



Course Outcomes

Students will have:

Fluency in describing the theory and practice of compilation, in particular, the lexical analysis, syntax, and semantic analysis, code generation and optimization phases of compilation.

Ability to create lexical rules and grammars for a programming language.

Ability to use Flex or similar tools to create a lexical analyzer and Yacc/Bison tools to create a parser.

Ability to implement a lexer without using Flex or any other lexer generation tools.

Ability to implement a parser such as a bottom-up SLR parser without using Yacc/Bison or any other compiler-generation tools.

Ability to implement semantic rules into a parser that performs attribution while parsing.

Ability to design a compiler for a concise programming language.

Relationship between Course Outcomes and Program Outcomes

CSE 302 substantially supports the following program outcomes:

B. An ability to analyze a problem and identify and define the computing requirements appropriate to it solution

C. An ability to design, implement, and evaluate a computer-based system process, component, or program to meet desired needs

I. An ability to use current techniques, skills, and tools necessary for computing practices

K. An ability to apply design and development principles in the construction of software systems of varying complexity

Prerequisites by Topic

1. Finite Automata (e.g., Subset Construction Algorithm)

2. Names, Bindings, Type Checking and Scopes

4. Expressions and Assignment Statements

5. Statement-Level Control Structures

6. Pointers and Binary Trees

7. Elementary Parsing

8. Elementary Code Generation

Major Topics Covered in the Course

1. Introduction to Compiler Design

2. Lexical Analysis, such as NFA/DFA conversion, Flex, etc.

3. Syntax Analysis, such as recursive-descent parsing, LL (1) grammar and predictive parsing, LR (0) parsing and SLR (1) parsing, LR (1) parsing and LALR (1) parsing, Yacc, etc.

4. Syntax-Directed Translation (SDT), such as SDT with LL-parser and DAG

5. Type Checking

6. Run-Time Environments

7. Intermediate Code Generation

Assessment Plan for the Course

The students are given eleven homework assignments, two major programming projects of three weeks duration each, a midterm exam, and a final examination. Each homework assignment typically covers a single topic. Students are required to extend a context-free language and design and implement a lexer and bottom-up (SLR) parser for the language in the first programming project. In the second project, students are required to extend a context-free language and design and implement a compiler using compiler construction tools such as Bison and Yacc. Midterm test has five questions, and the final examination has nine questions. Each of these questions typically covers a single topic. I track the performance of the students on each homework assignment, each programming project assignment, and each question on the midterm and final examination.