《第5章自顶向下语法分析方法》由会员分享，可在线阅读，更多相关《第5章自顶向下语法分析方法（147页珍藏版）》请在金锄头文库上搜索。
1、第第5章自顶向下语法分析方法章自顶向下语法分析方法 语法分析（语法分析（Syntax AnalysisSyntax Analysis）是编译程序是编译程序的核心部分。词法分析只是将字符形式的源程的核心部分。词法分析只是将字符形式的源程序中的各个单词识别出来，形成单词的机内表序中的各个单词识别出来，形成单词的机内表示形式，但是这些单词串如何构成更大的语法示形式，但是这些单词串如何构成更大的语法成分成分语句，那就由语法分析来完成。语法语句，那就由语法分析来完成。语法分析的主要任务就是分析的主要任务就是“组词成句组词成句”，即在词法，即在词法分析识别出单词串的基础上，根据语言的语法分析识别出单词串的
2、基础上，根据语言的语法规则，识别出各类语法成分，如规则，识别出各类语法成分，如“语句语句”、“程序程序”等。等。 将完成语法分析任务的程序称为语法分析程将完成语法分析任务的程序称为语法分析程序，也称为语法分析器或简称分析器。序，也称为语法分析器或简称分析器。程程序序设设计计语语言言的的语语法法结结构构是是用用上上下下文文无无关关文文法法描描述述的的，因因此此，语语法法分分析析器器的的实实现现原原理理就就是是按按所所给给定定的的文文法法G G，识识别别输输入入符符号号串串是是否否为为一一个个句句子子（即即L(G)L(G)成成立立吗吗？），同同时时检检查查和和处处理理语语法法错错误误。语语法法分分
3、析析的的关关键键是是句句型型识识别别问问题题。给给定定一一串串单单词词（即即文文法法的的终终结结符符），怎怎样样知知道道它它是是不不是是该该文文法法产产生生的的一一个个句句子子呢呢？可可以以利利用用推推导导，或或者者利利用用语语法法树树来来进进行行判判断断。一一般般来来说说，语语法法分分析析的的过过程程就就是是为一个句子建立语法树的过程。为一个句子建立语法树的过程。语语法法分分析析的的方方法法很很多多，按按照照建建立立语语法法树树的的不不同同方方向向，通通常常将将语语法法分分析析分分为为两两类类，一一类类是是自自顶顶向向下下分分析析法法，另另一一类类是是自自底底向上分析法。向上分析法。本本章章
4、主主要要介介绍绍自自顶顶向向下下分分析析法法，自自底底向向上分析法。上分析法。第第4章教学内容章教学内容语法分析的任务；语法分析的任务；确定的自顶向下语法分析的基本思想；确定的自顶向下语法分析的基本思想；LL(1)LL(1)文法的定义和判别方法；文法的定义和判别方法；非非LL(1)LL(1)文法到文法到LL(1)LL(1)文法的等价变换；文法的等价变换；确定的自顶向下分析方法：确定的自顶向下分析方法：递归下降分析法递归下降分析法预测分析法预测分析法自底向上自底向上语法分析的基本思想；语法分析的基本思想；短短语语、直直接接短短语语和和句句柄柄的的定定义义，以以及及如如何何利利用用语语法法树树寻寻
5、找找短短语语、直直接接短短语语和和句句柄。柄。自底向上语法自底向上语法分析方法：分析方法：优先分析法优先分析法LRLR分析法分析法一、一、自顶向下的语法分析思想自顶向下的语法分析思想【自自顶顶向向下下（top top - - down down ）分分析析法法的的基基本本思思想想】自自顶顶向向下下语语法法分分析析的的基基本本思思想想是是以以文文法法的的开开始始符符号号为为树树根根，采采用用最最左左推推导导，试试图图自自上上而而下下地地为为输输入入的的单单词词串串构构造造一一棵棵语语法法树树。若若语语法法树树的的端端末末节节点点从从左左向向右右排排列列恰恰好好是是输输入入串串，则则该该输输入入串
6、串就就是是文法的句子，否则就不是。文法的句子，否则就不是。 这这种种分分析析过过程程实实质质是是一一种种试试探探过过程程，是是反反复复使用不同产生式来匹配输入串的过程。使用不同产生式来匹配输入串的过程。示例示例【例例4.1】设有以下文法设有以下文法G1S:SaABAbA|cBdBe|de输入串输入串abbcdeabbcde的最左推导如下：的最左推导如下：S S aABaAB abABabAB abbABabbAB abbcBabbcB abbcdeabbcde因此，输入串因此，输入串abbcdeabbcde是该文法是该文法G G1 1的句子的句子。下下面面从从建建立立语语法法树树来来看看句句子
7、子的的推推导导过过程程。为为了了自自顶顶向向下下地地构构造造输输入入串串abbcdeabbcde的的语语法法树树，首首先先按按文文法法的的开开始始符符号号产产生生根根节节点点S S，再再根根据据产产生生式式规规则则自自顶顶向向下下地地生生长长这这棵棵语语法法树树。语语法法树树的的建建立过程如图所示。立过程如图所示。SaABbAbAcde 自顶向下分析法也称面向目标的分析方法，在对自顶向下分析法也称面向目标的分析方法，在对输入串进行最左推导的过程中，在选择产生式时其输入串进行最左推导的过程中，在选择产生式时其实是一种试探方法，如果每一步选择产生式来匹配实是一种试探方法，如果每一步选择产生式来匹配
8、的时候都能够每选必中，则这种方法称为确定的分的时候都能够每选必中，则这种方法称为确定的分析方法；否则在选择产生式时面临多种可能，不知析方法；否则在选择产生式时面临多种可能，不知道选择哪一个产生式合适，就是不确定的分析方法。道选择哪一个产生式合适，就是不确定的分析方法。 因此自顶向下分析法又可分为确定的和不确定的因此自顶向下分析法又可分为确定的和不确定的两种，确定的分析方法对文法有一定的限制，但由两种，确定的分析方法对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。不确语法分析器，因而仍是目前常
9、用的方法之一。不确定的方法即带回溯的分析方法，这种方法实际上是定的方法即带回溯的分析方法，这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因而一种穷举的试探方法，因此效率低，代价高，因而极少使用。极少使用。1. 1. 不确定的自顶向下分析不确定的自顶向下分析不确定的自顶向下分析法的基本思想是，对任不确定的自顶向下分析法的基本思想是，对任何输入串何输入串试图用一切可能的办法，从文法的试图用一切可能的办法，从文法的开始符号出发，自上而下的为它建立一棵语法开始符号出发，自上而下的为它建立一棵语法树。如果试探成功，则树。如果试探成功，则为相应文法的句子，为相应文法的句子，否则否则就不是文法句子
10、。这种分析过程本质上就不是文法句子。这种分析过程本质上是一种穷举试探过程，是反复使用不同规则，是一种穷举试探过程，是反复使用不同规则，谋求匹配输入串的过程。因此这种匹配过程往谋求匹配输入串的过程。因此这种匹配过程往往一次不能成功，需要重新匹配，称为回溯。往一次不能成功，需要重新匹配，称为回溯。引起回溯的原因在于文法中关于某个非终结符引起回溯的原因在于文法中关于某个非终结符的产生式有多个时，而根据面临的输入符无法的产生式有多个时，而根据面临的输入符无法唯一确定选择哪个产生式来匹配，从而引起回唯一确定选择哪个产生式来匹配，从而引起回溯。溯。自顶向下分析法中存在的问题自顶向下分析法中存在的问题回溯问
11、题回溯问题左递归问题左递归问题回溯问题回溯问题回溯时需要恢复到出错点位置，删去曾回溯时需要恢复到出错点位置，删去曾经匹配过的符号，还包括一些语义处理。经匹配过的符号，还包括一些语义处理。因此处理回溯是一项复杂的工作，在回因此处理回溯是一项复杂的工作，在回溯时，要清除在回溯之前编译程序所做溯时，要清除在回溯之前编译程序所做的大量记录工作，然后重新开始记录，的大量记录工作，然后重新开始记录，这就降低了语法分析的效率。避免回溯这就降低了语法分析的效率。避免回溯是自顶向下语法分析中需要解决的问题是自顶向下语法分析中需要解决的问题之一。之一。 回溯的具体表现回溯的具体表现回溯具体表现为下列两种情况：回溯
12、具体表现为下列两种情况：1. 1. 由于相同左部的产生式的候选式由于相同左部的产生式的候选式的的FIRSTFIRST集交集不为空而引起回溯。集交集不为空而引起回溯。2.2.由于相同左部非终结符的候选式存在能推由于相同左部非终结符的候选式存在能推导出导出的产生式，且该非终结符的的产生式，且该非终结符的FOLLOWFOLLOW集中含有其它候选式的集中含有其它候选式的FIRSTFIRST集的元素。集的元素。表现一示例表现一示例由于相同左部的产生式的候选式的由于相同左部的产生式的候选式的FIRSTFIRST集交集不为空而引起回溯：集交集不为空而引起回溯：【例例4 46 6】设有文法设有文法G G6 6
13、SS为：为：SxAySxAyA*|*A*|*串串x*y*y的分析过程的分析过程SxAy* * *(S,x)选择产生式选择产生式SxAySxAy 当前要替换当前要替换的非终结符的非终结符当前要匹配当前要匹配的输入符的输入符(A,* *)可选择两个产生式可选择两个产生式 A*A*或或A*A*SxAy* *回溯：回到出错点，重新回溯：回到出错点，重新选择产生式选择产生式A*A*，成功成功原因原因上述文法发生回溯的原因就在于上述文法发生回溯的原因就在于A A的两个的两个产生式的候选式的第一个符号都是产生式的候选式的第一个符号都是* *，从，从而根据输入符而根据输入符* *来选择来选择A A的产生式时有
14、多的产生式时有多种可能，因此会引起回溯。种可能，因此会引起回溯。即：关于即：关于A A的的产生式的可选集交集不为产生式的可选集交集不为。SELECT(A*)SELECT(A*)=*SELECT(A*)SELECT(A*)=*表现二示例表现二示例由于相同左部非终结符的候选式存在能推导出由于相同左部非终结符的候选式存在能推导出的产生式，且该非终结符的的产生式，且该非终结符的FOLLOWFOLLOW集中含有集中含有其它候选式的其它候选式的FIRSTFIRST集的元素。集的元素。【例如例如】例例4.54.5的文法的文法G G5 5： SaASSaAS Sb Sb AbAAbA A A对输入对输入串串a
15、bab# #的试探推导过程的试探推导过程SaASSaASbASaASb原因原因上述文法发生回溯的原因就在于选择产上述文法发生回溯的原因就在于选择产生式生式AA相当于与相当于与A A的后随符号的后随符号FOLLOEWFOLLOEW（A A）a,ba,b匹配，但是由于匹配，但是由于A A的后随符号的后随符号b b与与A A的第一个候选式的第一的第一个候选式的第一个符号个符号b b相同，从而根据输入符相同，从而根据输入符b b来选择来选择A A的产生式时有多种可能，因此会引起回的产生式时有多种可能，因此会引起回溯。溯。即：关于即：关于A的产生式的可选集交集不为的产生式的可选集交集不为。SELECT(
16、AbA)AbA)SELECT(AA)=b)=b左递归问题左递归问题【例例4.7】算术表达式的文法算术表达式的文法G G7 7EE为：为：EET|TTT*F|FFi|（E）对输入对输入串串i*i+ii*i+i进行试探推导进行试探推导EE+TE+TEE+TEE+TE+TE+T结论结论当一个文法是左递归的，采用自顶向下当一个文法是左递归的，采用自顶向下分析法会使分析过程陷入无限循环之中。分析法会使分析过程陷入无限循环之中。回溯会使语法分析动作不确定，而回溯会使语法分析动作不确定，而左递左递归会使语法分析程序陷入无限循环之中，归会使语法分析程序陷入无限循环之中，这些都使得语法分析的动作是不确定的。这些
17、都使得语法分析的动作是不确定的。不不确确定定的的语语法法分分析析方方法法带带回回溯溯的的自自顶顶向向下下分分析析法法实实际际上上是是一一种种穷穷举举的的试试探探方方法法，当当分分析析不不成成功功时时则则推推翻翻以以前前的的分分析析退退回回到到适适当当位位置置再再重重新新试试探探其其余余候候选选式式可可能能的的推推导导，这这样样需需要要记记录录已已选选过过的的产产生生式式，直直到到把把所所有有可可能能的的推推导导序序列列都都试试完完仍仍不不成成功功才才能能确确认认输输入入串串不不是是该该文文法法的的句句子子而而报报错错。由由于于在在编编译译程程序序真真正正实实现现时时往往往往是是边边分分析析边边
18、插插入入语语义义动动作作，因因而而带带回回溯溯的的语语法法分分析析方方法法代代价价很很高高，效效率率很很低低，在在实实用用编编译译程程序序中中几几乎乎不不用用，因因此此对对它它实实现现的的详详细细算算法不做介绍。法不做介绍。2.确定的自顶向下的分析确定的自顶向下的分析 确定的自顶向下分析方法，首先要解决从确定的自顶向下分析方法，首先要解决从文法的开始符号出发，如何根据当前的输入文法的开始符号出发，如何根据当前的输入符号符号( (单词符号单词符号) )唯一地确定选用哪个产生式唯一地确定选用哪个产生式替换相应非终结符往下推导，或构造一棵相替换相应非终结符往下推导，或构造一棵相应的语法树。应的语法树
19、。 【例例4.24.2】若有文法若有文法G G2 2SS：SaABSaABAbBAbB AcAAcABaBaBdBd文法文法G G2 2的句子的句子acbadacbad的自顶向下分析过程如下：的自顶向下分析过程如下：示例一示例一注意：注意：# #是输入结束符是输入结束符 最左推导最左推导过程过程所选产生式所选产生式输入串输入串( (当前要替换的非当前要替换的非终结符终结符, ,输入符输入符) )1Sacbad#(S,a)2aABSaABacbad#(A,c)3acABAcAacbad#(A,b)4acbBBAbBacbad#(B,a)5acbaBBaacbad#(B,d)6acbadBdacb
20、ad#推导成功推导成功以以上上最最左左推推导导所所建建立立输输入入串串acbadacbad的的语语法法树树如如图图所示。所示。SaABcAbBad选择产生式是唯一选择产生式是唯一的的 在在第第2 2步步推推导导时时，当当前前要要替替换换的的非非终终结结符符为为A A，面面临临的的输输入入符符为为c c，所所以以选选择择A A的的产产生生式式来来推推导导时时，只只能能选选产产生生式式AcAAcA，而而不不能能选选AbBAbB。同同样样，在在第第5 5步步推推导导时时，当当前前要要替替换换的的非非终终结结符符为为B B，面面临临的的输输入入符符为为d d，所所以以选选择择B B的的产产生生式式来来
21、推推导导时时，只只能能选选产产生生式式BdBd，而而不不能能选选BaBa。这这样样就就保保证证上上述述每每一一步步推推导导都是确定的。都是确定的。文法的特点文法的特点文法文法G G2 2有以下两个特点：有以下两个特点：(1)(1)每个产生式的右部都由终结符号开始；每个产生式的右部都由终结符号开始；(2)(2)如如果果两两个个产产生生式式有有相相同同的的左左部部，那那么么它它们们的右部由不同的终结符开始。的右部由不同的终结符开始。 对于这样的文法显然在推导过程中完全对于这样的文法显然在推导过程中完全可以根据当前要替换的非终结符和输入符可以根据当前要替换的非终结符和输入符号决定选择哪个产生式往下推
22、导，因此分号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。析过程是唯一确定的。 示例二示例二【例例4.34.3】若有文法若有文法G G3 3SS为：为：SAaSAaSBbSBbAcAcAdAAdABeBeBfBBfB文法文法G G3 3的句子的句子ddcaddca的自顶向下分析的自顶向下分析过程如下：过程如下：最左推导最左推导过程过程所选产生式所选产生式输入串输入串( (当前要替换的非当前要替换的非终结符终结符, ,输入符输入符) )1Sddca#(S,d)2AaSAaddca#(A,d)3dAaAdAddca#(A,d)4ddAaAdAddca#(A,c)5ddcaAcddca#推导
23、成功推导成功以以上上最最左左推推导导所所建建立立输输入入串串ddcaddca的的语语法法树树如如图图所示。所示。SAadAdAc文法的特点文法的特点这个文法的特点是：这个文法的特点是：（1 1）产生式的右部不全是由终结符开始。）产生式的右部不全是由终结符开始。（2 2）如如果果两两个个产产生生式式有有相相同同的的左左部部，它它们们的的右部是由不同的终结符或非终结符开始。右部是由不同的终结符或非终结符开始。（3 3）文法中无空产生式。）文法中无空产生式。讨论讨论对于产生式中相同左部含有非终结符开始的产对于产生式中相同左部含有非终结符开始的产生式，在推导过程中选用哪个产生式不像生式，在推导过程中选
24、用哪个产生式不像G G2 2文文法那样直观。法那样直观。对于输入对于输入串串ddcaddca，其第一个符号是其第一个符号是d d，这时从这时从S S出发选择出发选择SAaSAa还是选择还是选择SBbSBb时，需要知道时，需要知道AaAa或或BbBb能推导出的首终结符号集合是什么（即能推导出的首终结符号集合是什么（即AaAad d，还是还是BbBbdd）。若）。若AaAad d成立，则成立，则选择选择SAaSAa往下推导；若往下推导；若BbBbdd成立，则选择成立，则选择SBbSBb往下推导；其它情况则为不确定推导或往下推导；其它情况则为不确定推导或出错。出错。 首终结符号集首终结符号集【定义定
25、义4.14.1】设设G(VN,VT,P,S)是上下是上下文无关文法，文无关文法，是由非终结符与终结符是由非终结符与终结符组成的任意符号串，用组成的任意符号串，用FIRST()表示表示的首终结符集，则的首终结符集，则FIRST()a|a,aVT,(,(VNVT )*若若，则规定则规定FIRST()(空集空集)。*求符号串求符号串AaAa与与BbBb的首终结符集：的首终结符集：因为因为AaAacaca，AaAadAadAa，所以所以FIRST(AaFIRST(Aa)=c,d)=c,d。因为因为BbBbebeb，BbBbfBbfBb，所以所以FIRST(Bb)=e,fFIRST(Bb)=e,f。但是
26、但是FIRST(AaFIRST(Aa) FIRST(Bb)= ) FIRST(Bb)= 因因而而可可以以根根据据当当前前的的输输入入符符号号是是属属于于哪哪个个产产生生式式右右部部的的首首终终结结符符集集而而决决定定选选择择相相应应产产生生式式进进行行推推导导，即即当当前前要要替替换换的的非非终终结结符符为为S S，面面临临的的输输入入符符为为 d d时时 ， 只只 能能 选选 择择 产产 生生 式式 SAaSAa（ 因因 为为dFIRST(AadFIRST(Aa) )）。这这样样仍仍然然是是确确定定的的自自顶顶向向下下分分析。析。假假如如考考虑虑文文法法中中有有_产产生生式式时时, ,将将会
27、会产产生生什么问题呢？先看下面的例子：什么问题呢？先看下面的例子：【例例4.44.4】若有文法若有文法G4SG4S：SaABAbBAcAABaBd文法文法G4G4的句子的句子acaaca的自顶向下分析过程如下：的自顶向下分析过程如下：最左推导最左推导过程过程所选产生式所选产生式输入串输入串( (当前要替换的非当前要替换的非终结符终结符, ,输入符输入符) )1Saca#(S,a)2aABSaABaca#(A,c)3acABAcAaca#(A,a)4acBAaca#(B,a)5acaBaaca#推导成功推导成功以以上上最最左左推推导导所所建建立立输输入入串串acaaca的的语语法法树树如如图图所
28、所示。示。SaABcAa讨论讨论 考查以上推导，在第考查以上推导，在第3 3步到第步到第4 4步的推导中，步的推导中，即即acABacABacBacB时，因为当前要替换的最左非终结时，因为当前要替换的最左非终结符为符为A A，面临输入符为面临输入符为a a，而关于而关于A A的产生式右部的产生式右部的首终结符集都不包含的首终结符集都不包含a a，但有，但有，因此对于因此对于a a的匹配自然认为只能依赖于在可能的推导过程的匹配自然认为只能依赖于在可能的推导过程中中A A的后面的符号，所以这时选用产生式的后面的符号，所以这时选用产生式AA往下推导，而当前往下推导，而当前A A后面的符号为后面的符号
29、为B B，B B的产生式的产生式右部的首终结符集包含了右部的首终结符集包含了a a，所以可匹配。由此所以可匹配。由此可以看出，当前输入符可以看出，当前输入符a a与与A A后面的非终结符后面的非终结符B B匹匹配。配。 当某一非终结符的产生式中含有当某一非终结符的产生式中含有_产产生式时，它的非空产生式右部的首终结生式时，它的非空产生式右部的首终结符集两两不相交，并与在推导过程中紧符集两两不相交，并与在推导过程中紧跟该非终结符右边可能出现的首终结符跟该非终结符右边可能出现的首终结符号集也不相交，则仍可构造确定的自顶号集也不相交，则仍可构造确定的自顶向下分析。为此，我们为非终结符引入向下分析。为
30、此，我们为非终结符引入后随符号集的概念。后随符号集的概念。后随符号集后随符号集【定义定义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
31、.4中的文法中的文法G4，可用观察法求可用观察法求得得FOLLOW(A)a,d。在自顶向下分在自顶向下分析过程中，如果当前要替换的非终结符析过程中，如果当前要替换的非终结符A面临输入符面临输入符a或或d时，应该选择产生式时，应该选择产生式A去匹配，而当面临去匹配，而当面临b或或c时，则分别选择产时，则分别选择产生式生式AbB或或AcA去匹配。去匹配。因此当文法中还有形如：因此当文法中还有形如：AA的产生式时，其中的产生式时，其中AVN,V*，当，当和和不同时推导出不同时推导出时，设时，设,则当则当FIRST()(FIRST()FOLLOW(A)）时，时，对于非终结符对于非终结符A的替换仍可唯一
32、地确定产生的替换仍可唯一地确定产生式。式。*SELECT集集在自顶向下分析过程中，对每个产生式在自顶向下分析过程中，对每个产生式的选择都可由输入符来决定。综合以上的选择都可由输入符来决定。综合以上情况，为每个产生式定义一个可选集情况，为每个产生式定义一个可选集（SELECT）如下：如下：可选集的定义可选集的定义【定定义义4.34.3】给给定定上上下下文文无无关关文文法法的的产产生生式式AA，AVAVN N, V, V* *, ,则定义：则定义：如果如果, , 则则SELECT(A)= FIRST()SELECT(A)= FIRST()；如果如果， 则则SELECT(A)=FIRST()FOLL
33、OW(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的的各各个个可可选选集集互互不不相相交交，则则语语法法
34、分分析析程程序序就就可可以以根根据据当当前前输输入入符符和和A A的的可可选选集集来来唯唯一正确的选择一正确的选择A A的某个产生式去匹配。的某个产生式去匹配。 LL(1)LL(1)文法文法 【定义定义4.4】一个上下文无关文法是一个上下文无关文法是LL(1)文法的充文法的充分必要条件是关于同一非终结符的各个产生式的分必要条件是关于同一非终结符的各个产生式的可选集互不相交。可选集互不相交。LL(1)文法的含义是：第一个文法的含义是：第一个L表明自顶向下分析表明自顶向下分析过程中是从左到右扫描输入串，第二个过程中是从左到右扫描输入串，第二个L表明分表明分析过程中采用最左推导，析过程中采用最左推导
35、，1表明只需向前查看一表明只需向前查看一个输入符号便可决定选择哪个产生式（规则）进个输入符号便可决定选择哪个产生式（规则）进行推导。行推导。类似地，也可以有类似地，也可以有LL(k)文法，也就是需要向前文法，也就是需要向前查看查看K个符号才能够确定选择哪个产生式。通常个符号才能够确定选择哪个产生式。通常采用采用K=1，个别情况采用个别情况采用K=2。示例【例例4.4】文法文法G4S：SaABAbBAcAABaBd计算可选集：计算可选集：SELECT(SaABSELECT(SaAB) )aaSELECT(AbBSELECT(AbB) )bbSELECT(AcASELECT(AcA) )ccSEL
36、ECT(A)SELECT(A)FOLLOW(A)FOLLOW(A)a,da,dSELECT(Ba)SELECT(Ba)aaSELECT(Bd)SELECT(Bd)dd显然有：显然有：SELECT(AbB)SELECT(AcASELECT(AbB)SELECT(AcA) )bcbc SELECT(AbB)SELECT(ASELECT(AbB)SELECT(A) )ba,dba,d SELECT(AcA)SELECT(ASELECT(AcA)SELECT(A) )ca,dca,d SELECT(Ba)SELECT(Bd)SELECT(Ba)SELECT(Bd)adad 所以，该文法是所以，该文法是
37、LL(1)LL(1)文法。文法。示例【例例4.54.5】 设文法设文法G G5 5SS为：为：SaASSaASSbSbAbAAbAAA因为有：因为有：SELECT(SaASSELECT(SaAS) ) FIRST(aASFIRST(aAS) )aaSELECT(Sb)SELECT(Sb) FIRST(b)FIRST(b)bbSELECT(AbASELECT(AbA) ) FIRST(bAFIRST(bA) )bbSELECT(A)SELECT(A)FOLLOW(A)FOLLOW(A)FIRST(S)FIRST(S)a,ba,b所以：所以：SELECT(SaAS)SELECT(SbSELECT(
38、SaAS)SELECT(Sb) )ababSELECT(AbA)SELECT(ASELECT(AbA)SELECT(A) )baba，bb因因此此，该该文文法法不不是是LL(1)LL(1)文文法法，因因而而也也就就不不可可能能进行确定的自顶向下语法分析。进行确定的自顶向下语法分析。原因原因从从对对输输入入串串abab的的下下列列两两种种不不同同推推导导过程来看：过程来看：第一种推导过程可为：第一种推导过程可为： S S aASaAS abASabAS abSabS 在在句句型型abSabS中中由由于于S S不不能能推推出出，所所以以第第一种推导过程推不出一种推导过程推不出abab；第二种推导过
39、程可为：第二种推导过程可为： S S aASaAS aSaS abab 第二种推导过程推出了第二种推导过程推出了abab。以上两种推导中，当第二步推导时当前以上两种推导中，当第二步推导时当前输入符为输入符为b b，对句型对句型aASaAS中的中的A A用哪个产生用哪个产生式推导不能唯一确定，也就是导致了这式推导不能唯一确定，也就是导致了这个文法不能进行确定的自顶向下分析。个文法不能进行确定的自顶向下分析。也即非也即非LLLL（1 1）文法是不能进行确定的自文法是不能进行确定的自顶向下分析。顶向下分析。结论结论确定的自顶向下语法分析要求文法是确定的自顶向下语法分析要求文法是LLLL（1 1）文法
40、。文法。二、二、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去准确匹配，从而解决回溯问题去准确匹配，从而解决回
41、溯问题。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
42、 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 2XXk k,X,X1 1,
43、 , X X2 2,X Xk k都都是是非非终终结结符符，首首先先把把FIRST(XFIRST(X1 1) )加加入入FIRST()FIRST()中中；若若X X1 1X X2 2XXi 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集的算法中，第集的算法中，第条规则中的情条规则中的情况最复杂，下面具体说明一下。况最复杂
44、，下面具体说明一下。设设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)F
45、IRST(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）FI
46、RST（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集不集不再增大为
47、止。再增大为止。若若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)
48、，而，而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
49、.8】若文法若文法G8S为：为：SABSbCAAbBBaDCADCbDaSDc求求各非终结符的各非终结符的FOLLOW集集FOLLOW(S)FOLLOW(S) FOLLOW(D) FOLLOW(D) ( S ( S是文法的开始符号，是文法的开始符号，DaSDaS) ) 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)(
50、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
51、)FIRST(b)bSELECT(DaS)FIRST(aS)aSELECT(Dc)FIRST(c)c再来考虑计算产生式是再来考虑计算产生式是_产生式，其可产生式，其可选集为相应产生式左部的选集为相应产生式左部的FOLLOW集。集。SELECT(A)FOLLOW(A)a，c，SELECT(B)FOLLOW(B)再考虑复杂的情况，产生式的右部是非终结符再考虑复杂的情况，产生式的右部是非终结符开头的，其可选集的计算要取决于相应产生式开头的，其可选集的计算要取决于相应产生式右部的符号是否能够推导出右部的符号是否能够推导出。ABSELECT(SAB)FIRST(AB)FOLLOW(S)b,a,ADSEL
52、ECT(CAD)FIRST(AD)a,b,c*结果结果最后将产生式的可选集整理如下：最后将产生式的可选集整理如下：SELECT(SAB)b,a,SELECT(SbC)bSELECT(A)a，c，SELECT(Ab)bSELECT(B)SELECT(BaD)aSELECT(CAD)a,b,cSELECT(Cb)bSELECT(DaS)aSELECT(Dc)c判断是否为判断是否为LL(1)文法文法因为：因为：SELECT(SAB)SELECT(SbC)b,a,bbSELECT(A)SELECT(Ab)a，c，bSELECT(B)SELECT(BaD)aSELECT(CAD)SELECT(Cb)a,
53、b,cbSELECT(DaS)SELECT(Dc)ac结论：不是结论：不是LL(1)文法文法由于关于非终结符由于关于非终结符S的产生式的可选集的的产生式的可选集的交集不为空集，即意味着当前的最左非交集不为空集，即意味着当前的最左非终结符为终结符为S，面临的输入符为面临的输入符为b时，可以时，可以选择产生式选择产生式SAB或者或者SbC来匹配。同来匹配。同样，关于非终结符样，关于非终结符C的产生式的可选集的的产生式的可选集的交集也不为空集。因此，这个文法的交集也不为空集。因此，这个文法的自自顶向下语法分析动作是不确定。顶向下语法分析动作是不确定。所以，该文法不是所以，该文法不是LL(1)文法。文
54、法。三、某些非三、某些非LL(1)文法到文法到LL(1)文法的等价转换文法的等价转换LL(1)文法的性质：文法的性质：LL(1)文法是无二义性的；文法是无二义性的；LL(1)文法不含左递归；文法不含左递归；LL(1)文法没有公共左因子。文法没有公共左因子。非非LL(1)文法的改造文法的改造消除左递归消除左递归消除回溯：消除回溯：提取左公因子提取左公因子1.消除文法的左递归消除文法的左递归当一个文法是左递归文法时，采用自顶向下分当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进人无穷循环之中。文法左析法会使分析过程进人无穷循环之中。文法左递归是指文法中的某个非终结符递归是指文法中的某个非
55、终结符A存在推导存在推导AA，而自顶向下分析法是采用最左推导，而自顶向下分析法是采用最左推导，即每次替换的都是当前句型中的最左非终结符，即每次替换的都是当前句型中的最左非终结符，当试图用非终结符当试图用非终结符A去匹配输人串时，结果使去匹配输人串时，结果使当前句型的最左非终结符仍然为当前句型的最左非终结符仍然为A，也就是说，也就是说，在没有读进任何输人符号的情况下，又重新要在没有读进任何输人符号的情况下，又重新要求求A去进行新的匹配，于是造成无穷循环。所去进行新的匹配，于是造成无穷循环。所以采用自顶向下分析法进行语法分析需要消除以采用自顶向下分析法进行语法分析需要消除文法的左递归性。文法的左递
56、归性。+ +递归文法递归文法【递归文法递归文法】递归文法是指对文法中任一递归文法是指对文法中任一非终结符非终结符A，若存在一个推导序列，在推若存在一个推导序列，在推出的符号串中又出现了该非终结符本身，出的符号串中又出现了该非终结符本身，即即AA，则该文法是递归的。则该文法是递归的。若文法中对任一非终结符若文法中对任一非终结符A有推导有推导AA，则称该文法是则称该文法是左递归左递归的。的。若文法中对任一非终结符若文法中对任一非终结符A有推导有推导AA，则称该文法是则称该文法是右递归右递归的。的。+ + + +左递归左递归左递归又可以分为直接左递归和间接左左递归又可以分为直接左递归和间接左递归。递
57、归。【直接左递归直接左递归】若文法中的某一产生式形若文法中的某一产生式形如如AA，V*，则称该文法是直接左则称该文法是直接左递归的。递归的。【间接左递归间接左递归】若文法中存在某一非终结若文法中存在某一非终结符符A，使得使得AA至少需要两步推导，至少需要两步推导，则称该文法是间接左递归的。则称该文法是间接左递归的。+ +消除直接左递归的方法一消除直接左递归的方法一【方法一方法一】只需将产生式进行改写，使之不含左只需将产生式进行改写，使之不含左递归。为此需要引进一个新的非终结符，把含递归。为此需要引进一个新的非终结符，把含有左递归的产生式改写成右递归的产生式即可。有左递归的产生式改写成右递归的产
58、生式即可。设有产生式是关于非终结符设有产生式是关于非终结符A的直接左递归的直接左递归AA|（,V*，且，且不以不以A开头）开头）对对A引入一个新的非终结符引入一个新的非终结符A，把上式改写为：把上式改写为：AAAA|改写前后产生式是等价的。改写前后产生式是等价的。前式推导：前式推导：AAAAnn后式推导：后式推导：AAAAnAn从从A推出的符号串的集合是相同的，也就是推出的符号串的集合是相同的，也就是说，它们是等价的。说，它们是等价的。+ + +一般情况一般情况若某文法中非终结符若某文法中非终结符A的产生式形如：的产生式形如：AA1|A2|An-1|An|1|2|m-1|m其中：其中：i、jV
59、*，i=1,n，j=1,m，且，且j不以不以A开头，开头，则可用下述方法消除直接左递归：则可用下述方法消除直接左递归：引入一个新的非终结符引入一个新的非终结符AA1A|2A|m-1A|mAA1A|2A|n-1A|nA|示例示例【例例410】算术表达式算术表达式文法文法G7E：EE+T|TTT*F|FFi|（E）消除直接左递归后，文法变成：消除直接左递归后，文法变成：ETEE+TE|TFTT*FT|Fi|（E）消除直接左递归的方法二消除直接左递归的方法二【方法二方法二】采用扩充采用扩充BNF表示法改写含直接左递表示法改写含直接左递归的产生式。归的产生式。在扩充的在扩充的BNF表示中，有如下约定：
60、表示中，有如下约定：花括号花括号：表示符号串表示符号串的可出现的可出现0次或多次，即表次或多次，即表示示*。：表示符号串表示符号串的可出现的可出现m次至次至n次，次，m为最小次数，为最小次数，n为最大次数。为最大次数。【例如例如】AA|可改写为：可改写为：Am mn n方括号方括号：表示表示10即即的出现可有可无，它的出现可有可无，它用来表示可供选择的符号串。用来表示可供选择的符号串。【例如例如】A|可改写为：可改写为：A圆括号（圆括号（）利用圆括号可在产生式右部中提取公共因子。利用圆括号可在产生式右部中提取公共因子。【例如例如】A1|2|m-1|m可改写为：可改写为：A（1|2|m-1|m）
61、示例示例【例例411】算术表达式的文法算术表达式的文法G G7 7EE为：为：EET|TTT*F|FFi|（E）对文法对文法G7用扩充用扩充BNF表示法对其进行改表示法对其进行改写。写。示例示例因为产生式因为产生式EET|T表示表示E所生成的符所生成的符号串由号串由T开头且后跟开头且后跟0个或多个十个或多个十T；而产而产生式生式TT* *F|F表示表示T所生成的符号串由所生成的符号串由F开头且后面跟开头且后面跟0个或多个个或多个* *F，所以该文所以该文法可改写成如下形式：法可改写成如下形式：ET+TTF* *FFi|（E）消除间接左递归的方法消除间接左递归的方法消除直接左递归是比较容易的，但
62、是消消除直接左递归是比较容易的，但是消除间接左递归就不是那么容易的事。除间接左递归就不是那么容易的事。【方法一方法一】采用代入法把间接左递归变成采用代入法把间接左递归变成直接左递归。直接左递归。【方法二方法二】直接改写文法。直接改写文法。示例示例【例例412】设有文法设有文法G10S：SA|AS因为因为SAS，所以所以S是一个间接递归的是一个间接递归的非终结符。为了消除这种间接左递归，将非终结符。为了消除这种间接左递归，将式式代入代入式，即可得到与原文法等价的文法（可式，即可得到与原文法等价的文法（可以证明）：以证明）：SS|式是式是直接左递归的，可以采用前面介绍的消直接左递归的，可以采用前面
63、介绍的消除直接左递归的方法，对文法进行改写后可得除直接左递归的方法，对文法进行改写后可得文法：文法：SSSS|2消除回溯消除回溯在在自自顶顶向向下下分分析析过过程程中中，当当某某个个非非终终结结符符A A对对应应多多个个候候选选式式时时，如如果果其其中中有有几几个个候候选选式式的的左左端端第第一一符符号号相相同同，那那么么就就会会使使得得语语法法分分析析程程序序无无法法根根据据当当前前要要替替换换的的非非终终结结符符和和当当前前输输人人符符唯唯一一地地决决定定选选用用哪哪个个候候选选式式来来替替换换A A，只只能能采采用用试试探探的的办办法法，任任选选某某个个候候选选式式去去试试探探一一次次。
64、如如果果不不能能导导致致最最终终正正确确地地匹匹配配，只只得得再再换换另一个候选式去试探，从而引起回溯另一个候选式去试探，从而引起回溯。在在自自顶顶向向下下分分析析过过程程中中，由由于于回回溯溯需需要要推推翻翻前前面面的的分分析析，包包括括已已做做的的一一大大堆堆语语义义工工作作，重重新新去去进进行行试试探探，这这样样大大大大降降低低了了语语法法分分析析器器的的工工作作效效率率，因因此此，需需要要消消除除回回溯。溯。对对于于上上述述情情况况（即即，同同一一非非终终结结符符有有多多个个候候选选式式的的首首符符相相同同），可可以以采采用用提提“左左因因子子”的的方方法法来来改改造造文文法法，使使得
65、得文文法法的的每每个个非非终终结结符符的的各各个个候候选选式式的的首首符符都都不不相相同同，从而可以消除上面所说的回溯现象。从而可以消除上面所说的回溯现象。提取公共左因子提取公共左因子若若A A的产生式为：的产生式为： AA1 1|2 2经过提取公共左因子经过提取公共左因子，原产生式变为：原产生式变为： AAAA A A1 1|2 2 一般情况一般情况若若A A的产生式为：的产生式为： AA1 1|2 2|k-1k-1 | |k k经过提取公共左因子经过提取公共左因子，原产生式变为：原产生式变为： AAAA A A1 1|2 2|k-1k-1 | |k k 如果如果m m、n n（其中其中1m
66、1m、nknk）中仍中仍然含有公共左因子，则可反复提取它们然含有公共左因子，则可反复提取它们的共同左因子，直到每个新引入的非终的共同左因子，直到每个新引入的非终结符的产生式再无公共左因子为止。结符的产生式再无公共左因子为止。 示例示例【例例415】前面例前面例46中的文法中的文法G6S为：为：SxAyA* * *|* *关于关于A的产生式有公共左因子，提取公共的产生式有公共左因子，提取公共左因子左因子a后，文法改写为：后，文法改写为：SxAyA* *AA* *|计算该文法的可选集计算该文法的可选集SELECT（SxAy）xSELECT（A* *A）* *SELECT（A* *）* *SELEC
67、T（A）FOLLOW（A）FOLLOW（A）y因为：因为：SELECT（ A* *） SELECT（ A） * *y所以，上述文法是所以，上述文法是LL（1）文法，这时再用自文法，这时再用自顶向下分析方法分析符号串顶向下分析方法分析符号串x* *y，就不会产生就不会产生回溯了。回溯了。示例示例【例例4 41515】设有文法设有文法G G1313SS为：为： Sa S bSa S b SabSab关关于于S S的的产产生生式式有有公公共共左左因因子子，提提取取公公共共左左因因子子a a后，文法改写为：后，文法改写为： SaSa（S b |bS b |b）进一步变换为文法进一步变换为文法G G13
68、13 S, S,其产生式为：其产生式为： Sa SSa S SS b |b SS b |b计算该文法的可选集计算该文法的可选集SELECT（SaS）aSELECT（SSb）FIRST（Sb）FIRST（S）aSELECT（Sb）b因为：因为：SELECT（ SSb） SELECT（ Sb）ab所以，上述文法所以，上述文法是是LL（1）文法，可以进文法，可以进行确定的自顶向下的语法分析。行确定的自顶向下的语法分析。三、确定的自顶向下分析方法三、确定的自顶向下分析方法特征特征根据下一个输入符号为当前要处根据下一个输入符号为当前要处理的非终结符选择产生式理的非终结符选择产生式要求要求文法是文法是LL
69、(1)的的语法分析方法：语法分析方法：1递归下降分析法递归下降分析法2预测分析法预测分析法1.递归下降分析法递归下降分析法递归子程序法是比较简单直观易于构造递归子程序法是比较简单直观易于构造的一种语法分析方法。的一种语法分析方法。实现思想：文法中每个非终结符对应一实现思想：文法中每个非终结符对应一个递归过程个递归过程(子程序子程序)，每个过程的功能，每个过程的功能是识别由该非终结符推出的串，当某非是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时能够按终结符的产生式有多个候选式时能够按LL(1)形式可唯一地确定选择某个候选式形式可唯一地确定选择某个候选式进行推导。进行推导。示例示例
70、【例例410】算术表达式算术表达式文法文法G7E：EE+T|TTT* *F|FFi|（E）消除直接左递归后，文法变成：消除直接左递归后，文法变成：ETEE+TE|TFTT* *FT|Fi|（E）计算计算FIRST集与集与FOLLOW集集各非终结符的各非终结符的FIRSTFIRST集为：集为：FIRST(E)=FIRST(E)=(,i(,iFIRST(E)=FIRST(E)=+ +FIRST(T)=FIRST(T)=(,i(,iFIRST(T)=FIRST(T)=* *FIRST(F)=FIRST(F)=(,i(,i 各非终结符的各非终结符的FOLLOWFOLLOW集集合为：合为：FOLLOW(
71、E)=FOLLOW(E)=),),FOLLOW(E)=FOLLOW(E)=) )，FOLLOW(T)=FOLLOW(T)=，) )，FOLLOW(T)=FOLLOW(T)=,),)，# # FOLLOW(F)=FOLLOW(F)=* *, ,，),#),#计算计算SELECT集集各产生式的各产生式的SELECT集为：集为：SELECT(ETE)FIRST(TE)（,iSELECT(E十十TE)SELECT(E)FOLLOW(E)），），SELECT(TFT)FIRST(FT)（，（，iSELECT(T* *FT)* *SELECT(T)FOLLOW(T)十，），十，），SELECT(F（E）)
72、（SELECT(Fi)i该文法是该文法是LL(1)文法文法因为：因为：SELECT(E十十TE)SELECT(E)SELECT(T* *FT)SELECT(T)SELECT(F（E）)SELECT(Fi)所所以以，该该文文法法中中关关于于同同一一个个非非终终结结符符的的产产生生式式的的SELECT集集两两两两不不相相交交，因因此此，该该文文法法是是LL（1）文文法法，可可以以进进行行确确定定的的自自顶向下语法分析。顶向下语法分析。递归子程序递归子程序EETE非终结符非终结符E对应的子程序为：对应的子程序为：E()T();E();递归子程序递归子程序EE+TE|非终结符非终结符E对应的子程序为：
73、对应的子程序为：E()ifsym+read(sym);T();E();elseifsymFOLLOW(E)return;elseerror();递归子程序递归子程序TTFT非终结符非终结符T对应的子程序为：对应的子程序为：T()F();T();递归子程序递归子程序TT* *FT|非终结符非终结符T对应的子程序为：对应的子程序为：T()ifsym* *read(sym);F();T();elseifsymFOLLOW(T)return;elseerror();递归子程序递归子程序FFi|（E）非终结符非终结符F对应的子程序为：对应的子程序为：F()ifsym=iread(sym);elseifs
74、ym( (read(sym);E();ifsym)read(sym);elseerror();主程序主程序main()read(sym);E();if(sym=#)printf(“分析成功分析成功”)；elseprintf(“分析失败分析失败”)；示例示例【例例411】算术表达式的文法算术表达式的文法G G7 7EE：EET|TTT*F|FFi|（E）对文法对文法G7用扩充用扩充BNF表示法对其进行改写表示法对其进行改写成如下形式：成如下形式：ET+TTF* *FFi|（E）递归子程序递归子程序EET+T非终结符非终结符E对应的子程序为：对应的子程序为：E()T();while(sym=+)r
75、ead(sym);T();递归子程序递归子程序TTF* *F非终结符非终结符T对应的子程序为：对应的子程序为：T()F();while(sym=* *)read(sym);F();递归子程序递归子程序FFi|（E）非终结符非终结符F对应的子程序为：对应的子程序为：F()ifsym=iread(sym);elseifsym( (read(sym);E();ifsym)read(sym);elseerror();主程序主程序main()read(sym);E();if(sym=#)printf(“分析成功分析成功”)；elseprintf(“分析失败分析失败”)；2.预测分析法预测分析法预测分析法
76、用一个分析栈存放当前要替换的非预测分析法用一个分析栈存放当前要替换的非终结符的某个候选式的符号串（倒放在栈内），终结符的某个候选式的符号串（倒放在栈内），当非终结符呈现在栈顶时，它就是当前非终结当非终结符呈现在栈顶时，它就是当前非终结符；此外，还使用一张矩阵形式的预测分析表，符；此外，还使用一张矩阵形式的预测分析表，它是根据可选集构造的，它的入口指出了某非它是根据可选集构造的，它的入口指出了某非终结符和某终结符匹配时所应选择的候选式和终结符和某终结符匹配时所应选择的候选式和语义动作。预测分析程序的总控程序就是利用语义动作。预测分析程序的总控程序就是利用栈顶符号和当前输人符号对输人串进行预测分栈
77、顶符号和当前输人符号对输人串进行预测分析，而预测的信息则存放在预测分析表的相应析，而预测的信息则存放在预测分析表的相应入口里。入口里。一个预测分析程序是由三个部分组成一个预测分析程序是由三个部分组成总控程序（表驱动程序）总控程序（表驱动程序）预测分析表预测分析表先进后出的语法分析栈先进后出的语法分析栈预测分析程序的模型预测分析程序的模型预测分析程序实际上就是一个下推自动预测分析程序实际上就是一个下推自动机，它是用下推自动机来识别输入符号机，它是用下推自动机来识别输入符号串的。串的。a a1 1 a a2 2 a ai i a an n # #输入串输入串总控程序总控程序预测分析表预测分析表（L
78、L(1)LL(1)分析表）分析表）栈顶符号栈顶符号# #x x1 1x xn n 分析栈分析栈预测分析法表预测分析法表(LL(1)LL(1)分析表分析表) )表示表示: :一个矩阵（或二维数组）一个矩阵（或二维数组）M MA A ，a a行行: :对应文法的一个非终结符对应文法的一个非终结符A A列列: :对应一个终结符对应一个终结符a a或输入结束符或输入结束符“”。大小大小: mn, m: mn, m是文法中非终结符数，是文法中非终结符数，n n是终结是终结符数符数1 1（外加一个结束符（外加一个结束符“”）。）。数组的值数组的值M MA A ，a a ：存放着面临输人符号存放着面临输人符
79、号a a时，所应选择时，所应选择A A的某条产生式，即指出当前推的某条产生式，即指出当前推导所应使用的产生式。数组中的空白入口中应导所应使用的产生式。数组中的空白入口中应填人适当的出错处理子程序名或编号，即此种填人适当的出错处理子程序名或编号，即此种情况下存在语法错误。情况下存在语法错误。预测分析表的构造预测分析表的构造预测分析法的实现关键在于预测分析表。预测分析法的实现关键在于预测分析表。预测分析表是指分析栈中的文法符号与预测分析表是指分析栈中的文法符号与输入串中的符号的一种匹配关系，记为输入串中的符号的一种匹配关系，记为M MA A，a a，其中其中A A为分析栈中的符号，为分析栈中的符号
80、，a a为输入符号。为输入符号。 可以由可选集直接来构造预测分析表。可以由可选集直接来构造预测分析表。预测分析表的构造算法预测分析表的构造算法预测分析表的构造算法是：预测分析表的构造算法是：对每个终结符对每个终结符aSELECTaSELECT（AA），把），把AA填入填入MAMA，aa中；中；把所有无定义的把所有无定义的MAMA，aa均填上均填上“出错标出错标志志”。 结论结论上述算法可应用于任何文法上述算法可应用于任何文法G G以构造它的以构造它的分析表分析表M M。但对于某些文法，有些但对于某些文法，有些MAMA，aa中可能有若干个产生式，或者说有些中可能有若干个产生式，或者说有些M MA
81、A，aa可能是多重定义的。如果可能是多重定义的。如果G G是左递是左递归或回溯的，那么归或回溯的，那么M M至少含有一个多重定至少含有一个多重定义入口。因此，消除左递归和提取公共义入口。因此，消除左递归和提取公共左因子将有助于获得无多重定义的分析左因子将有助于获得无多重定义的分析表表M M。可以证明：可以证明：一个文法一个文法G G的预测分析表的预测分析表M M不含多重定义入口，不含多重定义入口，当且仅当该文法是当且仅当该文法是LLLL（l l）文法。文法。示例示例【例例419】前前述述算算术术表表达达式式的的文文法法G7E为：为：ETEE十十TE|TFTT* *FT|Fi|（E）表达式文法的
82、预测分析表表达式文法的预测分析表i+* *()#EETEETEEE+TEEETTFTTFTTTT* *FTTTFFiF(E)预测分析程序的工作流程预测分析程序的工作流程预测分析程序在总控程序控制下进行对预测分析程序在总控程序控制下进行对输入串的分析，利用分析栈记录分析过输入串的分析，利用分析栈记录分析过程中使用的文法符号。输入串中存放的程中使用的文法符号。输入串中存放的终结符号串，分析栈中存放的是终结符终结符号串，分析栈中存放的是终结符和非终结符组成的符号串。和非终结符组成的符号串。 预测分析表的工作流程预测分析表的工作流程-1分析开始时，首先将栈底符号分析开始时，首先将栈底符号“”及及文法的
83、开始符号文法的开始符号S依次推入分析栈的栈底，依次推入分析栈的栈底，并对各条指示器置初值，此时分析栈和并对各条指示器置初值，此时分析栈和输入串的格局为输入串的格局为(用箭头表示输入串指针用箭头表示输入串指针和栈顶指针当前所指向的位置和栈顶指针当前所指向的位置)：#S栈顶指针栈顶指针 a1a2an#输入串指针输入串指针 预测分析表的工作流程预测分析表的工作流程-2设在分析的某一步，分析栈和余留的输设在分析的某一步，分析栈和余留的输入符号串处于如下的格局：入符号串处于如下的格局： #X1X2Xm-1Xm栈顶指针栈顶指针 a1aiai+1an#输入串指针输入串指针 此时，可根据栈顶的文法符号此时，可
84、根据栈顶的文法符号X Xm m的不同的不同情况，分别处理：情况，分别处理： 情形一情形一若若X Xm m为终结符，即为终结符，即x xm mVVT T，且，且X Xm ma ai i“”时，则表明栈顶符号已与当前正扫时，则表明栈顶符号已与当前正扫视的输入符号相匹配，此时应将视的输入符号相匹配，此时应将X Xm m从栈中从栈中弹出，而且将输入指针向前移动一个位弹出，而且将输入指针向前移动一个位置至置至a ai i1 1。从而得到如下格局：从而得到如下格局：a1aiai+1an#输入串指针输入串指针 #X1X2Xm-1栈顶指针栈顶指针 情情形形二二若若X Xm m为非终结符，即为非终结符，即X X
85、 m mVVN N，则以则以 X Xm m及及 a ai i组成组成符号对（符号对（X Xm m，a ai i）查分析表查分析表 M M，假设假设M MX Xm m，a ai i中存放着关于中存放着关于X Xm m的一个产生式的一个产生式X Xm m ABCABC，此时，此时，首先将首先将X Xm m从分析栈中弹出，并将该产生式右部从分析栈中弹出，并将该产生式右部ABCABC的逆替换栈顶符号，即把的逆替换栈顶符号，即把ABCABC按逆序推入栈中按逆序推入栈中（此即用该产生式推导一步）。输入指针不动。（此即用该产生式推导一步）。输入指针不动。从而得到新的格局如下：从而得到新的格局如下： 否则出错
86、，即否则出错，即M MX Xm m，a ai i“ERROR”ERROR”，则调用出则调用出错处理程序来进行处理或宣告分析失败。错处理程序来进行处理或宣告分析失败。 a1aiai+1an#输入串指针输入串指针 #X1X2Xm-1CBA栈顶指针栈顶指针 情形三情形三若若x xm ma ai i“”，即输入串与分析栈均即输入串与分析栈均为空，则表明输入符号串已完全得到匹为空，则表明输入符号串已完全得到匹配，此时可宣告分析成功，结束工作，配，此时可宣告分析成功，结束工作，接收输入串。此时的格局如下：接收输入串。此时的格局如下： a1aiai+1an#输入串指针输入串指针 #栈顶指针栈顶指针 反复使用
87、第二步进行处理，直至分析成反复使用第二步进行处理，直至分析成功或者分析失败。功或者分析失败。示例示例【例例419】算术表达式的文法算术表达式的文法G7E为：为：ETEE十十TE|TFTT* *FT|Fi|（E）给出输入串给出输入串ii的分析过程：的分析过程：分析栈分析栈(栈顶符栈顶符,输入输入符符)剩余输入串剩余输入串1#E(E,i)查表查表E TEi+i#2#ET(T,i)查表查表T FTi+i#3#ETF(F,i)查表查表Fii+i#4#ETi(i,i)匹配匹配+i#5#ET(T,+)查表查表T +i#6#E(E,+)查表查表E+TE+i#7#ET+(+,+)匹配匹配i#8#ET(T,i)
88、查表查表T FTi#9#ETF(F,i)查表查表F ii#10#ETi(i,i)匹配匹配#11#ET(T,#)查表查表T #12#E(E,#)查表查表E #13#(#,#)成功接收成功接收#示例示例【例例419】设有文法设有文法G16P为：为：Pbegind；XendXd；XXsYY；sYY 用预测分析法分析的步骤分为四步：用预测分析法分析的步骤分为四步：1是否需要改写文法是否需要改写文法如果文法是左递归的，或者具有公共左如果文法是左递归的，或者具有公共左因子，则需要对文法进行改写。因子，则需要对文法进行改写。因为上述文法因为上述文法G16不具有左递归和公共左不具有左递归和公共左因子，所以不需
89、要对文法进行改写，直因子，所以不需要对文法进行改写，直接证明该文法是接证明该文法是LL（1）文法即可。文法即可。2判断文法是否为判断文法是否为LL(1)文法文法该文法的各个产生式的该文法的各个产生式的SELECT集为：集为：SELECT（Pbegind；Xend）=beginSELECT（Xd；X）=dSELECT（XsY）=sSELECT（Y；sY）=；SELECT（Y ）=FOLLOW（Y）=FOLLOW（X）=end因为：因为：SELECT(Xd；X)SELECT(XsY)dsSELECT(Y；sY)SELECT(Y )；end所以，该文法是所以，该文法是LL（1）文法。文法。3根据可选
90、集构造预测分析表根据可选集构造预测分析表根据构造预测分析表的算法，可得上述根据构造预测分析表的算法，可得上述文法的预测分析表如表所示。文法的预测分析表如表所示。beginds;end#PPbegind；XendXXd；X XsYYY；sY Y 4.给出输入串的分析过程给出输入串的分析过程给出输入串给出输入串begind；s；send的分析过的分析过程程:分析栈分析栈(栈顶符栈顶符,输入输入符符)剩余输入串剩余输入串1#P(P,begin)查表查表begind；s；send2#endX；dbegin(begin,begin)匹配匹配d；s；send3#endX；d(d,d)匹配匹配；s；send
91、4#endX；(；,；)匹配匹配s；send5#endX(X,s)查表查表XsYs；send6#endYs(s,s)匹配匹配；send7#endY(Y,；)查表查表Y；sY；send8#endYs；(；,；)匹配匹配send9#endYs(s,s)匹配匹配end10#endY(Y,end)查表查表Y end#end(end,end)匹配匹配12#(#,#)成功接收成功接收 LL(1)分析中的一种错误处理办法分析中的一种错误处理办法发现错误1栈栈顶的顶的终结符与当前输入符不匹配终结符与当前输入符不匹配2非终结符非终结符A于栈顶，面临的输入符为于栈顶，面临的输入符为a，但分析表但分析表M的的MA,
92、a为为空空“应急”恢复策略跳过输入串中的一些符号直至遇到跳过输入串中的一些符号直至遇到“同步符号同步符号”为止。为止。同步符号的选择1把把FOLLOW(A)中的所有符号作为中的所有符号作为A的同步符号。跳过输入串的同步符号。跳过输入串中的一些符号直至遇到这些中的一些符号直至遇到这些“同步符号同步符号”，把，把A从栈中弹出，从栈中弹出，可使分析继续可使分析继续2把把FIRST(A)中的符号加到中的符号加到A的同步符号集，当的同步符号集，当FIRST(A)中的符中的符号在输入中出现时，可根据号在输入中出现时，可根据A恢复分析恢复分析小结小结1.语法分析的任务；语法分析的任务；2.确定的自顶向下语法分析方法的基本思确定的自顶向下语法分析方法的基本思想，存在的问题是：左递归和回溯；想，存在的问题是：左递归和回溯；3.分析方法：预测分析法。分析方法：预测分析法。
