复习—编译原理第4章课件.ppt

《复习—编译原理第4章课件.ppt》由会员分享，可在线阅读，更多相关《复习—编译原理第4章课件.ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理1计算机学院计算机学院编 译 原 理 Compiler Principles任课教师：郑丽萍任课教师：郑丽萍2014201420152015第第第第2 2学期学期学期学期计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理2n句型分析：句型分析：就是识别一个符号串是否为某文法的句型，就是识别一个符号串是否为某文法的句型，是某个是某个推导（归约）推导（归约）推导（归约）推导（归约）的构造过程。的构造过程。n分析程序分析程序(识别程序识别程序)：在语言的编译实现中，完成句型在语言的编译实现中，完成句型分析的

2、程序。分析的程序。n从左到右的分析算法：从左到右的分析算法：总是从总是从左左到到右右地识别输入符号地识别输入符号串，首先识别符号串中的串，首先识别符号串中的最左最左符号，进而符号，进而依次识别右边依次识别右边的的一个符号，直到分析结束。一个符号，直到分析结束。语法分析的方法语法分析的方法一、基本概念一、基本概念计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理3q自上而下分析法自上而下分析法从从文法的开始符号文法的开始符号出发出发，反复使用文法的，反复使用文法的产生式产生式，为，为待识别句子建立一个待识别句子建立一个最左推导最左推导，以寻找与，以寻找与输入符号串输入符号串

3、匹配匹配的的推导推导推导推导。q自下而上分析法自下而上分析法从从输入符号串输入符号串开始开始，逐步进行逐步进行归约归约，从，从叶子节点叶子节点，由，由底上向上底上向上逐步建立一棵完整的语法树，直至逐步建立一棵完整的语法树，直至归约归约归约归约到文法的到文法的开始符号（树根）。开始符号（树根）。二、语法分析的两种方法二、语法分析的两种方法计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理4自顶向下分析方法的基本缺点自顶向下分析方法的基本缺点自顶向下分析方法的基本缺点自顶向下分析方法的基本缺点不能处理具有左递归性的文法不能处理具有左递归性的文法不能处理具有左递归性的文法不能处

4、理具有左递归性的文法文法文法文法文法GG，存在，存在，存在，存在UUV VN N，ifU=U,ifU=U,则则则则GG为左递归文法为左递归文法为左递归文法为左递归文法+一、左递归文法一、左递归文法 左递归文法左递归文法左递归文法左递归文法 回溯问题回溯问题回溯问题回溯问题一般方法面临问题及解决一般方法面临问题及解决计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理5要实行自顶向下分析，必须要消除文法的左递归，不要实行自顶向下分析，必须要消除文法的左递归，不要实行自顶向下分析，必须要消除文法的左递归，不要实行自顶向下分析，必须要消除文法的左递归，不仅消除仅消除仅消除仅消除直

5、接左递归直接左递归直接左递归直接左递归，而且消除，而且消除，而且消除，而且消除间接左递归间接左递归间接左递归间接左递归。直接左递归直接左递归 若若 P P|、V*且且不以不以P开头开头 串的特点串的特点.间接左递归间接左递归 若若 P=P 例如：例如：SAa ASb|b *如果文法具有如果文法具有如果文法具有如果文法具有间接左递归间接左递归间接左递归间接左递归，则也将发生上述问题。，则也将发生上述问题。，则也将发生上述问题。，则也将发生上述问题。计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理6二、回溯问题二、回溯问题1 1什么是回溯什么是回溯什么是回溯什么是回溯?分析

6、工作要部分地或全部地退回去重做叫回溯。分析工作要部分地或全部地退回去重做叫回溯。严重的效率低，只有在理论上的意义而无实际意义严重的效率低，只有在理论上的意义而无实际意义。U:=U:=a a 1 1|a a 2 2|a a 3 32 2造成回溯的条件造成回溯的条件造成回溯的条件造成回溯的条件?3 3回溯带来的问题回溯带来的问题回溯带来的问题回溯带来的问题?文法中，对于某个非终结符号的规则其右部有多个选择，文法中，对于某个非终结符号的规则其右部有多个选择，并根据所面临的输入符号不能准确并根据所面临的输入符号不能准确的确定所要选择时，就可能的确定所要选择时，就可能出现回溯。出现回溯。计算机学院计算机

