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