《编译原理》使用手册.doc

编译原理网络课程用户使用手册一. 课程简介建立编译原理网络课程的目的不仅使学生掌握构造编译程序的原理和技术，而且能够使学生对该领域产生浓厚的兴趣和求知欲，为以后进一步从事软件工作打下良好的基础。主要内容涵盖了大学计算机系本科生所学内容，共十章，有编译概述，文法和语言，词法分析，语法分析，语法制导翻译，运行时刻环境的组织，中间代码生成，目标代码生成，代码优化，面向对象的语言的编译介绍。每章后附有习题，必做的习题给出了参考答案。最后讲解一个小的编译器的设计与实现，并给出了完整的用PASCAL书写的源代码。72学时，4学分。先修课程有计算引论、程序设计及数据结构。使用对象为计算机软件专业的本科生；希望学习编译原理的学生和工程技术人员或是讲授编译原理课程的教师。二. 系统安装本课件要求通用网络运行环境 ，不要求数据库。根据使用媒体不同有两种安装方式： 如果该课件需网络发布，通过互联网使用课件，则安装步骤如下：1. 把“编译课件”文件夹里面的所有文件及子文件夹拷贝到IIS的Web服务目录下面。2. 设置Web服务的起始页面为index.htm，其他均遵从IIS的默认配置就可以提供课件服务（由于本课件对路径采用的都是相对目录，因此无须对可见中的路径配置做任何改动）。 如果通过本机使用课件，则只需把“编译课件”下的所有文件及子文件夹拷贝到本地硬盘的任何位置即可。三. 与“4A网络课程教学平台”的挂接1在“4A网络课程支撑平台”所在目录的VCLASSNCOURSE子目录下，创建一个新文件夹，文件夹名称必须是英文，将编译原理网络课程所有内容拷贝至该文件夹。2打开“4A网络课程教学平台”的登录页面，以系统管理员身份登录，对该门课程进行配置。具体步骤如下：(1)点击导航栏“课程管理”菜单，出现图1：图1 课程管理界面(2)点击“添加新的课程”按钮，出现图2：图2 “添加新的课程”界面图2中为该门网络课程的中文名称。图2中为课件所在目录名称，即为NCOURSE目录下该课程的文件夹名称（必须是英文）。图2中为该课程首页文件名称。这三项配置好后，再进行交费、学分、专业、日期等选项的设置，检查无误后点击“添加”，编译原理网络课程在4A网络教学平台下配置完成，即可开始使用。3如何检查配置是否正确配置完成后再次点击导航栏“课程管理”，如图3：图3 课程管理界面页面上会出现这门网络课程，点击课件内容栏的“查看”，如出现正常首页页面，则配置成功，如无法显示，则返回上一配置页面进行检查。四学习方法 1 阅读学习指导：2 阅读正文；3 使用演示加深理解基本算法和原理；4 观看幻灯片，那是教师对正文的讲解和总结； 5 分析小编译实例； 6 自己做练习，和参考答案对照。7 在没有完全掌握时，选择上面的学习环节继续学习。五下面是关于课件使用界面的说明1. 总界面课件的内容组织横向上看，分成六部分：包括学习指导、学习内容、演示、习题、课堂、实例，可以通过点击首页的连接直接进入各个部分：图4 总界面2. 各部分界面例：学习内容部分图5 分界面1例：学习指导部分图6 分界面2例：习题与参考答案部分。要看参考答案，请点按钥匙按钮。图7 分界面33. 演示界面在需要时有使用说明。一般来说，对于学习本课程的读者来说，使用方法是一目了然的。本课件采用统一的傻瓜式层次界面，使用非常方便。图8 演示界面六最佳使用效果：看演示，最好用17吋显示器，使用全屏显示。七. 教学安排（学习指导）第一章 编译概述要求掌握的内容：1、编译方式、解释方式及其区别；2、编译程序的构成，工作流程及各部分的功能；3、编译程序中一遍扫描的概念。要求了解的内容：1、实现编译程序的自展技术；2、编译程序的伙伴程序及构造编译程序的工具；建议学习流程：沿着本章各节顺序1.1 翻译和解释1.2 编译程序的组成部分；1.3 有关编译程序的设计与实现；1.4 编译器的伙伴；1.5 构造编译器的工具。第二章 语言基本知识要求熟练掌握的内容：1、程序语言的形式描述，上下文无关文法和语言的形式定义，推导，句型，句子的概念；2、对程序语言来说，已知语言，能写出其文法；反之，根据文法，能描述出文法定义的语言；3、分析树，二义性，短语，直接短语，句柄，用分析树图示对符号串的推导，并解释上述概念。要求掌握的内容：1、符号串及其运算；2、2型和3型文法描述在程序语言中的对象。要求了解的内容：1、文法和语言的分类。学习难点：1、已知一个上下文无关语言，写出它的上下文无关文法；反之，已知一个上下文无关文法，描述出它定义的语言。建议学习流程： 21 串的集合（准备知识）； 22 文法和语言； 作业：21(a)(c)(d)(e)，23(a)(c)； 23 分析树和二义性； 作业：21(b)， 22, 2.3(b), 2.4, 2.5； 24 形式语言概观。第三章 词法分析要求熟练掌握的内容：1、 正规表达式与正则集合的定义，正规表达式的等价性；2、 DFA，NFA以及它们之间的转换方法，DFA的化简；3、 正规表达式转换成FA； 4、 词法分析器的功能及词法分析器模型；5、 词法分析器的手工构造：对于给定的程序语言，设计出它的词法分析器的输出，画出识别单词的DFA M ，并用某种程序语言实现它。 要求掌握的内容：1、 词法分析器的自动生成原理，对于给定的程序语言，用正规表达式描述出它的单词。要求了解的内容：1、词法分析器自动生成工具LEX和使用方法。学习难点：1、已知一个正规集，写出它的正规表达式；2、已知一个正规表达式,写出它的正规集； 3、正规表达式和有限自动机的等价变换。建议学习流程：观看演示1：“一个词法分析器的演示”；3.1 词法分析器的设计；3.2 词法分析器的构造；作业： 3.1、 3.2、 3.3、 3.4 3.3 有穷自动机 3.4正规表达式与有限自动机 观看演示7：“根据正规表达式生成NFA、DFA、最简DFA 作业： 3.5、 3.6、 3.7、 3.10、 3.11、 3.12、 3.13 3.5正规文法与有限自动机（FA）的等价性 作业：3.14 3.6词法分程序的自动构造工具第四章 语法分析要求熟练掌握的内容：1、语法分析分自顶向下分析和自底向上分析。自顶向下分析为输入串构造一个最左推导；自底向上分析为输入串构造一个最右推导；2、为构造预测的自顶向下分析文法应满足的条件；3、消除文法中的直接左递归和提取左公因子；4、求FIRST和FOLLOW集合；5、对于给定文法，构造预测的递归分析器和LL(1)分析表；6、句柄的概念和一般自底向上分析过程； 7、算符优先分析表（表达式）的构造和算符优先分析算法； 8、构造识别文法活前缀的DFA M； 9、构造LR(0), SLR(1), LR(1), LALR分析表。 要求掌握的内容：1、语法分析器的功能和模型；2、消除文法中的间接左递归；3、LL(1)分析和LR分析的驱动程序；4、利用二义性文法构造LR分析表；5、LALR(1)分析表的有效构造方法。 要求了解的内容：1、自顶向下的带回溯的分析方法；2、语法分析的自动生成工具Yacc及其使用方法。 学习难点：1、为构造预测的自顶向下分析方法，文法所应满足的条件；2、求FIRST和FOLLOW集；3、文法的等价变换；4、构造识别已知文法活前缀的DFA M；5、LALR(1)分析表的有效构造方法。 建议学习流程：演示1：自顶向下与自底向上分析4.1 语法分析器的作用；4.2 预测分析器；演示3：预测分析器对表达式的分析过程；4.3 书写文法；演示2：消除左递归；作业：4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.4 自顶向下的带回溯的分析方法简介；4.5 自底向上分析；作业：4.9演示4：算符优先分析法的分析过程；4.6 算符优先分析法；作业：4.10演示5：SLR分析器的分析过程；4.7 LR分析器；演示6：LR(0)项目集规范族的构造过程；作业：4.11 4.12 4.13 4.14 4.15 4.16 4.17 4.18 4.8 LR分析方法对二义文法的应用4.9 分析器的生成器Yacc作业：4.19 4.20 4.21 4.22第五章 语法制导翻译要求熟练掌握的内容：1、语法制导定义的形式，综合属性，继承属性，依赖图和属性值计算顺序的概念；2、建立表达式的语法树的语法制导定义；3、S-属性定义，S-属性定义中属性值的计算；4、L-属性定义，L-属性定义中的属性值的计算；5、翻译模式的作用，从语法制导到翻译模式的变换方法；6、从翻译模式中（仅含综合属性）消除直接左递归；7、预测递归翻译器的设计；8、构造一般程序语言的类型表达式；9、构造一般程序语言类型检查的翻译模式。要求掌握的内容：1、设计一般程序语言成份的语法树（例如程序，while语句等）；2、自底向上计算继承属性。3、类型等价中结构等价和名字等价的概念；要求了解的内容：1、消除翻译模式中的直接左递归（翻译模式中含继承属性）；2、基于分析树的一般属性值计算方法；3、语法制导定义中属性值计算的一般方法；学习难点：1、从L-属性定义变换到翻译模式；2、为构造预测递归翻译器，消除翻译模式中的直接左递归；3、按自底向上分析的次序计算继承属性值；4、类型的结构等价和名字等价及在实现类型分析中的区别。建议学习流程： 5.1 语法制导定义的形式； 演示1：继承属性的传递； 作业：5.1，5.3，5.4； 5.2 语法树的构造； 演示2：语法树的构造； 5.3 S-属性定义及其自底向上的计算； 演示3：S-属性定义及其自底向上的计算 作业：5.6； 5.4 L-属性定义； 作业： 5.2，5.5，5.8； 5.5：自顶向下翻译； 演示5：表达式9-5+2的分析树和依赖图 作业：5.7， 5.9，5.12； 5.6 自底向上计算继承属性； 演示4：具有综合属性和继承属性的简单的翻译模式的应用 作业：5.10, 5.15, 5.16 ； 5.8 类型分析； 作业：5.17, 5.18，5.19，5.20。第六章 运行时刻环境要求熟练掌握的内容：1、活动树，控制链，名字的绑定；2、运行时刻内存的布局划分，活动记录的结构，编译时把局部名字映射到活动记录的相对位上；3、静态存储分配策略的实现；4、栈式存储分配策略的实现；5、采用静态作用域规则的块结构语言实现访问非局部名字静态链（访问链）和DISPLAY表；要求掌握的内容：1、影响组织运行时刻环境的因素;2、高级语言分别满足什么条件,运行时分别采用静态存储分配，动态栈式分配，动态堆式分配；3、参数传递：值调用，引用调用，复制恢复。要求了解的内容：1、堆式存储分配策略的实现；2、动态作用域语言访问非局部名字；3、参数传递：名字调用；学习难点：1、程序语言中影响组织运行时刻环境的因素；2、运行时实现非局部名字的访问；3、设置调用序列和返回序列；4、参数传递：名字调用。建议学习流程： 6.1 有关源语言中的一些问题的讨论； 演示1：活动树演示 作业：6.1； 6.2 存储组织； 6.3 运行时刻存储分配策略； 演示2：控制栈演示 演示3：栈式存储分配演示 6.4 对局部名字的访问； 演示4：DISPLAY表的演示 作业：6.3，6.4； 6.5：参数传递； 作业：6.2；第七章 中间代码生成要求熟练掌握的内容：1、中间代码形式，DAG（有向无环图），语法树，后缀式，三地址代码（变形三元式，四元式）；2、说明语句的翻译模式，符号表中描述作用域信息，表项中属性域的设置，插入表项和查找表项的算法；3、赋值语句的翻译模式；4、数组元素的翻译模式；5、回填技术，goto语句的翻译；6、控制流语句的中间代码；7、使用回填技术翻译布尔表达式的翻译模式；8、使用回填技术翻译控制流语句的翻译模式；9、过程调用的翻译模式。要求掌握的内容：1、控制流语句中布尔表达式的语法制导定义； 2、控制流语句的语法制导定义； 3、CASE语句的翻译； 4、for语句的翻译。学习难点：1、符号表项中属性域的设置，符号表中作用域信息的描述； 2、数组元素的翻译模式； 3、使用回填技术，翻译控制流语句中的布尔表达式； 4、使用回填技术翻译控制流语句。 建议学习流程： 7.1 中间语言 作业：7.1 7.2 7.3 7.2 说明语句 演示1：计算说明语句中的名字的相对位置 演示2：处理嵌套过程中的说明语句 作业：7.4 7.3 赋值语句 演示3：简单赋值语句的翻译 演示4：对数组元素的翻译 作业：7.8 7.4 布尔表达式翻译 演示5：用于计值的布尔表达式的翻译 演示7：使用回填翻译布尔表达式 作业：7.5 7.5 CASE语句 7.6 回填 演示6：控制流语句的翻译 演示8：使用回填翻译控制流语句 作业：7.7, 7.8, 7.9 7.7 过程调用 第八章 代码生成要求熟练掌握的内容：1.采用栈式分配，调用序列和返回序列的目标代码，名字的地址表示；2.基本块的定义，基本块的划分；3.流图的定义，程序流图的构造算法；4.下次引用信息，求变量的下次引用信息的算法；5.寄存器描述器和地址描述器的作用；6.基本块的DAG表示；7.基本块的DAG构造算法。 要求掌握的内容：1.采用静态存储分配，过程调用和返回的目标代码2.目标机器的指令形式和指令开销；3.函数getreg算法；4.一个简单的代码生成器算法；5.从基本块的DAG生成目标代码。学习难点：1.求变量的下次引用信息的算法； 2.函数getreg算法；3.在构造和应用DAG中，指针、数组和过程调用的处理；4.从基本块的DAG构造目标代码。建议学习流程： 8.1 目标机器 8.2 运行存储管理 演示1：构造三地址代码的流图 8.4 下次应用信息 演示2：计算变量的下次引用信息 8.5 一个简单的代码生成器 作业：8.1 8.2 8.4 8.5 8.6 基本块的DAG表示法 作业：8.7 8.7 从DAG生成目标代码 第九章 代码优化要求熟练掌握的内容：9.1 引言中间代码改进的标准优化编译