编译原理课件chap04(陈火旺).ppt-淘文阁

资源描述

《编译原理课件chap04(陈火旺).ppt》由会员分享，可在线阅读，更多相关《编译原理课件chap04(陈火旺).ppt（75页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第四章语法分析-自上而下分析第四章第四章语法分析语法分析自上而下分析自上而下分析高级语言的语法结构适合用上下无关文法描述，高级语言的语法结构适合用上下无关文法描述，因此，我们将上下文无关文法作为语法分析的基础。因此，我们将上下文无关文法作为语法分析的基础。本章和下一章，我们将介绍编译程序构造中的一些本章和下一章，我们将介绍编译程序构造中的一些典型的语法分析方法典型的语法分析方法4.1语法分析器功能语法分析器功能语法分析是编译过程的核心部分。它的任务是在语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定词法分析识别出单词符号串的基础上，分析并判定程序的语法结构

2、是否符合语法规则。程序的语法结构是否符合语法规则。下图表明了语法分析器在编译程序中的地位。下图表明了语法分析器在编译程序中的地位。第四章语法分析-自上而下分析源程序词法分析单词符号取下一单词语法分析词法分析树编译后续符号表语法分析器在编译程序中地位语法分析器在编译程序中地位第四章语法分析-自上而下分析语法分析是编译程序的核心部分：在词法分析的基础上，识别单词符号序列是否是给定文法的正确句子（程序）。常用方法自顶向下分析自底向上分析确定不确定算符优先分析LR分析第四章语法分析-自上而下分析自顶向下语法分析方法自顶向下分析法就是从文法的开始符号出发，试图推导出与输入的单词串完全匹配的句子。如果能够

3、推导出，则该输入串是给定文法的句子；如果不能推导出，则该输入串不是给定文法的句子。第四章语法分析-自上而下分析例：已知符号串例：已知符号串例：已知符号串例：已知符号串S=cadS=cad文法文法文法文法GZ:GZ:ZcAdZcAdAab|aAab|a求解求解求解求解S S L(GZ)L(GZ)分析过程分析过程分析过程分析过程是设法建立一棵语法树是设法建立一棵语法树是设法建立一棵语法树是设法建立一棵语法树,使语法树的末端结点与使语法树的末端结点与使语法树的末端结点与使语法树的末端结点与给定符号串相匹配给定符号串相匹配给定符号串相匹配给定符号串相匹配.1.1.开始开始开始开始:令令令令Z Z为根结

4、点为根结点为根结点为根结点Z Z2.2.用用用用Z Z的右部的右部的右部的右部,符号串去匹配输入串符号串去匹配输入串符号串去匹配输入串符号串去匹配输入串 Z Zc cA Ad d完成一步推导完成一步推导完成一步推导完成一步推导Z ZcAdcAd 检查检查检查检查 c-cc-c匹配匹配匹配匹配 A A是非终结符是非终结符是非终结符是非终结符,将匹配任务交给将匹配任务交给将匹配任务交给将匹配任务交给A A第四章语法分析-自上而下分析6 6 6 63.3.选用选用选用选用A A的右部符号串匹配输入串的右部符号串匹配输入串的右部符号串匹配输入串的右部符号串匹配输入串 A A有两个右部有两个右部有两个右

5、部有两个右部,选第一个选第一个选第一个选第一个 c cA Ad da ab bZ Z完成进一步推导完成进一步推导完成进一步推导完成进一步推导A Aabab检查检查检查检查,a-a,a-a匹配匹配匹配匹配,b-d,b-d不匹配不匹配不匹配不匹配(失败失败失败失败)但是还不能冒然宣布但是还不能冒然宣布但是还不能冒然宣布但是还不能冒然宣布S S L(GZ)L(GZ)4.4.回溯回溯回溯回溯即砍掉即砍掉即砍掉即砍掉A A的子树的子树的子树的子树改选改选改选改选A A的第二右部的第二右部的第二右部的第二右部 Z Zc cA Ad da aA Aaa检查检查检查检查 a-aa-a匹配匹配匹配匹配 d-

