资源描述
第第5 5章章 自顶向下的语法分析方法自顶向下的语法分析方法任务：任务：根据文法规则，从源程序单词符号串中识别出语法根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查。成分，并进行语法检查。两大类分析方法：两大类分析方法：自顶向下分析自顶向下分析自底向上分析自底向上分析语法分析的任务语法分析的任务自顶向下分析法也就是从文法的开始符号出自顶向下分析法也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能句子，若输入串是给定文法的句子，则必能推出，反之必然出错。推出，反之必然出错。回顾在“文法和语言”一章中介绍的关于句子、句型和语言的定义及什么叫最左推导、最右推导和规范推导的基本概念。句型、句子、语言的定义句型、句子、语言的定义 句型:有文法G S，若S x，且xV*则称x是文法G S的句型。符号 表示经过0步或若干步的推导。句子:有文法GS，若S x，且x VT*,则称x是文法G S的句子。例：GS：S0S1，S01可有推导 S 0S1 00S11 000S111 00001111说明00001111是GS的句子。*=*=*=句型的分析句型的分析 句型分析句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。最左（最右）推导最左（最右）推导：在推导的任何一步 ，都是对中的最左（右）非终结符进行替换。最右推导被称为规范推导。最右推导被称为规范推导。由规范推导所得的句型称为规范句型。由规范推导所得的句型称为规范句型。句型分析的有关问题句型分析的有关问题 如何选择使用哪个产生式进行推导？如何选择使用哪个产生式进行推导？假定要被替换的最左非终结符号是V，且左部为V的规则有n条：VA1|A2|An，那么如何确定用哪个右部去替换V呢？如何识别可归约的串？如何识别可归约的串？在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中寻找一个子串，看它是否能归约到文法的某个非终结符号，该子串称为“可归约串”。【例例】=acbGS:SaAbAcd|c 分析过程是设法建立一分析过程是设法建立一棵语法树棵语法树,使语法树的末端结使语法树的末端结点与给定符号串相匹配点与给定符号串相匹配.1.开始开始:令令S为根结点为根结点 S2.用用S的右部的右部,符号串去匹配输入串符号串去匹配输入串 SaAb完成一步推导完成一步推导SaAb 检查检查 a-a匹配匹配 A是非终结符是非终结符,将匹配任务交给将匹配任务交给A3.选用选用A的右部符号串匹配输入串的右部符号串匹配输入串 A有两个右部有两个右部,选第一个选第一个 aAbcdS完成进一步推导完成进一步推导Acd 检查检查,c-c匹配匹配,b-d不匹配不匹配(失败失败)但是还不能冒然宣布但是还不能冒然宣布 L(GS)4.回溯回溯 即砍掉即砍掉A的子树的子树 改选改选A的第二右部的第二右部SaAbcAc 检查检查 c-c匹配匹配 b-b匹配匹配建立语法树建立语法树,末端结点为末端结点为acb与输入与输入acb相匹配相匹配,建立了推导序列建立了推导序列 SaAbacbacb L(GS)=acbGS:SaAbAcd|c自顶向下分析方法分类自顶向下分析方法分类确定的确定的不确定的不确定的回溯回溯是否所有的文法都能采用确定的自上而下的分析是否所有的文法都能采用确定的自上而下的分析该文法的特点是：该文法的特点是：关于关于A A的产生式的不同右部开始符号集合都含有的产生式的不同右部开始符号集合都含有a a，因此要替换，因此要替换非终结符非终结符A A时，对当前输入符为时，对当前输入符为a a的情况，不能确定用产生式的情况，不能确定用产生式AabAab 的右部还是用的右部还是用AaAa的右部去替换。所以导致必须用带回溯的自顶向的右部去替换。所以导致必须用带回溯的自顶向下分析下分析，这是一个不确定的分析这是一个不确定的分析文法含有左递归，可见一个文法含有左递归时不能用确定的自顶向文法含有左递归，可见一个文法含有左递归时不能用确定的自顶向下分析下分析文法含有左递归，一个文法含有左递归时不能用确定的自顶向文法含有左递归，一个文法含有左递归时不能用确定的自顶向下分析。由以上例子可以看出，例下分析。由以上例子可以看出，例5.45.4例例5.65.6的文法不能用确的文法不能用确定的自顶向下分析定的自顶向下分析,可用带回溯的自顶向下分析。可用带回溯的自顶向下分析。回溯问题回溯问题什么是回溯（什么是回溯（backtracking）?分析工作要部分地或全部地退回去重做叫分析工作要部分地或全部地退回去重做叫回溯回溯造成回溯的条件：造成回溯的条件：文法中，对于某个非终结符号的文法中，对于某个非终结符号的规则其右部规则其右部有多个选择有多个选择，并根据所面临的输入符号不能准确并根据所面临的输入符号不能准确的确定所要选择时，就可能出现回溯。的确定所要选择时，就可能出现回溯。回溯带来的问题：回溯带来的问题：严重的严重的低效率低效率，只有在理论上的意义而无实际意义，只有在理论上的意义而无实际意义5.1 确定的自顶向下分析思想确定的自顶向下分析思想 确定的自顶向下分析方法:首先要解决从某文法的开始符号出发，对给定的输入符号串如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导.例5.1若有文法G1S:SpA|qBAcAd|aBdB|c识别输入串w=pccadd是否是G1S的句子试探推导过程：SpApcAdpccAddpccadd试探成功。这个文法有以下两个特点这个文法有以下两个特点：每个产生式的右部都由终结符号开始。如果两个产生式有相同的左部，那么它们的右部由不同的右部由不同的 终结符开始。即每个产生式的右部的开始终结符不同。终结符开始。即每个产生式的右部的开始终结符不同。对于这样的文法显然在推导过程中完全可以根据当前的输入符号决对于这样的文法显然在推导过程中完全可以根据当前的输入符号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。定选择哪个产生式往下推导，因此分析过程是唯一确定的。例5.2若有文法G2S:SAp|BqAa|cABb|dB识别输入串w=ccap是否是G2S的句子，那么试探推出输入串的推导过程为：SApcApccApccap试探推导成功。文法的特点是：文法的特点是：产生式的右部不全是由终结符开始。如果两个产生式有相同的左部，它们的右部是由不同的 终结 符或非终结符开始。文法中无空产生式。对于产生式中相同左部含有非终结符开始的产生式时，在对于产生式中相同左部含有非终结符开始的产生式时，在推导过程中选用哪个产生式不像例推导过程中选用哪个产生式不像例5.15.1文法那样直观，对文法那样直观，对于于 W=W=ccapccap 为输入串时，其第一个符号是为输入串时，其第一个符号是c c，这时从，这时从S S出发出发选择选择 SApSAp 还是选择还是选择 SBqSBq，需要知道，需要知道，ApAp或或BqBq它们的它们的开始终结符号集合开始终结符号集合是什么？是什么？因为因为c c是包含在是包含在ApAp的的开始终结符号集合中开始终结符号集合中，且不包含在，且不包含在BqBq的的开始终结符号集合中开始终结符号集合中，则选择，则选择 SApSAp 往下进行推导。往下进行推导。SAp|BqAa|cABb|dB 定义定义5.15.1 设设G=(VG=(VT T，V VN N，S S，P)P)是上下文无关文法是上下文无关文法FIRST(FIRST()=)=a|a|a,aVa,aVT T，,V,V*若若 ,则规定则规定FIRST(FIRST()G2：SAp|BqAa|cABb|dB不难求出在例5.2文法G2中FIRST(S Ap)=FIRST(Ap)=a,cFIRST(FIRST(S Bq)=)=FIRST(Bq)=b,d因此有 FIRST(Ap)(FIRST(Bq)=这样文法这样文法G G中，两个产生式有相同的左部，它们中，两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。的右部是由不同的终结符或非终结符开始。它们它们右部的符号串可能推导出的右部的符号串可能推导出的FirstFirst集不相交，集不相交，因因而可以根据当前的输入符号是属于哪个产生式的而可以根据当前的输入符号是属于哪个产生式的FIRSTFIRST集而决定选择相应产生式进行推导，因此集而决定选择相应产生式进行推导，因此仍能构造确定的自顶向下分析。仍能构造确定的自顶向下分析。W=W=ccapccap 为输入为输入串时，其第一个符号是串时，其第一个符号是c c，这时从，这时从S S出发选择出发选择 SApSAp 还是选择还是选择 SBqSBq，因为，因为c c属于属于SAp的的FIRST集，所以选择集，所以选择SAp推导。推导。对于文法对于文法G的所有非终结符的每个候选式的所有非终结符的每个候选式，其终结首符，其终结首符号集称为号集称为FIRST集，定义如下：集，定义如下：例5.3若有文法G3S:S aA|dA bAS|识别输入串w=abd是否是G3S的句子试探推导出abd的推导过程为：SaAabASabSabd试探推导成功。文法的特点是：文法的特点是：文法中含有空产生式。从以上推导过程中我们可以看到在第2步到第3步的推导中，因当前面临输入符号为因当前面临输入符号为d d，而最左非终结符，而最左非终结符A A的产生式右部的开始符号集合都不包含的产生式右部的开始符号集合都不包含d d，但有，但有，因此对于因此对于d d 的的匹配自然认为匹配自然认为只能依赖于在可能的推导过程中只能依赖于在可能的推导过程中A A的后面的符号，所的后面的符号，所以这时选用产生式以这时选用产生式AA往下推导，而往下推导，而当前当前A A后面的符号为后面的符号为S S，S S产生产生式右部的开始的终结符号集合包含了式右部的开始的终结符号集合包含了d d，所以可匹配。，所以可匹配。一个文法非终结符的后跟符号的集合如下：定义定义5.25.2：设设 G=(VT，VN，S，P)是上下文无关是上下文无关 文法，文法，AVN，S是开始符号是开始符号 FOLLOW(A)=a|S A,且且aVT，aFIRST(),VT*,V+若若S A,且且 ,则则#FOLLOW(A)。也可定义为：也可定义为：FOLLOW(A)=a|S Aa,a VT若有若有S A，则规定则规定#FOLLOW(A)这里我们用这里我们用#作为输入串的结束符，或称为句子括号，作为输入串的结束符，或称为句子括号，如：如：#输入串输入串#。因此当文法中含有形如：AA的产生式时，其中AVN，,V*，当,不同时推导出空时,设,则当FIRST()(FIRST()FOLLOW(A)=时，对于非终结符A的替换仍可唯一地确定候选。综合以上情况可定义选择集合综合以上情况可定义选择集合SELECTSELECT如下：如下：定义定义5.3 5.3 给定上下文无关文法的产生式给定上下文无关文法的产生式A,AVN,V*,若若 ,则则SELECT(A)=FIRST()如果如果 则则：SELECT(A)=（FIRST()）FOLLOW(A)n定义定义5.45.4 一个上下文无关文法是LL(1)文法的充分必要条件是：对每个非终结符A的两个不同产生式，A,A,满足SELECT(A)SELECT(A)=其中，不同时能 LL(1)文法的定义文法的定义LL(1)文法的含义：第一个L 从左到右扫描输入串 第二个L 生成的是最左推导 1 向右看一个输入符号便可 决定选择哪个产生式。LL(1)LL(1)文法的判别文法的判别 当我们需选用自顶向下分析技术时，首先必须判别所给文法是否是LL(1)文法。因而我们对任给文法需计算FIRST、FOLLOW、SELECT集合，进而判别文法是否为LL(1)文法。根据定义计算根据定义计算FIRST(X)对每一文法符号对每一文法符号XV XV 计算计算FIRST(X)FIRST(X)1.1.若若XVXVT T，则，则FIRST(X)FIRST(X)XX。2.2.若若XVXVN N，且有产生式，且有产生式XaXa，aVaVT T，则则 aFIRST(XaFIRST(X)XX,则则FIRST(XFIRST(X)。3.X3.XY Y是一个产生式且是一个产生式且Y Y V VN N 则把则把FIRST(Y)FIRST(Y)中的所有非中的所有非 元素都加入到元素都加入到FIRST(X)FIRST(X)中中4 4、若、若XVXVN N；Y1Y1，Y2Y2，YiVYiVN N，且有产生式，且有产生式XY1 Y2 XY1 Y2 YnYn；当当Y1 Y2 Y1 Y2 Yn-1 Yn-1都都 时，则时，则FIRST(Y1)FIRST(Y1)、FIRST(Y2)FIRST(Y2)、FIRST(Yn-1)FIRST(Yn-1)的所有非空元素和的所有非空元素和FIRST(YnFIRST(Yn)都包含在都包含在FIRST(X)FIRST(X)中。中。即即:FIRST(X)=(FIRST(Y1):FIRST(X)=(FIRST(Y1)）（FIRST(Y2)FIRST(Y2)）（FIRST(Yn-FIRST(Yn-1 1)）FIRST(YnFIRST(Yn)5 5、当、当(4)(4)中所有中所有Yi Yi ,(i,(i=1,2,=1,2,n)n)，则，则FIRST(X)=(FIRST(Y1)FIRST(X)=(FIRST(Y1)）（FIRST(Y2)FIRST(Y2)（FIRST(YnFIRST(Yn)）反复使用上述反复使用上述(2)(5)步直到每个符号的步直到每个符号的FIRST集合不再增大为止。集合不再增大为止。例文法GS为：SABSbCAAbBBaDCADCbDaSDc求每个非终结符的求每个非终结符的First集。集。例文法GS为：SABSbCAAbBBaDCADCbDaSDcFIRST(S)=FIRST(A)FIRST(B)b=b,a,FIRST(A)=b=b,FIRST(B)aa,FIRST(C)=FIRST(A)FIRST(D)FIRST(b)=b,a,cFIRST(D)=ac=a,c也可以由关系图法求文法符号的FIRST集，可作为一种验证。其方法为：(a)每个文法符号对应图中一个结点，对应终结符的结点时用符号本身标记，对应非终结符的结点用FIRST(A)标记。这里A表示非终结符。(b)如果文法中有产生式AX，且 ,则从对应A的结点到对应X的结点连一条箭弧。(c)凡是从FIRST(A)结点有路径可到达的终结符结点所标记的终结符都为FIRST(A)的成员。(d)由是否为某非终结符FIRST集的成员，若是则将加入该非终结符的FIRST集中。文法GS为：SABSbCAAbBBaDCADCbDaSDcFIRST(S)=b,a,FIRST(A)=b,FIRST(B)=a,FIRST(C)=a,b,cFIRST(D)=a,c根据定义计算根据定义计算对文法中每一 AVN 计算 FOLLOW(A)(a)设S为文法中开始符号，把#加入FOLLOW(S)中(这里“#”为句子括号)。(b)若AB是一个产生式，则把FIRST()的非空元素加入 FOLLOW(B)中。如果 则把FOLLOW(A)也加入FOLLOW(B)中。(c)反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。计算计算FOLLOW集集【例例】GE GEETEE+TE|TFTT*FT|F(E)|i求求FOLLOWFOLLOW(E)=#,)E是开始符号是开始符号#FOLLOW(E)又又F(E)FOLLOW(E)FOLLOW(E)=#,)E TE FOLLOW(E)加入加入 FOLLOW(E)FOLLOW(T)=+,),#E +TE FIRST(E)-加入加入FOLLOW(T)又又E，FOLLOW(E)加入加入FOLLOW(T)FOLLOW(T)=FOLLOW(T)=+,),#T FT FOLLOW(T)加入加入FOLLOW(T)FOLLOW(F)=*,+,),#T FT FOLLOW(F)=FIRST（T）-又又T FOLLOW(T)加入加入FOLLOW(F)FIRST(F)=(,iFIRST(T)=*,FIRST(T)=(,iFIRST(E)=+,FIRST(E)=(,i例：文法GS为：SABSbCAAbBBaDCADCbDaSDc求每个非终结符的求每个非终结符的Follow集。集。解：FOLLOW(S)=#FOLLOW(D)#FOLLOW(A)=(FIRST(B)FOLLOW(S)FIRST(D)a,#,cFOLLOW(B)=FOLLOW(S)=#FOLLOW(C)=FOLLOW(S)=#FOLLOW(D)=#判断它是否是判断它是否是LL(1)文法文法文法GS为：SABSbCAAbBBaDCADCbDaSDc每个产生式的SELECT集合计算为：SELECT(SAB)=（FIRST(AB)-)FOLLOW(S)=b,a,#SELECT(SbC)=FIRST(bC)=bSELECT(A)=(FIRST()-)FOLLOW(A)=a,c,#SELECT(Ab)=FIRST(b)=bSELECT(B)=(FIRST()-)FOLLOW(B)=#SELECT(BaD)=FIRST(aD)=aSELECT(CAD)=FIRST(AD)=a,b,cSELECT(Cb)=FIRST(b)=bSELECT(DaS)=FIRST(aS)=aSELECT(Dc)=FIRST(c)=c文法GS为：SABSbCAAbBBaDCADCbDaSDcSELECT(ASELECT(A)=)=FIRST(FIRST()(不能推出不能推出)或或 SELECT(ASELECT(A)=)=（FIRST(FIRST()）FOLLOW(A)FOLLOW(A)()由以上计算结果可得相同左部产生式的由以上计算结果可得相同左部产生式的SELECTSELECT交集为：交集为：SELECT(SAB)SELECT(SbC)=b,a,#b=bSELECT(A)SELECT(Ab)=a,c,#b=SELECT(B)SELECT(BaD)=#a=SELECT(CAD)SELECT(Cb)b,a,cbbSELECT(DaS)SELECT(Dc)=ac由由LL(1)LL(1)文法定义知该文法不是文法定义知该文法不是LL(1)LL(1)文法，因为具有相同左部其产文法，因为具有相同左部其产生式的生式的SELECTSELECT集的交集不为空。集的交集不为空。非非LL(1)LL(1)文法到文法到LL(1)LL(1)文法的等价转换文法的等价转换由前面可知：确定的自顶向下分析要求对给定语言的文法必须是LL(1)形式。然而，不一定每个语言都有LL(1)文法。对一个语言的非LL(1)文法是否能变换为等价的LL(1)形式以及如何变换是本节讨论的主要问题。例：判断下列文法是否是LL(1)文法G：SaA Sd AbAS A解：select(SaA)=a select(S d)=d select(SaA)select(S d)=select(AbAS)=b select(A)=First()-Follow(A)=Follow(A)=a,d,#select(AbAS)select(A )=所以，该文法所以，该文法是是LL（1）文）文法。法。例：判断下列文法是否是LL(1)文法文法GS为：SaASSbAbAA例例 文法文法G SG S为：为：SaASSaASSbSbAbAAbAAA则则 SELECT(SaASSELECT(SaAS)=a)=aSELECT(SbSELECT(Sb)=b)=bSELECT(AbASELECT(AbA)=b)=bSELECT(ASELECT(A)=)=a,ba,b 所以所以 SELECT(SaAS)SELECT(SbSELECT(SaAS)SELECT(Sb)=)=abab=SELECT(AbA)SELECT(ASELECT(AbA)SELECT(A)=)=ba,bba,b 因此，该文法不是因此，该文法不是LL(1)LL(1)文法，因而也就不可能用确定的自顶向文法，因而也就不可能用确定的自顶向 下分析。下分析。5.2 LL(1)文法的定义和判别文法的定义和判别一个文法是否是一个文法是否是LLLL（1 1）文法，与产生式的）文法，与产生式的SelectSelect集有关。集有关。一个上下文无关文法是LL(1)文法的充分必要条件是：对每个非终结符A的两个不同产生式，A,A,满足SELECT(A)SELECT(A)=其中，不同时能推出。若文法中含有直接或间接左递归，或含有左公共因子则该若文法中含有直接或间接左递归，或含有左公共因子则该文法肯定不是文法肯定不是LL(1)文法。因而，我们设法消除文法中的左文法。因而，我们设法消除文法中的左递归，提取左公共因子对文法进行等价变换，在某些特殊递归，提取左公共因子对文法进行等价变换，在某些特殊情况下可能使其变为情况下可能使其变为LL(1)文法。文法。1提取左公共因子提取左公共因子若文法中含有形如：若文法中含有形如：A|的产生式，这导致了对相的产生式，这导致了对相同左部的产生式其右部的同左部的产生式其右部的SELECT集相交，也就是集相交，也就是SELECT(A)SELECT(A)，不满足不满足LL(1)文文法的充分必要条件。法的充分必要条件。现将产生式现将产生式A|进行等价变换为：进行等价变换为：A（|）使产生式变换为：使产生式变换为：AAA|写成一般形式为：写成一般形式为：A1|2|n，提取左公共因子后变为：，提取左公共因子后变为：A（1|2|n），再引进非终结符），再引进非终结符A，变为：，变为：AAA1|2|n若在若在i、j、k (其中其中1i，j，kn)中仍含有左中仍含有左公共因子，这时可再次提取，这样反复进行提取直到公共因子，这时可再次提取，这样反复进行提取直到引进新非终结符的有关产生式再无左公共因子为止。引进新非终结符的有关产生式再无左公共因子为止。例1：若文法G的产生式为：(1)SaSb(2)SaS(3)S请提取文法中的左公因子对产生式对产生式(1)、(2)提取左公因子后得：提取左公因子后得：S aS(b|)S进一步变换为文法进一步变换为文法G：SaSAAbASSelect(A b)Select(A)=b Follow(A)=b Follow(S)=b (First(A)-)#)=b (b#)不是不是LL(1)文法文法因此文法中不含左公共因子只因此文法中不含左公共因子只是是LL(1)文法的必要条件。文法的必要条件。例例2：若文法：若文法G的产生式为：的产生式为：(1)Aad(2)ABc(3)BaA(4)BbB请提取文法中的隐式左公因子。请提取文法中的隐式左公因子。产生式产生式(2)的右部以非终结符开始，因此左公共因子可的右部以非终结符开始，因此左公共因子可能是隐式的，所以这种情况下能是隐式的，所以这种情况下,对文法对文法G2分别用分别用(3)、(4)的右部替换的右部替换(2)中的中的B，可得：，可得：(1)Aad(2)AaAc(3)AbBc(4)BaA(5)BbBAa(d|Ac)AbBcBaABbB提取公因子引进新非终结符引进新非终结符A，去掉，去掉(，)后后得得G为：为：(1)AaA(2)AbBc(3)Ad(4)AAc(5)BaA(6)BbB而文法例而文法例2中的中的G变成变成LL(1)文法文法.值得注意的是对文法进行提取左公共因子变换后，有值得注意的是对文法进行提取左公共因子变换后，有时会使某些产生式变成无用产生式，在这种情况下必时会使某些产生式变成无用产生式，在这种情况下必须对文法重新压缩须对文法重新压缩(或化简）或化简）例3：若有文法G的产生式为：(1)SaSd(2)SAc(3)AaS(4)Ab用产生式(3)、(4)中右部替换产生式(2)中右部的A，文法变为：(1)SaSd(2)SaSc(3)Sbc(4)AaS(5)Ab对(1)、(2)提取左公共因子得：SaS(d|c)引入新非终结符A后变为：(1)SaSA(2)Sbc(3)Ad|c(4)AaS(5)Ab显然，原文法G3中非终结符A变成不可到达的符号，产生式(4)、(5)也就变为无用产生式，所以应删除。此外也存在某些文法不能在有限步骤内提取完左公共因子。此外也存在某些文法不能在有限步骤内提取完左公共因子。例：若有文法G4的产生式为：(1)SAp|Bq(2)AaAp|d(3)BaBq|e用(2)、(3)产生式的右部替换(1)中产生式的A、B使文法变为：(1)SaApp|aBqq(2)Sdp|eq(3)AaAp|d(4)BaBq|e对(1)提取左公共因子则得：Sa(App|Bqq)再引入新非终符S结果得等价文法为：(1)SaS(2)Sdp|eq(3)SApp|Bqq(4)AaAp|d(5)BaBq|e同样分别用(4)、(5)产生式的右部替换(3)中右部的A、B再提取左公共因子最后结果得：(1)SaS (2)Sdp|eq (3)SaS(4)Sdpp|eqq (5)SAppp|Bqqq(6)AaAp|d (7)BaBq|e有些文法可有些文法可能能不能在有限步不能在有限步骤内骤内完全提取左公共因子。完全提取左公共因子。由上面所举例子可以说明以下问题：由上面所举例子可以说明以下问题：不一定每个文法的左公共因子都能在有限的步骤内不一定每个文法的左公共因子都能在有限的步骤内 替换成无左公共因子的文法，上面文法替换成无左公共因子的文法，上面文法G4就是如就是如 此此.一个文法提取了左公共因子后，只解决了相同左部一个文法提取了左公共因子后，只解决了相同左部 产生式右部的产生式右部的FIRST集不相交问题，当改写后的文集不相交问题，当改写后的文 法不含空产生式，且无左递归时，则改写后的文法法不含空产生式，且无左递归时，则改写后的文法 是是LL(1)文法，否则还需用文法，否则还需用LL(1)文法的判别方式进文法的判别方式进 行判断才能确定是否为行判断才能确定是否为LL(1)文法。文法。2.2.消除左递归消除左递归设一个文法含有下列形式的产生式。设一个文法含有下列形式的产生式。1)AA AV1)AA AVN N，VV*2)AB2)AB BABA A,BVN,A,BVN,V,V*可称含可称含1)1)中产生式的文法为含有中产生式的文法为含有直接左递归直接左递归。含。含2)2)中产生式中产生式的文法有的文法有A A A A 则称文法中含有则称文法中含有间接左递归间接左递归，文法中只，文法中只要含有要含有1)1)或含有或含有2)2)的产生式或二者皆有，均认为文法是左递的产生式或二者皆有，均认为文法是左递归的，然而，一个文法是左递归时不能采用确定的自顶向下归的，然而，一个文法是左递归时不能采用确定的自顶向下分析法。分析法。a)a)消除直接左递归，把直接左递归改写为右递归，如对文法消除直接左递归，把直接左递归改写为右递归，如对文法 G G：SSaSSa SbSb一般情况下，假定关于一般情况下，假定关于A A的全部产生式是：的全部产生式是：AA1|A2|Am|1|2|n其中，i(1im)不等于,j(1jn)不以A开头，消除直接左递归后改写为：消除直接左递归后改写为：AA1 1 A|A|2 2 A|A|n n A AAA1 1 A|A|2 2 A|A|m m A|A|可改写为：可改写为：SbSSbS SaS|SaS|b)b)消除间接左递归。消除间接左递归。对于间接左递归的消除需先将间接左递归变为直接左对于间接左递归的消除需先将间接左递归变为直接左递归，然后再按递归，然后再按a)a)消除直接左递归。消除直接左递归。例：文法G为例：(1)AaB(2)ABb(3)BAc(4)Bd用产生式(1)、(2)的右部代替产生式(3)中的非终结符A得到左部为B的产生式为：(1)BaBc(2)BBbc(3)Bd消除左递归后得：B(aBc|d)BBbcB|再把原来其余的产生式AaBABb加入，最终文法为：(1)AaB(2)ABb(3)B(aBc|d)B(4)BbcB|可以检验改写后的文法不是LL(1)文法。例：文法：E E+T|T T T*F|F F(E)|i 试消除它的左递归E TEE+TE|T FTT*FT|F(E)|ic)c)消除文法中一切左递归的算法。消除文法中一切左递归的算法。步骤步骤(P89(P89 P90 P90 算法步骤）算法步骤）1)把文法的所有非终结符按某一顺序排序；把文法的所有非终结符按某一顺序排序；如如A A1 1，A A2 2,A,An n 2)A12)A1产生式右部用产生式右部用A2A2，,An,An表示，表示，A2A2产生式右部用产生式右部用A3A3，,An,An表示，表示，A3A3产生式右部用产生式右部用A4A4，,An,An表示，表示，,An An产生式右部用产生式右部用AnAn表示。消除表示。消除AnAn中的直接中的直接 左递归。左递归。3)3)去掉无用产生式。去掉无用产生式。例如，有文法的产生式为：例如，有文法的产生式为：(1)(1)SQc|cSQc|c(2)(2)QRb|bQRb|b(3)(3)RSa|aRSa|a该文法为间接左递归，按上述方法消除该文法的一切左递归。该文法为间接左递归，按上述方法消除该文法的一切左递归。若非终结符排若非终结符排序为序为S S、Q Q、R.R.(1)(1)号产生式左部为号产生式左部为S S的产生式是用后面的符号表示，不用修改的产生式是用后面的符号表示，不用修改 (2)(2)号产生式中右部是用后面的符号表示，不用修改号产生式中右部是用后面的符号表示，不用修改 (3)(3)号产生式中号产生式中R R是用前面的是用前面的S S表示，表示，所以把所以把(1)(1)右部代入右部代入(3)(3)得：得：(4)(4)RQca|ca|aRQca|ca|a 再将再将(2)(2)的右部代入的右部代入(4)(4)得：得：(5)(5)RRbca|bca|ca|aRRbca|bca|ca|a对对(5)(5)消除直接左递归得：消除直接左递归得：R(bca|ca|a)RR(bca|ca|a)RRbcaR|RbcaR|最终文法变为：SQc|cQRb|bR(bca|ca|a)RRbcaR|若非终结符的排序为若非终结符的排序为R R、Q Q、S,S,第（第（3 3）个产生式不用修改）个产生式不用修改 第（第（2 2）Q Q用用R R表示，需修改，把表示，需修改，把(3)(3)代入代入(2)(2)得：得：(1)SQc|c(2)QRb|b(3)RSa|a QSab|ab|b.(4)第（第（1 1）个产生式中，）个产生式中，S S用用Q Q表示，则需修改。表示，则需修改。(4)(4)代入（代入（1 1）得：得：SSabc|abc|bc|c消除该产生式的左递归后，最终文法变为：消除该产生式的左递归后，最终文法变为：S(abc|bc|c)SSabcS|QRb|bRSa|a由于由于Q Q、R R为不可到达的非终结符，所以以为不可到达的非终结符，所以以Q Q、R R为左部及包含为左部及包含Q Q、R R的产生式应删的产生式应删除。除。当非终结符的排序不同时，最后结果的产生式形式不同，但它们是等价的。当非终结符的排序不同时，最后结果的产生式形式不同，但它们是等价的。把上述算法归结为：把上述算法归结为：若非终结符的排序为若非终结符的排序为A A1 1，A A2 2，A An n。for(i=1;i=n;i+)for(i=1;i=n;i+)for(j=1;j=i-1;j+)for(j=1;jTEE-+TE|T-FTT-*FT|F-(E)|ii+*()#ETETEE+TE TFTFT T *FT Fi(E)第1列为非终结符第1行为终结符+#每个元素为产生式或空矩阵中的元素如何填?例例:S pA|qBA cAd|aB d B|c识别输入串识别输入串w=pccadd是否是是否是G1S的句子的句子?SpApcAdpccAddpccaddAaA A A遇到输入符遇到输入符a a，选用哪个产生式，选用哪个产生式?即是即是:如果如果a a select(Aselect(A )则把则把A A 加入到加入到M(A,a)M(A,a)中。中。解：解：(1)判断它是否是判断它是否是LL（1）文法因为该文法含有左）文法因为该文法含有左递归，所以不是递归，所以不是LL（1）文法，必须改写成）文法，必须改写成LL(1)文文法：法：G E:(1)E TE (2)E +TE (3)E (4)T FT (5)T *FT (6)T (7)F (E)(8)F i 例：为文法例：为文法G(E):G(E):E E E+T|T E+T|T T T T T*F|FF|F F F i|(Ei|(E)构造预测分析表。构造预测分析表。每个产生式的每个产生式的SelectSelect集：集：Select(E TE)=First(T)=First(F)=i,(Select(E +TE)=+Select(E )=Follow(E)=Follow(E)=#,)Select(T FT)=First(F)=(,iSelect(T *FT)=*Select(T )=Follow(T)=Follow(T)=(First（E)-)Follow(E)=(First（E)-)Follow(E)=+,#,)Select(F (E)=(Select(F i)=iG E:(1)E TE (2)E +TE (3)E (4)T FT (5)T *FT (6)T (7)F (E)(8)F i i+*()#EETT F TE TE +TE FT FT *FT i(E)SELECT(SELECT(ETEETE )=)=(,i(,i SELECT(SELECT(E E+TE+TE)=)=+SELECT(SELECT(E E)=)=),#),#SELECT(SELECT(TFTTFT)=)=(,i(,i SELECT(SELECT(T T*FTFT)=)=*SELECT(SELECT(T T)=)=+,),#+,),#SELECT(SELECT(F(E)F(E)=)=(SELECT(SELECT(FiFi)=)=i i 举例：对符号串举例：对符号串i+i*i#的分析过程的分析过程 Ei+*()#E TE TEE+TETFTFTT*FTFi(E)举例：对符号串举例：对符号串i+i*i#的分析过程的分析过程(续续1)Ei+*()#E TE TEE+TETFTFTT*FTFi(E)举例：对符号串举例：对符号串i+i*i#的分析过程的分析过程(续续2)Ei+*()#E TE TEE+TETFTFTT*FTFi(E)17接受接受预测分析程序的框图预测分析程序的框图分析算法分析算法 BEGINBEGIN 首先把首先把#然后把文法开始符号推入栈；把第一个输入符号读进然后把文法开始符号推入栈；把第一个输入符号读进a;a;FLAGFLAG：=TRUE=TRUE；WHILE FLAG DOWHILE FLAG DO BEGIN BEGIN 把栈顶符号上托出去并放在把栈顶符号上托出去并放在中；中；IF X IF X VtVt THEN IF X=a THEN 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,bX,b=X=X X X1 1X X2 2.X.XK K THEN THEN 把把X XK K，X X K-1K-1,.,X,.,X1 1一一 一推进栈一推进栈 ELSEELSEERRORERROR END OF WHILE;END OF WHILE;STOP/STOP/*分析成功，过程完毕分析成功，过程完毕*ENDEND 本章小结本章小结nLL(1)LL(1)文法的判别文法的判别n非非LL(1)LL(1)文法到文法到LL(1)LL(1)文法的等价变换文法的等价变换n给定一个文法，会构造其递归下降分析程给定一个文法，会构造其递归下降分析程序及预测分析表。序及预测分析表。
展开阅读全文