编译原理复习提纲整理要点.pdf

《编译原理复习提纲整理要点.pdf》由会员分享，可在线阅读，更多相关《编译原理复习提纲整理要点.pdf（22页珍藏版）》请在三一文库上搜索。

1、一、 概述 1. 编译方式与解释方式区别：是否生成目标代码 2. 编译程序总框架 二、 词法分析 1.状态转换图的功能：识别（接受）一定的符号串（单词） 2.状态转换图的程序实现的思路：为每个状态结点都编写一个子程序 3.字母表的概念：一般用表示 4.闭包的概念：闭包V*中的每个字都是由V 中的字经过若干次连接而成的 5.正则闭包 V+的概念：是V 上所有符号串的集合 6.*定义：表示上所有字的全体，空字也包括在其中 7.+空字 不包含，非 8. ， ， 之间的区别 9. 所对应的正规集为 10.正规式与正规集的定义：知道如何用正规式表示一个正规集 11.简述 NFA和 DFA的定义与区别 1

2、2.若 M 的某些结点既是初态结点又是终态结点，或者存在一条从某初态结点到某个终态结点的 通路，那么空字 可为 M 所识别 13.正规式与优先自动机的等价性 14.定理 2.对于上的每一个正规式V，存在一个上的DFA M，使得 L(M)=L(V) 15.DFA M 的化简的概念和方法：终态和非终态是可区别的，因为终态可以读出空字 ，而非终态 不能读出空字 16.课后作业一个例题 17.构造一个 DFA ，它接受 =x，y上所有倒数第二个字符为y 的字符串 三、 语法分析 （1）基本定义 1.上下文无关文法的定义 2.句型、句子的概念 3.文法和语言的对应关系，给出文法构造语言，文法G产生的句子

3、的全体是该文法的语言 4.语法分析树与二义性：判断文法的二义性方法：如果一个文法含有二义性的句子（对应两棵不同 的语法树），则称该文法是二义性文法 5.3 型文法是正规文法、正则文法、线性文法 6.2 型文法也称为称为上下文无关文法 7.若一个文法是递归的，则由它产生的语言的句子个数是无限的 （2）自上而下 8. 文法左递归的定义 9. 消除文法的左递归的方法：直接左递归 10. 消除回溯的方法：提取公共左因子 11. 递归下降分析法的概念，应满足什么条件？ 12. 递归下降法对文法的每个非终结符构造一个相应的子程序 13. 预测分析法：给文法构造预测分析表：消除左递归、消除回溯、First

4、集、 Follow 集。举例子时， 便成 Sa|aS| （T） （3）自下而上 14. 短语、直接短语的概念 15. 句柄的概念（一个句型的最左直接短语） 16. 规范归约（最左） 、规范推导（最右） 、规范句型 17. 规范归约的关键问题是寻找句柄 18. 在规范归约中，可归约串必出现在栈顶 19. 算符文法、算符优先文法的概念，如何判断 20. 构造算符优先关系表、Fisrtvt 、lastvt 集合，可不考虑#号 21. 素短语：算符优先归约的关键问题是寻找最左素短语 22. 算符优先法尤其适用于表达式的分析 23. 给出文法 G（P） X jYj Y kZ|i Z Yid 该文法是否为

5、算符优先文法？请根据FIRSTVT 、LASTVT集合构造算符优先关系表说明之 24. 欲构造行之有效的自上而下分析器，则必须消除文法中含有的左递归 25. LR分析法属于自底向上分析方法 26. 从文法出发构造LR （0）分析表的步骤 四、语义分析 1. 综合属性和继承属性概念 五、中间代码生成 1. 中间代码是一种面向语法，易于翻译成目标代码的代码 2. 后缀式（逆波兰式）的概念 3. 逆波兰式中各运算法出现的顺序与实际运算顺序一致 4. 后缀式与抽象语法树（表达式树）的关系 5. DAG的含义 6. 四元式表示方法，联系时通过临时变量，可以翻译各种语句 7. 将赋值语句表示成后缀式和四元

