研究生院第四章_2_

1、1第四章第四章 语法分析语法分析分析器的作用分析器的作用上下文无关文法的分析上下文无关文法的分析自上而下的分析自上而下的分析自底向上的分析自底向上的分析LR分析器分析器二义文法的应用二义文法的应用Yacc介绍介绍2自底向上的分析（自底向上的分析（1）什么是自底向上的分析什么是自底向上的分析使用了显式栈来完成分析，栈中包括终结符号和非终结符使用了显式栈来完成分析，栈中包括终结符号和非终结符号，以及其他的一些信息等号，以及其他的一些信息等$InputString$StartSymbol $接受接受分析器根据当前栈中的符号以及向前看的分析来决定分析分析器根据当前栈中的符号以及向前看的分析来决定分析器

2、的动作：器的动作：接受接受移进移进归约归约报错报错要对文法进行扩展要对文法进行扩展也称为移进也称为移进-归约分析，包括算符优先分析、归约分析，包括算符优先分析、LR分析分析3自底向上的分析（自底向上的分析（2）自底向上的分析与预测分析器的比较自底向上的分析与预测分析器的比较一般而言，自底向上的分析功能更强大一般而言，自底向上的分析功能更强大如：预测分析器不能处理左递归等，而自底向上的分析则不如：预测分析器不能处理左递归等，而自底向上的分析则不成问题成问题对栈和向前看的符号的使用上：对栈和向前看的符号的使用上：可以将输入符号移进栈，直至它判断出要执行的动作为止可以将输入符号移进栈，直至它判断出要

3、执行的动作为止进行动作判断时可以使用栈中所有的符号进行动作判断时可以使用栈中所有的符号开始时栈为空，而接受时栈中为文法的开始符号开始时栈为空，而接受时栈中为文法的开始符号预测分析器描述的是从文法开始符号推导得到句子的过程预测分析器描述的是从文法开始符号推导得到句子的过程,是一个匹配的过程，而自底向上的分析描述的推导过程的是一个匹配的过程，而自底向上的分析描述的推导过程的逆过程，是一个归约的过程逆过程，是一个归约的过程错误恢复：自底向上的分析所使用的特定算法的能力会影错误恢复：自底向上的分析所使用的特定算法的能力会影响到分析程序是否可早些检测出错误的能力，规范的响到分析程序是否可早些检测出错误的

4、能力，规范的LR分分析甚至在报告错误之前不做任何无效的归约析甚至在报告错误之前不做任何无效的归约自底向上的分析器较为复杂自底向上的分析器较为复杂4自底向上的分析（自底向上的分析（3）自底向上分析举例自底向上分析举例为输入串构造分析树是叶节点开始的，直至逆序为输入串构造分析树是叶节点开始的，直至逆序得到根节点得到根节点文法：文法：SaABeAAbc | bBd句子句子abbcde的归约过程：的归约过程：abbcdeaAbcdeaAdeaABeS对应的最右推导：对应的最右推导：abbcdeaAbcdeaAdeaABeSrmrmrmrm5自底向上的分析（自底向上的分析（4）A Ab ba ab bc

5、 cd de eA AB BS SabbcdeaAbcdeaAdeaABeSrmrmrmrm6自底向上的分析（自底向上的分析（5）句柄句柄定义：定义：右句型右句型(最右推导可得到的句型最右推导可得到的句型)的的句柄句柄是一个产生式是一个产生式A以及以及中的一个位置，在这个位置可找到串中的一个位置，在这个位置可找到串，用用A代代替替得到最右推导的前一个右句型。即如果有如下的最右得到最右推导的前一个右句型。即如果有如下的最右推导序列推导序列则在则在后的后的A是是的句柄。的句柄。非形式的说法：非形式的说法：一个串的句柄是和一个产生式右部匹配的子串，并且，把一个串的句柄是和一个产生式右部匹配的子串，并

6、且，把它归约成该产生式左部的非终结符代表了最右推导逆过程它归约成该产生式左部的非终结符代表了最右推导逆过程的一步的一步唯一性：唯一性：文法无二义时，句柄是唯一的；否则，句柄不一定唯一文法无二义时，句柄是唯一的；否则，句柄不一定唯一ASrm*rm7自底向上的分析（自底向上的分析（6）上例中的句柄上例中的句柄Ab是右句型是右句型abbcde的句柄，它的位置？的句柄，它的位置？AAbc是右句型是右句型aAbcde的句柄，它的位置？的句柄，它的位置？简称：简称：如果清楚地知道句柄的位置和应用的产生式的话，可以直如果清楚地知道句柄的位置和应用的产生式的话，可以直接说子串接说子串是是的句柄的句柄作用：作用

7、：移进移进-归约分析器将终结符号从输入移进到栈中，直到归约分析器将终结符号从输入移进到栈中，直到它能执行一个归约得到下一个右句型它能执行一个归约得到下一个右句型判断分析中的下一个句柄是移进判断分析中的下一个句柄是移进-归约分析器的主要任归约分析器的主要任务务句柄总是为它的产生式构成一个完整的右部，而这个句柄总是为它的产生式构成一个完整的右部，而这个产生式是下一步归约中应用的产生式，而且归约发生产生式是下一步归约中应用的产生式，而且归约发生时，句柄的最右边的位置与栈的顶部对应时，句柄的最右边的位置与栈的顶部对应8自底向上的分析（自底向上的分析（7）句柄代表了最左边的由一个内部节点和它所有的下一代

