编译原理自顶向下语法分析法

1、第四章 自顶向下语法分析方法语法分析是编译过程的核心部分。语法分析的任务是：按照文法，从源程序符号串中识别出各类语法成份，同时进行语法检查，为语义分析和代码生成作准备。执行语法分析任务的程序称为分析程序。也称为语法分析器，它是编译程序的主要子程序之一。在第二章中我们已经介绍过。通过语法分析可建立起相应的语法树。按语法树的建立方法，我们将语法分析方法分成两大类，即自顶向下分析和自底向上分析。下面，我们先介绍自顶向下分析。本章重点：自顶向下分析、LL（1）分析，然后再介绍自底向上分析。第一节 自顶向下分析方法一、带回溯的自顶向下分析算法这是自顶向下分析的一般方法，即对任一输入符号串，试图用一切可能

2、的方法，从识别符号出发，根据文法自上而下地为输入串建立一棵语法树。下面用一个简单例子来说明这种过程：假定有文法GS：Scd Aab|a 以及输入串w=cad为了自上而下地构造w的语法树，我们首先按文法的识别符号产生根结点S，并让指示器IP指adcASbadcASdcAS向输入串的第一符号c。然后，用S的规则（此处左部为S的规则仅有一条）把这棵树发展为 （ a） （b） （c） 图3-1-1图3-1-1a图。我们希望用S的子结从左至右匹配整个输入串w。首先，此树的最左子结是终结符c为标志的子结，它和输入串的第一个符号相匹配。于是，我们就把IP调整为指向下一输入符号a，并让第二个子结A去进行匹配，

3、非终结符A有二个选择，我们试着用它的第一个选择去匹配输入串，于是把语法树发展为图3-1-1b图。子树A的最左子结和IP所指的符号相符，然后我们再把IP调为指向下一符号d并让A的第二个子结进入工作。但A的第二个子结为终结符号b，与IP当前指的符号d不一致。因此，A宣告失败。这意味着A的第一个选择此刻不适用于构造w的语法树。这时，我们应该回头（回溯）看A是否还有别的选择。为了实现回溯，我们一方面应把A的第一个选择所生长的子树注销掉；另一方面，应把IP恢复为进入A时的原值，也就是让它重新指向第二输入符号a。现在我们试探用A的第二个选择，即考虑生成图3-1-1c的语法树。由于子树A只有一个子结a，而且

4、，它和IP所指的符号相一致，于是，A完成了匹配任务。在A获得匹配后，指示器指向下一个未被触及的符号d。在S的第二子结A完成匹配后，接着就轮到第三个子结d进行工作。由于这个子结和最后一个输入符号相符，于是，我们完成了构造语法树的任务，证明了w是文法G s的一个句子。上述自顶向下地为输入符号w建立语法树的过程，实际上也是设法建立一个最左推导序列，以便通过一步步推导将输入串推导出来。很明显，对于输入串w可以通过如下的推导过程将其推导出来：Sc A da bW：cad 2p指示口SCAdcad所以用最左推导，是因为我们对输入串是自左向右扫描的，只有使用最左推导，才能保证按扫描顺序去匹配输入串。在上述推

5、出符号串w的过程中，由于出现在符号串中的非终结符号只有一个，因此，未明显地表现出最左推导的性质。根据以上分析，不难编出程序来实现这种分析的算法。但是，上述这种自顶向下的分析算法存在着一定的困难和缺点。困难表现在不能为左递归文法构造自顶向下的语法分析器（上述所举例子的文法Gs是不具有在递归性的）。缺点主要表现在存在着回溯问题。当然，应用带回溯的自顶向下的分析算法还必须将文法规则存放于内存。下面将具体介绍这种分析算法所存在的问题及其解决办法。二、存在问题及解决办法（一）左递归问题自顶向下分析法只有规则排列得合适时，才能正确工作。该法的一个基本缺点是不能处理具有左递归的文法。如下所示。AAB|BbB

6、Ac|dAa    BA CB bA C如：直接左递归 和 间接左递归AABACcBbACcSSa|bSSaSaSaSaAaAB|BbBAc|d无法确定语法树的终止，清除直接左递归的较好方法是改改为右递归如：SSa|b 改为SbSSaS|一般情况下，直接左递归的形式可为：消除AA1|A2| Am|1|2n清除左递归后改写为：A1A1|2A1 |nA1A11A|2A1 |mmA1|对于间接左递归的消除，需先将间接左递归变为直接左递归，然后再接上述方法消除。条件是文法中无AA的有害规则和 或A的空产生式算法：SQc|cQRb|b SSabc 排列R、Q、SR代入Q，Q