6、式 六、代码优化 1. 简述代码优化的原则与优化的级别，并列举三种常用的优化技术 2. 基本块、流图的概念，如何画、节点对应基本块 3. 局部优化的方法，DAG是对基本块进行优化的有效工具 4. 不变运算的代码外提的条件 5. 循环优化中的强度削弱的含义 七、目标代码生成 1. 编译程序生成的目标程序种类(309) 一：概述 1. 编译方式与解释方式区别 在于是否生成目标代码，编译方式生成了目标代码。 2. 编译程序总框架 二：词法分析 1.状态转换图的功能：识别（接受）一定的符号串（单词） 上图是一个很简单的状态转换图。上图代表：状态0 通过 X 弧可以转换到状态1，通过 Y弧可以转换到状态

7、2 2.字母表的概念： 一个由有限元素组成的集合，每个元素称为一个符号或一个字， 一般用表示一个字母表 例： = a , b , c 元素： a，b，c 字母表中的字可拼接在一起构成一个序列，如aa,ab,bc,bbc 等，符号的顺序不同所 代表的序列也不同。 不包含任何字符的序列称为空字，用来表示 另外有几个概念必须先了解： 字(符号串 )的连接 设 x 和 y 是两个字 (符号串 )，则定义xy 为他们的连接 例： ab 和 ba 连接是 abba 注: (1)（空字）是连结运算的恒等元素 x = x = x (2)字(符号串 )的 n 次连接 x n = xxx x 规定 x 0 = x

8、 1= x，x2=xx，x3= xxx 集合的 (连接 )积 设 U 和 V 是两个“字 (符号串 )的集合”， 则定义 UV 为他们的 (连接 )积 UV=xy|x U 且 yV 例：设 U=a, ab, V=b, ba, 则 UV=ab, aba, abb, abba 集合 V 的 n 次 (连接 )积记为： V n = V V VV n 个 规定V 0= 例：设 V=a, b，那么 V 0= V 1= a,b V 2=VV=aa,ab,ba,bb V 3=VVV=V2V=aaa,aba,baa,bba, aab,abb,bab,bbb 3.闭包的概念： 设 V 是一个字（符号串）的集合，

9、 则 V 的闭包定义为V *， V * = V 0V1V2 注：闭包V * 中的每个字都是由V 中的字经过有限次连接而成的 正则闭包V+的定义为 V + = VV * 闭包与正则闭包的差别在于，闭包里是含有 的，因为闭包里有集合V0 ，而正则闭包 由于在闭包的基础上又连接了一个V，所以正则闭包里是没有空字的。 *定义：表示上所有字的全体，空字也包括在其中 +表示上所有字的全体，但不包括 4. ， ， 之间的区别（小题） 空字：表不包含任示何字符的序列称 ：表示一个空集 ： 表示含有空字的集合 5.正规式与正规集的定义： 我们可以把具有相同特征的字放在一起组成一个集合，即所谓的正规集 然后使用一

10、种形式化的方法来表示正规集，即所谓的正规式 正规式是描述单词结构的一种形式； 正规集是该类单词的全集。 举例 对于下面的例子，大家应该好好思考一下后面4 个的含义， 对做大题是很有帮助的。做 大题时，题目通常会给你一个实际问题，你需要先把他要实现的功能抽象成一个正规集， 再用正规式表达出来，才能继续做后面的步骤。 所对应的正规集为 6.简述有限自动机NFA和 DFA的定义与区别 NFA代表非确定的有限自动机；DFA代表确定的有限自动机 所谓的有限自动机，其实他并不代表任何实体的机器，只是一种数学模型而已。就像函 数、数列是一种数学模型一样。函数通过函数表达式实现他的功能：你给他一个自变量， 他

11、能根据表达式求出因变量的值。而有限自动机是通过状态转换图来实现功能，你给他 一个初始状态和一个输入符号，他能根据你输入的这个符号将原状态转换到另一个状 态，用他来模拟计算机的识别功能。 下面简单介绍一下DFA （确定的有限自动机）的五元式表示法：(重要 ) 定义：一个确定有限自动机（DFA）M 是一个五元式： M = (S, , f, s 0, F)，其中 1)S是一个有限的状态集合，它的每个元素我们称为一个状态 2) 是一个有穷的输入符号的字母表，它的每个元素我们称为一 个输入字符 3)f 是从S S的单值部分映射 4)s0是 S的一个元素，为初始状态， 它是唯一的 5)状态集合F是终止状态

