第5自顶向下的语法分析方法课件.ppt_163文库

资源描述

1、第第5 5章章自顶向下的语法分析方法自顶向下的语法分析方法语法分析的作用是识别由词法分析给出的语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子单词符号序列是否是给定文法的正确句子(程序程序)。目前语法分析常用的方法有目前语法分析常用的方法有:1 1、自顶向下（自上而下）分析、自顶向下（自上而下）分析2 2、自底向上（自下而上）分析、自底向上（自下而上）分析自顶向下分析法也就是从文法的开始符号出自顶向下分析法也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能句子，若输入串是给定文法的

2、句子，则必能推出，反之必然出错。推出，反之必然出错。回顾在“文法和语言”一章中介绍的关于句子、句型和语言的定义及什么叫最左推导、最右推导和规范推导的基本概念。句型、句子、语言的定义句型、句子、语言的定义句型:有文法G S，若S x，且x V*则称x是文法G S的句型。符号表示经过0步或若干步的推导。句子:有文法GS，若S x，且xVT*，则称x是文法G S的句子。例：GS：S0S1，S01可有推导 S 0S1 00S11 000S111 00001111说明00001111是GS的句子。句型的分析句型的分析句型分析句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。最左（

3、最右）推导最左（最右）推导：在推导的任何一步，都是对中的最左（右）非终结符进行替换。最右推导被称为规范推导。最右推导被称为规范推导。由规范推导所得的句型称为规范句型。由规范推导所得的句型称为规范句型。句型分析的有关问题句型分析的有关问题如何选择使用哪个产生式进行推导？如何选择使用哪个产生式进行推导？假定要被替换的最左非终结符号是V，且左部为V的规则有n条：VA1|A2|An，那么如何确定用哪个右部去替换V呢？如何识别可归约的串？如何识别可归约的串？在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中寻找一个子串，看它是否能归约到文法的某个非终结符号，该子串称为“可归约串”。5.1

4、确定的自顶向下分析思想确定的自顶向下分析思想确定的自顶向下分析方法:首先要解决从某文法的开始符号出发，对给定的输入符号串如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导.例 5.1若有文法G1S:S pA|qBA cAd|aB d B|c识别输入串w=pccadd是否是G1S的句子试探推导过程：S pA pcAd pccAdd pccadd试探成功。这个文法有以下两个特点这个文法有以下两个特点：每个产生式的右部都由终结符号开始。如果两个产生式有相同的左部，那么它们的右部由不同的终右部由不同的终结符开始。即每个产生式的右部的开始终结符不同。结符开始。即每个

5、产生式的右部的开始终结符不同。对于这样的文法显然在推导过程中完全可以根据当前的输入符对于这样的文法显然在推导过程中完全可以根据当前的输入符号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。例 5.2若有文法G2S:S Ap|BqA a|cA B b|dB识别输入串w=ccap是否是G2S的句子，那么试探推出输入串的推导过程为：S Ap cAp ccAp ccap试探推导成功。文法的特点是：文法的特点是：产生式的右部不全是由终结符开始。如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。文法中无空产生式。对于产生

6、式中相同左部含有非终结符开始的产生式时，在对于产生式中相同左部含有非终结符开始的产生式时，在推导过程中选用哪个产生式不像例推导过程中选用哪个产生式不像例5.1文法那样直观，对文法那样直观，对于于 W=ccap 为输入串时，其第一个符号是为输入串时，其第一个符号是c，这时从，这时从S出发出发选择选择 SAp 还是选择还是选择 SBq，需要知道，需要知道，Ap或或Bq它们的它们的开始终结符号集合开始终结符号集合是什么？是什么？因为因为c是包含在是包含在Ap的的开始终结符号集合中开始终结符号集合中，且不包含在，且不包含在Bq的的开始终结符号集合中开始终结符号集合中，则选择，则选择 SAp 往下进行推

