研究生院第四章_1_

1、1第四章第四章 语法分析语法分析分析器的作用分析器的作用上下文无关文法的分析上下文无关文法的分析自上而下的分析自上而下的分析自底向上的分析自底向上的分析LR分析器分析器二义文法的应用二义文法的应用2分析器的作用（分析器的作用（1 1）分析器在编译器的位置分析器在编译器的位置接收词法分析器输出的记号串，检查是否合乎语法接收词法分析器输出的记号串，检查是否合乎语法报告语法错误，并恢复语法错误，从而可以继续分析报告语法错误，并恢复语法错误，从而可以继续分析输出是分析树的某种形式输出是分析树的某种形式分析时其它的任务：将各种记号的信息收入符号表、类型分析时其它的任务：将各种记号的信息收入符号表、类型检

2、查和其它语义检查、中间代码的生成，这些放在检查和其它语义检查、中间代码的生成，这些放在“前端前端的其它部分的其它部分”完成完成3分析器的作用（分析器的作用（2 2）语法错误的处理语法错误的处理从编译器的设计就开始计划出错处理从编译器的设计就开始计划出错处理错误性质错误性质词法错误：如标识符、关键字或算符的拼写错误词法错误：如标识符、关键字或算符的拼写错误语法错误：如算术表达式的括号不配对。语法错误：如算术表达式的括号不配对。v大多数错误的诊断和恢复在语法阶段完成大多数错误的诊断和恢复在语法阶段完成v现代分析方法能以非常有效的方法诊断语法错误现代分析方法能以非常有效的方法诊断语法错误语义错误：如

3、算符作用于不相容的运算对象语义错误：如算符作用于不相容的运算对象逻辑错误：如无穷的递归调用逻辑错误：如无穷的递归调用4分析器的作用（分析器的作用（3 3）语法分析器出错处理的基本目标：语法分析器出错处理的基本目标：清楚而准确地报告错误的出现清楚而准确地报告错误的出现v错误的实际位置可能远远先于其发现的位置，如错误的实际位置可能远远先于其发现的位置，如C C语言中的语言中的“ ”不匹配不匹配迅速地从每个错误中恢复出来，以便诊断后面的迅速地从每个错误中恢复出来，以便诊断后面的错误错误保证正确程序的处理速度保证正确程序的处理速度5分析器的作用（分析器的作用（4 4）PascalPascal程序错误的

4、出现统计程序错误的出现统计60%60%的程序的语法、语义是正确的的程序的语法、语义是正确的40%40%有错误，其中有错误，其中v80%80%的出错语句只含有一个错误的出错语句只含有一个错误v13%13%含两个错误含两个错误v大部分的错误是简单的，大部分的错误是简单的，90%90%的错误是单个记号错的错误是单个记号错PascalPascal程序错误的分类统计程序错误的分类统计60%60%的错误是标点符号错的错误是标点符号错v大多数是分号的不正确使用大多数是分号的不正确使用20%20%是算符或运算对象错误是算符或运算对象错误v如将赋值号如将赋值号:=:=写成写成= =15%15%是关键字错误是关键

5、字错误5%5%是其他类型的错误是其他类型的错误6分析器的作用（分析器的作用（5 5）错误的报告错误的报告位置位置错误的提示信息错误的提示信息错误恢复的问题错误恢复的问题继续报告更多的错误继续报告更多的错误v使编译器恢复到某一状态，继续分析使编译器恢复到某一状态，继续分析伪错误伪错误v抑制过于接近的错误，但作用有限抑制过于接近的错误，但作用有限7分析器的作用（分析器的作用（6 6）错误恢复策略错误恢复策略紧急方式恢复紧急方式恢复v每次抛弃一个输入符号，直至输入符号属于某个每次抛弃一个输入符号，直至输入符号属于某个指定的同步记号集合为止。同步符号一般是定界指定的同步记号集合为止。同步符号一般是定界

6、符，如符，如endendv简单，不会陷入死循环简单，不会陷入死循环短语级恢复：短语级恢复：v对剩余输入进行局部纠正，用可以使分析器继续对剩余输入进行局部纠正，用可以使分析器继续分析的输入串代替剩余输入的前缀分析的输入串代替剩余输入的前缀v典型的是用分号代替逗号、删除多余的分号等典型的是用分号代替逗号、删除多余的分号等v很难应付实际错误出现在诊断点前的情况很难应付实际错误出现在诊断点前的情况v但要仔细选择替换的串，以免引起死循环但要仔细选择替换的串，以免引起死循环8分析器的作用（分析器的作用（7 7）出错产生式出错产生式v根据经常出现的错误，构造产生错误结构的产生根据经常出现的错误，构造产生错误