7、Sab|ab|bQ代入S，SSabc|abc|bc|cS（abc|bc|c）SSabc S|QRb|bRSa|a（二）回溯 问题 当产生式都有多个选择时，选那个输入串去匹配为了避免回溯，就必须保证：对文法的任何非终结符号特别是规则都右部有多个选择的非终结符号，当用它去匹配输入串时，应是确定无疑的。即：U11|22|nn该规则右部有n个选择,为了实现目的,我们对文法的要求是:F1rstIRST（i）f1rstFIRST（j）=（ij）定义1：设G=（VT，VN，S，P）是上下文无关文法FIRST（）=a| Þa，aVT，V*若Þ，则规定FIRST（）即对文法中的任意一个非终符

8、号，其规则右部有多个选择时，那么，由各个选择所推出的终结符号串的头符号集合要两两不相交。这样，就可能根据当时读进的符号是属于哪个选择的FIRST（），来唯一地确定应该选用哪个选择来匹配输入串。如当前的输入符号为b(bVT)，若bFIRST（i），则用第i个选择；若b不FIRST（i），其中i=1n，则语法错，转出错处理。这样就避免了分析过程的回溯。若文法的任一非终结符号，其规则右部的各个选择所能推出的终结符号串的头符号集合不满足两两相交的条件时，那么，要构造一个不带回溯的自顶向下的语法分析程序，需要采取什么措施呢？一般可采取改写文法的办法来解决。定义1：设G=（VT，VN，S，P）是上下文无关

9、文法F1RST（）=|Þ，VT，V*若Þ，则规定F1RST（）（三）改写文法， 当文法不满足，可改写文法提因子a1a2aian#  X 分析栈  #图4-2-1总控程序分析表mUxv|xw Ux(vx|w)提因子三、递归子程序法此方法的主要做法是：对文法中每个非终结符号U（它们都分别代表一种语法成分）,都编出一个子程序，以完成该非终结符号所对应的语法成分的分析和识别任务。某个非终结符号的语法分析子程序的功能是：用该非终结符号的规则的右部符号串去匹配输入串。分析过程是按文法规则自顶向下一级一级地分配任务，即调用有关的子程序来完成。当编译程序根据文法和当前输

10、入符号预测到下一个语法成分为U时，即预测到待匹配的输入符号串可以为从U出发所推导出的符号串相匹配时，就确定U为目标，并调用分析和识别U的子程序。在分析和识别U的过程中，有可能还要确立其他子目标并调用相应的子程序，只有在被调用的分析和识别某语法成分的子程序匹配输入串成功并正确返回时，该语法成分才算真正的获得了识别，并确定输入串无语法错误。由于这种分析方法的特点是带有预测性的，并在分析过程中对着一个目标，所以，称为预测的和面向目标的。下面，我们简单讨论一下，为什么针对某些非终结符号所编出的分析程序要编成递归子程序?。回答很简单，因为文法具有递归性。前面已讲过，自顶向下分析不能处理左递归文法，若有左

11、递归，则应改写文法予以消除。但是，消除了左递归不等于消除了文法的所有递归性质，此时，文法仍可以有右递归性或自嵌入性。如在文法中有规则UU或UU此仍为递归规则，故分析U的子程序要编成递归子程序。因为该子程序在用规则右部符号串去匹配输入串的过程中，又要调用U自己。即在通过该子程序正常出口返回调用程序以前，又要重新直接进入该子程序，这就是直接递归。此外，还有间接递归，如在文法中有规则：UV VUW那么UÞVÞUW即UUW在该情况下，在分析U的子程序中要调用分析V的子程序；而在分析U的子程序中又要调用分析V的子程序。这样，对U的分析程序就要编成递归子程序，因在进入U的分析程序以后，