6、dd-d匹配匹配匹配匹配建立语法树建立语法树建立语法树建立语法树,末端结点为末端结点为末端结点为末端结点为cadcad与输入与输入与输入与输入cadcad相匹配相匹配相匹配相匹配,建立了推导序列建立了推导序列建立了推导序列建立了推导序列 E EcAdcAdcadcadcadcad L(G(E)L(G(E)S=cadGZ:ZcAdS=cadGZ:ZcAdAab|aAab|a分析工作要部分析工作要部分析工作要部分析工作要部分地或全部地分地或全部地分地或全部地分地或全部地退回去重做叫退回去重做叫退回去重做叫退回去重做叫回溯回溯回溯回溯第四章语法分析-自上而下分析自顶向下语法分析要解决的关键问题假定要

7、被代换的最左非终结符号是假定要被代换的最左非终结符号是B，且，且有有n条规则：条规则：BA1|A2|An，那么如何，那么如何确定用哪个右部去替代确定用哪个右部去替代B？第四章语法分析-自上而下分析1.分析过程是带有预测的，对输入符号串要分析过程是带有预测的，对输入符号串要预测属于什么语法成分，然后根据该语法预测属于什么语法成分，然后根据该语法成分的文法建立语法树。成分的文法建立语法树。2.分析过程是一种试探过程，是尽一切办法分析过程是一种试探过程，是尽一切办法(选用不同规则选用不同规则)设法建立语法树的过程，设法建立语法树的过程，由于是试探过程，故难免有失败，由于是试探过程，故难免有失败，所以

8、分析所以分析过程需进行回溯，因此我们也称这种方法是带过程需进行回溯，因此我们也称这种方法是带回溯的自顶向下分析方法。回溯的自顶向下分析方法。第四章语法分析-自上而下分析自顶向下分析存在的问题及解决方法自顶向下分析自顶向下分析方法的基本方法的基本缺点缺点：不能处理不能处理具有左递归性的文法具有左递归性的文法自顶向下分析为什么不能处理左递归文法？自顶向下分析为什么不能处理左递归文法？文法文法G G，存在，存在UUVnVn，ifU=U,ifU=U,则则G G为左递归文法为左递归文法+1左递归文法：左递归文法左递归文法回溯问题回溯问题第四章语法分析-自上而下分析10101010如果我们在匹配输入串过程

9、中，假定正好轮到要用非终结符如果我们在匹配输入串过程中，假定正好轮到要用非终结符如果我们在匹配输入串过程中，假定正好轮到要用非终结符如果我们在匹配输入串过程中，假定正好轮到要用非终结符 U U直接直接直接直接匹配输入串，即要用匹配输入串，即要用匹配输入串，即要用匹配输入串，即要用U U的右部符号串的右部符号串的右部符号串的右部符号串UU去匹配，为去匹配，为去匹配，为去匹配，为了用了用了用了用UU去匹配，又得用去匹配，又得用去匹配，又得用去匹配，又得用U U去匹配，这样无限的循环下去去匹配，这样无限的循环下去去匹配，这样无限的循环下去去匹配，这样无限的循环下去将无法终止。将无法终止。将无法终

10、止。将无法终止。如果文法具有如果文法具有如果文法具有如果文法具有间接间接间接间接左递归，则也将发生上述问题，只不过左递归，则也将发生上述问题，只不过左递归，则也将发生上述问题，只不过左递归，则也将发生上述问题，只不过环的圈子兜的更大。环的圈子兜的更大。环的圈子兜的更大。环的圈子兜的更大。要实行自顶向下分析，必须要消除文法的左递归，下面要实行自顶向下分析，必须要消除文法的左递归，下面要实行自顶向下分析，必须要消除文法的左递归，下面要实行自顶向下分析，必须要消除文法的左递归，下面我们将介绍我们将介绍我们将介绍我们将介绍直接直接左递归的消除方法左递归的消除方法左递归的消除方法左递归的消除方法，在此

11、基础上再介，在此基础上再介，在此基础上再介，在此基础上再介绍绍绍绍一般一般左递归的消除方法左递归的消除方法左递归的消除方法左递归的消除方法。自顶向下分析为什么不能处理左递归文法？自顶向下分析为什么不能处理左递归文法？自顶向下分析为什么不能处理左递归文法？自顶向下分析为什么不能处理左递归文法？第四章语法分析-自上而下分析11111111消除消除直接直接左递归左递归:11111111规则一（提因子）规则一（提因子）规则一（提因子）规则一（提因子）i)i)已知已知已知已知 Uxy|xw|xzUxy|xw|xz解：解：解：解：Ux(y|w|z)Ux(y|w|z)得：得：得：得：UxUUxUUy|w|z