7、结构的产生式，产生式的被匹配，意味着错误的出现，从而式，产生式的被匹配，意味着错误的出现，从而可以给出适当的错误信息可以给出适当的错误信息全局纠正全局纠正v理想的编译器：处理不正确的输入串时，作尽可理想的编译器：处理不正确的输入串时，作尽可能少的修改能少的修改v算法的开销太大算法的开销太大v提供了评价错误恢复技术的标准提供了评价错误恢复技术的标准9上下文无关文法的分析（上下文无关文法的分析（1 1）上下文无关文法的相关概念上下文无关文法的相关概念推导推导最右（左）推导：最右（左）推导：推导的每一步都是替代最右（左）边非终结符的推导的每一步都是替代最右（左）边非终结符的推导推导对于算术表达式文法

8、：对于算术表达式文法：E E + E | E E E + E | E * * E | ( E ) | -E | id E | ( E ) | -E | id对于串对于串-(-(id + id)id + id)，它是上述文法的句子：它是上述文法的句子：最右推导：最右推导：最左推导：最左推导：最右推导也称为规范推导最右推导也称为规范推导id)(idE)(idE)(EEEid)(idid)(EE)(EEElmlmlmlmrmrmrmrm10上下文无关文法的分析（上下文无关文法的分析（2 2）最右（左）推导的性质：最右（左）推导的性质：如果每步推导可以写成如果每步推导可以写成A=A=，其中其中AA是是

9、应用的产生式，则：应用的产生式，则：v如果上述推导是最右推导，则如果上述推导是最右推导，则是文法的符号串，而是文法的符号串，而只含有终结符号只含有终结符号v如果上述推导是最左推导，则如果上述推导是最左推导，则是文法的符号串，而是文法的符号串，而只含有终结符号只含有终结符号右（左）句型：右（左）句型：如果一个句型是有文法的开始符号通过最右（左）推如果一个句型是有文法的开始符号通过最右（左）推导得到的，则称这个句形是该文法的右（左）句型导得到的，则称这个句形是该文法的右（左）句型由规范推导得到的句型称为规范句型由规范推导得到的句型称为规范句型11上下文无关文法的分析（上下文无关文法的分析（3 3）

10、分析树和推导的关系分析树和推导的关系分析树每个内部节点都是非终结符分析树每个内部节点都是非终结符子节点的标记子节点的标记对于串对于串-(-(id + id)id + id)，它的最右推导构造分析树：它的最右推导构造分析树：12上下文无关文法的分析（上下文无关文法的分析（4 4）分析树不能表示推导的过程分析树不能表示推导的过程每个分析树都有对应的最右推导和最左推导每个分析树都有对应的最右推导和最左推导文法和语言文法和语言如何验证一个语言是某个文法产生的如何验证一个语言是某个文法产生的由文法推导得到的句子都是这个语言的句子由文法推导得到的句子都是这个语言的句子这个语言中所有的句子都可以这个文法推导

11、得到这个语言中所有的句子都可以这个文法推导得到上下文无关文法可以描述程序设计语言的大部分上下文无关文法可以描述程序设计语言的大部分内容，但仍然引入一些新的限制，以保证某些需内容，但仍然引入一些新的限制，以保证某些需求，这些限制可以在分析器的其它部分完成求，这些限制可以在分析器的其它部分完成变量的先声明，后使用变量的先声明，后使用函数调用的参数结合函数调用的参数结合13上下文无关文法的分析（上下文无关文法的分析（5 5）文法的改写文法的改写每个分析方法都只能处理某一类的文法，因此需要对每个分析方法都只能处理某一类的文法，因此需要对给定的文法进行改写，以满足要求给定的文法进行改写，以满足要求二义性

12、文法二义性文法一个文法，如果存在某个句子有不止一棵分析树与之一个文法，如果存在某个句子有不止一棵分析树与之对应，则称这个文法是二义的对应，则称这个文法是二义的表达式文法的句子表达式文法的句子id+idid+id* *idid对应了两个最左推导对应了两个最左推导idddEdddd*iiiiE*EiEiEEE idddEddidE*iiiiE*EE*EEEE 14上下文无关文法的分析（上下文无关文法的分析（6 6）15上下文无关文法的分析（上下文无关文法的分析（7 7）一个二义性的文法是可能将其改写，得到一个等价的一个二义性的文法是可能将其改写，得到一个等价的无二义性的文法的，但这种变换不总是可行

13、的无二义性的文法的，但这种变换不总是可行的v如表达式文法可以改写为：如表达式文法可以改写为： E E + E | TE E + E | T T T T T * * T | F T | F F ( E ) | -E | id F ( E ) | -E | id满足了通常的算符优先次序，但仍然未解决算符的结合满足了通常的算符优先次序，但仍然未解决算符的结合性问题性问题v为了满足左结合的要求，继续改写表达式文法：为了满足左结合的要求，继续改写表达式文法： E E + T | TE E + T | T T T T T * * F | F F | F F ( E ) | -E | id F ( E )

14、| -E | id满足了左结合的要求满足了左结合的要求16上下文无关文法的分析（上下文无关文法的分析（8 8）一个二义性的文法对于某些分析而言，是不能接一个二义性的文法对于某些分析而言，是不能接受的，因为不能唯一确定某个句子对应的分析树受的，因为不能唯一确定某个句子对应的分析树v有时可以通过文法改写，得到无二义性的文法有时可以通过文法改写，得到无二义性的文法v也可以构造允许二义文法的分析器，但要带有消也可以构造允许二义文法的分析器，但要带有消除二义性的规则，从而使分析器为每个句子保留除二义性的规则，从而使分析器为每个句子保留一棵分析树一棵分析树悬空悬空elseelse二义性的处理二义性的处理s

15、tmt if if expr then then stmt | if | if expr then then stmt else else stmt | other | otherotherother表示其它的语句表示其它的语句17上下文无关文法的分析（上下文无关文法的分析（9 9）18上下文无关文法的分析（上下文无关文法的分析（1010）v这个文法是二义性的：这个文法是二义性的：if if E1 then if then if E2 then then S1 else else S219上下文无关文法的分析（上下文无关文法的分析（1111）v这个文法可以如下进行改写这个文法可以如下进行改写：

16、使得每个使得每个elseelse与前面最近与前面最近的还没有配对的的还没有配对的thenthen相配对相配对stmt matched_stmt | | unmatched_stmtmatched_stmt if if expr then then matched_stmt else else matched_stmt | other | otherunmatched_stmt if if expr then then stmt | if | if expr then then matched_stmt else else unmatched_stmt20上下文无关文法的分析（上下文无关文法的分

17、析（1212）将上述改写后，将上述改写后，if if E1 then if then if E2 then then S1 else else S2只对应一种分析树只对应一种分析树21上下文无关文法的分析（上下文无关文法的分析（1313）v上述文法中，一个配对的语句或者是不包含上述文法中，一个配对的语句或者是不包含不配对语句的不配对语句的if-then-elseif-then-else语句，或者是不语句，或者是不包含条件语句的其它语句包含条件语句的其它语句v上述文法虽然消除了二义性，但增加了文法上述文法虽然消除了二义性，但增加了文法的复杂性，而分析方法可以方便地按照遵循的复杂性，而分析方法可以

18、方便地按照遵循最近嵌套规则的方法来配置，从而可以解决最近嵌套规则的方法来配置，从而可以解决上述的二义性上述的二义性v解决悬挂解决悬挂elseelse问题的其它方法：问题的其它方法：必须出现必须出现elseelse部分部分1.1.使用关键字标明一个条件语句的终结（使用关键字标明一个条件语句的终结（bracketing keywordbracketing keyword）22上下文无关文法的分析（上下文无关文法的分析（1414）if_stmt if if expr then then statement_sequence endif endif | if | ifexpr then then st

19、atement_sequence else else statement_sequence endif endif两个例子：两个例子：if x0 thenif x0 then if y=1/x then ok = true if y=1/x then ok = true else z = 1/x else z = 1/x endif endifendifendif和和if x0 thenif x0 then if y=1/x then ok = true if y=1/x then ok = true endif endifelse z = 1/xelse z = 1/xendifendif2

20、3上下文无关文法的分析（上下文无关文法的分析（1515）无关紧要的二义性无关紧要的二义性有些文法虽然存在二义性，但由于相结合的语义不必有些文法虽然存在二义性，但由于相结合的语义不必依赖于使用的是哪种消除二义性的规则，可以将这样依赖于使用的是哪种消除二义性的规则，可以将这样的二义性称为无关紧要的二义性的二义性称为无关紧要的二义性( (inessential inessential ambiguity)ambiguity)如算术加法如算术加法: (: (a+b)+c = a+(b+c)a+b)+c = a+(b+c)24上下文无关文法的分析（上下文无关文法的分析（1616）左递归的消除左递归的消除

21、一个文法是左递归的，如果它有非终结符一个文法是左递归的，如果它有非终结符A A，对某个串对某个串，存在着推导存在着推导自上而下的方法不能处理左递归的文法自上而下的方法不能处理左递归的文法对于左递归的产生式：对于左递归的产生式：AA|AA|，可以用非左递归的可以用非左递归的产生式代替：产生式代替： AAAA A AAA|左递归的分类左递归的分类v直接见诸于产生式的左递归称为直接左递归直接见诸于产生式的左递归称为直接左递归v一般的左递归：如文法一般的左递归：如文法SAa|bSAa|bAAc|Sd|AAc|Sd|AA25上下文无关文法的分析（上下文无关文法的分析（1717）直接左递归的消除直接左递归

22、的消除如果如果A A的所有产生式可以如下表示的所有产生式可以如下表示 AAAA1 1|A|A2 2| |A|Am m|1 1|1 1| |n n其中其中i i都不以都不以A A开始，开始，i i都是非空的，如下变换可以都是非空的，如下变换可以消除直接左递归消除直接左递归 AA1 1A A|2 2A A| | | n nA A A A1 1A A|2 2A A| |m mA A|例：表达式文法的左递归的消除例：表达式文法的左递归的消除EE+T|TEE+T|TETEETETTTT* *F|FF|FE E+TE+TE|F(E)|-E|idF(E)|-E|idTFTTFTT T* *FTFT|F(E)

23、|-E|idF(E)|-E|id26上下文无关文法的分析（上下文无关文法的分析（1818）一般左递归的消除的例子一般左递归的消除的例子SAa|bSAa|bAAc|Sd|AAc|Sd|首先，用首先，用S S的产生式替换的产生式替换ASdASd中的中的S S，得到：得到：SAa|bSAa|bAAc|Aad|bd|AAc|Aad|bd|消除这个文法中的直接左递归，得到消除这个文法中的直接左递归，得到SAa|bSAa|bAbdAAbdA|A|AA AcAcA|adA|adA|27上下文无关文法的分析（上下文无关文法的分析（1919）一般左递归的消除的算法：一般左递归的消除的算法： ( (算法算法3.1

24、)3.1)如果文法不含回路（形如如果文法不含回路（形如 的推导），也不含有以的推导），也不含有以为为右部的产生式，则下面算法可以消除左递归右部的产生式，则下面算法可以消除左递归把文法把文法G G的所有非终结符按任一种顺序排列成的所有非终结符按任一种顺序排列成P P1 1,P,P2 2, ,P,Pn n；按此顺序执行按此顺序执行for i = 1 to n dofor i = 1 to n do for j = 1 to i-1 dofor j = 1 to i-1 do 把形如把形如P Pi iPPj j的规则改写成的规则改写成: : P Pi i 1 1|2 2|k k。 其中其中P Pj

25、j1 1|2 2| |k k是关于是关于P Pj j的所有产生式的所有产生式 endforendfor 消除关于消除关于P Pi i的直接左递归的直接左递归endforendfor化简由化简由2)2)得到的文法：除去从开始符号无法达到的非得到的文法：除去从开始符号无法达到的非终结符的产生式终结符的产生式PP28上下文无关文法的分析（上下文无关文法的分析（2020）-无关的文法：如果它没有无关的文法：如果它没有-产生式，或者只有产生式，或者只有一个一个-产生式：产生式：SS，且开始符号且开始符号S S不出现在任何不出现在任何产生式的右部产生式的右部v若有某个上下文无关文法若有某个上下文无关文法G

