课程名称 教学大纲 一 课程基本信息 开课单位信息学院课程代码 CS131 课程名称编译原理英文名称 Programming Languages and Compilers 学分 4 学时 64 授课对象 ( 面向专业 ) CS 双语 / 中文 / 全英文授课 双语 先修课程 CS100 二 课程简介和教学目的 课程简介 : 1. 本课程介绍编译器构造的一般原理和基本实现方法, 主要介绍编译器的各个阶段 : 词法分析 语法分析 语义分析 中间代码生成 代码优化和目标代码生成 反映直至 20 世纪末的一些重要成果, 如有关类型制导的编译思想 2. 本课程在介绍命令式程序设计语言实现技术的同时, 强调一些相关的理论知识, 如形式语言和自动机理论 语法制导的定义和属性文法 类型论等 它们是计算机专业理论知识的重要一部分, 在本书中结合应用来介绍这些知识, 有助于学生较快领会和掌握 3. 本课程强调形式化描述技术, 并以语法制导定义作为翻译的主要描述工具 4. 本课程强调对编译原理和技术在宏观上的理解, 而不把读者的注意力分散到一些枝节的算法上, 如计算开始符号集合和后继符号集合的算法, 回填技术等 作为原理性的教材, 本书介绍基本的理论和方法, 而不偏向于某种源语言或目标机器 教学目的 : 理论 : 使学生熟练掌握编译器构造的一般原理 基本实现方法及其相关理论知识
实践 : 能够独立设计和开发简单语言的编译器 课程意义 : 1. 本课程能使学生对编程语言的设计和实现有深刻的理解, 对和编程语言有关的理论 ( 形式语言和自动机理论 类型论等 ) 有所了解, 对宏观上把握编程语言来说, 起一个奠基的作用 2. 对软件工程来说, 编译器是一个很好的实例 ( 基本设计 模块划分等 ), 也是本科期间能碰到的唯一的大型例子, 学生从本课程的学习也能了解到软件工程中的一些技术 ( 如基于事件驱动的编程 ) 本课程所介绍的概念和技术能应用到一般的软件设计之中 3. 大多数程序员同时是语言的设计者, 虽然是一些简单的语言 ( 如输入输出 ), 本课程的学习有助于提高对这些语言的设计水平 4. 编译技术在软件逆向工程 程序理解和软件安全等方面有着广泛的应用 5. 软件逆向工程 : 以另外一种形式创建系统同一层次的表示或者更高层次的抽象, 应用 : 技术仿造 软件维护 6. 程序理解 : 通过分析 抽象和一般化来获取软件知识的演绎过程 (1) 基于机器代码和中间代码层的理解, 需要借助于反汇编和反编译技术 ;(2) 基于源代码的理解 ;(3) 基于语法层的理解, 程序分段 程序切片和程序分析等技术就是其中的最典型代表 ;(4) 基于程序语义层的理解, 模式匹配 格局识别 (plan recognition) 概念赋值(concept assigned) 和概念分析 (concept analysis) 等都是进行语义级的软件理解和分析技术 7. 软件安全 : 满足安全策略 基本安全策略 : 类性安全 控制流安全和内存安全 还有信息流安全 用到词法 语法和语义分析 类性系统和类性检查 控制流分析和数据流分析等 编译器将走向类型制导的编译器 三 教学内容 教学方式和学时安排 ( 建议例表如下 ) 课堂教学内容 教学进度和学时安排 教学方式 第一章绪论 第 1 周 课堂教学 课后
1.1 语言处理 1.2 编译器结构 第二章一个简单的语法制导翻译 器 2.1 引言 2.2 语法定义 2.3 语法制导翻译 2.4 语法分析 2.5 简单表达式的翻译器 2.6 词法分析 2.7 符号表 2.8 中间代码生成 第 3 章词法分析 3.1 词法分析器的作用 3.2 输入缓冲 3.4 词法单元的识别 3.5 词法分析器生成工具 Lex 3.6 有穷自动机 3.7 从正则表达式到自动机 3.8 词法分析器生成工具的设 计 3.9 基于 DFA 的模式匹配器的优 化 第 4 章语法分析 4.1 引论 4.2 上下文无关文法 4.3 设计文法 4.4 自顶向下的语法分析 4.5 自底向上的语法分析 4.6 LR 语法分析技术介绍 : 简单 LR 4.7 更强大的 LR 语法分析器 4.8 使用二义性文法 4.9 语法分析器的生成工具 随堂测验 第 5 章语法制导的翻译 5.1 语法制导定义 复习 ( 作业 ) 第 1 周课堂教学 复习 ( 作业 ) 第 2 周 总计 4 学时第 2 周课堂教学 复习 ( 作业 ) 材料阅第 3 周读 词法分析器项 4 学时目第 4 周 4 学时第 5 周 总计 1第 5 周课堂教学 复习 ( 作业 ) 材料阅第 6 周读 语法分析器项 4 学时目第 7 周 4 学时第 8 周 总计 1第 8 周闭卷 第 9 周课堂教学 复习 4 学时 ( 作业 )
5.2 SDD 的求值顺序 5.3 语法制导翻译的应用 5.4 语法制导的翻译方案 5.5 实现 L- 属性的 SDD 第 6 章中间代码生成 (6h) 6.1 语法树的变种 6.2 三地址代码 6.3 类型和声明 6.4 表达式的翻译 6.5 类型检查 6.6 控制流 6.7 回填 6.8 Switch 语句 6.9 过程中间代码 随堂测验讲解 第 10 周 第 10 周 第 11 周 4 学时第 12 周 课堂教学 复习 ( 作业 ) 材料阅 读 第 7 章运行时环境 7.1 存储组织 7.2 栈空间分配 7.3 栈中非局部数据访问 7.4 堆管理 7.5 内存回收简介 第 12 周 第 13 周 课堂教学 复习 ( 作业 ) 第 8 章代码生成 8.1 代码生成器设计中的问题 8.2 目标程序 8.3 目标程序中的地址 8.4 基本块和流图 8.5 基本块优化 8.6 一个简单代码生成器 8.7 窥孔优化 8.8 寄存器分配和指派 8.9 通过树重写来选择指令 第 9 章优化 9.1 优化的主要来源 9.2 数据流分析介绍 9.3 数据流分析基础 9.4 常量传播 9.5 部分冗余消除 9.6 流图中的循环 第 13 周 第 14 周 4 学时第 15 周 4 学时第 16 周 课堂教学 复习 ( 作业 ) 项目代码生成器课堂教学 复习 ( 作业 ) 材料阅读
9.7 基于区域的分析 9.8 符号分析 Review 期末考试 第 16 周 第 17 周 闭卷 注 : 习题课 实验 ( 上机 / 实践 ) 内容和基本要求可参照填写 四 考核方式和成绩评定 项目 30% 作业 20% 期中测试 20% 期末测试 30% 五 推荐教材和参考书目 书名 作者 译者 出版社 出版时间 ISBN 教材 : Compilers: Principles, Techniques and Tools (2Ed.) by Aho et al, 机械工业 出版社 参考书目 : Compiler Construction Principles and Practice by Louden,PWS Publishing Company 六 其他说明 建议内容 : 1. 课程教学网站 教学参考网站 ; 2. 基于学业规范的要求 ( 道德行为规范 作业规范 实验规范等 ) 3. 个性化的要求 七 教师信息和开课单位审核意见 签名 : 邮箱 songfu@shanghaitech.edu.cn 授课教师 年月日 签名 : 年月日 电话 15921769918 邮箱 电话
课程负责人 ( 大纲负责人 ) 签名 : 年月日 开课单位审核意见 签名 : ( 单位公章 ) 年月日
Course Syllabus I.General Information Course Code Course Title CS131 Programming Languages and Compilers Credit 4 Teaching Hours 64 Major CS Prerequisite(s) CS100 II.Course Description This course covers the fundamentals of compiler design, including lexical analysis, parsing, semantic analysis, compile-time memory organization, run-time memory organization, code generation, and compiler portability issues. Goal: 1. Understand what is a compiler 2. Understand the different phases of a compiler 3. Have an idea about designing and maintaining a compiler using compiler generator tools III.Course Schedule 1. Introduction (2h, xh denotes x Teaching hours) 1.1 Language Processors 1.2 The Structure of a Compiler 2. Simple Syntax-Directed Translator (4h) 2.1 Introduction 2.2 Syntax Definition 2.3 Syntax-Directed Translation 2.4 Parsing 2.5 A Translator for Simple Expressions 2.6 Lexical Analysis 2.7 Symbol Tables 2.8 Intermediate Code Generation
3. Lexical analysis (12h) 3.1 The Role of the Lexical Analyzer 3.2 Input Buffering 3.3 Specification of Tokens 3.4 Recognition of Tokens 3.5 The Lexical-Analyzer Generator Lex 3.6 Finite Automata 3.7 From Regular Expressions to Automata 3.8 Design of a Lexical-Analyzer Generator 3.9 Optimization of DFA-Based Pattern Matchers 4. Syntax Analysis (12h) 4.1 Introduction 4.2 Context-free grammars 4.3 Writing a grammar 4.4 Top-down parsing 4.5 Bottom-up parsing 4.6 Introduction to LR parsing: simple LR 4.7 More powerful LR parsers 4.8 Using ambiguous grammars 4.9 Parser generators 5. Syntax-Directed Translation (6h) 5.1 Syntax-directed definitions 5.2 Evaluation orders for SDD's 5.3 Applications of syntax-directed translation 5.4 Syntax-directed translation schemes 5.5 Implementing L-attributed SDD's 6. Intermediate-Code Generation (6h) 6.1 Variants of syntax trees 6.2 Three-address code 6.3 Types and declarations 6.4 Translation of expressions 6.5 Type checking 6.6 Control flow 6.7 Back patching 6.8 Switch-statements 6.9 Intermediate code for procedures 7. Run-time Environment (4h) 7.1 Storage organization 7.2 Stack allocation of space 7.3 Access to nonlocal data on the stack 7.4 Heap management 7.5 Introduction to garbage collection 8. Code generation (6h) 8.1 Issues in the design of a code generator
8.2 The target language 8.3 Addresses in the target code 8.4 Basic blocks and flow graphs 8.5 Optimization of basic blocks 8.6 A simple code generator 8.7 Peephole optimization 8.8 Register allocation and assignment 8.9 Instruction selection by tree rewriting 9. Optimizations (6h) 9.1 The principal sources of optimization 9.2 Introduction to data-flow analysis 9.3 Foundations of data-flow analysis 9.4 Constant propagation 9.5 Partial-redundancy elimination 9.6 Loops in flow graphs 9.7 Region-based analysis 9.8 Symbolic analysis Midterm 2h Midterm exam analysis 2h Review, 2h IV.Evaluation Projects 30% Homework 20% Midterm 20% Final 30% V.Textbooks and References Textbook: Compilers: Principles, Techniques and Tools (2Ed.), by Aho, Lam, Sethi, and Ullman (ISBN-10: 0321486811). References: Compiler Construction Principles and Practice by Louden VI.Instructor Information Email songfu@shanghaitech.edu.cn Instructors Signature / Print Name Date Tel 15921769918 Email Signature / Print Name Date Tel
Course Director Signature / Print Name Date Approved by Signature / Print Name (Seal of Department) Date
附 : 编写说明 1. 大纲采用中英文双语填写 ; 2. 课程代码 由教学与学生事务处统一编码, 其余内容由任课教师编写, 由开课单位审核 3. 课堂讲授一般 16 个学时计 1 学分, 实验 实践一般 48 学时计 1 学分 4. 课程简介 教学目的 教学内容 考核方式 等栏目的填写尽可能详实准确, 使学生能够清楚明白本课程的性质 目的 内容和要求等 5. 考核方式 由授课老师自定 上科大研究生和本科生课程考核成绩统一使用等级制, 为便于成绩存档和查询, 要求授课教师在 成绩评定 同时提供百分制和等级制成绩 具体参照上海科技大学成绩管理相关规定执行 6. 教师信息 中, 课程负责人 是在有多位教师讲授同 1 门课的情况下, 设置的主持教授, 负责组织课程和教学大纲的编写, 如该课程由 1 位课程教师独立授课, 课程负责人 信息无需重复填写和签名