资源目录
压缩包内文档预览：
编号：21836409
类型：共享资源
大小：13.06MB
格式：ZIP
上传时间：2019-09-06
上传人：QQ24****1780
认证信息
个人认证
王**（实名认证）
浙江
IP属地：浙江
25
积分
- 关 键 词：
-
大学
编译
原理
实用教程
杨德芳
课件
ppt
- 资源描述：
-
大学编译原理实用教程-杨德芳-课件PPT,大学,编译,原理,实用教程,杨德芳,课件,ppt
- 内容简介：
-
第4章 自顶向下的语法分析技术本章学习目标语法分析是继词法分析之后，编译过程的第二个阶段。它的主要任务是对词法分析的输出结果单词序列进行分析，识别出合适的语法单位。语法分析分为自顶向下和自底向上的两类方法。自顶向下的语法分析又分为确定的自顶向下分析（无回溯）和不确定的（带回溯的）的自顶向下语法分析两种。本章主要内容有：。自顶向下的语法分析的基本思想。LL(1)语法分析方法。确定的自顶向下分析技术，包括递归子程序法和预测分析技术4.1确定的自顶向下分析方法自顶向下分析就是从文法的开始符号出发并寻找出这样一个推导序列：推导出的句子恰好是输入符号串；或者说，能否从根结点出发向下生长出一棵语法树，其叶结点组成的句子恰好为输入符号串。显然，语法树的每一步生长（每一步推导）都以能否与输入符号串匹配为准。如果最终句子得到识别，则证明输入符号串为该文法的一个句子；否则，输入符号串不是该文法的句子。自顶向下分析分为确定的自顶向下分析和不确定的自顶向下分析法两种。具体分析方法归纳如下：（1）自顶向下建树，试图生成一个和所给符号串（输入符号串）相一致的终结符号串。（2）在建树过程中，按照一定的规律选择生成规则，展开为向下生长的树。每一步都试图将生成的尚未消除的最左叶片与输入符号匹配。（3）匹配失败后，必须退回到出错点，选择其他可能的规则，直到生长出与读入符号串完全一致的树型结构，这种方法称为回溯。（4）如果按上述方法构造成功，说明读入的符号串是文法的一个句子；反之，如果穷尽所有的途径都没有办法成功，则说明读入的符号串不是文法的一个句子。4.1.1确定的自顶向下分析思想确定的自顶向下分析方法，首先要解决从文法的开始符号出发，如何根据当前的输入符号（单词符号）惟一地确定选用哪个产生式替换非终结符往下推导，或者构造一棵相应的语法树。例题4.1设有文法GS ：SpA | qBAcAd |a BdB |b若输入串W=pccadd。自顶向下的推导过程为：SpApcAdpccAdd pccadd确定的自顶向下分析的语法树如图4-1所示。 例4.2 设有文法GS 为：SAp | BqAa |cABb |dB当输入串W=ccap时，那么试图推出输入串的推导过程为：SApcApccApccap，构造出确定的自顶向下分析的语法树如图4-2所示。该文法的产生式的右部不全是终结符开始，也有非终结符A和B。在推导过程中选用哪个产生式就不直观。比如在第一步推导中，是选择以A开始还是以B开始的产生式，我们必须向下再找一步，看看A和B的产生式哪个是有c开始。先看A，A的产生式规则是有a和c开始，而B的产生式规则是有b 和d 开始，很显然是用以A开始的产生式规则。所以就产生了推导：SAp，此时，A有两个产生式规则，很容易判断出用哪个。通过此例子，能看出在语法推导过程中，有一点很重要，那就是文法中产生式规则的开始符号。下面就产生式规则的首符号集进行定义。定义4.1 设G=(VN, VT,S,P)是上下文无关文法FIRST( )=a|a,a VT , , V* 如果，则规定 FIRST( ),，FIRST( )为的开始符号集或首符号集。定义4.1 设G=(VN, VT,S,P)是上下文无关文法FIRST( )=a|a,a VT , , V* 如果，则规定 FIRST( ),，FIRST( )为的开始符号集或首符号集。例如，FIRST(Ap)=a,cFIRST(Bq)=b,d这样，在推导时，只要这两个产生式右部的首符号集没有交集，就可以惟一的选择产生式的规则。例4.3 若有文法GS：SaA | dAbAS| 若输入串W=abd，则试图推导出abd 串的推导过程为：S aA abAS abS abd该输入串确定的语法树如下图4-3所示。定义4.2 设G=（VT,VN,S,P）是上下文无关文法，A VN ，S是开始符号FOLLOW（A）=a| SA，且a VT，aFIRST()， VT*，V+若S=A，且 =*，且# FOLLOW(A)。也可以定义为FOLLOW（A）=a|SAa，a VT若有S=A，则规定#FOLLOW（A）一般来讲，我们用“#”作为输入串的结束符，或称为句子的括号，如#输入串#。4.1.2 LL(1)文法的定义根据上面的分析我们重新定义一个产生式被选择时的集合SELECT如下。定义4.3 给定上下文无关文法的产生式A，AVN，V*，若不能推出，则SELECT(A)=FIRST()如果能够推导出，则SELECT(A)=(FIRST()FOLLOW(A)。LL(1)文法定义：。定义4.4 一个上下文无关文法是LL（1）文法的充分必要条件是，对每个非终结符A的两个不同的产生式，A，A 满足SELECT（A）SELECT（A）=其中，和不同时推出。如果某个文法满足上述条件，称该文法为LL(1)文法。如果一个文法是LL(1)文法，就可以采用确定的自顶向下分析技术进行语法分析。LL(1)文法的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第二个L表明分析过程中将用最左推导，1表明只需向右看一个符号便可以决定如何推导即选择哪个产生式规则进行推导例4.4 有一文法，判断该文法是否是LL(1)文法，写出判断过程。 SpA | qBAcAd |a BdB |bSELECT(SpA)SELECT(SqB)=pq=SELECT(AcAS)SELECT(Aa)=ca=SELECT(BdB)SELECT(Bb)=db=所以是LL(1)文法，即可以采用确定的自顶向下的分析方法。例4.5 若有文法G4S：SaA | dAbAS| SELECT(SaA)SELECT(Sd)=ad=SELECT(AbA)SELECT(A)=bFIRST()FOLLOW(A) =b#,a,d=所以该文法也是一个LL(1)文法。例4.6 设文法 SaAS | bAbA| 则SELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(S)=a,b根据LL(1)的定义有SELECT(SaAS)SELECT(Sb)=ab=SELECT(AbA)SELECT(S)=ba,b,#因此该文法不是LL(1)文法，即该文法不能采用自顶向下分析法进行分析。例4.7 有文法GS：SBAABS|dBaA|bS|c证明该文法G是LL(1)文法。【证明】一个LL(1)文法的充要条件是：对每一个非终结符A的任何两个不同产生式A|，有下面的条件成立：SELECT(A)SELECT(A)=对于该文法，FIRST(B)=a,b,c；FIRST(A)=a,b,c,d；FIRST(S)=a,b,cSELECT(ABS)=FIRST(B)=a,b,cSELECT(Ad)=FIRST(d)=dSELECT(A BS )SELECT(Ad )=SELECT(BaA) SELECT(BbS) SELECT(Bc)=abc=所以该文法是一个LL(1)文法。4.2 LL(1)文法我们在采用确定的自顶向下分析时，首先要判定该文法是否是一个LL(1)文法，然后才能进行语法分析。对于给定的任何一个文法，首先要计算FIRST，FOLLOW，SELECT集合，进而判别文法是否为LL(1)文法。如果给定一个文法，它不是LL(1)文法，则需要将其转换为LL(1)文法。例4.8 若文法GS为 SABSbCAAb B BaDCADCbDaSDc1求出能推出的非终结符首先建立一个以文法的非终结符个数为上界的一维数组，其数组元素为非终结符，对应每一个非终结符有一个标志位，用来记录能否推出。其值有三种情况“未定”、“是”、“否”。用一个数组X 来表示这些状态。计算出能推导出的非终结符的步骤如下：（1）将数组X 中对应的每一个非终结符的标记记为“未定”。（2）扫描文法中的产生式。(a)删除所有右部含有终结符的产生式。若这使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应的非终结符的标记值改为“否”，说明该非终结符不能推出。(b)若某一非终结符的某一个产生式右部为，则将数组中对应该非终结符的标志置为“是”，并从文法中删除该非终结符的所有的产生式。例中对应非终结符A，B的标志改为“是”。（3）扫描产生式右部的每一个符号。(a)若所扫描到的非终结符号在数组中对应的标志是“是”，则删去该非终结符，若这使产生式右部为空，则对产生式右部的非终结符在数组中对应的标志改为“是”，并删除该非终结符为左部的所有的产生式。(b)若所扫描到的非终结符号在数组中对应的标志是“是”，则删除该产生式。若这使得产生式左部非终结符的有关产生式都被删除，则把在数组中该非终结符对应的标志改成“否”。（4）重复（3），直到扫描完一遍文法的产生式，数组中的非终结符对应的特征再没有改变为止2FIRST集合的求法（1）对于每一个文法符号XV，计算FIRST（X）。(a)若XVT ，则FIRST（X）=X(b)若XVN，并且有产生式Xa，aVT，则aFIRST（X）。(c)若XVN，X，则FIRST（X）。(d）若XVN，Y1，Y2，Yi都属于VN，而有产生式XY1Y2Yn。当Y1，Y2，Yi-1都能够推出（1in），则FIRST（Y1 ）， FIRST（Y2 ），FIRST（Yi-1）， FIRST（Yi ）都包含在FIRST（X）中。（e）当（d）中所有的Yi（1in），则FIRST（X）=FIRST（Y1 ）FIRST（Y2 ）FIRST（Yn ）。(2)每个产生式右部符号串的FIRST集合的步骤如下：（a）如果符号串V*，=X1X2XXn，当X1不能，则置FIRST（）=FIRST（X1）（b）如果对于任何j，(1ji-1，2in)，则FIRST（Xj），FIRST（Xi）则FIRST（）=（FIRST（X1）（FIRST（X2）（FIRST（Xi-1）FIRST（Xi）当所有FIRST（Xj）（1jn）都含有时，则FIRST（）=FIRST（X1）FIRST（X2） FIRST（Xn）由 此算法可以计算出例题4.8文法各非终结符的FIRST集。FIRST（S）=FIRST（A）FIRST（B）b=b,a,FIRST（A）=b=b,FIRST（B）=a= a, FIRST（C）=FIRST（A）FIRST（D）FIRST（b）=b,a,cFIRST（D）=ac=a,c每个产生式右部符号串的开始符号集合为：FIRST（AB）=b,a,FIRST（bC）=bFIRST()= FIRST(b)=bFIRST(aD)=aFIRST(AD)=a,b,cFIRST(b)= bFIRST(aS)= aFIRST(c)= c3计算FOLLOW集合根据定义计算FOLLOW集合对于文法中每一个非终结符AVN，计算FOLLOW（A）的步骤如下：设S为文法的开始符号，把#加入到FOLLOW(S)中(#为被检查的句子的括号)。若AB是一个产生式，则把FIRST（）的非空元素加入到FOLLOW（B）中。如果，则把FOLLOW(A)也加入到FOLLOW（B）中，因为当形如：D1A1AB的产生式时，会有推导S=1A11aB11B1可以知道FIRST(1)FOLLOW(A)则必有FIRST(1)FOLLOW(B)所以有FOLLOW(A)FIRST(B)反复使用(b)直到每个非终结符的FOLLOW集合不再扩大为止。现在计算例题4.8文法各非终结符的FOLLOW集。FOLLOW(S)=#FOLLOW(D)FOLLOW(A)=(FIRST(B)FOLLOW(S)FIRST(D)FOLLOW(B)=FOLLOW(S)FOLLOW(C)=FOLLOW(S)FOLLOW(D)=FOLLOW(B)FIRST(C)最终的计算结果是：FOLLOW(S)=#FOLLOW(A)=a,#,cFOLLOW(B)=#FOLLOW(C)=#FOLLOW(D)=#4计算SELECT集根据上面文法的FIRST集和FOLLOW集计算得结果如表4-2所示,该表表示的是文法的FIRST集合和FOLLOW集合。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由以上计算结果可得相同的左部产生式的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,cb=bSELECT(DaS)SELECT(Dc)=ac=由LL(1)文法定义知该文法不是LL(1)文法。4.2.2将非LL(1)文法转变成LL(1)文法采用确定的自顶向下分析要求给定的文法必须是LL(1)文法，但并不是所有的文法是LL(1)文法。对于给定的文法，如果该文法含有直接左递归或间接左递归，或含有左公共因子则称该文法肯定不是LL(1)文法，要想将非LL(1)文法改为LL(1)文法，必须进行等价变换。1提取左公因子将含有形如A|格式的产生式的文法叫做直接左公因子。直接左公因子会导致相同左部的产生式，其右部的FIRST 集合有交集，即SELECT(A)SELECT(A)，不满足LL(1)文法的充分必要条件。含有左公因子的文法不是LL（1）文法，我们必须要将非LL（1）文法改为LL(1)文法。采用的方法如下：将A1|2|3|.|n，提取左公因子后变为：A(1|2|3|.|n)引进非终结符A,变为:AAA1|2|3|n如果改进后，仍然含有左公因子，可以继续提取，直到不再含有左公因子为止。例4.9设有文法如下：SS；TSTTif e then S else S Tif e then S Ta将Tif e then S else S和Tif e then S 两个产生式提取左公因子后，变为：Tif e then S( else S|)，引进新的非终结符T，产生式规则变为:Tif e then S T T else S|该文法变为：SS；TSTTif e then S T T else S|Ta例4.10若文法的产生式为：SaSbSaSS根据消除左公因子的公式，文法变为：SaS（b|）引进非终结符A后得到SaSAAb|文法变为：SaSAA b|S在某些文法中有些左公因子可能是隐式的，在这种情况下，要将产生式规则进行替换。例4.11有某个文法，其产生式为AadABcBaABbB将文法的产生式规则为：AadAaAcAbBcBaA BbB从上面的式子可以看出仍旧含有左公因子。提取左公因子后得到Aa(d|Ac)AbBcBaA BbB引进A后得到产生式为AaAAbBcAdAAcBaA BbB2消除左递归文法中的产生式含有左递归。左递归分为直接左递归和间接左递归两种方式。直接左递归的形式为：AA，间接左递归的产生式的格式为：AB BA用含有左递归的文法在进行语法检查时，容易产生回溯，降低了检查的效率。例4.12文法含有左递归,，左递归的格式为：SSa Sb该文法产生的语言是L=ban|n0，对于输入串baaaa#，判断该输入串是否合法，在选择产生式规则时，先选择第一个产生式，再选择第二个产生式 ，判断推断是否和输入串一致，如果不一致，则废除此选择，回到上一次选择中，继续调用递归的产生式重复试探直到判断结束。（1）除直接左递归一般来讲，直接左递归的格式为：AA1|A2|A3|An|1|2|3|n消除直接左递归，改写的公式为：A(1|2|3|n) AA(1|2|3|n)A|例4.13将文法 SSa Sb改写为非递归算法，算法的格式为：SbS SaS|再根据此文法对句子进行检查，效率就提高了很多。例4.14文法 ABBX|BAXXa|Xb|a|b可以直接改写文法为：ABBX|BBAB|XaX|bXXAX|bX|（2）消除间接左递归对于含有间接左递归的文法，需要将间接左递归改为直接左递归，然后再消除直接左递归。例4.15对于文法(1)AaB (2)ABb(3)BAc(4)Bd该文法是一个间接左递归的文法，将该文法变为直接左递归，方法是将（1）和（2）产生式代入（3）得到：BaBcBBbc文法由原来的文法变为：(1)AaB(2)ABb(3)BaBcBBbc(4)Bd最终的文法变为：(1)A aB (2)ABb(3)B(aBc|d)B(4)BbcB| (3)消除文法中的一切左递归算法。 对于文法中出现左递归，我们可以采用一种统一的算法解决，算法的步骤如下：1)把文法的所有非终结符按照某一顺序排列；如：A1，A2， An2) 从A1开始消除左部为A1的产生式的直接左递归，然后把左部为A1的所有规则的右部逐个替换为右部以A1开始的产生式中的A1，并消除左部为A2的产生式的直接左递归。继而以同样的方式把A1，A2的右部代入左部为A3右部以A1，A2开始的产生式中，消除左部为A3的产生式的直接左递归，直到把左部为A1，A2，An-1的右部代入左部为An的产生式中，从An消除左递归。3）去掉无用产生式。算法描述如下：将非终结符的排序为：A1，A2， Anfor i：=1 to n dobegin for j：=1 to i1 do begin 若j的所有产生式为：j|3 |k替换成形如ij 的产生式变为i|3 |k end消除i中的一切直接左递归。end最后消除无用的产生式。例4.16 设文法（1）ABcd （2）BCe|f（3）CAb|c假设该文法的非终结符的排列次序为A，B，C，则按照该算法执行过程为：i=1,j=0上述算法不执行；i=2,j=1不代入；i=3,j=1代入为（3）为（3）CBcdb|c;i=3,j=2代入为 （3）CCecdb|fcdb|c;将（3）直接递归进行改例4.16设文法(1) A Bcd (2) BCe|f(3）C Ab|c令3个非终结符的顺序为C，B，A，执行算法，当i=1,j=0；不做替换。i=2,j=1将C代入到B，将(2) BCe|f变为（2）BAbe|ce|f当i=3,j=2时将产生式（2）BAbe|ce|f 替换（1） A Bcd产生式变为A Abecd|cecd|fcd 消除A的产生式的直接左递归：A(cecd|fcd)AA becd A| 改写后的文法为：A(cecd|fcd)AA becd A| BAbe|ce|fCAb|c删除多余的产生式，最后得到文法为：A(cecd|fcd)AAbecd A| 写变为：C(fcdb|c)CCCecdbC|原来的文法变为：（1） ABcd （2）BCe|f（3）C(fcdb|c) C（4）CCecdb C|例4.17 有文法的产生式为(1) S Qc |c (2) QRb|b(3）R Sa|a该文法是一个间接左递归，按照算法消除该文法中的一切左递归。若非终结符的排列次序为S，Q，R。则算法的执行过程为：i=1,j=0不执行i=2,j=1不执行i=3,j=1将（1） S Qc|c 代入到（3）R Sa|a得到（3）R Qc a| c a|ai=3,j=2将（2） QRb |b代入（3）R Qc a| c a|a得到（3）R Rbc a| bc a|c a|a对得到最新的产生式规则（3）消除递归得到：R（bc a|c a|a）R Rbc a R|消除左递归后文法最后变为：(1) S Qc |c (2) QRb|b（3）R（bc a|c a|a）R （4）Rbc a R|如果非终结符的排列次序为R，Q，S，则算法的执行过程为：i=1,j=0不执行； i=2,j=1将（3）R Sa |a代入（2） QRb|b为（2）Q Sa b |ab|bi=3,j=1不执行；i=3,j=2将（2）Q Sa b |ab|b代入（1） S Qc |c 得到（1）S Sa b c | abc| bc|c将(1)SSabc|abc|bc|c消除左递归后得到最终文法为：S( abc| bc|c)SSabcS|QRb|bR Sa|a由于Q，R为不可到达的非终结符，所以以Q，R 为左部的产生式规则应该除掉。虽然排列次序不同，产生式的规则也不同，但算法是等价的。 如果非终结符的排列次序为R，Q，S，则算法的执行过程为：i=1,j=0不执行； i=2,j=1将（3）R Sa |a代入（2） QRb|b为（2）Q Sa b |ab|bi=3,j=1不执行；i=3,j=2将（2）Q Sa b |ab|b代入（1） S Qc |c 得到（1）S Sa b c | abc| bc|c将(1)SSabc|abc|bc|c消除左递归后得到最终文法为：S( abc| bc|c)SSabcS|QRb|bR Sa|a由于Q，R为不可到达的非终结符，所以以Q，R 为左部的产生式规则应该除掉。虽然排列次序不同，产生式的规则也不同，但算法是等价的。 4.3确定的自顶向下分析技术确定的自顶向下分析技术的实现有两种。一种是递归子程序法，另一种是预测分析表的方法。下面就这两种分析技术进行讨论。4.3.1 递归子程序法递归子程序法是一种比较容易构造的语法分析方法。它要求文法满足LL（1）文法。它的实现思想就是对应文法中的每个非终结符，编写一个递归过程，每个过程的功能是识别该非终结符推出的串。当某个非终结符的产生式有多个候选时能够按照LL（1）的形式唯一地确定选择某个候选进行推导。递归分析方法有时也称为递归下降分析法。下面是一个文法的具体实例，例4.18 设文法的形式如下：(1) S(A)|aAb(2) Ae A |dS A(3)Ad A|该文法的是一个LL(1)文法。需要对非终结符编写三个过程。P(S)，P(A)，P(A)各个过程的流程图如图4-5所示。编写程序：子程序P（S）： read(ch) if ch=( then begin read(ch)；P(A)；If ch=)then goto Lelse errorendelse if cha then error else begin read(ch);P(A); If ch=b then goto L else error endL:read(ch) return子程序P(A):If ch= e then begin read(ch);goto L endIf ch d then errorP(S);L:P(A);return;子程序P(A):L:if ch=d then beginread(ch);goto Lend;else if ch=b then goto L else if ch=) then goto Lelse errorL:return例4.19 设有文法如下:SS;TSTTif e then S else S Tif e then S Ta试为其构造递归下降识别程序。【构造步骤】：1首先检查该文法是否满足适应的先决条件，既无左递归和无回溯性。显然该文法不是LL（1）文法。将该文法进行等价变换，变为LL（1）文法。SS;TSTTif e then S T T else S|Ta编写程序得到该文法的递归子程序void getsymbol( ).void error ( )void S( )T( );S1( )void S1( )if(sym=;) getsymbol( );T ( );S1( ); void T( )if (sym=a) getsymbol( );else if (sym=if) getsymbol( ); if (sym=e)getsymbol ( );if(sym=then) getsymbol ( );S( );T1( );else error( );else error( );void T1( ) If(sym=else) getsymbol();S( );void main( )getsymbol( );S( );只有在一个文法的所有非终结符转换图都是确定的情况下，才可以用它们来构造递归下降分析程序。所谓一个非终结符转换图是确定的，是指它的每个状态节点的所有射出连线均不同名。而且若存在以非终结符为标记的连线，那么该连线必须是这个状态接点惟一射出的连线。4.3.2 预测分析法递归子程序法是由一组子程序组成，语法分析的实现取决于递归子程序的实现。用确定的自顶向下分析时，在实现技术上还有另外一种方法，那就是预测分析技术。1预测分析技术的算法流程图预测分析技术又称LL（1）分析法。一个预测分析器有三部分构成：预测分析程序、先进先出栈和预测分析表。1预测分析技术的算法流程图预测分析技术又称LL（1）分析法。一个预测分析器有三部分构成：预测分析程序、先进先出栈和预测分析表。LL（1）分析器模型如图4-6所示。输入符号串，指要分析的输入符号串。为了分析算法的统一，需要在输入串的末尾放置一个特殊符号#。分析表M，它是一个二维表，可以用一个二维数组MA，a来表示。A是一个非终结符，a为终结符或句子括号#，矩阵元素MA，a中的内容是一条关于A的产生式，表明当用非终结符A向下推导时，面临输入符a时，所应采取的侯选产生式。当元素内容无产生式时，则表明用A为左边向下推导时不该出现的符号，因此元素内容为转向出错处理的信息。2控制程序描述将“#”和文法的开始符号依次压入栈中。把第一个输入符号读入a；do 把栈顶符号弹出并放入x中；if (xVT)if (x=a)将下一个输入字符读入a；else error( ); else if(Mx,a=xy1y2yk) 按逆序依次把yk，yk-1,、y1压入栈中； 输出“xy1y2yk”； else error( );while(x!= “ #”)3预测分析技术举例 现在以表达式文法为例构造预测分析表。表达式文法为：E E+T|TT T*F|FF i|(E)该文法很显然不是一个LL(1)文法，构造LL(1)文法，构造步骤如下：(1)将文法转换为LL(1)文法，先消除左递归，是文法变为：ET EE+T E|T F TT*F T|Fi|(E)(2)判断该文法是否是LL(1)文法1)FIRST(E)=(,i FIRST(E)=+,FIRST(T)=(,iFIRST(T)=*,FIRST(F)=(,i各非终结符的FOLLOW集合为：FOLLOW（E)=)，#FOLLOW（E)=)，#FOLLOW（T)=+，)，#FOLLOW（T)=+，)，#FOLLOW（F)=*，+，)，#求各个产生式的SELECT集合为：SELECT(ET E)=(,i SELECT(E+T E)=+ SELECT(E)=#, ) SELECT(T F T)=(,i SELECT(T *F T)=* SELECT(T)=+,),# SELECT(F(E)=( SELECT(Fi)=i 由上可知，该文法是一个LL(1)文法。例4.20 有映射程序设计语言中ifthenelse 语句的文法为:Si EtSeS| i EtS |aEb其中，else 遵从最近匹配原则.（1）试改造文法,并为之构造LL(1)分析表.（2）利用构造的分析表分析句子ibtibtaea，要求给出分析过程中每一 步的分析栈和输入串的变化以及输出信息。【解】（1）提取公共左因子得到：SiEtSS|aSeS|E b求出每个非终结符的FIRST集和FOLLOW集合。FIRST(S)=i ，aFIRST(S)=e,FIRST(E)=bFOLLOW（S）=e，#FOLLOW（S）=e,#FOLLOW（E）=tSELECT（S iEtSS）=i SELECT（S a）=aSELECT(S eS)=eSELECT(S )=FOLLOW(S)=e,#SELECT(Eb)=b构造分析表为表4-5所示：小 结自顶向下分析法的基本思想是从文法的识别符号开始出发，试图推导出输入符号串。虽然不是所有的上下文无关语言都是能被确定的自上而下分析器所识别，但是，能用确定的自上而下分析器进行分析的上下文无关文法已经有充分的能力去定义许多常用的高级语言，而且能构造有效的
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号