《最新【考研计算机专业课】天津大学 编译原理PPT课件 Part4语法分析(共42张PPT课件).pptx》由会员分享，可在线阅读，更多相关《最新【考研计算机专业课】天津大学 编译原理PPT课件 Part4语法分析(共42张PPT课件).pptx（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Part4Part4语法分析语法分析第一页，共四十二页。语法分析器的作用语法分析器的作用(zuyng)(zuyng)第二页，共四十二页。以语法分析器为核心以语法分析器为核心(hxn)(hxn)的编译器模型的编译器模型语法分语法分析器析器词法分词法分析器析器中间代码中间代码生成器生成器语义分析器语义分析器一部分中一部分中间代码间代码输入字输入字符串符串程序入口程序入口初始化工作初始化工作第三页，共四十二页。语法分析器的作用语法分析器的作用(zuyng)(zuyng)接收词法分析器提供的记号串接收词法分析器提供的记号串检查记号串是否检查记号串是否(sh fu)能由源程序语言的文法产生能由源程序语言
2、的文法产生用易于理解的方式提示语法错误信息，并能从常见的用易于理解的方式提示语法错误信息，并能从常见的错误中恢复过来错误中恢复过来语法分语法分析器析器词法词法分析器分析器符号表符号表前端的其前端的其余部分余部分源程序源程序记号记号取下一取下一个记号个记号语法树语法树中间表示中间表示第四页，共四十二页。语法分析器工作语法分析器工作(gngzu)(gngzu)原理原理语言的结构是用上下文无关文法描述的，因此，语法分析器的工语言的结构是用上下文无关文法描述的，因此，语法分析器的工作本质上就是按照文法的产生式，识别输入符号串是否为一个句作本质上就是按照文法的产生式，识别输入符号串是否为一个句子。子。语
3、法分析器是从左向右的扫描输入字符串，每次读入一个符号，语法分析器是从左向右的扫描输入字符串，每次读入一个符号，并判断，看是否能从文法的开始符号出发并判断，看是否能从文法的开始符号出发(chf)推导出这个输入串。推导出这个输入串。或者，从概念上讲，就是要建立一棵与输入串匹配的语法分析树。或者，从概念上讲，就是要建立一棵与输入串匹配的语法分析树。语法分析器分类语法分析器分类 通用的语法分析方法，用来分析任何文法，生成编译器时效率太低通用的语法分析方法，用来分析任何文法，生成编译器时效率太低编译器使用的语法分析方法编译器使用的语法分析方法处理文法的一些子类处理文法的一些子类自顶向下（建立分析树）自顶
4、向下（建立分析树）LL文法，其分析器常用手工实现文法，其分析器常用手工实现自底向上（建立分析树）自底向上（建立分析树）LR文法，其分析器常利用自动生成工具构造文法，其分析器常利用自动生成工具构造第五页，共四十二页。自顶向下分析面临自顶向下分析面临(minlng)(minlng)的困的困难难第六页，共四十二页。自顶向下分析自顶向下分析(fnx)(fnx)面临的困难面临的困难 自顶向下分析的主旨是，对任何输入自顶向下分析的主旨是，对任何输入(shr)串，试图用串，试图用一切可能的办法，从文法的开始符号（根结）出发，一切可能的办法，从文法的开始符号（根结）出发，自顶向下的为输入自顶向下的为输入(sh
5、r)串建立一棵语法树。串建立一棵语法树。或者说，为输入串寻找一个最左推导。或者说，为输入串寻找一个最左推导。这种分析过程本质上是一种试探过程，是反复使用不这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。同产生式谋求匹配输入串的过程。 自顶向下分析的一般方法是带自顶向下分析的一般方法是带“回溯回溯”的。的。第七页，共四十二页。自顶向下分析自顶向下分析(fnx)(fnx)的简单例子的简单例子假定文法假定文法(wnf)GS，以及输入串，以及输入串x*y（记为（记为）。）。SxAyA*|*初始化：初始化：第一步扩展第一步扩展Sx*yIPSx*yIPyAx第八页，共四十二页。
6、自顶向下分析的简单自顶向下分析的简单(jindn)(jindn)例子例子假定假定(jidng)文法文法GS，以及输入串，以及输入串x*y（记为（记为）。）。SxAyA*|*第二步扩展：第二步扩展：回溯回溯x*yIPSx*yIPyAx*SyAx*第九页，共四十二页。自顶向下分析面临自顶向下分析面临(minlng)(minlng)的困难的困难 文法的左递归性问题。含有左递归的文法将使上述的自顶向下的文法的左递归性问题。含有左递归的文法将使上述的自顶向下的分析过程陷入无限循环。因此，我们要使用自顶向下分析法必须分析过程陷入无限循环。因此，我们要使用自顶向下分析法必须要消除文法的左递归。要消除文法的左
7、递归。由于回溯，就碰到一大堆的麻烦事情。如果我们走了一大段错路，最后由于回溯，就碰到一大堆的麻烦事情。如果我们走了一大段错路，最后必须回头，那么，就应把已经作的一大堆语义工作（指中间代码生成工必须回头，那么，就应把已经作的一大堆语义工作（指中间代码生成工作和各种表格的簿记工作）推倒重来。这些事情既麻烦又费时间，所以，作和各种表格的簿记工作）推倒重来。这些事情既麻烦又费时间，所以，最好设法最好设法(shf)消除回溯。消除回溯。在上述的自顶向下分析过程中，当一个非终结符用某一候选在上述的自顶向下分析过程中，当一个非终结符用某一候选 匹配成功时，匹配成功时，这种成功可能是暂时的。这种成功可能是暂时的
8、。当最终报告分析不成功时，难于知道输入串出错的确切位置。当最终报告分析不成功时，难于知道输入串出错的确切位置。由于带回溯的自顶向下分析方法实际上采用了一种穷尽一切可能由于带回溯的自顶向下分析方法实际上采用了一种穷尽一切可能的试探法，因此效率很低。的试探法，因此效率很低。第十页，共四十二页。LL(1)LL(1)分析法分析法第十一页，共四十二页。消除消除(xioch)(xioch)左递归左递归直接直接(zhji)左递归的消除左递归的消除PP | PPPP | EE+T | TTT*F | FF(E) | iETEE+TE | TFTT*FT | F(E) | i第十二页，共四十二页。消除消除(xi
9、och)(xioch)左递归的算法左递归的算法如果一个文法不含回路（形如如果一个文法不含回路（形如P=+P的推导），也不含以的推导），也不含以为右部的为右部的产生式，那么执行下述算法将保证消除左递归（但改写后的文法可产生式，那么执行下述算法将保证消除左递归（但改写后的文法可能含有能含有为右部的产生式）。为右部的产生式）。 把文法把文法G的所有非终结符按任一种顺序排列成的所有非终结符按任一种顺序排列成P1,P2,Pn；按此顺；按此顺序执行：序执行：FOR i := 1 TO n DOBEGINFOR j:= 1 TO i-1 DO把所有形如把所有形如PiPj的规则改写为：的规则改写为：Pi1 |
10、 2| | k。其中其中Pj1 | 2 | | k是关于是关于Pj的所有规则；的所有规则；消除关于消除关于Pi的直接的直接(zhji)左递归左递归END化简由第化简由第2步得到的文法。即去除那些从开始符号出发永远无法到达的步得到的文法。即去除那些从开始符号出发永远无法到达的非终结符的产生式规则。非终结符的产生式规则。第十三页，共四十二页。消除消除(xioch)(xioch)左递归的例子左递归的例子SQc | cQRb | bRSa |aRSa |aQSab | ab | bSSabc | abc | bc | cSabcS | bcS | cSSabcS | RSa |aQSab | ab |
11、 bSabcS | bcS | cSSabcS | SQc | cQRb | bRbcaR |caR | aRRbcaR | 第十四页，共四十二页。消除消除(xioch)(xioch)回溯、提取左因子回溯、提取左因子 为了消除回溯就必须保证：为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务临的输入符号准确地指派它的一个候选去执行任务(rn wu)，并且此，并且此候选的工作结果应该是确信无疑的。候选的工作结果应该是确信无疑的。也就是说，若此候选获得成功匹配，那么
12、这种匹配决不会是虚假的；若此也就是说，若此候选获得成功匹配，那么这种匹配决不会是虚假的；若此候选无法完成匹配任务，则任何其他候选也肯定无法完成。候选无法完成匹配任务，则任何其他候选也肯定无法完成。 假定现在轮到非终结符假定现在轮到非终结符A区执行匹配（或称识别）任务，区执行匹配（或称识别）任务，A共有共有n个候选个候选1, 2, , n，即，即A1 | 2 | | n。A所面临的第一个输入符号为所面临的第一个输入符号为a，如果，如果A能够根据不同的输入符号指派能够根据不同的输入符号指派相应的候选相应的候选i作为全权代表去执行任务，那就肯定无需回溯。作为全权代表去执行任务，那就肯定无需回溯。在这
13、里已不再是让某个候选去试探性的执行任务，而是根据所面临的输入符号在这里已不再是让某个候选去试探性的执行任务，而是根据所面临的输入符号准并的指派唯一的一个候选。准并的指派唯一的一个候选。第十五页，共四十二页。消除回溯、提取消除回溯、提取(tq)(tq)左因子左因子令是一个不含左递归的文法，对令是一个不含左递归的文法，对G的所有非终结符的每个候选的所有非终结符的每个候选定义定义它的终结首符集它的终结首符集FIRST()为：为：FIRST()=a | =*a, aVT 若若=*，则规定，则规定(gudng)FIRST()FIRST()是是的所有可能推导的开头终结符或可能的的所有可能推导的开头终结符或
14、可能的 如果非终结符的所有候选首符集两两不相交，即的任何两个如果非终结符的所有候选首符集两两不相交，即的任何两个不同候选不同候选i和和FIRST(i) FIRST(j)=那么当要求匹配输入串时，就能根据它所面临的第一个输入那么当要求匹配输入串时，就能根据它所面临的第一个输入符号，准确的指派某一个候选前去执行任务。这个候选就是那符号，准确的指派某一个候选前去执行任务。这个候选就是那个终结首符集含的个终结首符集含的。 第十六页，共四十二页。消除回溯、提取消除回溯、提取(tq)(tq)左因子左因子提取左因子的方法提取左因子的方法假定的规则是：假定的规则是：1 |2 | |n |1 |2 | |m（其
15、中，每个（其中，每个不以不以开头）开头）那么这些规则可以那么这些规则可以(ky)改写为：改写为：AA |1 |2 | |mA1 |2 | |n经过反复提取左因子，就能够把每个非终结符（包括新引进者）经过反复提取左因子，就能够把每个非终结符（包括新引进者）的所有候选首符集便成为两两不相交。我们为此要付出的代价是的所有候选首符集便成为两两不相交。我们为此要付出的代价是大量引进新的非终结符和大量引进新的非终结符和产生式。产生式。 第十七页，共四十二页。LL(1)LL(1)分析分析(fnx)(fnx)条件条件ETEE+TE | TFTT*FT | F(E) | i对输入对输入(shr)串串i+i进行自
16、顶向下进行自顶向下分析分析Ei + iIPTEiFIRST(TE)Ei + iIPTEiFIRST(FT)FTEi + iIPTEiFIRST(i)FTi第十八页，共四十二页。LL(1)LL(1)分析分析(fnx)(fnx)条件条件ETEE+TE | TFTT*FT | F(E) | i对输入串对输入串i+i进行进行(jnxng)自顶向下自顶向下分析分析Ei + iIPTE+不属于不属于(shy)T的任一候选式的的任一候选式的首符集首符集FTiETEFTi+TEFTi第十九页，共四十二页。LL(1)LL(1)分析分析(fnx)(fnx)条件条件只有当只有当a是允许在文法的某个句型中跟在是允许在
17、文法的某个句型中跟在A后面的终结符时，才可能允后面的终结符时，才可能允许许A自动匹配成功，否则，自动匹配成功，否则，a在这里的出现就是一种语法错误。在这里的出现就是一种语法错误。假定假定S是文法是文法G的开始符号，对于的开始符号，对于G的任何非终结符的任何非终结符A，我们定义，我们定义(dngy)FOLLOW(A)=a | S=*Aa，aVT特别是，若特别是，若S=*A，则规定，则规定#FOLLOW(A)。换句话说，。换句话说，FOLLOW(A)是所有句型中出现在紧接是所有句型中出现在紧接A之后的终结符或之后的终结符或“#”。 当非终结符当非终结符A面临输入符号面临输入符号a，且，且a不属于不
18、属于A的任意候选首符集但的任意候选首符集但A的某个候选首符集包含的某个候选首符集包含时，只有当时，只有当aFOLLOW(A)时，才可时，才可能允许能允许A自动匹配。自动匹配。 第二十页，共四十二页。LL(1)LL(1)分析分析(fnx)(fnx)条件条件通过上面的讨论，我们可以找出满足构造不带回溯的自顶向下通过上面的讨论，我们可以找出满足构造不带回溯的自顶向下分析的文法条件。分析的文法条件。 文法不含左递归文法不含左递归对于文法中每一个非终结符对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。的各个产生式的候选首符集两两不相交。即，若即，若A1 |2 | |n，则，则FIRST(i
19、)FIRST(j)=(ij)对文法中的每个非终结符对文法中的每个非终结符A，若它存在某个候选首符集包含，若它存在某个候选首符集包含，则，则，FIRST(A)FOLLOW(A)=如果一个文法如果一个文法G满足以上条件，则称该文法满足以上条件，则称该文法G为为LL(1)文法。文法。这里这里LL(1)中的第一个中的第一个L表示表示(biosh)从左到右扫描输入串，第二个从左到右扫描输入串，第二个L表示表示(biosh)最左推导，最左推导，1表示表示(biosh)分析时每一步只需向前查看一个符号。分析时每一步只需向前查看一个符号。 第二十一页，共四十二页。LL(1)LL(1)分析分析(fnx)(fnx
20、)条件条件对于一个对于一个LL(1)文法，可以对其输入串进行有效的无文法，可以对其输入串进行有效的无回溯的自顶向下分析。回溯的自顶向下分析。假设要用非终结符假设要用非终结符A进行匹配，面临的输入符号为进行匹配，面临的输入符号为a，A的所有产生式为的所有产生式为A1 |2 | |n若若aFIRST(i)，则指派，则指派i去执行匹配任务。去执行匹配任务。若若a不属于任何一个候选首字符集，则：不属于任何一个候选首字符集，则：若若属于某个属于某个FIRST(i)，且，且aFOLLOW(A)，则让，则让A与与自动匹配；自动匹配；否则，否则，a的出现是一种语法错误。的出现是一种语法错误。根据根据(gnj)
21、LL(1)文法的条件，每一步这样的工作都是文法的条件，每一步这样的工作都是确信无疑的确信无疑的 第二十二页，共四十二页。递归下降递归下降(xijing)(xijing)分析程序构造分析程序构造第二十三页，共四十二页。扩充扩充(kuchng)(kuchng)的巴科斯范式的巴科斯范式前面的巴科斯范式只用到了两个元符号前面的巴科斯范式只用到了两个元符号“”和和“|” 扩充扩充(kuchng)几个元语言符号：几个元语言符号：用花括号用花括号表示闭包运算表示闭包运算*。用用n0表示表示可任意重复可任意重复0次至次至n次。次。00=0=.用方括号用方括号表示表示10，即表示，即表示的出现可有可无（等价于的
22、出现可有可无（等价于 |）。）。 例如，通常的例如，通常的“实数实数”可定义为：可定义为：decimalsigninteger.digitexponentexponentEsignintegerintegerdigitdigitsign+ | -第二十四页，共四十二页。递归下降递归下降(xijing)(xijing)分析程序的构造分析程序的构造当文法满足当文法满足LL(1)条件时，我们就可以为它构造一个条件时，我们就可以为它构造一个不带回溯的自顶向下分析程序，这个分析程序是由一不带回溯的自顶向下分析程序，这个分析程序是由一组递归过程组递归过程(guchng)组成的。每个过程组成的。每个过程(g
23、uchng)对应文法的对应文法的一个非终结符。这样的一个分析程序称为递归下降分一个非终结符。这样的一个分析程序称为递归下降分析器。析器。 EE+T | TTT*F | FF(E) | iET+TTF*FF(E) | i第二十五页，共四十二页。递归下降递归下降(xijing)(xijing)分析程序构造分析程序构造ET+TTF*FF(E) | iPROCEDURE E;BEGINT;WHILE SYM = + DOBEGIN ADVANCE; T ENDENDPROCEDURE T;BEGINF;WHILE SYM = * DOBEGIN ADVANCE; F ENDEND第二十六页，共四十二页
24、。预测预测(yc)(yc)分析程序分析程序第二十七页，共四十二页。预测分析程序工作预测分析程序工作(gngzu)(gngzu)过程过程实现实现LL(1)分析分析(fnx)的另一种有效方法是使用一张分析的另一种有效方法是使用一张分析(fnx)表表和一个栈进行联合控制。下面要介绍的预测分析和一个栈进行联合控制。下面要介绍的预测分析(fnx)程序就程序就是属于这种类型的是属于这种类型的LL(1)分析分析(fnx)器。器。 第二十八页，共四十二页。预测预测(yc)(yc)分析表分析表预测分析表示一个预测分析表示一个MA,a形式的矩阵形式的矩阵(j zhn)。其中。其中A为非终结符，为非终结符，a是终结
25、符或是终结符或# 。矩阵元素矩阵元素MA,a中存放着一条关于中存放着一条关于A的产生式，指出当的产生式，指出当A面临输面临输入符号入符号a时所应采用的候选。时所应采用的候选。MA,a中也可能存放一个中也可能存放一个“出错标志出错标志”，指出，指出A根本不该面临根本不该面临输入符号输入符号a。 i+*()#EETEETEEE+TEEETTFTTFTTTT*FTTTFFiF(E)第二十九页，共四十二页。预测分析预测分析(fnx)(fnx)过程概述过程概述预测分析程序的总控程序在任何时候都是按预测分析程序的总控程序在任何时候都是按STACK栈顶符号栈顶符号X和当前和当前(dngqin)的输入符号的输
26、入符号a行事的。如下图所示，对于任何行事的。如下图所示，对于任何(X,a)，总控程序，总控程序每次都执行下述三种可能的动作之一：每次都执行下述三种可能的动作之一：若若X = a = #，则宣布分析成功，停止分析过程。，则宣布分析成功，停止分析过程。若若X = a #，则把，则把X从从STACK栈顶弹出，让栈顶弹出，让a指向下一个输入符号。指向下一个输入符号。若若X是一个非终结符，则查看分析表是一个非终结符，则查看分析表M。若若MX,a中存放着关于中存放着关于X的一个产生式，那么，先把的一个产生式，那么，先把X弹出弹出STACK栈顶，栈顶，然后把产生式的右部符号串按反序一一推进然后把产生式的右部
27、符号串按反序一一推进STACK栈（若右部符号为栈（若右部符号为，则意味着不推什么东西进栈）。则意味着不推什么东西进栈）。在把产生式的右部符号退进栈的同时应该做这个产生式对应的语义动在把产生式的右部符号退进栈的同时应该做这个产生式对应的语义动作（目前暂且不管）。作（目前暂且不管）。若若MX,a中存放着中存放着“出错标志出错标志”，则调用出错诊断程序，则调用出错诊断程序ERROR。 第三十页，共四十二页。预测预测(yc)(yc)分分析过程举析过程举例例i+*()#EETEETEEE+TEEETTFTTFTTTT*FTTTFFiF(E)i1*i2+i3步骤步骤(bzhu)符号符号(fho)栈栈输入串
28、输入串所用产生式所用产生式0#Ei*i+i#1#ETi*i+i#ETE2#ETFi*i+i#TFTTFT3#ETii*i+i#Fi4#ET *i+i#5#ETF* *i+i#T*FT6#ETF i+i#7#ETi i+i#Fi8#ET +i#9#E +i#T10#ET+ +i#E+TE11#ET i#12#ETF i#TFT13#ETi i#Fi14#ET #15#E #T16# #E第三十一页，共四十二页。预测预测(yc)(yc)分析表的构造分析表的构造FIRST集合的构造集合的构造若若XVT，则，则FIRST(X)=X；若若XVN，且有产生式，且有产生式Xa，则把，则把a加入到加入到FIR
29、ST(X)中；若中；若X也是一也是一条产生式，则把条产生式，则把也加到也加到FIRST(X)中。中。若若XY是一个产生式且是一个产生式且YVN，则把，则把FIRST(Y)中的所有中的所有(suyu)非非元素元素都加到都加到FIRST(X)中；若中；若XY1Y2Yk是产生式，是产生式，Y1,Yi-1都是非终结都是非终结符，而且对于任何的符，而且对于任何的j，1ji-1，FIRST(Yj)都含有都含有，则把，则把FIRST(Yi)中的所有非中的所有非元素都放到元素都放到FIRST(X)中；特别的是，若所中；特别的是，若所有的有的FIRST(Yj)均含有均含有，j=1,2,k，则把，则把加到加到FI
30、RST(X)中中 第三十二页，共四十二页。FIRSTFIRST集合构造集合构造(guzo)(guzo)的例子的例子FIRST(E)=+,FIRST(T)=*,FIRST(F)=( , iFIRST(T)=( , iFIRST(E)=( , iETEE+TE | TFTT*FT | F(E) | i第三十三页，共四十二页。预测分析预测分析(fnx)(fnx)表的构造表的构造FOLLOW集合的构造集合的构造对于文法对于文法(wnf)的开始符号的开始符号S，置，置#于于FOLLOW(S)中。中。若若AB是一个产生式，则把是一个产生式，则把FIRST() 加至到加至到FOLLOW(B)中。中。若若AB
31、是一个产生式，或是一个产生式，或AB是一个产生式而是一个产生式而=（即（即FIRST()），则把），则把FOLLOW(A)加至加至FOLLOW(B)中。中。 构造分析表构造分析表M的算法是：的算法是：对文法对文法G的每个产生式的每个产生式A执行第执行第2步和第步和第3步；步；对每个终结符对每个终结符aFIRST()，把，把A加至加至MA,a中；中；若若FIRST()，则对任何，则对任何bFOLLOW(A)把把A加至加至MA,a中。中。把所有无定义的把所有无定义的MA,a标上标上“出错标志出错标志”。 第三十四页，共四十二页。FOLLOWFOLLOW集合集合(jh)(jh)构造的例子构造的例子F
32、OLLOW(E)=),#FOLLOW(E)=),#FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=*,+,),#ETEE+TE | TFTT*FT | F(E) | iFIRST(E)=+,FIRST(T)=*,FIRST(F)=( , iFIRST(T)=( , iFIRST(E)=( , ii+*()#EETEETEEE+TEEETTFTTFTTTT*FTTTFFiF(E)第三十五页，共四十二页。LL(1)LL(1)分析分析(fnx)(fnx)中的错误处理中的错误处理 第三十六页，共四十二页。错误的出现错误的出现(chxin)(chxin)及基本做法及基本做
33、法栈顶的终结符与当前的输入符号不匹配。栈顶的终结符与当前的输入符号不匹配。非终结符非终结符A处于处于(chy)栈顶，面临的输入符号为栈顶，面临的输入符号为a，但，但分析表分析表M中中MA,a为空。为空。 基本的做法就是跳过输入串中的一些符号直至遇到基本的做法就是跳过输入串中的一些符号直至遇到“同步符号同步符号”为止。这种做法的效果有赖于同步符为止。这种做法的效果有赖于同步符号集的选择。号集的选择。 第三十七页，共四十二页。同步同步(tngb)(tngb)符号集的选择符号集的选择 把把FOLLOW(A)中的所有符号放入非终结符中的所有符号放入非终结符A的同步符号集。的同步符号集。如果我们跳读一些
34、输入符号直至出现如果我们跳读一些输入符号直至出现FOLLOW(A)中的同步符中的同步符号，把号，把A从栈中弹从栈中弹(zhn dn)出来，这样就可能使分析继续下去。出来，这样就可能使分析继续下去。对于非终结符对于非终结符A来说，只用来说，只用FOLLOW(A)作为它的同步符号集是不作为它的同步符号集是不够的。例如，如果分号作为语句的终结符，那么作为语句开头的够的。例如，如果分号作为语句的终结符，那么作为语句开头的关键字就可能不在产生表达式的非终结符的关键字就可能不在产生表达式的非终结符的FOLLOW集合中。这集合中。这样，在一个赋值语句后少一个分号就可能导致作为下一个语句开样，在一个赋值语句后
35、少一个分号就可能导致作为下一个语句开头的关键字被跳过头的关键字被跳过如果把如果把FIRST(A)中的符号加入非终结符中的符号加入非终结符A的同步符号集，那么当的同步符号集，那么当FIRST(A)中的一个符号在输入中出现时，可以根据中的一个符号在输入中出现时，可以根据A恢复语法分恢复语法分析析第三十八页，共四十二页。同步符号同步符号(fho)(fho)集的选择集的选择 如果一个非终结符产生空串，那么推导如果一个非终结符产生空串，那么推导的产生式可以作为缺省的情况，的产生式可以作为缺省的情况，这样做可以推迟某些错误检查，但不能导致放弃一个错误。这种方法减这样做可以推迟某些错误检查，但不能导致放弃一
36、个错误。这种方法减少在错误恢复期间必须考虑的非终结符数。少在错误恢复期间必须考虑的非终结符数。如果不能匹配栈顶的终结符号，一种简单的想法是弹出栈顶的这如果不能匹配栈顶的终结符号，一种简单的想法是弹出栈顶的这个终结符号，并发出一条信息，说明已经插入这个终结符，继续个终结符号，并发出一条信息，说明已经插入这个终结符，继续进行进行(jnxng)语法分析。结果，这种方法使一个单词符号的同步符号语法分析。结果，这种方法使一个单词符号的同步符号集包含所有其他单词符号。集包含所有其他单词符号。 对于改后的分析表，如果遇到对于改后的分析表，如果遇到MA,a是空，在跳过输入符号是空，在跳过输入符号a，若该，若该
37、项为项为“同步同步”，则弹出栈顶的非终结符；如果是初始状态，则需要，则弹出栈顶的非终结符；如果是初始状态，则需要继续读入下一个输入符号，直至该项不为空或继续读入下一个输入符号，直至该项不为空或“同步同步”；若栈顶的；若栈顶的终结符号不匹配输入符号，则弹出栈顶的终结符。终结符号不匹配输入符号，则弹出栈顶的终结符。 第三十九页，共四十二页。错误处理错误处理例子例子(l zi)(l zi)i+*()#EETEETEsynchsynchEE+TEEETTFTsynchTFTsynchsynchTTT*FTTTFFisynchsynchF(E)synchsynch)i*+i步骤步骤(bzhu)符号符号(
38、fho)栈栈输入串输入串附注附注0#E)i*+i#1#Ei*+i#i属于属于FIRST(E)2#ETi*+i#ETEETE3#ETFi*+i#TFT4#ETii*+i#5#ET *+i#6#ETF* *+i#7#ETF +i#8#ET +i#9#E +i#T10#ET+ +i#E+TE11#ET i#12#ETF i#TFT13#ETi i#Fi14#ET #15#E #T16# #E错，跳过）错，跳过）TiT*FT错，同步，弹出错，同步，弹出F第四十页，共四十二页。 第四十一页，共四十二页。内容(nirng)总结Part4语法分析。因此，我们要使用自顶向下分析法必须要消除文法的左递归。PP。把文法G的所有非终结符按任一种顺序排列成P1,P2,。若此候选无法完成匹配任务，则任何其他候选也肯定无法完成。经过反复提取左因子，就能够把每个非终结符（包括新引进者）的所有候选首符集便成为两两不相交(xingjio)。前面的巴科斯范式只用到了两个元符号“”和“|”。integerdigitdigit。其中A为非终结符，a是终结符或#第四十二页，共四十二页。