自顶向下语法分析方法.ppt

第5章自顶向下语法分析方法 语法分析（Syntax Analysis）是编译程序 的核心部分。词法分析只是将字符形式的源 程序中的各个单词识别出来，形成单词的机 内表示形式，但是这些单词串如何构成更大 的语法成分语句，那就由语法分析来完 成。语法分析的主要任务就是“组词成句” ，即在词法分析识别出单词串的基础上，根 据语言的语法规则，识别出各类语法成分， 如“语句”、“程序”等。 将完成语法分析任务的程序称为语法分析 程序，也称为语法分析器或简称分析器。 程序设计语言的语法结构是用上下文无 关文法描述的，因此，语法分析器的实 现原理就是按所给定的文法G，识别输 入符号串是否为一个句子（即 L(G)成立吗？），同时检查和处理 语法错误。语法分析的关键是句型识别 问题。给定一串单词（即文法的终结符 ），怎样知道它是不是该文法产生的一 个句子呢？可以利用推导，或者利用语 法树来进行判断。一般来说，语法分析 的过程就是为一个句子建立语法树的过 程。 语法分析的方法很多，按照建立语法树 的不同方向，通常将语法分析分为两类 ，一类是自顶向下分析法，另一类是自 底向上分析法。 本章主要介绍自顶向下分析法，自底向 上分析法。 第4章教学内容 语法分析的任务； 确定的自顶向下语法分析的基本思想 ； LL(1)文法的定义和判别方法； 非LL(1)文法到LL(1)文法的等价变换 ； 确定的自顶向下分析方法： 递归下降分析法 预测分析法 自底向上语法分析的基本思想； 短语、直接短语和句柄的定义，以及 如何利用语法树寻找短语、直接短语 和句柄。 自底向上语法分析方法： 优先分析法 LR分析法 一、自顶向下的语法分析思想 【自顶向下（top - down ）分析法的基本思想 】自顶向下语法分析的基本思想是以文法的开 始符号为树根，采用最左推导，试图自上而下 地为输入的单词串构造一棵语法树。若语法树 的端末节点从左向右排列恰好是输入串，则该 输入串就是文法的句子，否则就不是。 这种分析过程实质是一种试探过程，是反 复使用不同产生式来匹配输入串的过程。 示例 【例4.1】设有以下文法G1S: SaAB AbA|c BdBe|de 输入串abbcde的最左推导如下： S aAB abAB abbAB abbcB abbcde 因此，输入串abbcde是该文法G1的句子。 下面从建立语法树 来看句子的推导过 程。为了自顶向下 地构造输入串 abbcde的语法树， 首先按文法的开始 符号产生根节点S， 再根据产生式规则 自顶向下地生长这 棵语法树。语法树 的建立过程如图所 示。 S a A B b A b A c d e 自顶向下分析法也称面向目标的分析方法，在 对输入串进行最左推导的过程中，在选择产生式 时其实是一种试探方法，如果每一步选择产生式 来匹配的时候都能够每选必中，则这种方法称为 确定的分析方法；否则在选择产生式时面临多种 可能，不知道选择哪一个产生式合适，就是不确 定的分析方法。 因此自顶向下分析法又可分为确定的和不确定 的两种，确定的分析方法对文法有一定的限制， 但由于实现方法简单、直观，便于手工构造或自 动生成语法分析器，因而仍是目前常用的方法之 一。不确定的方法即带回溯的分析方法，这种方 法实际上是一种穷举的试探方法，因此效率低， 代价高，因而极少使用。 1. 不确定的自顶向下分析 不确定的自顶向下分析法的基本思想是，对 任何输入串试图用一切可能的办法，从文法 的开始符号出发，自上而下的为它建立一棵 语法树。如果试探成功，则为相应文法的句 子，否则就不是文法句子。这种分析过程本 质上是一种穷举试探过程，是反复使用不同 规则，谋求匹配输入串的过程。因此这种匹 配过程往往一次不能成功，需要重新匹配， 称为回溯。 引起回溯的原因在于文法中关于某个非终结 符的产生式有多个时，而根据面临的输入符 无法唯一确定选择哪个产生式来匹配，从而 引起回溯。 自顶向下分析法中存在的问题 回溯问题 左递归问题 回溯问题 回溯时需要恢复到出错点位置，删去曾 经匹配过的符号，还包括一些语义处理 。因此处理回溯是一项复杂的工作，在 回溯时，要清除在回溯之前编译程序所 做的大量记录工作，然后重新开始记录 ，这就降低了语法分析的效率。避免回 溯是自顶向下语法分析中需要解决的问 题之一。 回溯的具体表现 回溯具体表现为下列两种情况： 1. 由于相同左部的产生式的候选式的 FIRST集交集不为空而引起回溯。 2.由于相同左部非终结符的候选式存在能 推导出的产生式，且该非终结符的 FOLLOW集中含有其它候选式的FIRST集的 元素。 表现一示例 由于相同左部的产生式的候选式的FIRST 集交集不为空而引起回溯： 【例46】设有文法G6S为： SxAy A*|* 串x*y的分析过程 S x A y * * (S,x) 选择产生式SxAy 当前要替换 的非终结符 当前要匹配 的输入符 (A, *) 可选择两个产生式 A*或A* S x A y * 回溯：回到出错点，重新 选择产生式A*，成功 原因 上述文法发生回溯的原因就在于A的两 个产生式的候选式的第一个符号都是* ，从而根据输入符*来选择A的产生式时 有多种可能，因此会引起回溯。 即：关于A的产生式的可选集交集不为 。 SELECT(A*)SELECT(A*)=* 表现二示例 由于相同左部非终结符的候选式存在能推导 出的产生式，且该非终结符的FOLLOW集中 含有其它候选式的FIRST集的元素。 【例如】例4.5的文法G5： SaAS Sb AbA A 对输入串ab#的试探推导过程 S a A S S a A S b A S a A S b 原因 上述文法发生回溯的原因就在于选择产 生式A相当于与A的后随符号 FOLLOEW（A）a,b匹配，但是由于A 的后随符号b与A的第一个候选式的第一 个符号b相同，从而根据输入符b来选择 A的产生式时有多种可能，因此会引起 回溯。 即：关于A的产生式的可选集交集不为 。 SELECT(AbA)SELECT(A)=b 左递归问题 【例4.7】算术表达式的文法G7E为： E ET|T T T*F| F F i |（E） 对输入串i*i+i进行试探推导 E E + T E + T E E + T E E + T E + T E + T 结论 当一个文法是左递归的，采用自顶向下 分析法会使分析过程陷入无限循环之中 。 回溯会使语法分析动作不确定，而左递 归会使语法分析程序陷入无限循环之中 ，这些都使得语法分析的动作是不确定 的。 不确定的语法分析方法带回溯的自顶向 下分析法实际上是一种穷举的试探方法 ，当分析不成功时则推翻以前的分析退回到 适当位置再重新试探其余候选式可能的推导 ，这样需要记录已选过的产生式，直到把所 有可能的推导序列都试完仍不成功才能确认 输入串不是该文法的句子而报错。由于在编 译程序真正实现时往往是边分析边插入语义 动作，因而带回溯的语法分析方法代价很高 ，效率很低，在实用编译程序中几乎不用， 因此对它实现的详细算法不做介绍。 2.确定的自顶向下的分析 确定的自顶向下分析方法，首先要解决 从文法的开始符号出发，如何根据当前的输 入符号(单词符号)唯一地确定选用哪个产生 式替换相应非终结符往下推导，或构造一棵 相应的语法树。 【例4.2】若有文法G2S： SaAB AbB AcA Ba Bd 文法G2的句子acbad的自顶向下分析过程如下 ： 示例一 注意：#是输入结束符 最左推导 过程 所选产生式输入串 (当前要替换的非 终结符,输入符) 1 Sacbad# (S,a) 2 aABSaABacbad#(A,c) 3 acAB AcAacbad#(A,b) 4 acbBBAbBacbad#(B,a) 5 acbaBBaacbad#(B,d) 6 acbadBdacbad#推导成功 以上最左推导所建立输入串acbad的语法树如图 所示。 S a A B c A b B a d 选择产生式是唯一的 在第2步推导时，当前要替换的非终结 符为A，面临的输入符为c，所以选择A 的产生式来推导时，只能选产生式 AcA，而不能选AbB。同样，在第5 步推导时，当前要替换的非终结符为B ，面临的输入符为d，所以选择B的产生 式来推导时，只能选产生式Bd，而不 能选Ba。这样就保证上述每一步推导 都是确定的。 文法的特点 文法G2有以下两个特点： (1)每个产生式的右部都由终结符号开始； (2)如果两个产生式有相同的左部，那么它 们的右部由不同的终结符开始。 对于这样的文法显然在推导过程中完全 可以根据当前要替换的非终结符和输入符 号决定选择哪个产生式往下推导，因此分 析过程是唯一确定的。 示例二 【例4.3】若有文法G3S为： SAa SBb Ac AdA Be BfB 文法G3的句子ddca的自顶向下分析 过程如下： 最左推导 过程 所选产生式输入串 (当前要替换的非 终结符,输入符) 1 Sddca#(S,d) 2 AaSAaddca#(A,d) 3 dAa AdAddca#(A,d) 4 ddAaAdAddca#(A,c) 5 ddcaAcddca#推导成功 以上最左推导所建立输入串ddca的语法树如图 所示。 S A a d A d A c 文法的特点 这个文法的特点是： （1）产生式的右部不全是由终结符开始。 （2）如果两个产生式有相同的左部，它们的 右部是由不同的终结符或非终结符开始。 （3）文法中无空产生式。 讨论 对于产生式中相同左部含有非终结符开始的 产生式，在推导过程中选用哪个产生式不像G2 文法那样直观。 对于输入串ddca，其第一个符号是d，这时从 S出发选择SAa还是选择SBb时，需要知道 Aa或Bb能推导出的首终结符号集合是什么（ 即Aad，还是Bbd）。若Aad成立 ，则选择SAa往下推导；若Bbd成立， 则选择SBb往下推导；其它情况则为不确定 推导或出错。 首终结符号集 【定义4.1】设G( VN, VT , P, S)是上下 文无关文法，是由非终结符与终结符 组成的任意符号串，用FIRST()表示 的首终结符集，则 FIRST() a|a, aVT,(VNVT ) * 若，则规定FIRST() (空集) 。 * 求符号串Aa与Bb的首终结符集： 因为Aaca，AadAa，所以FIRST(Aa)=c,d。 因为Bbeb，BbfBb，所以FIRST(Bb)=e,f。 但是FIRST(Aa) FIRST(Bb)= 因而可以根据当前的输入符号是属于哪个产生式 右部的首终结符集而决定选择相应产生式进行推 导，即当前要替换的非终结符为S，面临的输入 符为d时，只能选择产生式SAa（因为 dFIRST(Aa)）。这样仍然是确定的自顶向下分 析。 假如考虑文法中有_产生式时,将会产 生什么问题呢？先看下面的例子： 【例4.4】若有文法G4S： SaAB AbB AcA A Ba Bd 文法G4的句子aca的自顶向下分析过程如 下： 最左推导 过程 所选产生式输入串 (当前要替换的非 终结符,输入符) 1 Saca# (S,a) 2 aABSaABaca#(A,c) 3 acAB AcAaca#(A,a) 4 acBA aca#(B,a) 5 acaBaaca#推导成功 以上最左推导所建立输入串aca的语法树如图所 示。 S a A B c A a 讨论 考查以上推导，在第3步到第4步的推导中， 即acABacB时，因为当前要替换的最左非终结 符为A，面临输入符为a，而关于A的产生式右部 的首终结符集都不包含a，但有，因此对于a 的匹配自然认为只能依赖于在可能的推导过程 中A的后面的符号，所以这时选用产生式A 往下推导，而当前A后面的符号为B，B的产生式 右部的首终结符集包含了a，所以可匹配。由此 可以看出，当前输入符a与A后面的非终结符B匹 配。 当某一非终结符的产生式中含有_ 产生式时，它的非空产生式右部的首终 结符集两两不相交，并与在推导过程中 紧跟该非终结符右边可能出现的首终结 符号集也不相交，则仍可构造确定的自 顶向下分析。为此，我们为非终结符引 入后随符号集的概念。 后随符号集 【定义4.2】设G( VN, VT , P, S)是上下文无 关文法，A是G中的非终结符，用 FOLLOW(A)表示A的后随符号集，则有 ： FOLLOW(A)a|S Aa，aVT 特别地，若有SA,则规定FOLLOW(A) 。 换句话说，FOLLOW(A)是指在G的各个句 型中位于A后面的那些终结符或。 用作为输入串的结束符，或称为句子括号， 如：输入串。 * 对于例4.4中的文法G4，可用观察法求 得FOLLOW(A)a,d。在自顶向下分 析过程中，如果当前要替换的非终结符A 面临输入符a或d时，应该选择产生式 A去匹配，而当面临b或c时，则分别 选择产生式AbB 或AcA去匹配。 因此当文法中还有形如： A A 的产生式时，其中AVN, ,V*，当和 不同时推导出时，设, ,则当 FIRST()(FIRST()FOLLOW(A)） 时 ，对于非终结符A的替换仍可唯一地确定产 生式。 * SELECT集 在自顶向下分析过程中，对每个产生式 的选择都可由输入符来决定。综合以上 情况，为每个产生式定义一个可选集（ SELECT）如下： 可选集的定义 【定义4.3】给定上下文无关文法的产生式 A，AVN, V*,则定义： 如果, 则SELECT(A)= FIRST() ； 如果 ， 则SELECT(A)=FIRST()FOLLOW(A)； 特别地，如果， 则SELECT(A)=FOLLOW(A)。 * * 可选集的含义 可选集的含义如下：在自顶向下分析过 程中，如果当前要替换的最左非终结符 为A，面临输入符为aSELECT(A) 时，则可以选择产生式A来匹配。 因此，只要文法G的某一个非终结符A的 各个可选集互不相交，则语法分析程序 就可以根据当前输入符和A的可选集来 唯一正确的选择A的某个产生式去匹配 。 LL(1)文法 【定义4.4 】 一个上下文无关文法是LL(1)文法的 充分必要条件是关于同一非终结符的各个产生 式的可选集互不相交。 LL(1)文法的含义是：第一个L表明自顶向下分 析过程中是从左到右扫描输入串，第二个L表明 分析过程中采用最左推导，1表明只需向前查看 一个输入符号便可决定选择哪个产生式（规则 ）进行推导。 类似地，也可以有LL(k)文法，也就是需要向前 查看K个符号才能够确定选择哪个产生式。通常 采用K=1，个别情况采用K=2。 示例 【例4.4】文法G4S： SaAB AbB AcA A Ba Bd 计算可选集： SELECT(SaAB)a SELECT(AbB)b SELECT(AcA)c SELECT(A)FOLLOW(A)a,d SELECT(Ba)a SELECT(Bd)d 显然有： SELECT(AbB)SELECT(AcA)bc SELECT(AbB)SELECT(A)ba,d SELECT(AcA)SELECT(A)ca,d SELECT(Ba)SELECT(Bd)ad 所以，该文法是LL(1)文法。 示例 【例4.5】 设文法G5S为： SaAS Sb AbA A 因为有： SELECT(SaAS) FIRST(aAS)a SELECT(Sb) FIRST(b)b SELECT(AbA) FIRST(bA)b SELECT(A)FOLLOW(A)FIRST(S)a,b 所以： SELECT(SaAS)SELECT(Sb)ab SELECT(AbA)SELECT(A)ba， b 因此，该文法不是LL(1)文法，因而也就不可能 进行确定的自顶向下语法分析。 原因 从对输入串ab的下列两种不同推导 过程来看： 第一种推导过程可为： S aAS abAS abS 在句型abS中由于S不能推出，所以 第一种推导过程推不出ab； 第二种推导过程可为： S aAS aS ab 第二种推导过程推出了ab。 以上两种推导中，当第二步推导时当前 输入符为b，对句型aAS中的A用哪个产 生式推导不能唯一确定，也就是导致了 这个文法不能进行确定的自顶向下分析 。也即非LL（1）文法是不能进行确定 的自顶向下分析。 结论 确定的自顶向下语法分析要求文法是LL （1）文法。 二、LL（1）文法 LL(1)文法是一类可以进行确定的自顶向下语 法分析的文法。 根据LL(1)文法的定义，对于同一非终结符A 的任意两个产生式A和A，都要满足 ： SELECT(A)SELECT(A) 这样，当前非终结符A面临输入符a时，如果 aSELECT(A)，则可以选择产生式A 去准确匹配，从而解决回溯问题。 LL（1）文法的判别 采用确定的自顶向下分析技术时，首先 必须判别所给文法是否是LL（1）文法 。因而对任何给定的文法需要计算 FIRST、FOLLOW、SELECT集合，进而判 别该文法是否为LL（1）文法。 1.构造FIRST集 符号串的首终结符集为FIRST()， 定义： FIRST() a|a, aVT,(VNVT ) * 若，则规定FIRST()。 * 构造FIRST集的算法 对于文法符号串(VNVT )*，构造FIRST() 的算法如下：反复使用如下规则，直至FIRST集 不再增大为止。 若a,且a是终结符,则FIRST()a ； 若X,X是非终结符,且有Xb,则把b 加入FIRST ()中； 若X1X2Xk,X1, X2,Xk都是非终结符 ，首先把FIRST(X1)加入FIRST()中；若 X1X2Xi ,则把FIRST (Xi1Xi2Xk)加 入FIRST ()中，其中1ik1；若X1X2Xk ,则把FIRST()加入FIRST()中。 + + 在构造FIRST集的算法中，第条规则中的情 况最复杂，下面具体说明一下。 设ABC，A，B，C都是非终结符，则 分情况讨论： 若A，则FIRST()FIRST(A)； 若A，但B，则 FIRST()FIRST(A) FIRST(BC)； 若AB，但是C，则FIRST()FIRST (A) FIRST(B) FIRST(C)； 若ABC，但是，则 FIRST()FIRST(A)FIRST(B)FIRST(C ) FIRST()。 + + + + + 示例一 【例4.8】若文法G8S为： SAB SbC A Ab B BaD CAD Cb DaS Dc 求各非终结符的FIRST集 FIRST（S） FIRST（AB）FIRST（bC） ( SAB ，SbC ) FIRST（A）FIRST（B）b ( A ) b,ab b,a FIRST（A）FIRST（b）b ( Ab ) FIRST（B）FIRST（aD）a (BaD ) FIRST（C） FIRST（AD）FIRST（b） ( CAD ， Cb ) FIRST（A）FIRST（D）b ( A ) b,a,cb b,a,c FIRST（D） FIRST（aS）FIRST（c） ( DaS ，Dc ) aca,c 结果 所以最终求得： FIRST（S）b,a FIRST（A）b FIRST（B）a FIRST（C）b,a,c FIRST（D）a,c 2.构造FOLLOW集 非终结符A的后随符号集的定义为： FOLLOW(A)a|S Aa， aVT 特别地，若有S A,则规定 FOLLOW(A)。 * * 构造FOLLOW集的算法 对文法中每一非终结符A，构造FOLLOW(A)的 算法如下：反复使用如下规则，直至FOLLOW 集不再增大为止。 若A是文法的开始符号,则把输入结束符加入 FOLLOW(A)中； 若BAa,a是终结符,则把a加入FOLLOW(A) 中； 若BAX,X是非终结符,则把FIRST(X)加入 FOLLOW(A)中； 若BA或BA,且，则把FOLLOW(B) 加入FOLLOW(A)中。 * 注意 在构造FOLLOW集的算法中，将第条规 则解释一下： 如果有句型Ba，显然a是B的后随符 号，aFOLLOW(B)，而BA，用它往 下进行推导有SBaAa，那 么a也是A的后随符号，aFOLLOW(A)即 FOLLOW(B)中的后随符号都是FOLLOW(A) 中的后随符号。 + 同样的，如果有BA，且， 用它往下进行推导有： SBaAaAa， 即也有FOLLOW(B)中的后随符号都是 FOLLOW(A)中的后随符号。 * 示例一 【例4.8】若文法G8S为： SAB SbC A Ab B BaD CAD Cb DaS Dc 求各非终结符的FOLLOW集 FOLLOW(S) FOLLOW(D) ( S是文法的开始符号，DaS) FOLLOW(S) FOLLOW(A) FIRST（B）FIRST(D)FOLLOW(S) (SAB,且B , CAD) a ，c ， FOLLOW(B)FOLLOW(S) ( SAB) FOLLOW(C)FOLLOW(S) ( SbC ) FOLLOW(D) FOLLOW(B)FOLLOW(C) ( BaD ，CAD ) FOLLOW(S) 结果 所以最终求得： FOLLOW(S) FOLLOW(A)a ，c ， FOLLOW(B) FOLLOW(C) FOLLOW(D) 计算此文法各个产生式的可选集 SELECT集 首先考虑计算产生式的右部是终结符开头 的，其可选集只包含这一个终结符。 SELECT(SbC)FIRST(bC)b SELECT(Ab)FIRST(b)b SELECT(BaD)FIRST(aD)a SELECT(Cb)FIRST(b)b SELECT(DaS)FIRST(aS)a SELECT(Dc)FIRST(c)c 再来考虑计算产生式是_产生式，其可 选集为相应产生式左部的FOLLOW集 。 SELECT(A)FOLLOW(A) a ，c ， SELECT(B)FOLLOW(B) 再考虑复杂的情况，产生式的右部是非终结 符开头的，其可选集的计算要取决于相应产 生式右部的符号是否能够推导出。 AB SELECT(SAB) FIRST(AB)FOLLOW(S) b,a, AD SELECT(CAD) FIRST(AD) a,b,c * * 结果 最后将产生式的可选集整理如下： SELECT(SAB)b,a, SELECT(SbC)b SELECT(A)a ，c ， SELECT(Ab)b SELECT(B) SELECT(BaD)a SELECT(CAD)a,b,c SELECT(Cb)b SELECT(DaS)a SELECT(Dc)c 判断是否为LL(1)文法 因为： SELECT(SAB)SELECT(SbC) b,a, bb SELECT(A)SELECT(Ab) a ，c ，b SELECT(B)SELECT(BaD) a SELECT(CAD)SELECT(Cb) a,b,cb SELECT(DaS)SELECT(Dc) ac 结论：不是LL(1)文法 由于关于非终结符S的产生式的可选集 的交集不为空集，即意味着当前的最左 非终结符为S，面临的输入符为b时，可 以选择产生式SAB或者SbC来匹配 。同样，关于非终结符C的产生式的可 选集的交集也不为空集。因此，这个文 法的自顶向下语法分析动作是不确定。 所以，该文法不是LL(1)文法。 三、某些非LL(1)文法到LL(1) 文法的等价转换 LL(1)文法的性质： LL(1)文法是无二义性的； LL(1)文法不含左递归； LL(1)文法没有公共左因子。 非LL(1)文法的改造 消除左递归 消除回溯：提取左公因子 1.消除文法的左递归 当一个文法是左递归文法时，采用自顶向下 分析法会使分析过程进人无穷循环之中。文 法左递归是指文法中的某个非终结符A存在推 导A A，而自顶向下分析法是采用最左 推导，即每次替换的都是当前句型中的最左 非终结符，当试图用非终结符A去匹配输人串 时，结果使当前句型的最左非终结符仍然为 A，也就是说，在没有读进任何输人符号的情 况下，又重新要求A去进行新的匹配，于是造 成无穷循环。所以采用自顶向下分析法进行 语法分析需要消除文法的左递归性。 + 递归文法 【递归文法】递归文法是指对文法中任一 非终结符A，若存在一个推导序列，在 推出的符号串中又出现了该非终结符本 身，即AA，则该文法是递归的 。 若文法中对任一非终结符A有推导 AA，则称该文法是左递归的。 若文法中对任一非终结符A有推导 AA，则称该文法是右递归的。 + + + 左递归 左递归又可以分为直接左递归和间接左 递归。 【直接左递归】若文法中的某一产生式形 如AA，V*，则称该文法是直接 左递归的。 【间接左递归】若文法中存在某一非终结 符A，使得AA至少需要两步推导， 则称该文法是间接左递归的。 + 消除直接左递归的方法一 【方法一】只需将产生式进行改写，使之不含 左递归。为此需要引进一个新的非终结符， 把含有左递归的产生式改写成右递归的产生 式即可。 设有产生式是关于非终结符A的直接左递归 AA| （,V*，且不以A开头） 对A引入一个新的非终结符A，把上式改写为 ： A A AA| 改写前后产生式是等价的。 前式推导： A AA Ann 后式推导： AAAAnA n 从A推出的符号串的集合是相同的，也就是 说，它们是等价的。 + + 一般情况 若某文法中非终结符A的产生式形如： AA1 |A2 |An-1 |An|1 |2 |m-1 |m 其中： i、jV*，i=1,n，j=1,m，且j不以A开头， 则可用下述方法消除直接左递归： 引入一个新的非终结符A A 1A|2A|m-1A|mA A1A|2A|n-1A|nA| 示例 【例410】算术表达式文法 G7E： EE +T | T TT * F | F Fi |（E） 消除直接左递归后，文法变成： ETE E+T E| TFT T* FT| Fi |（E） 消除直接左递归的方法二 【方法二】采用扩充BNF表示法改写含直接左 递归的产生式。 在扩充的BNF表示中，有如下约定： 花括号 ： 表示符号串的可出现0次或多次，即表 示*。 ： 表示符号串的可出现m次至n次，m 为最小次数，n为最大次数。 【例如】AA | 可改写为： A m n 方括号 ：表示10即的出现可有可无，它用 来表示可供选择的符号串。 【例如】A | 可改写为： A 圆括号（ ） 利用圆括号可在产生式右部中提取公共因子 。 【例如】 A1 |2 |m-1 |m 可改写为： A（1 |2 |m-1 |m） 示例 【例411 】算术表达式的文法G7E为： E ET|T T T*F| F F i |（E） 对文法G7用扩充BNF表示法对其进行改 写。 示例 因为产生式EET|T表示E所生成的 符号串由T开头且后跟0个或多个十T； 而产生式TT * F|F表示T所生成的符 号串由F开头且后面跟0个或多个* F， 所以该文法可改写成如下形式： E T + T T F * F F i |（E） 消除间接左递归的方法 消除直接左递归是比较容易的，但是消 除间接左递归就不是那么容易的事。 【方法一】采用代入法把间接左递归变成 直接左递归。 【方法二】直接改写文法。 示例 【例412】设有文法G10S： S A| A S 因为S A S，所以S是一个间接递归 的非终结符。为了消除这种间接左递归，将 式代入式，即可得到与原文法等价的文 法（可以证明）： S S| 式是直接左递归的，可以采用前面介绍的 消除直接左递归的方法，对文法进行改写后 可得文法： S S S S| 2消除回溯 在自顶向下分析过程中，当某个非终结 符A对应多个候选式时，如果其中有几 个候选式的左端第一符号相同，那么就 会使得语法分析程序无法根据当前要替 换的非终结符和当前输人符唯一地决定 选用哪个候选式来替换A，只能采用试 探的办法，任选某个候选式去试探一次 。如果不能导致最终正确地匹配，只得 再换另一个候选式去试探，从而引起回 溯。 在自顶向下分析过程中，由于回溯需要 推翻前面的分析，包括已做的一大堆语 义工作，重新去进行试探，这样大大降 低了语法分析器的工作效率，因此，需 要消除回溯。 对于上述情况（即，同一非终结符有多 个候选式的首符相同），可以采用提“左 因子”的方法来改造文法，使得文法的每 个非终结符的各个候选式的首符都不相 同，从而可以消除上面所说的回溯现象 。 提取公共左因子 若A的产生式为： A1|2 经过提取公共左因子，原产生式变为 ： AA A1|2 一般情况 若A的产生式为： A1|2|k-1 |k 经过提取公共左因子，原产生式变为 ： AA A1|2|k-1 |k 如果m、n（其中1m、nk）中 仍然含有公共左因子，则可反复提取它 们的共同左因子，直到每个新引入的非 终结符的产生式再无公共左因子为止。 示例 【 例415】前面例46中的文法G6S 为： Sx A y A * * | * 关于A的产生式有公共左因子，提取公 共左因子a后，文法改写为： Sx A y A * A A * | 计算该文法的可选集 SELECT（Sx A y）x SELECT（A* A）* SELECT（A*）* SELECT（A）FOLLOW（A） FOLLOW（A）y 因为： SELECT（A*）SELECT（A） *y 所以，上述文法是LL（1）文法，这时再用自 顶向下分析方法分析符号串x*y，就不会产生 回溯了。 示例 【例415】设有文法G13S为： Sa S b Sab 关于S的产生式有公共左因子，提取公共左因 子a后，文法改写为： Sa（S b |b） 进一步变换为文法G13 S,其产生式为： Sa S SS b |b 计算该文法的可选集 SELECT（Sa S）a SELECT（SS b） FIRST（Sb）FIRST（S）a SELECT（Sb）b 因为： SELECT（SSb）SELECT（Sb ）ab 所以，上述文法是LL（1）文法，可以 进行确定的自顶向下的语法分析。 三、确定的自顶向下分析方法 特征根据下一个输入符号为当前要处 理的非终结符选择产生式 要求文法是LL(1)的 语法分析方法： 1 递归下降分析法 2 预测分析法 1.递归下降分析法 递归子程序法是比较简单直观易于构造 的一种语法分析方法。 实现思想：文法中每个非终结符对应一 个递归过程(子程序)，每个过程的功能 是识别由该非终结符推出的串，当某非 终结符的产生式有多个候选式时能够按 LL(1)形式可唯一地确定选择某个候选 式进行推导。 示例 【例410】算术表达式文法 G7E： EE +T | T TT * F | F Fi |（E） 消除直接左递归后，文法变成： ETE E+T E| TFT T * FT| Fi |（E） 计算FIRST集与FOLLOW集 各非终结符的FIRST 集为： FIRST(E)=(,i FIRST(E)=+ FIRST(T)=(,i FIRST(T)=* FIRST(F)=(,i 各非终结符的FOLLOW 集合为： FOLLOW(E)=), FOLLOW(E)=)， FOLLOW(T)=，)， FOLLOW(T)=,)， # FOLLOW(F)=*,， ),# 计算SELECT集 各产生式的 SELECT集为： SELECT(ETE)FIRST(TE)（,i SELECT(E 十TE) SELECT(E)FOLLOW(E) ）， SELECT(TFT)FIRST(FT)（，i SELECT(T * FT) * SELECT(T)FOLLOW(T)十，）， SELECT(F（E）) （ SELECT(Fi)i 该文法是LL(1)文法 因为： SELECT(E十TE)SELECT(E) SELECT(T * FT)SELECT(T) SELECT(F（E）)SELECT(Fi) 所以，该文法中关于同一个非终结符的产 生式的SELECT集两两不相交，因此，该 文法是LL（1）文法，可以进行确定的自 顶向下语法分析。 递归子程序E ETE 非终结符E对应的子程序为： E( ) T( ); E ( ); 递归子程序E E+T E| 非终结符E对应的子程序为： E ( ) if sym+ read(sym);T( ); E ( ); else if symFOLLOW(E) return; else error( ); 递归子程序T TFT 非终结符T对应的子程序为： T( ) F( ); T ( ); 递归子程序T T * FT| 非终结符T对应的子程序为： T ( ) if sym* read(sym);F( ); T ( ); else if symFOLLOW(T) return; else error( ); 递归子程序F Fi |（E） 非终结符F对应的子程序为： F ( ) if sym=i read(sym); else if sym ( read(sym); E( ); if sym) read(sym); else error( ); 主程序 main( ) read(sym); E( ); if (sym= =# ) printf(“分析成功”)； else printf(“分析失败”)； 示例 【例411 】算术表达式的文法G7E： E ET|T T T*F| F F i |（E） 对文法G7用扩充BNF表示法对其进行改 写成如下形式： E T + T T F * F F i |（E） 递归子程序E E T + T 非终结符E对应的子程序为： E( ) T( ); while (sym= =+) read(sym); T( ); 递归子程序T T F * F 非终结符T对应的子程序为： T( ) F( ); while (sym= =*) read(sym); F( ); 递归子程序F Fi |（E） 非终结符F对应的子程序为： F ( ) if sym=i read(sym); else if sym ( read(sym); E( ); if sym) read(sym); else error( ); 主程序 main( ) read(sym); E( ); if (sym= =# ) printf(“分析成功”)； else printf(“分析失败”)； 2.预测分析法 预测分析法用一个分析栈存放当前要替换的 非终结符的某个候选式的符号串（倒放在栈 内），当非终结符呈现在栈顶时，它就是当 前非终结符；此外，还使用一张矩阵形式的 预测分析表，它是根据可选集构造的，它的 入口指出了某非终结符和某终结符匹配时所 应选择的候选式和语义动作。预测分析程序 的总控程序就是利用栈顶符号和当前输人符 号对输人串进行预测分析，而预测的信息则 存放在预测分析表的相应入口里。 一个预测分析程序是由三个部分组成 总控程序（表驱动程序） 预测分析表 先进后出的语法分析栈 预测分析程序的模型 预测分析程序实际上就是一个下推自动 机，它是用下推自动机来识别输入符号 串的。 a1 a2 ai an # 输入串 总控程序 预测分析表 （LL(1)分析表） 栈顶符号 # x1 xn 分析栈 预测分析法表(LL(1)分析表) 表示:一个矩阵（或二维数组）MA ，a 行:对应文法的一个非终结符A 列:对应一个终结符a或输入结束符“”。 大小: mn, m是文法中非终结符数，n是终 结符数1（外加一个结束符“”）。 数组的值MA ，a ：存放着面临输人符号 a时，所应选择A的某条产生式，即指出当前 推导所应使用的产生式。数组中的空白入口 中应填人适当的出错处理子程序名或编号， 即此种情况下存在语法错误。 预测分析表的构造 预测分析法的实现关键在于预测分析表 。 预测分析表是指分析栈中的文法符号与 输入串中的符号的一种匹配关系，记为 MA，a，其中A为分析栈中的符号， a为输入符号。 可以由可选集直接来构造预测分析表。 预测分析表的构造算法 预测分析表的构造算法是： 对每个终结符aSELECT（A），把 A填入MA，a中； 把所有无定义的MA，a均填上“出错 标志”。 结论 上述算法可应用于任何文法G以构造它 的分析表M。但对于某些文法，有些MA ，a中可能有若干个产生式，或者说有 些MA，a可能是多重定义的。如果G是 左递归或回溯的，那么M至少含有一个 多重定义入口。因此，消除左递归和提 取公共左因子将有助于获得无多重定义 的分析表M。 可以证明： 一个文法G的预测分析表M不含多重定义入 口，当且仅当该文法是LL（l）文法。 示例 【例419】前述算术表达式的文法G7E 为： E TE E 十TE| T FT T *FT| F i |（E） 表达