12、在返回调用程序以前，又可能间接地进入自己。下面，我们举两个例子，说明如何根据文法来构造该文法的语法分析程序。例1 文法GZZ（U）|aUbUdZ|Ud|e（4-7）文法有左递归，所以，首先要改写文法：Z（U）|aUbU（dZ|e）d（4-8）由分析可知，经改写之后的文法左递归；上述两条规则，其右部均各有两个选择，但两个选择各自所推出的终结符号串的头符号集合不相交，即：（a=de=所以，文法满足构造一个不带回溯的自顶向下分析器的条件。故我们可对文法中的两个非终结符号分别编出其分析子程序。且由于有：Z Z 和 U U所以，都要编成递归子程序。我们以框图形式给出这两个子程序，见图4.2SSFSSFF

13、F递归入口(SYM)=（？读符号U(SYM)=（？出错读符号递归出口(SYM)=a？读符号U(SYM)=b？出错(a) 非终结符Z的分析程序SSSFF递归入口(SYM)=d？读符号Z(SYM)=d？读符号递归出口(SYM)=e读符号出错(b) 非终结符U的分析程序图4.2图中，除要调用递归入口和递归出口两个子程序（这两个子程序后面介绍）此外，还要调用读符号和出错处理子程序。读符号子程序的功能是：扫描下一个符号，并把它放在全程单元SYM中。出错处理子程序：当分析过程中发现有语法错误时，就调用出错处理程序，用它打印错误信息和跳过一段源程序。关于错误处理，我们将在第九章中专门讨论。当子程序调用时，在

14、读下一个符号方面，要注意衔接的正确性。我们约定：当调用某个子程序时，它所要分析的第一个符号已经读进单元SYM中；同样地，在从子程序返回报告成功之前，已经把跟在分析过的子符号串之后的那个符号读进SYM中了。上述两个子程序的框图就是按此约定画出的。第二节 LL(1)分析方法a1a2aian#  X 分析栈  #图4-2-1图4-2-1总控程序分析表m本节，我们将介绍实现自顶向下分析的另一种方法，即所谓LL(1)分析方法。如此命名该分析方法的原因在于相应的语法分析将按自左至右的顺序扫描输入符号串，并在此过程中产生一个句子的最左推导。至于括号中的“1”，则表示在分析过程中，每进行一

15、步推导，只要向前查看一个输入符号，便能确定当前所应选用的产生式（规则）。因此，我们通常把按上述方法执行语法分析任务的程序称为LL(1)分析程序或LL(1)分析器，使用这种方法进行语法分析，可借助于一张分析表及一个语法分析栈，在一个总控程序控制下很方便地实现。下面，我们将首先介绍LL(1)分析器的逻辑结构和工作过程，然后再介绍LL(1)分析器的构造方法。（一）LL(1)分析器的逻辑结构及工作过程在逻辑上，一个LL(1)分析器由一个总控程序、一张分析表和一个分析栈组成，如图4-2-1所示。其中：1、“输入”即待分析的符号串（注意，#VT，我们之所以在输入串的末尾放置一个#，仅为了分析算法格式的统一

16、）。2、分析表M可用一个矩阵（或二维数组）来表示，它概括了相应文法的全部信息。矩阵的每一行与文法的一个非终结符号A相关联，而每一列则与文法的一个终结符号或#相关联。分析表元素MA, a或者指示了当前推导所应使用的产生式，或者指出了输入串中含有语法错误。分析器对每一输入串的分析在总控程序控制下进行。其算法如下（为书写方便。在下面的叙述中，我们将分析栈按顺时钟旋转九十度）：第一步 分析开始时，首先将符号#及文法的开始符号S依次置于分析栈底部，并把各指示器调整至起始位置，即初始格局为 # S a1a2an#分析栈 输入串然后，反复执行第二步所列的工作。第二步 设在分析的某一步，分析栈及余留的输入符号

17、串处于如下的格局 aiai+1 # X1 X2Xm-1 Xm其中，X1，X2，Xm为分析过程中所得的文法符号，此时，可视栈顶符号Xm的不同情况，分别做如下的动作： ai ai+1 # X1 X2Xm-1 Xm WVU1、若XmVN，则以Xm及ai组成符号对（Xm, ai）查分析表M，设MXm, ai为一产生式，譬如说XmUVW，此时将Xm从分析栈中退出，并将UVW按反序推入栈中（即用该产生式推导一步），从而得到新的格局但若MXm, ai=“ERROR”，则调用出错处理程序进行处理；2、若Xm=ai#，则表明栈顶符号已与当前正扫视的输入符号得到匹配，此时应将Xm（即ai）从栈中退出，并将输入符号