7、学院计算机学院计算机学院2023/1/4编译原理编译原理71)1)语法分析要重做语法分析要重做语法分析要重做语法分析要重做2)2)语法处理工作要推倒重来语法处理工作要推倒重来语法处理工作要推倒重来语法处理工作要推倒重来因此自顶向下的一般分析方法因此自顶向下的一般分析方法因此自顶向下的一般分析方法因此自顶向下的一般分析方法不能处理左递归不能处理左递归不能处理左递归不能处理左递归、复、复、复、复杂的杂的杂的杂的回溯技术回溯技术回溯技术回溯技术、回溯导致语义工作推倒重来、难以报告出、回溯导致语义工作推倒重来、难以报告出、回溯导致语义工作推倒重来、难以报告出、回溯导致语义工作推倒重来、难以报告出错的确

8、切位置、效率低。错的确切位置、效率低。错的确切位置、效率低。错的确切位置、效率低。欲采用此方法，必须：欲采用此方法，必须：欲采用此方法，必须：欲采用此方法，必须：1 1、消除左递归；、消除左递归；、消除左递归；、消除左递归；2 2、消除回溯、消除回溯、消除回溯、消除回溯4 4效率低的原因效率低的原因效率低的原因效率低的原因计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理8消除文法的左递归产生式消除文法的左递归产生式方法：方法：改写产生式，使产生式不含左递归。改写产生式，使产生式不含左递归。改写产生式，使产生式不含左递归。改写产生式，使产生式不含左递归。n法一：PP|产生

9、式的符号串为产生式的符号串为.引入一元语言符引入一元语言符号号，x表示表示x可出现任意次。可出现任意次。则：则：PP|改写为改写为P例例1：SAcAAa|b改为：改为：SAcAba一、消除直接左递归一、消除直接左递归例例2：EE+T|TTT*F|F消除左递归：消除左递归：ET+TTF*F计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理9n法二：对左递归对左递归 AA|的非终结符的非终结符A，引入一个新的非终，引入一个新的非终结符结符A，使得：，使得：AA|等价写成：等价写成：一般地：若一般地：若其中其中ii均不以均不以A A打头，则：打头，则：AAAA|计算机学院计算机

10、学院计算机学院计算机学院2023/1/4编译原理编译原理10i)i)已知已知已知已知 Uxy|xw|xzUxy|xw|xz解：解：解：解：Ux(y|w|z)Ux(y|w|z)得：得：得：得：UxUUxUUy|w|zUy|w|zii)ii)已知已知已知已知 Ux|xyUx|xy解：解：解：解：Ux(y|)Ux(y|)n法二步骤总结使用使用使用使用提因子法，提因子法，提因子法，提因子法，不仅有助于消除直接左递归。而且有不仅有助于消除直接左递归。而且有不仅有助于消除直接左递归。而且有不仅有助于消除直接左递归。而且有助于压缩文件的长度，使我们更加有效的分析句子。助于压缩文件的长度，使我们更加有效的分析

11、句子。助于压缩文件的长度，使我们更加有效的分析句子。助于压缩文件的长度，使我们更加有效的分析句子。Step1：提因子：提因子计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理11若：若：若：若：PPPP|则可改写为：则可改写为：则可改写为：则可改写为：PP PPPP P|P|例例EE+T|TTT*F|FF(E)|id消除左递归后文法消除左递归后文法 ETE E +TE|TFT T *F T|F(E)|id注意：注意：此方法只能消除出现在此方法只能消除出现在产生式的全部产生式的全部直接左递归直接左递归，不，不能消除经两步或多步推导所出能消除经两步或多步推导所出现的一切现的一

12、切间接左递归。间接左递归。Step1：将左递归规则改为右递归：将左递归规则改为右递归计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理12二、消除间接左递归二、消除间接左递归n1 间接左递归产生原因n产生式右边产生式右边首符号为非终结首符号为非终结符符；n(存在回路存在回路)前面非终结符引用前面非终结符引用后面非终结符，后面非终结后面非终结符，后面非终结符引用前面非终结符。符引用前面非终结符。例例1：SAc|c(1)ABb|b(2)BSa|a(3)对例对例1：lBSa|a带入带入(2)，得，得ASab|ab|bl带入带入S产生式，得产生式，得SSabc|abc|bc|cl