8、组句柄代表了最左边的由一个内部节点和它所有的下一代组成的子树成的子树句柄的右边符号串只含有终结符号句柄的右边符号串只含有终结符号活前缀：一个规范句型的一个前缀，如果不含句柄后的任活前缀：一个规范句型的一个前缀，如果不含句柄后的任何符号，则称它为该规范句型的一个活前缀何符号，则称它为该规范句型的一个活前缀活前缀不超过最右句柄的右端，因此在活前缀的右端加上一活前缀不超过最右句柄的右端，因此在活前缀的右端加上一些终结符后可以使它成为右句型些终结符后可以使它成为右句型只要输入串的已扫描部分可以归约成一个活前缀，意味着所只要输入串的已扫描部分可以归约成一个活前缀，意味着所扫描的部分没有错误扫描的部分没有

9、错误S SA A9自底向上的分析（自底向上的分析（8）例例1：考虑表达式文法：考虑表达式文法 EE+E | E*E | （E）| id对于最右推导：对于最右推导：但这个文法是有二义性的，因此存在另一个最右推导但这个文法是有二义性的，因此存在另一个最右推导321*rm32*rm3*rm*rm*rmid*idid id*idE id*EE E*EE EEE10自底向上的分析（自底向上的分析（9）移进移进-归约分析的实现归约分析的实现用栈来保存文法符号，输入缓冲区来保存待分析用栈来保存文法符号，输入缓冲区来保存待分析的串的串句柄的选择：句柄的选择：如何决定右句型中要归约的子串如何决定右句型中要归约的

10、子串当一个要归约的子串是多个产生式的右部时，如当一个要归约的子串是多个产生式的右部时，如何确定选择哪个产生式何确定选择哪个产生式动作动作（1）移进：将下一个输入符号移进栈顶）移进：将下一个输入符号移进栈顶（2）归约：句柄位于栈顶，必须在栈中确定完整的句柄，）归约：句柄位于栈顶，必须在栈中确定完整的句柄，并决定用哪个产生式归约并决定用哪个产生式归约（3）接受：分析成功）接受：分析成功（4）出错：报告错误，调用错误恢复例程）出错：报告错误，调用错误恢复例程11自底向上的分析（自底向上的分析（10）栈栈输输 入入动动 作作 (1) $ id1+id2*id3$ 移进移进 (2) $id1 +id2*

11、id3$ 按按Eid归约归约 (3) $E +id2*id3$ 移进移进 (4) $E+ id2*id3$ 移进移进 (5) $E+id2 *id3$ 按按Eid归约归约 (6) $E+E *id3$ 移进移进 (7) $E+E* id3$ 移进移进 (8) $E+E*id3 $ 按按Eid归约归约 (9) $E+E*E $ 按按EE*E归约归约 (10)$E+E $ 按按EE+E归约归约 (11)$E $ 接受接受12自底向上的分析（自底向上的分析（11）移进移进-归约分析的冲突归约分析的冲突移进移进-归约冲突归约冲突根据栈中所有的内容和下一个输入符号不能决定是移进还是根据栈中所有的内容和下

12、一个输入符号不能决定是移进还是归约归约归约归约-归约冲突归约冲突根据栈中所有的内容和下一个输入符号不能决定使用哪一个根据栈中所有的内容和下一个输入符号不能决定使用哪一个产生式归约产生式归约移进移进-归约分析的冲突的解决归约分析的冲突的解决利用移进优先的约定可以解决一些二义性文法引起的冲突利用移进优先的约定可以解决一些二义性文法引起的冲突（如（如if then else ）对于有些情况要借助其它信息解决，如对于有些情况要借助其它信息解决，如FORTRAN语言中语言中数组引用和过程调用：数组引用和过程调用：A( i , j , k )，i、j、k是数组的下标表达式还是参数？是数组的下标表达式还是参

13、数？13LR分析器分析器（1）LR分析算法分析算法LR文法文法LR(0)分析分析SLR(1)分析分析LR(1)规范分析规范分析LALR(1)分析分析14LR分析器分析器（2）LR(k)分析分析L指从左到右扫描输入，指从左到右扫描输入，R指构造最右推导的逆，指构造最右推导的逆，k指的是指的是在决定分析动作时向前看的符号个数，在决定分析动作时向前看的符号个数，(k)省略时，表示省略时，表示k是是1LR(k)分析能力强大分析能力强大LR分析器能够构造识别所有上下文无关文法写的程序设计语分析器能够构造识别所有上下文无关文法写的程序设计语言的结构言的结构LR分析方法是已知的最一般的无回溯移进分析方法是已

14、知的最一般的无回溯移进-归约方法，它能归约方法，它能够和其他移进够和其他移进-归约方法一样有效地实现归约方法一样有效地实现LR方法能分析的文法类是预测分析法能分析的文法类的真超方法能分析的文法类是预测分析法能分析的文法类的真超集集LR分析器能及时察觉语法错误，快到自左向右扫描输入的最分析器能及时察觉语法错误，快到自左向右扫描输入的最大可能大可能手工构造手工构造LR分析器的工作量太大，但可以利用专门的工分析器的工作量太大，但可以利用专门的工具（如具（如Yacc）来构造来构造如果文法二义或有其它难以自左向右分析的结构，分析器的如果文法二义或有其它难以自左向右分析的结构，分析器的生成器能定位这些结构

