《编译原理》教学大纲

1、编译原理教学大纲大纲说明课程代码：3225003 总学时：64学时（讲课48学时，实验16学时）总学分： 4课程类别：学科基础课适用专业: 计算机科学与技术（专业）预修要求：C语言程序设计、C+程序设计、数据结构 课程的性质、任务及地位 ： 编译原理是计算机科学与技术专业的一门重要基础课。通过对该课程的学习，使学生掌握编译过程中的相关原理和编译技术，让学生能初步进行编译程序的开发和维护，同时促进提高学生开发软件的能力。教学目的与基本要求：本课程的目的，通过向学生讲述编译系统的结构、工作流程及编译程序各部分的设计原理和实现技术，使学生既掌握编译技术理论的基础与基本知识，也具有设计、实现、分析和维

2、护编译程序等方面的初步能力。本课程理论性较强。因授课对象为工科学生，所以在强调编译系统的构造原理和实现方法的同时，为培养学生的实际工作能力，通过上机实践进一步加深学生对课堂教学内容的理解。目的是要使学生牢固掌握相关的基本理论和基本方法，并能初步利用上述理论和方法解决简单实际问题。教学方法和教学手段的建议：在教学方法上，贯彻理论联系实际、“精讲、多练”的原则，进行案例式、启发式的教学，对于一些实际性较强的问题要多采用课堂讨论等方式 ，以提高学生的思辨能力和学习的主动性；引导学生读书、理解、体悟、运用相结合；提高学生的学习兴趣与热情，培养与发挥学生的提出、分析及解决问题的能力。教学手段：运用多媒体

3、教学手段+黑板+上机实验的手段。采取课堂讲授、课堂讨论、课后练习与自学等形式。大纲的使用说明：大纲对课程性质、目的等作简单说明，同时列出各章节要学习的知识点、重点、难点，便于教学时教授重点的安排和学生自学安排。大纲正文第一章 引论 学时：4学时（讲课4学时，实验0学时）了解编译的概念；理解编译程序的各组成部分及功能。本章讲授要点：介绍程序设计语言与编译程序间的关系，主要内容包括：各级程序设计语言的定义、源程序的执行、编译程序的构造、编译程序的分类、形式语言理论与编译实现技术的联系。重点：程序设计语言的定义，语法图及BNF表示法，编译程序的各阶段功能。难点：程序执行的方式、编译程序“趟”的概念。

4、第一节 程序设计语言与编译程序的联系一、 源程序、程序设计语言的执行二、 编译程序的两种方式：解释与编译三、 编译程序的定义第二节 编译程序构造及有关概念四、 程序设计语言的四个方面：语法、语义、语用、语境五、 语法的定义：语法图、BNF表示法、口语六、 程序执行的过程七、 编译程序的组成模块：词法分析、语法分析、语义分析、代码优化、目标代码生成八、 “趟”的概念九、 编译程序的分类第三节 形式语言与编译实现技术思考题：1 编译原理的定义是什么？2 编译原理由几部分构成？各部分完成哪些工作？3 在编译过程中“趟”的概念是指什么？第二章 文法与语言 学时：8学时（讲课6学时，实验2学时）理解字母

5、表的定义及闭包、符号串的基本知识及其运算、符号串集合概念及运算；掌握文法的形式定义、Chomsky语言的分类、文法等价及其等价变换方法、语法分析树与句型分析。本章讲授要点：字母表的定义及闭包、符号串的基本知识及其运算、符号串集合概念及运算、文法的形式定义、Chomsky语言的分类、文法等价及其等价变换方法、语法分析树与句型分析。重点： Chomsky文法的定义、文法和语言之间的关系、规范推导和规范规约、文法的二义性判定；文法的化简。难点：句型分析、文法的文法的二义性判定、文法等价及其等价变换方法。第一节 符号串与符号串集合一、 字母表的定义、字母表的闭包与正闭包二、 符号串及其运算第二节 文法

