编译原理复习提纲整理

1、说明1. 这份资料的最初来源是王金伟老师给大家发的复习提纲， 我在 下面会给大家附一份原版，后面的 21 面资料是在那个的基础上 整理和细化得到的。 最初做这份资料的目的是我本人作为班长为 了帮助我们班的同学顺利通过考试而整理的。 听王老师说有想法 留给学弟学妹们用，我放假后又对一些内容进行了修正和改进， 得到了大家看到的这个版本2. 这份资料加入了很多我个人的理解。 与原提纲相比， 我增删了 一些内容，并对某些内容进行了调序与合并。3. 这份资料融入了老师平时上课的以及最后复习课给的， 更重要 的是我个人的理解和猜测。 大家或许都有感受， 觉得编译原理书 上或者上说的句子根本看不懂。 针对这

2、个问题， 我把很多晦涩难 懂的形式化的算法通过我的理解后用比较形象易懂的话表述了 出来，表述得可能并不科学严谨， 但我的目的是为了能帮助大家 做题和考试4. 里面的每一个考点我都在最后用括号加了注释， 方便不同起点 不同准备时间的同学进行选择，这里简单说明“了解” ：代表这一部分的内容被老师列在提纲内， 但其实并不 太影响大家对大题的计算； 并且据我的分析也并不太可能出小题 所以时间很紧的同学可以略看就好，当然看看还是有好处的。“小题” 一类的字样代表这一块的知识点值得出填空选择， 大家 有时间应该理解性的记忆下来 （在 2012 年的期末考试上，选择 为 1 分*10 题；填空为 1 分*1

3、0 题，判断改错为 2 分*5 题，小题 总计 30 分）“简答” ：老师在最后复习课上说过编译原理是有简答题的， 简 答不同于计算， 很可能是让你默写一些步骤。 所以这一块内容大 家需要背诵， 即使不理解也要背下来 （在 2012 年的期末考试上， 简答题的分值为 5 分*4 题=20 分“铺垫”“大题步骤” 等代表这一块的内容对于综合大题的做 题是必须了解的， 或者其实就是做大题的分解步骤， 这些块的内 容是所有人必须看懂并且记下来的“实际大题” ：总共列出的有 4 道，应该每年考察的都会是这 4 中题型， 每一道的分值都在 1215分左右， 是所有人想通过考试 所必须攻克的。 这里通常我

4、会标出他需要用到之前的哪些哪些知 识点（ 2012 年期末考试 4 道题的总分值为 50 分）5. 如果大家想去打印， 最好在装有 2007 及以上的机器上打印， 否则有些符号可能会显示不出来。建议大家去生活广场找机器 打，不要去景元鸿6. 由于时间仓促， 这份资料做的并不完善和严谨， 难免有错漏之 处，希望大家谅解。大家可以一边看我的这份资料，一边看老师 最后给的两套， 课本来不及就别看了。 真心希望这份资料能对大 家有用，祝大家都考得好。最后说一句， 我们去年编译原理考得好的人挺多的， 其实也不是 很难，没有人挂！本人惭愧，只有 89，考得比我好的多太多了。 总结原因是把时间花在了研究大题

5、上面， 小题的很多知识点都没 有背熟，随便错了几个小题就基本和 90 无缘了。10 计 1 王成正2012/7/9（老师给的提纲原版）一、 概述1. 编译方式与解释方式区别：是否生成目标代码2. 编译程序总框架二、 词法分析1. 状态转换图的功能：识别（接受）一定的符号串（单词）2. 状态转换图的程序实现的思路：为每个状态结点都编写一 个子程序3. 字母表的概念：一般用刀表示4. 闭包的概念：闭包V*中的每个字都是由V中的字经过若干次连接而成的5. 正则闭包的概念：是 V上所有符号串的集合6. 刀*定义：表示刀上所有字的全体，空字E也包括在其中7. 刀+空字£不包含，非 £

6、8. £, , £ 之间的区别9. £所对应的正规集为 £ 10. 正规式与正规集的定义：知道如何用正规式表示一个正规 集11. 简述和的定义与区别12. 若M的某些结点既是初态结点又是终态结点，或者存在一条从某初态结点到某个终态结点的£通路，那么空字£可为M所识别13. 正规式与优先自动机的等价性14. 定理2.对于刀上的每一个正规式V,存在一个刀上的M ,使得 L(M)(V)15. M的化简的概念和方法：终态和非终态是可区别的，因 为终态可以读出空字 £，而非终态不能读出空字 £16. 课后作业一个例题17.

7、构造一个，它接受刀=x , y上所有倒数第二个字符为y的字符串语法分析(1)基本定义1. 上下文无关文法的定义2. 句型、句子的概念3. 文法和语言的对应关系，给出文法构造语言，文法G产生的句子的全体是该文法的语言4. 语法分析树与二义性：判断文法的二义性方法：如果一个 文法含有二义性的句子 （对应两棵不同的语法树） ，则称该 文法是二义性文法5. 3 型文法是正规文法、正则文法、线性文法6. 2 型文法也称为称为上下文无关文法7. 若一个文法是递归的，则由它产生的语言的句子个数是无限的（2）自上而下8. 文法左递归的定义9. 消除文法的左递归的方法：直接左递归10. 消除回溯的方法：提取公共