7、导。往下进行推导。S Ap|BqA a|cA B b|dB一个文法符号串的终结符的首符集定义如下一个文法符号串的终结符的首符集定义如下：定义定义5.1 设设G=(VT，VN，S，P)是上下文无关文法是上下文无关文法FIRST()=a|a,aVT，,V*若若 ,则规定则规定FIRST()不难求出在例5.2文法G2中FIRST(Ap)=a,cFIRST(Bq)=b,d因此有因此有 FIRST(Ap)(FIRST(Bq)=这样文法这样文法G中，中，两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。但它们右部的符号串可能推导出的但它们右部的符号串可能推导出的First集不相交，因而可

8、以根据当前的输入符号是属于哪个产生式的集不相交，因而可以根据当前的输入符号是属于哪个产生式的FIRST集而决定选择相应产生式进行推导，因此仍能构造确定的自集而决定选择相应产生式进行推导，因此仍能构造确定的自顶向下分析。顶向下分析。G2：S Ap|BqA a|cA B b|dB例 5.3若有文法G3S:S aA|dA bAS|识别输入串w=abd是否是G3S的句子试探推导出abd的推导过程为：S aA abAS abS abd试探推导成功。文法的特点是：文法的特点是：文法中含有空产生式。从以上推导过程中我们可以看到在第2步到第3步的推导中，因当前面临输入符号为因当前面临输入符号为d，而最左非终结

9、符，而最左非终结符A的产生式右部的开始符号集合都不包含的产生式右部的开始符号集合都不包含d，但有，但有，因此对于因此对于d 的匹的匹配自然认为配自然认为只能依赖于在可能的推导过程中只能依赖于在可能的推导过程中A的后面的符号，所以的后面的符号，所以这时选用产生式这时选用产生式A往下推导，而往下推导，而当前当前A后面的符号为后面的符号为S，S产生式产生式右部的开始的终结符号集合包含了右部的开始的终结符号集合包含了d，所以可匹配。，所以可匹配。当一个文法中相同左部非终结符的右部存在能的情况则必须知道该非终结符的后跟符号的集合中的符号是该非终结符的后跟符号的集合中的符号是否可以唯一地确定选择哪个产生

10、式。否可以唯一地确定选择哪个产生式。为此，我们定义一个文法非终结符的后跟符号的集合如下：定义定义5.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

11、的替换仍可唯一地确定候选。综合以上情况可定义选择集合综合以上情况可定义选择集合SELECT如下：如下：定义定义5.3 给定上下文无关文法的产生式A,AVN,V*,若 ,则SELECT(A)=FIRST()如果则：SELECT(A)=（FIRST()）FOLLOW(A)是否所有的文法都能采用确定的自上而下的分析是否所有的文法都能采用确定的自上而下的分析该文法的特点是：该文法的特点是：关于关于A的产生式的不同右部开始符号集合都含有的产生式的不同右部开始符号集合都含有a，因此要替，因此要替换非终结符换非终结符A时，对当前输入符为时，对当前输入符为a的情况，不能确定用产生式的情况，不能确定用产生式A

12、ab 的右部还是用的右部还是用Aa的右部去替换。所以导致必须用带回溯的右部去替换。所以导致必须用带回溯的自顶向下分析的自顶向下分析，这是一个不确定的分析这是一个不确定的分析文法含有左递归，可见一个文法含有左递归时不能用确定的自顶向文法含有左递归，可见一个文法含有左递归时不能用确定的自顶向下分析下分析文法含有左递归，一个文法含有左递归时不能用确定的自顶向文法含有左递归，一个文法含有左递归时不能用确定的自顶向下分析。由以上例子可以看出，例下分析。由以上例子可以看出，例5.4例例5.6的文法不能用确定的文法不能用确定的自顶向下分析的自顶向下分析,可用带回溯的自顶向下分析。可用带回溯的自顶向下分析。5

13、.2 LL(1)文法的定义和判别文法的定义和判别由5.1的例1例6可知，一个文法能否用确一个文法能否用确定的自顶向下分析与文法中相同左部的每定的自顶向下分析与文法中相同左部的每个产生式右部的开始符号集合有关，当某个产生式右部的开始符号集合有关，当某个非终结符能推出个非终结符能推出时则与该非终结符时则与该非终结符的后跟符号集合也有关。综合以上两点，的后跟符号集合也有关。综合以上两点，即一个文法能否用确定的自顶向下分析与即一个文法能否用确定的自顶向下分析与产生式的产生式的SelectSelect集有关。此外在产生式中集有关。此外在产生式中不存在左递归。不存在左递归。n定义定义5.4 一个上下文无

14、关文法是LL(1)文法的充分必要条件是：对每个非终结符A的两个不同产生式，A,A,满足SELECT(A)SELECT(A)=其中，不同时能 LL(1)文法的定义文法的定义LL(1)文法的含义：第一个L 从左到右扫描输入串第二个L 生成的是最左推导 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(

15、AbAS)select(A )=所以，该文法是LL（1）文法。例：判断下列文法是否是LL(1)文法文法G S为：SaASSbAbAA例文法G S为：SaASSbAbAA则 SELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=a,b所以 SELECT(SaAS)SELECT(Sb)=ab=SELECT(AbA)SELECT(A)=ba,b 因此，该文法不是LL(1)文法，因而也就不可能用确定的自顶向下分析。LL(1)文法的判别文法的判别当我们需选用自顶向下分析技术时，首先必须判别所给文法是否是LL(1)文法。因而我们对任给文法需计算FIRST、

16、FOLLOW、SELECT集合，进而判别文法是否为LL(1)文法。4、若XVN；Y1，Y2，YiVN，且有产生式XY1 Y2 Yn；当Y1 Y2 Yi-1都时，(其中1in)，则FIRST(Y1)、FIRST(Y2)、FIRST(Yi-1)的所有非空元素和FIRST(Yi)都包含在FIRST(X)中。5、当(4)中所有Yi ,(i=1,2,n)，则FIRST(X)=(FIRST(Y1)）（FIRST(Y2)）（FIRST(Yn)）反复使用上述反复使用上述(2)(5)步直到每个符号的步直到每个符号的FIRST集合不再增大为止。集合不再增大为止。例文法G S为：SABSbCAAbBBaDCADC

17、bDaSDc求每个终结符的First集。例文法G S为：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的结点连一条箭弧。

18、(c)凡是从FIRST(A)结点有路径可到达的终结符结点所标记的终结符都为FIRST(A)的成员。(d)由是否为某非终结符FIRST集的成员，若是则将加入该非终结符的FIRST集中。文法G S为：SABSbCAAbBBaDCADCbDaSDc FIRST(S)=b,a,FIRST(A)=b,FIRST(B)=a,FIRST(C)=a,b,cFIRST(D)=a,c计算计算FOLLOW集集根据定义计算根据定义计算对文法中每一 AVN 计算 FOLLOW(A)(a)设S为文法中开始符号，把#加入FOLLOW(S)中(这里“#”为句子括号)。(b)若AB是一个产生式，则把FIRST()的非空元素

19、加入 FOLLOW(B)中。如果则把FOLLOW(A)也加入FOLLOW(B)中。(c)反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。例：文法G S为：SABSbCAAbBBaDCADCbDaSDc求每个非终结符的Follow集。文法G S为：SABSbCAAbBBaDCADCbDaSDc解：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)文法文法文法G S为：SA

20、BSbCAAbBBaDCADCbDaSDc每个产生式的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

21、)=c文法G S为：SABSbCAAbBBaDCADCbDaSDc由以上计算结果可得相同左部产生式的SELECT交集为：SELECT(SAB)SELECT(SbC)=b,a,#b=b SELECT(A)SELECT(Ab)=a,c,#b=SELECT(B)SELECT(BaD)=#a=SELECT(CAD)SELECT(Cb)b,a,cbb SELECT(DaS)SELECT(Dc)=ac 由LL(1)文法定义知该文法不是LL(1)文法，因为关于S和C的相同左部其产生式的SELECT集的交集不为空。非LL(1)文法到LL(1)文法的等价转换由前面可知：确定的自顶向下分析要求对给定语言的文法必须

