编译原理第五章

自顶向下语法分析第五章5.0概述语法分析是编译程序的核心部分语法分析的任务：1、识别由词法分析给出的单词符号序列是否是给定文法的正确句子；2、按照语言既定的语法规则，对字符串形式的源程序进行语法检查，并识别出相应的语法成分。语法分析的处理依据是语言的文法规则分析结果是识别出的无语法错误的语法成分，可以与语法树的形式来表示。语法分析的关键是句型识别问题设给定文法G和字符串（句子），检查、判断句子是否是文法G所能产生的合法的句子，同时检查和处理语法错误。语法分析器的作用及在编译程序中的作用scanner语法分析器语义分析。。。。。。。。。。。。。中间代码生成源程序源程序取下一个单词分析树源程序语法分析的方法分成两大类语法分析自顶向下分析方法自底向上分析方法确定的自顶向下分析方法不确定的自顶向下分析方法算符优先分析方法LR分析方法自顶向下语法分析也称面向目标的分析方法：从文法的开始符号出发推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，否则出错。确定的分析方法：对文法有一定的限制，方法简单、直观，便于实现，是常用的方法。不确定的分析方法：带回溯的分析方法，是一种穷举的试探方法，效率低、代价高，较少使用。5．1确定的自顶向下分析思想给定的条件是：1、已知文法条件；2、给出输入的字符串。判断该输入的字符串是已知文法的句子。判定的思路是：从文法开始符号出发，根据输入的符号唯一地确定选用哪个产生式替换相应的非终结符往下推导。最终与输入字符串相匹配。实际上，根据文法的特点（确切地讲根据产生式的不同特点），推导过程的复杂程度也不一样。如果文法有如下的特点：（1）每个产生式的右部都由终结符开始。（2）如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。对于这样的文法显然在推导过程中完全可以根据当前的输入符号决定选择那个产生式往下推导，也就是说分析过程是唯一确定的。例5.1若有文法G[S]:S→pA│qBA→cAd│aB→dB│b若输入串为pccadd。推导判断是否合法？文法是确定性的文法，但是被识别的句子可能是不符合文法的！如果文法有如下特点：产生式的右部不全是由终结符开始。如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。文法中无空产生式。如果左部相同，右部不同，但是右部的符号串可以推导出的首符号集不相交，因而，可以根据输入符号串判定相应的产生式进行推导。这样的推导过程仍然是确定的。例5-2：若有文法G[S]：S→ApS→BqA→aA→cAB→bB→dB判断符号串ccap表面看不确定，实际上确定！例5.2的推导过程如下：开始符号S的两个产生式的右部都不是以终结符开始；根据右部非终结符所推导出的首字符集，判断选择那个产生式；FIRST（Ap）={a,c}；FIRST(Bq)={b,d}；两个字符集不相交；唯一确定S→Ap作为选择。S→Ap→cAp→ccAp→ccap为推导过程。输入串ccap为可以接受。存在一个回溯的问题，即在替换某个非终结符时，存在多种选择，当选择某个推导到后面可能无解，必须退回重新选择。消除回溯或者避免回溯可以通过求解首字符集，判断首字符集不相交。