6、与语言的形式定义一、 文法的形式定义、重写规则的表示形式二、 文法的定义、应用文法产生语言的句子三、 语言的形式定义第三节 语言的分类一、Chomsky语言分类法二、Chomsky的文法定义三、上下文无关的讨论 第四节 文法等价与等价变换一、文法等价二、压缩文法等价变换三、消去单规则等价变换四、消去左规则等价变换第五节 语法分析树与句型分析一、语法分析树二、句型分析思考题：1 弄清字母表、字符串集合、字符串闭包及正闭包的定义。2 弄清文法、重写规则与语言之间的关系。3 Chomsky语言类有几类？各有什么特点？4 什么是无用规则，如何消除？5 弄清在推导语法树中，弄清句型、短语、简单短语、句柄

7、以及句子的概念。第三章 词法分析 学时：14学时（讲课10学时，实验4学时）了解词法分析的目标和实现方法、词法分析器的目标是识别源程序中的各个单词。理解确定有限自动机的组成和非确定有限自动机的组成。掌握状态转换图、状态转换图与正则文法的相互转换、确定有限自动机和非确定有限自动机、NFA转DFA、DFA的最小化、正则表达式与正则集、正规式转DNF。本章讲授要点：词法分析器的目标是识别源程序中的各个单词。词法分析可以通过确定有限自动机来完成。：状态转换图、状态转换图与正则文法的相互转换、确定有限自动机和非确定有限自动机、NFA转DFA、DFA的最小化、正则表达式与正则集。词法分析程序的实现与编写，

8、以及词法扫描程序的算法。重点：状态转换图、正则文法与状态转换图的互换、NFA转DFA、DFA的最小化。正则表达式与状态转换图。 难点：NFA转DFA、DFA的化简、正则文法与正则表达式。第一节 引言一、 词法分析的任务、词法分析程序二、 符号的识别与重写规则的关系三、 词法分析的实现方式第二节 正则表达式与有穷状态自动机一、 状态转换图、状态转换系统二、 确定有穷状态自动机DFA三、 非确定有穷状态自动机NFA四、 DFA的化简五、 正则表达式第三节 词法分析程序的实现一、 单词与属性字二、 标识符的处理三、 词法分析程序的编写第四节 词法分析程序的自动生成一、 基本思想二、 扫描程序与构造程

9、序三、 自动生成系统LEX思考题：1 词法分析的功能是什么？2 什么是状态转换图、NFA、DFA？3 如何将NFA转换为DFA？4 如何简化DFA？5 正则表达式与DFA有何关系？第四章 语法分析自顶向下的语法分析技术 学时：6学时（讲课6学时，实验0学时）了解语法分析的功能和两中大的分析方法：自顶向下的语法分析法和自下而上的语法分析。理解自上而下的分析方法-从文法的开始符号推导出句子本身的分析方法，自下而上的分析方法从语句归约为文法开始符号的分析原理。掌握FELLOW（）和FIRST（）的算法、预测分析表的构造和预测分析过程。 本章讲授要点：自顶向下的语法分析法带回溯自顶向下分析技术、无回溯

10、顶向下分析技术及其算法、递归下降分析法和预测分析法，预测分析法的文法要求、分析表的构造方法、预测分析方法。 重点：无回溯的递归下降分析技术与预测分析法。难点：LL（1）文法的判定、预测分析法、递归下降分析法。第一节 引言一、 自顶向下分析技术及识别算法二、 讨论的前提三、 要解决的基本问题第二节 带回溯的自顶向下分析技术一、 基本思想二、 实现算法及举例三、 问题及其解决第三节 无回溯的自顶向下分析技术一、 先决条件二、 递归下降分析技术三、 预测分析技术思考题：1 何为自顶向下分析技术？2 如何区别带回溯自顶向下分析技术与无回溯顶向下分析技术？3 什么是分析表的构造方法？4 什么是预测分析方

11、法？第五章 语法分析自底向上分析技术 学时：16学时（讲课10学时，实验6学时）理解自底向上的语法分析法及算法、自底向上的语法分析的基本实现方法；掌握LR分析原理及组成、LR（0）项目集规范族的构造、LR（0）分析表的构造、SLR（k）分析表构造方法、LAL（k）分析表构造方法、识别程序的自动构造。本章讲授要点：自底向上的语法分析法及算法、自底向上的语法分析的基本实现方法； LR（k）分析技术、SLR（k）分析表构造方法、LALR（k）分析表构造方法、识别程序的自动构造。重点：简单优先分析技术的实现、LR（k）分析技术。难点： LR（1）分析表的构造、消除文法的左递归。第一节 概述一、 自顶向

