CS 541 - Compiler Design

 

Credits: 3

 

Course Description

 

Intermediate aspects of a compilation process for high-level computer languages. Theoretical and practical issues in developing a complete translator. Code generation for expressions, control statements and procedures (including parameter passing). Symbol tables, runtime organization for simple and structured variables. Using compilers and translators for automation (filters, programs writing programs).

 

Prereqs: CS 441 or instructor’s consent.

 

Needed Skills

 

Students should be adept in programming in a modern programming language and have knowledge of machine organization.

 

Learning Outcomes

 

Successful students will learn:

1. How to specify lexical and syntactical structure of languages.

2. How to use regular patterns.

3. How to use parsing techniques.

4. How to design and implement translators.

5. How to use tools to generate lexical analyzers and parsers.

6. How to organize runtime storage for static and dynamic objects.

7. How to generate intermediate code for basic language constructs.

8. How to use parsing and translation techniques for automation of computing tasks.

 

Measures

 

These eight specific tasks will be used to measure students as applied to a three part project that creates a comprehensive compiler (lexer, parser, and code generation), homework assignments, and exams and/or a final examination. All the topics combined with a substantial programming project and other assignments will provide the student with the formative feedback about the development of their skills and knowledge.

 

CAC Categories

 

Topic

Core

Advanced

Math Fundamentals

0

0

Data Structures

6

0

Algorithms & Software Design

7

5

Computer Organization and Architecture

9

2

Concepts of Programming Languages

13

2

Social and ethical issues

1

0

Total

36

9

 

Math Fundamentals: none

 

Data Structures (6): Core (6): Symbol tables. Trees and graphs.

 

Algorithms and Software (12):

Core (7): Parsing algorithms including LL(1) and LR(1) techniques.

Advanced(5): Algorithms and heuristics for optimal code generation, register allocation and garbage collection. Compiler-compilers.

 

Computer Organization and Architecture (11):

Core (9): Environments, memory allocation, run-time storage organization.

Advanced(2): Review of different architectures.

 

Concepts of Programming Languages (15):

Core (13): Imperative languages, they constructs, specification and compilation.

Advanced(2): Compilation for non-imperative languages.

 

Social and ethical issues (1): Responsible usage of computers, social impact of incorrect algorithms and faulty software

 

Oral Communication (presentations)

 

Class discussion is encouraged. Students present their solutions either in class or individually to the instructor.

 

Written Communication

 

Students design and document a very complex set of computer programs and inputs to software tools that generate computer programs. The documentation evolves over the course of the semester to reflect the project growth. Homework assignment includes problems that require clear presentation of the solutions that use technical terminology and complex concepts.

 

Coverage

 

Theoretical Content: 30%

Theoretical underpinnings of the translation theory such as grammars, syntax-directed translation and concepts in programming languages.

 

Problem Analysis: 20%

Analysis of programming language constructs, syntax and semantics and their formal specifications and their computer translation.

 

Solution Design: 50%

Designing a complete compiler for a high-level language.

 

Student Evaluation and Feedback

 

Students are evaluated on their work that includes programming project, homework assignment and exams. Students receive back all of their work with comments to indicate problems and point out correct or better solutions. Sample solutions and typical errors are discussed in class.

 

Grading

 

Grade is determined by performance on homework assignments (25%), programming assignments (40%), and exams (35%). Final grades will be assigned according to the following scale: A=90-100%, B=80-89%, C=70-79%, E=0-59%. (Categories and weights for assignments and scales are examples only; actual categories, weights and scales used may vary with instructor.)

 

NOTE: 100% lecture - 0% recitations

 

Course Evaluation Questions

 

The course has helped me:

37. How to specify lexical and syntactical structure of languages.

38. How to use regular patterns and grammars.

39. How to use parsing and translation techniques for automation of computing tasks.

40. How to use tools to generate lexical analyzers, parsers, translators and code generators.

41. How to organize runtime storage for static and dynamic objects.

42. Design and write a complex programming project.

 

Possible Textbook

 

Compilers: Theory and Practice,
Aho, Sethi, Ullman,
Addison-Wesley, 1990