编译原理：第5章自上而下语法分析

资源描述

《编译原理：第5章自上而下语法分析》由会员分享，可在线阅读，更多相关《编译原理：第5章自上而下语法分析（64页珍藏版）》请在金锄头文库上搜索。

1、第第5章章自上而下语法分析自上而下语法分析语法分析是继词法分析之后编译过程的第2阶段。它的主要任务是对词法分析的输出结果单词序列进行分析，识别合法的语法单位。语法分析最常用的方法有：优先方法、递归下降法、LL方法和LR方法。所谓自上而下分析是指从树的根结开始朝着句子向下进行分析、构造语法树的。本章中,我们通过讨论一个一般的非确定的自上而下分析器来讨论上下无关语言的自上而下分析器的设计。5.1非确定的下推自动机下面所要构造的非确定的自上而下分析器属于一般的下推自动机（PDA）类。所谓一个下推或栈自动机（StackAutomaton）,非形式地说，应包含：一个输入符号串；一个读头，它从左至右移动

2、，每次读进一个输入符号；一个有穷状态自动机，用于控制整个系统的操作；一个后进先出下推栈，下推自动机的非空移动: 5.1.1PDA形式定义形式上说，一个PDA是一个七元组：(Q,H,q0,Z0,F)其中，Q是状态的有穷集，它的每个元素称为一个状态；是有穷的字母表，它的每个元素是一个输入符号；H是有穷的下推栈字符表，它的每个元素称为一个栈符号。q0Q是该PDA的初态；Z0H是下推栈的初始符号；FQ是一个终态集(或接收状态集)；它的每个元素称为终态；(可空)。是一个转换函数，它将三元组(q,a,Z)映象成对偶集（p1,h1）,(p2,h2),，即，(q,a,Z)=（p1,h1）,(p2,h2),.5

3、.1.2PDA的构形和移动PDA的一个构形是一个三元组：(q,w,h)其中，qQ；w*是尚待扫描的输入串，包括读头当前所指的符号；hH*是栈的内容。PDA的一次移动可看作是从一种构形变换成另一种构形的一种方式。反过来，构形又为定义PDA的移动提供了一种更简单的手段。我们称(q,ax,Zh)(p,x,hh)是一次可能的移动，当且仅当(p,h)(q,a,Z)。常用+表示由一次或多次移动组成的序列。用*表示由零次或多次移动组成的序列。注意“零”次移动并不改变当前的构形。例5.1考虑下表定义的两状态PDA，其的两个状态分别是p和Q，(p,a,Z)=（p1,h1）,(p2,h2),输入符号是0和1，栈符

4、号是R，B和G。该PDA识别由符号0和1组成的所有回文(Palindrome)。这个自动机是非确定的，因为在行3和行6包含了可供选择的移动；也因为无输入符号(如在行7)时照样可进行移动，而且此时存在相应的选择。该PDA的开始状态时p，初始栈内容时R。它停止于空栈。用该PDA识别输入串001100，其识别过程如下：（p,001100,R）（p,01100,BR）由行1或（Q,001100,）由行7(阻塞)（p,01100,BR）（p,1100,BBR）由行3a或（Q,1100,R）由行3b（Q,1100,R）（Q,1100,）由行10(阻塞)（p,1100,BBR）（p,100,GBBR）由行5

5、（p,100,GBBR）（p,00,GGBBR）由行6a或（Q,00,BBR）由行6b（p,00,GGBBR）（p,0,BGGBBR）由行4（p,0,BGGBBR）（p,BBGGBBR）由行3a(阻塞)或（Q,GGBBR）由行3b(阻塞)（Q,00,BBR）（Q,0,BR）由行8（Q,0,BR）（Q,R）由行8（Q,R）（Q,）由行10(接收)5.1.3上下文无关语言与PDA联系PDA和上下文无关语言的一个重要定理是：定理5.1对每一个上下文无关语言L，存在一个恰好识别L的非确定的PDAM，反之亦然。这个定理在编译系统中的实际重要性在于：现有的大多数高级程序设计语言都可用上下文无关文法描述。因