12、Uy|w|ziii)iii)已知已知已知已知 Ux|xyUx|xy解：解：解：解：Ux(y|)Ux(y|)使用提因子法使用提因子法使用提因子法使用提因子法，不仅有助于消除直接左递归。而且，不仅有助于消除直接左递归。而且，不仅有助于消除直接左递归。而且，不仅有助于消除直接左递归。而且有助于压缩文件的长度，使我们更加有效的分析句子。有助于压缩文件的长度，使我们更加有效的分析句子。有助于压缩文件的长度，使我们更加有效的分析句子。有助于压缩文件的长度，使我们更加有效的分析句子。ii)ii)已知已知已知已知 Uxy|xw|xzUxy|xw|xzyyyy1 1y y2 2wywy1 1w w2 2解：解：

13、解：解：Ux(yUx(y11(y(y22|w|w22)|z)|z)得：得：得：得：UxUUxUUyUy11y y1 1|z|zyy1 1yy22|w|w2 2第四章语法分析-自上而下分析12121212规则二规则二规则二规则二将左递归规则改为右递归规则将左递归规则改为右递归规则将左递归规则改为右递归规则将左递归规则改为右递归规则若：若：若：若：PPPP|则可改写为：则可改写为：则可改写为：则可改写为：PP PPPP P|P|例例例例22已知已知已知已知GEGE：E:=T*F|T/F|FE:=T*F|T/F|FT:=F|T*F|T/FT:=F|T*F|T/F 解：左递归改为右递归得：解：左递归

14、改为右递归得：解：左递归改为右递归得：解：左递归改为右递归得：E:=T*F|T/F|FE:=T*F|T/F|F T:=FTT:=FTT:=*FT|/FT|T:=*FT|/FT|第四章语法分析-自上而下分析一般而言，假定关于一般而言，假定关于P的全部产生式是的全部产生式是PP 1|P 2|P 1m|1|2|n其中，每个其中，每个都不等于都不等于，而每个，而每个都不都不以以P开头，那末，消除开头，那末，消除P的直接左递归性就是把的直接左递归性就是把这些规则改写成：这些规则改写成：P|1P|2P|nPP1P|2P|mP|第四章语法分析-自上而下分析1414消除消除一般一般左递归左递归1.把把G的

18、非终结符的排序不同由于对非终结符的排序不同由于对非终结符的排序不同,最后得到的文法在形最后得到的文法在形最后得到的文法在形最后得到的文法在形式上可能是不一样的式上可能是不一样的式上可能是不一样的式上可能是不一样的,但是不难证明它们的等价但是不难证明它们的等价但是不难证明它们的等价但是不难证明它们的等价.第四章语法分析-自上而下分析自顶向下语法分析方法自顶向下语法分析方法自顶向下分析法分确定性和不确定性两自顶向下分析法分确定性和不确定性两种。种。自顶向下的确定性分析法对文法有一定自顶向下的确定性分析法对文法有一定的限制，但实现简单直观，便于手工或的限制，但实现简单直观，便于手工或自动构造；自动

19、构造；自顶向下的不确定性分析法是带有回溯自顶向下的不确定性分析法是带有回溯的分析方法，效率低，代价高，极少使的分析方法，效率低，代价高，极少使用。用。第四章语法分析-自上而下分析一、一、确定的自顶向下分析思想确定的自顶向下分析思想1、方方法法：从从开开始始符符号号出出发发，不不断断替替换换非非终终结结符符，根根据据当当前前的的单单词词符符号号就就可可以以唯唯一一选选定定要要替替换换的的产产生生式。式。例例1：文法：文法G(S)：SpASqBAcAdAa输入串输入串W=pccadd自顶向下的推导过程为自顶向下的推导过程为:第四章语法分析-自上而下分析SPASPAcdAcdASPAcdAcdASP

20、AcdAa相应的语法树：相应的语法树：SpApcAdpccAddpccaddSpASqBAcAdAa输入串W=pccadd第四章语法分析-自上而下分析例例1：文法：文法G(S)：SpASqBAcAdAa该文法的特点：该文法的特点：（1）每个产生式的右部都由）每个产生式的右部都由终结符号终结符号开始；开始；（2）如果两个产生式有）如果两个产生式有相同的左部相同的左部，则它们的，则它们的右部右部由由不同不同的终结符开始。的终结符开始。对于这样的文法，其推导过程可以根据当前的输对于这样的文法，其推导过程可以根据当前的输入符号决定选择哪个产生式往下推导，因此，分入符号决定选择哪个产生式往下推导，因此，

21、分析过程是析过程是唯一确定唯一确定的。的。第四章语法分析-自上而下分析例例2：文法：文法G(S)为：为：SApSBqAa cABb dB该文法的特点：该文法的特点：（1）产生式的右部不全是由终结符号开始；）产生式的右部不全是由终结符号开始；（2）如果两个产生式有）如果两个产生式有相同的左部相同的左部，则它们的，则它们的右右部部由由不同不同的终结符或非终结符开始。的终结符或非终结符开始。（3）无空产生式。无空产生式。ccap如何根据输入串的第如何根据输入串的第1个符号来确定产生式呢？个符号来确定产生式呢？第四章语法分析-自上而下分析例例2：文法：文法G(S)为：为：SApSBqAa cABb d

22、B当输入当输入W=ccap推导：推导：自顶向下的推导过程为：自顶向下的推导过程为：第四章语法分析-自上而下分析例例2：文法：文法G(S)为：为：SApSBqAa cABb dB当输入当输入W=ccap推导：推导：自顶向下的推导过程为：自顶向下的推导过程为：SApcApccApccap语法树为：语法树为：SAPSAPcASAPcAcASAPcAcAa第四章语法分析-自上而下分析例例2：文法：文法G(S)为：为：SApSBqAa cABb dB该文法的特点：该文法的特点：（1）产生式的右部不全是由终结符号开始；）产生式的右部不全是由终结符号开始；（2）如果两个产生式有）如果两个产生式有相同的左部相

23、同的左部，则它们的，则它们的右右部部由由不同不同的终结符或非终结符开始。的终结符或非终结符开始。（3）无空产生式。无空产生式。ccap如何根据输入串的第如何根据输入串的第1个符号来确定产生式呢？个符号来确定产生式呢？第四章语法分析-自上而下分析2、开始符号集合的定义：、开始符号集合的定义：设设G=（VT，VN，P，S）是上下文无关文法，）是上下文无关文法，开开始始符符号号集集合合为为First()=a|a，aVT，、V*规规则则右右部部的的开开始始符符号号集集包包括括所所有有终终结结符符a，使使得得规规则则右右部部经经过若干推导后得到的字符串以过若干推导后得到的字符串以a为起始。为起始。若

25、IRST(Bq)=b，d针对产生式规则的右部产生开始符号集合第四章语法分析-自上而下分析如何根据输入串的第如何根据输入串的第1 1个符号来确定产生式呢个符号来确定产生式呢？根据当前输入符号属于哪个产生式右部的开始根据当前输入符号属于哪个产生式右部的开始符号集合而决定选择相应产生式进行推导。符号集合而决定选择相应产生式进行推导。第四章语法分析-自上而下分析例例3：文法：文法GS：SaA|dAbAS|若输入若输入W=abd，则推导过程为：，则推导过程为：第四章语法分析-自上而下分析SaASaAbASSaAbASd例例3：文法：文法GS：SaA|dAbAS|若输入若输入W=abd，则推导过程为：，则

26、推导过程为：SaAabASabSabd当非终结符当非终结符A面临输入符号面临输入符号d，且，且d不属于不属于A的任的任何候选首符集，但何候选首符集，但A的候选首符集包含的候选首符集包含第四章语法分析-自上而下分析当某一非终结符的产生式中含有空产生式时，第二步推当某一非终结符的产生式中含有空产生式时，第二步推导的产生式该如何确定呢导的产生式该如何确定呢？根据后跟符号集合确定根据后跟符号集合确定3、后跟符号集合的定义：设设G=（VT，VN，P，S）是是上上下下文文无无关关文文法法，AVN，S是开始符号，是开始符号，Follow(A)=a|S uA且且aVT，a First()，uVT*，V+。针对

27、非终结符针对非终结符若若SuA，且，且，则，则#Follow(A)（#表示输入串的结束符，或句子括号）表示输入串的结束符，或句子括号）可写成为：可写成为：Follow(A)a|SAa，aVT若若SA，则，则#Follow(A)。*第四章语法分析-自上而下分析Follow(A)是所有句型中出现在紧接是所有句型中出现在紧接A之后的终结之后的终结符或符或“#”。例例4：在例：在例2中文法中文法GS为：为：SAp|BqAa|cABb|dB求求Follow集。集。解：解：Follow(S)=？Follow(A)=？Follow(B)=？第四章语法分析-自上而下分析换句话说：换句话说：Follow(A)是

28、所有句型中出现在紧接是所有句型中出现在紧接A之后的终结之后的终结符或符或“#”。例例4：在例：在例2中文法中文法GS为：为：SAp|BqAa|cABb|dB求求Follow集。集。解：解：Follow(S)=#Follow(A)=pFollow(B)=q第四章语法分析-自上而下分析自上而下语法分析要解决的关键问题自上而下语法分析要解决的关键问题假定要被代换的最左非终结符号是假定要被代换的最左非终结符号是B，且，且有有n条规则：条规则：BA1|A2|An，那么如何，那么如何确定用哪个确定用哪个右部去替代去替代B？根据规则的选择集合来确定。根据规则的选择集合来确定。第四章语法分析-自上而下分析4、

29、选择集合的定义、选择集合的定义给定上下文无关文法的产生式给定上下文无关文法的产生式A，A VN，V*，若若，则，则Select（A）=First()，若若，则，则Select(A)=（First()-）Follow(AA)*给定输入串，根据产生式规则的选择集合选择产生给定输入串，根据产生式规则的选择集合选择产生式进行推导。式进行推导。第四章语法分析-自上而下分析5、LL(1)文法的定义：文法的定义：文法不含左递归；文法不含左递归；文法不含左递归；文法不含左递归；对于文法中每个非终结符对于文法中每个非终结符对于文法中每个非终结符对于文法中每个非终结符A A A A的各个产生式的候选首的各个产生式

30、的候选首的各个产生式的候选首的各个产生式的候选首符集两两不相交。即，若符集两两不相交。即，若符集两两不相交。即，若符集两两不相交。即，若Ax1|x2|xn Ax1|x2|xn Ax1|x2|xn Ax1|x2|xn 如果：如果：如果：如果：FIRST(xi)FIRST(xj)=(iFIRST(xi)FIRST(xj)=(iFIRST(xi)FIRST(xj)=(iFIRST(xi)FIRST(xj)=(ij,i,j=1,2,n)j,i,j=1,2,n)j,i,j=1,2,n)j,i,j=1,2,n)而当而当而当而当FIRST(xi)FIRST(xi)FIRST(xi)FIRST(xi)时，有

31、时，有时，有时，有 FIRST(xi)FOLLOW(U)=FIRST(xi)FOLLOW(U)=FIRST(xi)FOLLOW(U)=FIRST(xi)FOLLOW(U)=一个文法若满足以上条件，则称该文法为一个文法若满足以上条件，则称该文法为一个文法若满足以上条件，则称该文法为一个文法若满足以上条件，则称该文法为LL(1)LL(1)LL(1)LL(1)文法。文法。文法。文法。只有对满足只有对满足LL(1)文法的句子，才能进行确定的自顶文法的句子，才能进行确定的自顶向下分析：向下分析：给给定定输输入入串串，就就可可以以根根据据产产生生式式规规则则的的选选择择集集合合确确定定唯唯一一的产生式进行

32、推导。的产生式进行推导。第四章语法分析-自上而下分析LL(1)的含义：从左L向右扫描输入串，分析过程中采用最左L推导，只需向右看1个符号就可确定如何推导（选择哪个产生式进行推导）。第四章语法分析-自上而下分析例5：上例3文法：SaA|dAbAS|证明该文法为LL(1)文法。第四章语法分析-自上而下分析例5：上例3文法：SaA|dAbAS|证明该文法为LL(1)文法。不难看出：Select(SaA)=First(aA)aSelect(Sd)=First(d)=dSelect(AbAS)=bSelect(A)=（first()-）follow(A)=a,d,#Select(SaA)Select(S

33、d)ad=Select(AbAS)Select(A)ba,d,#=所以上述文法是LL(1)文法。SAaaA*SaAabASabAdSaAabASabAaA所以Follow(A)=a,d,#第四章语法分析-自上而下分析例：设文法GS为：SaAS|bAbA|判别是否是LL(1)文法。第四章语法分析-自上而下分析解：Select(SaAS)=first(aAS)=aSelect(Sb)=bSelect(AbA)=bSelect(A)=（first()-）follow(A)=a,bSelect(SaAS)Select(Sb)ab=Select(AbA)Select(A)ba,b因此，该文法不是LL（1