26、 G，则存在一个不带则存在一个不带-产生产生式的上下文无关文法式的上下文无关文法G G，使得使得L(G)- = L(GL(G)- = L(G) )。特别地，若特别地，若L(G)L(G)中不含中不含，则有则有L(G) = L(GL(G) = L(G) )29上下文无关文法的分析（上下文无关文法的分析（2121）提取左因子提取左因子当不清楚应该用两个选择的哪一个来替换非终结符当不清楚应该用两个选择的哪一个来替换非终结符A A时时，可以重写，可以重写A A的产生式来推迟决定，直至看见足够多的的产生式来推迟决定，直至看见足够多的输入，能正确决定所需为止输入，能正确决定所需为止用于产生适合预测分析的文法

27、用于产生适合预测分析的文法方法：方法：如果有如果有AA1 1|2 2，这是这是A A的两个产生式，用下面的两个产生式，用下面的产生式替换的产生式替换 AAAA A A1 1 | | 2 2对于如下简写的文法（悬空的对于如下简写的文法（悬空的elseelse），），提取左因子提取左因子SiiEt tS | i | iEt tSe eS | a | aSiiEt tSS|a|aEbbSeeS| |Ebb30自上而下分析自上而下分析基本概念和构造无回溯自上而下分析基本概念和构造无回溯自上而下分析器的方法器的方法LLLL（1 1）文法和分析文法和分析自上而下分析的错误恢复自上而下分析的错误恢复31自上

