编译原理第五章

1、自顶向下语法分析第五章5.0 概述概述v语法分析是编译程序的核心部分 v语法分析的任务：1、识别由词法分析给出的单词符号序列是否是给定文法的正确句子 ；2、按照语言既定的语法规则，对字符串形式的源程序进行语法检查，并识别出相应的语法成分 。v语法分析的处理依据是语言的文法规则 v分析结果是识别出的无语法错误的语法成分，可以与语法树的形式来表示。 v语法分析的关键是句型识别问题 v设给定文法G和字符串（句子），检查、判断句子是否是文法G所能产生的合法的句子，同时检查和处理语法错误。语法分析器的作用及在编译程序中的作用scanner语法分析器语义分析。中间代码生成源程序源程序取下一个单词分析树源程

2、序语法分析的方法分成两大类 语法分析语法分析自顶向下分析方法自底向上分析方法确定的自顶向下分析方法不确定的自顶向下分析方法算符优先分析方法LR分析方法v自顶向下语法分析也称面向目标的分析方法自顶向下语法分析也称面向目标的分析方法：从文法的开始符号出发推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，否则出错。v确定的分析方法确定的分析方法：对文法有一定的限制，方法简单、直观，便于实现，是常用的方法。v不确定的分析方法不确定的分析方法：带回溯的分析方法，是一种穷举的试探方法，效率低、代价高，较少使用。51 确定确定的自顶向下分析思想的自顶向下分析思想v给定的条件是：1、

3、已知文法条件；2、给出输入的字符串。判断该输入的字符串是已知文法的句子。v判定的思路是：从文法开始符号出发，根据输入的符号唯一地唯一地确定选用哪个产生式替换相应的非终结符往下推导。最终与输入字符串相匹配。v实际上，根据文法的特点（确切地讲根据产生式的不同特点），推导过程的复杂程度也不一样。v如果文法有如下的特点：（1）每个产生式的右部都由终结符开始。（2）如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。对于这样的文法显然在推导过程中完全可以根据当前的输入符号决定选择那个产生式往下推导，也就是说分析过程是唯一确定的。v例例5.1v若有文法GS:vSpAqBvAcAdavBdBbv若

4、输入串为pccadd。推导判断是否合法？文法是确定性的文文法是确定性的文法，但是被识别的法，但是被识别的句子可能是不符合句子可能是不符合文法的！文法的！v如果文法有如下特点：产生式的右部不全是由终结符开始。如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。文法中无空产生式。v如果左部相同，右部不同，但是右部的符号串可以推导出的首符号集不相交首符号集不相交，因而，可以根据输入符号串判定相应的产生式进行推导。这样的推导过程仍然是确定的。v例5-2：若有文法GS：vSApvSBqvAavAcAvBbvBdB1.判断符号串ccap表面看不确定，实际上确定！v例5.2的推导过程如下：

5、 开始符号S的两个产生式的右部都不是以终结符开始； 根据右部非终结符所推导出的首字符集，判断选择那个产生式； FIRST（Ap）=a,c；FIRST(Bq)=b,d；两个字符集不相交； 唯一确定SAp作为选择。vSApcApccApccap为推导过程。 v输入串ccap为可以接受。v存在一个回溯的问题，即在替换某个非终结符时，存在多种选择，当选择某个推导到后面可能无解，必须退回重新选择。1.消除回溯或者避免回溯可以通过求解首字符集，判断消除回溯或者避免回溯可以通过求解首字符集，判断首字符集不相交首字符集不相交。 v定义定义：设G=(VT，VN，S，P)是上下文无关文法。FIRST()=a* a

6、， aVT，V*若*，则规定FIRST()称FIRST()为的开始符号集合开始符号集合或首字符集首字符集。v文法GS：SApSBqAaAcABbBdBv产生式左部分相同的右部分的首字符集都不相交。所以，该文法可以进行自顶向下的确定性分析。v那么如果在产生式中存在空产生式，如何判定它可以确定的进行语法分析？v例53 若有文法GS：SaA；Sd；AbAS；A。 判断字符串：abdv推导过程：S aAabASabSabSabdv当某个非终结符的产生式中含有空产生式时，它的非空产生式右部的首字符集两两不相交，并且在推导过程中紧跟在该非终结符右边可能出现的终结符也不相交，则仍可以构造确定的语法分析。v这