6、此定理5.1隐含了：识别这个语言的机械识别器必是PDA。定理5.1包含两方面含义：给定一个上下文无关语言，存在一个识别它的PDAM；反过来，给定一个PDAM，可以根据它构造出一个等价的上下文无关文法。前者对编译程序的构造很有吸引力，但后者则不然。算法5.1从CFG到NDPDA给定CFGG=（N，P，S）可以构造一个相应的非确定的PDAM：M=(Q,H,q0,Z0,F)它只有一个状态q和下面的转换规则：对P中每一个形如Aw的产生式，(q,A)包含(q,w);对每个a，(p,a,a)包含(q,)且Q=q=H=Nq0=qZ0=SF为终态集(可空)。这个PDA停止于空栈。例5.2考虑文法S0S1|c该

7、文法描述语言0*c1*,其中0的个数和1的个数相等。转换规则是：1.(q,0,0)=(q,)2.(q,1,1)=(q,)3.(q,c,c)=(q,)4.(q,S)=(q,0S1),(q,c)(其中可与任何合法输入符号匹配)给定输入串00c11，所构造的PDA用下面的移动序列来接收它(注意，我们可从构形中省掉状态，因为它总是相同的)：(q,00c11,S)4a(q,00c11,0S1)1(q,0c11,S1)4a(q,0c11,0S11)1(q,c11,S11)4b(q,c11,c11)3(q,11,11)2(q,1,1)2(q,)(接收)输入串，栈和句型由算法5.1构造的非确定的PDA的一个有

8、趣特性是由下面的定理表示出来的。定理5.2令(q,y,h)是某个文法G相关的NDPDA的任意构形，其中输入串是xy，如果(q,xy,S)*(q,y,h)那么xh是G的一个最左句型，换言之，S=*xh(S是G的开始符号)。上述定理反过来也成立：给定G中的任何句型xh，如果x是一个终结符串，而且h中至多最左符号是终结符，那么，(q,y,h)是该NDPDA的一个构形，而且(q,xy,S)*(q,y,h)5.2消除左递归方法5.2.1文法的左递归性文法的左递归性属文法递归性的一种，在一文法中，所有形如AxAyx,y(N)*，AN称为递归产生式(或自嵌入产生式)。若其中x=，则有AAy称之为直接左递归产

9、生式。若其中y=，则有AxA称之为直接右递归产生式。若一文法中至少含有一条递归产生式，或在用该文法推导符号串的过程中，存在AA或AA或AA形式的推导，则称该文法是(直接)递归的。为了避免无限循环，自上而下分析法的文法不应含有左递归。有则消除。文法的左递归性文法的左递归性直接左递归：UUx|y间接左递归：UUx例：G22A：ABBX|BAXXa|Xb|a|b5.2.2用扩展的BNF表示法消除左递归在前面，文法的产生式都是采用巴科斯范式（BNF）描述的，它使得文法更严谨、简洁和清晰。为了消除文法的左递归，需对巴科斯范式进行扩展，增加以下元符号：花括号：表示符号串x出现零次或多次。：n表示符号串x能

11、(x|y|z)v也就是说，使用上述规则，可把产生式改写成相对于某个非终结符而言，至多只含一个直接左递归的右部；然后，利用上述规则消除这个直接左递归。5.2.3直接改写法设产生式UUxy此产生式称为直接左递归形式。其中，x和y是两个符号串，y的首字符不是U。产生式为直接左递归形式，可直接改写为一个等价的非直接左递归形式UyUUxU其中U是新引进的非终结符号。显然，这种形式与原形式是等价的，即从A推出的符号串是相同的。直接左递归更一般的形式UUx1Ux2Uxmy1y2yn其中，xi(i=1,2,m),yi(i=1,2,n)的头字符都不是U。Uy1Uy2UynUUx1Ux2UxmU5.2.4消除所有

