《编译原理》教学大纲

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

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

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

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

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

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

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

8、FA 的最小化、正则表达式与正则集。词法分析程序的实现与编写，以及词法扫描程序的算法。重点 ：状态转换图、正则文法与状态转换图的互换、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 如何区别

11、带回溯自顶向下分析技术与无回溯顶向下分析技术？3 什么是分析表的构造方法？-4 什么是预测分析方法？第五章语法分析自底向上分析技术学时： 16 学时（讲课10 学时，实验6学时）理解自底向上的语法分析法及算法、自底向上的语法分析的基本实现方法；掌握LR 分析原理及组成、LR （ 0 ）项目集规范族的构造、LR （ 0 ）分析表的构造、SLR （ k ）分析表构造方法、 LAL （ k ）分析表构造方法、识别程序的自动构造。本章讲授要点：自底向上的语法分析法及算法、自底向上的语法分析的基本实现方法；LR （ k ）分析技术、SLR （ k ）分析表构造方法、LALR （ k ）分析表构造方法、识

12、别程序的自动构造。重点 ：简单优先分析技术的实现、LR （ k ）分析技术。难点 ： LR （ 1 ）分析表的构造、消除文法的左递归。第一节概述一、 自顶向下分析技术及识别算法二、 讨论的前提三、 要解决的基本问题第二节简单优先分析技术（自学）一、 优先关系与优先文法二、 简单优先分析技术三、 优先函数第三节算符优先分析技术（自学）一、 算符文法二、 算符优先关系与算符优先文法三、 算符优先文法句型的识别四、 算符优先技术与简单优先技术的比较第四节LR(K) 分析技术四、 LR(K)文法与LR(K)分析技术五、 SLR(K)分析表构造方法六、 LALR(K) 分析表构造方法七、 识别程序的自动

13、构造思考题：1 什么是自底向上的语法分析法？2 LR （ k ）分析技术是什么？3 SLR （ k ）分析表构造方法是什么？4 LAL （ k ）分析表构造方法是什么？第六章语义分析与目标代码生成学时： 12 学时（讲课8 学时，实验4 学时）了解语义分析的概念；理解属性文法和属性翻译文法的概念、抽象语法树、逆波兰表示法、四元式序列、三元式序列；掌握算术表达式的翻译、布尔表达式的翻译、条件语句和循环语句的翻译。 了解说明部分的翻译； 数组的翻译、 过程语句和过程调用的翻译来阐述语法制导翻译模式和如何生成之间代码。本章讲授要点：属性文法、语义分析的概念、说明部分的翻译；目标代码的生成：虚拟-机、

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

15、体类型的翻译第三节目标代码的生成一、概况二、控制语句的翻译第四节源程序的内部中间表示一、抽象语法树二、逆波兰表示法三、四元式序列四、三元式序列思考题：1 弄清相关概念：注释分析树、综合属性、继承属性、依赖图等。2 控制语句的翻译要点十什么？3 类型表达式及其等价性是指什么？4 四元式序列与三式序列有何区别？第七章运行环境（自学2学时）了解运行环境的相关问题；理解存储分配策略：静态存储分配，栈式存储分配，堆式存储分配。本章讲授要点： 运行环境的相关问题；存储分配策略：静态存储分配，栈式存储分配，堆式存储分配；符号表的引进、组织及数据结构；运行时刻支持系统。自学要求：在学习该章节内容时应该将实践环

16、节中所用的相关存储技术加以考虑。重点： 运行时的内存的划分、活动记录、运行时的分配策略。难点： 栈式存储分配和堆式存储分配、存储组织、运行时的分配策略。第一节引言第二节存储分配策略一、 静态存储分配二、 栈式存储分配-三、 堆式存储分配第三节符号表一、 符号表的组织二、 符号表的数据结构第四节运行时刻支持系统思考题：1 运行时内存如何划分？2 弄清各各存储分配策略。3 弄清概念：环境、状态、结合、悬空引用、运行时刻支持环境。第八章：代码优化学时： 4 学时（讲课4 学时，实验 0学 时 ）了解代码优化的含义。理解从语法制导阶段的优化方法到相对中间代码的优化方法：强度削弱、常数合并和常数传播、无

17、用变量和无用代码删除。掌握以基本信息块和循环体内的代码优化来进行。本章讲授要点：代码优化的分类、代码优化程序的结构；基本块的优化、线性窥孔优化方法、基本信息块优化、循环块的划分、循环内的优化。重点： 线性窥孔优化，基于结构信息的优化、循环块的划分和循环优化。难点： 基于结构信息的优化、循环块的划分。语法制导阶段的优化、线性窥孔优化及基本信息块的优化。第一节概述一、 优化分类二、 代码优化程序的结构第二节基本块与流图一、 基本块优化的种类二、 基本块优化的实现第三节与循环有关的优化一、 循环优化的种类二、 循环优化的实现第四节窥孔优化一、 冗余指令删除二、 控制流优化三、 代数化简思考题：1 代

18、码优化分哪几类？2 弄清相关概念：基本块、流图、无环路有向图dag 、公共子表达式、窥孔优化等。3 代码优化程序由几部分组成？各功能是什么？本课程对学生自学的要求：由于本课程理论比较抽象，它是计算机专业课中教难学的课程。课堂上不一定能将问题完全弄懂，而课程内容前后相关，要求学生课后要进行复习。同时，该课程有上机实践，要求学生自己去复习C 语言和数据结构方面的知识，独立完成4 个上机实践。故该课程对学生-自学能力要求较高。课时数分配表：章节内容学时数第一章引论4第二章前后文无关文法和语言8（ 6+2）14（ 10+4第三章词法分析）第四章语法分析（自顶向下）6（ 6+0）16（ 10+6第五章语

19、法分析（自底向上）12（ 8+4第六章语义分析）第七章远行环境0（自学）第八章代码优化4（ 4+0）合计64 （ 48+16）考核方式与要求：70% ，平时成绩占考核由平时成绩和期末考试综合评价。其中，期末考试占成绩的30% ，平时成绩由作业、上机实验、课堂问答等3 部分组成。参考书目：1张幸儿编计算机编译原理科学出版社 2003年第 2版2西北工业大学出版2002年第 2蒋立源、康慕宁编编译原理社版3等编编译原2001年第3版陈火旺、刘春林理国防工业出版社4吕映芝、张素琴等编编译原理清华大学出版社2001年第 15版5伍春香 编编译原理 - 习题与解析清华大学出版社2001年第 1版-编译原

20、理实验大纲一、总则本大纲的适用范围1）大纲相关的课程名称及课程属性数 据 结 构 ， C 语言程序设计，专业基础课2）本大纲的适用范围计算机科学技术专业3） 实验总课时16学时本大纲的实验目的和要求性质：编译程序课程的必须实践环节目的和要求：在弄懂编译原理理论的基础上， 通过与课文内容的同步实验， 训练学生分析、 设计编译程序的动手能力，从而加深对编译程序课程各个部分学习和理解。本实验课程的重点和内容）从文件中读一行并将字符依次存入字符指针变量中；）将一行字符串根据空格将单词分开；）看单词中是否包含某些保留单词用；）根据文法描述语言进行单词分类，并用状态转换图描述单词的识别过程；）根据状态转换

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