编译技术语法分析11ppt课件

资源描述

《编译技术语法分析11ppt课件》由会员分享，可在线阅读，更多相关《编译技术语法分析11ppt课件（94页珍藏版）》请在金锄头文库上搜索。

1、编译原理第四章第四章语法分析语法分析自上而下分析自上而下分析1.四元式四元式单词符号单词符号语法单位语法单位四元式四元式目标代码目标代码词法分析器词法分析器语法分析器语法分析器语义分析与中间代码生成语义分析与中间代码生成器器优化段优化段源程序源程序表表格格管管理理出出错错处处理理目标代码生成器目标代码生成器2第四章第四章语法分析语法分析自上而下分析自上而下分析n本章主要介绍语法分析的处理本章主要介绍语法分析的处理n要进行语法分析，必须对语言的语法结构进行描述。要进行语法分析，必须对语言的语法结构进行描述。采用正规式和有限自动机可以描述和识别语言的单词符号；采用正规式和有限自动机可以描述和识别语

2、言的单词符号；用上下文无关文法来描述语法规则。用上下文无关文法来描述语法规则。3n上下文无关文法的定义：上下文无关文法的定义：一个上下文无关文法一个上下文无关文法G G是一个四元式是一个四元式 G=(VG=(VT T，V VN N，S S，P)P)，其中，其中V VT T：终结符集合：终结符集合( (非空非空) )V VN N：非终结符集合：非终结符集合( (非空非空) )，且，且V VT T V VN N= =S S：文法的开始符号，：文法的开始符号，S S V VN NP P：产生式集合：产生式集合( (有限有限) )，每个产生式形式为，每个产生式形式为P P， P P V VN N，

3、( (V VT T V VN N) )* *开始符开始符S S至少必须在某个产生式的左部出现一次。至少必须在某个产生式的左部出现一次。4n例，定义只含例，定义只含+，*的算术表达式的文法的算术表达式的文法G=，其中，其中，P由下列产生式组成：由下列产生式组成：EiEE+EEE*EE(E)5n定义：称定义：称 A 直接推出直接推出，即，即 A仅当仅当A 是一个产生式，是一个产生式，且且，(VT VN)*。n如果如果 1 2n，则我们称这个序列是从，则我们称这个序列是从 1到到 n的一个推导。若存的一个推导。若存在一个从在一个从 1到到 n的推导，则称的推导，则称 1可以推导出可以推导出 n。n

4、例：对文法例：对文法(1)E(E)(E+E)(i+E)(i+i)6n通常，用通常，用表示：从表示：从 1 1出发，经过一步或若干步，可以推出出发，经过一步或若干步，可以推出 n n。用用表示：从表示：从 1 1出发，经过出发，经过0 0步或若干步，可以推出步或若干步，可以推出 n n。所以所以：即即或或q定义：假定定义：假定G G是一个文法，是一个文法，S S 是它的开始符号。如果是它的开始符号。如果，则，则称是一个称是一个句句型型。仅含终结符号的句型是一个。仅含终结符号的句型是一个句子句子。文法。文法G G所产生的句子的全体是一个所产生的句子的全体是一个语言语言，将，将它记

5、为它记为 L(G)L(G)。74.1 语法分析器的功能语法分析器的功能n语法分析的任务是分析一个文法的句子结构。语法分析的任务是分析一个文法的句子结构。n语法分析器的功能：按照文法的产生式语法分析器的功能：按照文法的产生式( (语言的语法规则语言的语法规则) )，识别输入符，识别输入符号串是否为一个句子号串是否为一个句子( (程序程序) )。8源程序源程序单词符号单词符号取下一单词取下一单词.语法分语法分析树析树词法分词法分析器析器语法分语法分析器析器符号表符号表编译程序编译程序后续部分后续部分9n语法分析的方法：语法分析的方法：自下而上分析法自下而上分析法(Bottom-up)(Bottom

6、-up)n基本思想：从输入串开始，逐步进行基本思想：从输入串开始，逐步进行“归约归约”，直到文法的开始符号。即，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。把产生式的右部替换成左部符号。n算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。分析表达式。nLRLR分析法：规范归约分析法：规范归约10G(E)：Ei|E+E|E-E|E*E|E/E|(E)i*i+iE*i+iE*E+iE