22、是LL(1)形式。然而，不一定每个语言都有LL(1)文法。对一个语言的非LL(1)文法是否能变换为等价的LL(1)形式以及如何变换是本节讨论的主要问题。若文法中含有直接或间接左递归，或含有左公共因子则若文法中含有直接或间接左递归，或含有左公共因子则该文法肯定不是该文法肯定不是LL(1)文法。因而，我们设法消除文法文法。因而，我们设法消除文法中的左递归，提取左公共因子对文法进行等价变换，在中的左递归，提取左公共因子对文法进行等价变换，在某些特殊情况下可能使其变为某些特殊情况下可能使其变为LL(1)文法。文法。1提取左公共因子提取左公共因子若文法中含有形如：A|的产生式，这导致了对相同左部的产生式

24、若文法G的产生式为：(1)SaSb(2)SaS(3)S请提取文法中的左公因子对产生式(1)、(2)提取左公因子后得：S aS(b|)S进一步变换为文法G：SaSAAbAS例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)BbB提取产生式(1)、(2)的左公共因子得：Aa(

25、d|Ac)AbBcBaABbB引进新非终结符A，去掉(，)后得G为：(1)AaA(2)AbBc(3)Ad(4)AAc(5)BaA(6)BbB不难验证经提取左公共因子后文法例1中的G仍不是LL(1)文法。而文法例2中的G变成LL(1)文法，因此文法中不含左公共因子只是因此文法中不含左公共因子只是LL(1)文法的必要文法的必要条件。条件。值得注意的是对文法进行提取左公共因子变换后，有值得注意的是对文法进行提取左公共因子变换后，有时会使某些产生式变成无用产生式，在这种情况下必时会使某些产生式变成无用产生式，在这种情况下必须对文法重新压缩须对文法重新压缩(或化简或化简例3：若有文法G的产生式为：(1)

26、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)