7、种情况下就要看该非终结符的后跟符号集后跟符号集（FOLLOW）。通常情况下，只需要考虑通常情况下，只需要考虑FIRST集集合就可以了。但是，当产生式右部合就可以了。但是，当产生式右部出现出现或者能够推导出或者能够推导出，则应该考，则应该考虑该产生式左部的非终结符的后跟虑该产生式左部的非终结符的后跟字符集。字符集。v后跟符号集（后跟符号集（FOLLOW）定义：）定义：设G=(VT,VN,S,P)是上下文无关文法，AVN，S是开始符号。FOLLOW(A)=aS *.Aa.，a VT，若有S *.A，则规定# FOLLOW(A)v#作为输入串的结束符号。作为输入串的结束符号。v假设文法中有形如下的产

8、生式：假设文法中有形如下的产生式：AAv若和不能同时推导为。如不为，可以为。v在推导过程中，可以确定地替换A的条件是FIRST() ( FIRST() U FOLLOW(A) ) =v事实上，在语法分析上还是追求确定的自上而下的分析方法。 v当确定首字符集和后跟字符集，就可以形成一个新的字符集：选择字符集选择字符集SELECT。v根据对选择字符集的判断就可以判定语法分析是否可以为确定的。v给定上下文无关文法的产生式给定上下文无关文法的产生式Aa AVn,aV*，v若若为非空的产生式，为非空的产生式，SELECT（A）=FIRST（）v若若包含空产生式，包含空产生式，SELECT（A）=（FIR

9、ST（）-）FOLLOW(A)v通过通过FIRST（）和）和FOLLOW(A)就可以求出就可以求出SELECT（A）从而就可以判定针对这个非终结符是否可以）从而就可以判定针对这个非终结符是否可以进行确定的语法分析。进行确定的语法分析。v我们将满足自顶向下分析技术条件的文法为LL（1）文法。v一个上下文无关文法是一个上下文无关文法是LL（1）文法的充分必要条件）文法的充分必要条件是，对每个非终结符是，对每个非终结符A的两个不同产生式，的两个不同产生式，A；A，满足：，满足：SELECT（A）SELECT（A）=；其中，；其中，、不能同时包含空产生式。不能同时包含空产生式。vLL（1）文法含义是：

10、第一个）文法含义是：第一个L表明自顶向下分析是从表明自顶向下分析是从左向右扫描输入串，第二个左向右扫描输入串，第二个L表明分析过程是用最左表明分析过程是用最左推导，推导，1表明只需向右看一个符号便可以决定如何推表明只需向右看一个符号便可以决定如何推导即选择哪个产生式进行推导。导即选择哪个产生式进行推导。v选择集合选择集合SELECT：v例：例： SaA Sd A AbASvSELECT(SaA )=FIRST（）=avSELECT(Sd )=FIRST（d）=dv SELECT(AbAS )=bvSELECT(A)=a,d,#vSELECT(SaA ) SELECT(Sd )= vSELECT

11、(AbAS ) SELECT(A)= v可知文法为可知文法为LL（1）文法，可用确定的自顶向）文法，可用确定的自顶向下分析。下分析。例题vS pAvS qBvA cAdvA avB dBvB bl每个产生式右部都由终结符开始l如果两个产生式有相同的左部,那么它们的右部由不同的终结符开始l这是直观的、确定的分析方法的文法例题vS ApvS BqvA cAvA avB dBvB bl产生式右部不不都由终结符开始l如果两个产生式有相同的左部,那么它们的右部由不同的终结符或非终结符开始l如果左部相同，右部的符号串可以推导出的首字符集合首字符集合不相交l文法中无空产生式l这是隐蔽的，但是是确定的分析方这

12、是隐蔽的，但是是确定的分析方法的文法法的文法例题vS aAvS dvA bASvA l 当某个非终结符的产生式中含有空产生式时，它的非空产生式右部的首字符集合两两不相交l 并且在推导过程中紧跟该非终结符右边可能出现的终结符集合也不相交l 仍然是确定的分析方法的文法仍然是确定的分析方法的文法l 后跟字符集合的求解一定要注意：后跟字符集合的求解一定要注意： 它是针对某个非终结符的计算；它是针对某个非终结符的计算； 它将来要用到以这个非终结符作为左部，它将来要用到以这个非终结符作为左部，并且能够推导出空的产生式并且能够推导出空的产生式 在推导过程中，有可能出现在该非终结在推导过程中，有可能出现在该非

13、终结符后面的终结符。因为是推导，所以一符后面的终结符。因为是推导，所以一定要从开始符号出发。定要从开始符号出发。 特别要注意特别要注意# #，什么时候属于后跟字符，什么时候属于后跟字符集。集。例题vS aASvS bvA bAvA l 最后一个产生式可以推导出空，在将来分析过程中，就很有可能用到它的这个特点，因此，需要求出产生式左部非终结符的后跟字符集。这个产生式的SELECT集合，除了包括首字符集以外，还应考虑A的后跟字符集l A的后跟字符集中不包括#，这是因为，从S出发进行推导，永远不会出现S A这样的形式这样的形式52 LL（1）文法的判别）文法的判别v当我们需选用自顶向下分析技术时，首