28、而下分析（自上而下分析（1 1）自上而下分析的一般方法自上而下分析的一般方法对任何输入串，试图用一切可能的方法，从文法开始符号对任何输入串，试图用一切可能的方法，从文法开始符号出发，自上而下、从左到右地为输入串建立分析树，即为出发，自上而下、从左到右地为输入串建立分析树，即为输入串寻找最左推导。这是一个试探的过程输入串寻找最左推导。这是一个试探的过程可以执行一组递归的过程来处理输入，每个过程联系到文可以执行一组递归的过程来处理输入，每个过程联系到文法的一个非终结符，称为递归下降分析法的一个非终结符，称为递归下降分析对于如下文法和输入串对于如下文法和输入串cadcad，自上而下的分析树建立自上而

29、下的分析树建立ScAdScAdA Aab|aab|a32自上而下分析（自上而下分析（2 2）一般的自上而下分析存在的问题：一般的自上而下分析存在的问题：如果文法存在左递归如果文法存在左递归( )( )，则使自上而下的分，则使自上而下的分析过程陷入无限循环析过程陷入无限循环当非终结符用某个选择匹配成功时，这种成功可能是当非终结符用某个选择匹配成功时，这种成功可能是暂时的。由于这种虚假现象的存在，需要回溯技术暂时的。由于这种虚假现象的存在，需要回溯技术由于回溯，需要把已做的一些语义工作推倒重来，费由于回溯，需要把已做的一些语义工作推倒重来，费时费力，所以最好设法消除回溯时费力，所以最好设法消除回溯

