编译原理自学辅导书.doc

编译原理自学辅导书第一章绪论1.主要内容本章通过对编译原理课程的介绍，引出了编译程序的概念，着重讨论了编译程序与解释程序的区别，揭示了编译程序在计算机运行时的地位和作用；通过本章的学习，对编译程序的词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、错误检查和处理程序、各种信息表格的管理程序等八个部分的功能和作用有一定的了解；了解编译程序执行“遍”概念。2.学习要求识记编译程序的概念、编译程序与解释程序的区别，明确编译程序的八个组成部分，了解八个组成部分的功能和作用。3.重点、难点重点掌握编译程序的概念和编程程序的八个组成部分。4.考核形式主要以填空和改错的形式出现。第二章 前后文无关文法和语言1.主要内容本章通过对语言的解释，介绍了定义语言的三种方法；介绍了字母表、符号串和符号串集等概念，并介绍了求符号串的前缀、后缀、子串、长度、连接、方幂和字符串集的和、积、闭包的算法；通过文法推导的例子，引出了文法、语言、BNF范式、推导、归约的概念，说明了文法和语言的关系，介绍了求规范推导、规范归约的算法；通过递归的概念，介绍了递归文法的定义；通过树的概念，引出了语法树、子树、短语、简单短语、句柄、二义性的概念，并介绍了通过语法树求短语、句柄、简单短语，文法二义性的算法，通过推导和归约的方法求出语法树的方法；本章最后介绍了文法的四种分类，重点阐述了2型文法和3型文法。2.学习要求了解字母表、符号串、符号串集、递归、BNF范式、推导、归约、句子、句型等概念，了解符号串的前缀、后缀、子串、长度、连接、方幂和字符串集的和、积、闭包的求法；掌握文法、语言的定义；理解文法和语言的关系；理解什么是规范推导、规范归约；掌握规范推导、规范归约的算法，并能够求出对应的语法树；熟练掌握根据语法树求短语、简单短语、句柄的算法；通过给定文法，掌握求文法二义性的算法；了解文法的分类，并重点掌握2型文法和3型文法的定义。3.重点、难点二义性文法的算法：（1）文法既存在左递归，又存在右递归，则为二义性文法；（2）假设文法的一个句子，如果对此句子的推导存在两棵语法树，则为二义性文法。4.习题布置课后习题：2-7,2-115.考核形式填空、判断、推理、作图。第三章词法分析及词法分析程序1.主要内容本章通过对词法分析器的介绍，说明了词法分析器的作用，词法分析器的输入和输出、以及词法分析阶段的必要性；介绍了单词符合的内部表示，并简单说明了源程序输入和如何预处理程序；通过状态转换图的介绍，引入了如何由正则文法构造状态转换图，并由状态转换图表示正则文法的算法；通过状态转换图，引入了有限自动机的概念，说明了确定的有限自动机、非确定有限自动机和语言之间的联系，并介绍了有限自动机和状态转换图转换的算法；通过正则文法，引入了正则表达式和正则集的概念，并介绍了由正则文法构造相应正则表达式、由正则表达式构造有限自动机的算法；通过词法分析程序，介绍了lex程序的输入、输出和程序本身的构造。2.学习要求了解词法分析器的作用和词法分析阶段的必要性，单词符号的内部表示，了解状态转换图、状态转换矩阵、正则式、正则集、LEX的概念；理解确定的有限自动机、非确定的有限自动机和语言之间的联系；掌握词法分析器的输入和输出、LEX程序的输入、输出和基本构造；熟练应用正则文法、状态转换图、正则式、有限自动机相互转换的算法，3.重点、难点正则文法、状态转换图、正则式、有限自动机相互转换的算法：正则文法状态转换图，正则文法正则式；状态转换图可表示为有限自动机，非确定的有限自动机确定的有限自动机（状态转换图）正则式有限自动机（状态转换图）4.习题布置课后习题：3-9,3-12,3-225.考核形式填空、判断、推理、作图。第四章语法分析和语法分析程序1.主要内容通过对语法分析程序的介绍，引入了自上而下分析的三种方法和自下二上的三种分析方法；通过自上而下分析方法的介绍，引入了消除左递归和消除回溯的算法；通过递归下降分析法的介绍，引入了求FIRST集和求FOLLOW集、构造递归下降分析表和递归下降子程序框图的算法；通过LL(1)文法的介绍，引入了LL(1)分析器的构造、LL(1)分析表的构造以及采用LL(1)进行语法分析程序的算法；通过对自下二上分析方法的介绍引入了语法分析的一般方法；通过对简单优先分析法概念的介绍，说明了求简单优先矩阵和用简单优先分析法进行语法分析的算法；通过对算符优先文法的介绍，引入了素短语的概念，并介绍了构造算符优先矩阵和用算符优先矩阵进行语法分析的算法；通过LR分析法的介绍，引入了可归前缀、活前缀、项目有效项目集族的概念，并说明了构造LR分析器、构造有效项目集族的算法。2.学习要求了解语法分析的概念、各种分析方法的分析表的构造、各种分析方法的的进行语法分析的算法；了解自上而下和自下二上分析法进行语法分析的精髓；理解简单优先文法和算法优先文法的概念，掌握根据语法树求素短语、最左素短语、简单优先文法的符号比较、算法优先文法的符号比较的算法，掌握构造递归下降程序框图的算法；熟练应用消除左递归、F