14、先必须判定所给文法是否是LL（1）文法。 v我们对任给文法需要计算FIRST、FOLLOW、SELECT集合，进而判别文法是否为LL（1）文法。lSELECT是关于产生式的；lFIRST包含两个情况：一是产生式右部；另一个是非终结符；lFOLLOW是关于能推出空的产生式左部的非终结符的；求出能推出求出能推出的非终结符的非终结符v利用一个以文法的非终结符个数为上界，每个非终结符为元素的一维数组。逐步扫描，确定能够推出的非终结符。计算计算FIRST集集v根据定义计算FIRST()=a*a, a VT, 、V*若*，则规定FIRST()；对每个文法符号XV计算计算FIRST(X),有：有：v若若XV

15、T, 则则FIRST(X)=X；v若若XVN, 且有产生式且有产生式X a， a VT,则则a FIRST(X)；v若若XVN, 且且X ，则则 FIRST(X)；v若若XVN,Y1,Y2,Yi都都VN,且有产生式且有产生式XY1,Y2,Yn ,当当Y1,Y2,Yi-1都都*，则FIRST(Y1)-，FIRST(Y2)-， FIRST(Yi-1)-， FIRST(Yi)都包含在FIRST(X)中；a)当d)中的所有的Yi *，（i=1，2，n），则FIRST(X)= FIRST(Y1) FIRST(Y2) FIRST(Yn) .通常情况下，我们要求出所有非终结符的通常情况下，我们要求出所有非终

16、结符的FIRST集合，这是为了将来求集合，这是为了将来求FOLLOW集集合是用得上；重要的是求产生式右部符号串的合是用得上；重要的是求产生式右部符号串的FIRST集合，这是求集合，这是求SELECT集合的重集合的重要元素。要元素。vS ABvS bCvA vA bvB vB aDvC ADvC bvD aSvD c计算计算FIRST集集v根据关系图法计算每个文法符号对应图中一个节点，对应终结符的节点时用符号本身标记，对应非终结符的节点时用FIRST(A)标记。（这里A表示非终结符）如果文法中有产生式AX,且*，则从对应A的节点到对应X的节点连一条射线弧；凡是从FIRST(A)节点有路径可到达的

17、终结符节点所标记的终结符都为FIRST(A)成员；是否为FIRST(A)成员由直接方法判断。bcaFIRST(S)FIRST(B)FIRST(D)FIRST(A)FIRST(C)vS ABvS bCvA vA bvB vB aDvC ADvC bvD aSvD cX可能是终结符，也可能是非终结符。计算计算FOLLOW集集v根据定义计算v对文法中的每一个非终结符AVN,计算计算FOLLOW(A):设设S为文法的开始符号，把为文法的开始符号，把#加入加入FOLLOW(S)中；中；若AB是一个产生式，则把FIRST()的非空元素加入到FOLLOW(A)中；a)反复使用b)直到每个非终结符的FOLLO

18、W集合不再扩大为止。这里要特别注意：当 *时，则FOLLOW(A)的内容也加入到FOLLOW(B)中，这是因为假如有：D 1A2A B的两个产生式，在推导过程中有：S *1A2 1 B 2事实上，往往我们先求出所有的非终结符的FOLLOW集合，然后根据产生式是否能推导出空空来决定是否采用计算计算FOLLOW集集v根据关系图法计算文法G中的每个符号和“#”对应图中的一个节点，对应终结符的节点用符号本身标记，对应非终结符的节点，则用FOLLOW(A)或FIRST(A)标记；从开始符号S的FOLLOW(S)节点到“#”号的节点连接一个射线弧；如果文法中有产生式ABX，且 *，则从FOLLOW(B)节

19、点到FIRST(X)节点连接一射线弧，当XVT, 则与则与X相连；相连；如果文法中有产生式如果文法中有产生式AB，且 *，则从FOLLOW(B)节点到FOLLOW(A)节点连接一射线弧；对每一个FIRST(A)节点，如果有产生式AX，且 *，则从FIRST(A)到FIRST(X)连一射线弧，若XVT, 则与则与X相连；相连；a)凡是从凡是从FOLLOW(A)节点有路径可以到达的终结符或节点有路径可以到达的终结符或“#”号的节号的节点，其所标记的终结符或点，其所标记的终结符或“#”号即为号即为FOLLOW(A)的成员。的成员。vS ABvS bCvA vA bvB vB aDvC ADvC bv