30、当最终报告分析不成功时，难以知道输入串出错的确当最终报告分析不成功时，难以知道输入串出错的确切位置切位置带回溯的自上而下分析是一种穷举搜索，代价极高，带回溯的自上而下分析是一种穷举搜索，代价极高，只有理论意义，实践价值不大只有理论意义，实践价值不大AA33自上而下分析（自上而下分析（3 3）确定的递归下降分析举例确定的递归下降分析举例v对于文法对于文法G1SG1S：SpASpA SqBSqB AcAdAcAd AaAa对输入串对输入串pccaddpccadd，自上而下的推导过程是：自上而下的推导过程是：S = pA = pcAd = pccAdd = pccaddS = pA = pcAd =

31、 pccAdd = pccadd对应的分析树：对应的分析树：34自上而下分析（自上而下分析（4 4）文法文法G1G1的特点：的特点：每个产生式的右部都由终结符号开始每个产生式的右部都由终结符号开始如果两个产生式的左部相同，则它们的右部由不同的如果两个产生式的左部相同，则它们的右部由不同的终结符号开始终结符号开始显然，显然，G1G1在推导过程中可以根据当前的输入符号唯一在推导过程中可以根据当前的输入符号唯一地选择哪个产生式继续推导地选择哪个产生式继续推导v对于文法对于文法G2SG2S：SApSAp SBqSBq AaAa AcAAcA BbBb BdBBdB对输入串对输入串ccapccap，自上

32、而下的推导过程是：自上而下的推导过程是：S = Ap = cAp = ccAp = ccapS = Ap = cAp = ccAp = ccap35自上而下分析（自上而下分析（5 5）对应的分析树：对应的分析树：文法文法G2G2的特点：的特点：每个产生式的右部不全是由终结符号开始每个产生式的右部不全是由终结符号开始如果两个产生式的左部相同，则它们的右部由不同的如果两个产生式的左部相同，则它们的右部由不同的终结符号或非终结符号开始终结符号或非终结符号开始文法中没有文法中没有产生式产生式虽然不象虽然不象G1G1那样直观，那样直观，G2G2在推导过程中仍然可以根据在推导过程中仍然可以根据当前的输入符

33、号唯一地选择哪个产生式继续推导当前的输入符号唯一地选择哪个产生式继续推导36自上而下分析（自上而下分析（6 6）v对于文法对于文法G3SG3S：SaASaA SdSd AbASAbAS AA对输入串对输入串abdabd，自上而下的推导过程是：自上而下的推导过程是：S = aA = abAS = abS = abdS = aA = abAS = abS = abd对应的分析树：对应的分析树：37自上而下分析（自上而下分析（7 7）不需要回溯的条件：对文法的任何非终结符，当要去匹不需要回溯的条件：对文法的任何非终结符，当要去匹配输入串时，它能够根据所面临的输入符号准确地指派配输入串时，它能够根据所