13、对对对对S S消除直接左递归得：消除直接左递归得：消除直接左递归得：消除直接左递归得：S(abc|bc|c)SSabcS|n 2 消除方法n找出找出所有所有引用引用前面非终结符前面非终结符的的产生式进行代换，即先变换成产生式进行代换，即先变换成直直接左递归接左递归。计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理13一、消除回溯的途径 改写文法对具有多个候选式右部对具有多个候选式右部对具有多个候选式右部对具有多个候选式右部反复反复反复反复提取左因子，使其具有不同首符号提取左因子，使其具有不同首符号提取左因子，使其具有不同首符号提取左因子，使其具有不同首符号例例1UxV|

14、xWU,V,WVn,xVt改写为：改写为：Ux(V|W)更清楚表示更清楚表示UxZZV|W注意：注意：要进一步检查要进一步检查要进一步检查要进一步检查V V和和和和WW的首符号集是否相交，若相交，的首符号集是否相交，若相交，的首符号集是否相交，若相交，的首符号集是否相交，若相交，则要再次提取左因子。则要再次提取左因子。则要再次提取左因子。则要再次提取左因子。回溯的消除及回溯的消除及LL(1)LL(1)文法文法计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理14一般的，一般的，一般的，一般的，对于有公共左因子的文法对于有公共左因子的文法Aa 1|a 2|a k|，其中，其

15、中 不以不以a a开头，开头，aaV V。提左因子：提左因子：判断判断adeSaAadAade例：例：Ad|de|f改为：改为：AdA|f A|e A A a aA A|A A 1 1|2 2|k k若若 1 2 k还有某些候选式有相同首符号，则依次提取，还有某些候选式有相同首符号，则依次提取，直到每个候选式的首符号不同为止。直到每个候选式的首符号不同为止。注意：注意：注意：注意：提取公因子会引入大量非终结符和提取公因子会引入大量非终结符和产生式。产生式。回溯的消除及回溯的消除及LL(1)LL(1)文法文法计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理15n 1 定义

16、FIRST(X)=a|aFIRST(X)=a|aV VT T且且且且XXa a ，X X，V V*特别的：特别的：X X ，则则FIRST(X)FIRST(X)n对文法对文法G的所有非终结符的的所有非终结符的每个候选式每个候选式X其其首符号集首符号集为为FIRST(X)。n对对A的任何两个不同的选择的任何两个不同的选择 i和和 j，希望有，希望有FIRST(i)FIRST(j)=此时，当要求此时，当要求A匹配输入串时，匹配输入串时，A就可根据所面临第一个输入就可根据所面临第一个输入符号符号a，准确指派某个候选式推导，该候选式即为，准确指派某个候选式推导，该候选式即为aFIRST(X)的的X候选