28、文法的产生式愈来愈多无限增加下去，但不能得到提取左公共因子的预期结果。由上面所举例子可以说明以下问题：由上面所举例子可以说明以下问题：不一定每个文法的左公共因子都能在有限的步骤内不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法，上面文法替换成无左公共因子的文法，上面文法G4就是如就是如此。此。一个文法提取了左公共因子后，只解决了相同左部一个文法提取了左公共因子后，只解决了相同左部产生式右部的产生式右部的FIRST集不相交问题，当改写后的文集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法法不含空产生式，且无左递归时，则改写后的文法是是LL(1)

29、文法，否则还需用文法，否则还需用LL(1)文法的判别方式进文法的判别方式进行判断才能确定是否为行判断才能确定是否为LL(1)文法。文法。2.消除左递归消除左递归设一个文法含有下列形式的产生式。1)AA AVN，V*2)AB BA A,BVN,V*可称含1)中产生式的文法为含有直接左递归。含2)中产生式的文法有A A 则称文法中含有间接左递归，文法中只要含有1)或含有2)的产生式或二者皆有，均认为文法是左递归的，然而，一个文法是左递归时不能采用自顶向下分析法。为了使某些含有左递归的文法经过等价变换消除左递为了使某些含有左递归的文法经过等价变换消除左递归后可能变为归后可能变为LL(1)文法，可采

30、取下列变换公式：文法，可采取下列变换公式：a)消除直接左递归，把直接左递归改写为右递归，消除直接左递归，把直接左递归改写为右递归，如对文法如对文法G：SSaSb可改写为：可改写为：SbSSaS|一般情况下，假定关于一般情况下，假定关于A的全部产生式是：的全部产生式是：AA1|A2|Am|1|2|n其中，i(1im)不等于,j(1jn)不以A开头，消除直接左递归后改写为：消除直接左递归后改写为：A1 A|2 A|n AA1 A|2 A|m A|b)消除间接左递归。消除间接左递归。对于间接左递归的消除需先将间接左递归变为直接左对于间接左递归的消除需先将间接左递归变为直接左递归，然后再按递归，然后再

32、。步骤步骤(P83 P84 算法步骤）算法步骤）1)把文法的所有非终结符按某一顺序排序；把文法的所有非终结符按某一顺序排序；如如A1，A2,An 2)A1产生式右部用产生式右部用A2，,An表示，表示，A2产生式右部用产生式右部用A3，,An表示，表示，A3产生式右部用产生式右部用A4，,An表示，表示，,An产生式右部用产生式右部用An表示。消除表示。消除An中的直接左递归。中的直接左递归。3)去掉无用产生式。去掉无用产生式。把上述算法归结为：把上述算法归结为：若非终结符的排序为A1，A2，An。for(i=1;i=n;i+)for(j=1;j=i-1;j+)将规则Ai Ajr改写：/若Aj

33、 1|2|k /则：替换产生式变为：Ai1r|2r|kr 消除规则中的直接左递归例如，有文法的产生式为：(1)SQc|c(2)QRb|b(3)RSa|a该文法为间接左递归，按上述方法消除该文法的一切左递归。若非终结符排序为若非终结符排序为S、Q、R,（1）式左部为S的产生式是用后面的符号表示，不用修改 (2)号产生式中右部是用后面的符号表示，不用修改，(3)式中R是用前面的S表示，所以把(1)右部代入(3)得：(4)RQca|ca|a 再将(2)的右部代入(4)得：(5)RRbca|bca|ca|a对(5)消除直接左递归得：R(bca|ca|a)RRbcaR|最终文法变为：SQc|cQRb|b