34、面临的输入符号准确地指派它的一个选择去执行任务，并且这个选择的工作结果应它的一个选择去执行任务，并且这个选择的工作结果应是确信无疑的是确信无疑的FIRSTFIRST集：令文法集：令文法G G是不含左递归的文法，对是不含左递归的文法，对G G的非终结符的非终结符的候选的候选，定义它的开始符号（终结首符）集合：定义它的开始符号（终结首符）集合：特别地，如果特别地，如果可以推导出空串，则空串也是可以推导出空串，则空串也是FIRST()FIRST()的元素的元素如果非终结符如果非终结符A A的任意两个选择的开始符号集满足的任意两个选择的开始符号集满足FIRST(FIRST(i i)FIRST()FIR

35、ST(j j)=)=，且空串不是关于且空串不是关于A A的所的所有开始符号集的元素，则有开始符号集的元素，则A A可以根据所面临的第一个可以根据所面临的第一个输入符号，准确地指派一个选择去去执行任务，这个输入符号，准确地指派一个选择去去执行任务，这个选择是那个开始符号集含选择是那个开始符号集含a a的的，参考文法参考文法G1G1的例子的例子Vaa., | a)FIRST(T38自上而下分析（自上而下分析（8 8）预测分析器：预测分析器：在不含左递归且每个非终结符所有选择的开始符号集在不含左递归且每个非终结符所有选择的开始符号集都两两不相交的条件下，存在可能构造专门的递归下都两两不相交的条件下，

36、存在可能构造专门的递归下降分析器，称为预测分析器，它仅向前看一个符号便降分析器，称为预测分析器，它仅向前看一个符号便无二义地为非终结符决定所需的处理无二义地为非终结符决定所需的处理处理输入串时的过程调用序列隐含地定义了输入的分处理输入串时的过程调用序列隐含地定义了输入的分析树析树文法：产生文法：产生PascalPascal类型的子集，记号类型的子集，记号dotdotdotdot代表代表.type simple| id| id| array | array simple of of typesimple integer integer | char | char | num dotdot num

37、 | num dotdot num39自上而下分析（自上而下分析（9 9）上述文法的预测分析器的代码（上述文法的预测分析器的代码（PascalPascal的程序）的程序）Procedure match(t : token);Procedure match(t : token);BeginBeginif lookahead = t thenif lookahead = t thenlookahead := nexttokenlookahead := nexttokenelse errorelse errorEndEndProcedure type;Procedure type;BeginBegi

38、nif lookahead if lookahead 属于属于 integer,char, num theninteger,char, num thensimplesimpleelse if lookahead = else if lookahead = then begin then beginmatch(match(); match(id); match(id)endendelse if lookahead = array then beginelse if lookahead = array then beginmatch(array);match(match(array);match(

39、 );simple;match();simple;match( ););match(of);typematch(of);typeendendelse errorelse errorendend40自上而下分析（自上而下分析（1010）Procedure simple;Procedure simple;BeginBeginif lookahead = integer thenif lookahead = integer thenmatch(integer)match(integer)else if lookahead = char thenelse if lookahead = char the

40、nmatch(char)match(char)else if lookahead = num then beginelse if lookahead = num then beginmatch(num); match(dotdot); match(num)match(num); match(dotdot); match(num)endendelse errorelse errorendend41自上而下分析（自上而下分析（1111）非递归的预测分析：非递归的预测分析：显式地维持一个状态栈，而不是隐式地通过递显式地维持一个状态栈，而不是隐式地通过递归调用归调用42自上而下分析（自上而下分析（12

41、12）表驱动的预测分析器包括：表驱动的预测分析器包括：v输入缓冲区：要分析的输入串，以输入缓冲区：要分析的输入串，以$ $作为结束的标记作为结束的标记v栈：存放文法的符号串，栈底符号是栈：存放文法的符号串，栈底符号是$ $，分析开始时，栈，分析开始时，栈中只含有文法的开始符号，它在中只含有文法的开始符号，它在$ $的上面的上面v分析表：是一个两维的数组分析表：是一个两维的数组MAMA，aa，A A是非终结符，是非终结符，a a是是终结符或终结符或$ $v输出流输出流预测分析器的工作过程：预测分析器的工作过程：v根据栈顶当前的符号根据栈顶当前的符号X X和输入符号和输入符号a a决定分析器的动作

42、：决定分析器的动作：如果如果X=a=$X=a=$，分析器宣告分析完全成功而停机分析器宣告分析完全成功而停机如果如果X=a$X=a$，分析器弹出栈顶符号分析器弹出栈顶符号X X，推进输入指针，指推进输入指针，指向下一个符号向下一个符号如果如果X X是终结符但不是是终结符但不是a a，则报告出错，调用错误恢复例程则报告出错，调用错误恢复例程1)1)如果如果X X是非终结符，程序访问分析表是非终结符，程序访问分析表M M，若若MXMX，aa是是X X的产的产生式，则将生式，则将X X弹出栈，将对应的产生式的右部依倒序压入弹出栈，将对应的产生式的右部依倒序压入栈，栈，同时做相应的动作，如作为输出，打印

43、所用的产生式同时做相应的动作，如作为输出，打印所用的产生式，或执行其它代码等，或执行其它代码等；如果；如果MAMA，aa指示出错，分析器调指示出错，分析器调用错误恢复例程用错误恢复例程43自上而下分析（自上而下分析（1313）FOLLOWFOLLOW集：对文法集：对文法G G的任何非终结符的任何非终结符A A，定义它的后继符号集合定义它的后继符号集合：特别地，如果特别地，如果A A可以是某个句型的最右符号，则可以是某个句型的最右符号，则$ $也是也是FOLLOW(A)FOLLOW(A)的元素的元素FOLLOW(A)FOLLOW(A)集合是所有句型中出现在紧接集合是所有句型中出现在紧接A A之后