12、下分析技术及识别算法二、 讨论的前提三、 要解决的基本问题第二节 简单优先分析技术（自学）一、 优先关系与优先文法二、 简单优先分析技术三、 优先函数第三节 算符优先分析技术（自学）一、 算符文法二、 算符优先关系与算符优先文法三、 算符优先文法句型的识别四、 算符优先技术与简单优先技术的比较第四节 LR(K)分析技术四、 LR(K)文法与LR(K)分析技术五、 SLR(K)分析表构造方法六、 LALR(K)分析表构造方法七、 识别程序的自动构造思考题：1 什么是自底向上的语法分析法？2 LR（k）分析技术是什么？3 SLR（k）分析表构造方法是什么？4 LAL（k）分析表构造方法是什么？第六

13、章 语义分析与目标代码生成 学时：12学时（讲课8学时，实验4学时）了解语义分析的概念；理解属性文法和属性翻译文法的概念、抽象语法树、逆波兰表示法、四元式序列、三元式序列；掌握算术表达式的翻译、布尔表达式的翻译、条件语句和循环语句的翻译。了解说明部分的翻译；数组的翻译、过程语句和过程调用的翻译来阐述语法制导翻译模式和如何生成之间代码。本章讲授要点：属性文法、语义分析的概念、说明部分的翻译；目标代码的生成：虚拟机、控制语句的翻译；源程序的内部中间表示：抽象语法树、逆波兰表示法、四元式序列、三元式序列。、数组的翻译、过程语句和过程调用的翻译来阐述语法制导翻译模式和如何生成之间代码。重点：属性文法、

14、属性翻译文法、简单算术表达式和赋值语句的翻译、布尔表达式的翻译、条件语句的翻译、循环语句的翻译、数组的翻译、过程语句和过程调用的翻译。难点：语句的语法制导翻译、属性文法和属性翻译文法、常见的中间语言简介、简单算术表达式和赋值语句的翻译、布尔表达式的翻译、各种语句的翻译。第一节 概述一、 语义分析二、 属性文法三、 类型体制与语义分析第二节 说明部分的分析一、 常量定义的翻译二、 变量定义的翻译三、 函数定义的翻译四、 结构体类型的翻译第三节 目标代码的生成一、 概况二、 控制语句的翻译第四节 源程序的内部中间表示一、 抽象语法树二、 逆波兰表示法三、 四元式序列四、 三元式序列思考题：1 弄清

15、相关概念：注释分析树、综合属性、继承属性、依赖图等。2 控制语句的翻译要点十什么？3 类型表达式及其等价性是指什么？4 四元式序列与三式序列有何区别？第七章 运行环境 （自学2学时）了解运行环境的相关问题；理解存储分配策略：静态存储分配，栈式存储分配，堆式存储分配。本章讲授要点：运行环境的相关问题；存储分配策略：静态存储分配，栈式存储分配，堆式存储分配；符号表的引进、组织及数据结构；运行时刻支持系统。自学要求：在学习该章节内容时应该将实践环节中所用的相关存储技术加以考虑。重点：运行时的内存的划分、活动记录、运行时的分配策略。难点：栈式存储分配和堆式存储分配、存储组织、运行时的分配策略。第一节

16、引言第二节 存储分配策略一、 静态存储分配二、 栈式存储分配三、 堆式存储分配第三节 符号表一、 符号表的组织二、 符号表的数据结构第四节 运行时刻支持系统思考题：1 运行时内存如何划分？2 弄清各各存储分配策略。3 弄清概念：环境、状态、结合、悬空引用、运行时刻支持环境。第八章：代码优化 学时：4学时（讲课4学时，实验0学时）了解代码优化的含义。理解从语法制导阶段的优化方法到相对中间代码的优化方法：强度削弱、常数合并和常数传播、无用变量和无用代码删除。掌握以基本信息块和循环体内的代码优化来进行。本章讲授要点：代码优化的分类、代码优化程序的结构；基本块的优化、线性窥孔优化方法、基本信息块优化、