15、并报告生成器能定位这些结构并报告15LR分析器分析器（3）LR分析算法分析算法组成组成驱动程序对所有的驱动程序对所有的LR分析器是一样的，只是分析表不同分析器是一样的，只是分析表不同栈中存储形如栈中存储形如s0X1s1X2s2Xmsm的串，其中的串，其中sm在栈顶，在栈顶，Xi是是文法符号，文法符号，si是是状态状态符号，它概括了栈中它下面部分所包符号，它概括了栈中它下面部分所包含的信息含的信息输输入入栈栈L LR R分分析析程程序序输输出出a ac ct ti io on nL LR R分分析析器器模模型型a a1 1. . . .a ai i. . . .a an n$ $s sm mX

16、Xm ms sm m- -1 1X Xm m- -1 1. . . .s s0 0g go ot to o16LR分析器分析器（4）分析表包括动作函数分析表包括动作函数action和转移函数和转移函数goto两部两部分组成分组成根据栈顶当前的状态根据栈顶当前的状态sm和当前的输入符号和当前的输入符号ai访问访问actionsm , ai，取值包括：取值包括：移进移进s，其中，其中s是一个状态是一个状态按文法产生式按文法产生式A归约归约接受接受出错出错函数函数goto取状态和文法符号为变元，产生一个状态取状态和文法符号为变元，产生一个状态vLR分析器栈中的文法符号总是形成活前缀分析器栈中的文法符

17、号总是形成活前缀v在在LR(0)分析、分析、SLR分析、规范分析、规范LR分析和分析和LALR分析中分析中，构造一个识别文法，构造一个识别文法G的活前缀的确定有限自动机，的活前缀的确定有限自动机，则则goto函数是这个自动机的状态转换函数，初始状态函数是这个自动机的状态转换函数，初始状态是初启时置于是初启时置于LR分析器栈中的状态分析器栈中的状态17LR分析器分析器（5）LR分析器的分析器的格局格局是二元组是二元组它的第一个成分是栈的内容，第二个成分是尚未接收它的第一个成分是栈的内容，第二个成分是尚未接收的输入：的输入：(s0X1s1X2s2Xmsm，aiai+1an$)，这个格局，这个格局代

18、表右句型代表右句型X1X2Xmaiai+1an动作：动作：移进：移进：如果如果actionsm , ai=移进移进s，分析器执行移进动作，进分析器执行移进动作，进入格局入格局(s0X1s1X2s2Xmsmais，ai+1an$) ，其中，其中s=gotosm , ai18LR分析器分析器（6）归约：归约：如果如果actionsm , ai=归约归约A, 则分析器执行归约则分析器执行归约, 进进入格局入格局(s0X1s1X2s2Xm-rsm-rAs， aiai+1an$), 其中其中s=gotosm-r , A，r是是的长度，的长度，完成这个动作时，首先从栈中弹出完成这个动作时，首先从栈中弹出2

19、r个符号（包括个符号（包括r个状态符号和个状态符号和r个文法符号，这些文法符号刚好匹配个文法符号，这些文法符号刚好匹配产生式右部产生式右部 ），然后将产生式左边的非终结符），然后将产生式左边的非终结符A和和gotosm-r , A的状态的状态s压入栈压入栈在归约动作时执行与归约产生式相关的语义动作在归约动作时执行与归约产生式相关的语义动作接受：接受：如果如果actionsm , ai=接受，分析完成接受，分析完成出错：出错：如果如果actionsm , ai=出错，分析器发现错误，调用错出错，分析器发现错误，调用错误恢复例程误恢复例程19LR分析器分析器（7）LR分析算法分析算法输入：输入：L

20、R分析表和输入串分析表和输入串输出：若输出：若是句子，得到是句子，得到的自下而上分析，否则报错的自下而上分析，否则报错方法：方法：将初始状态将初始状态s0在分析器的栈顶，在分析器的栈顶，$在输入缓冲区在输入缓冲区让让ip指向指向$的第一个符号的第一个符号repeat forever begin令令s是栈顶的状态，是栈顶的状态，a是是ip指向的符号指向的符号if actions , a = 移进移进s then begin把把a和和s依次压入栈依次压入栈推进推进ip指向下一个输入符号指向下一个输入符号endelse if actions , a=归约归约A then begin栈顶弹出栈顶弹出2

21、*|个符号个符号令令s是现在的栈顶状态是现在的栈顶状态把把A和和gotos , A压入栈压入栈输出产生式输出产生式A或作相关的语义动作或作相关的语义动作endelse if actions , a=接受接受 then returnelse error()end20LR分析器分析器（8）表达式文法：对文法产生式标号表达式文法：对文法产生式标号(1) EE+T(2) ET(3) TT*F(4) TF(5) F(E)(6) Fid为了表示的简便，对各类动作如下简化表示：为了表示的简便，对各类动作如下简化表示：(1) si表示移进，把当前输入符号和状态表示移进，把当前输入符号和状态i压进栈压进栈(2)

22、 rj表示按第表示按第j个产生式进行归约个产生式进行归约(3) acc表示接受表示接受(4) 空白表示出错空白表示出错21LR分析器分析器（9）状 态状 态动 作动 作id + * ( ) $id + * ( ) $0 0s5s51 12 23 34 4s5s55 56 6s5s57 7s5s58 89 910101111s6s6r2r2r4r4accaccs6s6r1r1r3r3r5r5s7s7r4r4r4r4r4r4r2r2r2r2s4s4s4s4r6r6r6r6r6r61 1s4s4s4s4s11s11s7s7r1r1r1r1r3r3r3r3r3r3r5r5r5r5r5r5转 移转 移E