17、式。候选式。二、FIRST集*回溯的消除及回溯的消除及LL(1)LL(1)文法文法计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理16n 2 FIRST（X）构造方法n1).若若X V，则，则FIRST(X)=X；n2).若若X VN，且有，且有Xa，则，则a FIRST(X)；a可为可为；n3).若有若有XY1Y2YK，Yi V VN N(1iK)，则，则(FIRST(Y1)FIRST(X);若若 FIRST(Y1)，则，则(FIRST(Y2)FIRST(X)；同样，若同样，若 FIRST(Yj)(1j A 且且aFRIST(),V*,V*l若若S=uA，且且=，则，

18、则#FOLLOW(A)三、FOLLOW集对文法对文法G的所有的所有含有含有含有含有 产生式产生式产生式产生式的的非终结符非终结符非终结符非终结符A A定义它的定义它的FOLLOW(A)。对含有对含有的的A的所有候选式的所有候选式 i，希望有，希望有FIRST(FIRST(i i )FOLLOW(AFOLLOW(A )=)=*计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理18l1).文法的开始符号文法的开始符号S，置，置#FOLLOW(S)；当当AVN为句型的尾符号时，则为句型的尾符号时，则#FOLLOW（A）l2).对于对于BA，则，则(FIRST()FOLLOW(A

19、)；l3).对于对于BA，或，或BA而而 FIRST()，则把则把FOLLOW（B）加至）加至FOLLOW（A）中。）中。l反复使用反复使用2、3步，直到每个非终结符的步，直到每个非终结符的FOLLOW集不再集不再增大为止。增大为止。n 2 FOLLOW(A)构造方法计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理19 四、LL(1)文法2 2、若、若、若、若=,=,则则则则FIRST(FIRST()FOLLOW(FOLLOW(A A)=)=*定理：定理：文法文法文法文法GG是是是是LL(1)LL(1)文法的文法的文法的文法的充分必要条件充分必要条件充分必要条件充分必要

20、条件是：对于是：对于是：对于是：对于GG的的的的 每一个非终结符每一个非终结符每一个非终结符每一个非终结符A A的任意两条规则的任意两条规则的任意两条规则的任意两条规则A A|,下列条件成立：下列条件成立：下列条件成立：下列条件成立：1 1、FIRST(FIRST()FIRST(FIRST()=)=计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理201 LL(1)含义：L：从左至右顺序扫描输入串；从左至右顺序扫描输入串；L：按最左推导方式；按最左推导方式；1：每一次推导均向前查看一个输入符号准确指派产生式。每一次推导均向前查看一个输入符号准确指派产生式。2 LL(1)文

21、法性质:没有公共左因子；没有公共左因子；无二义性；无二义性；不含左递归。不含左递归。对对LL(1)文法，可构造一个无回溯自顶向下语法分析程序，方法为：文法，可构造一个无回溯自顶向下语法分析程序，方法为：q预测分析法（LL(1)分析法）计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理21LL(1)分析方法是一种比递归子程序法更有效的自顶向下分析分析方法是一种比递归子程序法更有效的自顶向下分析方法。方法。LL(1)分析使用一个下推栈而不是递归调用来完成分析。分析使用一个下推栈而不是递归调用来完成分析。名称中第一个名称中第一个L表示自左向右顺序扫描输入符号串，第二个表示自左向

22、右顺序扫描输入符号串，第二个L表示分析过程产生一个句子的最左推导。表示分析过程产生一个句子的最左推导。括号中的括号中的1表示每进行一步推导，只需要向前查看一个输入符表示每进行一步推导，只需要向前查看一个输入符号，便能确定当前所应选用的规则。号，便能确定当前所应选用的规则。预测分析法预测分析法计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理22LL(1)分析器由一个总控程序（表驱动程序）、一张分析表（预分析器由一个总控程序（表驱动程序）、一张分析表（预测分析表、测分析表、LL(1)分析表）和一个分析栈组成。分析表）和一个分析栈组成。输入符号串：分析栈a1a2an#XZS#

23、LL（1）总控程序分析表输出流栈中存放文法的栈中存放文法的符号串，栈底符符号串，栈底符号是号是#待分析串，从待分析串，从左到右扫描左到右扫描是一个两维数组是一个两维数组MA,a,A是非是非终结符，终结符，a是终是终结符或结符或#LL(1)LL(1)分析的基本方法分析的基本方法计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理23输入符号串输入符号串:指要分析的输入符号串，它以右界符指要分析的输入符号串，它以右界符#作为结尾。作为结尾。分析栈：用来存放一系列文法符号。分析开始时，先将分析栈：用来存放一系列文法符号。分析开始时，先将#入栈，入栈，然后再将文法的开始符号入栈。然

24、后再将文法的开始符号入栈。输出流：分析过程中使用的产生式序列。输出流：分析过程中使用的产生式序列。总控程序：分析器对输入串的分析靠总控程序完成总控程序：分析器对输入串的分析靠总控程序完成.根据分析栈根据分析栈的栈顶符号的栈顶符号X和当前的输入符号和当前的输入符号a，总控程序按照分析表的指示，总控程序按照分析表的指示来决定分析器的动作。工作过程如下：来决定分析器的动作。工作过程如下：计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理24第一步第一步 初始化初始化:分析开始时，首先将符号分析开始时，首先将符号#及文法的开始符号及文法的开始符号S S依次置于分析栈的底部，并把各

25、指示器调整至起始位置，如图依次置于分析栈的底部，并把各指示器调整至起始位置，如图1 1所示。然后，反复执行第二步的操作。所示。然后，反复执行第二步的操作。输入符号串：输入符号串：a1a2an#分析栈：分析栈：S#图图1 1 分析开始时状况分析开始时状况 第二步第二步 假设分析的某一步，分析栈及余留的符号串如图假设分析的某一步，分析栈及余留的符号串如图2 2：a iai+1 an#X1X2Xm-1Xm 图图2 2 分析进行中的状况分析进行中的状况 计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理25(1)(1)若若X X m mVV n n，则查分析表的，则查分析表的X

26、X m m行行a a i i列，假设列，假设M XM X m m，a a i i 为产生式为产生式X X m m Y Y1 1Y Y2 2Y Y k k，则将，则将X X m m出栈，并将出栈，并将Y Y1 1Y Y2 2Y Y k k反序入栈，如图反序入栈，如图3 3；若；若M XM X m m，a a i i 为为ERRORERROR，则出错。，则出错。a iai+1 an#X1X2Xm-1Y k Y k-1Y1 图图3 3 反序入栈反序入栈 (2)(2)若若X Xm m=a=ai i#，表表示示栈栈顶顶与与扫扫描描的的符符号号匹匹配配，则则栈栈顶顶符符号号X X m m出出栈，输入指示器

27、指向下一个符号，否则栈，输入指示器指向下一个符号，否则(即即X Xm maa i i)出错。出错。(3)(3)若若X Xm m=a=a i i=#=#，表示输入串完全匹配，分析成功。，表示输入串完全匹配，分析成功。计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理261 分析表：可用一个二维数组表示，它的每一行与文法的一个非终可用一个二维数组表示，它的每一行与文法的一个非终结符相关联，每一列则与文法的一个终结符号或界符结符相关联，每一列则与文法的一个终结符号或界符“#”相关联。相关联。n元素：元素：MA，a文法产生式文法产生式|error（AVN，aVT#）n基本思想基本

28、思想当文法中某一当文法中某一非终结符非终结符呈现在呈现在栈顶栈顶时时,根据当前的根据当前的输入符号输入符号，分析表应指示要用该分析表应指示要用该非终结符的哪一条候选非终结符的哪一条候选式式匹配输入串匹配输入串(即进行下一步最左推导即进行下一步最左推导)根据这个思想，我们可以构造分析表算法根据这个思想，我们可以构造分析表算法!预测分析表的构造预测分析表的构造计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理27分析表元素分析表元素MA,a(AVN,aVT#)，按下述规则确定：，按下述规则确定：对于文法中的对于文法中的每个每个产生式产生式A1|2|m1）若若aFirst(i)

29、，则置，则置MA,a=“Ai”2）若）若 First(j)，且，且aFollow(A)，则，则MA,a=“A”3）除上述两种情况外，其余的一切表元素均置为）除上述两种情况外，其余的一切表元素均置为error。2 预测分析表构造算法预测分析表各元素含义为：预测分析表各元素含义为：或指出或指出当前推导当前推导所应使用的所应使用的产生式产生式，或指出或指出输入符号串输入符号串中存在着中存在着语法错误语法错误.计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理28注：注：注：注：1 1）用分析表构造算法可以为任意文法）用分析表构造算法可以为任意文法）用分析表构造算法可以为任意文法

30、）用分析表构造算法可以为任意文法GG构造其分析表构造其分析表构造其分析表构造其分析表MM22）若文法为非）若文法为非）若文法为非）若文法为非LL(1)LL(1)文法，则构造出的文法，则构造出的文法，则构造出的文法，则构造出的MM包含有多重元素。包含有多重元素。包含有多重元素。包含有多重元素。则则则则分析过程有回溯分析过程有回溯分析过程有回溯分析过程有回溯。可以证明：一个文法可以证明：一个文法G的预测分析表不含多重的预测分析表不含多重元素，当且仅当该元素，当且仅当该文法是文法是LL(1)LL(1)的。的。计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理29五、结 论对对L

31、L(1)LL(1)文法，总能构造预测分析表，且表中不含多重元素。文法，总能构造预测分析表，且表中不含多重元素。对对非非LL(1)LL(1)文法，尽管可为其建立预测分析表，但表中必出现文法，尽管可为其建立预测分析表，但表中必出现多重元素多重元素。非非LL(1)LL(1)文法文法所造表中所造表中,必有冲突元素。必有冲突元素。事实上事实上事实上事实上,是否有冲突元素也是是否有冲突元素也是是否有冲突元素也是是否有冲突元素也是判别一文法是否是判别一文法是否是判别一文法是否是判别一文法是否是LL(1)LL(1)LL(1)LL(1)文法的方法之一。文法的方法之一。文法的方法之一。文法的方法之一。n对某些对某

32、些非非LL(1)文法文法，可通过，可通过消除左递归消除左递归消除左递归消除左递归，反复，反复提取左因子提取左因子提取左因子提取左因子等方等方法将其改造成法将其改造成LL(1)文法文法。n n但是，但是，但是，但是，并非所有的非并非所有的非LL(1)文法都能改造为文法都能改造为LL(1)文法。文法。六、非LL(1)文法的改造计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理30从输入串开始，进行最左归约，直到到达文法的开始符号为从输入串开始，进行最左归约，直到到达文法的开始符号为从输入串开始，进行最左归约，直到到达文法的开始符号为从输入串开始，进行最左归约，直到到达文法的开

33、始符号为止。止。止。止。大致过程：大致过程：大致过程：大致过程：把输入符号逐个把输入符号逐个把输入符号逐个把输入符号逐个移进移进移进移进到一个到一个到一个到一个栈栈栈栈里，当栈顶形成里，当栈顶形成里，当栈顶形成里，当栈顶形成某个产生式的右部某个产生式的右部某个产生式的右部某个产生式的右部（句柄）句柄）句柄）句柄）时，把栈顶的这一部分替换成时，把栈顶的这一部分替换成时，把栈顶的这一部分替换成时，把栈顶的这一部分替换成（归约为）（归约为）（归约为）（归约为）它的左部符号。称作它的左部符号。称作它的左部符号。称作它的左部符号。称作“移进移进移进移进归约归约归约归约”分析。分析。分析。分析。自下而上分

34、析过程自下而上分析过程语法分析程序查找规约串依据 a+b#输出带#计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理31“移进移进移进移进-归约归约归约归约”分析对符号栈的使用有四类操作：分析对符号栈的使用有四类操作：分析对符号栈的使用有四类操作：分析对符号栈的使用有四类操作：移进移进移进移进、归约归约归约归约、接接接接受受受受和和和和出错处理出错处理出错处理出错处理。“移进一归约移进一归约移进一归约移进一归约”分析器使用分析器使用分析器使用分析器使用一个栈一个栈一个栈一个栈和一个存放输入符号串和一个存放输入符号串和一个存放输入符号串和一个存放输入符号串ww的的的的缓缓缓

35、缓冲器冲器冲器冲器。工作过程：自左至右将串工作过程：自左至右将串工作过程：自左至右将串工作过程：自左至右将串ww的符号依次入栈，一旦的符号依次入栈，一旦的符号依次入栈，一旦的符号依次入栈，一旦栈顶栈顶栈顶栈顶形成形成形成形成句句句句柄柄柄柄即即即即归约归约归约归约。归约可持续多次，直至栈顶不再呈现句柄为止。然后，。归约可持续多次，直至栈顶不再呈现句柄为止。然后，。归约可持续多次，直至栈顶不再呈现句柄为止。然后，。归约可持续多次，直至栈顶不再呈现句柄为止。然后，继续移进符号，重复这个过程，直至最终形成如下格局：继续移进符号，重复这个过程，直至最终形成如下格局：继续移进符号，重复这个过程，直至最终

36、形成如下格局：继续移进符号，重复这个过程，直至最终形成如下格局：栈栈栈栈输入输入输入输入#S#S#分析过程的每一步，栈中符号串与剩余输入符号串恰是一个规范分析过程的每一步，栈中符号串与剩余输入符号串恰是一个规范分析过程的每一步，栈中符号串与剩余输入符号串恰是一个规范分析过程的每一步，栈中符号串与剩余输入符号串恰是一个规范句型。且栈中符号串为该句型的一个句型。且栈中符号串为该句型的一个句型。且栈中符号串为该句型的一个句型。且栈中符号串为该句型的一个活前缀活前缀活前缀活前缀。总结活前缀：活前缀：活前缀：活前缀：是是是是 规范句型的一个前缀，且不含句柄之后的任规范句型的一个前缀，且不含句柄之后的任规

37、范句型的一个前缀，且不含句柄之后的任规范句型的一个前缀，且不含句柄之后的任何符号何符号何符号何符号，则称为该规范句型的一个，则称为该规范句型的一个，则称为该规范句型的一个，则称为该规范句型的一个活前缀活前缀活前缀活前缀。计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理32算符优先分析法算符优先分析法一、算符文法定义 算符文法算符文法CFGG=（VN,VT,P,S）,U,V,W均为非终结均为非终结符，符，x,y均为终结符。均为终结符。如果如果CFG(不含空产生式不含空产生式)G中没有形中没有形如如UVW的产生式，则称的产生式，则称G为算符文法（为算符文法（OG）。）。n推

38、论：推论：算符文法的任何句型都不含两个相邻的非终结符。算符文法的任何句型都不含两个相邻的非终结符。n终结符号终结符号终结符号终结符号a a与与与与b b之间的优先关系有三种：之间的优先关系有三种：之间的优先关系有三种：之间的优先关系有三种：a b表示表示a的优先级低于的优先级低于ba b表示表示a的优先级等于的优先级等于ba b表示表示a的优先级大于的优先级大于b计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理33二、算符优先关系定义 在在OG（算符优先文法）中（算符优先文法）中 nx=y G中有形如中有形如Uxy或或U xVy的产生式。的产生式。nxy G中有形如中有

39、形如 U Wy的产生式的产生式,而而W x或或W xVn n规定：规定：规定：规定：若若 S x或或 S Vx 则则#计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理34三、算符优先关系计算及其表示11定义定义定义定义nFIRSTVT(W)=y|WyWVynLASTVT(W)=x|WxWxV22三种关系计算三种关系计算三种关系计算三种关系计算nx=y：Uxy或或UxVynxy：每个非终结符：每个非终结符B的的FIRSTVT(B)，形如，形如UxB中，每个中，每个y FIRSTVT(B)，则有，则有xy：每个非终结符：每个非终结符B的的LASTVT(B)，形如，形如UBy

40、中，每个中，每个x LASTVT(B)，则有，则有xy成立。成立。计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理35对文法的每一非终结符号构造对文法的每一非终结符号构造FIRSTVT集和集和LASTVT集，算集，算法分别如下法分别如下)构造构造FIRSTVT集，置集，置FIRSTVT(A)=若文法中有形如若文法中有形如Ab或或ABb的规则，则的规则，则bFIRSTVT(A)若文法中有形如若文法中有形如AB的规则，则的规则，则FIRSTVT(B)FIRSTVT(A)计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理36)构造构造LASTVT集，置集

41、，置LASTVT(A)=若文法中有形如若文法中有形如Aa或或AaB的规则，则的规则，则aLASTVT(A)若文法中有形如若文法中有形如AB的规则，则的规则，则LASTVT(B)LASTVT(A)(2)(2)形如形如a Aa A的规则右部的规则右部，a FIRSTVT(A)a bSTVT(A)b )形如形如a ba b或或a A ba A b的规则右部的规则右部，a a=b=b(3)#(3)#STVT(S)#计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理373 3、算符优先文法算符优先文法算符优先文法算符优先文法在在OG文法文法G中，若任意两个终结符间至多只有三种算符中

42、，若任意两个终结符间至多只有三种算符优先关系优先关系=、中的一种算符优先关系存在，则称中的一种算符优先关系存在，则称G为算符为算符优先文法优先文法(OPG)。算符优先文法是无二义的。算符优先文法是无二义的。计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理381素短语：素短语：至少含有一个终结符号至少含有一个终结符号，并且，并且除自身之外不再含有任何更小的除自身之外不再含有任何更小的带有带有终结符号的短语终结符号的短语，则称为，则称为素短语素短语。2最左素短语：最左素短语：句型最左边的素短语。句型最左边的素短语。算符优先文法句型的最左素短语是算符优先文法句型的最左素短语是

43、唯一的。唯一的。EE+TE+TTT*FFi句型T+T*F+i的语法树最左素短语不一定是当前句型的句柄最左素短语不一定是当前句型的句柄最左素短语不一定是当前句型的句柄最左素短语不一定是当前句型的句柄最左素短语可能不是相应文法的任何产生式的右部。最左素短语可能不是相应文法的任何产生式的右部。按算符优先关系所确定的归约串恰好是当前句型的最左素短语按算符优先关系所确定的归约串恰好是当前句型的最左素短语计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理39 LR LR分析器概述分析器概述一、一、LRLR分析器构成分析器构成n总控程序总控程序(驱动程序驱动程序)。对所有。对所有LRL

44、R分析器都相同。分析器都相同。n分析表分析表(分析函数分析函数)。不同文法分析表不同，同一文法采用的。不同文法分析表不同，同一文法采用的LRLR分析器不同时，分析表也将不同。分析器不同时，分析表也将不同。n分析栈。分析栈。包括文法符号栈和相应的状态栈。包括文法符号栈和相应的状态栈。总控程序总控程序outputInput(#)LR分析表分析表ACTIONGOTOS0#Sm Xm 状态栈状态栈符号栈符号栈计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理401 1 分析表构成分析表构成 动作表动作表(ACTION)ACTIONS,a：表示在当前状态表示在当前状态S下，面临扫描

45、符号下，面临扫描符号a所应采取的动所应采取的动作。动作有四种：移进、归约、出错、接受。作。动作有四种：移进、归约、出错、接受。转向表转向表(GOTO)GOTOS，X：若：若X VT，表示在当前状态下，读入，表示在当前状态下，读入a应转向什么状态；应转向什么状态；若若X VN，表示当前栈顶句柄归约成，表示当前栈顶句柄归约成X后，应转向什么状态。后，应转向什么状态。移进移进 ai 和和s=gotosm,ai进栈进栈actionsm,ai=归约归约 rj:AXm-r+1Xm-r+2Xm 接受接受 s=gotosm-r,A 出错出错计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原

46、理41注：注：注：注：对于终结符的转向动作，可与其移进动作合并在一起填对于终结符的转向动作，可与其移进动作合并在一起填在动作表中，这样转向表可进行压缩，只保留非终结符转向在动作表中，这样转向表可进行压缩，只保留非终结符转向部分。部分。ACTIONGOTOa1a2anS0S1SkA1A2AmS5r4acc28计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理422 LR2 LR分析器的总控程序分析器的总控程序 总控程序的动作由当前栈顶状态总控程序的动作由当前栈顶状态Sm和扫描符号和扫描符号ai查表决定。查表决定。1 1）移进移进移进移进 把把(Sm,ai)的下一状态的下一状

47、态S=GOTOSm，ai连同连同扫描符号扫描符号进栈，栈顶进栈，栈顶成成(S,ai)，扫描指针后移；，扫描指针后移；2 2）归约）归约）归约）归约 用产生式用产生式A进行归约。若进行归约。若 的长度为的长度为，则弹出栈顶则弹出栈顶 项，使栈顶项，使栈顶状态变为状态变为Sm-，然后将，然后将(Sm-,A)的下一状态的下一状态S=GOTOSm-,A连同连同A一一起起入入栈，栈顶变为栈，栈顶变为(S,A)。扫描指针不动，即不改变现行输入符号。扫描指针不动，即不改变现行输入符号。3 3）接受）接受）接受）接受 4 4）报错）报错）报错）报错注：注：不管哪一类分析程序，总控程序的动作都一样。计算机学院计

48、算机学院计算机学院计算机学院2023/1/4编译原理编译原理43LRLR分析总结分析总结n 特征特征n规范的；n符号栈中的符号是规范句型的前缀，且不含句柄以后的任何符号(活前缀)；n分析决策依据栈顶状态和现行输入符号。识别活前缀的 DFA.n 四种技术四种技术n LR(0)SLR(1)LR(1)计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理44 在规范归约的句型中，不含有句柄以后任何符号的前缀在规范归约的句型中，不含有句柄以后任何符号的前缀称为活前缀。它有两种情况：归态活前缀和非归态活前缀。称为活前缀。它有两种情况：归态活前缀和非归态活前缀。归态活前缀归态活前缀归态活

49、前缀归态活前缀 活前缀尾部正好是句柄之尾，这时可进行归约。归约活前缀尾部正好是句柄之尾，这时可进行归约。归约后又会成为另一句型的活前缀。后又会成为另一句型的活前缀。非归态活前缀非归态活前缀非归态活前缀非归态活前缀 句柄尚未形成，需要继续移进若干符号后才能形成。句柄尚未形成，需要继续移进若干符号后才能形成。活前缀计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理45一、LR(0)分析表的基本策略状态状态DFA状态的转换状态的转换构造文法构造文法GG的一个的一个DFADFA，用于识别所有活前缀。，用于识别所有活前缀。由若干由若干LR(0)项目所组成的项目所组成的集合集合(项目

50、集项目集项目集项目集)来表示。来表示。由分析过程中由分析过程中的的移进归约移进归约移进归约移进归约操作引发。操作引发。LR(0)LR(0)分析表的构造分析表的构造计算机学院计算机学院计算机学院计算机学院2023/1/4编译原理编译原理46n定义：定义：n对文法对文法G的的每个产生式右部添加一个圆点每个产生式右部添加一个圆点，称为，称为G的一个的一个LR(0)项目项目(简称项目简称项目)。A或或An注：注：添加位置不同，叫做不同项目。添加位置不同，叫做不同项目。n用圆点用圆点“”表示识别一个产生式右部符号到达的位置，表示识别一个产生式右部符号到达的位置，项目记录了项目记录了当前活前缀状况。当前活