17、循环块的划分、循环内的优化。重点：线性窥孔优化，基于结构信息的优化、循环块的划分和循环优化。难点：基于结构信息的优化、循环块的划分。语法制导阶段的优化、线性窥孔优化及基本信息块的优化。第一节 概述一、 优化分类二、 代码优化程序的结构第二节 基本块与流图一、 基本块优化的种类二、 基本块优化的实现第三节 与循环有关的优化一、 循环优化的种类二、 循环优化的实现第四节 窥孔优化一、 冗余指令删除二、 控制流优化三、 代数化简思考题：1 代码优化分哪几类？2 弄清相关概念：基本块、流图、无环路有向图dag、公共子表达式、窥孔优化等。3 代码优化程序由几部分组成？各功能是什么？本课程对学生自学的要求

18、：由于本课程理论比较抽象，它是计算机专业课中教难学的课程。课堂上不一定能将问题完全弄懂，而课程内容前后相关，要求学生课后要进行复习。同时，该课程有上机实践，要求学生自己去复习C语言和数据结构方面的知识，独立完成4个上机实践。故该课程对学生自学能力要求较高。课时数分配表：章节 内 容 学时数第一章引论 4第二章前后文无关文法和语言 8（6+2）第三章词法分析 14（10+4）第四章语法分析（自顶向下） 6（6+0）第五章语法分析（自底向上） 16（10+6）第六章语义分析 12（8+4）第七章远行环境 0（自学）第八章代码优化 4（4+0）合计64（48+16）考核方式与要求：考核由平时成绩和期

19、末考试综合评价。其中，期末考试占成绩的70%，平时成绩占30%，平时成绩由作业、上机实验、课堂问答等3部分组成。参考书目：1张幸儿 编计算机编译原理 科学出版社 2003年第2版2蒋立源、康慕宁 编编译原理 西北工业大学出版社 2002年第2版3陈火旺、刘春林 等编编译原理 国防工业出版社 2001年第3版4吕映芝、张素琴 等编编译原理 清华大学出版社 2001年第15版5伍春香 编编译原理-习题与解析 清华大学出版社 2001年第1版编译原理实验大纲一、总则1本大纲的适用范围1）大纲相关的课程名称及课程属性数据结构，C语言程序设计，专业基础课2）本大纲的适用范围计算机科学技术专业3）实验总课

20、时16学时2本大纲的实验目的和要求性质： 编译程序课程的必须实践环节目的和要求：在弄懂编译原理理论的基础上，通过与课文内容的同步实验，训练学生分析、设计编译程序的动手能力，从而加深对编译程序课程各个部分学习和理解。3本实验课程的重点和内容1）从文件中读一行并将字符依次存入字符指针变量中；2）将一行字符串根据空格将单词分开；3）看单词中是否包含某些保留单词用；4）根据文法描述语言进行单词分类，并用状态转换图描述单词的识别过程；5）根据状态转换图编写词法分析程序；6）验证赋值语句中算术表达式的语法分析程序，条件语句或循环语句中的布尔表达式的LR分析程序；7）设计程序语句的LR分析程序；8）根据语言

21、的文法写出它的属性翻译文法；9）根据属性翻译文法在语法分析的基础上添加动作代码；4本大纲所需的实验设备奔腾PII以上、内存32MB以上、WINDOWS 2000、TUBRO-C 。二、实验项目及学时安排1. 实验项目一 简单的单词识别程序1） 实验类型：验证性与设计性实验2） 实验开设属性：必开实验3）学时数 ： 2课时4）实验目的：熟悉C操作环境，分析验证性实验程序的代码结构，了解如何从文件中逐行读数据到字符串变量中；掌握对符号串进行扫描以识别单词的编程技巧。5）实验要求： 熟悉 TUBRO-C系统环境。 能够设计简单的单词识别器2. 实验项目二词法分析器的设计1）实验类型：验证性与设计性实验2）实验开设属性：必开实验3）学时数 ： 4课时4）