第5章自顶向下语法分析方法

第5章自顶向下语法分析方法语法分析（SyntaxAnalysis）是编译程序的核心部分。词法分析只是将字符形式的源程序中的各个单词识别出来，形成单词的机内表示形式，但是这些单词串如何构成更大的语法成分——语句，那就由语法分析来完成。语法分析的主要任务就是“组词成句”，即在词法分析识别出单词串的基础上，根据语言的语法规则，识别出各类语法成分，如“语句”、“程序”等。将完成语法分析任务的程序称为语法分析程序，也称为语法分析器或简称分析器。程序设计语言的语法结构是用上下文无关文法描述的，因此，语法分析器的实现原理就是按所给定的文法G，识别输入符号串α是否为一个句子（即α∈L(G)成立吗？），同时检查和处理语法错误。语法分析的关键是句型识别问题。给定一串单词（即文法的终结符），怎样知道它是不是该文法产生的一个句子呢？可以利用推导，或者利用语法树来进行判断。一般来说，语法分析的过程就是为一个句子建立语法树的过程。语法分析的方法很多，按照建立语法树的不同方向，通常将语法分析分为两类，一类是自顶向下分析法，另一类是自底向上分析法。本章主要介绍自顶向下分析法。第5章教学内容语法分析的任务；确定的自顶向下语法分析的基本思想；LL(1)文法的定义和判别方法；非LL(1)文法到LL(1)文法的等价变换；确定的自顶向下分析方法：递归下降分析法预测分析法一、自顶向下的语法分析思想【自顶向下（top-down）分析法的基本思想】自顶向下语法分析的基本思想是以文法的开始符号为树根，采用最左推导，试图自上而下地为输入的单词串构造一棵语法树。若语法树的端末节点从左向右排列恰好是输入串，则该输入串就是文法的句子，否则就不是。这种分析过程实质是一种试探过程，是反复使用不同产生式来匹配输入串的过程。示例【例1】设有以下文法G1[S]:S→aABA→bA|cB→dBe|de输入串abbcde的最左推导如下：SaABabABabbABabbcBabbcde因此，输入串abbcde是该文法G1的句子。下面从建立语法树来看句子的推导过程。为了自顶向下地构造输入串abbcde的语法树，首先按文法的开始符号产生根节点S，再根据产生式规则自顶向下地生长这棵语法树。语法树的建立过程如图所示。SaABbAbAcde自顶向下分析法也称面向目标的分析方法，在对输入串进行最左推导的过程中，在选择产生式时其实是一种试探方法，如果每一步选择产生式来匹配的时候都能够每选必中，则这种方法称为确定的分析方法；否则在选择产生式时面临多种可能，不知道选择哪一个产生式合适，就是不确定的分析方法。因此自顶向下分析法又可分为确定的和不确定的两种，确定的分析方法对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。不确定的方法即带回溯的分析方法，这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因而极少使用。1.不确定的自顶向下分析不确定的自顶向下分析法的基本思想是，对任何输入串α试图用一切可能的办法，从文法的开始符号出发，自上而下的为它建立一棵语法树。如果试探成功，则α为相应文法的句子，否则α就不是文法句子。这种分析过程本质上是一种穷举试探过程，是反复使用不同规则，谋求匹配输入串的过程。因此这种匹配过程往往一次不能成功，需要重新匹配，称为回溯。引起回溯的原因在于文法中关于某个非终结符的产生式有多个时，而根据面临的输入符无法唯一确定选择哪个产生式来匹配，从而引起回溯。自顶向下分析法中存在的问题回溯问题左递归问题回溯问题回溯时需要恢复到出错点位置，删去曾经匹配过的符号，还包括一些语义处理。因此处理回溯是一项复杂的工作，在回溯时，要清除在回溯之前编译程序所做的大量记录工作，然后重新开始记录，这就降低了语法分析的效率。避免回溯是自顶向下语法分析中需要解决的问题之一。回溯的具体表现回溯具体表现为下列两种情况：1.由于相同左部的产生式的候选式的FIRST集交集不为空而引起回溯。2.由于相同左部非终结符的候选式存在能推导出ε的产生式，且该非终结符的FOLLOW集中含有其它候选式的FIRST集的元素。表现一示例由于相同左部的产生式的候选式的FIRST集交集不为空而引起回溯：【例2】设有文法G2[S]为：S→xAyA→**|*串x*y的分析过程SxAy**(S,x)选择产生式S→xAy当前要替换的非终结符当前要匹配的输入符(A,*)可选择两个产生式A→**或A→*SxAy*回溯：回到出错点，重新选择产生式A→*，成功原因上述文法发生回溯的原因就在于A的两个产生式的候选式的第一个符号都是*，从而根据输入符*来选择A的产生式时有多种可能，因此会引起回溯。即：关于A的产生式的可选集交集不为Ø。SELECT(A→**)∩SELECT(A→*)={*}表现二示例由于相同左部非终结符的候选式存在能推导出ε的产生式，且该非终结符的FOLLOW集中含有其它候选式的FIRST集的元素。【例3】文法G3：S→aASS→bA→bAA→ε对输入串ab#的试探推导过程SaASSaASbASaASεb原因上述文法发生回溯的原因就在于选择产生式A→ε相当于与A的后随符号FOLLOEW（A）＝{a,b}匹配，但是由于A的后随符号b与A的第一个候选式的第一个符号b相同，从而根据输入符b来选择A的产生式时有多种可能，因此会引起回溯。即：关于A的产生式的可选集交集不为Ø。SELECT(A→bA)∩SELECT(A→ε)={b}左递归问题【例4】算术表达式的文法G4[E]为：E→E＋T|TT→T*F|FF→i|（E）对输入串i*i+i进行试探推导EE+TE+TEE+TEE+TE+TE+T……结论当一个文法是左递归的，采用自顶向下分析法会使分析过程陷入无限循环之中。回溯会使语法分析动作不确定，而左递归会使语法分析程序陷入无限循环之中，这些都使得语法分析的动作是不确定的。不确定的语法分析方法――带回溯的自顶向下分析法――实际上是一种穷举的试探方法，当分析不成功时则推翻以前的分析退回到适当位置再重新试探其余候选式可能的推导，这样需要记录已选过的产生式，直到把所有可能的推导序列都试完仍不成功才能确认输入串不是该文法的句子而报错。由于在编译程序真正实现时往往是边分析边插入语义动作，因而带回溯的语法分析方法代价很高，效率很低，在实用编译程序中几乎不用，因此对它实现的详细算法不做介绍。2.确定的自顶向下的分析确定的自顶向下分析方法，首先要解决从文法的开始符号出发，如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导，或构造一棵相应的语法树。【例5】若有文法G5[S]：S→aABA→bBA→cAB→aB→d文法G2的句子acbad的自顶向下分析过程如下：示例一注意：#是输入结束符最左推导过程所选产生式输入串(当前要替换的非终结符,输入符)1Sacbad#(S,a)2aABS→aABacbad#(A,c)3acABA→cAacbad#(A,b)4acbBBA→bBacbad#(B,a)5acbaBB→aacbad#(B,d)6acbadB→dacbad#推导成功以上最左推导所建立输入串acbad的语法树如图所示。SaABcAbBad选择产生式是唯一的在第2步推导时，当前要替换的非终结符为A，面临的输入符为c，所以选择A的产生式来推导时，只能选产生式A→cA，而不能选A→bB。同样，在第5步推导时，当前要替换的非终结符为B，面临的输入符为d，所以选择B的产生式来推导时，只能选产生式B→d，而不能选B→a。这样就保证上述每一步推导都是确定的。文法的特点文法G5有以下两个特点：(1)每个产生式的右部都由终结符号开始；(2)如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。对于这样的文法显然在推导过程中完全可以根据当前要替换的非终结符和输入符号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。示例二【例6】若有文法G6[S]为：S→AaS→BbA→cA→dAB→eB→fB文法G6的句子ddca的自顶向下分析过程如下：最左推导过程所选产生式输入串(当前要替换的非终结符,输入符)1Sddca#(S,d)2AaS→Aaddca#(A,d)3dAaA→dAddca#(A,d)4ddAaA→dAddca#(A,c)5ddcaA→cddca#推导成功以上最左推导所建立输入串ddca的语法树如图所示。SAadAdAc文法的特点这个文法的特点是：（1）产生式的右部不全是由终结符开始。（2）如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。（3）文法中无空产生式。讨论对于产生式中相同左部含有非终结符开始的产生式，在推导过程中选用哪个产生式不像G2文法那样直观。对于输入串ddca，其第一个符号是d，这时从S出发选择S→Aa还是选择S→Bb时，需要知道Aa或Bb能推导出的首终结符号集合是什么（即Aad…，还是Bbd…）。若Aad…成立，则选择S→Aa往下推导；若Bbd…成立，则选择S→Bb往下推导；其它情况则为不确定推导或出错。＋＋＋＋首终结符号集【定义1】设G＝(VN,VT,P,S)是上下文无关文法，α是由非终结符与终结符组成的任意符号串，用FIRST(α)表示α的首终结符集，则FIRST(α)＝{a|αaβ,a∈VT,α,β∈(VN∪VT)*}若α＝ε，则规定FIRST(α)＝Ø(空集)。*求符号串Aa与Bb的首终结符集：因为Aaca，AadAa，所以FIRST(Aa)={c,d}。因为Bbeb，BbfBb，所以FIRST(Bb)={e,f}。但是FIRST(Aa)∩FIRST(Bb)=Ø因而可以根据当前的输入符号是属于哪个产生式右部的首终结符集而决定选择相应产生式进行推导，即当前要替换的非终结符为S，面临的输入符为d时，只能选择产生式S→Aa（因为d∈FIRST(Aa)）。这样仍然是确定的自顶向下分析。假如考虑文法中有ε_产生式时,将会产生什么问题呢？先看下面的例子：【例7】若有文法G7[S]：S→aABA→bBA→cAA→εB→aB→d文法G7的句子aca的自顶向下分析过程如下：最左推导过程所选产生式输入串(当前要替换的非终结符,输入符)1Saca#(S,a)2aABS→aABaca#(A,c)3acABA→cAaca#(A,a)4acεBA→εaca#(B,a)5acaB→aaca#推导成功以上最左推导所建立输入串aca的语法树如图所示。SaABcAεa讨论考查以上推导，在第3步到第4步的推导中，即acABacB时，因为当前要替换的最左非终结符为A，面临输入符为a，而关于A的产生式右部的首终结符集都不包含a，但有ε，因此对于a的匹配自然认为只能依赖于在可能的推导过程中A的后面的符号，所以这时选用产生式A→ε往下推导，而当前A后面的符号为B，B的产生式右部的首终结符集包含了a，所以可匹配。由此可以看出，当前输入符a与A后面的非终结符B匹配。当某一非终结符的产生式中含有ε_产生式时，它的非空产生式右部的首终结符集两两不相交，并与在推导过程中紧跟该非终结符右边可能出现的首终结符号集也不相交，则仍可构造确定的自顶向下分析。为此，我们为非终结符引入后随符号集的概念。后随符号集【定义2】设G＝(VN,VT,P,S)是上下文无关文法，A是G中的非终结符，用FOLLOW(A)表示A的后随符号集，则有：FOLLOW(A)＝{a|S…Aa…，a∈VT}特别地，若有S…A,则规定＃∈FOLLOW(A)。换句话说，FOLLOW(A)是指在G的各个句型中位于A后面的那些终结符或‘＃’。用‘＃’作为输入串的结束符，或称为句子括号，如：＃输入串＃。*对于例7中的文法G7，可用观察法求得FOLLOW(A)＝{a,d}。在自顶向下分析过程中，如果当前要替换的非终结符A面临输入符a或d时，应该选择产生式A→ε去匹配，而当面临b或c时，则分别选择产生式A→bB或A→cA去匹配。因此当文法中还有形如：A→αA→β的产生式时，其中A∈VN