8、左因子11. 递归下降分析法的概念，应满足什么条件？12. 递归下降法对文法的每个非终结符构造一个相应的子程序13. 预测分析法：给文法构造预测分析表：消除左递归、消除回溯、集、集。举例子时，便成 Sf（ T）（ 3 ）自下而上14. 短语、直接短语的概念15. 句柄的概念（一个句型的最左直接短语）16. 规范归约（最左） 、规范推导（最右） 、规范句型17. 规范归约的关键问题是寻找句柄18. 在规范归约中，可归约串必出现在栈顶19. 算符文法、算符优先文法的概念，如何判断20. 构造算符优先关系表、 、集合，可不考虑 #号21. 素短语：算符优先归约的关键问题是寻找最左素短语22. 算符优

9、先法尤其适用于表达式的分析23. 给出文法 G（P）X fY fZ f24. 该文法是否为算符优先文法？请根据、集合构造算符 优先关系表说明之（ 12 分）25. 优先函数的优点：便于比较，节省空间26. 优先函数的构造方法27. 欲构造行之有效的自上而下分析器， 则必须消除文法中 含有的左递归28. 分析法属于自底向上分析方法29. 从文法出发构造（ 0）分析表的步骤四、语义分析1. 综合属性和继承属性概念五、中间代码生成1. 中间代码是一种面向语法， 易于翻译成目标代码的代码2. 后缀式（逆波兰式）的概念3. 逆波兰式中各运算法出现的顺序与实际运算顺序一致4. 后缀式与抽象语法树（表达式树

10、）的关系5. 的含义6. 四元式表示方法， 联系时通过临时变量， 可以翻译各种 语句7. 将赋值语句表示成后缀式和四元式 六、代码优化1. 简述代码优化的原则与优化的级别， 并列举三种常用的 优化技术2. 基本块、流图的概念，如何画、节点对应基本块3. 局部优化的方法，是对基本块进行优化的有效工具4. P285 中间注意5. 不变运算的代码外提的条件6. 循环优化中的强度削弱的含义七、目标代码生成1. 编译程序生成的目标程序种类一：概述1. 编译方式与解释方式区别（小题）在于是否生成目标代码，编译方式生成了目标代码2.编译程序总框架（简答题，背！）（字符串）表格 管 理错理目标程序二：词法分析

11、1状态转换图的功能：（较重要铺垫）串（单词）上图是一个很简单的状态转换图。上图代表：状态0通过X弧可以转换到状态1,通过Y弧可以转换到状态22.字母表的概念：（较重要铺垫）一个由有限元素组成的集合，每个元素称为一个符号或一个字，一般用刀表示一个字母表例：刀=a , b , c兀素：a, b, c字母表中的字可拼接在一起构成一个序列，如等，符号的顺序不同所代表的序列也不同不包含任何字符的序列称为空字，用£来表示另外有几个概念必须先了解：字（符号串 ） 的连接设 x 和 y 是两个字 （ 符号串 ），则定义为他们的连接 例：和连接是注: （1） £（空字）是连结运算的恒等元素

12、£ x = x£ = x（2） 字（符号串 ） 的 n 次连接=X规定 x0 = £1 2 3x = x， x ， x=集合的 （连接 ）积设U和V是两个“字（符号串）的集合”，则定义为他们的 （连接）积 U 且 y V例：设 a, , b, ,则, , , 集合V的n次（连接）积记为：=V V V Vn 个规定 V 0= £例：设 a, b ，那么V）= £ V1= V3. 闭包的概念：（较重要铺垫）设V是一个字（符号串）的集合，则V的闭包定义为V ,V* = V 0 U V1u 寸 U 注：闭包V中的每个字都是由 V中的字经过有限次连接 而

13、成的正则闭包的定义为*闭包与正则闭包的差别在于， 闭包里是含有£的，因为闭 包里有集合V3,而正则闭包由于在闭包的基础上又连接了 一个V,所以正则闭包里是没有空字 £的。刀*定义：表示刀上所有字的全体，空字£也包括在其中刀+表示刀上所有字的全体，但不包括£4. £, , £ 之间的区别（小题）£空字：表不包含任示何字符的序列称 :表示一个空集 £ :表示含有空字£的集合5. 正规式与正规集的定义：(较重要铺垫)我们可以把具有相同特征的字放在一起组成一个集合，即所谓的正规集然后使用一种形式化的方法来表示正规