18、指示器向前推进一个位置；3、若Xm=ai=#，则表明输入串已完全得到匹配，此时即可宣告分析成功而结束分析工作。顺便提及，在上述分析过程的每一步，可视需要附加相应的的语义处理工作。例 考虑文法GE：ETE' E'+TE'| T'*FT'|F(E)|Ii TFT' 相应的分析表如图4-2-2所示（其构造方法，在后面叙述）。现以输入符号串i+i*i为例，列出利用上述算法对此符号串的分析过程如图4-2-3所示。i+*()#EETE'ETE'E'E'+TE'E'E'TTFT'TFT'T

19、'T'T'*FT'T'T'F FiF(E)图4-2-2步骤 分析栈 余留输入串所用产生式 1 # E i+i*i# ETE' 2 # E'T i+i*i# TFT' 3 # E'T'F i+i*i# Fi 4 # E'T'i i+i*i# 5 # E'T'  +i*i# T' 6 # E'  +i*i# E'+TE' 7 # E'T+  +i*i# 8 # E'T  i*i# T'

20、FT' 9 # E'T'F  i*i# Fi 10 # E'T'i i*i# 11 # E'T' *i# T'*FT' 12 # E'T'F* *i# 13 # E'T'F  i# Fi 14 # E'T'i  i# 15 # E'T'  # T' 16 # E'  # E' 17 #  # 成功图4-2-3步骤 分析栈 余留输入串所用产生式 1 # E i

21、+i*i# ETE' 2 # E'T i+i*i# TFT' 3 # E'T'F i+i*i# Fi 4 # E'T'i i+i*i# 5 # E'T'  +i*i# T' 6 # E'  +i*i# E'+TE' 7 # E'T+  +i*i# 8 # E'T  i*i# T'FT' 9 # E'T'F  i*i# Fi 10 # E'T'i i*i# 11 # E&

22、#39;T' *i# T'*FT' 12 # E'T'F* *i# 13 # E'T'F  i# Fi 14 # E'T'i  i# 15 # E'T'  # T' 16 # E'  # E' 17 #  # 成功图4-2-3（二）LL(1)分析表的构造方法 上述LL(1)分析算法对于不同的LL(1)文法都是相同的。也就是说，是说，对不同的LL(1)分析器而言，它们的总控程序都是相同的，不同的仅仅是分析表。再者总控程序十分简

23、单，非常容易实现，所以我们只着重讨论构造分析表的问题。为了构造分析表，我们需要预先定义和构造两个与文法有关的集合FIRST和FOLLOW。假定是文法G的任一符号串，或者说(VTUTN)*，我们定义：FIRST()= a | a, aVT特别是，若 ，则规定FIRST()，换句话说，FIRST()是从可能推导出的所有开头终结符号或可能的。假定S是文法的开始符号，对于G的任何非终结符A，我们定义：FOLLOW(A)=a|SA a，aVT特别是，若SA，则规定#FOLLOW(A)。换句话说，FOLLOW(A)是所有句型中出现在紧接A之后的终结符或#。下面，我们将首先给出构造集合FIRST及FOLLO

24、W的算法，然后再给出构造分析表的算法。（三）1、计算F1RST集根据定义计算由定义 FIRST（）=a| a aVT 、 V*,若，则规定FIRST()对每一文法符号XV计算FIRST(X)。（a）若XVT,则FIRST(X)=x（b）若XVN,且有产生式Xa,aFIRST(X)。（c）若XVN,X,则FIRST(X)。（d）若XVN,Y1,Y2,，Yi都VN,而有产生式XY1Y2Yn。当Y1,Y2,，Yi-1都时，（其中1in），则FIRST(Y1),FIRST(Y2),，FIRST(Yi-1),FIRST(Yi)都包含在FIRST(X)中。（e）当（d）中所有Yi，(i=1,2,n)则FI

25、RST(X)=FIRST(Y1)FIRST(Y2)FIRST(Yn)。反复使用上述(b)(e)步直到每个符号的FIRST集合不再增大为止。求出每个文法符号的FIRST集合后也就不难求出一个符号串的FIRST集合。 (四)2、计算FOLLOW集1）根据定义计算对文法中每一AVN计算FOLLOW(A)(a) 设S为文法中开始符号，把#加入FOLLOW (S)中(这里“#”为句子括号)。(b) 若AB是一个产生式，则把FIRST()的非空元素加入FOLLOW（B）中。如果则把FOLLOW（A）也加入FOLLOW（B）中，因为当有形如：D1A1AB的产生式时,A, B, DVN, , 11,

