編譯器

This course is intended to explore the principal ideas and techniques of compiler construction. Topics include lexical analysis, syntax analysis including LL and LR parsers, type checking, run-time environments, symbol tables, code generation, and compiler-construction tools. Some compiler optimization techniques will also be covered. This course aims to give you a solid foundation in the theory of compiler construction as well as the experience of building a compiler. Much of what you have learned about algorithms and data structures will come to bear as you study and implement the various components of a compiler. In a sense, compiler construction is a showcase for many other disciplines of computer science. Course Objectives: (1) To learn structure of compilers. (2) To learn techniques used in compiler construction such as lexical analysis, top-down and bottom-up parsing, context-sensitive analysis, intermediate code generation, and code optimization. (3) To learn basic data structures used in compiler construction such as abstract syntax trees, symbol tables, three-address code, and stack machines. (4) To learn software tools used in compiler construction such as lexical analyzer generators (Lex), and parser generators (Yacc). (5) To construct a compiler for a small language using the above techniques and tools.

Programming Languages, Data Structures, and Assembly Language and System Programming

無備註

Course website and TAs will be announced in the first week of the semester.

1學期作業 The course involves a significant programming project - implementing a compiler for a simple programming language. The project will build the compiler as a series of phases and you must keep pace with the project in order to be successful in this course. The project draws heavily on much of what you have learned thus far and will stretch your programming skills. You are free to choose the language you will use for the programming project. You will be assigned to generate code for the Java virtual machine. The penalty for late homework is 15% per day (weekends count as 1 day). Late homework will not be accepted after the solutions have been posted. There will be NO CREDIT given for plagiarism. 2.考試狀況 Midterm and final exams 3.評量方法 Midterm Exam 30% Final Exam 30% Course Projects 40%

• Introduction

  - Course introduction - Overview of compilers, phases of a compiler

  講授：

  3

• Lexical analysis, scanning

  - Regular expressions, lex/flex, start on FSA - How lex works, NFAs, DFAs

  講授：

  9

  實作：

  3

• Syntax analysis, parsing

  - Context free grammars, ambiguity - Yacc/Bison introduction, top-down parsers - Top-down parsers, intro to bottom-up parsers - Bottom-up parsers - LR parsing

  講授：

  15

  實作：

  3

• Context-Sensitive Analysis

  - Syntax-directed definitions, intro to semantic analysis - Type checking

  講授：

  6

  實作：

  3

• Runtime environments

  - Symbol tables - Stack/heap managemen

  講授：

  6

• Code generation

  - Generating code for JVM, Jasmin assembly language

  講授：

  6

  實作：

  3

• Code optimization

  - Data-flow analysis - Instruction scheduling/register allocation

  講授：

  6

Required textbook: Compilers: Principles, Techniques, and Tools (2nd edition), by Aho, Lam, Sethi, and Ullman, Addison Wesley, 2007. Reference book: Lex & Yacc, by Doug Brown, John Levine, and Tony Mason, O'Reilly Media, 1995.

地點

EC532

時間

教師未提供此項資料

聯絡方式

分機56688 ypyou@cs.nctu.edu.tw