20、D aSvD c#caFOLLOW(S)FIRST(B)FIRST(D)FOLLOW(A)FOLLOW(C)FOLLOW(B)FOLLOW(D)计算计算SELECT集集v根据FIRST集集和FOLLOW集集求SELECT集集v需要判断每个终结符是否可推导出空产生式。需要判断每个终结符是否可推导出空产生式。例题vS ABvS bCvA vA bvB vB aDvC ADvC bvD aSvD c首先，判断能推出首先，判断能推出的非终结符。求的非终结符。求这个非中符的后跟字符集。有些，能这个非中符的后跟字符集。有些，能够直观判断，有些，需要推导；够直观判断，有些，需要推导；求求FIRST集合，这里

21、需要两个步骤。集合，这里需要两个步骤。先计算每个非终结符的先计算每个非终结符的FIRST集合；集合；然后，再求每个产生式右部符号串的然后，再求每个产生式右部符号串的FIRST集合。我们需要结果是后者，集合。我们需要结果是后者，但前者在计算后者是会用到；但前者在计算后者是会用到；求求FOLLOW集合，需要注意：集合，需要注意：FOLLOW集合一定是针对非终结符的；集合一定是针对非终结符的；有些可以直观计算；有些可以直观计算；有些要注意推导，有些要注意推导，A B形式时，形式时，如果如果能推导出能推导出，则则FOLLOW（A）也属于也属于FOLLOW（B）例题vS ABvS bCvA vA bvB

22、 vB aDvC ADvC bvD aSvD c非终结符名称是否推出FIRST集合FOLLOW集合S是b,a, #A是b, a,c,#B是a, #C否b,a, c#D否a, c#例题产生式产生式SELECT集合集合S ABb,a,#SbCbA a,c,#A bbB #BaDaCADa,b,cCbbDaSaDccabc#SABAB; bCABA A b BaD CADAD; bADDaSc5.3 某些非LL（1）文法到LL（1）文法的等价交换v确定的自顶向下分析要求对给定语言的文法必须是LL（1）形式。v但是，不是所有的语言都有LL（1）文法。v不是LL（1）文法的原因，要么是直接或间接左递归；

23、要么含有左公共因子。v左公共因子：文法中形如A|v直接左递归：AA；v间接左递归：AB；BAv消除左递归或左公共因子，能否将非LL（1）文法转换成LL（1）文法？提取左公共因子提取左公共因子v若文法中含有形如：A|的产生式，这导致了对相同左部的产生式其右部的FIRST集相交，不满足LL（1）文法的充分必要条件。v将产生式A|等价变换为： A（|）v引进新的非终结符A，使产生式变换为： AA；A |v一般形式为： A1|2|3|.|nv提取左公因子： A（1|2|3|.|n）v引进新非终结符A： AA； A1|2|.|nv若123.n中仍含有左公共因子，可再次提取，这样反复进行提取，直到引进新非

24、终结符的有关产生式再无左公共因子为止。例5. 6 （提取左公共因子后为非LL（1）v若文法G1的产生式为：v（1）SSbv（2） SSv（3） S ；v对（1）（2）提取左公共因子后得：vSS（b| ）vS ；v进一步变换为文法G1vSSAvAbvA vS ；例5. 7（提取左公共因子后为LL（1）v若文法G2的产生式为：v1、Aad；2、ABcv3、BaA；4、BbBv产生式2的右部以非终结符开始，因此，左公共因子可能是隐含的。用其相同左部而右部以终结符开始的产生式进行相应替换。v1、 Aad； 2、AaAc；3、 AbBcv4、 BaA；5、BbBv提取1、2的左公共因子得：vAa（d|A

25、c）； AbBc； BaA；BbBv引进新非终结符A，得文法G2vAaA； AbBc； Ad； A Ac； vBaA；BbB例5.8（提取左公共因子后，产生无用产生式，必须化简文法）v若有文法G3的产生式为：v1、SaSd；2、SAc；v3、AaS；4、Abv用3、4中的右部替换2中的右部的A，得v1、 SaSd； 2、SaSc；3、 Sbc；v4、 AaS；5、Abv对1、2提取左公共因子v SaS（d|c）；v引进新的非终结符A后得v1、 SaSA；2、Sbc；v3、A d|c；v4、AaS；5、Abv非终结符A变成不可到达的符号，产生式4、5为无用的产生式。例5.9（不能在有限步骤内提取