26、 ,V*,在推导过程中可能出现句型序列如：S1A11B11B1，由定义可知FIRST(1)FOLLOW（A）和FIRST(1)FOLLOW(B)。所以也就有FOLLOW(A)FOLLOW(B)(c) 反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。使如，使用上述两个算法为文法（4.11）GE构造的全部非终结符号所构造的FIRST集及FOLLOW集如下：FIRST（E）=FIRST（T）=FIRST（F）=(，i，FIRST（E）=+，FIRST（T）=*，FOLLOW（E）=FOLLOW（E）=)，#，FOLLOW（T）=FOLLOW（T）=+，)，#，FOLLOW（F）=+，*，

27、），#。3、 构造LL(1)分析表算法图中符号说明如下：“#”句子括号即输入串的括号“S”文法的开始符号“X”存放当前输入符号a的工作单元3、构造分析表的算法对于任一给定的已化简文法G，所谓构造相应的分析表M，其实也就是定义M的各个元素。对此，我们在前面介绍LL（1）分析器的逻辑结构时已初步涉及到了。现在，我们假定G的每一非终结符的FOLLOW集与各候选式的FIRST集均已按上面的算法作出，为构造G的分析表M，则只需对G中的每一产生式Aa，依如下的规则确定M的各个元素：（1）对FIRST（a）中的每一终结符a，置MA, a=“Aa”。（2）若FIRST（a），则对属于FOLLOW（A）的每一符

28、号b（b为终结符或#），置MA，b=“Aa”。（3）把M中所有不能按规则1、2定义的元素均置为ERROR（出错）。例如，按上述算法为文法（4.11）GE所构造的分析表如图4-.12-2所示。一个文法G，若它的分析表M不含多重元素，则称它是一个LL（1）文法。一个LL（1）文法是无二义的，它所定义的语言恰好就是它的分析表M所能识别的全部名句子。可以证明，一个文法G是LL（1）的，当且仅当对于G的每一个非终结符A的任何两条不同规则A=|，下面的条件成立：（1）FIRST（）FIRST（）=，也就是由和推导不出以某个同一终结符a为首的符号串；它们不应该都能推出空字。（2）假若Þ，那么，FI

29、RST（）FOLLOW（A）=。也就是，若Þ，则所能推出的串的首符不应在FOLLOW（A）中。很清楚，文法（4-11GE）是LL（1）文法。应当指出，对已化简的每一个文法G，尽管都可按上述算法为它们构造一个分析表M。然而，在某些情况下，例如G存在左递归或二义性等等，则在相应的分析表中，必然会出现多重定义的元素。请看下面的文法：G=（S，A，B，C，a，b，c，P，S），其中，P由如下产生式组成： Sa b B, ASC,ABABA，A BA b A，CB，Cc因为FIRST（S）=aFIRST（A）=FIRST（B）=,a,bFIRST（C）=a，b，c故由上述算法的规则1可知：MA

30、，a中含有“ASC”及“ABAA”，MA，b中含有“ABAA”。再由A中含有的产生式A，且bFOLLOW（A），故由规则2可知，MA，b中也含有产生式“A”。可见在此文法的分析表中，元素MA，a及MA，b都是多重定义的。出现上述情况的原因，在于G中存在如下的问题。 （1）G中含有左递归变量A和B；（2）对于G中的三个A产生式，有： FIRST（SC）FIRST（BAA）FIRST（BAA）FOLLOW（a）。也就是说，G不是一个LL（1）方法。实际上，可以证明，对于任何文法G，当且仅当它是一个LL（1）文法时，才能的按上述算法为它构造一个无多重定义元素的分析表，而且此分析表能分析并且仅能分析G

31、中的全部句子。然而，尽管如此，对某些非LL（1）文法而言，通过消除左递归和提取左因子，有可能把它们改造为LL（1）文法。例如，对于非LL（1）文法EE+T|T，T（E）|a（E）|a，经消除其中的左递归并对T-产生式提取左因子之后，我们就把它改造为如下的LL（1）文法：ET+T，EE+TE|TaT|（E），T（E）|，但是，并非所有的非LL（1）文法都能改造为LL（1）文法。例如，对于文法SAU|BR，AaAU|b，BaBR|b，Uc，Rd，因对于S-产生式，有FIRST（AU）FIRST（BR），故它不是一个LL（1）文法。为了对S-产生式提取左因子，将其中的非终结符号A，B分别以其各候选式

