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

第第5章自顶向下语法分析方法章自顶向下语法分析方法 语法分析（语法分析（Syntax AnalysisSyntax Analysis）是编译程序）是编译程序的核心部分。词法分析只是将字符形式的源程的核心部分。词法分析只是将字符形式的源程序中的各个单词识别出来，形成单词的机内表序中的各个单词识别出来，形成单词的机内表示形式，但是这些单词串如何构成更大的语法示形式，但是这些单词串如何构成更大的语法成分成分语句，那就由语法分析来完成。语法语句，那就由语法分析来完成。语法分析的主要任务就是分析的主要任务就是“组词成句组词成句”，即在词法，即在词法分析识别出单词串的基础上，根据语言的语法分析识别出单词串的基础上，根据语言的语法规则，识别出各类语法成分，如规则，识别出各类语法成分，如“语句语句”、“程序程序”等。等。将完成语法分析任务的程序称为语法分析程将完成语法分析任务的程序称为语法分析程序，也称为语法分析器或简称分析器。序，也称为语法分析器或简称分析器。程程序序设设计计语语言言的的语语法法结结构构是是用用上上下下文文无无关关文文法法描描述述的的，因因此此，语语法法分分析析器器的的实实现现原原理理就就是是按按所所给给定定的的文文法法G G，识识别别输输入入符符号号串串是是否否为为一一个个句句子子（即即L(G)L(G)成成立立吗吗？），同同时时检检查查和和处处理理语语法法错错误误。语语法法分分析析的的关关键键是是句句型型识识别别问问题题。给给定定一一串串单单词词（即即文文法法的的终终结结符符），怎怎样样知知道道它它是是不不是是该该文文法法产产生生的的一一个个句句子子呢呢？可可以以利利用用推推导导，或或者者利利用用语语法法树树来来进进行行判判断断。一一般般来来说说，语语法法分分析析的的过过程程就就是是为一个句子建立语法树的过程。为一个句子建立语法树的过程。语语法法分分析析的的方方法法很很多多，按按照照建建立立语语法法树树的的不不同同方方向向，通通常常将将语语法法分分析析分分为为两两类类，一一类类是是自自顶顶向向下下分分析析法法，另另一一类类是是自自底底向上分析法。向上分析法。本本章章主主要要介介绍绍自自顶顶向向下下分分析析法法，自自底底向向上分析法。上分析法。第第4章教学内容章教学内容语法分析的任务；语法分析的任务；确定的自顶向下语法分析的基本思想；确定的自顶向下语法分析的基本思想；LL(1)LL(1)文法的定义和判别方法；文法的定义和判别方法；非非LL(1)LL(1)文法到文法到LL(1)LL(1)文法的等价变换；文法的等价变换；确定的自顶向下分析方法：确定的自顶向下分析方法：递归下降分析法递归下降分析法预测分析法预测分析法自底向上自底向上语法分析的基本思想；语法分析的基本思想；短短语语、直直接接短短语语和和句句柄柄的的定定义义，以以及及如如何何利利用用语语法法树树寻寻找找短短语语、直直接接短短语语和和句句柄。柄。自底向上语法自底向上语法分析方法：分析方法：优先分析法优先分析法LRLR分析法分析法一、一、自顶向下的语法分析思想自顶向下的语法分析思想【自自顶顶向向下下（top top-down down）分分析析法法的的基基本本思思想想】自自顶顶向向下下语语法法分分析析的的基基本本思思想想是是以以文文法法的的开开始始符符号号为为树树根根，采采用用最最左左推推导导，试试图图自自上上而而下下地地为为输输入入的的单单词词串串构构造造一一棵棵语语法法树树。若若语语法法树树的的端端末末节节点点从从左左向向右右排排列列恰恰好好是是输输入入串串，则则该该输输入入串串就就是是文法的句子，否则就不是。文法的句子，否则就不是。这这种种分分析析过过程程实实质质是是一一种种试试探探过过程程，是是反反复复使用不同产生式来匹配输入串的过程。使用不同产生式来匹配输入串的过程。示例示例【例例4.1】设有以下文法设有以下文法G1S:SaABAbA|cBdBe|de输入串输入串abbcdeabbcde的最左推导如下：的最左推导如下：S S aAB aAB abAB abAB abbAB abbAB abbcB abbcB abbcdeabbcde因此，输入串因此，输入串abbcdeabbcde是该文法是该文法G G1 1的句子。的句子。下下面面从从建建立立语语法法树树来来看看句句子子的的推推导导过过程程。为为了了自自顶顶向向下下地地构构造造输输入入串串abbcdeabbcde的的语语法法树树，首首先先按按文文法法的的开开始始符符号号产产生生根根节节点点S S，再再根根据据产产生生式式规规则则自自顶顶向向下下地地生生长长这这棵棵语语法法树树。语语法法树树的的建建立过程如图所示。立过程如图所示。SaABbAbAcde 自顶向下分析法也称面向目标的分析方法，在对自顶向下分析法也称面向目标的分析方法，在对输入串进行最左推导的过程中，在选择产生式时其输入串进行最左推导的过程中，在选择产生式时其实是一种试探方法，如果每一步选择产生式来匹配实是一种试探方法，如果每一步选择产生式来匹配的时候都能够每选必中，则这种方法称为确定的分的时候都能够每选必中，则这种方法称为确定的分析方法；否则在选择产生式时面临多种可能，不知析方法；否则在选择产生式时面临多种可能，不知道选择哪一个产生式合适，就是不确定的分析方法。道选择哪一个产生式合适，就是不确定的分析方法。因此自顶向下分析法又可分为确定的和不确定的因此自顶向下分析法又可分为确定的和不确定的两种，确定的分析方法对文法有一定的限制，但由两种，确定的分析方法对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。不确语法分析器，因而仍是目前常用的方法之一。不确定的方法即带回溯的分析方法，这种方法实际上是定的方法即带回溯的分析方法，这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因而一种穷举的试探方法，因此效率低，代价高，因而极少使用。极少使用。1.1.不确定的自顶向下分析不确定的自顶向下分析不确定的自顶向下分析法的基本思想是，对任不确定的自顶向下分析法的基本思想是，对任何输入串何输入串试图用一切可能的办法，从文法的试图用一切可能的办法，从文法的开始符号出发，自上而下的为它建立一棵语法开始符号出发，自上而下的为它建立一棵语法树。如果试探成功，则树。如果试探成功，则为相应文法的句子，为相应文法的句子，否则否则就不是文法句子。这种分析过程本质上就不是文法句子。这种分析过程本质上是一种穷举试探过程，是反复使用不同规则，是一种穷举试探过程，是反复使用不同规则，谋求匹配输入串的过程。因此这种匹配过程往谋求匹配输入串的过程。因此这种匹配过程往往一次不能成功，需要重新匹配，称为回溯。往一次不能成功，需要重新匹配，称为回溯。引起回溯的原因在于文法中关于某个非终结符引起回溯的原因在于文法中关于某个非终结符的产生式有多个时，而根据面临的输入符无法的产生式有多个时，而根据面临的输入符无法唯一确定选择哪个产生式来匹配，从而引起回唯一确定选择哪个产生式来匹配，从而引起回溯。溯。自顶向下分析法中存在的问题自顶向下分析法中存在的问题回溯问题回溯问题左递归问题左递归问题回溯问题回溯问题回溯时需要恢复到出错点位置，删去曾回溯时需要恢复到出错点位置，删去曾经匹配过的符号，还包括一些语义处理。经匹配过的符号，还包括一些语义处理。因此处理回溯是一项复杂的工作，在回因此处理回溯是一项复杂的工作，在回溯时，要清除在回溯之前编译程序所做溯时，要清除在回溯之前编译程序所做的大量记录工作，然后重新开始记录，的大量记录工作，然后重新开始记录，这就降低了语法分析的效率。避免回溯这就降低了语法分析的效率。避免回溯是自顶向下语法分析中需要解决的问题是自顶向下语法分析中需要解决的问题之一。之一。回溯的具体表现回溯的具体表现回溯具体表现为下列两种情况：回溯具体表现为下列两种情况：1.1.由于相同左部的产生式的候选式的由于相同左部的产生式的候选式的FIRSTFIRST集交集不为空而引起回溯。集交集不为空而引起回溯。2.2.由于相同左部非终结符的候选式存在能推由于相同左部非终结符的候选式存在能推导出导出的产生式，且该非终结符的的产生式，且该非终结符的FOLLOWFOLLOW集中含有其它候选式的集中含有其它候选式的FIRSTFIRST集的元素。集的元素。表现一示例表现一示例由于相同左部的产生式的候选式的由于相同左部的产生式的候选式的FIRSTFIRST集交集不为空而引起回溯：集交集不为空而引起回溯：【例例4 46 6】设有文法设有文法G G6 6SS为：为：SxAySxAyA*|*A*|*串串x*y*y的分析过程的分析过程SxAy*(S,x)选择产生式选择产生式SxAy SxAy 当前要替换当前要替换的非终结符的非终结符当前要匹配当前要匹配的输入符的输入符(A,*)可选择两个产生式可选择两个产生式 A*A*或或A*A*SxAy*回溯：回到出错点，重新回溯：回到出错点，重新选择产生式选择产生式A*A*，成功，成功原因原因上述文法发生回溯的原因就在于上述文法发生回溯的原因就在于A A的两个的两个产生式的候选式的第一个符号都是产生式的候选式的第一个符号都是*，从，从而根据输入符而根据输入符*来选择来选择A A的产生式时有多的产生式时有多种可能，因此会引起回溯。种可能，因此会引起回溯。即：关于即：关于A A的产生式的可选集交集不为的产生式的可选集交集不为。SELECT(A*)SELECT(A*)=*SELECT(A*)SELECT(A*)=*表现二示例表现二示例由于相同左部非终结符的候选式存在能推导出由于相同左部非终结符的候选式存在能推导出的产生式，且该非终结符的的产生式，且该非终结符的FOLLOWFOLLOW集中含有集中含有其它候选式的其它候选式的FIRSTFIRST集的元素。集的元素。【例如例如】例例4.54.5的文法的文法G G5 5：SaASSaAS Sb Sb AbA AbA A A对输入串对输入串ab#ab#的试探推导过程的试探推导过程SaASSaASbASaASb原因原因上述文法发生回溯的原因就在于选择产上述文法发生回溯的原因就在于选择产生式生式AA相当于与相当于与A A的后随符号的后随符号FOLLOEWFOLLOEW（A A）a,ba,b匹配，但是由于匹配，但是由于A A的后随符号的后随符号b b与与A A的第一个候选式的第一的第一个候选式的第一个符号个符号b b相同，从而根据输入符相同，从而根据输入符b b来选择来选择A A的产生式时有多种可能，因此会引起回的产生式时有多种可能，因此会引起回溯。溯。即：关于即：关于A的产生式的可选集交集不为的产生式的可选集交集不为。SELECT(AbA)AbA)SELECT(A)=bA)=b左递归问题左递归问题【例例4.7】算术表达式的文法算术表达式的文法G G7 7EE为：为：EET|TTT*F|FFi|（E）对输入串对输入串i*i+ii*i+i进行试探推导进行试探推导EE+TE+TEE+TEE+TE+TE+T结论结论当一个文法是左递归的，采用自顶向下当一个文法是左递归的，采用自顶向下分析法会使分析过程陷入无限循环之中。分析法会使分析过程陷入无限循环之中。回溯会使语法分析动作不确定，而回溯会使语法分析动作不确定，而左递左递归会使语法分析程序陷入无限循环之中，归会使语法分析程序陷入无限循环之中，这些都使得语法分析的动作是不确定的。这些都使得语法分析的动作是不确定的。不不确确定定的的语语法法分分析析方方法法带带回回溯溯的的自自顶顶向向下下分分析析法法实实际际上上是是一一种种穷穷举举的的试试探探方方法法，当当分分析析不不成成功功时时则则推推翻翻以以前前的的分分析析退退回回到到适适当当位位置置再再重重新新试试探探其其余余候候选选式式可可能能的的推推导导，这这样样需需要要记记录录已已选选过过的的产产生生式式，直直到到把把所所有有可可能能的的推推导导序序列列都都试试完完仍仍不不成成功功才才能能确确认认输输入入串串不不是是该该文文法法的的句句子子而而报报错错。由由于于在在编编译译程程序序真真正正实实现现时时往往往往是是边边分分析析边边插插入入语语义义动动作作，因因而而带带回回溯溯的的语语法法分分析析方方法法代代价价很很高高，效效率率很很低低，在在实实用用编编译译程程序序中中几几乎乎不不用用，因因此此对对它它实实现现的的详详细细算算法不做介绍。法不做介绍。2.确定的自顶向下的分析确定的自顶向下的分析 确定的自顶向下分析方法，首先要解决从确定的自顶向下分析方法，首先要解决从文法的开始符号出发，如何根据当前的输入文法的开始符号出发，如何根据当前的输入符号符号(单词符号单词符号)唯一地确定选用哪个产生式唯一地确定选用哪个产生式替换相应非终结符往下推导，或构造一棵相替换相应非终结符往下推导，或构造一棵相应的语法树。应的语法树。【例例4.24.2】若有文法若有文法G G2 2SS：SaABSaABAbB AbB AcAAcABaBaBdBd文法文法G G2 2的句子的句子acbadacbad的自顶向下分析过程如下：的自顶向下分析过程如下：示例一示例一注意：注意：#是输入结束符是输入结束符 最左推导最左推导过程过程所选产生式所选产生式输入串输入串(当前要替换的非当前要替换的非终结符终结符,输入符输入符)1Sacbad#(S,a)2aABSaABacbad#(A,c)3acABAcAacbad#(A,b)4acbBBAbBacbad#(B,a)5acbaBBaacbad#(B,d)6acbadBdacbad#推导成功推导成功以以上上最最左左推推导导所所建建立立输输入入串串acbadacbad的的语语法法树树如如图图所示。所示。SaABcAbBad选择产生式是唯一的选择产生式是唯一的 在在第第2 2步步推推导导时时，当当前前要要替替换换的的非非终终结结符符为为A A，面面临临的的输输入入符符为为c c，所所以以选选择择A A的的产产生生式式来来推推导导时时，只只能能选选产产生生式式AcAAcA，而而不不能能选选AbBAbB。同同样样，在在第第5 5步步推推导导时时，当当前前要要替替换换的的非非终终结结符符为为B B，面面临临的的输输入入符符为为d d，所所以以选选择择B B的的产产生生式式来来推推导导时时，只只能能选选产产生生式式BdBd，而而不不能能选选BaBa。这这样样就就保保证证上上述述每每一一步步推推导导都是确定的。都是确定的。文法的特点文法的特点文法文法G G2 2有以下两个特点：有以下两个特点：(1)(1)每个产生式的右部都由终结符号开始；每个产生式的右部都由终结符号开始；(2)(2)如如果果两两个个产产生生式式有有相相同同的的左左部部，那那么么它它们们的右部由不同的终结符开始。的右部由不同的终结符开始。对于这样的文法显然在推导过程中完全对于这样的文法显然在推导过程中完全可以根据当前要替换的非终结符和输入符可以根据当前要替换的非终结符和输入符号决定选择哪个产生式往下推导，因此分号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。析过程是唯一确定的。示例二示例二【例例4.34.3】若有文法若有文法G G3 3SS为：为：SAaSAaSBbSBbAcAcAdAAdABeBeBfBBfB文法文法G G3 3的句子的句子ddcaddca的自顶向下分析的自顶向下分析过程如下：过程如下：最左推导最左推导过程过程所选产生式所选产生式输入串输入串(当前要替换的非当前要替换的非终结符终结符,输入符输入符)1Sddca#(S,d)2AaSAaddca#(A,d)3dAaAdAddca#(A,d)4ddAaAdAddca#(A,c)5ddcaAcddca#推导成功推导成功以以上上最最左左推推导导所所建建立立输输入入串串ddcaddca的的语语法法树树如如图图所示。所示。SAadAdAc文法的特点文法的特点这个文法的特点是：这个文法的特点是：（1 1）产生式的右部不全是由终结符开始。）产生式的右部不全是由终结符开始。（2 2）如如果果两两个个产产生生式式有有相相同同的的左左部部，它它们们的的右部是由不同的终结符或非终结符开始。右部是由不同的终结符或非终结符开始。（3 3）文法中无空产生式。）文法中无空产生式。讨论讨论对于产生式中相同左部含有非终结符开始的产对于产生式中相同左部含有非终结符开始的产生式，在推导过程中选用哪个产生式不像生式，在推导过程中选用哪个产生式不像G G2 2文文法那样直观。法那样直观。对于输入串对于输入串ddcaddca，其第一个符号是，其第一个符号是d d，这时从，这时从S S出发选择出发选择SAaSAa还是选择还是选择SBbSBb时，需要知道时，需要知道AaAa或或BbBb能推导出的首终结符号集合是什么（即能推导出的首终结符号集合是什么（即AaAad d，还是，还是BbBbd d）。若）。若AaAad d成立，则成立，则选择选择SAaSAa往下推导；若往下推导；若BbBbd d成立，则选择成立，则选择SBbSBb往下推导；其它情况则为不确定推导或往下推导；其它情况则为不确定推导或出错。出错。首终结符号集首终结符号集【定义定义4.14.1】设设G(VN,VT,P,S)是上下文是上下文无关文法，无关文法，是由非终结符与终结符组是由非终结符与终结符组成的任意符号串，用成的任意符号串，用FIRST()表示表示的的首终结符集，则首终结符集，则FIRST()a|a,aVT,(,(VNVT )*若若，则则规规定定FIRST()(空空集集)。*求符号串求符号串AaAa与与BbBb的首终结符集：的首终结符集：因为因为AaAacaca，AaAadAadAa，所以，所以FIRST(Aa)=c,dFIRST(Aa)=c,d。因为因为BbBbebeb，BbBbfBbfBb，所以，所以FIRST(Bb)=e,fFIRST(Bb)=e,f。但是但是FIRST(Aa)FIRST(Bb)=FIRST(Aa)FIRST(Bb)=因因而而可可以以根根据据当当前前的的输输入入符符号号是是属属于于哪哪个个产产生生式式右右部部的的首首终终结结符符集集而而决决定定选选择择相相应应产产生生式式进进行行推推导导，即即当当前前要要替替换换的的非非终终结结符符为为S S，面面临临的的输输入入符符为为 d d时时，只只 能能 选选 择择 产产 生生 式式 SAaSAa（因因 为为dFIRST(Aa)dFIRST(Aa)）。这这样样仍仍然然是是确确定定的的自自顶顶向向下下分分析。析。假假如如考考虑虑文文法法中中有有_产产生生式式时时,将将会会产产生生什么问题呢？先看下面的例子：什么问题呢？先看下面的例子：【例例4.44.4】若有文法若有文法G4SG4S：SaABAbBAcAABaBd文法文法G4G4的句子的句子acaaca的自顶向下分析过程如下：的自顶向下分析过程如下：最左推导最左推导过程过程所选产生式所选产生式输入串输入串(当前要替换的非当前要替换的非终结符终结符,输入符输入符)1Saca#(S,a)2aABSaABaca#(A,c)3acABAcAaca#(A,a)4acBAaca#(B,a)5acaBaaca#推导成功推导成功以以上上最最左左推推导导所所建建立立输输入入串串acaaca的的语语法法树树如如图图所所示。示。SaABcAa讨论讨论 考查以上推导，在第考查以上推导，在第3 3步到第步到第4 4步的推导中，步的推导中，即即acABacABacBacB时，因为当前要替换的最左非终结时，因为当前要替换的最左非终结符为符为A A，面临输入符为，面临输入符为a a，而关于，而关于A A的产生式右部的产生式右部的首终结符集都不包含的首终结符集都不包含a a，但有，但有，因此对于，因此对于a a的匹配自然认为只能依赖于在可能的推导过程的匹配自然认为只能依赖于在可能的推导过程中中A A的后面的符号，所以这时选用产生式的后面的符号，所以这时选用产生式AA往下推导，而当前往下推导，而当前A A后面的符号为后面的符号为B B，B B的产生式的产生式右部的首终结符集包含了右部的首终结符集包含了a a，所以可匹配。由此，所以可匹配。由此可以看出，当前输入符可以看出，当前输入符a a与与A A后面的非终结符后面的非终结符B B匹匹配。配。当某一非终结符的产生式中含有当某一非终结符的产生式中含有_产产生式时，它的非空产生式右部的首终结生式时，它的非空产生式右部的首终结符集两两不相交，并与在推导过程中紧符集两两不相交，并与在推导过程中紧跟该非终结符右边可能出现的首终结符跟该非终结符右边可能出现的首终结符号集也不相交，则仍可构造确定的自顶号集也不相交，则仍可构造确定的自顶向下分析。为此，我们为非终结符引入向下分析。为此，我们为非终结符引入后随符号集的概念。后随符号集的概念。后随符号集后随符号集【定义定义4.2】设设G(VN,VT,P,S)是上下文无是上下文无关文法，关文法，A是是G中的非终结符，用中的非终结符，用FOLLOW(A)表示表示A的后随符号集，则有：的后随符号集，则有：FOLLOW(A)a|SAa，aVT特别地，若有特别地，若有SA,则规定则规定FOLLOW(A)。换换句句话话说说，FOLLOW(A)是是指指在在G的的各各个个句句型中位于型中位于A后面的那些终结符或后面的那些终结符或。用用作作为为输输入入串串的的结结束束符符，或或称称为为句句子子括括号号，如：输入串。如：输入串。*对于例对于例4.4中的文法中的文法G4，可用观察法求，可用观察法求得得FOLLOW(A)a,d。在自顶向下分析。在自顶向下分析过程中，如果当前要替换的非终结符过程中，如果当前要替换的非终结符A面面临输入符临输入符a或或d时，应该选择产生式时，应该选择产生式A去去匹配，而当面临匹配，而当面临b或或c时，则分别选择产生时，则分别选择产生式式AbB或或AcA去匹配。去匹配。因此当文法中还有形如：因此当文法中还有形如：AA的产生式时，其中的产生式时，其中AVN,V*，当，当和和不同时推导出不同时推导出时，设时，设,则当则当FIRST()(FIRST()FOLLOW(A)）时，时，对于非终结符对于非终结符A的替换仍可唯一地确定产生的替换仍可唯一地确定产生式。式。*SELECT集集在自顶向下分析过程中，对每个产生式在自顶向下分析过程中，对每个产生式的选择都可由输入符来决定。综合以上的选择都可由输入符来决定。综合以上情况，为每个产生式定义一个可选集情况，为每个产生式定义一个可选集（SELECT）如下：）如下：可选集的定义可选集的定义【定定义义4.34.3】给给定定上上下下文文无无关关文文法法的的产产生生式式AA，AVAVN N,V,V*,则定义：则定义：如果如果,则则SELECT(A)=FIRST()SELECT(A)=FIRST()；如果如果，则则SELECT(A)=FIRST()FOLLOW(A)SELECT(A)=FIRST()FOLLOW(A)；特别地，如果特别地，如果，则则SELECT(A)=FOLLOW(A)SELECT(A)=FOLLOW(A)。*可选集的含义可选集的含义可可选选集集的的含含义义如如下下：在在自自顶顶向向下下分分析析过过程程中中，如如果果当当前前要要替替换换的的最最左左非非终终结结符符为为A A，面面临临输输入入符符为为aSELECT(A)aSELECT(A)时时，则可以选择产生式则可以选择产生式AA来匹配。来匹配。因因此此，只只要要文文法法G G的的某某一一个个非非终终结结符符A A的的各各个个可可选选集集互互不不相相交交，则则语语法法分分析析程程序序就就可可以以根根据据当当前前输输入入符符和和A A的的可可选选集集来来唯唯一正确的选择一正确的选择A A的某个产生式去匹配。的某个产生式去匹配。LL(1)LL(1)文法文法【定义定义4.4】一个上下文无关文法是一个上下文无关文法是LL(1)文法的充文法的充分必要条件是关于同一非终结符的各个产生式的分必要条件是关于同一非终结符的各个产生式的可选集互不相交。可选集互不相交。LL(1)文法的含义是：第一个文法的含义是：第一个L表明自顶向下分析表明自顶向下分析过程中是从左到右扫描输入串，第二个过程中是从左到右扫描输入串，第二个L表明分表明分析过程中采用最左推导，析过程中采用最左推导，1表明只需向前查看一表明只需向前查看一个输入符号便可决定选择哪个产生式（规则）进个输入符号便可决定选择哪个产生式（规则）进行推导。行推导。类似地，也可以有类似地，也可以有LL(k)文法，也就是需要向前文法，也就是需要向前查看查看K个符号才能够确定选择哪个产生式。通常个符号才能够确定选择哪个产生式。通常采用采用K=1，个别情况采用，个别情况采用K=2。示例【例例4.4】文法文法G4S：SaABAbBAcAABaBd计算可选集：计算可选集：SELECT(SaAB)SELECT(SaAB)aaSELECT(AbB)SELECT(AbB)bbSELECT(AcA)SELECT(AcA)ccSELECT(A)SELECT(A)FOLLOW(A)FOLLOW(A)a,da,dSELECT(Ba)SELECT(Ba)aaSELECT(Bd)SELECT(Bd)dd显然有：显然有：SELECT(AbB)SELECT(AcA)SELECT(AbB)SELECT(AcA)bcbc SELECT(AbB)SELECT(A)SELECT(AbB)SELECT(A)ba,dba,d SELECT(AcA)SELECT(A)SELECT(AcA)SELECT(A)ca,dca,d SELECT(Ba)SELECT(Bd)SELECT(Ba)SELECT(Bd)adad 所以，该文法是所以，该文法是LL(1)LL(1)文法。文法。示例【例例4.54.5】设文法设文法G G5 5SS为：为：SaASSaASSbSbAbAAbAAA因为有：因为有：SELECT(SaAS)SELECT(SaAS)FIRST(aAS)FIRST(aAS)aaSELECT(Sb)SELECT(Sb)FIRST(b)FIRST(b)bbSELECT(AbA)SELECT(AbA)FIRST(bA)FIRST(bA)bbSELECT(A)SELECT(A)FOLLOW(A)FOLLOW(A)FIRST(S)FIRST(S)a,ba,b所以：所以：SELECT(SaAS)SELECT(Sb)SELECT(SaAS)SELECT(Sb)ababSELECT(AbA)SELECT(A)SELECT(AbA)SELECT(A)baba，bb因因此此，该该文文法法不不是是LL(1)LL(1)文文法法，因因而而也也就就不不可可能能进行确定的自顶向下语法分析。进行确定的自顶向下语法分析。原因原因从从对对输输入入串串abab的的下下列列两两种种不不同同推推导导过程来看：过程来看：第一种推导过程可为：第一种推导过程可为：S S aAS aAS abAS abAS abS abS 在在句句型型abSabS中中由由于于S S不不能能推推出出，所所以以第第一种推导过程推不出一种推导过程推不出abab；第二种推导过程可为：第二种推导过程可为：S S aAS aAS aS aS ab ab 第二种推导过程推出了第二种推导过程推出了abab。以上两种推导中，当第二步推导时当前以上两种推导中，当第二步推导时当前输入符为输入符为b b，对句型，对句型aASaAS中的中的A A用哪个产生用哪个产生式推导不能唯一确定，也就是导致了这式推导不能唯一确定，也就是导致了这个文法不能进行确定的自顶向下分析。个文法不能进行确定的自顶向下分析。也即非也即非LLLL（1 1）文法是不能进行确定的自）文法是不能进行确定的自顶向下分析。顶向下分析。结论结论确定的自顶向下语法分析要求文法是确定的自顶向下语法分析要求文法是LLLL（1 1）文法。）文法。二、二、LLLL（1 1）文法）文法LL(1)LL(1)文法是一类可以进行确定的自顶向下语文法是一类可以进行确定的自顶向下语法分析的文法。法分析的文法。根据根据LL(1)LL(1)文法的定义，对于同一非终结符文法的定义，对于同一非终结符A A的的任意两个产生式任意两个产生式AA和和AA，都要满足：，都要满足：SELECT(A)SELECT(A)SELECT(A)SELECT(A)这样，当前非终结符这样，当前非终结符A A面临输入符面临输入符a a时，如果时，如果aSELECT(A)aSELECT(A)，则可以选择产生式，则可以选择产生式AA去准确匹配，从而解决回溯问题去准确匹配，从而解决回溯问题。LLLL（1 1）文法的判别）文法的判别采采用用确确定定的的自自顶顶向向下下分分析析技技术术时时，首首先先必必须须判判别别所所给给文文法法是是否否是是LLLL（1 1）文文法法。因因而而对对任任何何给给定定的的文文法法需需要要计计算算FIRSTFIRST、FOLLOWFOLLOW、SELECTSELECT集集合合，进进而而判判别别该该文文法法是否为是否为LLLL（1 1）文法。）文法。1.1.构造构造FIRSTFIRST集集符符号号串串的的首首终终结结符符集集为为FIRST()FIRST()，定定义：义：FIRST()FIRST()a|a|a,aVa,aVT T,(V,(VN NVVT T )*若若，则规定，则规定FIRST()FIRST()。*构造构造FIRSTFIRST集的算法集的算法对对于于文文法法符符号号串串(V VN NV VT T )*，构构造造FIRST(FIRST()的的算算法法如如下下：反反复复使使用用如如下下规规则则，直直至至FIRSTFIRST集集不再增大为止。不再增大为止。若若a,a,且且a a是终结符是终结符,则则FIRST()FIRST()aa；若若X,XX,X是是非非终终结结符符,且且有有Xb,Xb,则则把把b b加加入入FIRST()FIRST()中；中；若若X X1 1X X2 2X Xk k,X,X1 1,X X2 2,X,Xk k都都是是非非终终结结符符，首首先先把把FIRST(XFIRST(X1 1)加加入入FIRST()FIRST()中中；若若X X1 1X X2 2X Xi i,则则把把FIRST FIRST(X(Xi i1 1X Xi i2 2X Xk k)加加入入FIRST FIRST()()中中，其其中中1ik1ik1 1；若若X X1 1X X2 2X Xk k ,则则把把FIRST()FIRST()加入加入FIRST()FIRST()中。中。+在构造在构造FIRSTFIRST集的算法中，第集的算法中，第条规则中的情条规则中的情况最复杂，下面具体说明一下。况最复杂，下面具体说明一下。设设ABCABC，A A，B B，C C都是非终结符，则分都是非终结符，则分情况讨论：情况讨论：若若A A，则，则FIRST()FIRST()FIRST(A)FIRST(A)；若若A A，但，但B B，则，则FIRST()FIRST()FIRST(A)FIRST(A)FIRST(BC)FIRST(BC)；若若ABAB，但是，但是C C，则，则FIRST()FIRST()FIRST FIRST(A)(A)FIRST(B)FIRST(B)FIRST(C)FIRST(C)；若若ABCABC，但是，但是，则，则FIRST()FIRST()FIRST(A)FIRST(A)FIRST(B)FIRST(B)FIRST(C)FIRST(C)FIRST()FIRST()。+示例一示例一【例例4.8】若文法若文法G8S为：为：SABSbCAAbBBaDCADCbDaSDc求各非终结符的求各非终结符的FIRST集集FIRST（S）FIRST（AB）FIRST（bC）(SAB，SbC)FIRST（A）FIRST（B）b(A)b,abb,aFIRST（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,cbb,a,cFIRST（D）FIRST（aS）FIRST（c）(DaS，Dc)aca,c结果结果所以最终求得：所以最终求得：FIRST（S）b,aFIRST（A）bFIRST（B）aFIRST（C）b,a,cFIRST（D）a,c2.2.构造构造FOLLOWFOLLOW集集非终结符非终结符A的后随符号集的定义为：的后随符号集的定义为：FOLLOW(A)a|SAa，aVT特别地，若有特别地，若有SA,则规定则规定FOLLOW(A)。*构造构造FOLLOWFOLLOW集的算法集的算法对文法中每一非终结符对文法中每一非终结符A，构造，构造FOLLOW(A)的算的算法如下：反复使用如下规则，直至法如下：反复使用如下规则，直至FOLLOW集不集不再增大为止。再增大为止。若若A是文法的开始符号是文法的开始符号,则把输入结束符加入则把输入结束符加入FOLLOW(A)中；中；若若BAa,a是终结符是终结符,则把则把a加入加入FOLLOW(A)中；中；若若BAX,X是非终结符是非终结符,则把则把FIRST(X)加入加入FOLLOW(A)中；中；若若BA或或BA,且且，则把，则把FOLLOW(B)加加入入FOLLOW(A)中。中。*注意注意在构造在构造FOLLOWFOLLOW集的算法中，将第集的算法中，将第条规则条规则解释一下：解释一下：如果有句型如果有句型BaBa，显然，显然a a是是B B的后随符的后随符号，号，aFOLLOW(B)aFOLLOW(B)，而，而BABA，用它往下，用它往下进行推导有进行推导有S SBaBaAaAa，那么，那么a a也是也是A A的后随符号，的后随符号，aFOLLOW(A)aFOLLOW(A)即即FOLLOW(B)FOLLOW(B)中的后随符号都是中的后随符号都是FOLLOW(A)FOLLOW(A)中中的后随符号。的后随符号。+同样的，如果有同样的，如果有BABA，且，且，用它往下进行推导有：用它往下进行推导有：S SBaBaAaAaAaAa，即也有即也有FOLLOW(B)FOLLOW(B)中的后随符号都是中的后随符号都是FOLLOW(A)FOLLOW(A)中的后随符号。中的后随符号。*示例一示例一【例例4.8】若文法若文法G8S为：为：SABSbCAAbBBaDCADCbDaSDc求各非终结符的求各非终结符的FOLLOW集集FOLLOW(S)FOLLOW(S)FOLLOW(D)FOLLOW(D)(S (S是文法的开始符号，是文法的开始符号，DaS)DaS)FOLLOW(S)FOLLOW(S)FOLLOW(A)FOLLOW(A)FIRSTFIRST（B B）FIRST(D)FOLLOW(S)FIRST(D)FOLLOW(S)(S (SAB,AB,且且B B ,C,CAD)AD)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(S)FOLLOW(A)a，c，FOLLOW(B)FOLLOW(C)FOLLOW(D)计算此文法各个产生式的可选集计算此文法各个产生式的可选集SELECT集集首先考虑计算产生式的右部是终结符开头首先考虑计算产生式的右部是终结符开头的，其可选集只包含这一个终结符。的，其可选集只包含这一个终结符。SELECT(SbC)FIRST(bC)bSELECT(Ab)FIRST(b)bSELECT(BaD)FIRST(aD)aSELECT(Cb)FIRST(b)bSELECT(DaS)FIRST(aS)aSELECT(Dc)FIRST(c)c再来考虑计算产生式是再来考虑计算产生式是_产生式，其可产生式，其可选集为相应产生式左部的选集为相应产生式左部的