12、的集合，它是S的子集 (可空 ) 一个非确定有限自动机（NFA ）M是一个五元式 M = (S, , f, S0, F)，其中 S 是一个有限的状态集合，它的每个元素我们称为一个状态 是一个有限的输入符号的字母表，它的每个元素我们称为一个输入字符 f 是从 S * 2S 的部分映射，其中，2S 表示 S 的幂集合（所有S的子集组成的集 合） （f 是非单值的M是非确定） 状态集合S0 是初始状态集合，它是 S的子集 状态集合F 是终止状态的集合，它是S 的子集 注： DFA和 NFA 的区别在于（ 3）和（ 4） ，其他几点都差不多，这是有可能出简答题的， 大家要记住他们的区别和联系 7.DF

13、A的识别功能 对于 *中任何字 ，如果存在一条从初态结点到某个终态结点的道路，这条路上所有 的标识符连成的字等于 ，则 可被 DFA M 所识别 (接受，读出 ) 若 M 的某些结点既是初态结点又是终态结点，或者存在一条从某初态结点到某个终态 结点的 通路，那么空字 可为 M 所识别 8.状态转换图的分裂规则（大题步骤） 例子： (这里 Y有两个圈圈代表他是最终状态的点) 划到最后要求每条弧上都只有一个字母或者数字 9._CLOSURE(I) 和 Ia=_CLOSURE(J)的构造方法（大题步骤） 这里先需要了解几个定义 我们假设有某个状态集I，这个集合中含有不同的状态。 定义 1 状态集 I

14、 的 a 弧转换： move( I, a ) 是一个状态集，是从I 中的状态出发经过一条 a 弧到达的状态的全体。 定义 2 状态集 I 的 (空字 )闭包： _CLOSURE( I ) 是一个状态集，由两部分组成: 状态集 I 中的所有原状态。 从 I 中的状态出发经过任意条 弧，所能到达的状态的全体。 定义 3 Ia=_CLOSURE( move( I, a ) ) 是一个状态集。 下面给出一个实例： 例：有如下一个状态转换图假定I=1, 2 ，求 Ia= ？ J=move(I,a)=5,4,3 Ia=_CLOSURE(J) = 5,4,3,6,2,7,8 （即先做a 弧转换，将求得的状态

15、再求空字闭包） 本知识点旨在让大家掌握在知道了I 这个状态集合后，怎样求Ia 10.如何用子集法将非确定的有限自动机确定化（大题步骤） 方法：先画一张表 IIaIb _CLOSURE(S0) A B C BDE CFG 1.这张表的首行上首列上固定是大写字母I 2.表格后面有几列，取决于这个有限自动机的输入符号数量，有几个输入符号就有几列， 这里假设 Ia Ib 的下标 a b 代表这个有限自动机的输入符号 3.第二行的第一列也是固定的，S0 代表的是这个有限自动机的初始状态,即求 S0的空字 闭包，我们假设求出来的状态集合是A 4.将 A 所对应的Ia Ib 分别求出来，我们假设是B 和 C

16、 5.如果 B 和 C 都分别于A 不同，需要将B，C作为新的状态集合加入到第一列中 6.继续求出B 和 C所对应的Ia Ib ，再检验： 对于 DEFG这四个状态集合，有没有与ABC 是不同的，如果有，加入到第一列的下面，再继续计算，如果与前面的ABC相同就不 再需要加入了。 7.按照这样的方法一直进行下去，知道第一列不再有新的状态集合加入了，这个表就构 造好了。 8.再画一张表，与上面的表相对应 Sab 0 1 2 3 4 1 3 4 2 2 4 3 1 9.对于上面这种表的构造方法很简单，大家也可以不另外画表，而直接标在原来的表中 这种表来源是，在原来表的第一列上分别表上s01234 ，

