《编译原理》教学大纲.doc
《《编译原理》教学大纲.doc》由会员分享，可在线阅读，更多相关《《编译原理》教学大纲.doc（11页珍藏版）》请在冰点文库上搜索。
《编译原理》教学大纲
大纲说明
课程代码：
3225003
总学时：
64学时（讲课48学时，实验16学时）
总学分：
4
课程类别：
学科基础课
适用专业:
计算机科学与技术（专业）
预修要求：
C语言程序设计、C++程序设计、数据结构
课程的性质、任务及地位：
《编译原理》是计算机科学与技术专业的一门重要基础课。
通过对该课程的学习，使学生掌握编译过程中的相关原理和编译技术，让学生能初步进行编译程序的开发和维护，同时促进提高学生开发软件的能力。
教学目的与基本要求：
本课程的目的，通过向学生讲述编译系统的结构、工作流程及编译程序各部分的设计原理和实现技术，使学生既掌握编译技术理论的基础与基本知识，也具有设计、实现、分析和维护编译程序等方面的初步能力。
本课程理论性较强。
因授课对象为工科学生，所以在强调编译系统的构造原理和实现方法的同时，为培养学生的实际工作能力，通过上机实践进一步加深学生对课堂教学内容的理解。
目的是要使学生牢固掌握相关的基本理论和基本方法，并能初步利用上述理论和方法解决简单实际问题。
教学方法和教学手段的建议：
在教学方法上，贯彻理论联系实际、“精讲、多练”的原则，进行案例式、启发式的教学，对于一些实际性较强的问题要多采用课堂讨论等方式，以提高学生的思辨能力和学习的主动性；引导学生读书、理解、体悟、运用相结合；提高学生的学习兴趣与热情，培养与发挥学生的提出、分析及解决问题的能力。
教学手段：
运用多媒体教学手段+黑板+上机实验的手段。
采取课堂讲授、课堂讨论、课后练习与自学等形式。
大纲的使用说明：
大纲对课程性质、目的等作简单说明，同时列出各章节要学习的知识点、重点、难点，便于教学时教授重点的安排和学生自学安排。
大纲正文
第一章引论 学时：
4学时（讲课4学时，实验0学时）
了解编译的概念；理解编译程序的各组成部分及功能。
本章讲授要点：
介绍程序设计语言与编译程序间的关系，主要内容包括：
各级程序设计语言的定义、源程序的执行、编译程序的构造、编译程序的分类、形式语言理论与编译实现技术的联系。
重点：
程序设计语言的定义，语法图及BNF表示法，编译程序的各阶段功能。
难点：
程序执行的方式、编译程序“趟”的概念。
第一节程序设计语言与编译程序的联系
一、源程序、程序设计语言的执行
二、编译程序的两种方式：
解释与编译
三、编译程序的定义
第二节编译程序构造及有关概念
四、程序设计语言的四个方面：
语法、语义、语用、语境
五、语法的定义：
语法图、BNF表示法、口语
六、程序执行的过程
七、编译程序的组成模块：
词法分析、语法分析、语义分析、代码优化、目标代码生成
八、“趟”的概念
九、编译程序的分类
第三节形式语言与编译实现技术
思考题：
1．编译原理的定义是什么？
2．编译原理由几部分构成？
各部分完成哪些工作？
3．在编译过程中“趟”的概念是指什么？
第二章文法与语言学时：
8学时（讲课6学时，实验2学时）
理解字母表的定义及闭包、符号串的基本知识及其运算、符号串集合概念及运算；掌握文法的形式定义、Chomsky语言的分类、文法等价及其等价变换方法、语法分析树与句型分析。
本章讲授要点：
字母表的定义及闭包、符号串的基本知识及其运算、符号串集合概念及运算、文法的形式定义、Chomsky语言的分类、文法等价及其等价变换方法、语法分析树与句型分析。
重点：
Chomsky文法的定义、文法和语言之间的关系、规范推导和规范规约、文法的二义性判定；文法的化简。
难点：
句型分析、文法的文法的二义性判定、文法等价及其等价变换方法。
第一节符号串与符号串集合
一、字母表的定义、字母表的闭包与正闭包
二、符号串及其运算
第二节文法与语言的形式定义
一、文法的形式定义、重写规则的表示形式
二、文法的定义、应用文法产生语言的句子
三、语言的形式定义
第三节语言的分类
一、Chomsky语言分类法
二、Chomsky的文法定义
三、上下文无关的讨论
第四节文法等价与等价变换
一、文法等价
二、压缩文法等价变换
三、消去单规则等价变换
四、消去左规则等价变换
第五节语法分析树与句型分析
一、语法分析树
二、句型分析
思考题：
1．弄清字母表、字符串集合、字符串闭包及正闭包的定义。
2．弄清文法、重写规则与语言之间的关系。
3．Chomsky语言类有几类？
各有什么特点？
4．什么是无用规则，如何消除？
5．弄清在推导语法树中，弄清句型、短语、简单短语、句柄以及句子的概念。
第三章词法分析学时：
14学时（讲课10学时，实验4学时）
了解词法分析的目标和实现方法、词法分析器的目标是识别源程序中的各个单词。
理解确定有限自动机的组成和非确定有限自动机的组成。
掌握状态转换图、状态转换图与正则文法的相互转换、确定有限自动机和非确定有限自动机、NFA转DFA、DFA的最小化、正则表达式与正则集、正规式转DNF。
本章讲授要点：
词法分析器的目标是识别源程序中的各个单词。
词法分析可以通过确定有限自动机来完成。
：
状态转换图、状态转换图与正则文法的相互转换、确定有限自动机和非确定有限自动机、NFA转DFA、DFA的最小化、正则表达式与正则集。
词法分析程序的实现与编写，以及词法扫描程序的算法。
重点：
状态转换图、正则文法与状态转换图的互换、NFA转DFA、DFA的最小化。
正则表达式与状态转换图。
难点：
NFA转DFA、DFA的化简、正则文法与正则表达式。
第一节引言
一、词法分析的任务、词法分析程序
二、符号的识别与重写规则的关系
三、词法分析的实现方式
第二节正则表达式与有穷状态自动机
一、状态转换图、状态转换系统
二、确定有穷状态自动机DFA
三、非确定有穷状态自动机NFA
四、DFA的化简
五、正则表达式
第三节词法分析程序的实现
一、单词与属性字
二、标识符的处理
三、词法分析程序的编写
第四节词法分析程序的自动生成
一、基本思想
二、扫描程序与构造程序
三、自动生成系统LEX
思考题：
1．词法分析的功能是什么？
2．什么是状态转换图、NFA、DFA？
3．如何将NFA转换为DFA？
4．如何简化DFA？
5．正则表达式与DFA有何关系？
第四章语法分析——自顶向下的语法分析技术学时：
6学时（讲课6学时，实验0学时）
了解语法分析的功能和两中大的分析方法：
自顶向下的语法分析法和自下而上的语法分析。
理解自上而下的分析方法---从文法的开始符号推导出句子本身的分析方法，自下而上的分析方法—从语句归约为文法开始符号的分析原理。
掌握FELLOW（）和FIRST（）的算法、预测分析表的构造和预测分析过程。
本章讲授要点：
自顶向下的语法分析法带回溯自顶向下分析技术、无回溯顶向下分析技术及其算法、递归下降分析法和预测分析法，预测分析法的文法要求、分析表的构造方法、预测分析方法。
重点：
无回溯的递归下降分析技术与预测分析法。
难点：
LL
（1）文法的判定、预测分析法、递归下降分析法。
第一节引言
一、自顶向下分析技术及识别算法
二、讨论的前提
三、要解决的基本问题
第二节带回溯的自顶向下分析技术
一、基本思想
二、实现算法及举例
三、问题及其解决
第三节无回溯的自顶向下分析技术
一、先决条件
二、递归下降分析技术
三、预测分析技术
思考题：
1．何为自顶向下分析技术？
2．如何区别带回溯自顶向下分析技术与无回溯顶向下分析技术？
3．什么是分析表的构造方法？
4．什么是预测分析方法？
第五章语法分析——自底向上分析技术学时：
16学时（讲课10学时，实验6学时）
理解自底向上的语法分析法及算法、自底向上的语法分析的基本实现方法；掌握LR分析原理及组成、LR（0）项目集规范族的构造、LR（0）分析表的构造、、SLR（k）分析表构造方法、LAL（k）分析表构造方法、识别程序的自动构造。
本章讲授要点：
自底向上的语法分析法及算法、自底向上的语法分析的基本实现方法；LR（k）分析技术、SLR（k）分析表构造方法、LALR（k）分析表构造方法、识别程序的自动构造。
重点：
简单优先分析技术的实现、LR（k）分析技术。
难点：
LR
（1）分析表的构造、消除文法的左递归。
第一节概述
一、自顶向下分析技术及识别算法
二、讨论的前提
三、要解决的基本问题
第二节简单优先分析技术（自学）
一、优先关系与优先文法
二、简单优先分析技术
三、优先函数
第三节算符优先分析技术（自学）
一、算符文法
二、算符优先关系与算符优先文法
三、算符优先文法句型的识别
四、算符优先技术与简单优先技术的比较
第四节LR（K）分析技术
四、LR（K）文法与LR（K）分析技术
五、SLR（K）分析表构造方法
六、LALR（K）分析表构造方法
七、识别程序的自动构造
思考题：
1．什么是自底向上的语法分析法？
2．LR（k）分析技术是什么？
3．SLR（k）分析表构造方法是什么？
4．LAL（k）分析表构造方法是什么？
第六章语义分析与目标代码生成学时：
12学时（讲课8学时，实验4学时）
了解语义分析的概念；理解属性文法和属性翻译文法的概念、抽象语法树、逆波兰表示法、四元式序列、三元式序列；掌握算术表达式的翻译、布尔表达式的翻译、条件语句和循环语句的翻译。
了解说明部分的翻译；数组的翻译、过程语句和过程调用的翻译来阐述语法制导翻译模式和如何生成之间代码。
本章讲授要点：
属性文法、语义分析的概念、说明部分的翻译；目标代码的生成：
虚拟机、控制语句的翻译；源程序的内部中间表示：
抽象语法树、逆波兰表示法、四元式序列、三元式序列。
、数组的翻译、过程语句和过程调用的翻译来阐述语法制导翻译模式和如何生成之间代码。
重点：
属性文法、属性翻译文法、简单算术表达式和赋值语句的翻译、布尔表达式的翻译、条件语句的翻译、循环语句的翻译、数组的翻译、过程语句和过程调用的翻译。
难点：
语句的语法制导翻译、属性文法和属性翻译文法、常见的中间语言简介、简单算术表达式和赋值语句的翻译、布尔表达式的翻译、各种语句的翻译。
第一节概述
一、语义分析
二、属性文法
三、类型体制与语义分析
第二节说明部分的分析
一、常量定义的翻译
二、变量定义的翻译
三、函数定义的翻译
四、结构体类型的翻译
第三节目标代码的生成
一、概况
二、控制语句的翻译
第四节源程序的内部中间表示
一、抽象语法树
二、逆波兰表示法
三、四元式序列
四、三元式序列
思考题：
1．弄清相关概念：
注释分析树、综合属性、继承属性、依赖图等。
2．控制语句的翻译要点十什么？
3．类型表达式及其等价性是指什么？
4．四元式序列与三式序列有何区别？
第七章运行环境（自学2学时）
了解运行环境的相关问题；理解存储分配策略：
静态存储分配，栈式存储分配，堆式存储分配。
本章讲授要点：
运行环境的相关问题；存储分配策略：
静态存储分配，栈式存储分配，堆式存储分配；符号表的引进、组织及数据结构；运行时刻支持系统。
自学要求：
在学习该章节内容时应该将实践环节中所用的相关存储技术加以考虑。
重点：
运行时的内存的划分、活动记录、运行时的分配策略。
难点：
栈式存储分配和堆式存储分配、存储组织、运行时的分配策略。
第一节引言
第二节存储分配策略
一、静态存储分配
二、栈式存储分配
三、堆式存储分配
第三节符号表
一、符号表的组织
二、符号表的数据结构
第四节运行时刻支持系统
思考题：
1．运行时内存如何划分？
2．弄清各各存储分配策略。
3．弄清概念：
环境、状态、结合、悬空引用、运行时刻支持环境。
第八章：
代码优化学时：
4学时（讲课4学时，实验0学时）
了解代码优化的含义。
理解从语法制导阶段的优化方法到相对中间代码的优化方法：
强度削弱、常数合并和常数传播、无用变量和无用代码删除。
掌握以基本信息块和循环体内的代码优化来进行。
本章讲授要点：
代码优化的分类、代码优化程序的结构；基本块的优化、线性窥孔优化方法、基本信息块优化、循环块的划分、循环内的优化。
重点：
线性窥孔优化，基于结构信息的优化、循环块的划分和循环优化。
难点：
基于结构信息的优化、循环块的划分。
语法制导阶段的优化、线性窥孔优化及
基本信息块的优化。
第一节概述
一、优化分类
二、代码优化程序的结构
第二节基本块与流图
一、基本块优化的种类
二、基本块优化的实现
第三节与循环有关的优化
一、循环优化的种类
二、循环优化的实现
第四节窥孔优化
一、冗余指令删除
二、控制流优化
三、代数化简
思考题：
1．代码优化分哪几类？
2．弄清相关概念：
基本块、流图、无环路有向图dag、公共子表达式、窥孔优化等。
3．代码优化程序由几部分组成？
各功能是什么？
本课程对学生自学的要求：
由于本课程理论比较抽象，它是计算机专业课中教难学的课程。
课堂上不一定能将问题完全弄懂，而课程内容前后相关，要求学生课后要进行复习。
同时，该课程有上机实践，要求学生自己去复习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）
考核方式与要求：
考核由平时成绩和期末考试综合评价。
其中，期末考试占成绩的70%，平时成绩占30%，平时成绩由作业、上机实验、课堂问答等3部分组成。
参考书目：
1．张幸儿编《计算机编译原理》科学出版社2003年第2版
2．蒋立源、康慕宁编《编译原理》西北工业大学出版社2002年第2版
3．陈火旺、刘春林等编《编译原理》国防工业出版社2001年第3版
4．吕映芝、张素琴等编《编译原理》清华大学出版社2001年第15版
5．伍春香编《编译原理---习题与解析》清华大学出版社2001年第1版
《编译原理》实验大纲
一、总则
1．本大纲的适用范围
1）大纲相关的课程名称及课程属性 数据结构，C语言程序设计，专业基础课
2）本大纲的适用范围 计算机科学技术专业
3） 实验总课时 16学时
2．本大纲的实验目的和要求
性质：
编译程序课程的必须实践环节
目的和要求：
在弄懂编译原理理论的基础上，通过与课文内容的同步实验，训练学生分析、设计编译程序的动手能力，从而加深对编译程序课程各个部分学习和理解。
3．本实验课程的重点和内容
1）从文件中读一行并将字符依次存入字符指针变量中；
2）将一行字符串根据空格将单词分开；
3）看单词中是否包含某些保留单词用；
4）根据文法描述语言进行单词分类，并用状态转换图描述单词的识别过程；
5）根据状态转换图编写词法分析程序；
6）验证赋值语句中算术表达式的语法分析程序，条件语句或循环语句中的布尔表达式的LR分析程序；
7）设计程序语句的LR分析程序；
8）根据语言的文法写出它的属性翻译文法；
9）根据属性翻译文法在语法分析的基础上添加动作代码；
4．本大纲所需的实验设备
奔腾PII以上、内存32MB以上、WINDOWS2000、TUBRO-C。
二、实验项目及学时安排
1.实验项目一简单的单词识别程序
1）实验类型：
验证性与设计性实验
2）实验开设属性：
必开实验
3）学时数：
2课时
4）实验目的：
熟悉C操作环境，分析验证性实验程序的代码结构，了解如何从文件中逐行读数据到字符串变量中；掌握对符号串进行扫描以识别单词的编程技巧。
5）实验要求：
①熟悉TUBRO-C系统环境。
②能够设计简单的单词识别器
2.实验项目二 词法分析器的设计
1）实验类型：
验证性与设计性实验
2）实验开设属性：
必开实验
3）学时数：
4课时
4）实验目的：
掌握词法分析器的简单设计。
根据文法描述语言进行单词分类，并用状态转换图描述单词的识别过程；根据状态转换图编写词法分析程序。
5）实验要求：
①了解验证性程序中对整数与标识符是如何区分的；
②掌握词法分析器的程序设计技巧。
③分析状态转换图与语言中单词的联系；掌握根据状态转换图编写词法分析程序的方法。
3.实验项目三 语法分析器
1）实验类型：
验证性实验
2）实验开设属性：
必开实验
3）学时数：
6课时
4）实验目的：
了解语法分析的作用及基本过程；掌握LR分析方法中LR分析表的构造、LR分析程序的编写；
5）实验要求：
①对算术表达式文法进行语法分析，判断输入的表达式是否正确。
E:
:
=E+E|E*E|（E）|i
②程序分析过程中建立两个栈：
符号堆栈和状态堆栈。
状态栈保留的是状态信息，而符号栈中保留的是源程序语句中已经分析的符号。
③利用LR分析法写出程序语句的语法分析代码
④根据LR分析表，补充lrparse（）程序中的移进和归约操作。
程序调试后验证各种语句的分析是否正确。
并在实验报告中写出程序代码、验证源文件的输出结果
4.实验项目四 中间代码生成
1）实验类型：
设计性实验
2）实验开设属性：
必开实验
3）学时数：
4课时
4）实验目的：
了解常见的语句、表达式的翻译；了解常见的中间语言，掌握对于给定文法进行语法制导翻译技术。
5）实验要求：
①了解常见的语句、表达式的翻译；了解常见的中间语言；对于给定文法，能进行语法制导翻译
②对某语言按要求完成：
自行完成对文法的“拆分”和语义动作的编写；
③利用实验项目三中完成的语法分析程序插入语法制导翻译的属性计算动作子程序。
④使语法分析程序运行后能生成中间代码—用四元式表示
升级会员 