14、集，即所谓的正规式正规式是描述单词结构的一种形式；正规集是该类单词的全集。举例对于下面的例子，大家应该好好思考一下后面 4个的含义， 对做大题是很有帮助的。做大题时，题目通常会给你一个 实际问题，你需要先把他要实现的功能抽象成一个正规集， 再用正规式表达出来，才能继续做后面的步骤。正规式正规集aabba|bab(a|b)(a|b) aa.ab.ba.bb a*(> a, aa, 任意个a的串(a|bf& a, bt aa, ab,所有孔b组成的串ba*b, ba, baa, baaa,a(alfef工上以a为首的字的全体(a|br(aalbbHa|b)*上含有阴或bb的字的全体&

15、#163;所对应的正规集为 £ 6. 简述有限自动机和的定义与区别(重要铺垫) 代表非确定的有限自动机；代表确定的有限自动机所谓的有限自动机，大家一定觉得这个概念坑爹死了。其 实他并不代表任何实体的机器，只是一种数学模型而已。 就像函数、数列是一种数学模型一样。函数通过函数表达 式实现他的功能：你给他一个自变量，他能根据表达式求 出因变量的值。而有限自动机是通过状态转换图来实现功 能，你给他一个初始状态和一个输入符号，他能根据你输 入的这个符号将原状态转换到另一个状态，用他来模拟计 算机的识别功能。下面简单介绍一下 （确定的有限自动机） 的五元式表示法： （重要）定义：一个确定有限自

16、动机（）M是一个五元式：M = （S,刀,f, so, F），其中1） S 是一个有限的状态集合， 它的每个元 素我们称为一个状态2）刀是一个有穷的输入符号的字母表，它的每个元素我们称为一个输入字符3）f是从SXE S的单值部分映射4）So是S的一个兀素，为初始状态，它是 唯一的5）状态集合 F 是终止状态的集合， 它是 S 的子集（可空）M = （S,刀,f, SO, F） ，其中S是一个有限的状态集合，它的每个元素我们称为一个状 态刀是一个有限的输入符号的字母表，它的每个元素我们 称为一个输入字符f是从Sx" * f 2S的部分映射，其中，2S表示S的幂 集合（所有S的子集组成的

17、集合）（f是非单值的cM是非 确定）状态集合SO是初始状态集合，它是S的子集状态集合F是终止状态的集合，它是 S的子集注：和的区别在于（3）和（4）,其他几点都差不多，这是 有可能出简答题的，大家要记住他们的区别和联系7的识别功能（小题）对于刀*中任何字a,如果存在一条从初态结点到某个终态 结点的道路，这条路上所有的标识符连成的字等于a,则a可被M所识别（接受，读出）若M的某些结点既是初态结点又是终态结点，或者存在一 条从某初态结点到某个终态结点的£通路，那么空字£可为M所识别8状态转换图的分裂规则（大题步骤）例子：（这里Y有两个圈圈代表他是最终状态的点 ）Koji/ioi

18、©<9 C01ETO 設OK汽）划到最后要求每条弧上都只有一个字母或者数字9. £ 和=£ （J）的构造方法（大题步骤）这里先需要了解几个定义我们假设有某个状态集I，这个集合中含有不同的 状态。定义1状态集I的a弧转换：（I, a ） 是一个状态集，是从I中的状态出发经过 一 条a弧到达的状态的全体。定义2状态集I的£ （空字）闭包：£ （ I ）是一个状态集，由两部分组成:状态集I中的所有原状态。从I中的状态出发经过 任意条E弧，所能到达的状态的全体。定义 3=£ ( ( I, a )是一个状态集。下面给出一个实例：例：有如下

19、一个状态转换图假定1, 2，求=?()=5,4,3£ (J) =5,4,3,627,8(即先做a弧转换，将求得的状态再求空字闭包)本知识点旨在让大家掌握在知道了I这个状态集合后，怎样求10. 如何用子集法将非确定的有限自动机确定化(大题步骤)方法：先画一张表& (SO) ABCBDECFG1. 这张表的首行上首列上固定是大写字母I2. 表格后面有几列，取决于这个有限自动机的输入符号数量，有几个输入符号就有几列，这里假设的下标a b代表这个有限自动机的输入符号3. 第二行的第一列也是固定的，SO代表的是这个有限自动 机的初始状态,即求SO的空字闭包，我们假设求出来的状 态集合是

20、A4将A所对应的 分别求出来，我们假设是 B和C5. 如果B和C都分别于A不同，需要将B, C作为新的状态 集合加入到第一列中6. 继续求出B和C所对应的 ，再检验：对于这四个状态 集合，有没有与是不同的，如果有，加入到第一列的下面， 再继续计算，如果与前面的相同就不再需要加入了。7. 按照这样的方法一直进行下去，知道第一列不再有新的 状态集合加入了，这个表就构造好了。8. 再画一张表，与上面的表相对应Sab01213424332149. 对于上面这种表的构造方法很简单，大家也可以不另外画表，而直接标在原来的表中这种表来源是，在原来表的第一列上分别表上 S01234 ， a和b不变，然后按照第

21、一列中数字所对应的状态集，依 次对应在后面的列上标上相应数字。例如第一列中B对应1，C对应2，那么将第二列第二行中的 B也标上1，第三 列第二行中的C标上2,等等。10. 画出下面的这个表或在原表中标好后，就可以按照这个表画出状态转换图了，例如，0状态通过a弧转换成1状 态，通过b弧转换成2状态；1状态通过a弧转换成3状 态，通过b弧转换成4状态，等等。画出这个状态转换图 后，就完成了一个非确定有限自动机的确定化。11. 有限自动机的化简（大题步骤）分析：这是一块用文字很难表述清楚的内容，并且在实际 的化简中如果题目难度大是很容易出错的，但是期末考试 通常不会太复杂，整体的思路如下：1. 将第

22、10步中得到的已经确定的中的所有状态分为 两组，一组为终态节点，一组为非终态节点。需要补 充的是，在上一步构造的表格中，s那一列的节点哪 些是终态哪些是非终态呢？这需要看你最初构造的正 规式中的哪个是终态节点了。例如在下面的 12 中， Y 为终态节点，那么在以上的表格中只要是含有 Y 元素 的状态集合都将成为终态集。2. 将每个分组检验， 看他们是否还能分割， 检验的方法 实在难以用文字描述清楚， 请大家看下面的实际例题， 自己领会。3. 每个分组都不能再分割后， 若还含有大于 2 个元素的 分组，则这个分组中的所有状态都是等价的，可以用 其中的一个代替他们，代替的方法是：假设用状态 1 代

23、替状态 2，则把状态 2 及其引出去的弧全部删去， 并把原来指向状态 2 的弧指向状态 1 下面是老师复习上的一个例子， 这是一个较为复杂的例 子，可能会看不懂，大家多问一问周围会的同学，期 末考试时，肯定不会出这么复杂，通常在将终态节点 和非终态节点区分开后，剩下的就已经快分好了，所 以大家不用太担心，化简也是有可能不考察的，大家 看清题目要求。例：J=2J=2J=3把DFAM5进行化简解： 状态集分为两组：终态结点5非终态结点0, 1, 2, 3, 考察0, 1, 2, 3, 4因为，0. 1, 2, 3, 40 = 2,4匚0,4,234J=2,40, 1, 2, 3, 41=1,3,5

24、(20,1,2,3,440,3,5所以，0, 1, 2, 3, 4可再分，分成0,1,2,3和4 考察0, 1, 2,3因为，0,1,2,30= 2, 4U0, 1, 2, 3J=2,4所以，0,1,2,3必可再分看图,把0,4,2,3分割为0,4,2和3 考察0,1,2因为，0,1,20=<2 0,1,20,1,2b =1,3(Z 0,1,2 所以，0,1,2必可再分 看图，把0,4,2分割为0, 1,2 考察1,2因为，1,20= 2u4,20,2讦3u3所以4,2不可再分所以，最终把M分割为0, 1,2 , 3 , 4 , 5用状态2代替状态仁 把引向状态1的箭弧都引向状态2, 把

25、4消去，得到一个DFAW1012. 实际大题例题：构造一个，它接受刀=x , y上所有倒数第二个字符为 y 的字符串在这里还是想先说明一下这道题的解题思路和步骤，希望大家能真正明白整个解题的过程，让大家真正明白这样的一道大题是应 该怎么做的（具体的完整解答过程这里不贴出来了，这是2012年考试之前老师复习课上给的一道题目，本以为会考原题，但是最后考的是一个（0|10）*的题，大家也可以看老师复习上给出的例题，都是非常经典的例题！也是有可能出原题的）上面这道题的分析思路是1. 根据他所描述的功能，构造出一个正规式，正规式先给大家：（）*y （）（其实对于这样的大题最关键就是构造对正规式，大家一

26、定把老师最后的上所有的例题是如何构造正规式的都记下 来！这一步做不出来后面的都没分了！）2. 构造一个初始状态X和和最终状态Y，将正规式写在他3. 按照第8点中的分裂规则对他进行分裂，分裂直到每一 条转换弧上都只含有一个字符4. 分裂结束得到的一个状态转换图实际上就是一个（非确 定的有限自动机）5. 在掌握了第 9点知识的前提下， 就可以按照第 10点说的 步骤，将求得的确定化6. 得到确定化之后的状态转换图， 剩下的事情就是化简了。 也就是第 11 点当中的只是 看到这里强烈建议大家先动笔试一试上面这道例题，相信 只要你认真学习了前面的知识，做出来是没有问题的，祝 大家成功！三：语法分析（1

27、）基本定义1. 上下文无关文法的定义 （重要铺垫 ） 文法：是描述语言的语法结构的形式规则 （或称语法规则） 上下文无关文法概念 :它所定义的语法范畴（或语法单位）是完全独立于这 种范畴可能出现的环境的（与它所在的上下文无关）（重要！以下的概念一定要理解熟知！ ）上下文无关文法 G可定义为一个四元式（,S, P） 是终结符号集合， 它的每个元素称为终结符号， 用小写字母表示。 是非终结符号集合， 它的每个元素称为非终结符号， 用大写字母 表示。S 是一个开始符号，是一个非终结符，至少在一个产生式作为左部出现P是一个产生式的集合，它的每个元素称为一条产生式，可以表 示为： ia | b，其中P是

28、非终结符，叫做 产生式的左部，a 和b分别叫做这个产生式的一个侯选式，他们既可以是终结符, 也可以是非终结符，也可以是他们的组合。2. 句型、句子的概念（小题）设G是一个文法，S是它的开始符号，如果 S二a, 且a （ U ） *则称a是G的一个句型；如果S a, 且a ，则称a是G的一个句子；句子实际上是仅含 有终结符号的句型3. 文法和语言的对应关系：（了解）一个文法G所产生的句子的全体就是一个语言。给定一个 文法，就能从结构上唯一确定其语言；给定一种语言，能 找到其文法，但该文法不是唯一的4. 语法分析树与二义性：（了解）用一棵树来表示句型的推导，简称语法树。若一个文法的一个句子对应两棵

29、不同的语法树， 则称该句子是二义 性句子如果一个文法含有二义性的句子， 则称该文法是 二义性文法。（5,6,7均可能出填空判断选择等小题）5. 3型文法是正规文法、正则文法、线性文法（用于词法分析）6. 2 型文法也称为上下文无关文法（用于语法分析）7. 1 型文法也称为上下文有关文法 若一个文法是递归的，则由它产生的语言的句子个数是无 限的。（2）自上而下（以下 812均为 13 的大题铺垫）8. 文法左递归的定义一个文法中如果存在某个产生式 i Pa （即有某个侯选式的 最左边的符号是这个产生式左部非终结符本身） ，则此文法是 有左递归的。9. 消除文法的左递归的方法 ： 只要求消除直接左

30、递归，方法见下面的例子。设有产生式 iPa | B其中B不以P开头，a不为£,那么，我们可以把 P的规则改为如下的非直接左递归形式：P'fa P | £这样就消除了 iPa | p这个式子的左递归。（提示：在做题时，要把整个文法的每个产生式都逐一检验， 有时含有左递归的产生式是不只一个的，需要逐个消除。 ）10 集合集的构造方法（较抽象）集的构造方法：对于任意一个符号X,构造他的集的方法是：（1）若 X （终结符），则（X）=X.（2）若X （非终结符），且有产生式 Xa（小写a代表 任意一个终结符号，他是侯选式左边的第一个字符）,则把a加 入到（X）中；若X-&#

31、163;也是一条产生式，则把£也加到 （X）中。若有产生式X Y（大写Y代表任意一个非终结符号，他 是侯选式左边的第一个字符）,则把（Y）中所有非£元素都加到（X） 中；集的构造方法：（书上的表述很难懂，这里我用自己的水话表 述）（1）对于文法中给定的开始符号 S,置#与（S）中；（2）将所有产生式侯选式中的非终结符都标出来，并从前往后挨个检查为方便讨论，我们假设 A-a是一个产生式，（这里B和C 代表非终结符，a代表终结符）1. 先检验这个非终结符的右边还有没有别的符号（不管这个符 号是终结符还是非终结符），在这是我们检查的第一个非终结符， 它右边是有符号C的，如果检验到

32、的某个非终结符右边有别的符号，例如这里的B,那么检验他右边符号的集合，这里是（ C）。先将（C）中非空字 £的元素加入到（B）中；注意，如果（C）中含有空字£，还要把（A）中的元素也加入到（B）中（如果不含空字就不这么做）2. 如果检验到的终结符右边没有别的符号了，例如这里的C,那么，直接将(A)中的元素加入到(C)中。在这里，a的存在是无关痛痒的。也就是说，我们在检验某个非终结符时只要看他的右边就好了， 左边有没有有什么都是无 所谓的。 大家按照上面的方法， 将每一个侯选式中的非终结符都 这样检查一遍，最后就能求得所有非终结符的集了11. 递归下降分析法的概念，应满足什么

33、条件？大家不必知道概念，只须知道能够用递归下降分析法分析的 文法是( 1)文法，要成为这种文法，必须满足以下条件：(1) 文法不含左递归(在这里提一句： 欲构造行之有效的自 上而下分析器，则必须消除文法中含有的左递归 ，请大 家记住这句话，有 可能考 小题)(2) 对于文法中每一个非终结符 A的各个产生式的候选式的集 两两不相交。即，若Aa i| a 2| | a n则(a i) n ( aj)=(i Mj)(3) 对于文法中的每个非终结符 A,若它的某个候选式的集中 包含£,则必须满足(A) n (A)=12. 预测分析表的构造构造预测分析表的算法是： (这里需要先画一张表格，代入

34、 题中很容易理解，光看步骤比较抽象，大家可以看第 13 中的大题，边看边理解)（1）先画一张表格，表的首行是文法中所有的终结符号， 首列是所有产生式的左部）（2） 检验文法中每个产生式的每一个侯选式。 我们先假设这 里有一个产生式为 Za,若（a ）中含有终结符a,则把“ La”写入（1）中构造的表中的 M项（M表示以 产生式左部A为行，终结符a为列所对应的表格）；若（b） 中含有终结符B,则把“ A-B”写入（1）中构造的表 中的MA, B 项（MA, B 表示以产生式左部 A为行，终 结符B为列所对应的表格）；按照这样的方法依次执行下 去,直到把每一个产生式的每一个侯选式都检验完并对 应填

35、入表格。（3）特别地，若某个产生式侯选式的集中包含有空子我 们接着引用上例进行说明。在A-a中，假设（a ）里还包含有£,则找出（A）中的所有终结符元素，我们假设 其中一个是B ,那么把“ A-a”写入MA, B 中，按照 此方法将（A）中的所有兀素逐一检验，并将“ Aa”填 入对应的表格中去即可。13. 实际大题（ 8 1 2点的综合知识, 15分左右！） 本题会出一个综合性的大题。 题目会给出一个文法, 要你最 终构造出他的预测分析表,整个过程的步骤如下1. 消除文法左递归 2. 构造每个产生式左部（即 -> 符号左边 的非终结符） 的集、集 3. 构造每个产生式的每个侯选

36、式的集 4. 证明文法是一个 (1) 文法 5. 构造出预测分析表。在 812 点当中，已经介绍了这些步骤的实现方法，以下是 老师给的复习用的上的例题，我对步骤做了一些补充说 明例：设有文法 G(，S，P) ，其中a , A , , , (, ) ; ; S = SP:S - a | A | (T)T | S(1) 消除其产生式的左递归 .(2) 经改写后的文法是否是 (1) 的？给出它的预测分析表 解：(1) 消除其产生式的直接左递归对于T - | S (按照第9点中介绍的知识，这里，aB )所以变成T-'T'-' | £所以文法改写后变为：S - a |

37、A | (T)T-'T'-' | £（2） 经改写后的文法是否是 （1） 的？给出它的预测分析表。 （这里的整体思路是按照第十点的知识构造出相应的集 和 集 再按照第十一点的知识证明他是一个（ 1 ）文法，最 后再用第十二点中知识求出预测分析表）解： （先求所有产生式左部那个非终结符号的集，用的是 第十点中关于集求法的（ 2）中的方法）（S ）= a A（ ；（T ）= aA（ ；（T ' ）= ,£；（紧接着求所有的侯选式的集，方法是：如果这个侯 选式的开头字符是终结符，也就是某个小写字母，又或 者是空字，那么这个侯选式的集就是那个小写字母

38、或者 空字 £；如果侯选式开头是非终结符，就将那个非终结 符的集中除空字 £ 以外的元素变为侯选式本身集的元素)(' )= a A ( ;素)(' )= , ;(a)= a ;( A )= A ;(T)= ( ;S 的集中除空字以外的元（, 本身）（ a 本身）£ 本身）£) =£ (接着求所有产生式左部那个非终结符号的集， 方法在第十 点中已经说得很清楚了，这里我再说明一下。大家做题 时，可以在所有的侯选式中把出现非终结符的位置都标 出来，然后挨个按照规则检查，就不会错了。有时在求 某个非终结符的集时，发现其中还包含着其他非终

39、结符 集的元素， 但那个集却还没有求出来， 此时可先记下来， 接着往下做，做到最后一定会找到某个终结符的集时与 其他非终结符是无关的，把他写出来后，再回头把前面 空出来的填完就好了。 )(T)= ) ;(T')= );(S)= # , ;完事之后要证明他是( 1)文法，用到第十一点中的知识。证明：S f a | A | (T)TT'f' | £(1) 文法已经消除了左递归(2) (a) n ( A) n (T)=a n A n (=(')n(£)二(3) 在 T'f' | £ 中，(£) = £

40、，里面含有空字，所以需要检验：（t '）n （T '）=,汀 n ）=以上，证明该文法是（1）文法（这一步证明别忘了写，不然会扣分的，我考试时这一步就给忘了哎）接下来构造他的预测分析表 （方法是第十二点的知识，我感觉我已经说得非常明白了，这里不再赘述了）aA()#SS “ aS AS (T)TTT'T'T，T'£T''（3 ）自下而上14. 短语、直接短语的概念（很难懂，对于书上的概念我也不太理解，这块知识会出两道小题）在这里请大家了解一下归约的概念：归约是指根据文法的产生式规则，把产生式的右部替换成左部符号。实际上，我们在（2

41、）中研究的自上而下是从产生式左部推导到右部的过程。也就是说，推导和归约其实是两个相逆的过程15. 句柄的概念（小题）一个句型的最左直接短语 是这个句型的句柄16. 规范归约、规范推导、规范句型（小题）规范归约（最左归约）是一个关于规范推导（最右推导）的 逆过程（提示：在（ 2）自上而下的讨论中，事实上我们一直使用的是最左推导，即总是先把侯选式最左边的非终结符推 导为终结符，请大家回想集的求法，事实上就是最左推 导的过程）由规范推导推出的句型称为规范句型 。由于规范句型是由规范推导推出的句型， 故该句型的句柄右 边只含有终结符号（因为他是最右推导，右边的非终结 符一定被推导成终结符了）规范归约的

42、关键问题是寻找句柄 （对应第 15 点）在规范归约中，可归约串必出现在栈顶19. 算符文法、 算符优先文法的概念， 如何判断（大题铺垫） 一个文法，如果它的任一产生式的右部都不含两个相继 （ 并 列）的非终结符，即不含如下形式的产生式右部： 则 我们称该文法为算符文法，也称文法算符之间的优先关系表示： （重要）1. a =. b当且仅当文法 G中含有形如 P-或 i的产生式；2 <. b当且仅当G中含有形如 i的产生式，而R ->b或 >；3>当且仅当G中含有形如P-的产生式，而>*或>（这里大家先不必记住三种情况需要满足的条件， 在后面求和集合时大家自然会

43、看到是和这些规则对应上的。这里 需要注意的是，算符之间的优先级关系有三种，请注意 =.<.>. 这三个符号右下角的那一点是不能少的， （正确 的写法应该是将点写在那三个符号的里面，不好弄，大 家可以看看课本上的正确写法）这不同等于数学上简单 的等于大于和小于，出现 a<的情况都是可能的，而且即 使有a v. b,却并不意味着有b>,这看起来很荒谬，但 是做题时却非常重要，这里大家一定要记住，以后如果 求得算符之间的优先关系是 a v. b ，千万不要自作聪明 写成b>，否则就全错了，切记切记！）如果一个算符文法G中的任何终结符对（a ,b）至多只满足下 述三关系之

44、一：a>av则称G是一个算符优先文法（文法）。如果有某两个算符之间的关系不只一种，那么它就不是一个算符优先文法20. 素短语（小题）素短语是指一个句型的短语， 它至少包括有一个终结符号且 除去它本身之外不再含任何更小的素短语 （了解） 最左素短语： 处在句型最左端那个素短语成为最左素短语（了解）请大家记下面两句话，有可能出 小题 ： 算符优先归约的关键问题是寻找最左素短语算符优先法尤其适用于表达式的分析21. 集合和集合的构造方法(大题步骤)集合构造方法：(1) 若有产生式ia或i，则 a (P);(2) 若a (Q)，且有产生式 iQ，则 a (P) o集合的构造方法(1) 若有产生式

45、ia或i ,则 a (P);(2) 若a (Q)，且有产生式 iQ ,则 a (P) o(解析：个人认为这两个集合的构造方法要比和集合简单得 多。针对以上的书面说法，说一些我个人的理解和方法。 构造某个产生式左部的 或者集合，其实都是从他的产生 式里去找。对于,无非两种情况，1.他的某个侯选式的第 一个字母就是终结符，如 P a，或者第一个字母是非 终结符而第二个字母是终结符如P-，那么就把这个a加入到P的集合中去；2.他的某个侯选式中的第一个字 母就是非终结符，如 P-Q，那么就把 Q的中的元素加 入到P中去(请注意，这里没有除去 £这一说，与集的 构造方法是不同的）。对应的集的构

46、造其实是和是刚好相 反的，大家想想就很容易明白，这里不赘述了。需要注意的是，当某个侯选式只有一个字符时，如P a或 iQ a和Q既算第一个也算最后一个，在构造两个集合时都应该予以考虑）22. 算符优先关系表的构造方法（大题步骤）这个方法是建立在你已经学会了上面所说的两个集合的构造方法基础上的，有了那两个集合，我们就可以根据他 们计算出文法当中所有终结符之间的优先关系了，方法 如下：（1）假定有个产生式的一个候选形为或 有（2）假定有个产生式的一个候选形为（a代表终结符，P代表 非终极符）那么，对任何b （P），有a <. b（3）假定有个产生式的一个候选形为那么，对任何a （P），有a

47、>. B（解析：（1）的情况很简单，对（2）和（3）,这里的方法概 括起来说就是，找到侯选式中所有一个终结符紧挨着一 个非终结符的情况，如或者，如果是前者，那么得出a< 的所有集合中的元素；如果是后者，那么得出P的所有集合中的元素 > 只要把所有候选式里的这两种情况都考虑 完，所有算符之间的优先关系也就找到了。还是请大家 注意，a<的所有集合中的元素这句话，并不等同于P的所有集合中的元素 >,千万别反过来写，一定把两种情况 的顺序记清楚，a是在前面还是在后面。）当把所有终结符的优先关系找出来后，就可以构造一张算符优先关系表了。表的首行首列分别都是文法的所有终结 符

48、，请注意，首行和首列写出来终结符的顺序一定要是 一致的。（请看下面的表）将算法优先关系的三个符号>.<. 按照前面找到的各算符之间的优先关系依次填入表格就 可以了。填入时要注意，一定要先读列，再读行。即首 列上的终结符对应的应该是符号左边的那个元素，首行 上的终结符对应的应该是符号右边的那个元素。a%<>!a>.<.<.<.%>.>.<.<.>.<>.>.>.><.<.<.=!>.>.>.当列完表格后， 需要进行判断： 如果在上面的表格中任意一 个空里

49、都至多只有一个符号，那么写：由于本文法中任 意两个终结符之间都至多只满足 >.<. 中的一个，由此可 以看出本文法是一个算符优先文法；如果有任意一个空 多余一个符号，那么写：由于本文法中任意某两个终结 符之间有两种优先级关系，由此可以看出本文法不是一 个算符优先文法23. 优先函数的构造方法 （可能单独考简答， 也可能加入计 算）优先函数的优点：便于比较，节省空间（ 2012 年只考察了 这样一道小题，并未单独考察别的大题）优先函数的构造方法： （建议大家熟记以下的步骤，是有可 能考简答题的）如果优先函数存在， 则可以通过以下三个步骤从优先表构造 优先函数 :（1）对于每个终结符a

50、,令其对应两个符号和，画一张以所 有符号和为结点的方向图。如果a>,则从画一条弧至如果a<，则从画一条弧至。（2）对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点 （包括出发点自身 ）。赋给的数作为 f（a）赋给的数作为g(a)(3) 检查所构造出来的函数f和g是否与原来的关系矛盾。 若没有矛盾，则f和g就是要求的优先函数，若有矛盾， 则不存在优先函数。这里所指的有没有矛盾是指是否满足下面的关系若，则 f(a) = g(b);若 a<,则 f(a)< g(b);若 a>,则 f(a)> g(b)例:例:取前面文法G(E)i+* # E->E+

51、T|TfAAA件(2) TtT*F|Fw1(3) Ft (E)| i9725124. 实际大题(19、21、22、23的综合知识，12分)这道大题会给你一个文法，问你该文法是否为算符优先文法？请根据、集合构造算符优先关系表说明之，有可能还会让你构造他的优先函数老师的复习提纲里给出了一道题， 没有答案，事实证明2012年的考题中并没有考这道题，请大家先做一做，希望大 家能先自己亲手动笔试一试，按照我上面说的方法算一 下，并不难，个人认为是目前的三道计算题中最简单的 一道例：给出文法G （P）X Y Z 该文法是否为算符优先文法？请根据、集合构造算符优先关系 表说明之（答案是：不是算符优先文法）2

52、5. 分析法属于自底向上分析方法（小题）26. 从文法出发构造（0）分析表的步骤（简答题！背！）（1）构造文法G的拓广文法 G（2）构造（0）项目（3）构造G的项目集规范族（和函数）（画出一个确定的有限自动机）（4）构造分析表四、语义分析（小题）综合属性用于“自下而上”传递信息在语法树中，一个结点的综合属性的值由其子结点的属 性值确定。因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称 s属性文法五、中间代码生成继承属性用于“自上而下”传递信息。在语法树中，一个结点的继承属性由此结点的父结点和 / 或兄弟结点的某些属性确定。用继承属性来表示程序

53、语言结构中的上下文依赖关 系很方便。五、中间代码生成1. 中间代码：（小题） 是一种面向语法，易于翻译成目标代码的代码 中间语言的形式有三种：后缀式、图表示法（包括抽象语法树和 有向无环图（） 两种）、三地址代码2. 后缀式（逆波兰式）的概念（和 4 组成简答） 把运算量 （操作数 ）写在前面，把算符写在后面。例如：，写成 逆波兰式中各运算法出现的顺序与实际运算顺序一致 这一块没什么好讲的， 大家自己看看题， 相信能悟出来其中 的道理（下面是老师复习上的题）（1）a*（）（2） *（）(4)A(CD)(5)(AB)( C D)(6)(AB)(C D E)解：(1)*(2)*+(3)*+(4)A

54、C D(5)A B CD(6)A B CD E3. 后缀式与抽象语法树（表达式树）的关系（小题） 后缀式其实是抽象语法书的线性表示形式， 并且是按后根序 遍历得到的。4. 将赋值语句表示成后缀式和四元式（简答题） 这里不介绍什么方法了，后缀式的求法已经在上面介绍过， 关于四元式，大家看看这个例子相信自然就能够明白。将表达式 （）*（） 分别表示成后缀式、 四元式 （这道题 2012 年 考的是原题）解：1. 后缀式： a b c + e * b c + f / +2. 四元式(1) ( +, b, c, T1 )(2) ( *, T1, e, T2 )(3) ( +, b, c, T3 )(4) ( /, T3, f, T4 )(5) ( +, T2, T4, T5 )(6) ( , T5, , a )再给一个例子：表达式 -()*()-() 分别表示成四元式解：1. 四元式(1)( +, a, b, T1 )(2)(-, T1, , T2 )(3)( +, c, d, T3 )(4)( *, T2, T3, T4 )(5)( +, a, b, T5 )(6)( +, T5,