35、Begin F;T End;Procedure E Begin if sym=+then Begin getsym T;E;End End;Procedure T Begin if sym=*then Begin getsym;F;T;End EndProcedure F Begin if symi then Begin if sym=(then Begin getsym;E;if sym=)then getsym;else Error End else Error End EndF(E)|i（见附录）递归子程序要求文法必须是递归子程序要求文法必须是LL(1)文法。文法。预测分析方法预测分析方

36、法预测分析方法是自顶向下分析的另一种方法，一个预测分析方法是自顶向下分析的另一种方法，一个预测分析器是由三个部分组成。预测分析器是由三个部分组成。预测分析程序预测分析程序(总控程序总控程序)先进后出栈先进后出栈(stack)预测分析表预测分析表表驱动予测分析程序模型表驱动予测分析程序模型 Input Input#总控程序总控程序预测分析表预测分析表stack其中只有预测分析表与文法有关，而分析表又可用一个矩阵M(或称二维数组)表示。矩阵的元素MA，a中的下标A表示非终结符，a为终结符或句子括号“#”，矩阵元素MA,a中的内容为存放着一条关于A的产生式，表明当用非终结符表明当用非终结符A向下推

37、向下推导时，面临输入符导时，面临输入符a时，所应采取的候选产生式，时，所应采取的候选产生式，当元素内容无产生式时，则表明用A为左部向下推导时遇到了不该出现的符号，因此元素内容为转向出错处理的信息AaA A遇到输入符a，选用哪个产生式，如果A ，a Frist()。如果A ，a Follow(A),即如果a select(A )则把则把A 加入到加入到M(A,a)中。中。解：解：(1)判断它是否是判断它是否是LL（1）文法因为该文法含有）文法因为该文法含有左递归，所以不是左递归，所以不是LL（1）文法，必须改写成）文法，必须改写成LL(1)文法：文法：G E:(1)E TE (2)E +TE (

38、3)E (4)T FT (5)T *FT (6)T (7)F (E)(8)F a 例：为文法G(E):E E+T|T T T*F|F F a|(E)构造预测分析表。构造预测分析表。Select(E TE)=First(T)=First(F)=a,(Select(E +TE)=+Select(E )=Follow(E)=Follow(E)=(#,)Select(T FT)=First(F)=(,aSelect(T *FT)=*Select(T )=Follow(T)=Follow(T)=(First（E)-)Follow(E)=(First（E)-)Follow(E)=+,#,)Select(F

39、 (E)=(Select(F a)=aG E:(1)E TE (2)E +TE (3)E (4)T FT (5)T *FT (6)T (7)F (E)(8)F a a+*()#EE TEE TE E +TE T FT FT T *FT F a (E)G E:(1)E TE (2)E +TE (3)E (4)T FT (5)T *FT (6)T (7)F (E)(8)F a分析输入串分析输入串#a+a#栈内容栈顶符号当前输入余留串 MX,b 1#E E a +a#E TE2#ET T a +a#T FT3#ETF F a +a#F a4#ETa a a +a#匹配a5#ET T +a#T

40、6#E E +a#E +TE7#ET+a#匹配+8#ET T a#T FT 9#ETF F a#F a10#ETa a a#匹配a11#ET T#T 12#E E#E 13#预测分析程序的框图分析算法分析算法 BEGINBEGIN 首先把首先把#然后把文法开始符号推入栈；把第一个输入符号读进然后把文法开始符号推入栈；把第一个输入符号读进a;a;FLAGFLAG：=TRUE=TRUE；WHILE FLAG DOWHILE FLAG DO BEGIN BEGIN 把栈顶符号上托出去并放在把栈顶符号上托出去并放在中；中；IF X IF X Vt THEN IF X=a THEN Vt THEN I

41、F X=a THEN 把下一把下一个输入符号读进个输入符号读进a a ELSE ERROR ELSE ERROR ELSE IF X=#THEN ELSE IF X=#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 ELSEERRORERROR END OF WHILE;END OF WHILE;STOP/STOP/*分析成功，过程完毕分析成功，过程完毕*ENDENDLL(1)LL(1)文法的性质文法的性质：LL(1)LL(1)文法是无二义的文法是无二义的 LL(1)LL(1)文法不含左递归文法不含左递归非非LL(1)LL(1)文法的改造文法的改造消除左递归消除左递归提左公因子提左公因子将产生式将产生式|变换为：变换为：B B B B|

展开阅读全文