23、 T FE T Fr6r62 23 310102 23 39 93 38 822LR分析器分析器（10）栈栈输输 入入动动 作作 (1) 0 id*id+id$ 移进移进 (2) 0 id 5 *id+id$ 按按Fid归约归约 (3) 0 F 3 *id+id$ 按按TF归约归约 (4) 0 T 2 *id+id$ 移进移进 (5) 0 T 2 * 7 id+id$ 移进移进 (6) 0 T 2 * 7 id 5 +id$ 按按Fid归约归约 (7) 0 T 2 * 7 F 10 +id$ 按按TT*F归约归约 (8) 0 T 2 +id$ 按按ET归约归约 (9) 0 E 1 +id$ 移

24、进移进 (10)0 E 1 + 6 id$ 移进移进 (11)0 E 1 + 6 id 5 $ 按按Fid归约归约 (12)0 E 1 + 6 F 3 $ 按按TF归约归约 (13)0 E 1 + 6 T 9 $ 按按EE+T归约归约 (14)0 E 1 $ 接受接受23LR分析器分析器（11）LR文法文法定义：一个文法，如果能够为它构造出定义：一个文法，如果能够为它构造出LR分析表，且表分析表，且表的条目都唯一的条目都唯一性质：性质：一个文法如果是一个文法如果是LR的，只要保证当句柄出现在栈顶时，自左的，只要保证当句柄出现在栈顶时，自左向右扫描的移进向右扫描的移进-归约分析器能够及时识别它便

25、足够了归约分析器能够及时识别它便足够了如果句柄出现在栈顶时，如果句柄出现在栈顶时，LR分析器不需要扫描整个栈，栈顶分析器不需要扫描整个栈，栈顶的状态符号包含了所需要的一切信息的状态符号包含了所需要的一切信息LR(k)文法：最多向前看文法：最多向前看k个符号就可以决定动作的个符号就可以决定动作的LR分分析器分析的文法称为析器分析的文法称为LR(k)文法文法与与LL文法的区别：文法的区别：LR(k)文法：在看见了产生式右部推导出的所有东西和文法：在看见了产生式右部推导出的所有东西和k个向个向前看的符号后，能识别产生式右部的出现前看的符号后，能识别产生式右部的出现LL(k)文法：在看见了右部推出的前

26、文法：在看见了右部推出的前k个符号就能识别所使用个符号就能识别所使用的产生式的产生式24LR分析器分析器（12）LR(0)项目的有限自动机项目的有限自动机LR(0)项目（项目（LR(0) item，简称项目、，简称项目、item）：）：是是在右部带有区分位置（一般是用一个在右部带有区分位置（一般是用一个“.”表示表示这个区分的位置）的产生式这个区分的位置）的产生式如果如果A是一个产生式，且是一个产生式，且=，则则A.是是LR(0)项目，其中项目，其中和和可以是空串可以是空串。如果如果A是一个产生式，则它只对应了一个项目是一个产生式，则它只对应了一个项目A.项目的解释：项目的解释：项目项目A.表

27、示已经看到了表示已经看到了(此时，此时，必须出现在栈的必须出现在栈的顶部顶部)，且可能从下面的输入符号中获取，且可能从下面的输入符号中获取项目项目A.表示将要用产生式表示将要用产生式A来识别来识别A，这种项目这种项目也称为初始项目也称为初始项目项目项目A.表示表示出现在分析栈的顶部，而且如果出现在分析栈的顶部，而且如果A在下一个归约中使用，则它可能是句柄，这种项目称在下一个归约中使用，则它可能是句柄，这种项目称为完整项目为完整项目25LR分析器分析器（13）例例2：考虑文法：考虑文法S(S)S | ，给出给出LR(0)项目项目首先构造拓广文法：加入一个产生式首先构造拓广文法：加入一个产生式SS

28、，分析器执行归分析器执行归约约SS时，表示分析成功时，表示分析成功在构造在构造LR(0)项目，共项目，共8个个 S.S SS. S.(S)S S(.S)S S(S.)S S(S).S S(S)S. S.26LR分析器分析器（14）LR(0)项目集合的有限自动机的构造项目集合的有限自动机的构造若有项目若有项目A.，且假设且假设以符号以符号X（终结符或非终终结符或非终结符）开始（即结符）开始（即=X），），则读入则读入X后，项目变为后，项目变为AX.，在自动机中有一个标记为在自动机中有一个标记为X的由状态的由状态A.X到状态到状态AX.的转换的转换这个转换的意义是：这个转换的意义是：如果如果X是一

29、个终结符，表示是一个终结符，表示X在分析中被从输入移进到在分析中被从输入移进到栈的顶部栈的顶部如果如果X是一个非终结符，可以理解为是用产生式是一个非终结符，可以理解为是用产生式X归约时发生，这个归约前面必须有一个归约时发生，这个归约前面必须有一个的识别，而由的识别，而由初始项目初始项目X.给出的状态表明这个识别的开始，此时给出的状态表明这个识别的开始，此时，必须考虑加入下面的转换，必须考虑加入下面的转换如果如果X是非终结符，则对每个项目是非终结符，则对每个项目A.X，添加一添加一个到项目个到项目X.的的转换（如果以转换（如果以X为左部的产生式多为左部的产生式多于一个，则每个都要如此处理）于一个