44、的终结符号之后的终结符号或或$ $所组成的集合所组成的集合预测分析表的构造：算法预测分析表的构造：算法3.23.2输入：文法输入：文法G G输出：预测分析表输出：预测分析表M M方法：方法：1 1）对文法的每个产生式）对文法的每个产生式AA，执行执行2 2）和）和3 3） 2 2）对对FIRST()FIRST()的每个终结符的每个终结符a a，把把AA加入到加入到 MA MA，aa中中 3 3）如果）如果在在FIRST()FIRST()中，对中，对FOLLOW(A)FOLLOW(A)的每个终结符的每个终结符b b ( (包括包括$)$)，把，把AA加入到加入到MAMA，bb中中 4 4）M M

45、的其它没有定义的条目是的其它没有定义的条目是errorerrorTVa.Aa.,*S | aFOLLOW(A)44自上而下分析（自上而下分析（1414）算法算法3.33.3：非递归的的预测分析：非递归的的预测分析输入：输入串输入：输入串和文法和文法G G的分析表的分析表M M方法：初始，分析器的格局是方法：初始，分析器的格局是$ $S S在栈里，在栈里，S S在栈顶；在栈顶；$在输入缓冲区在输入缓冲区，分析程序如下：，分析程序如下：让让ipip指向指向$的第一个符号；的第一个符号；repeatrepeat让让X X等于栈顶符号，并让等于栈顶符号，并让a a是是ipip指向的符号；指向的符号；i

46、f Xif X是终结符或是终结符或$ $，thenthen if X= if X=a a then then把把X X从栈顶弹出，并推进从栈顶弹出，并推进ipip else error()else error()else /else /* * X X是非终结符是非终结符 * */ / if MXif MX，a=XYa=XY1 1Y Y2 2Y Yk k then begin then begin从栈中弹出从栈中弹出X X；把把Y Yk k，Y Yk-1k-1， Y Y1 1压入栈，压入栈，Y Y1 1在栈顶在栈顶; ;输出产生式输出产生式XYXY1 1Y Y2 2Y Yk k end end

47、else error else erroruntil X=$until X=$45自上而下分析（自上而下分析（1515）无二义性表达式文法无二义性表达式文法G4G4：ETEETEE E+TE+TE|TFTTFTT T* *FTFT|F(E)|idF(E)|id则：则：FIRST(E) = FIRST(T) = FIRST(F) = ( FIRST(E) = FIRST(T) = FIRST(F) = ( ，id id FIRST(EFIRST(E) = + , ) = + , FIRST(TFIRST(T) = ) = * * , , FOLLOW(E) = FOLLOW(EFOLLOW(E)

48、 = FOLLOW(E) = ) , $ ) = ) , $ FOLLOW(T) = FOLLOW(TFOLLOW(T) = FOLLOW(T) = + , ) , $ ) = + , ) , $ FOLLOW(F) = + , FOLLOW(F) = + , * * , ) , $ , ) , $ 46自上而下分析（自上而下分析（1616）例：无二义性表达式文法的预测分析例：无二义性表达式文法的预测分析构造的分析表构造的分析表M M如果输入串是如果输入串是id+idid+id* *idid，分析过程中各部分的变化如下图分析过程中各部分的变化如下图所示，输入指针指在输入串最左边的符号上，分析器

49、跟踪所示，输入指针指在输入串最左边的符号上，分析器跟踪的是输入的最左推导，已扫描过的符号加上栈中的文法符的是输入的最左推导，已扫描过的符号加上栈中的文法符号（从顶到底），构成最左推导的句型号（从顶到底），构成最左推导的句型47自上而下分析（自上而下分析（1717）栈栈输输 入入 输输 出出$ $E Eid+idid+id* *id$id$ $E ET Tid+idid+id* *id$id$ ETE ETE$ $E ET TF Fid+idid+id* *id$id$ TFT TFT$ $E ET Tididid+idid+id* *id$id$ Fid Fid$ $E ET T +id +i

50、d* *id$id$ $E E +id +id* *id$id$ T T$ $E ET+T+ +id +id* *id$id$ E E+TE+TE$ $E ET T id id* *id$id$ $E ET TF F id id* *id$id$ TFT TFT$ $E ET Tidid id id* *id$id$ Fid Fid$ $E ET T * *id$id$ $E ET TF F* * * *id$id$ T T* *FTFT$ $E ET TF F id$ id$ $E ET Tidid id$ id$ Fid Fid$ $E ET T $ $ $E E $ $ T T$ $ $

51、 $ E E48自上而下分析（自上而下分析（1818）LL(1)LL(1)文法文法利用算法利用算法3.23.2，可以为任何文法，可以为任何文法G G以构造它的分析表以构造它的分析表M M，但对但对于某些文法，于某些文法，M M可能有某些条目对应了多个产生式，或说某可能有某些条目对应了多个产生式，或说某些些MAMA，aa可能是多重定义的可能是多重定义的如果如果G G是左递归或二义的，则是左递归或二义的，则M M至少有一个多重定义的条目至少有一个多重定义的条目对于如下文法，对应的分析表对于如下文法，对应的分析表M M如下：如下：SiiEt tSS|a|aSeeS|Ebb49自上而下分析（自上而下分