12、左递归的算法若一个文法不含形如AA的推导，也不含有以为右部的产生式，那么，执行下面的算法将保证消除该文法中的所有左递归:将文法G的所有非终结符整理成某一顺序U1，U2，Un。fori:=1tondobeginforj:=1toi1dobegin把产生式UiUj替换成Ui12m(其中Uj12m1是该文法中关于Uj的所有产生式)end;消除Ui产生式中的直接左递归end;化简改写之后的文法，删除多余产生式。5.3LL(k)文法LL(k)文法是上下文无关文法的一个真子集。同时，LL(k)文法也是允许采用确定的从左至右扫描(输入串)和自上而下分析技术的最大一类文法。LL系指：自左至右扫描(输入串)，自

13、上而下进行最左推导。给定一文法，判断它是否是一个LL(k)文法并不是很容易的事。我们将给出一个判断条件。根据这个条件就能推断一个给定的文法是否是LL(k)文法。此外，由于分析表是分析器的核心，因此，我们将给出构造LL(k)分析器的分析表的方法。5.3.1LL(1)文法的判断条件按照前面所述方法改造，消除左递归后的文法不一定就是一个LL(1)文法，还必须借助于某种判断条件才能确定。为此，我们将引进三个集合：FIRST,FOLLOW和SELECT。先定义集合FIRST和FOLLOW。设是文法G的一个符号串，(VNVT)*，定义FIRST()=aa,aVT,(VNVT)*特别，若有，则FIRST（）

14、。即，FIRST()是从可推导出的所有首终结符或可能的。设S是文法的识别符号，UVN，定义FOLLOW(U)=bSxUby，bVT，x,y(VNVT)*若SxU，则规定“$”FOLLOW(U)。即，FOLLOW(U)是文法的所有句型中紧接在U之后出现的终结符或$($不是文法符号，而是一个特定的结束符)。再来看看SELECT集合。假定U是文法G的任一产生式，其中UVN，(VNVT)*，集合SELECT(U)的构造如下：利用上面的三个集合可建立LL(1)文法的判断条件如下：令G是一个CFG，当且仅当对于G中每个具有相同左部的产生式(即一个非终结符的所有产生式)U1|1|n都有SELECT(Ui)S

15、ELECT(Uj)=(ij,i,j=1,2,n)，则文法G是一个LL(1)文法。5.3.2集合FIRST、FOLLOW与SELECT的构造1.设X(VNVT)，FIRST(X)的构造若XVT，则FIRST(X)=X；若XVN，它的产生式为Xa，aVT，则aFIRST(X)；若它有产生式X，则FIRST(X)；如果它有产生式XY，YVN，则FIRST(Y)FIRST(X)；如果它有产生式XY1Y2Yk（其中，Y1，Y2，Yi-1都是非终结符，且Y1Y2Yi1），则FIRST(Yi)FIRST(X)；如果Y1Y2Yk，则FIRST(X)。2.设(VNVT)*，=X1X2Xn，FIRST()的构造若

16、=，显然FIRST()=；若，则FIRST(X1)FIRST()；若X1X2Xi1，则FIRST(Xi)FIRST()；若X1X2Xn，则FIRST()。3.设UVN，FOLLOW(U)的构造若U是文法的开始(识别)符号，则$FOLLOW(U)；若有产生式AxUy，则FIRST(y)FOLLOW(U)；若有产生式AxU，或AxUy，y，则FOLLOW(A)FOLLOW(U)。例5.9设文法G32S：SAABAAiBABCBB+CBC)A*|(S是识别符号，且未出现在任何产生式右部，FOLLOW(S)=$。SA, $FOLLOW(A),C)A*,*FOLLOW(A),FOLLOW(A)=*,$;