26、完左公共因子）v若有文法G4的产生式为v1、SAp|Bq；2、AaAp|d；3、BaBq|ev用2、3的右部替换1中的A、B得v1、SaApp|aBqq；2、Sdp|eqv3、AaAp|d；4、BaBq|ev对1提取左共因子的vSa（App|Bqq）；v引入新的非终结符S后得v1、 SaS； 2、Sdp|eq ；3、S App|Bqq；v4、AaAp|d；5、BaBq|e；v用4、5中的右部替换3中的A、B，再提取左共因子，不断进行。v不一定每个文法的左公共因子都能在有限步骤内替换无左公共因子的文法。v一个文法提取了左公共因子后，只解决了相同左一个文法提取了左公共因子后，只解决了相同左部产生式

27、右部的部产生式右部的FIRST集不相交问题集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是LL（1）文法，否则还需要用LL（1）文法的判别方式进行判断才能确定是否为LL（1）文法。消除左递归v一个文法含有下列形式的产生式时：va) AAvb) AB ； BAv在a)中可称为含有左递归的规则或称为直接左递归；在b) 中为文法中含有左递归或间接左递归；文法中只要含有a)或b) 或者二者皆有均认为文法是左递归的。v文法是左递归时不能采用自顶向下分析方法。例5.11v有文法G6为：v1、AaB；2、ABb；v3、 BAc；4、 Bd；v若有输入串为adbcbcbc#，则分析过程

28、的语法树如下：AaBAcBbdAaBAcBbAc利用这样的推导不是不能推导出匹配，而是要不断地进行回溯。不是确定的分析方法。v含有左递归的文法绝对不是LL（1）文法。不能用确定的自顶向下分析法。v为了使某些含有左递归的文法经等价变换消除左递归后可能变成LL（1）文法，可采用下列变换公式：va) 消除直接左递归，把直接左递归改写为右递归vb）消除间接左递归，先将间接变直接，然后，按a）vc）消除文法中一切左递归的算法。消除直接左递归，把直接左递归改写为右递归v对文法：SSa；Sb 可改写为：vSbS；S a S |v新旧文法的语句集都为新旧文法的语句集都为:ban|n=0 所以文法等价所以文法等

29、价.消除间接左递归v对文法：AaB；ABb；BAc；B dv包含间接左递归：用1、2的右部代替产生式3的非终结符A得vBaBc； BBbc； B d 消除左递归后得vB（aBc|d）B；BbcB| 再把原来的1、2产生式加入得vAaB；ABb； B（aBc|d）B；BbcB| 消除文法中一切左递归的算法v1、把文法中的所有非终结符按某个顺序排序；v 如：A1，A2，A3，Anv2、从A1开始消除左部为A1的产生式的直接左递归，然后把左部为A1的所有规则的右部逐个替换左部为A2右部为A1开始的产生式中的A1，并消除左部为A2的产生式中的直接左递归。以此类推。v3、去掉无用产生式。例v有文法产生式

30、为：v（1）SQc|c；（2）QRb|b；（3）RSa|a；v该文法的每个非终结符互为间接左递归。v一、若非终结符按S、Q、R排序v左部为S的产生式无直接左递归，2中又不含S，所以将1的右部代入3中得到：4、RQca|ca|a；（至此1号非终结符解决完毕）v解决2号非终结符Q，将2中的右部代入4得到：5、 RRbca|ca|a；v对5消除直接左递归得： R（bca|ca|a）R；RbcaR|v最终文法变为：v（1）SQc|c；（2）QRb|b；v（2）R（bca|ca|a）R；（4）RbcaR|v二、若非终结符按R、Q、S排序v则把3代入2：QSab|ab|b；再将该产生式代入1得：vSSab

31、c|abc|bc|c；消除直接左递归，最终文法变为：vS（abc|bc|c）S；SabcS| ；QRb|b；RSa|a5.4 不确定的自顶向下分析思想v由于相同左部的产生式的右部FIRST集交集不为空而引起回溯。v由于相同左部非终结符的右部存在能推导出空产生式，且该非终结符FOLLOW集中含有其他右部FIRST集的元素。v由于文法含有左递归而引起回溯5.5 确定的自顶向下分析方法v预测分析方法v一个预测分析器由三个部分组成：预测分析程序、先进后出栈、预测分析器表。v其中只有预测分析器表与文法有关。表驱动预测分析程序模型测分析程序模型 Input Input #总控程序总控程序预测分析表预测分析表stackv预测分析表可用一个矩阵M(或称二维数组)表示。矩阵元素MA,a中的下标A表示非终结符， a为终结符或句子括号“#”，矩阵元素