52、析（1919）一个文法，如果它的预测分析表不含有多重定义的条目，则称一个文法，如果它的预测分析表不含有多重定义的条目，则称为为LL(1)LL(1)文法，第一个文法，第一个L L表示从左向右扫描输入，第二个表示从左向右扫描输入，第二个L L表示表示产生最左推导产生最左推导LL(1)LL(1)文法的性质文法的性质不是二义的不是二义的不含左递归不含左递归不回溯不回溯一个文法一个文法G G如果是如果是LL(1)LL(1)的，当且仅当的，当且仅当G G的任何两个产生式的任何两个产生式A|A|满足下面的条件：满足下面的条件：vFIRST()FIRST()FIRST()FIRST()是空集是空集v若若可以推

53、导得到空串，则可以推导得到空串，则FIRST()FOLLOW(A)FIRST()FOLLOW(A)是空集是空集将非将非LL(1)LL(1)文法变换为文法变换为LL(1)LL(1)文法的方法文法的方法提取左因子提取左因子消除左递归消除左递归不是所有的文法都可以变换为不是所有的文法都可以变换为LL(1)LL(1)文法的文法的50自上而下分析（自上而下分析（2020）预测分析的错误恢复预测分析的错误恢复非递归预测分析器的栈使得分析器希望和剩余输入非递归预测分析器的栈使得分析器希望和剩余输入匹配的终结符变得明显匹配的终结符变得明显当栈顶的终结符和下一个输入符号不匹配，或者栈当栈顶的终结符和下一个输入符

54、号不匹配，或者栈顶是非终结符顶是非终结符A A，输入符号是输入符号是a a，而而MAMA，aa是空白是空白时，预测分析器即发现一个错误时，预测分析器即发现一个错误紧急方式的错误恢复策略：跳过一些输入符号，直紧急方式的错误恢复策略：跳过一些输入符号，直到期望的同步记号中的一个出现为止到期望的同步记号中的一个出现为止效果依赖于同步记号集合的选择效果依赖于同步记号集合的选择51自上而下分析（自上而下分析（2121）同步记号的选择同步记号的选择开始，将开始，将FOLLOW(A)FOLLOW(A)的所有符号放入非终结符的所有符号放入非终结符A A的同的同步记号集合，如果跳过一些记号，直到看到步记号集合，

55、如果跳过一些记号，直到看到FOLLOW(A)FOLLOW(A)中的元素时，再把中的元素时，再把A A弹出栈，分析一般可弹出栈，分析一般可以继续下去以继续下去把高层结构的开始符号加到低层结构的同步集合中把高层结构的开始符号加到低层结构的同步集合中，例如将语句开始的关键字加入产生表达式非终结，例如将语句开始的关键字加入产生表达式非终结符的同步集合中符的同步集合中例如例如C C语言中的分号，用于终止一个语句，则语句开语言中的分号，用于终止一个语句，则语句开始的关键字很可能不出现在产生表达式的非终结符的始的关键字很可能不出现在产生表达式的非终结符的FOLLOWFOLLOW集合中，赋值语句后分号的遗漏会

56、引起下一个集合中，赋值语句后分号的遗漏会引起下一个语句的开始关键字被跳过语句的开始关键字被跳过把把FIRST(A)FIRST(A)的符号加入的符号加入A A的同步集合的同步集合1)1)如果如果FIRST(A)FIRST(A)的符号出现在输入中，则恢复关于的符号出现在输入中，则恢复关于A A的的分析是可能的分析是可能的52自上而下分析（自上而下分析（2222）如果非终结符可以产生空串，若出错时栈顶是这样如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，则可以使用产生空串的产生式的非终结符，则可以使用产生空串的产生式v这样会延迟错误的发现，但不会遗漏这样会延迟错误的发现，但不会遗漏v好处是可

57、以减少恢复要考虑的非终结符好处是可以减少恢复要考虑的非终结符如果终结符在栈顶而不能匹配，简单的方法是弹出如果终结符在栈顶而不能匹配，简单的方法是弹出此终结符此终结符v给出提示信息，说明插入了此符号，然后继续分析给出提示信息，说明插入了此符号，然后继续分析v等于把所有其它的记号作为此记号的同步集合等于把所有其它的记号作为此记号的同步集合53自上而下分析（自上而下分析（2323）例：对于无二义性例：对于无二义性G4G4，使用使用FOLLOWFOLLOW和和FIRSTFIRST符号作为同步记号，符号作为同步记号，用用synchsynch来指示从非终结符的来指示从非终结符的FOLLOWFOLLOW集合得到的同步记号集合得到的同步记号加有同步记号的分析