编译原理第五章自顶向下语法分析方法.doc

第5章自顶向下语法分析方法第五章 自顶向下语法分析方法课前索引 【课前思考】为了了解自顶向下（自上而下）分析的一般过程和问题，请学员首先回顾在文法和语言一章中介绍的有关基本概念： 句子、句型和语言的定义是什么？ 什么叫最左推导？ 什么叫最右推导和规范推导？ 什么叫确定的自顶向下语法分析？ 自顶向下语法分析是从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。 确定的自顶向下语法分析中用的是哪种推导？ 在确定的自顶向下语法分析过程中，当以同一个非终结符为左部的产生式有多个不同右部时，如何选择用哪个产生式的右部替换当前的非终结符？ 确定的自顶向下语法分析对文法有何限制？ 【学习目标】确定的自顶向下分析方法虽对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。要求学员通过本章的学习后达到以下要求： 能够对一个给定的文法判断是否是LL(1)文法； 能构造预测分析表； 能用预测分析方法判断给定的输入符号串是否是该文法的句子； 能对某些非LL(1)文法做等价变换： 消除左递归 提取左公共因子可能会变成LL(1)文法。这样可扩大自顶向下分析方法的应用。 【学习指南】确定的自顶向下分析由于实现方法简单、直观、便于手工构造，因此，仍是目前常用的语法分析方法之一，尤其对小型编译器的实现较为适合。对初学编译技术的学员也较容易入门。确定的自顶向下分析要求文法是LL(1)的，所以，能否用确定的自顶向下分析方法构造语法分析器，首先必须对所给文法进行判断。由此构造 LL(1) 分析器的关键问题是对文法的LL(1)判别。而判断 LL(1)文法时用到文法符号串的开始符号集合（FIRST集）和非终结符的后跟符号集合（FOLLOW集）的计算。本章的学习要求学员对给定的文法能熟练、准确地计算出产生式右部符号串的开始符号集合和每个非终结符的后跟符号集合，只有这两个集合的元素计算准确无误，才能对LL(1)文法的判断得出正确结论，从而正确构造LL(1)分析表。对非LL(1)文法的等价变换特别要注意的是：消除了左递归、提取了左公共因子后不一定就能满足LL(1)文法的条件。 【难 重 点】语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)，目前语法分析常用的方法有自顶向下（自上而下）分析和自底向上（自下而上）分析两大类。本章将主要介绍确定的自顶向下分析思想和对文法的要求。确定的自顶向下分析要求文法满足LL(1)文法。本章主要介绍内容为： LL(1) 文法的定义和判别 非LL(1)文法的等价变换 确定的自顶向下分析方法 递归子程序法（已在第2章应用本章不重复） 预测分析方法重点: LL(1)文法的定义和判别 非LL(1)文法的等价变换 预测分析方法难点:对一个文法如何判断是否是LL(1)文法，由于在判断 LL(1)文法时用到文法符号串的开始符号集合（FIRST集）和非终结符后跟符号集合（FOLLOW集）的计算，而一般学员往往因概念不清或不够细心对这两个集合的计算常常出错，导致判断和分析结果的错误。 【知识结构】 语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)，目前语法分析常用的方法有自顶向下（自上而下）分析和自底向上（自下而上）分析两大类。而自底向上分析又可分为算符优先分析和LR分析，这三种分析方法各有优缺点。但都是当今编译程序构造的实用方法，我们将在本章和第6、7章着重介绍它们的实现原理和技术。自顶向下分析法也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。自顶向下分析法又可分为确定的和不确定的两种，确定的分析方法需对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。不确定的方法即带回溯的分析方法，这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因而极少使用，本章不做详细介绍。为了了解自顶向下（自上而下）分析的一般过程和问题我们首先回顾在“文法和语言”一章中介绍的关于句子、句型和语言的定义及什么叫最左推导、最右推导和规范推导的基本概念。在确定的自顶向下语法分析中用的是最左推导。句型、句子、语言的定义句型:有文法G S， 若S x，且x V*则称x是文法G S的句型。符号 表示经过0步或若干步的推导。句子:有文法GS，若Sx，且xVT*，则称x是文法G S的句子。例：GS： S0S1， S01可有推导 S0S100S11000S11100001111说明00001111是GS的句子。f5-1-2.swf最左（最右）推导：在推导的任何一步 (其中、是句型)，都是对中的最左（右）非终结符进行替换。最右推导被称为规范推导。由规范推导所得的句型称为规范句型。句型的分析 句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。 分析算法可分为：自上而下分析法： 从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。自下而上分析法： 从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。两种方法反映了两种不同的语法树的构造过程自上而下的语法分析f5-1-3.swf自下而上的语法分析f5-1-4.swf句型分析的有关问题 如何选择使用哪个产生式进行推导？假定要被替换的最左非终结符号是V，且左部为V的规则有n条：VA1|A2|An，那么如何确定用哪个右部去替换V呢？ 如何识别可归约的串？在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中寻找一个子串，看它是否能归约到文法的某个非终结符号，该子串称为“可归约串”。5.1 确定的自顶向下分析思想确定的自顶向下分析方法，首先要解决从某文法的开始符号出发，对给定的输入符号串如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导，或构造一棵相应的语法树，若能够推导出给定的输入符号串，或能构造出语法树其末端结点以从左向右的顺序连接正好为给定的输入符号串，则所给的输入符号串为该文法的句子。例 5.1 这个文法有以下两个特点： 每个产生式的右部都由终结符号开始。 如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。对于这样的文法显然在推导过程中完全可以根据当前的输入符号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。 现举例说明： 例 5.1若有文法G1S:S pA |qBA cAd|aB d B |c识别输入串w= pccadd是否是G1S的句子试探推导过程：SpApcAdpccAddpccadd试探成功。相应语法树为图5.1。 图 5.1 确定的自顶向下语 法分析树(一) 例5.2 文法的特点是： 产生式的右部不全是由终结符开始。 如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。 文法中无空产生式。对于产生式中相同左部含有非终结符开始的产生式时，在推导过程中选用哪个产生式不像例5.1文法那样直观，对于 W=ccap 为输入串时，其第一个符号是c，这时从S出发选择 SAp 还是选择 SBq，需要知道，Ap或Bq它们的开始符号集合是什么，若c是包含在Ap的开始符号集合中，且不包含在Bq的开始符号集合中，则选择 SAp 往下进行推导。同样若c是包含在Bq的开始符号集合中，且不包含在Ap的开始符号集合中，则选择 SBq 往下推导，其它情况则为不确定推导或出错。又如：例 5.2若有文法G2S:S Ap |BqA a|cA B b|dB识别输入串w=ccap是否是G2S的句子，那么试探推出输入串的推导过程为 ：SApcApccApccap试探推导成功。很容易构造相应语法树如图5.2。 图5.2 确定的自顶向下语法分析树(二)即说明ccap是例5.2文法的句子。例5.3 文法的特点是：文法中含有空产生式。由此可以看出，当某一非终结符的产生式中含有空产生式时，它的非空产生式右部的首符号集两两不相交，并与在推导过程中紧跟该非终结符后边可能出现的终结符集也不相交，则仍可构造确定的自顶向下分析。例 5.3若有文法G3S:S aA|dA bAS|识别输入串w=abd是否是G3S的句子试探推导出abd的推导过程为：SaAabASabSabd试探推导成功。 相应语法树为图5.3。图5.3 确定的自顶向下语法分析树(三)从以上推导过程中我们可以看到在第2步到第3步的推导中，即abASTabS时，因当前面临输入符号为d，而最左非终结符A的产生式右部的开始符号集合都不包含d，但有，因此对于d 的匹配自然认为只能依赖于在可能的推导过程中A的后面的符号，所以这时选用产生式A往下推导，而当前A后面的符号为S，S产生式右部的开始符号集合包含了d，所以可匹配。例 5.15.3都是确定的自上而下语法分析 ，由当前的输入符号能唯一确定选择哪个产生式进行推导。但并非任意一个文法都能用确定的自顶向下分析法。引起自顶向下分析不确定的原因有以下三种情况 由于相同左部的产生式的右部开始符号集合交集不为空而引起回溯。例5.4文法的特点是：关于A的产生式的不同右部开始符号集合都含有a，因此要替换非终结符A时，对当前输入符为a的情况，不能确定用产生式Aab 的右部还是用Aa的右部去替换。所以导致必须用带回溯的自顶向下分析，而带回溯的自顶向下分析是一个试探过程，当分析不成功时则推翻分析退回到适当位置再重新试探其余候选可能的推导，这样需要记录已选过的产生式，直到把所有可能的推导序列都试完仍不成功才能确认输入串不是该文法的句子而报错。例5.4若有文法G4S: SxAyAab|a若当前输入串为xay，则可能的推导树为图5.8(a)。进一步推导对A可选择Aab替换，得语法树为图5.8(b)。其中xa都已匹配，当前面临输入符为y与b不能匹配，所以将输入串指针退回到a，对A的替换重新选用下一个产生式Aa进行试探，如图5.8(c)。输入串中当前符a得到匹配，指针向前移动到y，与语法树中y匹配，推导成功。图 5.8 不确定的自顶向下语法分析树(一) 由于相同左部非终结符的右部存在能的情况且该非终结符的后跟符号的集合中含有其它右部开始符号集合的元素。例5.5文法的特点是：相同左部非终结符A的产生式有两个AbAS和A。当当前输入符为b时，推导对产生式的选择可有两种考虑： 用产生式AbAS的右部替换A，因为bAS的开始符号为b可与当前输入符b匹配。 用产生式A的右部替换A，这时期望用A的后跟符号b与当前输入符b匹配。这种情况就不能唯一的确定选择哪个产生式进行推导，其原因是A的后跟符号集合含有b，而A的另一产生式AbAS的开始符号集合中也含有b。它们的交集不为空，凡含有这种情况产生式的文法就不能用确定的自顶向下语法分析。例5.5若有文法G4S: (1) SaAS(2) Sb(3) AbAS(4) A对输入串ab#的试探推导，试推过程在图5.9(a), (b),(c)中给出。当面临a时，用产生式(1)推导，a得到匹配，输入串指针移到b，语法树中可用A向下推导，而对A的产生式可选(3)或(4)，先试选用(3)推导。 图5.9不确定的自顶向下语法分析树(二)这时b得到匹配，输入串指针向右移动，输入符已结束，但从语法树可以看出末端结点并非全是终结符，而且ab右部的非终结符ASS不能推出,所以可知推导是失败的，需回溯使输入指针退回到b，对A的推导改为选用下一个产生式A，对b用A的后跟符匹配。 由于文法含有左递归而引起回溯。例5.6文法的特点是：文法含有左递归，可见一个文法含有左递归时不能用确定的自顶向下分析。由以上例子可以看出，例5.4例5.6的文法不能用确定的自顶向下分析, 可用带回溯的自顶向下分析。例 56若有文法G6S:(1) SSa(2) Sb若推导baa#开始由于输入当前符是b,所以试图用(2)推导对应语法树为图5.10(a)。这时推导树的末端结点都是终结符，输入串未分析完，所以应重新选用产生式(1)来推导，对应语法树为图5.10(b)。语法树末端结点最左符号为非终结符，当前输入符号为b，所以选用(2)继续推导，得语法树为图5.10(c)。此时语法树最左边的符号为终结符b与当前符号匹配，语法树下一符号与输入串的下一符号都为a所以匹配，但语法树的末端结点只有两个终结符，而输入串还有剩余部分a#，所以要把第二步的推导回溯，输入串指针也恢复到第一个符号，对第二步推导的重新选择只有选择产生式(1)。相应语法树为图5.10(d)。这时语法树的最左末端结点为非终结符S，当前输入符为b，所以试用产生式(2)推导，得语法树为图5.10(e)。图 5.10 不确定的自顶向下语法分析树(三)当前输入符与语法树最左末端结点匹配，剩余的输入符aa与语法树其余的末端结点也逐个相匹配，最后遇到输入串结束符，所以分析成功。第5章自顶向下语法分析方法5.2 LL(1) 文法的定义和判别由5.1的例1例6可知，一个文法能否用确定的自顶向下分析与文法中相同左部的每个产生式右部的开始符号集合有关，当有右部能 时则与其左部非终结符的后跟符号集合也有关。此外在产生式中不存在左递归，本节将确切地定义满足确定的自顶向下分析条件的文法即LL(1)文法及LL(1)文法的判别，并介绍如何对非LL(1)文法进行等价变换问题，也就是消除一个文法中的左递归和左公共因子。一个文法中含有左递归和左公共因子绝对不是LL(1)文法，所以也就不可能用确定的自顶向下分析法，对此结论读者可以自行证明 。然而，某些含有左递归和左公共因子的文法在通过等价变换把它们消除以后可能变为LL(1)文法，但需要用LL(1)文法的定义判别，也就是说文法中不含左递归和左公共因子，只是LL(1)文法的必要条件。一个文法符号串的开始符号集合定义如下：定义5.1 设G=(VT，VN，S，P)是上下文无关文法FIRST()=a|a,aVT，,V*若,则规定FIRST()不难求出在例5.2文法G2中FIRST(Ap)=a,cFIRST(Bq)=b,d因此有 FIRST()(FIRST()=这样文法G2中，关于S的两个产生式的右部虽然都以非终结符开始，但它们右部的符号串可能推导出的首符号集合不相交，因而可以根据当前的输入符号是属于哪个产生式右部的首符号集合而决定选择相应产生式进行推导，因此仍能构造确定的自顶向下分析。例 5.2文法G2S:S Ap|BqA a|cA B b|dB 识别输入串w=ccap是否是G2S的句子推导过程：SApcApccApccap 推导成功因为：FIRST(S)=FIRST(A)FIRST(B)FIRST(A)=a，cFIRST(B)=b，dFIRST(Ap)=a，cFIRST(Bq)=b，d所以：FIRST(Ap)FIRST(Bq)=FIRST(a)FIRST(cA)=FIRST(b)FIRST(dB)=面临当前输入符号都能唯一确定选择哪个产生式进行推导。当一个文法中相同左部非终结符的右部存在能的情况则必须知道该非终结符的后跟符号的集合中是否含有其它右部开始符号集合的元素。 为此，我们定义一个文法非终结符的后跟符号的集合如下： 定义5.2 设 G=(VT，VN，S，P)是上下文无关 文法，AVN，S是开始符号FOLLOW(A)=a|SA,且aVT，aFIRST(),VT* ,V+若SA,且, 则#FOLLOW(A)。也可定义为：FOLLOW(A)=a|S Aa,a VT若有S A，则规定#FOLLOW(A)这里我们用#作为输入串的结束符，或称为句子括号，如：#输入串#。因此当文法中含有形如：AA的产生式时，其中AVN，,V*，当,不同时推导出空时，设,则当FIRST()( FIRST()FOLLOW(A)=时，对于非终结符A的替换仍可唯一地确定候选。综合以上情况可定义选择集合SELECT如下：定义5.3 给定上下文无关文法的产生式A, AVN,V*, 若,则SELECT(A)=FIRST()如果，则SELECT(A)=FIRST()FOLLOW(A)。 FIRST()表示FIRST()的非元素。更进一步可以看出能够使用自顶向下分析技术必须使文法满足如下条件，我们称满足条件的文法为LL(1)文法，其定义为：定义5.4 一个上下文无关文法是LL(1)文法的充分必要条件是：对每个非终结符A的两个不同产生式，A, A,满足SELECT(A)SELECT(A)=其中，不同时能LL（1）文法也可定义为:一个文法G是LL（1）的，当且仅当对于G的每一个非终结符A的任何两个不同产生式 A|，下面的条件成立： FIRST（）FIRST()=，也就是和推导不出以某个相同的终结符a为首的符号串；它们不应该都能推出空字 假若那么，FIRST（) FOLLOW（A）也就是，若则所能推出的串的首符号不应在FOLLOW(A)中（如例5.3）。这种表示与定义5.4相比计算步骤少，但不如定义5.4清晰。结论：LL(1)文法是无二义的。LL(1)文法的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第二个L表明分析过程中将用最左推导，1表明只需向右看一个符号便可决定选择哪个产生式(规则)进行推导，类似也可以有LL(K)文法，也就是需向前查看K个符号才可确定选用哪个产生式。通常采用K=1，个别情况采用K=2。回顾5.1的例5.1例5.3文法满足LL(1)文法，例5.4例5.6不满足LL(1)文法。对例5.5文法不是LL(1)文法，不能用确定的自顶向下分析。其原因我们也可以直观地对输入串W=ab的下列两种不同推导过程看出，其第一种推导过程可为：SaASabASabS,在句型abS中由于S不能推出,所以第一种推导过程推不出ab,而按第二种推导过程可为SaASaSab,第二种推导过程推出了ab。在上述两种推导过程中，第一个输入符a的匹配都用了产生式SaAS,得到句型aAS。这时按最左推导需用A的产生式右部替换A，而关于A的产生式有两个不同的右部，即有两个候选。当前的输入符号为b，第一种推导过程认为产生式AbA的右部开始符号为b,所以可用bA替换A，使b得到匹配，第二种推导过程认为A的后跟符集合中含有b，所以用产生式A进行推导，用替换了A，得到句型aS，符号b由S往下推导去匹配，而关于S的产生式恰有Sb，所以用它推导b得到匹配。以上两种推导中，当第二步推导时当前输入符为b，对句型aAS中的A用哪个产生式推导不能唯一确定，也就是导致了这个文法不能构造确定的自顶而下分析。请学员自己用LL（1）文法的定义，证明例5.1例5.3满足LL(1)文法, 例5.4例5.6不满足LL(1)文法。现给出例5.3和例5.5的证明供学员验证。 例5.3的文法G3S 为： SaASdAbASA不难看出由定义5.3可得：SELECT(SaA)=aSELECT(Sd)=dSELECT(AbAS)=bSELECT(A)=a,d,#, 所以 SELECT(SaA)SELECT(Sd)=ad=SELECT(AbAS)SELECT(A)=ba,d,#, =由定义5.4知例5.3文法是LL(1)文法，所以可用确定的自顶向下分析。而对例5.5 文法G5S为：SaASSbAbAA则 SELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=a,b所以 SELECT(SaAS)SELECT(Sb)=ab=SELECT(AbA)SELECT(A)=ba,b因此，例5.5文法不是LL(1)文法，因而也就不可能用确定的自顶向下分析。5.2.2 LL(1)文法的判别 当我们需选用自顶向下分析技术时，首先必须判别所给文法是否是LL(1)文法。因而我们对任给文法需计算FIRST、FOLLOW、SELECT集合，进而判别文法是否为LL(1)文法。在下面的讨论中我们假定所给文法是经过压缩的。 所谓文法是经过压缩的是指：文法中不得含有有害规则和多余规则有害规则：形如UU的产生式。会引起文法的二义性多余规则：指文法中任何句子的推导都不会用到的规则 文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。 文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。含有、情况非终结符的产生式都为多余规则。例：GS 为：1) SBe 2) BCe 3) BAf 4) AAe 5) Ae6) CCf7) Df经对每个产生式进行分析可发现非终结符D为不可到达，C为不可终止含D 、C的产生式 2)，6)，7)为多余规则应去掉。现举例说明判断LL(1)文法的步骤。例5.7若文法G7S为：SABSbCAAbBBaDCADCbDaSDc判别步骤：1. 求出能推出的非终结符首先建立一个以文法的非终结符个数为上界的一维数组，其数组元素为非终结符，对应每一非终结符有一标志位，用以记录能否推出。其值有三种情况：未定、是、否。例5.5所对应数组X 的内容如表5.1。 表5.1非终结符能否推出空的表非终结符SABCD初值第一次扫描第二次扫描未定是未定是未定是未定否未定否计算能推出的非终结符步骤如下： 将数组X 中对应每一非终结符的标记置初值为未定。 扫描文法中的产生式。(a) 删除所有右部含有终结符的产生式，若这使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应该非终结符的标记值改为否，说明该非终结符不能推出。(b) 若某一非终结符的某一产生式右部为，则将数组中对应该非终结符的标志置为是，并从文法中删除该非终结符的所有产生式。例中对应非终结符A、B的标志改为是。 扫描产生式右部的每一符号。(a) 若所扫描到的非终结符号在数组中对应的标志是是，则删去该非终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改是，并删除该非终结符为左部的所有产生式。(b) 若所扫描到的非终结符号在数组中对应的标志是否，则删去该产生式，若这使产生式左部非终结符的有关产生式都被删去，则把在数组中该非终结符对应的标志改成否。 重复，直到扫描完一遍文法的产生式，数组中非终结符对应的特征再没有改变为止。由中(a) 、(b)得知例中对应非终结符D的标志改为否，对应非终结符A、B的标志改为是。经过上述中(a)、(b)两步后文法中的产生式只剩下：SAB和CAD ，也就是只剩下右部全是非终结符串的产生式。再由中的(a)步扫描到产生式SAB时，在数组中A、B对应的标志都为是，删去后S的右部变为空，所以S对应标志置为是。最后由中的(b)扫描到产生式CAD时，其中，A对应的标志为是，D对应的标志是否，删去该产生式后，再无左部为C的产生式，所以C的对应标志改为否。 请学员自己写一个含有两个以上产生式的文法为例，用1中的算法计算能推出的非终结符。2. 计算FIRST集 根据定义计算由定义5.1 FIRST()=a|a,aVT，,V*,若,则规定FIRST() 对每一文法符号XV 计算FIRST(X)(a) 若XVT，则FIRST(X)X。(b) 若XVN，且有产生式Xa，aVT， 则 aFIRST(X)。(c) 若XVN，X,则FIRST(X)。(d) 若XVN；Y1，Y2，YiVN，且有产生式XY1 Y2 Yn；当Y1 Y2 Yi-1都时，(其中1in)，则FIRST(Y1)、FIRST(Y2)、FIRST(Yi-1)的所有非元素和FIRST(Yi)都包含在FIRST(X)中。(e) 当(d)中所有Yi,(i=1,2,n)，则FIRST(X)=FIRST(Y1)FIRST(Y2)FIRST(Yn)反复使用上述(b)(e)步直到每个符号的FIRST集合不再增大为止。求出每个文法符号的FIRST集合后也就不难求出一个符号串的FIRST集合。若符号串V*，=X1 X2 Xn,当X1不能,则置FIRST()= FIRST(X1)。若对任何j(1ji-1，2in), FIRST(Xj), 则FIRST()=(FIRST(Xj)FIRST(Xi)当所有FIRST(Xj)(1jn)都含有时，则FIRST()=(FIRST(Xj)请学员用算法1的结果由算法2计算例5.7文法各非终结符的FIRST集。例5.7 文法G7S为：SABSbCAAbBBaDCADCbDaSDc参考答案：FIRST(S)=FIRST(A)FIRST(B)b=b,a,FIRST(A)=b= b,FIRST(B)aa,FIRST(C)=FIRST(A) FIRST(D)FIRST(b)=b,a,cFIRST(D)=ac=a,c所以最终求得：FIRST(S)=a,b,FIRST(A)=b,FIRST(B)=a,FIRST(C)=a,b,cFIRST(D)=a,c每个产生式的右部符号串的开始符号集合为： FIRST(AB)=a,b,FIRST(bC)=bFIRST()FIRST(b)bFIRST(aD)=aFIRST(AD)=a,b,cFIRST(b)=bFIRST(aS)=aFIRST(c)=c也可以由关系图法求文法符号的FIRST集，可作为一种验证。其方法为：(a) 每个文法符号对应图中一个结点，对应终结符的结点时用符号本身标记，对应非终结符的结点用FIRST(A)标记。这里A表示非终结符。(b) 如果文法中有产生式AX，且,则从对应A的结点到对应X的结点连一条箭弧。(c) 凡是从FIRST(A)结点有路径可到达的终结符结点所标记的终结符都为FIRST(A)的成员。(d) 由判别步骤1确定是否为某非终结符FIRST集的成员，若是则将加入该非终结符的FIRST集中。图 5.4 计算FIRST集的关系图以例5.5文法为例计算FIRST集的关系图，如图5.4所示。由关系图法求得例5.5文法非终结符的FIRST集结果如下：FIRST(S)=b,a,FIRST(A)=b,FIRST(B)=a,FIRST(C)=a,b,cFIRST(D)=a,c与根据定义求得的结果相同。注意，请读者自己考虑，为什么不能把结点画在关系图中。3. 计算FOLLOW集 根据定义计算对文法中每一 AVN 计算 FOLLOW(A)(a) 设S为文法中开始符号，把#加入FOLLOW(S)中(这里#为句子括号)。(b) 若AB是一个产生式，则把FIRST()的非空元素加入FOLLOW(B)中。如果则把FOLLOW(A)也加入FOLLOW(B)中。(c) 反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。现计算例5.5文法各非终结符的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)FOLLOW(C)由以上最终计算结果得：FOLLOW(S)=#FOLLOW(A)=a,#,cFOLLOW(B)=#FOLLOW(C)#FOLLOW(D)=#对(b)中时，则把FOLLOW(A)也加入FOLLOW(B)中的解释：因为当有形如：D1A1AB的产生式时，A，B，DVN，1,1,V*，在推导过程中可能出现句型序列如：S 1A1 1B11B1 ；（因有）由定义5.2可知FIRST(1) FOLLOW(A)和FIRST(1)FOLLOW(B)，所以也就有FOLLOW(A)FOLLOW(B)。用关系图法求非终结符的FOLLOW集。(a) 文法G中的每个符号和#对应图中的一个结点，对应终结符和#的结点用符号本身标记。对应非终结符的结点(如AVN)则用FOLLOW(A)或FIRST(A)标记。(b) 从开始符号S的FOLLOW(S)结点到#号的结点连一条箭弧。(c) 如果文法中有产生式ABX, 且,则从FOLLOW(B)结点到FIRST(X)结点连一条弧，当XVT时，则与X相连。(d) 如果文法中有产生式AB, 且，则从FOLLOW(B)结点到FOLLOW(A)结点连一条箭弧。(e) 对每一FIRST(A)结点如果有产生式AX, 且, 则从FIRST(A)到FIRST(X)连一条箭弧。图 5.5计算FOLLOW集的关系图(f) 凡是从FOLLOW(A)结点有路径可以到达的终结符或#号的结点，其所标记的终结符或#号即为FOLLOW(A)的成员。现在对例5.5文法用关系图法计算FOLLOW集，如图5.5所示, 则得FOLLOW(S)=#FOLLOW(A)=a,c,#FOLLOW(B)=#FOLLOW(C)=#FOLLOW(D)=#与根据定义计算结果相同。此外，对文法符号FIRST集和FOLLOW集的计算还有关系矩阵法等，有兴趣的读者可参考有关书籍。4. 计算SELECT集对例5.7文法的FIRST集和FOLLOW集计算结果如表5.2。表5.2 文法的FIRST集和FOLLOW集表非终结符名是否T*FIRST集FOLLOW集S是b,a,#A是b,a,c,#B是a,#C否a,b,c#D否a,c#每个产生式的SELECT集合计算为：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,cbbSELECT(DaS)SELECT(Dc)=ac由LL(1)文法定义知该文法不是LL(1)文法，因为关于S和C的相同左部其产生式的SELECT集的交集不为空。5.2.3 非LL(1)文法的等价变换 在第5.1、5.2.1和5.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)文法的充分必要条件。现将产生式A|进行等价变换为：A（|）其中(，)为元符号，可进一步引进新非终结符A，去掉(，)使产生式变换为：AAA|写成一般形式为：A1|2|n，提取左公共因子后变为：A（1|2|n），再引进非终结符A，变为：AAA1|2|n若在i、j、k (其中1i，j，kn)中仍含有左公共因子，这时可再次提取，这样反复进行提取直到引进新非终结符的有关产生式再无左公共因子为止。练习若文法G1的产生式为：(1) SaSb(2) SaS(3) S请提取文法中的左公因子。参考答案：对产生式(1)、(2)提取左公因子后得：S aS(b|)S进一步变换为文法G1：SaSAAbAS练习若文法G2的产生式为：(1) Aad(2) ABc(3) BaA(4) BbB请提取文法中的隐式左公因子。参考答案：产生式(2)的右部以非终结符开始，因此左公共因子可能是隐式的，所以这种情况下对右部以非终结符开始的产生式，用其相同左部而右部以终结符开始的产生式进行相应替换，对文法G2分别用(3)、(4)的右部替换(2)中的B，可得：(1) Aad(2) AaAc(3) AbBc(4) BaA(5) BbB提取产生式(1)、(2)的左公共因子得：Aa(d|Ac)AbBcBaABbB引进新非终结符A，去掉(，)后得G2为：(1) AaA(2) AbBc(3) Ad(4) AAc(5) BaA(6) BbB不难验证经提取左公共因子后文法G1仍不是LL(1)文法。而文法G2变成LL(1)文法，因此文法中不含左公共因子只是LL(1)文法的必要条件。值得注意的是对文法进行提取左公共因子变换后，有时会使某些产生式变成无用产生式，在这种情况下必须对文法重新压缩(或化简)。练习若有文法G3的产生式为：(1) SaSd(2) SAc(3) AaS(4) Ab参考答案：用产生式(3)、(4)中右部替换产生式(2)中右部的A，文法变为：(1) SaSd(2) SaSc(3) Sbc(4) AaS(5) Ab对(1)、(2)提取左公共因子得：SaS(d|c)引入新非终结符A后变为：(1) SaSA(2) Sbc(3) Ad|c(4) AaS(5) Ab显然，原文法G3中非终结符A变成不可到达的符号，产生式(4)、(5)也就变为无用产生式，所以应删除。此外也存在某些文法不能在有限步骤内提取完左公共因子。练习若有文法G4的产生式为：(1) SAp|Bq(2) AaAp|d(3) BaBq|e用(2)、(3)产生式的右部替换(1)中产生式的A、B使文法变为：(1) SaApp|aBqq(2) Sdp|eq(3) AaAp|d(4) BaBq|e对(1)提取左公共因子则得：Sa(App|Bqq)再引入新非终符S结果得等价文法为：(1) SaS(2) Sdp|eq(3) SApp|Bqq(4) AaAp|d(5) BaBq|e同样分别用(4)、(5)产生式的右部替换(3)中右部的A、B再提取左公共因子最后结果得：(1) SaS(2) Sdp|eq(3) SaS(4) Sdpp|eqq(5) SAppp|Bqqq(6) AaAp|d(7) BaBq|e可以看出若对(5)中产生式A、B继续用(6)、(7)产生式的右部替换，只能使文法的产生式愈来愈多无限增加下去，但不能得到提取左公共因子的预期结果。由上面练习所举例子可以说明以下问题： 不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法，上面文法G4就是如此。 一个文法提取了左公共因子后，只解决了相同左部产生式右部的FIRST集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是LL(1)文法，否则还需用LL(1)文法的判别方式进行判断才能确定是否为LL(1)文法。 2. 消除左递归设一个文法含有下列形式的产生式。1)AA AVN，V*2)ABBA A,BVN, ,V*可称含1)中产生式的文法为含有左递归的规则或称直接左递归的。含2)中产生式的文