定义：设G=(VT，VN，S，P)是上下文无关文法。FIRST(α)={a│α*aβ，a∈VT，α，β∈V*}若α*ε，则规定ε∈FIRST(α)称FIRST(α)为α的开始符号集合或首字符集。文法G[S]：S→ApS→BqA→aA→cAB→bB→dB产生式左部分相同的右部分的首字符集都不相交。所以，该文法可以进行自顶向下的确定性分析。那么如果在产生式中存在空产生式，如何判定它可以确定的进行语法分析？例5．3若有文法G[S]：S→aA；S→d；A→bAS；A→ε。判断字符串：abd推导过程：SaAabASabεSabSabd当某个非终结符的产生式中含有空产生式时，它的非空产生式右部的首字符集两两不相交，并且在推导过程中紧跟在该非终结符右边可能出现的终结符也不相交，则仍可以构造确定的语法分析。这种情况下就要看该非终结符的后跟符号集（FOLLOW）。通常情况下，只需要考虑FIRST集合就可以了。但是，当产生式右部出现ε或者能够推导出ε，则应该考虑该产生式左部的非终结符的后跟字符集。后跟符号集（FOLLOW）定义：设G=(VT,VN,S,P)是上下文无关文法，A∈VN，S是开始符号。FOLLOW(A)={a│S*….Aa….，a∈VT，}若有S*….A，则规定#∈FOLLOW(A)#作为输入串的结束符号。假设文法中有形如下的产生式：A→αA→β若α和β不能同时推导为ε。如α不为ε，β可以为ε。在推导过程中，可以确定地替换A的条件是FIRST(α)∩(FIRST(β)UFOLLOW(A))=Φ事实上，在语法分析上还是追求确定的自上而下的分析方法。当确定首字符集和后跟字符集，就可以形成一个新的字符集：选择字符集SELECT。根据对选择字符集的判断就可以判定语法分析是否可以为确定的。给定上下文无关文法的产生式A→aA∈Vn,a∈V*，若α为非空的产生式，SELECT（A→α）=FIRST（α）若α包含空产生式，SELECT（A→α）=（FIRST（α）-{ε}）∪FOLLOW(A)通过FIRST（α）和FOLLOW(A)就可以求出SELECT（A→α）从而就可以判定针对这个非终结符是否可以进行确定的语法分析。我们将满足自顶向下分析技术条件的文法为LL（1）文法。一个上下文无关文法是LL（1）文法的充分必要条件是，对每个非终结符A的两个不同产生式，A→α；A→β，满足：SELECT（A→α）∩SELECT（A→β）=Φ；其中，α、β不能同时包含空产生式。LL（1）文法含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第二个L表明分析过程是用最左推导，1表明只需向右看一个符号便可以决定如何推导即选择哪个产生式进行推导。选择集合SELECT：例：S→aAS→dA→εA→bASSELECT(S→aA)=FIRST（α）={a}SELECT(S→d)=FIRST（d）={d}SELECT(A→bAS)={b}SELECT(A→ε)={a,d,#}SELECT(S→aA)∩SELECT(S→d)=SELECT(A→bAS)∩SELECT(A→ε)=可知文法为LL（1）文法，可用确定的自顶向下分析。例题S→pAS→qBA→cAdA→aB→dBB→b每个产生式右部都由终结符开始如果两个产生式有相同的左部,那么它们的右部由不同的终结符开始这是直观的、确定的分析方法的文法例题S→ApS→BqA→cAA→aB→dBB→b产生式右部不都由终结符开始如果两个产生式有相同的左部,那么它们的右部由不同的终结符或非终结符开始如果左部相同，右部的符号串可以推导出的首字符集合不相交文法中无空产生式这是隐蔽的，但是是确定的分析方法的文法例题S→aAS→dA→bASA→ε当某个非终结符的产生式中含有空产生式时，它的非空产生式右部的首字符集合两两不相交并且在推导过程中紧跟该非终结符右边可能出现的终结符集合也不相交仍然是确定的分析方法的文法后跟字符集合的求解一定要注意：它是针对某个非终结符的计算；它将来要用到以这个非终结符作为左部，并且能够推导出空的产生式在推导过程中，有可能出现在该非终结符后面的终结符。因为是推导，所以一定要从开始符号出发。特别要注意#，什么时候属于后跟字符集。例题S→aASS→bA→bAA→ε最后一个产生式可以推导出空，在将来分析过程中，就很有可能用到它的这个特点，因此，需要求出产生式左部非终结符的后跟字符集。这个产生式的SELECT集合，除了包括首字符集以外，还应考虑A的后跟字符集A的后跟字符集中不包括#，这是因为，从S出发进行推导，永远不会出现S→……A这样的形式5．2LL（1）文法的判别当我们需选用自顶向下分析技术时，首先必须判定所给文法是否是LL（1）文法。我们对任给文法需要计算FIRST、FOLLOW、SELECT集合，进而判别文法是否为LL（1）文法。SELECT是关于产生式的；FIRST包含两个情况：一是产生式右部；另一个是非终结符；FOLLOW是关于能推出空的产生式左部的非终结符的；求出能推出ε的非终结符利用一个以文法的非终结符个数为上界，每个非终结符为元素的一维数组。逐步扫描，确定能够推出ε的非终结符。计算FIRST集根据定义计算FIRST(α)={a│α*aβ,a∈VT,α、β∈V*}若α*ε，则规定ε∈FIRST(α)；对每个文法符号X∈V计算FIRST(X),有：若X∈VT,则FIRST(X)={X}；若X∈VN,且有产生式X→a……，a∈VT,则a∈FIRST(X)；若X∈VN,且X→ε