17、ABA,FOLLOW(A)=FOLLOW(A)=*,$,AiBA|,FIRST(A)=i,=iFOLLOW(B),FOLLOW(A)=*,$FOLLOW(B),FOLLOW(B)=i,*,$;BCB,FOLLOW(B)=FOLLOW(B)=i,*,$,SELECT(AiBA)SELECT(A)=FIRST(iBA)(FIRST()FOLLOW(A)=i*,$,=,SELECT(B+CB)SELECT(B)=FIRST(+CB)(FIRST()FOLLOW(B)=+i,*,$,=,SELECT(C)A*)SELECT(C()=FIRST()A*)FIRST()=(=。此文法G是一个LL(1)文法

18、。需要注意的是，对于LL(1)文法，利用SELECT集，我们还可以得到十分有助于句子分析的结果：在分析过程中的某一步，当非终结符U正处于栈顶时，若aSELECT(U)是当前的输入符号，则可立即选用产生式U；若aSELECT(U)是当前的输入符号，则可选用产生式U。由于LL(1)文法的任何一对具有相同左部的产生式的SELECT集是不相交的，因此，根据现行的非终结符(已在栈顶)和当前的输入符号就能唯一地确定分析过程中的下一步动作，也就是说，我们完全可以为LL(1)文法构造一个确定的分析器。5.4确定的LL(1)分析器的构造逻辑上说，一个LL(1)分析器由两大部分组成：一个总控算法和一张分析表。LL

19、(1)分析器的总控算法基本上是一样的，只是分析表各不相同。由于总控程序比较容易实现，因此，我们常常把构造分析器的任务只看作是构造分析表。分析表是一个MU,a形式的矩阵，其中U为非终结符，a为终结符或$。矩阵元素MU,a中可能存放关于U的产生式，表示当U面临输入符号a时所应选用的产生式；MU,a中也可能存放一个ERROR，表示此时输入串中存在语法错误。5.4.1构造分析表M的算法对于构造分析表M的算法，我们可以有两种形式的描述，先来看看以FIRST和FOLLOW集合定义的算法：对文法的每一条产生式U，若aFIRST()，则MU,a=U；若FIRST()，则MU,b=U，其中，bFOLLOW(U)

20、；分析表M的其它元素均为出错标志error，通常用空白表示。如果用SELECT集合来定义算法，则有以下步骤：对文法G的每个产生式U，计算SELECT（U）。若SELECT（U）=a,a,则置MU,a为产生式U；若SELECT（U）=a1,a2,an,a1,a2,an都是终结符号或$或，则置MU,a1=MU,a2=MU,an产生式为U。对所有尚未定义的MU,a,置上ERROR（用空白表示）。例5.11对于例5.9中的文法GS，构造分析表。对于产生式SA，FIRST(A)=(,)，MS,(=SA，MS,)=SA。对于产生式ABA，FIRST(B)=(,)，MA,C=ABA，MA,)=ABA。对于产

21、生式AiBA,FIRST(iBA)=i,MA,i=AiBA。对于产生式A，FOLLOW(A)=*,$，MA,*=A,MA,$=A。对于产生式BCB,FIRST(C)=(,),MB,C=BCB，MB,)=BCB。对于产生式B+CB，FIRST(+CB)=+，MB,+=B+CB。对于产生式B，FOLLOW(B)=i,*,$,MB,i=B，MB,*=B,MB,$=B。对于产生式C)A*，FIRST()A*)=)，MC,)=C)A*。对于产生式C(，FIRST()=(，MC,(=C(。分析表M 5.4.2LL(1)分析器的总控算法LL(1)分析器就是带有LL(1)分析表的一个PDA，也称预测分析程序。

22、下面给出LL(1)分析器的总控算法：最初，分析器把文法的开始符号S置于栈顶(假定输入串以$结束)；若栈顶为一终结符，而且与当前输入符号匹配，则读头前进一位置(扫描下一输入符号)，并逐出栈顶符号。否则报错。(匹配动作)若栈顶符号是一非终结符U，且当前的输入符号为a，则查看分析表M，若MU,a置有关于U的产生式Uw，则先从栈中逐出U再把w下推进栈；若w=，则不推进任何信息进栈，仅逐出栈顶符号；若MU,a为空白，则调用出错处理子程序。(应用动作)重复步骤、，直至栈变为空。该分析器停止于空栈。(接收)例5.14按照LL（1）分析器总控算法，对文法G32S的符号串(i(进行分析，分析过程见下表。分析结果

23、表明该符号是文法G32S的一个句子。5.5LL(k)文法的几个结论可以证明：LL(k)文法是不含左递归的；LL(k)文法是无二义性的；一文法G是LL(1)，当且仅当对于G的每一非终结符U的任何两个不同产生式A|，下面的条件成立：FIRST()FIRST()=;,中至多只有一个能推出空串；若，则FIRST()FOLLOW(A)=。5.6递归下降分析程序及其设计若一文法G满足下述两个条件：G中不含有直接左递归；G中的每个非终结符的所有候选式的FIRST集都是两两不相交的。那么，我们就能为G中的每个非终结符编写一个相应的递归过程，把该文法中的所有这样一些递归过程组合起来就有可能构成一个不带回溯的自上

24、而下分析程序。这种分析程序称为递归下降分析程序(Recursive-descentParser)，它是一种确定的自上而下分析方法,也是编译程序中使用得最为广泛的一类分析程序。可以证明，一个递归下降分析程序能正确工作的必要条件是它的源文法是LL(1)的。下面，我们形式化描述递归子程序的设计方法。在定义子程序时用到一个全局变量ch，存放输入符号串的当前符号；还用到一个函数READ(ch)，从ch中读输入符号串的下一个符号。设aVT，P(a)代表语句ifch=athenREAD(ch)elseerror设=x1x2xn，xi(VNVT)(i=1,2,n)，P()代表复合语句beginP(x1);P(

25、x2);P(xn)end设UVN，产生式U12m，定义P(U)：read(ch);ifchFIRST(1)thenP(1)elseifchFIRST(2)thenP(2)elseifchFIRST(m)thenP(m)elseerror如果非终结符U有空产生式U，则改写P(U)为read(ch);ifchFIRST(1)thenP(1)elseifchFIRST(2)thenP(2)elseifchFIRST(m)thenP(m)elseifchFOLLOW(U)thenreturnelseerror5.6.1框图设计例5.15设文法GS：S(A)aAbAeAdSAAdA此文法的递归下降程序框

26、图设计如下所示。图中省略了递归入口RI和递归出口RO部分，如果采用低级语言编程，只需要在程序框图的开头和末尾加上这两个部分。5.6.2程序设计例5.16例5.15中的文法GS：子程序P(S)：READ(ch)ifch=(thenbeginREAD(ch);P(A);ifch=)thengotoLelseerrorendelseifchathenerrorelsebeginREAD(ch);P(A);ifch=bthengotoLelseerrorendL:READ(ch);return子程序P(A)：ifch=ethenbeginREAD(ch);gotoLendifchdthenerrorP

27、(S);L:P(A);return子程序P（A）：L:ifch=dthenbeginread(ch);gotoLendelseifch=bthengotoLelseifch=)thengotoLelseerrorL:return5.7带回溯的自上而下分析法不带回溯的自上而下分析法，并不适用于所有的上下文无关文法，必须对文法加以限制；而带回溯的自上而下分析法，对上下文无关文法具有通用性，几乎没有限制，但速度慢是这种分析法的致命弱点。5.7.1文法在内存中的存放形式带回溯的自上而下分析法，实际上就是穷举所有可能的推导，看是否能推导出待检查的符号串。在穷举所有可能的推导过程中，其唯一的依据是文法的产

28、生式。因此，一个文法若使用带回溯的自上而下分析法，则它的所有产生式都必须先保存在内存中，具体地说，是存放在一个一维数组中。在这个一维数组中，存放每一条产生式的左部和右部，并且在每一个产生式右部的尾符号之后放置一个符号“”，作为产生式右部的结束符；在一个非终结符的最后一个产生式右部的尾符号之后放置一个符号“$”，作为这个非终结符的所有产生式右部的结束符。5.7.2其它信息的存放在带回溯的自上而下分析法中，需设置一个S栈来保存当前目标以及它的“双亲”、“孩子”和“兄长”等信息，一旦试探失败，则可进行回溯。S栈的元素是一个五元组（GOAL，i，FATHER，SON，BROTHER）其中，GOAL是目

29、标，i是目标的产生式右部的符号在数组GRAMMAR中的位置，FATHER、SON和BROTHER分别是目标的双亲、第一个孩子和兄长。5.7.3带回溯的自上而下分析算法算法包括六个部分：INIT（初始化）、TEST（检查）、LOOK（查看）、SUCC（成功）、FAIL（失败）和ATRY（再试）。INIT：P:=1；P指示当前结点k:=1；k是栈S的栈顶指针j:=1；j是输入符号串INPUT的下标Sk:=(Z,0,0,0)；Z是文法的识别符，作为当前目标，压入S栈中gotoTEST；控制转到TEST部分TEST：ifGOALinVTthenifGOAL=INPUTjthenbeginj:=j+1；

30、gotoSUCC读下一个输入符号，转SUCC部分endelsegotoFAIL；i:=GOAL的产生式右部第一个选择的首符号在数组GRAMMAR中的位置；gotoLOOK；若GOAL是非终结符，则找到它的产生式右部第一选择的首符号的位置，且转LOOK部分LOOK：ifGRAMMARi=then若是产生式右部结束符ifFATHER0thengotoSUCC且有双亲，则转SUCC部分elseSTOP若无双亲，即根结点，则分析成功，待查符号串是句子ifGRAMMARi=$then若是一个非终结符的所有产生式的右部结束符ifFATHER0thengotoFAIL且有双亲，则转FAIL部分elseSTO

31、Pk:=k+1；S栈指针加1若GRAMMARi既不是“”，也不是“$”Sk:=（GRAMMARi,O,P,O,SON）；GRAMMARi作为当前目标进栈，P指示的原目标是当前目标的双亲，原目标的第一个孩子是当前目标的兄长SON:=k；当前目标是原目标的孩子P:=k；P指示当前目标gotoTEST；SUCC：P:=FATHER；向双亲报告匹配成功，双亲作为当前目标i:=i+1；gotoLOOK；FAIL：P:=FATHER；向双亲报告匹配失败，双亲作为当前目标SON:=SSON.BRO;将原目标的兄长作为当前目标的孩子k:=k1；与原目标脱离父子关系gotoATRY；再试探ATRY：ifSON=

32、0then若没有兄长beginwhileGRAMMARi1do则跳过当前产生式右部i:=i+1;i:=i+1;gotoLOOK取产生式右部另一个选择再查看end;i:=i1；若有兄长P:=SON；兄长作为当前目标ifGOALinVNthengotoATRY;j:=j1；gotoFAIL;用扩展的用扩展的BNF表示法消除左递归表示法消除左递归零次或多次，mn次零次或一次，可选项。()描述提取公因子。例：G标识符：|0|1|2|3|4|5|6|7|8|9a|b|c|e|f|g|h|i|j|k|m|n|o|p|q|r|s|t|u|v|w|x|y|z显然标识符产生式有左递归，可改写为|直接改写法直接改

33、写法UUx|y=UyU,UxU|UUx1|Ux2|Uxm|y1|y2yn=UU(x1|x2|xm)|(y1|y2yn)=U(y1|y2yn)UU(x1|x2|xm)U|直接改写法举例直接改写法举例例：G22A：ABBX|BAXXa|Xb|a|b改写为：G22A：ABBXBBAB|XaX|bXXaX|bX|消除左递归算法消除左递归算法将VN符号整理成序Uk，k=1,nfori:=1tondobeginj:=i+1tondo替换UiUj中的Uj消除Ui产生式中的直接左递归end化简，删除多余产生式消消除除左左递递归归算算法法举举例例例5.4设文法ABcdBCe|fCAb|c变换：BCe|f=BAb

35、构造FIRST()的构造VT，FIRST()=VN，a，aFIRST()；，FIRST()VN，XY，FIRST(X)-FIRST()，若X，则FIRST(Y)-FIRST()集合集合FIRST、FOLLOW的构造的构造FOLLOW（U）的构造U是开始符号，则#FOLLOW(U)AxUy，则FIRST(y)-FOLLOW（U）AxUy，y,(包括AxU) 则FOLLOW(A) FOLLOW(U)构造构造FIRST、FOLLOW举例举例例G27SSAABAAiBA|BCBB+CB|C)A*|(FIRSTFOLLOWS),(#A),(#,*Ai,#,*B),(#,*,iB+,#,*,iC),(#,

36、*,i,+构造分析表的算法构造分析表的算法MU,a=U，aFIRST()；MU,b=U，bFOLLOW（U）；MU,b=Error，空白处；例G27SSAABAAiBA|BCBB+CB|C)A*|(FIRSTFOLLOWS),(#A),(#,*Ai,#,*B),(#,*,iB+,#,*,iC),(#,*,i,+VNVTi+*()#SSASAAABAABAAAiBAAABBCBBCBBBB+CBBBCC(C)A*符号串(i(分析过程VNVTi+*()#SSASAAABAABAAAiBAAABBCBBCBBBB+CBBBCC(C)A*符号栈输入串符号栈输入串1#S(i(#8#ABii(#2#A(i

37、(#9#AB(#3#AB(i(#10#ABC(#4#ABC(i(#11#AB(#5#AB(i(#12#AB#6#ABi(#13#A#7#Ai(#14#5. .4 递归下降分析程序及其设计递归下降分析程序及其设计给每个非终结符设计一个相应的子程序。intfS()j=1;returnfA();intfA()iffB()returnfA();elsereturnError;intfA()if(chj=i)j=j+1;iffB()returnfA();elsereturnError;elsereturnOK;intfC()if(chj=)j=j+1;iffA()if(chj=*);j=j+1;retu

39、(包括AxU) 则FOLLOW(A) FOLLOW(U)例：已知文法GS：SeT|RTTDR|RdR|Da|bdLL(1)分析表abed#SSRTSRTSeTSRTSRTTTDR TDRTRRRRdRRDDaDbdFIRSTFOLLOWSa,b,e,d,#Ta,b,#Rd,a,b,#Da,bd,#已知文法GA：AAB|BBBC|CCD|DD（A）|i消除左递归，计算每个非终结符的FIRST、FOLLOW集。构造GS的LL(1)分析表。解：ABAABA|BCBBCB|CD|DD（A）|iFIRSTFOLLOWA,(,i),#A,),#B,(,i,),#B,),#C,(,i,),#D(,i,),#()i#AABAABAABAAABAAABBCBBCBBCBBBCBBBBCCDCDCDDD（A） DiABAABA|BCBBCB|CD|DD（A）|iFIRSTFOLLOWA,(,i),#A,),#B,(,i,),#B,),#C,(,i,),#D(,i,),#GS:SaAbDe|dABSD|eBSAc|cD|DSe|FIRSTFOLLOWSa,da,b,d,c,e,#Aa,d,c,eb,cBa,c,d,a,dDa,d,a,b,c,d,eabcde#SaAbDedABSDBSDBSDeBSac/cDSac/DSe/Se/第5章作业5.5

展开阅读全文

编译原理：第5章 自上而下语法分析

最新文档

编译原理：第5章自上而下语法分析