7、+iE+EEi+ +* *EiiEEEE11n语法分析的方法：语法分析的方法：自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)自上而下分析法自上而下分析法(Top-down)(Top-down)n基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找匹配匹配的的推导推导。n递归下降分析法：对每一语法变量递归下降分析法：对每一语法变量( (非终结符非终结符) )构造一个相应的子程序，构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作每个子程序识别一定的语法单位，通过子程序间的

8、信息反馈和联合作用实现对输入串的识别。用实现对输入串的识别。n预测分析程序预测分析程序F优点：直观、简单和宜于手工实现。优点：直观、简单和宜于手工实现。124.2.1自上而下分析面临的问题自上而下分析面临的问题n自上而下就是从文法的开始符号出发，向下自上而下就是从文法的开始符号出发，向下推导推导，推出句子。，推出句子。带带“回溯回溯”的的不带回溯的递归子程序不带回溯的递归子程序(递归下降递归下降)分析方法。分析方法。n自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号符号(根结点根结点)出发，自上而下地为输入

9、串建立一棵出发，自上而下地为输入串建立一棵语法树语法树。或者说，为输入。或者说，为输入串寻找一个最左推导。串寻找一个最左推导。13n例例4.1假定有文法假定有文法G(S):(1)SxAy(2)A*|*分析分析输入串输入串x*y(记为记为 )。Sx*yIPSx*yIPAxySx*yIPAxySx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*14例例假定有文法假定有文法GS: SSb GS: SSb Sa L=abSa L=abn n | n1 | n1W=abbb W=abbb S S b S b 15n当某个非终结符有多个产生式候选时，可能带来如下问题当某个非终结

10、符有多个产生式候选时，可能带来如下问题: :1. 1. 分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的是暂时的。出错。出错时时，不得不，不得不“回溯回溯”。2. 2. 文法左递归问题文法左递归问题。一个文法是含有左递归的，如果存在非终结符一个文法是含有左递归的，如果存在非终结符P P含有左递归的文法将使自上而下的分析陷入无限循环。含有左递归的文法将使自上而下的分析陷入无限循环。164.2.2左递归的消除、回溯的消除左递归的消除、回溯的消除n构造不带回溯的自上而下分析算法构造不带回溯的自上而下分析算法要消除文法

11、的左递归性要消除文法的左递归性克服回溯克服回溯174.2.2左递归的消除左递归的消除n直接消除见诸于产生式中的左递归：假定关于非终结符直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为的规则为PP | 其中其中不以不以P开头。开头。我们可以把我们可以把P的规则等价地改写为如下的非直接左递归形式：的规则等价地改写为如下的非直接左递归形式：P P P P | 左递归变右递归18n一般而言，假定一般而言，假定P关于的全部产生式是关于的全部产生式是PP 1|P 2|P m| 1| 2| n其中，每个其中，每个都不等于都不等于，每个，每个都不以都不以P开头开头那么，消除那么，消除P的直接

12、左递归性就是把这些规则改写成：的直接左递归性就是把这些规则改写成：P 1P | 2P | nP P 1P | 2P | mP | 左递归变右递归19n例例文法文法G(E):EET|TTT*F|FF(E)|i经消去直接左递归后变成：经消去直接左递归后变成：ETE E +TE | TFT T *FT | F(E)|i(4.2)PP 1|P 2|P m| 1| 2| nP 1P | 2P | nP P 1P | 2P | mP | 20n例如文法例如文法G(S):SQc|cQRb|bRSa|a(4.3)虽没有直接左递归，但虽没有直接左递归，但S、Q、R都是左递归的都是左递归的SQcRbcSabc一个