30、，则每个都要如此处理）27LR分析器分析器（15）自动机的初始状态与分析程序的初始状态对应：栈是自动机的初始状态与分析程序的初始状态对应：栈是空的，且将要识别一个文法的开始符号空的，且将要识别一个文法的开始符号S，但由于但由于S可可能出现在多个产生式的左部，所以拓广文法，加入能出现在多个产生式的左部，所以拓广文法，加入S和产生式和产生式SS，S是拓广文法的开始符号，是拓广文法的开始符号，S.S是是自动机的开始状态自动机的开始状态自动机的接受状态：此处的自动机是用于了解分析的自动机的接受状态：此处的自动机是用于了解分析的状态，而不是完全识别串，因此分析程序本身决定何状态，而不是完全识别串，因此分

31、析程序本身决定何时接受，自动机不必关心，所以可以没有接受状态时接受，自动机不必关心，所以可以没有接受状态28LR分析器分析器（16）例例2对应的对应的NFA：S S. .S SS S. .( (S S) )S SS S( (. .S S) )S SS SS S. .S S. .S S( (S S) )S S. .S S( (S S. .) )S SS S( (S S) ). .S SS S( (S S) )S S29LR分析器分析器（17）例例2对应的对应的DFA：S.SS.SS.(S)SS.(S)SS.S.0 0S(.S)SS(.S)SS.(S)SS.(S)SS.S.2 2SS.SS.1 1

