ll(1)文法的定义与判别

资源描述

《ll(1)文法的定义与判别》由会员分享，可在线阅读，更多相关《ll(1)文法的定义与判别（11页珍藏版）》请在金锄头文库上搜索。

1、单元目录第四单元自顶向下分析法4.2 LL(1)文法的定义和判别1. 定义定义4.4一个上下文无关文法是LL(1)文法的充分必要条件是：对每个非终结符A的两个不同产生式，A, A,满足SELECT(A)SELECT(A)=。其中，不同时能。 2. LL(1)文法的含义：文法的含义：第一个L 从左到右扫描输入串第二个L 生成的是最左推导1 向右看一个输入符号便可决定选择哪个产生式。例1：判断下列文法是否是LL(1)文法G：SaASdAbASA解： select(SaA)=aselect(S d)=dselect (SaA) select(S d)=select(AbAS)

2、=bselect(A)=First()-Follow(A)=Follow(A)=a,d,#select (AbAS) select(A )=所以，该文法是LL（1）文法。例2：判断下列文法是否是LL(1)文法文法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)文法，因而也就不可能用确定的自顶向下分析。 3. LL(1)文法的判别文法的判别当我们需选用自顶向下分析技术时，首先

3、必须判别所给文法是否是LL(1)文法。因而我们对任给文法需计算FIRST、FOLLOW、SELECT集合，进而判别文法是否为LL(1)文法。计算计算FIRST集集1.若XVT,则FIRST(X)=X.2.若XVN,且有产生式Xa.,aVT,则把a加入到FIRST(X)中;若X是一条产生式,则把也加到FIRST(X)中.3.若XY.是一个产生式且YVN,则把FORST(Y)中的所有非元素都加到FIRST(X)中.4、若XVN；Y1，Y2，YiVN，且有产生式XY1 Y2 Yn；当Y1，Y2，Yi-1都时，(其中1in)，则FIRST(Y1)、FIRST(Y2)、FIRST(Yi-1)的所

4、有非空元素和FIRST(Yi)都包含在FIRST(X)中。5、当(4)中所有Yi,(i=1,2,n)，则FIRST(X)=(FIRST(Y1) ）（FIRST(Y2) ）（FIRST(Yn) ）反复使用上述(2)(5)步直到每个符号的FIRST集合不再增大为止。例例3:文法GS为：SABSbCAAbBBaDCADCbDaSDc求每个终结符的First集。解：FIRST(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也可以由关系图

5、法求文法符号的FIRST集，可作为一种验证。其方法为：(a)每个文法符号对应图中一个结点，对应终结符的结点时用符号本身标记，对应非终结符的结点用FIRST(A)标记。这里A表示非终结符。(b)如果文法中有产生式AX，且,则从对应A的结点到对应X的结点连一条箭弧。(c) 凡是从FIRST(A)结点有路径可到达的终结符结点所标记的终结符都为FIRST(A)的成员。(d) 由是否为某非终结符FIRST集的成员，若是则将加入该非终结符的FIRST集中。例4:文法G S为：SABSbCAAbBBaDCADCbDaSDc解：FIRST(S)=b,a,FIRST(A)=b,FIRST(B)=a,FIRS

6、T(C)=a,b,cFIRST(D)=a,c 4.计算计算FOLLOW集集对文法中每一 AVN 计算 FOLLOW(A):(a)设S为文法中开始符号，把#加入FOLLOW(S)中(这里“#”为句子括号)。(b)若AB是一个产生式，则把FIRST()的非空元素加入FOLLOW(B)中。如果则把 FOLLOW(A)也加入FOLLOW(B)中。(c)反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。例5：文法GS为：SABSbCAAbBBaDCADCbDaSDc求每个非终结符的Follow集。解：FOLLOW(S)=# FOLLOW(D) #FOLLOW(A)=(FIRST(B)FOLLO

7、W(S)FIRST(D)a,#,cFOLLOW(B)=FOLLOW(S)=#FOLLOW(C)=FOLLOW(S)=#FOLLOW(D)=#例6：文法GS为：SABSbCAAbBBaDCADCbDaSDc判断它是否是LL(1)文法解：每个产生式的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)=FIRS

8、T(aD)=aSELECT(CAD)=FIRST(AD)=a,b,cSELECT(Cb)=FIRST(b)=bSELECT(DaS)=FIRST(aS)=aSELECT(Dc)=FIRST(c)=c由以上计算结果可得相同左部产生式的SELECT交集为：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)文法，因为关于S和C的相同左部其产生式

9、的SELECT集的交集不为空。单元目录第四单元自顶向下分析法4.3 非LL(1)文法到LL(1)文法的等价转换由前面可知：确定的自顶向下分析要求对给定语言的文法必须是LL(1)形式。然而，不一定每个语言都有LL(1)文法。对一个语言的非LL(1)文法是否能变换为等价的LL(1)形式以及如何变换是本节讨论的主要问题。若文法中含有直接或间接左递归，或含有左公共因子则该文法肯定不是LL(1)文法。因而，我们设法消除文法中的左递归，提取左公共因子对文法进行等价变换，在某些特殊情况下可能使其变为LL(1)文法。 1. 提取左公共因子提取左公共因子若文法中含有形如：A|的产生式，这导

11、)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(d|Ac)AbBcBaABbB引进新非终结符A，去掉(，)后得G为：(1) AaA(2) AbBc(3)

12、Ad(4) AAc(5) BaA(6) BbB不难验证经提取左公共因子后文法例1中的G仍不是LL(1)文法。而文法例2中的G变成LL(1)文法，因此文法中不含左公共因子只是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)引入新非

14、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可以看出若对(5)中产生式A、B继续用(6)、(7)产生式的右部替换，只能使文法的产生式愈来愈多无限增加下去，但不能得到提取左公共因子的预期结果。由上面所举例子可以说明以下问题：不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法，上面文法G4就是如此。一个文法提取了左公共因子后，只解决了相同左部产生式右部的FIRST集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是LL(1)文法，否则还需用LL(1)文法的判别方式进行判断才能确定是否为LL(1)文法。 2. 消除左递归：消除左递归：设一个文法含有下列形式的产生式。1)AA,AVN，V* 2)AB,BA A,BVN, ,V*可称含1)中产生式的文法为含有直接左递归。含2)中产生式的文法有AA 则称文法中含有间接左递归，文法中只要含有1)或含有2)的产生式

展开阅读全文

ll(1)文法的定义与判别

最新文档