32、替入，我们得到：SaAUU|bU|aBRR|bR经提取左因子后，得到了与原文法等价的新文法：SaS|bS，SU|RSAUU|BRR，AaAU|b，BaBR|b，Uc，Rd。Uc，Rd。显然，它仍不是一个LL（1）文法。且不难看出，无论把上述手续重复多次，都不能把它改造为LL（1）文法。（二）LL（1）分析表的构造方法上述LL（1）方法对任何文法都是相同的，不同的是分析表，构造两个集合十次ST和FOLLOW。定义2 设G =（VT，VN，S，P）是上下文无关文法，AVNS是开始符号 FOLLOW（A）=|SAUUG VT若有S*A，则规定 #G FOLLOW（A）#作为输入半结束符，#输入半#第

33、十三节 习题1、 构造下面文法的LL（1）分析表。D TLT int | realL id RR , id R | 解答案： LL（1）分析表见表4-3-1分析 虽然这个文法很简单，我们还是从求开始符号集合和后继符号集合开始。 FIRST（D）=FIRST（T）=int, real FOLLOW（D）=FOLLOW（L）=#FIRST（L）=id FOLLOW（T）=idFIRST（R）=，, FOLLOW（R）=#有了上面每个非终结符的FIRST集合，填分析表时要计算一个产生式右部的FIRST（）就不是件难事了。填表时唯一要小心的时，是产生式R右部的一个开始符号，而#在FOLLOW（R）中，

34、所以R填在输入符号#的栏目中。表2.4-3-1 LL（1）分析表非终结符输入符号int realid，#DDTLDTLTTintTrealLLid RRR,id RR 有了上面每个非终结符的FIRST集合，填分析表时要计算一个产生式右部的FIRST（）就不是件难事了。填表时唯一要小心的时，是产生式R右部的一个开始符号，而#在FOLLOW（R）中，所以R填在输入符号#的栏目中。2、 下面文法GS是否为LL（1）文法？说明理由。S  A B | P Q x A  x y B  b cP  d P | Q  a Q | 解答案： 该文法不是LL（1）

35、文法，见下面分析中的说明。分析 只有三个非终结符有两个选择。 1、P的两个右部d P 和 的开始符号肯定不相交。2、Q的两个右部a Q 和 的开始符号肯定不相交。3、对S来说，由于x FIRST(A B)，同时也有x FIRST(P Q x)（因为P和Q都可能为空）。所以该文法不是LL（1）文法。3、 设有以下文法： GS：SaAbDe|d ABSD|e BSAc| cD| DSe| （1）求出该文法的每一个非终结符U的FOLLOW集。（2）该文法是LL（1）文法吗？（3）构造CS的LL（1）分析表。解答案： （1）求文法的每一个非终结符U的FOLLOW集的过程如下：因为： S是识别符号，且有

36、ABSD、BSAc、DSe，所以FOLLOW（S）应包含FIRST(D)FIRST(Ac) FIRST(e) #=a,da,d,c,ee#=a,c,d,e# 又因为ABSD和D，所以FOLLOW中还包含FOLLOW(A)。因为SaAbDe和BSAc,所以FOLLOW（A）=FIRST（bDe）FIRST（c）=b,c综合、得FOLLOW（S）=a,d,c,e,#a,b,c,d,e,#因为ABSD，所以 FOLLOW（B）=FIRST（SD）=a,d 因为SaAbDe | d、ABSD| e和BSAc | cD，所以FOLLOW（D）=FIRST（e）FOLLOW（A）FOLLOW（B）

37、60;=eb,ca,d=a,b,c,d,e（2）GS不是LL（1）文法。因为产生式BSAc|cD| 中 FIRST（SAc）FOLLOW（B）=a,dØ（3）构造GS的LL（1）分析表。按照LL（1）分析表的构造算法构造方法GS的LL（1）分析表如表4-.13-2所示。表4.1-3-2 GS的LL（1）分析表abcde#SaAbDedABSDBSDBSDeBSac/cDSac/DSe/Se/4、 将文法GV改造成为LL(1)的。 GV：VN|NE EV|V+E Ni解答案： 对文法GV提取公共左因子后得到文法： GV：VNAA|EEVBB|+ENi求出文法GV中每一个非终结符号的FI