34、）文法，因而也就不可能用确定的自顶向下分析。第四章语法分析-自上而下分析当需要选用自顶向下分析技术时，首先必须判定所给的文法是否是LL(1)文法文法。第四章语法分析-自上而下分析4.4递归下降分析程序构造（递归下降分析程序构造（见见P75）当一个文法满足当一个文法满足LL(1)条件时，我们就可以构造一个不带回溯的条件时，我们就可以构造一个不带回溯的自上而下分析程序，这个分析程序由一组递归过程组成，每个过自上而下分析程序，这个分析程序由一组递归过程组成，每个过程对应文法的一个非终结符。这样一个分析程序称为递归下降分程对应文法的一个非终结符。这样一个分析程序称为递归下降分析器。析器。在本节中我们对

35、巴科斯范式进行了扩充：在本节中我们对巴科斯范式进行了扩充：（1）用花括号）用花括号表示闭包运算表示闭包运算*(2）用）用 0n表示表示可以任意重复可以任意重复0次至次至n次，次，00=。（3）用方括号）用方括号表示表示 01，即表示，即表示的出现可有可无。的出现可有可无。4.5预测分析程序预测分析程序使用高级语言的递归过程描述递归下降分析器，只有当具有实使用高级语言的递归过程描述递归下降分析器，只有当具有实现这种过程的编译系统时才有实际意义。实现现这种过程的编译系统时才有实际意义。实现LL(1)分析的另一种分析的另一种有效方式是使用一张分析表和一个栈进行联合控制。我们现在介有效方式是使

36、用一张分析表和一个栈进行联合控制。我们现在介绍的绍的预测分析程序预测分析程序就是属于这种类型的就是属于这种类型的LL(1)分析器。分析器。本节要本节要掌握对给定文法构造出每个非终结符的掌握对给定文法构造出每个非终结符的FIRST和和FOLLOW集合。集合。第四章语法分析-自上而下分析2、预测分析方法：、预测分析方法：自顶向下分析的另一种方法自顶向下分析的另一种方法(1)预测分析器的组成：预测分析器的组成：预测分析程序预测分析程序先进后出栈先进后出栈预测分析表与文法有关预测分析表与文法有关第四章语法分析-自上而下分析预测分析表可用一个矩阵表示。矩阵元预测分析表可用一个矩阵表示。矩阵元素素MA,a

37、中的中的A表示非终结符，表示非终结符，a表示终表示终结符或句子结束符结符或句子结束符#，矩阵元素，矩阵元素MA,a中中的内容是一条关于的内容是一条关于A的产生式，表明当用的产生式，表明当用非终结符非终结符A向下推导时，面临输入符向下推导时，面临输入符a时，时，所采用的候选产生式，当元素内容无产所采用的候选产生式，当元素内容无产生式时，表明用生式时，表明用A为左部向下推导时遇到为左部向下推导时遇到了不该出现的符号，因此元素内容为转了不该出现的符号，因此元素内容为转向出错处理。向出错处理。如何构造预测分析表？如何构造预测分析表？第四章语法分析-自上而下分析45454545()构造分析表构造分析表构

38、造分析表构造分析表基本思想是基本思想是基本思想是基本思想是:当文法中某一非终结符呈现在当文法中某一非终结符呈现在当文法中某一非终结符呈现在当文法中某一非终结符呈现在栈顶时栈顶时栈顶时栈顶时,根据当前的输入符号根据当前的输入符号根据当前的输入符号根据当前的输入符号,分分分分析表应指示析表应指示析表应指示析表应指示要用该非终结符里要用该非终结符里要用该非终结符里要用该非终结符里的哪一条规则去匹配输入串的哪一条规则去匹配输入串的哪一条规则去匹配输入串的哪一条规则去匹配输入串(即即即即进行下一步最左推导进行下一步最左推导进行下一步最左推导进行下一步最左推导)根据这个思想根据这个思想根据这个思想根据这个

39、思想,我们不难把构我们不难把构我们不难把构我们不难把构造分析表算法构造出来造分析表算法构造出来造分析表算法构造出来造分析表算法构造出来!终结符号终结符号终结符号终结符号非非非非终终终终结结结结符符符符号号号号第四章语法分析-自上而下分析表驱动的预测分析程序模型表驱动的预测分析程序模型（P77P77）第四章语法分析-自上而下分析(2)分析过程：#S进栈，当前终结符送a上托栈顶符号放入XXVT？Xa？X=#？ENDerrorM(X,a)是产生式吗？Xa？error若产生式为Xx1x2xn按逆序即xnx2x1入栈读下一个符号yyynnnyynn第四章语法分析-自上而下分析48484848执行程序主要

40、实现如下操作执行程序主要实现如下操作执行程序主要实现如下操作执行程序主要实现如下操作:1.1.把把把把#和文法识别符号和文法识别符号和文法识别符号和文法识别符号E E推进栈推进栈推进栈推进栈,并读入输入串的第一并读入输入串的第一并读入输入串的第一并读入输入串的第一个符个符个符个符a,a,重复下述过程直到正常结束或出错重复下述过程直到正常结束或出错重复下述过程直到正常结束或出错重复下述过程直到正常结束或出错.2.2.测定栈顶符号测定栈顶符号测定栈顶符号测定栈顶符号X X和当前输入符号和当前输入符号和当前输入符号和当前输入符号a,a,执行如下操作执行如下操作执行如下操作执行如下操作:(1)(1)

41、若若若若X=a=#X=a=#，分析成功，停止。，分析成功，停止。，分析成功，停止。，分析成功，停止。E E匹配输入串成功匹配输入串成功匹配输入串成功匹配输入串成功.(2)(2)若若若若X=a#X=a#，把，把，把，把X X推出栈，再读入下一个符号。推出栈，再读入下一个符号。推出栈，再读入下一个符号。推出栈，再读入下一个符号。(3)(3)若若若若X XV Vn n，查分析表，查分析表，查分析表，查分析表MM（详细步骤见下页）（详细步骤见下页）（详细步骤见下页）（详细步骤见下页）第四章语法分析-自上而下分析49494949(3)若若XVn，查分析表，查分析表M。a)MX,a=X=UVW则将则将X弹

42、出栈，将弹出栈，将UVW压入压入注：注：U在栈顶在栈顶（最左推导）（最左推导）b)MX,a=error转出错处理转出错处理c)MX,a=X:=-a为为X的后继符号的后继符号则将则将X弹出栈弹出栈（不读下一符号）（不读下一符号）继续分析。继续分析。第四章语法分析-自上而下分析分析算法分析算法 BEGINBEGIN 首先把首先把#然后把文法开始符号推入栈；把第一个输然后把文法开始符号推入栈；把第一个输入符号读进入符号读进a;FLAGa;FLAG：=TRUE=TRUE；WHILE FLAG DOWHILE FLAG DO BEGIN BEGIN 把栈顶符号上托出去并放在把栈顶符号上托出去并放在中；中