，则ε

∈FIRST(X)；若X∈VN,Y1,Y2,……,Yi都∈VN,且有产生式X→Y1,Y2,……,Yn,当Y1,Y2,……,Yi-1都*ε，则FIRST(Y1)-{ε}，FIRST(Y2)-{ε}，……，FIRST(Yi-1)-{ε}，FIRST(Yi)都包含在FIRST(X)中；当d)中的所有的Yi*ε，（i=1，2，…，n），则FIRST(X)=FIRST(Y1)FIRST(Y2)……FIRST(Yn){ε}.通常情况下，我们要求出所有非终结符的FIRST集合，这是为了将来求FOLLOW集合是用得上；重要的是求产生式右部符号串的FIRST集合，这是求SELECT集合的重要元素。S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c计算FIRST集根据关系图法计算每个文法符号对应图中一个节点，对应终结符的节点时用符号本身标记，对应非终结符的节点时用FIRST(A)标记。（这里A表示非终结符）如果文法中有产生式A→αXβ,且α*ε，则从对应A的节点到对应X的节点连一条射线弧；凡是从FIRST(A)节点有路径可到达的终结符节点所标记的终结符都为FIRST(A)成员；ε是否为FIRST(A)成员由直接方法判断。bcaFIRST(S)FIRST(B)FIRST(D)FIRST(A)FIRST(C)S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→cX可能是终结符，也可能是非终结符。计算FOLLOW集根据定义计算对文法中的每一个非终结符A∈VN,计算FOLLOW(A):设S为文法的开始符号，把{#}加入 FOLLOW(S)中；若A→αBβ是一个产生式，则把FIRST(β)的非空元素加入到FOLLOW(A)中；反复使用b)直到每个非终结符的FOLLOW集合不再扩大为止。这里要特别注意：当β*ε时，则FOLLOW(A)的内容也加入到FOLLOW(B)中，这是因为假如有：D→α1Aβ2A→αBβ的两个产生式，在推导过程中有：S*…α1Aβ2…

…α1αBβ

β2…事实上，往往我们先求出所有的非终结符的FOLLOW集合，然后根据产生式是否能推导出空来决定是否采用计算FOLLOW集根据关系图法计算文法G中的每个符号和“#”对应图中的一个节点，对应终结符的节点用符号本身标记，对应非终结符的节点，则用FOLLOW(A)或FIRST(A)标记；从开始符号S的FOLLOW(S)节点到“#”号的节点连接一个射线弧；如果文法中有产生式A→αBβX，且β*ε，则从FOLLOW(B)节点到FIRST(X)节点连接一射线弧，当X∈VT,则与X相连；如果文法中有产生式A→αBβ，且β*ε，则从FOLLOW(B)节点到FOLLOW(A)节点连接一射线弧；对每一个FIRST(A)节点，如果有产生式A→αXβ，且α

*ε，则从FIRST(A)到FIRST(X)连一射线弧，若X∈VT,则与X相连；凡是从FOLLOW(A)节点有路径可以到达的终结符或“#”号的节点，其所标记的终结符或“#”号即为FOLLOW(A)的成员。S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c#caFOLLOW(S)FIRST(B)FIRST(D)FOLLOW(A)FOLLOW(C)FOLLOW(B)FOLLOW(D)计算SELECT集根据FIRST集和FOLLOW集求SELECT集需要判断每个终结符是否可推导出空产生式。例题S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c首先，判断能推出ε的非终结符。求这个非中符的后跟字符集。有些，能够直观判断，有些，需要推导；求FIRST集合，这里需要两个步骤。先计算每个非终结符的FIRST集合；然后，再求每个产生式右部符号串的FIRST集合。我们需要结果是后者，但前者在计算后者是会用到；求FOLLOW集合，需要注意：FOLLOW集合一定是针对非终结符的；有些可以直观计算；有些要注意推导，A→αBβ形式时，如果β能推导出ε，则FOLLOW（A）也属于FOLLOW（B）例题S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c非终结符名称是否推出εFIRST集合FOLLOW集合S是b,a,ε#A是b,εa,c,#B是a,ε#C否b,a,c#D否a,c#例题产生式SELECT集合S→ABb,a,#S→bCbA→εa,c,#A→bbB→ε#B→aDaC→ADa,b,cC→bbD→aSaD→ccabc#S→AB→AB;→bC→ABA→εA→b→ε→εB→aD→εC→AD→AD;→b→ADD→aS→c5.3某些非LL（1）文法到LL（1）文法的等价交换确定的自顶向下分析要求对给定语言的文法必须是LL（1）形式。但是，不是所有的语言都有LL（1）文法。不是LL（1）文法的原因，要么是直接或间接左递归；要么含有左公共因子。左公共因子：文法中形如A→αβ|αγ直接左递归：A→Aβ；间接左递归：A→Bβ；B→Aα消除左递归或左公共因子，能否将非LL（1）文法转换成LL（1）文法？提取左公共因子若文法中含有形如：A→αβ|αγ的产生式，这导致了对相同左部的产生式其右部的FIRST集相交，不满足LL（1）文法的充分必要条件。将产生式A→αβ|αγ等价变换为：A→α（β|γ）引进新的非终结符A’，使产生式变换为：A→αA’；A’→β|γ一般形式为：A→αβ1|αβ2|αβ3|….|αβn提取左公因子：A→α（β1|β2|β3|….|βn）引进新非终结符A’：A→αA’；A’→β1|β2|….|βn若β1β2β3….βn中仍含有左公共因子，可再次提取，这样反复进行提取，直到引进新非终结符的有关产生式再无左公共因子为止。例5.6（提取左公共因子后为非LL（1））若文法G1的产生式为：（1）S→αSb（2）S→αS（3）S→ε；对（1）（2）提取左公共因子后得：S→αS（b|ε）S→ε；进一步变换为文法G‘1S→αSAA→bA→εS→ε；例5.7（提取左公共因子后为LL（1））若文法G2的产生式为：1、A→ad；2、A→Bc3、B→aA；4、B→bB产生式2的右部以非终结符开始，因此，左公共因子可能是隐含的。用其相同左部而右部以终结符开始的产生式进行相应替换。1、A→ad；2、A→aAc；3、A→bBc4、B→aA；5、B→bB提取1、2的左公共因子得：A→a（d|Ac）；A→bBc；B→aA；B→bB引进新非终结符A’，得文法G‘2A→aA’；A→bBc；A‘→d；A‘→Ac；B→aA；B→bB例5.8（提取左公共因子后，产生无用产生式，必须化简文法）若有文法G3的产生式为：1、S→aSd；2、S→Ac；3、A→aS；4、A→b用3、4中的右部替换2中的右部的A，得1、S→aSd；2、S→aSc；3、S→bc；4、A→aS；5、A→b对1、2提取左公共因子

S→aS（d|c）；引进新的非终结符A’后得1、S→aSA‘；2、S→bc；3、A’→d|c；4、A→aS；5、A→b非终结符A变成不可到达的符号，产生式4、5为无用的产生式。例5.9（不能在有限步骤内提取完左公共因子）若有文法G4的产生式为1、S→Ap|Bq；2、A→aAp|d；3、B→aBq|e用2、3的右部替换1中的A、B得1、S→aApp|aBqq；2、S→dp|eq3、A→aAp|d；4、B→aBq|e对1提取左共因子的S→a（App|Bqq）；引入新的非终结符S‘后得1、S→aS’；2、S→dp|eq；3、S’→App|Bqq；4、A→aAp|d；5、B→aBq|e；用4、5中的右部替换3中的A、B，再提取左共因子，不断进行。不一定每个文法的左公共因子都能在有限步骤内替换无左公共因子的文法。一个文法提取了左公共因子后，只解决了相同左部产生式右部的FIRST集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是LL（1）文法，否则还需要用LL（1）文法的判别方式进行判断才能确定是否为LL（1）文法。消除左递归一个文法含有下列形式的产生式时：a)A→Aβb)A→Bβ；B→Aα在a)中可称为含有左递归的规则或称为直接左递归；在b)中为文法中含有左递归或间接左递归；文法中只要含有a)或b)或者二者皆有均认为文法是左递归的。文法是左递归时不能采用自顶向下分析方法。例5.11有文法G6为：1、A→aB；2、A→Bb；3、B→Ac；4、B→d；若有输入串为adbcbcbc#，则分析过程的语法树如下：AaBAcBbdAaBAcBbAc……利用这样的推导不是不能推导出匹配，而是要不断地进行回溯。不是确定的分析方法。含有左递归的文法绝对不是LL（1）文法。不能用确定的自顶向下分析法。为了使某些含有左递归的文法经等价变换消除左递归后可能变成LL（1）文法，可采用下列变换公式：a)消除直接左递归，把直接左递归改写为右递归b）消除间接左递归，先将间接变直接，然后，按a）c）消除文法中一切左递归的算法。消除直接左递归，把直接左递归改写为右递归对文法：S→Sa；S→b可改写为：S→bS’；S’→aS’|ε新旧文法的语句集都为:{ban|n>=0}所以文法等价.消除间接左递归对文法：A→aB；A→Bb；B→Ac；B→d包含间接左递归：用1、2的右部代替产生式3的非终结符A得B→aBc；B→Bbc；B→d消除左递归后得B→（aBc|d）B’；B‘→bcB‘|ε