17、 a 和 b 不变，然后按照第一 列中数字所对应的状态集，依次对应在后面的列上标上相应数字。例如第一列中B对应 1，C对应 2，那么将第二列第二行中的B 也标上 1，第三列第二行中的C 标上 2，等等。 10.画出下面的这个表或在原表中标好后，就可以按照这个表画出状态转换图了，例如， 0 状态通过a 弧转换成1 状态， 通过 b 弧转换成 2 状态； 1 状态通过a 弧转换成3 状态， 通过 b 弧转换成4 状态，等等。 画出这个状态转换图后，就完成了一个非确定有限自动 机的确定化。 11.有限自动机 DFA的化简 整体的思路如下： 1.将第 10 步中得到的已经确定的DFA中的所有状态分为两

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

19、2 的弧指向状态1 下面是老师复习PPT上的一个例子，这是一个较为复杂的例子，可能会看不懂，大家多问一问 周围会的同学， 期末考试时， 肯定不会出这么复杂，通常在将终态节点和非终态节点区分开后， 剩下的就已经快分好了，所以大家不用太担心，化简也是有可能不考察的，大家看清题目要求。 例： 12. 例题：构造一个DFA ，它接受=x ，y 上所有倒数第二个字符为y 的字符串 说明一下这道题的解题思路和步骤，希望大家能真正明白整个解题的过程，让大家真正明白这样 的一道大题是应该怎么做的. 上面这道题的分析思路是 1.根据他所描述的功能，构造出一个正规式，正规式先给大家：（x|y ） * y (x|y

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

21、要你认真学习了前面的知识，做出来 是没有问题的，祝大家成功！ 三：语法分析 （1）基本定义 1.上下文无关文法的定义 文法：是描述语言的语法结构的形式规则（或称语法规则） 上下文无关文法概念: 它所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的（与 它所在的上下文无关） （重要！以下的概念一定要理解熟知！） 上下文无关文法G 可定义为一个四元式(VT， VN， S，P) VT是终结符号集合，它的每个元素称为终结符号，用小写字母表示。 VN是非终结符号集合，它的每个元素称为非终结符号，用大写字母表示。 S是一个开始符号，是一个非终结符，至少在一个产生式作为左部出现 P是一个产生

22、式的集合，它的每个元素称为一条产生式，可以表示为：P | b，其中 P 是非终 结符 ，叫做 产生式的左部，和 b 分别叫做 这个产生式的一个侯选式，他们既可以是终结符，也 可以是非终结符，也可以是他们的组合。 2.句型、句子的概念（小题） 设 G 是一个文法，S是它的开始符号，如果S ，且 (VNVT) * 则称 是 G 的一个句型；如果S ，且 VT* ，则称 是 G 的一个句子；句子实际上是仅含 有终结符号的句型 3.文法和语言的对应关系： （了解） 一个文法G 所产生的句子的全体就是一个语言。给定一个文法，就能从结构上唯一确 定其语言；给定一种语言，能找到其文法，但该文法不是唯一的 4

23、.语法分析树与二义性： （了解） 用一棵树来表示句型的推导，简称语法树。若一个文法的一个句子对应两棵不同的 语法树，则称该句子是二义性句子如果一个文法含有二义性的句子，则称该文法是 二义性文法。 （5,6,7 均可能出填空判断选择等小题） 5. 3型文法是正规文法、正则文法、线性文法（用于词法分析） 6. 2型文法也称为上下文无关文法（用于语法分析） 7. 1型文法也称为上下文有关文法 若一个文法是递归的，则由它产生的语言的句子个数是无限的。 （2）自上而下 8. 文法左递归的定义 一个文法中如果存在某个产生式PP （即有某个侯选式的最左边的符号是这个产生式左 部非终结符本身） ，则此文法是有

24、左递归的。 9. 消除文法的左递归的方法 ： 只要求消除直接左递归，方法见下面的例子。 设有产生式PP| 其中 不以 P 开头， 不为 ，那么，我们可以把P 的规则改为如下的非直接左递归形式： P P P P | 这样就消除了PP| 这个式子的左递归。 （提示：在做题时，要把整个文法的每个产生式都逐一检验，有时含有左递归的产生式是 不只一个的，需要逐个消除。） 10.First集合 Follow集的构造方法（较抽象） First集的构造方法： 对于任意一个符号X，构造他的frist 集的方法是： (1)若 XVT （终结符），则 FIRST(X)=X. (2)若 XVN（非终结符） ，且有产生

25、式 Xa （小写 a 代表任意一个终结符号，他是侯 选式左边的第一个字符） ，则把 a 加入到 FIRST(X) 中；若 X 也是一条产生式，则把也加到 FIRST(X) 中。 若有产生式XY （大写 Y 代表任意一个非终结符号，他是侯选式左边的第一个字符） ， 则把 FIRST(Y) 中所有非 元素都加到FIRST(X) 中； FOLLOW集的构造方法： （书上的表述很难懂，这里我用自己的水话表述） (1)对于文法中给定的开始符号S，置 #与 FOLLOW(S) 中； (2)将所有产生式侯选式中的非终结符都标出来，并从前往后挨个检查 为方便讨论， 我们假设A BC是一个产生式，（这里 B 和

26、 C 代表非终结符， 代表终结符） 1.先检验这个非终结符的右边还有没有别的符号（不管这个符号是终结符还是非终结符），在 这,B 是我们检查的第一个非终结符，它右边是有符号C 的， 如果检验到的某个非终结符右边有别的符号，例如这里的B，那么检验他右边符号的FIRST集 合，这里是 FIRST （C） 。先将 FIRST （C）中非空字 的元素加入到FOLLOW(B) 中；注意， 如果 FIRST （C）中含有空字 ，还要把FOLLOW （A）中的元素也加入到FOLLOW （B）中（如果不含空字 就不这么做） 2.如果检验到的终结符右边没有别的符号了，例如这里的C，那么，直接将FOLLOW （A

27、）中的 元素加入到FOLLOW （C）中。 在这里， 的存在是无关痛痒的。也就是说，我们在检验某个非终结符时只要看他的右边 就好了， 左边有没有有什么都是无所谓的。大家按照上面的方法，将每一个侯选式中的非终结符 都这样检查一遍，最后就能求得所有非终结符的FOLLOW集了 11. 递归下降分析法的概念，应满足什么条件？ 大家不必知道概念，只须知道能够用递归下降分析法分析的文法是LL（1）文法，要成为这 种文法，必须满足以下条件： (1)文法不含左递归（在这里提一句：欲构造行之有效的自上而下分析器，则必须消除文法 中含有的左递归，请大家记住这句话，有可能考小题 ） (2)对于文法中每一个非终结符A

28、 的各个产生式的候选式的FIRST集两两不相交。即，若 A1| 2| | n 则FIRST( i) FIRST( j)= (ij) (3)对于文法中的每个非终结符A，若它的某个候选式的FIRST集中包含 ,则必须满足 FIRST(A) FOLLOW(A)= 12. 预测分析表的构造 构造预测分析表的算法是：（这里需要先画一张表格，代入题中很容易理解，光看步骤比较 抽象，大家可以看第13 中的大题，边看边理解） （1）先画一张表格，表的首行是文法中所有的终结符号，首列是所有产生式的左部） (2)检验文法中每个产生式的每一个侯选式。我们先假设这里有一个产生式为A|b ，若 FIRST( )中含有终

29、结符a，则把“ A”写入（ 1）中构造的表中的MA,a 项（ MA,a 表示以产生式左部A 为行，终结符a 为列所对应的表格） ；若 FIRST(b) 中含有终结符， 则把“ A”写入（ 1）中构造的表中的MA, 项（MA, 表示以产生式左部A 为行， 终结符 为列所对应的表格） ；按照这样的方法依次执行下去，直到把每一个产生式的 每一个侯选式都检验完并对应填入表格。 (3)特别地，若某个产生式侯选式的FIRST集中包含有空子：我们接着引用上例进行说明。 在 A|b 中，假设FIRST( )里还包含有 ，则找出FOLLOW(A)中的所有终结符元素， 我们假设其中一个是,那么把“ A”写入 MA

30、, 中，按照此方法将FOLLOW(A)中的 所有元素逐一检验，并将“A”填入对应的表格中去即可。 13.实际大题 给出一个文法，要你最终构造出他的预测分析表，整个过程的步骤如下: 1.消除文法左递归2.构造每个产生式左部（即-符号左边的非终结符）的First 集、 Follow 集 3.构造每个产生式的每个侯选式的first 集 4.证明文法是一个LL(1)文法 5.构造出预测 分析表。 在 812 点当中， 已经介绍了这些步骤的实现方法，以下是老师给的复习用的PPT上的例题， 我对步骤做了一些补充说明 例：设有文法G(VT，VN，S，P)， 其中 VT=a， ，, ， (，) ；VN=S,T

31、 ； S = S P: S a | | (T) T T,S | S (1)消除其产生式的左递归. (2)经改写后的文法是否是LL(1)的？给出它的预测分析表 解： (1)消除其产生式的直接左递归 对于 T T,S | S (按照第 9 点中介绍的知识，这里P=T ，=,S ，=S ) 所以变成 T ST T ,ST | 所以文法改写后变为： S a | | (T) T ST T ,ST | (2)经改写后的文法是否是LL(1)的？给出它的预测分析表。 （这里的整体思路是按照第十点的知识构造出相应的FIRST集 和 FOLLOW集 再按照第十一 点的知识证明他是一个LL（1）文法，最后再用第十二

32、点中知识求出预测分析表） 解： （先求所有产生式左部那个非终结符号的FIRST集，用的是第十点中关于FIRST集求法 的（ 2）中的方法） FIRST( S )= a (; FIRST( T )= a (; FIRST( T )= , ; （紧接着求所有的侯选式的FIRST集，方法是： 如果这个侯选式的开头字符是终结符， 也就是某个小写字母，又或者是空字，那么这个侯选式的FIRST集就是那个小写字母或 者空字 ；如果侯选式开头是非终结符，就将那个非终结符的FIRST集中除空字 以外的 元素变为侯选式本身FIRST集的元素） FIRST(ST )= a (; （S的 FIRST集中除空字以外的元

33、素） FIRST(,ST )= , ; （, 本身） FIRST(a)= a ; （a 本身） FIRST( )= ; FIRST(T)= ( ; FIRST （ ） = （ 本身） （接着求所有产生式左部那个非终结符号的FOLLOW集，方法在第十点中已经说得很清楚 了，这里我再说明一下。大家做题时，可以在所有的侯选式中把出现非终结符的位置都 标出来， 然后挨个按照规则检查，就不会错了。 有时在求某个非终结符的FOLLOW集时， 发现其中还包含着其他非终结符FOLLOW集的元素，但那个 FOLLOW集却还没有求出来， 此时可先记下来，接着往下做，做到最后一定会找到某个终结符的FOLLOW集时与

34、其他 非终结符是无关的，把他写出来后，再回头把前面空出来的填完就好了。） FOLLOW(T)= ) ; FOLLOW (T )= ) ; FOLLOW (S)= # , ; 完事之后要证明他是LL（1）文法，用到第十一点中的知识。 证明： S a | | (T) T ST T ,ST | （1）文法已经消除了左递归 （2）FIRST(a)FIRST() FIRST(T)=a (= FIRST(,ST ) FIRST （ ）= （3）在 T,ST| 中， FIRST （ ）= ，里面含有空字，所以需要检验： FIRST( T ) FOLLOW (T )= ， , ) = 接下来构造他的预测分析表

35、 a ( ) ，# S S aS S (T) T TSTTSTTST TT T ,ST （3）自下而上 14. 短语、直接短语的概念 在这里请大家了解一下归约的概念： 归约是指根据文法的产生式规则，把产生式的右部替换成左部符号。实际上， 我们在（ 2） 中研究的自上而下是从产生式左部推导到右部的过程。也就是说，推导和归约其实是两 个相逆的过程 15. 句柄的概念 一个句型的 最左直接短语是这个句型的句柄 16. 规范归约、规范推导、规范句型 规范归约 （最左归约）是一个关于规范推导（ 最右推导）的逆过程 （提示：在（ 2）自上而下的讨论中，事实上我们一直使用的是最左推导，即总是先把侯选 式最左

36、边的非终结符推导为终结符，请大家回想FIRST集的求法，事实上就是最左推导 的过程） 由规范推导推出的句型称为规范句型。 由于规范句型是由规范推导推出的句型，故该句型的句柄右边只含有终结符号（因为他是 最右推导，右边的非终结符一定被推导成终结符了） 规范归约的关键问题是寻找句柄 在规范归约中，可归约串必出现在栈顶 19. 算符文法、算符优先文法的概念，如何判断 一个文法，如果它的任一产生式的右部都不含两个相继(并列 )的非终结符，即不含如下形式 的产生式右部：QR 则我们称该文法为算符文法，也称OG 文法 算符之间的优先关系表示：（重要） 1. a =. b 当且仅当文法G 中含有形如P ab

37、或 P aQb 的产生式； 2.a b或 R-Qb； 3.a.b 当且仅当G中含有形如P Rb 的产生式，而R-a 或 R- aQ （这里大家先不必记住三种情况需要满足的条件，在后面求FIRSTVT和 LASTVT集合时大家 自然会看到是和这些规则对应上的。这里需要注意的是，算符之间的优先级关系有三种， 请注意 = 这三个符号右下角的那一点是不能少的，（正确的写法应该是将点写在那三 个符号的里面，word 不好弄， 大家可以看看课本上的正确写法）这不同等于数学上简单 的等于大于和小于，出现a.a，这看起来很荒谬，但是做题时却非常重要，这里大家一定要记住，以后如果求得 算符之间的优先关系是a .

38、a，否则就全错了， 切记切记！ ） 如果一个算符文法G 中的任何终结符对(a，b)至多只满足下述三关系之一： a=.b a.b a. B （解析： (1)的情况很简单，对（2）和（ 3） ，这里的方法概括起来说就是，找到侯选式中所 有一个终结符紧挨着一个非终结符的情况，如 aP或者 Pa,如果是前者， 那么得出 a.a 只 要把所有候选式里的这两种情况都考虑完，所有算符之间的优先关系也就找到了。还是 请大家注意，a.a,千万别反过来写，一定把两种情况的顺序记清楚，a 是在前面还是在后 面。 ） 当把所有终结符的优先关系找出来后，就可以构造一张算符优先关系表了。表的首行首列 分别都是文法的所有终

39、结符，请注意， 首行和首列写出来终结符的顺序一定要是一致的。 （请看下面的表）将算法优先关系的三个符号. ! a . . . . . . . . . 当列完表格后，需要进行判断：如果在上面的表格中任意一个空里都至多只有一个符号， 那么写： 由于本文法中任意两个终结符之间都至多只满足.=C goto (8) (6) B:=B+1 (7) goto (4) (8) write A (9) halt 解： 第一步 是找出入口语句： （1）为程序的第一句；（4）为（7）的 GOTO得来；（6）为（ 5） 的后一句；（8）为（ 5）的 GOTO得来 第二步 画基本块： （画基本块的方法是用方框把语句框起

40、来，这里不好画，我没有框） （1） （2） （3）为一基本块（对应三种A 的方法）（4） （5）为一基本块（对应B） （6） （7）为一基本块（对应B） （8） （ 9）为一基本块（对应C） 第三步 画流图： 3. 局部优化的方法 DAG是对基本块进行优化的有效工具 利用 DAG可以实现局部优化 (1)合并已知量 (2)删除多余运算 (3)删除无用赋值 4. 不变运算的代码外提的条件 不变运算所在的结点是循环L 所有出口结点的必经结点. 对于循环不变运算A:=B op C，只有 A 在循环中其他地方未再定值,才能把 A:=B op C 外提 ; 循环中所有A 的引用点只有S中的 A 的定值才能到达。 5. 循环优化中的强度削弱的含义 把程序中执行时间较长的运算转换为执行时间较短的运算。 强度消弱主要是对与归纳变量有线性关系的变量赋值进行； 经过强度消弱后，循环中可能出现一些新的无用赋值； 对于消弱下标变量地址计算的强度非常有效 七、目标代码生成 目标代码一般有以下三种形式： 能够立即执行的机器语言代码。所有地址已经定位； 待装配的机器语言模块。执行时，由连接装配程序把它们和某些运行程序连接 起来，转换成能执行的机器语言代码； 汇编语言代码。尚须经过汇编程序汇编，转换成可执行的机器语言代码。