13、文法消除左递归的条件：一个文法消除左递归的条件：F不含以不含以为右部的产生式为右部的产生式F不含回路。不含回路。21n消除左递归的算法消除左递归的算法:1.把文法把文法G的所有非终结符按任一种顺序排列成的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序；按此顺序执行；执行；2.FORi:=1TOnDOBEGINFORj:=1TOi-1DO把形如把形如PiPj 的规则改写成的规则改写成Pi 1 | 2 | k ;(其中其中Pj 1| 2| k是关于是关于Pj的所有规则的所有规则)消除关于消除关于Pi规则的直接左递归性规则的直接左递归性END3.化简由化简由2所得的文法。去除那些从开始符

16、 (4.4)26n注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。样。但不难证明，它们都是等价的。n例如，若对文法例如，若对文法(4.3)的非终结符排序选为的非终结符排序选为S、Q、R，那么，最后所得的，那么，最后所得的无左递归文法是：无左递归文法是：SQc|cQRb|bRbcaR |caR |aR (4.5)R bcaR | n文法文法(4.4)和和(4.5)的等价性是显然的。的等价性是显然的。274.2.4消除回溯、提左因子消除回溯、提左因子n为了消除回溯就必须保证：对文法的任何非终

17、结符，当要它去匹配输入为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。务，并且此候选的工作结果应是确信无疑的。nA 1| 2| nSa.IPA.28n令令G是一个不含左递归的文法，对是一个不含左递归的文法，对G的所有非终结符的每个候选的所有非终结符的每个候选定义它的定义它的终结首符集终结首符集FIRST( )为：为：特别是，若特别是，若，则规定，则规定FIRST( )。如果非终结符如果非终结符A的所有候选首符集两

18、两不相交，即的所有候选首符集两两不相交，即A的任何两个不同候选的任何两个不同候选 i和和 jFIRST( i)FIRST( j) 当要求当要求A匹配输入串时，匹配输入串时，A就能根据它所面临的第一个输入符号就能根据它所面临的第一个输入符号a，准确地指派某，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含一个候选前去执行任务。这个候选就是那个终结首符集含a的的。29n提取公共左因子提取公共左因子:假定关于假定关于A的规则是的规则是A1|2|n| 1| 2| m(其中，每个其中，每个不以不以开开头头)那么，可以把这些规则改写成那么，可以把这些规则改写成A A | 1| 2| m

19、A 1| 2| nn经过反复提取左因子，就能够把每个非终结符经过反复提取左因子，就能够把每个非终结符(包括新引进者包括新引进者)的所有候选首的所有候选首符集变成为两两不相交。符集变成为两两不相交。30nETE E +TE | TFT T *FT | F(E)|ini+i4.2.4LL(1)分析条件分析条件31i + i IPEnG(E):ETE E +TE | TFT T *FT | F(E)|i32i + i IPETEnG(E):ETE E +TE | TFT T *FT | F(E)|i33i + i IPETEFTnG(E):ETE E +TE | TFT T *FT | F(E)|i

22、G的任何非终结符的任何非终结符A，我们定义，我们定义特别是，若特别是，若，则规定，则规定 FOLLOW(A)4.2.4LL(1)分析条件分析条件45n构造不带回溯的自上而下分析的文法条件构造不带回溯的自上而下分析的文法条件1. 文法不含左递归，文法不含左递归，2. 对于文法中每一个非终结符对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，的各个产生式的候选首符集两两不相交。即，若若A 1| 2| n 则则 FIRST( i)FIRST( j) (i j)3. 对文法中的每个非终结符对文法中的每个非终结符A，若它存在某个候选首符集包含，若它存在某个候选首符集包含，则，则FIR

23、ST( i)FOLLOW(A)= i=1,2,.,n如果一个文法如果一个文法G满足以上条件，则称该文法满足以上条件，则称该文法G为为LL(1)LL(1)文法文法。46n对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符分析。假设要用非终结符A进行匹配，面临的输入符号为进行匹配，面临的输入符号为a，A的所有产生式为的所有产生式为A 1| 2| n1.若若a FIRST( i)，则指派，则指派 i执行匹配任务；执行匹配任务；2.若若a不属于任何一个候选首符集，则：不属于任何一个候选首符集，则