再把原来的1、2产生式加入得A→aB；A→Bb；B→（aBc|d）B’；B‘→bcB‘|ε

消除文法中一切左递归的算法1、把文法中的所有非终结符按某个顺序排序；如：A1，A2，A3，……，An2、从A1开始消除左部为A1的产生式的直接左递归，然后把左部为A1的所有规则的右部逐个替换左部为A2右部为A1开始的产生式中的A1，并消除左部为A2的产生式中的直接左递归。以此类推。3、去掉无用产生式。例有文法产生式为：（1）S→Qc|c；（2）Q→Rb|b；（3）R→Sa|a；该文法的每个非终结符互为间接左递归。一、若非终结符按S、Q、R排序左部为S的产生式无直接左递归，2中又不含S，所以将1的右部代入3中得到：4、R→Qca|ca|a；（至此1号非终结符解决完毕）解决2号非终结符Q，将2中的右部代入4得到：5、R→Rbca|ca|a；对5消除直接左递归得：R→（bca|ca|a）R’；R‘→bcaR’|ε最终文法变为：（1）S→Qc|c；（2）Q→Rb|b；（2）R→（bca|ca|a）R’；（4）R‘→bcaR’|ε二、若非终结符按R、Q、S排序则把3代入2：Q→Sab|ab|b；再将该产生式代入1得：S→Sabc|abc|bc|c；消除直接左递归，最终文法变为：S→（abc|bc|c）S’；S‘→abcS’|ε；Q→Rb|b；R→Sa|a5.4不确定的自顶向下分析思想由于相同左部的产生式的右部FIRST集交集不为空而引起回溯。由于相同左部非终结符的右部存在能推导出空产生式，且该非终结符FOLLOW集中含有其他右部FIRST集的元素。由于文法含有左递归而引起回溯5.5确定的自顶向下分析方法预测分析方法一个预测分析器由三个部分组成：预测分析程序、先进后出栈、预测分析器表。其中只有预测分析器表与文法有关。表驱动预测分析程序模型

Input#总控程序预测分析表stack预测分析表可用一个矩阵M(或称二维数组)表示。矩阵元素M[A,a]中的下标A表示非终结符，a为终结符或句子括号“#”，矩阵元素M[A,a]中的内容为存放着一条关于A的产生式，表明当用非终结符A向下推导时，面临输入符号a时，应采取的候选产生式，若无产生式，元素内容转向出错处理的信息。预测分析表构造算法1.对文法G的每个产生式Ａ

,若每个终结符或“#”用a表示；若aSELECT(Ａ

)，把Ａ

加至[A,a]中，2.把所有无定义的[A,a]标上“出错标志”。为了使表简化，其产生式左部可以不写入表中，表中空白处为出错。可以证明，一个文法G的予测分析表不含多重入口，当且仅当该文法是LL(1)的例：G[E]:E→E+T|TT→T*F|FF→i|(E)

解：(1)判断文法是否为LL(1)文法由于文法中含有左递归，所与必须先消除左递归，使文法变为：G[E]:(1)E→TE’(2)E’

→