43、；IF X IF X Vt THEN IF X=a THEN Vt THEN IF X=a THEN 把下一把下一个输入符号读进个输入符号读进a a ELSE ERRORELSE ERROR ELSE IF X=ELSE IF X=#THEN THEN IF X=a THEN FLAG:=FALSE IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE ERROR ELSE IF ELSE IF X,b=X X,b=X X X1 1X X2 2.X.XK K THEN THEN 把把X XK K，X X K-1K-1,.,X,.,X1 1一一推进栈一一推进栈 ELSE

44、ELSEERRORERROR END OF WHILE;END OF WHILE;STOP/*STOP/*分析成功，过程完毕分析成功，过程完毕*ENDEND第四章语法分析-自上而下分析预测分析表构造算法预测分析表构造算法1.1.对文法对文法G G的每个产生式的每个产生式执行第二步执行第二步和第三步；和第三步；2.2.对每个终结符对每个终结符a a FIRST(FIRST()，把，把加加至至A,aA,a中，中，3.3.若若 FIRST(FIRST()，则对任何则对任何b b FOLLOW(A)FOLLOW(A)把把加至加至A,bA,b中，中，4.4.把所有无定义的把所有无定义的A,aA

45、,a标上标上“出错标志出错标志”。可以证明，一个文法可以证明，一个文法G G的预测分析表不含多重的预测分析表不含多重入口，当且仅当该文法是入口，当且仅当该文法是LL(1)LL(1)的的第四章语法分析-自上而下分析(3)实例分析：给定文法，构造预测分析表，并针对输入串i+i*i#构造预测分析过程。例：文法为：例：文法为：EE+T|TTT*F|FFi|(E)步骤：步骤：（1）判断文法是否为LL(1)文法。P如果文法中含有左递归，必须先消除左递归：如果文法中含有左递归，必须先消除左递归：（2）构造预测分析表）构造预测分析表：Select(A)（3）列出预测分析过程第四章语法分析-自上而下分析SSaS

47、T)=*，First(F)=(，iETE T不不，E不不First(E)=first(T)=first(F)=(,i 求求Follow集：集：Follow(E)=，#Follow(E)=，#Follow(T)=+，#Follow(T)=+，#Follow(F)=*，+，#ETEFTE(E)TEETEFTE(E)TE(TE)TEETET+TET+TT+FTT+(E)TT+(TE)TT+(T)TETEFTEFTF*FTF*(E)TF*(TE)TF*(FTE)TF*(FT)T第四章语法分析-自上而下分析求Select集：Select(ETE)=(，iSelect(E+TE)=+Select(E)=，

48、#Select(TFT)=(，iSelect(T*FT)=*Select(T)=，+，#Select(Fi)=iSelect(F(E)=(由上可知有相同左部产生式的Select集合的交集为空，所以文法是LL(1)第四章语法分析-自上而下分析v构造预测分析表构造预测分析表：方法：方法：对每个终结符或对每个终结符或#用用a表示。表示。若若a Select(Aa)，则，则Aa放入放入MA,a中。中。i+*()#ETETEE+TETFTFTT*FTFi(E)第四章语法分析-自上而下分析w对于某句子的分析过程：下面用预测分析程序，栈和预测分析表对输入串i+i*i#进行分析，给出栈的变化过程如下：步骤分析

49、栈剩余输入串所用产生式1#Ei+i*i#ETE2#ETi+i*i#TFT3#ETFi+i*i#Fi4#ETii+i*i#i匹配5#ET+i*i#T6#E+i*i#E+TE第四章语法分析-自上而下分析7#ET+i*i#+匹配8#ETi*i#TFT9#ETFi*i#Fi10#ETii*i#i匹配11#ET*i#T*FT12#ETF*i#*匹配13#ETFi#Fi14#ETii#i匹配15#ET#T 16#E#E 17#接受第四章语法分析-自上而下分析表驱动的预测分析程序模型表驱动的预测分析程序模型第四章语法分析-自上而下分析定义：定义：定义：定义：FIRST()=a|FIRST()=a|aa，a

50、a V Vt t，,V*V*若若若若，则规定，则规定，则规定，则规定 FIRST()FIRST()该集合称为该集合称为该集合称为该集合称为的头符号集合的头符号集合的头符号集合的头符号集合*61616161定义：定义：定义：定义：A AV VnnFOLLOW(A)=a|ZFOLLOW(A)=a|ZAA且且且且a aV Vt t,a,aFIRST(),FIRST(),V Vt t*,V V+若若若若ZZA,A,且且且且，则，则，则，则#FOLLOW(A)FOLLOW(A)该集合称为该集合称为该集合称为该集合称为A A的后继符号集合的后继符号集合的后继符号集合的后继符号集合或定义为：或定义为

展开阅读全文