24、：(1)若若属于某个属于某个FIRST( i)且且a FOLLOW(A)，则让则让A与与自动匹配。自动匹配。(2)否则，否则，a的出现是一种语法错误。的出现是一种语法错误。474.2.6构造构造FIRST( )若若*则规定则规定 FIRST( )直观上说文法符号串直观上说文法符号串的开始符号集是由的开始符号集是由推导出的开头的终结符推导出的开头的终结符（包括（包括）组成。）组成。 48例文法例文法GS:SApSBqAaAcABbBdBFIRST(Ap)=a,cFIRST(Bq)=b,dFIRST(a)=aFIRST(cA)=cFIRST(b)=bFIRST(dB)=d由于同一非终结符的

25、两个产生式的右部推导出来的开始符号集不相交，因此可根由于同一非终结符的两个产生式的右部推导出来的开始符号集不相交，因此可根据当前输入符属于哪个产生式右部的开始符号集而决定选哪个产生式进行推导，据当前输入符属于哪个产生式右部的开始符号集而决定选哪个产生式进行推导，可以进行确定的自顶向下分析可以进行确定的自顶向下分析49n对每一文法符号对每一文法符号X VTVN构造构造FIRST(X)连续使用下面的规则，直至每个集合连续使用下面的规则，直至每个集合FIRST不再增大为止：不再增大为止：1.若若X VT，则，则FIRST(X)X。2.若若X VN，且有产生式，且有产生式Xa，则把，则把a加入到加入到

26、FIRST(X)中；若中；若X 也是也是一条产生式，则把一条产生式，则把也加到也加到FIRST(X)中。中。503.l若若XY是一个产生式且是一个产生式且Y VN，则把，则把FIRST(Y)中的所有非中的所有非 -元素都加到元素都加到FIRST(X)中；中；l若若XY1Y2Yk是一个产生式，是一个产生式，Y1，Yi-1都是非终结符，而且，对于任都是非终结符，而且，对于任何何j，1 j i-1，FIRST(Yj)都含有都含有 (即即Y1Yi-1 )，则把则把FIRST(Yi)中的所有中的所有非非 -元素都加到元素都加到FIRST(X)中；特别是，若所有的中；特别是，若所有的FIRST(Yj)均

27、含有均含有，j1，2，k，则把，则把加到加到FIRST(X)中。中。51n对文法对文法G的任何符号串的任何符号串 =X1X2Xn构造集合构造集合FIRST( )。1.置置FIRST( )FIRST(X1) ；2.若对任何若对任何1 j i-1，FIRST(Xj)，则把，则把FIRST(Xi) 加至加至FIRST( )中；特别是，若所有的中；特别是，若所有的FIRST(Xj)均含有均含有，1 j n，则把，则把也加至也加至FIRST( )中。显然，若中。显然，若则则FIRST( ) 。52n例例4.6对于文法对于文法G(E)ETE E +TE | TFT T *FT | F(E)|i|