38、RST集： FIRST(V)=iFIRST(A)=, FIRST(E)=iFIRST(B)=+, FIRST(N)=i求出文法GV中每一个非终结符号的FOLLOW集：FOLLOW(V)=#FIRST(B)FOLLOW(E)=#,+,FOLLOW(A)= FOLLOW(V)=+,#FOLLOW(E)= FIRST()FOLLOW(B)= FIRST()FOLLOW(E)=FOLLOW(B)= FOLLOW(E)= FOLLOW(N)= FIRST(A)FOLLOW(V)=,+,#可以看到，对文法GV的产生式A|E，有FIRST(E)FOLLOW(A)=+,#= Ø对产生式B|+E，有F

39、IRST(+E)FOLLOW(B)=+= Ø而文法的其他产生式都只有一个不为空串（）的右部，所以文法GV是LL(1)文法。5、设有文法GS:SaABbcd|AASd|BSAh|eC|CSf|Cg|DaBD| 求每一个非终结符号的FOLLOW集合。 对每一个非终结符号的产生式选择，构造FIRST集合。 该文法是LL（1）文法吗？解答 首先将文法压缩，得到SaABbcd|AASd|BSAh|eC|CSf|Cg| 求每一个非终结符号的FOLLOW集合：S为开始符号，且有产生式 AASd, BSAh, CSfFOLLOW（S）=#FIRST(d) FIRST(Ah)FIRST(f)=#,d,

40、a,h,fSaABbcd,AASd,BSAhFOLLOW（A）=FIRSTBbcdFIRSTSdFIRSTh=b,a,d,h,eSaABbcdFOLLOW（B）=FIRSTbcd=bBeC,CCgFIRST（C）=FOLLOW（B）FIRST(g)=b, g 对每一个非终结符号的产生式右部选项，构造FIRST集合对 S：FIRST（aABbcd）=aFIRST（ ）=对 A：FIRST（ASd）=a, dFIRST（ ）=对 B：FIRST（SAh）=a, d, hFIRST（eC）=e FIRST（ ）=对C：FIRST（Sf）=a, f FIRST（Cg）=a, f, g FIRST（ ）

41、= 由于存在产生式CSf|Cg|FIRST（Sf）FIRST（Cg）=a, fa, f, gØ所以该文法不是LL（1）文法。65、已知文法：GA：AaAa|（1）该文法是LL（1）文法吗？为什么？（2）若采用LL（1）方法进行语法分析，如何得到该文法的LL（1）分析表？（3）若输入符号串“aaaa”，请给出语法分析过程。解答：（1）因为产生式AaAa| 有空产生式右部，而 FOLLOW(A)=#FIRST(a)=a, #造成 FIRST(A)FOLLOW(A)=A, a, #Ø所以该文法不是LL（1）文法。（2）若采用LL（1）方法进行语法分析，必须修改该文法。因该文法产生

42、偶数（可以为0）个a，所以得到文法GA：AaaA|此时对产生式AaaA|， 有 FOLLOW(A)=#FOLLOW(A)=#，因而FIRST(A)FOLLOW(A)=a, #=Ø所以文法GA是LL（1）文法，按LL（1）分析表构造算法构造该文法的LL（1）分析表如表4.2-3-3所示。表4.2-3-3 文法GA的LL(1)分析表A#AAaaAA（3）若采用LL(1)方法进行语法分析，对符号串“aaaa”的分析过程如表4.-3-43所示。 表4.3-3-4对符号串“aaaa”的分析过程步骤分析栈输入串产生式/动作1#Aa a a a #AaaA2#A a aa a a a #匹配3#A aa a a #匹配4#Aa a #AaaA5#A a aa a #匹配6#A aa#匹配7#A#A8#接受 7、设文法GS： SSbA|aABSbABc 将此文法改写为LL（1）文法。 求文法的每一个非终结符号的FIRST集合和FOLLOW集合。 构造相应的LL（1）分析表。解答 改写文法为LL（1）文法。因为SSbA|aA有左递归，将其改写为SaAbA文法变为GS：SaAbA&#