32、S(S.)SS(S.)S3 3S(S).SS(S).SS.(S)SS.(S)SS.S.4 4S(S)S.S(S)S.5 5S S( (S S) )S S( ( (30LR分析器分析器（18）文法的文法的LR项目的闭包计算项目的闭包计算对于文法对于文法G的的LR项目集项目集I，闭包闭包closure(I)的计算：的计算：J := Irepeatfor J 的每个项目的每个项目A.B和和G的每个产生式的每个产生式B，若若B.不在不在J中中 do把把B.加入加入Juntil 没有更多的项目可以加入没有更多的项目可以加入JLR(0)分析算法分析算法仅根据栈中的符号就可以决定动作仅根据栈中的符号就可以决

33、定动作若项目若项目A.a属于属于Ik且且GO1(Ik，a)= Ij，a为终结符，则置为终结符，则置ACTIONk，a为为sj若项目若项目A.属于属于Ik，那么对任何终结符，那么对任何终结符a（或结束符（或结束符$），置），置ACTIONk，a为为rj(假定产生式假定产生式A是文法的第是文法的第j个产生式个产生式)若项目若项目SS.属于属于Ik，则置，则置ACTIONk，$为接受为接受若若GOIk，A= Ij ，A为非终结符，则置为非终结符，则置gotok，A=j。分析表中凡不能用规则分析表中凡不能用规则14填入信息的空白格均置为报错填入信息的空白格均置为报错1此处的此处的GO是指自动机的状态转

34、换，而不是是指自动机的状态转换，而不是LR分析中的转移表（用分析中的转移表（用goto表示）表示）31LR分析器分析器（19）项目的分类：项目的分类：核心项目：包括初始项目核心项目：包括初始项目S.S和所有点不在左和所有点不在左端的项目端的项目非核心项目：它们的点都在左端非核心项目：它们的点都在左端项目分类的意义：项目分类的意义：DFA应用的项目集是核心项目的闭包形成应用的项目集是核心项目的闭包形成若有一个文法，核心项目唯一地判断出状态以及若有一个文法，核心项目唯一地判断出状态以及它的转换，则只需指出核心项目就可以完整地表它的转换，则只需指出核心项目就可以完整地表示出项目集合的示出项目集合的D

35、FA32LR分析器分析器（20）SLR分析分析规范的规范的LR(0)族：提供了构造族：提供了构造SLR分析表的基础分析表的基础对于对于LR(0)规范族中的项目集：规范族中的项目集：I = X.b, A. , B. LR(0)无法区分这三个不冲突的项目，此时要考察无法区分这三个不冲突的项目，此时要考察FOLLOW(A)和和FOLLOW(B)集合集合构造算法：构造算法：C := closure(S.S)repeatfor 对对C的每个项目集的每个项目集I和每个文法符号和每个文法符号X，若若goto(I , X)非空且不在非空且不在C中中 do把把goto(I , X)加入加入C中中until 没有

36、更多的项目可以加入没有更多的项目可以加入C33LR分析器分析器（21）例例3：拓广的表达式文法：拓广的表达式文法：EEEE+T | TTT*F | FF(E) | id对应的对应的LR(0)项目集规范族如下：项目集规范族如下：I0:E.E I5: Fid.E .E+TE .T I6: EE+.TT .T*FT.T*FT .FT.FF .(E)F.(E)F .idF.id34LR分析器分析器（22）I1:EE. I7: TT*.FE E.+TF.(E)F.idI2: E T.T T.*F I8: F(E.)EE.+TI3: T F. I9: EE+T.I4: F (.E)TT.*FE .E+TE

37、 .T I10: TT*F.T .T*FT .F I11: F(E).F .(E)F .id35LR分析器分析器（23）I I0 0I I1 1I I6 6I I9 9I I2 2E E+ +T T* *指向I指向I7 7F F指向I指向I3 3( (指向I指向I4 4idid指向I指向I5 5I I7 7I I1010* *F F( (指向I指向I4 4idid指向I指向I5 5I I3 3I I4 4I I8 8I I1111E E) )+ +指向I指向I6 6T T指向I指向I2 2F F指向I指向I3 3I I5 5idididid( (F FT T( (36LR分析器分析器（24）如

38、果将这个如果将这个DFA中的每个状态定为接受状态，而中的每个状态定为接受状态，而I0定为初定为初态，则这个态，则这个DFA识别文法的活前缀识别文法的活前缀对于项目对于项目A1.2对活前缀对活前缀1是是有效有效的，是指存的，是指存在推导序列在推导序列A1.2对活前缀对活前缀1有效表明当有效表明当1在分析栈顶时在分析栈顶时v如果如果2是是，则则A1是句柄，应该用这个产生式归约是句柄，应该用这个产生式归约v如果如果2不是不是，则表示句柄还没有完全进栈，要继续移进则表示句柄还没有完全进栈，要继续移进同一个活前缀的两个有效项目可能对应了不同的动作同一个活前缀的两个有效项目可能对应了不同的动作，引起了冲突

39、，引起了冲突v这种冲突可以通过向前看几个符号解决，也可以通过其这种冲突可以通过向前看几个符号解决，也可以通过其它方式解决它方式解决AS21rm*rm37LR分析器分析器（25）SLR分析表的构造分析表的构造输入：拓广文法输入：拓广文法G输出：输出：G的的SLR分析表函数分析表函数action和和goto方法：方法：(1)构造构造C=I0 , I1 , , In ，即即G的的LR(0)项目集规范族项目集规范族 (2)状态状态i从从Ii构造，它的动作如下确定：构造，它的动作如下确定： (a) 如果如果A.a在在Ii中，并且中，并且( Ii , a) = Ij，则置则置 action(i , a)为

40、为sj,含义是把含义是把a和状态和状态j移进栈移进栈, a必须为终结符必须为终结符 (b) 如果如果A.在在Ii中，则对中，则对FOLLOW(A)中的所有中的所有a，置置 action(i , a)为为rj, j是产生式是产生式A的编号。含义是按产生的编号。含义是按产生 式式A归约，这里归约，这里A不是不是S (c) 如果如果SS.在在Ii中，则置中，则置action(i , $)=acc，表示接受表示接受 (3)对所有的非终结符对所有的非终结符A，使用下面的规则构造状态使用下面的规则构造状态i的转移：的转移： 如果如果( Ii , A) = Ij，则则gotoi , A=j (4)不能由规则

41、不能由规则(2)和和(3)定义的条目置为出错定义的条目置为出错 (5)分析器的初始状态是包含分析器的初始状态是包含S.S的项目集对应的状态的项目集对应的状态38LR分析器分析器（26）如果在规则如果在规则(2)的构造中产生的动作有冲突，则该文的构造中产生的动作有冲突，则该文法不是法不是SLR(1)文法文法由上述算法生成的分析表成为文法由上述算法生成的分析表成为文法G的的SLR(1)分析表分析表每个每个SLR(1)文法都不是二义的文法都不是二义的存在非二义的文法，这个文法不是存在非二义的文法，这个文法不是SLR(1)的的对于在栈顶状态对于在栈顶状态s中的任何项目中的任何项目A.X，当当X是一个是

42、一个终结符，且终结符，且X在在FOLLOW (B)中时，中时，s中没有完整的项中没有完整的项目目B.。（。（若不满足，则存在移进若不满足，则存在移进-归约冲突）归约冲突）对于在对于在s中的任何两个完整项目中的任何两个完整项目A.和和B.，FOLLOW(A)与与FOLLOW(B)的交集为空集。（若不满的交集为空集。（若不满足，则存在归约足，则存在归约-归约冲突）归约冲突）SLR(1)分析能力比分析能力比LR(0)强，但仍然不能够满足要求强，但仍然不能够满足要求39LR分析器分析器（27）LR(1)规范分析规范分析SLR分析不能解决某些移进分析不能解决某些移进-归约冲突，而归约冲突，而LR(1)规

43、范规范分析可以，参考陈意云书的例分析可以，参考陈意云书的例3.31和和3.32LR(1)项目：项目：A.，a，其中其中A是产生式，是产生式，a是终结符号或是终结符号或$。1是指第二个成分的长度，这个成分称为项目的搜索符是指第二个成分的长度，这个成分称为项目的搜索符搜索符对搜索符对非空的项目非空的项目A.，a是不起作用的，但对是不起作用的，但对项目项目A. ，a，表示只有在下一个输入符号为表示只有在下一个输入符号为a时才能要求按时才能要求按A归约归约SLR(1)和和LR(1)对向前看符号的使用的不同：对向前看符号的使用的不同：SLR(1)是在是在LR(0)项目的项目的DFA构造完成后才考虑提供向

44、构造完成后才考虑提供向前看的符号，前看的符号，DFA的构造中不考虑向前看的符号的构造中不考虑向前看的符号LR(1)是在一开始就考虑向前看符号，是在一开始就考虑向前看符号，DFA的构造是在的构造是在考虑向前看符号的基础上进行的考虑向前看符号的基础上进行的40LR分析器分析器（28）LR(1)项目项目A.，a对活前缀对活前缀是是有效有效的，如果存的，如果存在着推导在着推导 其中：其中： = a是是的第一个符号，或者的第一个符号，或者是是则则a是是$例：考虑文法例：考虑文法SBB BaB | b对于最右推导：对于最右推导： ，项目，项目Ba.B，a对于对于活前缀活前缀 =aaa是有效的，是有效的，=

45、aa，A=B，=ab， =a和和=B对于最右推导：对于最右推导： ，项目，项目Ba.B，$对于活前对于活前缀缀Baa是有效的是有效的ASrm*rmaaaBabaaBabSrm*rmBaaBBaBSrm*rm41LR分析器分析器（29）有效的有效的LR(1)项目集族的构造方法本质上和构造项目集族的构造方法本质上和构造LR(0)项目集项目集规范族的方法是一样的规范族的方法是一样的Closure函数的构造：函数的构造：v考虑对活前缀考虑对活前缀有效的项目集中的项目有效的项目集中的项目A.B，a。必定存在一个最右推导必定存在一个最右推导 , 其中其中=，假定假定ax推出终结符串推出终结符串by，则对每

46、个形式则对每个形式B的产的产生式，有推导生式，有推导 ，于是，于是B.，b对对有效有效vb可能是从可能是从推出的第一个终结符，或者推出的第一个终结符，或者是空串，是空串，b就成了就成了a，即即b = FIRST(ax)，但在此处，考虑到但在此处，考虑到a是终结符，所以是终结符，所以有有FIRST(ax)= FIRST(a)xBxASrm*rmaa byBbySrm*rm42LR分析器分析器（30）Closure函数构造的算法：函数构造的算法：Function closure(I)Beginrepeatfor 对对I的每个项目的每个项目A.B，a，G中的每个产生式中的每个产生式B 和和FIRST

47、(a)的每个终结符的每个终结符b,如果如果B.，b不在不在I中中 do把把B.，b加到加到I中中until 再没有项目可加到再没有项目可加到I中中return Iend43LR分析器分析器（31）Goto函数的构造：函数的构造：function goto( I , X )begin令令J是项目是项目A X.，a的集合，使得的集合，使得A .X，a 在在I中中return closure(J)end项目的构造：项目的构造：procedure items(G)beginC := closure(S.S，$)repeat for C的每个项目的每个项目I和每个文法符号和每个文法符号X，若若goto(

48、I , X)非空且非空且 不在不在C中中 do把把goto(I , X)加入加入C中中until 再没有项目集可以加入再没有项目集可以加入C中中end44LR分析器分析器（31）规范的规范的LR(1)分析表的构造与分析表的构造与SLR分析表的构造相似分析表的构造相似输入：拓广文法输入：拓广文法G输出：输出：G的的LR(1)分析表函数分析表函数action和和goto方法：方法：(1)构造构造C=I0 , I1 , , In ，即即G的的LR(1)项目集规范族项目集规范族 (2)状态状态i从从Ii构造，它的动作如下确定：构造，它的动作如下确定： (a) 如果如果A.a, b在在Ii中，并且中，并

49、且goto( Ii , a) = Ij，则置则置 action(i , a)为为sj,含义是把含义是把a和状态和状态j移进栈移进栈, a必须为终结符必须为终结符 (b) 如果如果A. , a在在Ii中且中且A不是不是S，则置则置action(i , a)为为rj, j是产生式是产生式A的编号。含义是按产生式的编号。含义是按产生式A归约归约 (c) 如果如果SS. , $在在Ii中，则置中，则置action(i , $)=acc，表示接受表示接受 (3)对所有的非终结符对所有的非终结符A，使用下面的规则构造状态使用下面的规则构造状态i的转移：的转移： 如果如果DFA的转换函数的转换函数goto(

50、 Ii , A) = Ij，则则gotoi , A=j (4)不能由规则不能由规则(2)和和(3)定义的条目置为出错定义的条目置为出错 (5)分析器的初始状态是包含分析器的初始状态是包含S.S , $的项目集对应的状态的项目集对应的状态45LR分析器分析器（32）如果这个分析表中的动作函数没有多重定义的条目，则如果这个分析表中的动作函数没有多重定义的条目，则这个文法是这个文法是LR(1)文法文法在实际中，除非有二义性，几乎所有合理的程序设计语在实际中，除非有二义性，几乎所有合理的程序设计语言的文法都是言的文法都是LR(1)文法文法LR(1)分析过于复杂，产生的项目集合过多，尤其是很分析过于复杂

51、，产生的项目集合过多，尤其是很多项目集合的不同仅仅是因为第二个成分的不同多项目集合的不同仅仅是因为第二个成分的不同例例4：考虑拓广文法：考虑拓广文法S SS CCC cC | d46LR分析器分析器（33）S S . .S S, ,$ $S S. .C CC C, ,$ $C C. .c cC C, , c c/ /d dC C. .d d, ,c c/ /d dI I0 0S S S S. ., ,$ $I I1 1S SC C. .C C, ,$ $C C. .c cC C, ,$ $C C. .d d, ,$ $I I2 2S SC CC C. ., ,$ $I I5 5C Cc c.

52、.C C, ,$ $C C. .c cC C, ,$ $C C. .d d, ,$ $I I6 6C Cc cC C. ., ,$ $I I9 9C Cd d. ., ,$ $I I7 7C Cc c. .C C, ,c c/ /d dC C. .c cC C, ,c c/ /d dC C. .d d, ,c c/ /d dI I3 3C Cc cC C. ., ,c c/ /d dI I8 8C Cd d. ., ,c c/ /d dI I4 4d dd dC CC CC CS Sc cd dc cc cC Cc cd d47LR分析器分析器（34）状状 态态动动 作作c c d d $ $

53、0 0s s3 31 12 23 34 45 56 67 78 89 9s s6 6a ac cc cs s7 7r r1 11 1r r2 2转转 移移S S C C2 29 9s s4 45 58 8s s3 3s s4 4r r3 3r r3 3s s6 6s s7 7r r3 3r r2 2r r2 248LR分析器分析器（35）LALR(1)分析（分析（lookahead-LR分析）分析）引入引入LALR分析：分析：LR(1)项目集合的项目集合的DFA状态过于庞大，且很多状态的状态过于庞大，且很多状态的引入只是因为向前看的符号的不同引入只是因为向前看的符号的不同构造同心的构造同心的L

54、R(1)项目集：它们的第一个成分集合相项目集：它们的第一个成分集合相同同vLR(1)项目的项目的DFA的状态核心是的状态核心是LR(0)项目的项目的DFA的一个状态的一个状态v若具有相同核心的若具有相同核心的LR(1)项目的项目的DFA的两个状态的两个状态s1和和s2，假设假设在符号在符号X上有一个从状态上有一个从状态s1到状态到状态t1的转换，则在的转换，则在X上必然有上必然有一个从状态一个从状态s2到一个状态到一个状态t2的转换，且状态的转换，且状态t1和和t2具有相同的具有相同的核心核心LALR具有和具有和SLR一样个数的状态，但保留了一样个数的状态，但保留了LR分分析的一些特征，能力比

55、析的一些特征，能力比SLR要强要强LALR分析表的构造：分析表的构造：v将具有相同核心的将具有相同核心的LR(1)项目合并，动作和转移函数也做相项目合并，动作和转移函数也做相应的合并应的合并49LR分析器分析器（36）LALR(1)分析表是在分析表是在LR(1)分析表的基础上构造的，分析表的基础上构造的，但可能引入但可能引入LR(1)分析中不存在的冲突分析中不存在的冲突v不会引入移进不会引入移进-归约冲突（因为如果归约冲突（因为如果LALR(1)分析表中存在分析表中存在这类冲突，则在同心项目合并前的这类冲突，则在同心项目合并前的LR(1)分析表中必定存在分析表中必定存在冲突）冲突）v可能引进归

56、约可能引进归约-归约冲突归约冲突LR(1)能发现的错误，能发现的错误，LALR(1)也能发现，只是在报也能发现，只是在报错前可能要多作一些虚假的归约错前可能要多作一些虚假的归约对例对例4的的LR(1)分析，构造分析，构造LALR(1)分析：分析：合并同心项目：合并同心项目：I36：Cc.C , c/d/$ C.cC , c/d/$ C.d , c/d/$ I47：Cd. , c/d/$ I89：CcC. , c/d/$50LR分析器分析器（37）状状 态态动动 作作c c d d $ $0 0s s3 36 61 12 23 36 64 47 75 58 89 9s s3 36 6a ac c

57、c cs s4 47 7r r1 11 1r r2 2转转 移移S S C C2 2s s4 47 75 58 89 9s s3 36 6s s4 47 7r r3 3r r3 3r r3 3r r2 2r r2 2考虑输入串考虑输入串ccd$，对于对于LR(1)分析，把分析，把0 c 3 c 3 d 4入栈，在状态入栈，在状态4发现错误发现错误而对于而对于LALR(1)分析，把分析，把0 c 36 c 36 d 47入栈入栈然后用然后用Cd归约，栈的内容变为归约，栈的内容变为0 c 36 c 36 C 89再用再用CcC归约，栈的内容变为归约，栈的内容变为0 c 36 C 89第二次用第二次

58、用CcC归约，栈的内容变为归约，栈的内容变为0 C 2此时发现错误此时发现错误51二义文法的应用二义文法的应用二义性文法不是二义性文法不是LR文法，但二义性文法在一些情况下的表示更为文法，但二义性文法在一些情况下的表示更为简单简单在在LR分析中消除二义性的规则分析中消除二义性的规则使用优先级和结合规则来解决分析动作的冲突使用优先级和结合规则来解决分析动作的冲突移进优先于归约的规则可以解决最长匹配问题如悬挂移进优先于归约的规则可以解决最长匹配问题如悬挂else的问的问题题特殊情况产生式引起的二义性，可能导致归约特殊情况产生式引起的二义性，可能导致归约-归约冲突，可归约冲突，可以规定此时按特殊情况

59、产生式归约以规定此时按特殊情况产生式归约如文法：如文法：EE sub E sup E | E sub E | E sup E | E | c如果描述如果描述E sub E sup E的文法符号和状态序列已经在分析的文法符号和状态序列已经在分析栈中，当面临栈中，当面临或或$时，选择下面的哪个产生式归约？时，选择下面的哪个产生式归约？EE sub E sup EEE sup E此时可以通过规定哪个产生式优先归约来解决此时可以通过规定哪个产生式优先归约来解决52自底向上分析程序中的错误校正（自底向上分析程序中的错误校正（1）综述：综述：何时发现错误？何时发现错误？当分析表中检测到一个空白项（或错误项

60、），表示发现了错误当分析表中检测到一个空白项（或错误项），表示发现了错误LR分析中访问转移表不会发现错误分析中访问转移表不会发现错误如何更好地发现错误？如何更好地发现错误？尽可能多的空白项可以使得分析程序尽可能早地发现错误，这尽可能多的空白项可以使得分析程序尽可能早地发现错误，这样的错误信息更有意义，且是确定的样的错误信息更有意义，且是确定的但过多的空白项使得分析表过于庞大（考虑但过多的空白项使得分析表过于庞大（考虑LALR和和LR分析分析），如果减少错误项，可能在报错前会有一些不必要的归约动），如果减少错误项，可能在报错前会有一些不必要的归约动作发生，使得报错不准确作发生，使得报错不准确特定