28、x构造每个非终结符的构造每个非终结符的FIRST：53x xi i(,i,x*,(,i,x+,(,i,xFirstFirst集集(3)(3)x xi i(,i,x*,(,i,x+,(,i,xFirstFirst集集(2)(2)x xi i (,i,x+,FirstFirst集集(1)(1)E E T TT TF Fi ix xE E*,(,i,xi ix x+,FirstFirst集集(0)(0)*, *, (,i,x544.2.6构造构造FOLLOW(A)若有若有S=*A，则规定，则规定# FOLLOW(A)（注：（注：#输入串输入串#，#做为输入串的结束符）做为输入串的结束符）直观上说直观

29、上说,非终结符非终结符A的后跟符号集是由句型中紧跟的后跟符号集是由句型中紧跟A后的那些终结符后的那些终结符（包括（包括#）组成。）组成。55例例文法文法GS:SaA|dAbAS|由由S=*S得得# FOLLOW(S)由由S=aA=abAS=abbASS=abbASaA=abbASdFOLLOW(S)=#,a,d由由S=*aA得得# FOLLOW(A)由由S=*abAS=*abAaA得得a FOLLOW(A)=*abAd得得d FOLLOW(A)FOLLOW(A)=#,a,d56n对于文法对于文法G的每个非终结符的每个非终结符A构造构造FOLLOW(A)的办法是，连续使用下面的的办法是，连续使用

30、下面的规则，直至每个规则，直至每个FOLLOW不再增大为止：不再增大为止：1.对于文法的开始符号对于文法的开始符号S，置于，置于FOLLOW(S)中；中；2.若若A B 是一个产生式，则把是一个产生式，则把FIRST( ) 加至加至FOLLOW(B)中；中；3.若若A B是一个产生式，或是一个产生式，或AB 是一个产生式而是一个产生式而 (即即FIRST( )，则把则把FOLLOW(A)加至加至FOLLOW(B)中。中。57n例例4.6对于文法对于文法G(E)ETE E +TE | TFT T *FT | F(E)|i|x构造每个非终结符的构造每个非终结符的FOLLOW集：集：58*,+,#,

31、)+,#,)+,#,)#,)#,)FollowFollow集集(2)(2) +,#,)#,)#,)FollowFollow集集(1)(1)E E T TT TF FE E*+#,)FollowFollow集集(0)(0)+,#,)*,+,#,)59n例例4.6对于文法对于文法G(E)ETE E +TE | TFT T *FT | F(E)|i构造每个非终结符的构造每个非终结符的FIRST和和FOLLOW集合：集合：FIRST(E)=(,iFIRST(E )=+, FIRST(T)=(,iFIRST(T )=*, FIRST(F)=(,iFOLLOW(E)=),#FOLLOW(E )=),#FO

32、LLOW(T)=+,),#FOLLOW(T )=+,),#FOLLOW(F)=*,+,),#604.2.7 预测分析程序预测分析程序一、预测分析程序工作原理一、预测分析程序工作原理nif(a FIRST( i)用用A i推导推导nelseif(a FOLLOW(A)用用A 推导推导nelse语法错误语法错误n预测分析程序或预测分析程序或LL(1)分析法：分析法：总控程序总控程序分析表分析表MA，a矩阵，矩阵，A VN，a VT是终结符或是终结符或，分析栈分析栈STACK用于存放文法符号用于存放文法符号61总控程序总控程序分析表分析表X#输入串输入串分析栈分析栈STACKa1a2.ai#预测分析

33、程序的工作图预测分析程序的工作图# Sa1a2.ai#分析开始时：分析开始时：输出流输出流62q总控程序根据现行栈顶符号总控程序根据现行栈顶符号X和当前输入符号和当前输入符号a，执行下列三种动作之一，执行下列三种动作之一:1. 若若Xa，则宣布分析成功，停止分析。，则宣布分析成功，停止分析。2. 若若Xa ，则把，则把X从从STACK栈顶逐出，让栈顶逐出，让a指向下一个输入符号。指向下一个输入符号。匹配成功633. 若若X是一个非终结符，则查看分析表是一个非终结符，则查看分析表M。若若MX，a中存放着关于中存放着关于X的一个产生式，把的一个产生式，把X逐出逐出STACK栈顶，栈顶，把把产生式

34、的右部符号串按反序一一推进产生式的右部符号串按反序一一推进STACK栈栈(若右部符号为若右部符号为，则，则意味不推什么东西进栈意味不推什么东西进栈)。在把产生式的右部符号推进栈的同时应做。在把产生式的右部符号推进栈的同时应做这个产生式相应的语义动作。这个产生式相应的语义动作。若若MX，a中存放着中存放着“出错标志出错标志”，则调用出错诊察程序，则调用出错诊察程序ERROR。推导64预测分析程序流程预测分析程序流程上托栈顶符放入上托栈顶符放入XNYYNNNN YY Y把把#和和文文法法开开始始符符压压入入分分析析栈栈；当前输入符送当前输入符送a把把产产生生式式右右部部反反序进栈序进栈XVT

35、?X=# ? X=a ?X=a?读读下下一一输输入入符到符到aMX,a有有产产生生式式？出错出错结束结束出错出错预测分析程序工作过程预测分析程序工作过程65n预测分析程序的总控程序：预测分析程序的总控程序：BEGIN首先把首先把然后把文法开始符号推进然后把文法开始符号推进STACK栈；栈；把第一个输入符号读进把第一个输入符号读进a；FLAG:=TRUE;WHILEFLAGDOBEGIN把把STACK栈顶符号上托出去并放在栈顶符号上托出去并放在X中；中；IFX VTTHENIFX=aTHEN把下一输入符号读进把下一输入符号读进aELSEERROR匹配成功66ELSEIFX=#THENIFX=aT

36、HENFLAG:=FALSEELSEERRORELSEIFMX,a=XX1X2XkTHEN把把Xk,Xk-1,X1一一推进一一推进STACK栈栈/*若若X1X2Xk= ，不推什么进栈，不推什么进栈*/ELSEERRORENDOFWHILE;STOP/*分析成功，过程完毕分析成功，过程完毕*/END分析成功推导67n例例4.6对于文法对于文法G(E)ETE E +TE | TFT T *FT | F(E)|i输入串为输入串为i1*i2+i3，利用分析表进行预测分析：，利用分析表进行预测分析：68步骤步骤符号栈符号栈输入串输入串所用产生式所用产生式0#Ei1*i2+i3#1#E Ti1*i2+i3

37、#ETE 2#E T Fi1*i2+i3#TFT 3#E T ii1*i2+i3# Fi69步骤步骤符号栈符号栈输入串输入串所用产生式所用产生式3#E T ii1*i2+i3# Fi4#E T *i2+i3#5#E T F* *i2+i3#T *FT 6#E T Fi2+i3#7#E T ii2+i3#Fi70步骤步骤符号栈符号栈输入串输入串所用产生所用产生7#E T ii2+i3#Fi8#E T +i3#9#E +i3#T 10#E T+i3#E +TE 11#E Ti3#71步骤步骤符号栈符号栈输入串输入串所用产生所用产生11#E Ti3#12#E T Fi3#TFT 13#E T ii3

38、#Fi14#E T #15#E # T 16# E 72二、分析表二、分析表MA，a的构造的构造q构造构造FIRST( )和和FOLLOW(A)q构造分析表构造分析表MA，a73n例例4.6对于文法对于文法G(E)ETE E +TE | TFT T *FT | F(E)|i构造每个非终结符的构造每个非终结符的FIRST和和FOLLOW集合：集合：FIRST(E)=(,iFIRST(E )=+, FIRST(T)=(,iFIRST(T )=*, FIRST(F)=(,iFOLLOW(E)=),#FOLLOW(E )=),#FOLLOW(T)=+,),#FOLLOW(T )=+,),#FOLLOW

39、(F)=*,+,),#74n在对文法在对文法G的每个非终结符的每个非终结符A及其任意候选及其任意候选都构造出都构造出FIRST( )和和FOLLOW(A)之后，现在可以用它们来构造之后，现在可以用它们来构造G的分析表的分析表MA，a。1.对文法对文法G的每个产生式的每个产生式A 执行第执行第2步和第步和第3步；步；2.对每个终结符对每个终结符a FIRST( )，把，把A 加至加至MA，a中；中；3.若若FIRST( )，则对任何，则对任何b FOLLOW(A)把把A 加至加至MA，b中。中。4.把所有无定义的把所有无定义的MA，a标上标上“出错标志出错标志”。7576n如果如果G是左递归或

40、二义的，那么，是左递归或二义的，那么，M至少含有一个多重定义入口。因此，至少含有一个多重定义入口。因此，消除左递归和提取左因子将有助于获得无多重定义的分析表消除左递归和提取左因子将有助于获得无多重定义的分析表M。n可以证明，一个文法可以证明，一个文法G的预测分析表的预测分析表M不含多重定义入口，当且仅当该文不含多重定义入口，当且仅当该文法为法为LL(1)的。的。77G(S):S iCtS | iCtSeS | aC b提取左因子之后，改写成：提取左因子之后，改写成：G(S):S iCtSS | aS eS | C b最近匹配原则 784.2.10递归下降分析递归下降分析程序构造程序构造n构造不

41、带回溯的自上而下分析程序构造不带回溯的自上而下分析程序要消除文法的左递归性要消除文法的左递归性克服回溯克服回溯79q实现思想：实现思想：对对文文法法中中的的每每个个非非终终结结符符编编写写一一个个递递归归过过程程，识识别别由由该该非非终终结结符符推推出出的的串串。当当非非终终结结符符有有多多条条产产生生式式时时，按按当当前前输输入入符符属属于于哪哪条条产产生生式式的的FIRST集或集或FOLLOW集（集（A ）可唯一确定选择哪个产生式进行匹配。）可唯一确定选择哪个产生式进行匹配。当识别到终结符时，与当前输入符号匹配，并读取下一输入符；当识别到终结符时，与当前输入符号匹配，并读取下一输入符；当识

42、别到非终结符时，则调用该非终结符相应的过程。当识别到非终结符时，则调用该非终结符相应的过程。80例例算术表达式文法算术表达式文法G:ETE E+TETFT T*FTF(E)i判断判断G是是LL(1)文法文法1判断是否可以应用递归子程序法判断是否可以应用递归子程序法812构造文法构造文法G的递归下降分析器的递归下降分析器定义：定义：当一个文法满足当一个文法满足LL(1)LL(1)条件时，就为它构造一个不带回溯的自顶向下的分析程条件时，就为它构造一个不带回溯的自顶向下的分析程序，这个分析程序由一组递归过程组成，每个过程对应文法的一个非终结符。序，这个分析程序由一组递归过程组成，每个过程对应文法的一

43、个非终结符。这样的一个分析程序称为递归下降分析器。这样的一个分析程序称为递归下降分析器。82组成：组成：递归下降分析器由一个主程序递归下降分析器由一个主程序MAINMAIN和每个非终结符对应的一个递归过程组成。和每个非终结符对应的一个递归过程组成。用到的一些子过程：用到的一些子过程：过程过程GETNEXTGETNEXT负责读入下一个负责读入下一个TOKENTOKEN字字过程过程ERRORERROR负责报告语法错误负责报告语法错误约定：约定：变量变量TOKENTOKEN存放已读入的存放已读入的TOKENTOKEN字字过程进入时变量过程进入时变量TOKENTOKEN存放了一个待匹配的存放了一个待匹

44、配的TOKENTOKEN字字退出过程时，变量退出过程时，变量TOKENTOKEN中仍存放着一个待匹配的中仍存放着一个待匹配的TOKENTOKEN字。字。 83非终结符相应的分析子程序的构造方法非终结符相应的分析子程序的构造方法1)对于每个非终结符对于每个非终结符U，编写一个相应的子程序，编写一个相应的子程序P(U);2)对于产生式对于产生式Ux1|x2|xn，x1,.xn都都关于关于U的子程序的子程序P(U)按如下方法构造：按如下方法构造：ifTOKENinfirst(x1)thenp(x1)elseifTOKENinfirst(x2)thenp(x2)else.ifTOKENinfirst(

45、xn)thenp(xn)elseERROR843)如果如果U还有空产生式还有空产生式U,则算法中的语句：则算法中的语句：ifTOKENinfirst(xn)thenp(xn)elseERROR改写为改写为ifTOKENinfirst(xn)thenp(xn)elseifTOKENnotinfollow(U)thenERROR4)对于符号串对于符号串x=y1y2yn；p(x)的含义为：的含义为：beginp(y1);p(y2);p(yn)end如果如果yi VN，则P(yi)就代表就代表调用用yi的子程序；的子程序；yi VT T，则P(yi)为形如下述形如下述语句的一段程句的一段程序序ifTO

46、KEN=yithenGETNEXT(TOKEN)elseERROR85(1) program MAIN; /* 主程序主程序 */ begin GETNEXT (TOKEN); E (TOKEN); /* 转匹配转匹配ETE */ if TOKEN # then ERROR end. 构造文法构造文法G：ETE E+TETFTT*FTF(E)i的递归下降分析器的递归下降分析器(2) procedure E (TOKEN); /*匹配匹配ETE*/ begin T (TOKEN); /*转匹配转匹配TFT*/ E (TOKEN) /*转匹配转匹配E+TE*/ end; 86(3) procedu

47、re E (TOKEN); /*匹配匹配E+TE*/ begin if TOKEN=+ then /*选择产生式选择产生式E+TE*/ begin GETNEXT (TOKEN);/*匹配匹配+,读下一个读下一个TOKEN字字*/ T (TOKEN); /*转匹配转匹配TFT*/ E (TOKEN) /*转匹配转匹配E+TE*/ end else /*E对应的语句对应的语句*/if TOKEN) and TOKEN# then ERROR end;87(5) procedure T (TOKEN); /* 匹配匹配T*FT */ begin if TOKEN = * then /* 选择产生式

48、选择产生式T*FT */ begin GETNEXT (TOKEN); /* 匹配匹配*，读下一，读下一TOKEN字字 */ F (TOKEN); /* 转匹配转匹配F(E)i */ T (TOKEN) /* 转匹配转匹配T*FT */ end else /* T对应的语句对应的语句*/if TOKEN+ and TOKEN) and TOKEN# then ERROR end;(4) procedure T (TOKEN); /*匹配匹配TFT*/ begin F (TOKEN); /*转匹配转匹配F(E)i*/ T (TOKEN) /*转匹配转匹配T*FT*/ end; 88(6) pro

49、cedure F (TOKEN); /* 匹配匹配F(E)i */ begin if TOKEN = ( then /*选择产生式选择产生式F(E) */ begin GETNEXT (TOKEN); /* 匹配匹配(，读下一，读下一TOKEN字字 */ E (TOKEN); /* 转匹配转匹配ETE */ if TOKEN=) then GETNEXT (TOKEN) /* 匹配匹配), 读下一读下一TOKEN字字 */ else ERROR end else /* 选择产生式选择产生式Fi */ if TOKEN=i then GETNEXT (TOKEN) else ERROR end;

50、 89说明：如果说明：如果i Vn，则，则P(i)就代表调用处理就代表调用处理i的子程序；如果的子程序；如果i Vt，则，则P(i)为形如下述语句的一段程序：为形如下述语句的一段程序：ifch=ithenREAD(ch)elseerror即如果当前文法中的符号与输入符号匹配，则继续读入输入符号串的下一即如果当前文法中的符号与输入符号匹配，则继续读入输入符号串的下一个符号到个符号到ch中，否则出错。中，否则出错。 90n例例设文法设文法GS:S (A)|aAbA eA|dSAA dA| 试构造该文试构造该文法的递归子程序法的递归子程序(或递归下降分析或递归下降分析程序程序)。解：由解：由S (

51、A)|aAb,则则P(S)为：为：c h = ( ?R E A D ( c h ) c h = a ?YNP ( A )c h = ) ?R E A D ( c h )YN e r r o rR E A D ( c h )YNe r r o rP ( A )c h = b ?R E A D ( c h )YN e r r o r91由由A eA|dSA,则则P(A)为：为：n例例设文法设文法GS:S (A)|aAbA eA|dSAA dA| 试构造该文试构造该文法的递归子程序法的递归子程序(或递归下降分析或递归下降分析程序程序)。c h = e ?R E A D ( c h ) c h =

52、d ?YNR E A D ( c h )YNe r r o rP ( S )P ( A) )92由由A dA| ，则则P(A)为：为：n例例设文法设文法GS:S (A)|aAbA eA|dSAA dA| 试构造该文试构造该文法的递归子程序法的递归子程序(或递归下降分析或递归下降分析程序程序)。c h = d ?R E A D (c h ) c h F O L L O W (A) )?YNYNe r r o rP (A) )93特点：特点：优点：简单直观、易于构造优点：简单直观、易于构造缺点：缺点：对文法要求高，必须满足对文法要求高，必须满足LL(1)文法；文法；递归调用多，速度慢，占用空间多递归调用多，速度慢，占用空间多实用性：许多高级语言，如实用性：许多高级语言，如Pascal、c等编译系统常常采用此方法。等编译系统常常采用此方法。94

展开阅读全文

编译技术语法分析11ppt课件

最新文档