第三章语法分析－金锄头文库

资源描述

《第三章语法分析》由会员分享，可在线阅读，更多相关《第三章语法分析（182页珍藏版）》请在金锄头文库上搜索。

1、第三章第三章语法分析语法分析第三章第三章语法分析语法分析 3.1 完成下列选择题：(1) 文法G：SxSx|y所识别的语言是。 a. xyx b. (xyx)* c. xnyxn(n0) d. x*yx*(2) 如果文法G是无二义的，则它的任何句子。 a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同第三章第三章语法分析语法分析 (3) 采用自上而下分析，必须。a. 消除左递归 b. 消除右递归c. 消除回溯 d. 提取公共左因子(4) 设a、b、c是文法

2、的终结符，且满足优先关系ab和bc，则。a. 必有ac b. 必有cac. 必有ba d. ac都不一定成立第三章第三章语法分析语法分析 (5) 在规范归约中，用来刻画可归约串。 a. 直接短语 b. 句柄 c. 最左素短语 d. 素短语(6) 若a为终结符，则Aa为项目。 a. 归约 b. 移进 c. 接受 d. 待约(7) 若项目集Ik含有A ，则在状态k时，仅当面临的输入符号aFOLLOW(A)时，才采取“A ”动作的一定是。 a. LALR文法 b. LR(0)文法 c. LR(1)文法 d. SLR(1)文法第三章第三章语法分析语法分析 (8) 同心集合并有可能产生新的

3、冲突。a. 归约 b. “移进”/“移进” c.“移进”/“归约” d. “归约”/“归约”【解答】 (1) c (2) a (3) c (4) d (5) b (6) b (7) d (8) d3.2 令文法GN为 GN: ND|ND D0|1|2|3|4|5|6|7|8|9(1) GN的语言L(GN)是什么? (2) 给出句子0127、34和568的最左推导和最右推导。第三章第三章语法分析语法分析【解答】 (1) GN的语言L(GN)是非负整数。(2) 最左推导：NNDNDDNDDDDDDD0DDD01DD012D0127 NNDDD3D34 NNDNDDDDD5DD56D568最右推

4、导：NNDN7ND7N27ND27N127D1270127 NNDN4D434 NNDN8ND8N68D68568第三章第三章语法分析语法分析 3.3 已知文法GS为SaSb|Sb|b，试证明文法GS为二义文法。【解答】由文法GS：SaSb|Sb|b，对句子aabbbb可对应如图3-1所示的两棵语法树。第三章第三章语法分析语法分析图3-1句子aabbbb对应的两棵不同语法树第三章第三章语法分析语法分析因此，文法GS为二义文法(对句子abbb也可画出两棵不同语法树)。3.4 已知文法GS为SSaS|，试证明文法GS为二义文法。【解答】由文法GS：SSaS|，句子aa的语法树如图3-2

5、所示。第三章第三章语法分析语法分析图3-2句子aa对应的两棵不同的语法树第三章第三章语法分析语法分析由图3-2可知，文法GS为二义文法。3.5 按指定类型，给出语言的文法。 (1) L=aibj|ji0的上下文无关文法；(2) 字母表=a,b上的同时只有奇数个a和奇数个b的所有串的集合的正规文法；(3) 由相同个数a和b组成句子的无二义文法。【解答】 (1) 由L=aibj|ji0知，所求该语言对应的上下文无关文法首先应有SaSb型产生式，以保证b的个数不少于a的个数；其次，还需有SSb或Sb型的产生式，用以保证b的个数多于a的个数。因此，所求上下文无关文法GS为GS：SaSb|Sb|

8、应句型aAaBcbbdcc和aAcbBdcc的语法树如图3-4的(a)、(b)所示。第三章第三章语法分析语法分析图3-4 习题3.6的语法树(a)aAaBcbbdcc;(b)aAcbBdcc第三章第三章语法分析语法分析对树(a)，直接短语有3个：AaB、b和c，而AaB为最左直接短语(即为句柄)。对树(b)，直接短语有两个：Bd和c，而Bd为最左直接短语。能否不画出语法树，而直接由定义(即在句型中)寻找满足某个产生式的候选式这样一个最左子串(即句柄)呢？例如，对句型aAaBcbbdcc，我们可以由左至右扫描找到第一个子串AaB，它恰好是满足AAaB右部的子串；与树(a)对照，AaB的确

9、是该句型的句柄。是否这一方法始终正确呢？我们继续检查句型aAcbBdcc，由左至右找到第一个子串c，这是满足AC右部的子串，但由树(b)可知，c不是该句型的句柄。由此可知，画出对应句型的语法树然后寻找最左直接短语是确定句柄的好方法。第三章第三章语法分析语法分析 (2) 句子acabcbbdcc的最左推导如下：SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcA acabcbbdcAacabcbbdcc3.7 对于文法GS: S(L)|aS|aLL,S|S(1) 画出句型(S,(a)的语法树；(2) 写出上述句型的所有短语、直接短语、句柄、素短语和最左素短语。【

10、解答】 (1) 句型(S, (a)的语法树如图3-5所示。第三章第三章语法分析语法分析图3-5句型(S,(a)的语法树第三章第三章语法分析语法分析 (2) 由图3-5可知：短语：S、a、(a)、S,(a)、(S,(a)；直接短语：a、S；句柄：S；素短语：素短语可由图3-5中相邻终结符之间的优先关系求得，即： # (， (a)#因此，素短语为a。第三章第三章语法分析语法分析 3.8 下述文法描述了C语言整数变量的声明语句：GD: DTLTint|long|shortLid|L,id(1) 改造上述文法，使其接受相同的输入序列，但文法是右递归的；(2) 分别用上述文法GD和改造后的文法G

12、T) | aSS+S | TSTT,ST| 改造后的文法已经是LL(1)文法，不带回溯的递归子程序如下：void match (token t) if ( lookahead=t)lookahead=nexttoken; else error ( );第三章第三章语法分析语法分析 void S ( ) if ( lookahead=a)match (a);else if ( lookahead=()match ();T ( );第三章第三章语法分析语法分析 void S( ) if ( lookahead=+)match (+);S ( );第三章第三章语法分析语法分析 void T (

13、 ) S ( );T( );void T ( ) if ( lookahead=, )match (, );S ( );T ( );第三章第三章语法分析语法分析 3.10 已知文法GA: AaABl|aBBb|d(1) 试给出与GA等价的LL(1)文法GA；(2) 构造GA的LL(1)分析表；(3) 给出输入串aadl#的分析过程。【解答】 (1) 文法GA存在左递归和回溯，故其不是LL(1)文法。要将GA改造为LL(1)文法，首先要消除文法的左递归，即将形如PP | 的产生式改造为PPPP| 第三章第三章语法分析语法分析来消除左递归。由此，将产生式BBb|d改造为BdBBbB| 其次，

14、应通过提取公共左因子的方法来消除GA中的回溯，即将产生式AaABl|a改造为AaAAABl | 最后得到改造后的文法为GA：AaAAABl | BdBBbB| 第三章第三章语法分析语法分析求得： FIRST(A)=a FIRST(A)=a, FIRST(B)=d FIRST(B)=b, 对文法开始符号A，有FOLLOW(A)=#。由 AABl得 FIRST(B) FOLLOW(A)，即FOLLOW(A)=#,d；由 AABl得 FIRST(l) FOLLOW(B)，即FOLLOW(B)=l；由AaA得FOLLOW(A) FOLLOW(A)，即FOLLOW(A)=#,d；第三章第三章

15、语法分析语法分析由 BdB得 FOLLOW(B) FOLLOW(B)，即FOLLOW(B)=l。对AABl来说，FIRST(A)FOLLOW(A)=a#,d=，所以文法GA为所求等价的LL(1)文法。第三章第三章语法分析语法分析 (2) 构造预测分析表的方法如下：对文法GA的每个产生式A执行、步。对每个终结符aFIRST(A)，把A加入到MA,a中，其中为含有首字符a的候选式或为唯一的候选式。若FIRST(A)，则对任何属于FOLLOW(A)的终结符b，将A加入到MA,b中。把所有无定义的MA,a标记上“出错”。由此得到GA的预测分析表，见表3-1。第三章第三章语法分析语法分析

16、表3-1 预测分析表第三章第三章语法分析语法分析 (3)输入串aadl的分析过程见表3-2。第三章第三章语法分析语法分析表3-2 输入串aadl的分析过程第三章第三章语法分析语法分析 3.11 将下述文法改造为LL(1)文法： GV: VN | NEEV | V+ENi【解答】 LL(1)文法的基本条件是不含左递归和回溯(公共左因子)，而文法GV中含有回溯，所以先消除回溯，得到文法GV： G V：VNVV | EEVEE | +ENi第三章第三章语法分析语法分析一个LL(1)文法的充要条件是：对每一个终结符A的任何两个不同产生式A|有下面的条件成立：(1) FIRST()FIRS

17、T()=； (2) 假若，则有FIRST()FOLLOW(A)= 。即求出GV的FIRSTVT和LASTVT集如下：FIRST(N)=FIRST(V)=FIRST(E)=iFIRST(V)=, FIRST(E)=+, FOLLOW(V)=#第三章第三章语法分析语法分析由 VE得 FIRST() FOLLOW(E)，即 FOLLOW(E)= ；由 VNV得 FIRST(V) FOLLOW(N)，即 FOLLOW(N)= ；由EVE得FIRST(E) FOLLOW(V)，即FOLLOW(V)=#,+；由 VNV得 FOLLOW(V) FOLLOW(V)，即FOLLOW(V)=#,+；由V

19、此文法是否为算符优先文法；(2) 构造文法G的优先函数。第三章第三章语法分析语法分析【解答】 FIRSTVT集构造方法：由Pa或PQa，则aFIRSTVT(P)。若aFIRSTVT(Q)，且PQ，则aFIRSTVT(P)，也即FIRSTVT(Q)FIRSTVT(P)。由得：由EE+得FIRSTVT(E)=+；由TT*得FIRSTVT(T)=*；由Pi得FIRSTVT(P)=i。由得：由 TP得 FIRSTVT(P)FIRSTVT(T)，即 FIRSTVT(T)=*，i；由 ET得 FIRSTVT(T)FIRSTVT(E)，即 FIRSTVT(T)=+，*，i。第三章第三

20、章语法分析语法分析 LASTVT集构造方法：由Pa或PaQ, 则aLASTVT(P)。若aLASTVT(Q)，且PQ，则aLASTVT(P)，也即LASTVT(Q)LASTVT(P)。由得：E+T，得LASTVT(E)=+； T*P，得LASTVT(T)=*； Pi，得LASTVT(P)=i。由得：由 TP得 LASTVT(P)LASTVT(T)，即 LASTVT(T)=*，i；由 ET得 LASTVT(T)LASTVT(E)，即 LASTVT(E)=+，*，i。第三章第三章语法分析语法分析优先关系表构造方法：对Pab或PaQb，有ab；对PaR而bFIRSTVT(R

21、)，有ab；对PRb而aLASTVT(R)，有ab。解之无。由得：E+T，即+FIRSTVT(T)，有+*，+i； T*P，即*FIRSTVT(P)，有*i。由得：EE+，即LASTVT(E)+，有+，*+，i+； TT*，即LASTVT(T)*，有*，i*。第三章第三章语法分析语法分析得到优先关系表见表3-3。由于该文法的任何产生式的右部都不含两个相继并列的非终结符，故属算符文法，且该文法中的任何终结符对(见优先关系表)至多满足、和三种关系之一，因而是算符优先文法。第三章第三章语法分析语法分析表3-3 习题3.12的优先关系表第三章第三章语法分析语法分析用关系图构造优先函数的方

22、法是：对所有终结符a用有下脚标的fa、ga为结点名画出全部终结符所对应的结点。若存在优先关系ab或ab，则画一条从fa到ga的有向弧；若ab或ab，则画一条从g b到f a的有向弧。最后，对每个结点都赋一个数，此数等于从该结点出发所能到达的结点(包括出发结点)的个数，赋给fa的数作为f(a)，赋给gb的数作为g(b)。用关系图法构造本题的优先函数，如图3-7所示。得到优先函数见表3-4。第三章第三章语法分析语法分析图3-7习题3.12关系图构造第三章第三章语法分析语法分析表3-4 习题3.12的优先函数表第三章第三章语法分析语法分析该优先函数表经检查与优先关系表没有矛盾，故为所求优

23、先函数。也可由定义直接构造优先函数，其方法是：对每个终结符a，令f(a)=g(a)=1；如果ab，而f(a)g(b)，则令f(a)=g(b)+1；如果ab，而f(a)g(b)，则令g(b)=f(a)+1；如果ab，而f(a)g(b)，则令minf(a),g(b)=maxf(a),g(b)。重复上述过程，直到每个终结符的函数值不再变化为止。如果有一个函数值大于2n(n为终结符个数)，则不存在优先函数。优先函数的计算过程如表3-5所示。第三章第三章语法分析语法分析表3-5 优先函数的计算过程表第三章第三章语法分析语法分析计算最终收敛，并且计算得出的优先函数与关系图构造得出的优先函数是一样的

25、TVT(A)=d，又由 AS得LASTVT(S) LASTVT(A)，即LASTVT(A)=d,a,b,)。构造优先关系表方法如下：对Pab或PaQb，有ab；对PaR而bFIRSTVT(R)，有ab；对PRb而aFIRSTVT(R)，有ab。由此得到：由S(A)得()；由S(A得(FIRSTVT(A)，即(d,(a,(b,(；由AdA得dFIRSTVT(A)，即dd,da,db,d (；第三章第三章语法分析语法分析由SA)得LASTVT(A)，即d),a),b),)；由ASd得LASTVT(S)d，即ad,bd,)d；此外，由#S#得#；由#FIRSTVT(S)得 #a

26、,#b, # (；由LASTVT(S)#得a#, b#, )#。最后得到算符优先关系表，见表3-6。第三章第三章语法分析语法分析表3-6 习题3.13的算符优先关系表第三章第三章语法分析语法分析由表3-6可以看出，任何两个终结符之间至多只满足、三种优先关系之一，故GS为算符优先文法。(2) 为求出句型(SdSdS)的短语、简单短语、句柄，我们先画出该句型对应的语法树，如图3-8所示。第三章第三章语法分析语法分析图3-8句型(SdSdS)的语法树第三章第三章语法分析语法分析由图3-8得到：短语：S，SdS，SdSdS，(SdSdS)简单短语(即直接短语)：S句柄(即最左直接短语)

27、：S可以通过分析图3-8的语法树来求素短语和最左素短语，即找出语法树中的所有相邻终结符(中间可有一个非终结符)之间的优先关系。确定优先关系的原则是：同层的优先关系为；不同层时，层次离树根远者优先级高，层次离树根近者优先级低(恰好验证了优先关系表的构造算法)；在句型两侧加上语句括号“#”，即#，则有#和#，由此我们得到句型(SdSdS)的优先关系如图3-9所示。第三章第三章语法分析语法分析图3-9句型(SdSdS)的优先关系第三章第三章语法分析语法分析注意，句型中的素短语具有如下形式： aj-1ajaj+1aiai+1 而最左素短语就是该句型中所找到的最左边的那个素短语，即最左素短

28、语必须具备三个条件：至少包含一个终结符(是否包含非终结符则按短语的要求确定)；除自身外不得包含其他素短语(最小性)；在句型中具有最左性。第三章第三章语法分析语法分析因此，由图3-9得到SdS为句型(SdSdS)的素短语，它同时也是该句型的最左素短语。(3) 输入串(adb)#的分析过程见表3-7。第三章第三章语法分析语法分析表3-7 输入串(adb)#的分析过程第三章第三章语法分析语法分析为便于分析，同时给出了(adb)#的语法树，如图3-10所示。图3-10(adb)的语法树第三章第三章语法分析语法分析 3.14 在算符优先分析法中，为什么要在找到最左素短语的尾时才返回来

29、确定其对应的头，能否按扫描顺序先找到头后再找到对应的尾，为什么？【解答】设句型的一般形式为N1a1N2a2NnanNn+1。其中，每个ai都是终结符，而Ni则是可有可无的非终结符。对上述句型可以找出该句型中的所有素短语，每个素短语都具有如下形式：aj-1ajaj+1aiai+1 第三章第三章语法分析语法分析如果某句型得到的优先关系如下：则当从左至右扫描到第一个“”时，再由此从右至左扫描到第一个“”时，它们之间(当然不包含第一个“”前一个终结符和第二个“”后一个终结符)即为最左素短语。第三章第三章语法分析语法分析如果由左至右扫描到第一个“”，可以看出这并不一定是最左素短语的开头，因

30、为由它开始并不一定是素短语(在其内部还可能包含其他更小的素短语)，所以，在算符优先分析算法中，只有先找到最左素短语的尾(即“”)，才返回来确定与其对应的头(即“”)；而不能按扫描顺序先找到头然后再找到对应的尾。3.15 试证明在算符文法中，任何句型都不包含两个相邻的非终结符。【解答】设文法G=(VT,VN,S, )，其中VT是终结符集；VN是非终结符集；为产生式集合；S是开始符号。第三章第三章语法分析语法分析对句型的推导长度n作如下归纳：(1) 当n=1时，S，则存在一条产生式S属于，其中a(VTVN) *。由于文法是算符文法，所以中没有两个相邻非终结符，故归纳初始成立。(2) 设n=k

31、时结论成立，则对任何k+1步推导所产生的句型必为S其中，、(VTVN) *，UVN，而UV是一条产生式。第三章第三章语法分析语法分析由归纳假设，U是非终结符，设=12n，=12m，其中i、j (VTVN) (1in-1,2jm) ；但n和m必为位于U两侧的终结符。设V=V1V2Vr，由于它是算符文法的一个产生式右部候选式，因此V1V2Vr中不会有相邻的非终结符出现。又因为nV1和Vr1中的n、1为终结符，也即在推导长度为k+1时所产生的句型12nV1V2Vr12m不会出现相邻的非终结符，故n=k+1时结论成立。显然，在或为空时结论也成立。第三章第三章语法分析语法分析 3.16 给出文法G

32、S: SaSbPPbPcbQc QQaa (1) 它是Chomsky哪一型文法？ (2) 它生成的语言是什么？ (3) 它是不是算符优先文法？请构造算符优先关系表证实之；(4) 文法GS消除左递归、提取公共左因子后是不是LL(1)文法？请证实。第三章第三章语法分析语法分析【解答】 (1) 根据Chomsky的定义，对任何形如A的产生式，有AVN，(VTVN)*时为2型文法。而文法GS恰好满足这一要求，故为Chomsky 2型文法。(2) 由文法GS可以看出：S推出串的形式是ai P bi(i0)，P推出串的形式是bjQcj(j1)，Q推出串的形式是 ak(k1)。因此，文法 GS

33、生成的语言是L=aibjakcjbi|i0, j1, k1。第三章第三章语法分析语法分析 (3) 求出文法GS的FIRSTVT集和LASTVT集：FIRSTVT(S)=a,b FIRSTVT(P)=bFIRSTVT(Q)=aLASTVT(S)=b,c LASTVT(P)=cLASTVT(Q)=a构造优先关系表如表3-8所示。由于在优先关系中同时出现了aa和aa以及bb和bb，故文法GS不是算符优先文法。第三章第三章语法分析语法分析表3-8 优先关系表第三章第三章语法分析语法分析 (4) 消除文法GS的左递归：SaSb|PPbPc|bQcQaQQaQ|提取公共左因子后得到文法G

34、S:SaSb|PPbPPPc|QcQaQQaQ|第三章第三章语法分析语法分析求每个非终结符的FIRST集和FOLLOW集如下：FIRST(S)=a,bFIRST(P)=bFIRST(P)=a,bFIRST(Q)=aFIRST(Q)=a,FOLLOW(S)=b,#FOLLOW(P)=b,c,#FOLLOW(P)=b,c,#FOLLOW(Q)=cFOLLOW(Q)=c第三章第三章语法分析语法分析通过检查GS可以得到：每一个非终结符的所有候选式首符集两两不相交；存在形如A的产生式QaQ|，但有FIRST(aQ)FOLLOW(Q)=ac=所以文法GS是LL(1)文法。第三章第三章语法分析语法

35、分析 *3.17LR分析器与优先关系分析器在识别句柄时的主要异同是什么？【解答】如果SaA且有A，则称是句型相对于非终结符A的短语。特别的，如果有A，则称是句型相对于规则A的直接短语。一个句型的最左直接短语称为该句型的句柄。规范归约是关于的一个最右推导的逆过程，因此，规范归约也称最左归约。请注意句柄的“最左”特征。第三章第三章语法分析语法分析 LR分析器用规范归约的方法寻找句柄，其基本思想是：在规范归约的过程中，一方面记住已经归约的字符串，即记住“历史”；另一方面根据所用的产生式推测未来可能碰到的输入字符串，即对未来进行“展望”。当一串貌似句柄的符号串呈现于栈顶时，则可根据历史、展望以及现

36、实的输入符号等三方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。事实上，规范归约的中心问题恰恰是如何寻找或确定一个句型的句柄。给出了寻找句柄的不同算法也就给出了不同的规范归约方法，如LR(0)、SLR(1)、LR(1)以及LALR就是在归约方法上进行区别的。第三章第三章语法分析语法分析算符优先分析不是规范归约，因为它只考虑了终结符之间的优先关系，而没有考虑非终结符之间的优先关系。此外，算符优先分析比规范归约要快得多，因为算符优先分析跳过了所有单非产生式所对应的归约步骤。这既是算符优先分析的优点，同时也是它的缺点，因为忽略非终结符在归约过程中的作用存在某种危险性，可能导致把本来不

37、成句子的输入串误认为是句子，但这种缺陷容易从技术上加以弥补。为了区别于规范归约，算符优先分析中的“句柄”被称为最左素短语。第三章第三章语法分析语法分析 3.18 什么是规范句型的活前缀？引进它的意义何在？【解答】在讨论LR分析器时，需要定义一个重要概念，这就是文法的规范句型的“活前缀”。字的前缀是指该字的任意首部，例如，字abc的前缀有、a、ab或abc。所谓活前缀，是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。之所以称为活前缀，是因为在其右边增添一些终结符号后，就可以使它成为一个规范句型。引入活前缀的意义在于它是构造LR(0)项目集规范族时必须用到的一个重要概念。第三章第三章

38、语法分析语法分析对于一个文法G，首先要构造一个NFA，它能识别G的所有活前缀，这个NFA的每个状态即为一个“项目”。文法G每一个产生式的右部添加一个圆点称为G的一个LR(0)项目(简称项目)，可以使用这些项目状态构造一个NFA。我们能够把识别活前缀的NFA确定化，使之成为一个以项目集为状态的DFA，这个DFA就是建立LR分析算法的基础。构成识别一个文法活前缀的DFA项目集(状态)的全体称为这个文法的LR(0)项目集归范族。第三章第三章语法分析语法分析 3.19 试构造下述文法的SLR(1)分析表。GS: SbASB | bA AdSa | e BcAa | c【解答】首先将文法GS拓广为

39、GS: GS： (0) SS(1)SbASB(2)SbA第三章第三章语法分析语法分析 (3)AdSa(4)Ae(5)BcAa(6)Bc构造文法GS的LR(0)项目集规范族如下：I0: SS I5: AeSbASB I6: SbASBSbA BcAa第三章第三章语法分析语法分析 I1: SS BcI2: SbASB I7: AdSaSbA I8: SbASBAdSa I9: BcAaAe Bc第三章第三章语法分析语法分析 I3: SbASB AdSaSbA AeSbASB I10: AdSaSbA I11: BcAaI4: AdSa I12: BcAaSbASBSbA文法GS的DFA如图3

40、-11所示。第三章第三章语法分析语法分析图3-11文法GS的DFA第三章第三章语法分析语法分析注意，在比较熟练的情况下，也可以不构造LR(0)项目集规范族而直接画出文法GS的DFA。由于I3和I9既含有移进项目又含有归约项目，故文法GS不是LR(0)文法。我们构造文法GS的FOLLOW集如下：(1) FOLLOW(S)=#；(2) 由SAS得FIRST(S) FOLLOW(A)；即FOLLOW(A)=b；由SSB得FIRST(B) FOLLOW(S)；即FOLLOW(S)=c；由 ASa得 FIRST(a) FOLLOW(S)；即FOLLOW(S)=a,c；第三章第三章语法分析语法

41、分析 (3) 由 SS得 FOLLOW(S)FOLLOW(S)，即FOLLOW(S)=a,c,#；由SB得FOLLOW(S)FOLLOW(B)，即FOLLOW(B)=a,c,#；由SA得FOLLOW(S)FOLLOW(A)，即FOLLOW(A)=a,b,c,#；对I3有：bFOLLOW(S)=ba,c,#=对I9有：d,eFOLLOW(B)=d,ea,c,#= 故文法GS是SLR(1)文法。最后得到SLR(1)分析表见表3-9。第三章第三章语法分析语法分析表3-9 SLR(1)分析表第三章第三章语法分析语法分析 3.20 LR(0)、SLR(1)、LR(1)及LALR有何共同特征？

42、它们的本质区别是什么？【解答】 LR(0)、SLR(1)、LR(1)及LALR的共同特征是都用规范归约的方法寻找句柄，即LR分析器的每一步工作都是由栈顶状态和现行输入符号所唯一决定的。它们的本质区别是寻找句柄的方法不同。如果当前的栈顶状态为归约状态(即有形如A的项目属于栈顶状态)，则：(1) 对LR(0)来说，无论现行输入符号是什么，都认为栈顶的符号串为句柄而进行归约。 (2) 对SLR(1)来说，则对现行输入符号加了一点限制，即该输入符号必须属于允许跟在句柄之后的字符范围内，才认为栈顶的符号串为句柄而进行归约。第三章第三章语法分析语法分析 (3) 对LR(1)来说，对现行输入符号的限制则更

43、加严格，它在该输入符号跟在栈顶符号串后形成一个规范句型的前缀时，才认为栈顶的这个符号串为句柄，从而进行归约。由于要对不同的输入符号进行判断，因此LR(1)的状态数要比LR(0)、SLR(1)多。(4) LALR从本质上讲与LR(1)相同，只不过它把那些栈顶符号串相同但现行输入符号不同(即认为这个相同的栈顶符号串为同心)的判断合一(使状态数又减少到与LR(0)、SLR(1)一样)，只有输入符号跟在栈顶符号串后面形成一规范句型前缀时，才认为栈顶的这个符号串为句柄而进行归约。第三章第三章语法分析语法分析对于同心的栈顶符号串而言，由于面对不同的输入符号将形成不同规范句型的前缀，这就给归约带来一些困

44、难；也即，当输入串有误时，LR(1)能够及时地发现错误，而LALR则可能还继续执行一些多余的归约动作，但决不会执行新的移进，即LALR能够像LR(1)一样准确地指出出错的地点。此外，LALR这种同心集的合并有可能带来新的“归约”/“归约”冲突。3.21 请指出图3-12中的LR分析表(a)、(b)、(c)分属LR(0)、SLR(1)和LR(1)中的哪一种，并说明理由。第三章第三章语法分析语法分析【解答】我们知道，LR(0)、SLR(1)和LR(1)分析表构造的主要差别是构造算法(2)。其区别如下：(1)对LR(0)分析表来说，若项目A属于Ik(状态)，则对任何终结符a(或结束符#)，置

45、ACTIONk,a为“用产生式A进行归约(A为第j个产生式)”，简记为“rj”。表现在ACTION子表中，则是每个归约状态所在的行全部填满“rj”；并且，同一行的“rj”其下标j相同，而不同行的“rj”其下标j是不一样的。第三章第三章语法分析语法分析图3-12 LR分析表第三章第三章语法分析语法分析 (2) 对SLR(1)分析表来说，若项目A属于Ik，则对任何输入符号a，仅当aFOLLOW(A)时置ACTIONk,a为“用产生式A进行归约(A为第j个产生式)”，简记为“rj”。表现在ACTION子表中，则存在某个归约状态所在的行并不全部填满rj，并且不同行的“rj”其下标j不同。(3)

46、对LR(1)来说，若项目A,a属于Ik(状态)，则置ACTIONk,a为“用产生式A进行归约”，简记为“rj”。LR(1)是在SLR(1)状态(项目集)的基础上，通过状态分裂的办法(即分裂成更多的项目集)，使得LR分析器的每个状态能够确切地指出当后跟哪些终结符时才容许把归约为A。例如，假定A,a属于Ik(状态)，则置ACTIONk,a栏目为rj(A为第j个产生式)；而A,b属于Im(状态)，则同样置ACTIONm,b栏目为rj。表现在ACTION子表中，则在不同的行(即不同的状态)里有相同的rj存在。第三章第三章语法分析语法分析因此，图3-12(a)的分析表为LR(1)分析表(在不同行有相

47、同的r2存在)；图3-12(b)为LR(0)分析表(有rj的行是每行都填满了rj且同一行rj的j相同，不同行rj的j不同)；而图3-12(c)为LR(0)分析表(存在并不全部填满rj的行，且不同行rj的j不同)。3.22 文法G(S)的产生式集为 S(EtSeS) | (EtS) | i =EE+EF | FF*Fi | i构造文法G的SLR(1)分析表，要求先画出相应的DFA。第三章第三章语法分析语法分析【解答】将文法G拓广为文法GS：(0)SS(1) S(EtSeS)(2) S(EtS)(3) Si=E(4) E+EF(5) EF(6) F*Fi(7) Fi第三章第三章语法分析语法

48、分析列出LR(0)的所有项目：1. SS 9. S (EtSeS) 17. Si=E 25. EF 2. SS 10. S (EtSeS) 18. Si=E 26. EF 3. S(EtSeS) 11. S(EtS) 19. Si=E 27. F*Fi4. S (EtSeS) 12. S (EtS) 20. Si=E 28. F*Fi 第三章第三章语法分析语法分析 5. S (EtSeS) 13. S (EtS) 21. E+EF 29. F*Fi6. S (EtSeS) 14. S (EtS) 22. E+EF 30. F*Fi 7. S (EtSeS) 15. S (EtS) 23.

49、E+EF 31. Fi 8. S (EtSeS) 16. S (EtS) 24. E+EF 32. Fi第三章第三章语法分析语法分析用_CLOSURE方法构造文法GS的LR(0)项目集规范族：I0: SS I5: S (EtSeS) I13: E+EFS(EtSeS) S (EtS) E+EFS(EtS) I6: S (EtSeS) EFSi=E S(EtSeS) I14: E+EFI1: SS S(EtS) F*Fi第三章第三章语法分析语法分析 I2: S (EtSeS) Si=E FiS (EtS) I7: S (EtSeS) I15: E+EFE+EF I8: S (EtSeS)

50、I16: EFEF I9: S (EtS) I17: F*FiI3: S(EtSeS) I10: Si=E F*FiS(EtS) I11:Si=E Fi第三章第三章语法分析语法分析 I4: S (EtSeS) E+EF I18: F*FiS (EtS) EF I19: F*FiS(EtSeS) I12: Si=E I20: FiS(EtS)Si=E文法GS的DFA如图3-13所示。第三章第三章语法分析语法分析图3-13习题3.22的DFA第三章第三章语法分析语法分析构造SLR(1)分析表必须先求出所有形如“A”的FOLLOW(A)，即由FOLLOW集的构造方法求得GS的FOLLOW集

51、如下：(1) FOLLOW(S)=#；(2) 由S(EtSeS)得FIRST(t) FOLLOW(E)，即FOLLOW(E)=t；FIRST(e) FOLLOW(S)，即FOLLOW(S)=e； FIRST() ) FOLLOW(S)，即FOLLOW(S)=e,)；由F*Fi得FIRST(i) FOLLOW(F)，即FOLLOW(F)=i；由E+EF得FIRST(F)/FOLLOW(E)，即FOLLOW(E)=t,i；第三章第三章语法分析语法分析 (3) 由SS得FOLLOW(S) FOLLOW(S)，即FOLLOW(S)=e,),#；由 Si=E得 FOLLOW(S) FOLLOW(E)

52、，即FOLLOW(E)=t,i,e,),#；由 EF得 FOLLOW(E) FOLLOW(F)，即FOLLOW(F)=t,i,e,),#。最后得到SLR(1)分析表，见表3-10。第三章第三章语法分析语法分析表3-10 习题3.22的SLR(1)分析表第三章第三章语法分析语法分析 3.23 为二义文法GT构造一个LR分析表(详细说明构造方法)。其中终结符“，”满足右结合性，终结符“；”满足左结合性，且“，”的优先级高于“；”的优先级。 GT: TTAT | bTe | a A, | ;【解答】首先将文法GT拓广为文法GS：(0) ST第三章第三章语法分析语法分析 (1)TTAT

53、(2) TbTe(3) Ta(4) A，(5) A；下面列出LR(0)的所有项目： 1ST 5TTAT 9TbTe 13A， 2ST 6TTAT 10TbTe 14A，第三章第三章语法分析语法分析 3 TTAT 7 TbTe 11Ta 15A; 4TTAT 8TbTe 12Ta 16A; 用_CLOSURE方法构造文法GS的LR(0)项目集规范族，并根据转换函数GO构造出文法GS的DFA，如图3-14所示。第三章第三章语法分析语法分析图3-14习题3.23中文法GS的DFA第三章第三章语法分析语法分析已知文法GS为二义文法，故必然存在冲突。逐一检查各状态，得知I8存在“移进”/“归

54、约”冲突(因为TTAT要求归约，而TTAT却要求移进)。在此，LR(0)已不能满足要求，因为LR(0)分析表中的ACTION子表在某归约状态下(即某一行)的所有栏目全被“rj”占满，但由于存在“移进”/“归约”冲突，即在此状态下，有些栏目应填为“Sj”(即归约)。为了减少冲突，最好采用SLR(1)、LR(1)或LALR分析表。这里采用SLR(1)分析表。下面，构造文法GS中非终结符的FIRST集和FOLLOW集如下：FIRST(S)=FIRST(T)=a,b; FIRST(A)=“， ”,“；”FOLLOW(S)=#； FOLLOW(T)=“， ”,“； ”,e,#；FOLLOW(A)=a,b

55、第三章第三章语法分析语法分析因为TTAT要求归约，而TTAT要求移进，即对T要求归约而对A要求移进，则有：FOLLOW(T)FIRST(A)=“， ”,“； ”,e,#“，”,“；”=“，”,“；”也即冲突字符为“，”和“；”。下面分析“，”与“；”的具体情况。因为“，”的优先级高且有右结合，故不论是“，”还是“；”，遇见“，”其后的“，”一定移进；类似地，“；”优先级低且有左结合，则无论是“，”还是“；”，遇见其后的“；”一定归约。由此可得到SLR(1)分析表，见表3-11。第三章第三章语法分析语法分析从分析表中可以看到，本应该对在状态8对应ACTION子表中的字符集e,“，”,“，

56、”,#都执行用r1归约，但“，”和“；”存在“移进”/“归约”冲突，由于“，”的优先级高且有右结合，故对应ACTOIN8,“，”栏改为s5，即移进；由于“；”满足左结合性，即应归约，所以ACTION8,“，”栏仍为r1。第三章第三章语法分析语法分析表3-11 习题3.23的SLR(1)分析表第三章第三章语法分析语法分析注意，如果将条件改为“，”的优先级高且满足左结合，则将无法构造分析表。这是因为“，”在遇见其后的“，”时要求归约；而“；”在遇见其后的“，”时则要求移进；这时ACTION8,“，”栏就无法确定是放“r1”还是放“s5”了。3.24 文法GT及其SLR(1)分析表(见表3-

57、12)如下，给出串bibi的分析过程。GT:(1) TEbH (2) Ed (3) E(4) Hi (5) HHbi (6) H第三章第三章语法分析语法分析表3-12 习题3.24的SLR(1)分析表第三章第三章语法分析语法分析【解答】对句子bibi，先构造它的语法树，如图3-15所示。第三章第三章语法分析语法分析图3-15句子bibi的语法树第三章第三章语法分析语法分析 bibi的分析过程参考该语法树进行，见表3-13。第三章第三章语法分析语法分析表3-13 bibi的分析过程第三章第三章语法分析语法分析 3.25 给出文法GS及图3-16所示的LR(1)项目集规范族中

58、的0、1、2、3、4。 GS: SS;B | BBBaA | AAb(S) 第三章第三章语法分析语法分析图3-16习题3.25的部分项目集第三章第三章语法分析语法分析【解答】首先求出GS中所有非终结符的FOLLOW集。已知FOLLOW(S)=#；则：由 SS得 FOLLOW(S) FOLLOW(S)，即FOLLOW(S)=#；由SS;得FOLLOW(S)=#,;；由AS)得FOLLOW(S)=#,;,)；由BBa得FOLLOW(B)=a；第三章第三章语法分析语法分析由SB得FOLLOW(S) FOLLOW(B)，即FOLLOW(B)=#,;,),a；由BA得FOLLOW(B)

59、FOLLOW(A)，即FOLLOW(A)=#,;,),a。LR(1)的闭包CLOSURE(I)可按如下方法构造：(1) I的任何项目都属于CLOSURE(I)。(2) 若项目AB,a属于CLOSURE(I)，B是一个产生式，对FIRST(a)中的每个终结符b，如果B,b原来不在CLOSURE(I)中，则把它加进去。 (3) 重复执行步骤(2)，直至CLOSURE(I)不再增大为止。注意，b可能是从推出的第一个符号，若推出，则b就是a。第三章第三章语法分析语法分析我们先构造LR(1)项目集族的I0。由FOLLOW(S)=#可知SS,#CLOSURE(I0)。此时=，故b=a=“#”，即有：S

60、S;B,#CLOSURE(I0)SB,#CLOSURE(I0)此时对B而言，因=，即b=a=“#”。对SS;B,#，由于，而FIRST()=FIRST(;B)=;；则有：SS;B,#/;CLOSURE(I0)SB,#/;CLOSURE(I0)第三章第三章语法分析语法分析同时有：BBaA,#/;CLOSURE(I0)BA,#/;CLOSURE(I0)此时对A而言，因=，即b=a=“#/;”。对BBaA,#，由于，而FIRST()=FIRST(aA)=a；则有：BBaA,#/;/aCLOSURE(I0)BA,#/;/aCLOSURE(I0)同时有：Ab(S),#/;/aCLOSURE(I0)第

61、三章第三章语法分析语法分析图3-17 习题3.25的LR(1)部分项目集第三章第三章语法分析语法分析 3.26 一个非LR(1)的文法如下： LMLb | aM请给出所有“移进”/“归约”冲突的LR(1)项目集，以说明该文法确实不是LR(1)的。【解答】先将文法GL拓广为GL：(0) LL1) LMLb(2) La(3) M第三章第三章语法分析语法分析如果按LR(1)方法构造分析表时出现“移进”/“归约”冲突，则项目集规范族中一定包含如下形式的项目：Ab,a 和 A,b即移进符号与向前搜索符号相同。在构造LR(1)项目集族之前，我们先求出GL中所有非终结符的FIRST集和FOLLO

62、W集： FIRST(L)=FIRST(L)=a, FIRST(M)= 由FOLLOW集构造方法知FOLLOW(L)=#；第三章第三章语法分析语法分析由 LLb 得 FIRST(b) FOLLOW(L)，即FOLLOW(L)=b；由 LML 得 FIRST(L) FOLLOW(M)，即FOLLOW(M)=a；由 LL得 FOLLOW(L) FOLLOW(L)，即FOLLOW(L)=#,b。LR(1)闭包CLOSURE(I)构造方法如下：(1) I的任何项目都属于CLOSURE(I)。(2) 若项目AB,a属于CLOSURE(I)，B是一个产生式，对FIRST(a)中的每个终结符b，如果

63、B,b原来不在CLOSURE(I)中，则把它加进去。(3) 重复执行步骤(2)，直至CLOSURE(I)不再增大为止。第三章第三章语法分析语法分析注意，b可能是从推出的第一个符号，若推出，则b就是a。令LL,#CLOSURE(I0)，求得项目集如下：I0：LL,# I2：LMLb,# I4：LMLb,b LMLb,# LMLb,b LMLb,b La,# La,b La,b M, a M, a M, a I1：LL,# I3：LMLb,# I5：LMLb,#如果一个项目中含有m个移进项目：A1a11, A2a22, ,Amamm第三章第三章语法分析语法分析同时I中含有n个归约项目：B1

64、, B2, , Bn如果集合a1, ,am，FOLLOW(B1), ,FOLLOW(Bn)两两相交，则必然存在“移进”/“归约”冲突。由I0中La, #和M,a 可知aFOLLOW(M)=aa(在此=)；由I2中La,b和M,a 可知aFOLLOW(M)；由I4中La,b和M,a 可知aFOLLOW(M)；也即，I0 、I2 、I4三个项目集存在“移进”/“归约”冲突。第三章第三章语法分析语法分析 3.27 试证明任何一个SLR(1)文法一定是一个LALR(1)文法。【解答】我们知道，在求闭包_CLOSURE(I)时，构造有效的LR(1)项目集与构造LR(0)项目集是有区别的。如果AB属于

65、CLOSURE(I)，且关于B的产生式是B，则对LR(0)来说，项目B也属于CLOSURE(I)；而对LR(1)(假定AB的后续一个字符为a)，则要求对FIRST(a)中的每个终结符b，有项目B,b属于CLOSURE(I)。LR(1)、LR(0)以及SLR(1)方法的区别也仅在上述构造分析表的算法上。也即若项目第三章第三章语法分析语法分析 A属于Ik，则当“用产生式A归约”时，LR(0)是无论面临什么输入符号都进行归约；SLR(1)则是仅当面临的输入符号aFOLLOW(A)时才进行归约，而并不判断符号栈里的符号串所构成的活前缀是否把归约为A的规范句型前缀Aa；而LR(1)则明确指出只有当后跟

66、终结符a(即存在规范句型其前缀为Aa)时，才允许把归约为A。因此，LR(1)比SLR(1)更精确，解决的冲突也多于SLR(1)，但LR(1)的要求(即限制)也比SLR(1)严格。但是对LR(1)来说，其中的一些状态(项目集)除了向前搜索符不同外，其核心部分都是相同的，也即LR(1)比SLR(1)和LR(0)存在更多的状态，但是每个LR(0)文法、SLR(1)文法都是LR(1)文法。第三章第三章语法分析语法分析如果两个LR(1)项目集除去搜索符之后是相同的，则称这两个LR(1)项目集具有相同的心。当把所有同心的LR(1)项目集合并为一时，则会看到一个心就是LR(0)项目集(同时也是SLR(1

67、)项目集)，这种LR分析法称为LALR方法。假定有一个LR(1)文法，它的LR(1)项目集不存在动作冲突，如果我们把同心集合并为一，就可能导致冲突存在。但是这种冲突不会是“移进”/“归约”间的冲突。因为若存在这种冲突，则意味着面对当前的输入符号a，有一个项目A,a要求采取归约动作；同时又有另一项目Ba,b要求把a移进。第三章第三章语法分析语法分析这两个项目既然同处在合并之后的一个集合中，就意味着在合并之前必然有某个c使得A,a和Ba,c同处于(合并之前的)某一集合中，然而这又意味着原来的LR(1)项目集已经存在着“移进”/“归约”冲突了，同时也意味着SLR(1)项目集也已经存在着“移进”/

68、“归约”冲突(因为SLR(1)与合并后的LALR项目集相同。)第三章第三章语法分析语法分析但是，同心集的合并有可能产生新的“归约”/“归约 ”冲突。假定有对活前缀 ac有效的项目集为Ac,d, Bc,e，对 bc有效的项目集为 Ac,e, Bc,d，这两个集合都不含冲突，它们是同心的，但合并后就变成Ac,d/e, Bc,d/e，显然这是一个含有“归约”/“归约”冲突的集合。由于SLR(1)与LALR同心(项目集相同),故在SLR(1)文法中必然存在“归约”/“归约”冲突。由此可知,任何一个SLR(1)文法一定是一个LALR(1)文法。注意，LAL

69、R项目集族总是与同一文法的SLR(1)项目集的心相同，并且实现LALR分析对文法的要求比LR(1)严但比SLR(1)宽，而开销比SLR(1)大却远小于LR(1)。第三章第三章语法分析语法分析 3.28 已知文法GS: SaAd | ;Bd | aB| ;AAaBa(1) 试判断GS是否为LALR(1)文法。(2) 当一个文法是LR(1)而不是LALR(1)时，那么LR(1)项目集的同心集合并后会出现哪几种冲突，请说明理由。第三章第三章语法分析语法分析【解答】 (1) 将文法GS拓广为文法GS：(0) SS(1) SaAd(2) S;Bd(3) SaB(4) S;A(5) Aa(6) Ba

70、第三章第三章语法分析语法分析判断GS是否为LALR(1)文法的方法是：首先构造LR(1)项目集族，如果它不存在冲突，就把同心集合并在一起；若合并后的集族不存在“归约”/“归约”冲突(即不存在同一个项目集中有两个像Ac和Bc这样具有相同搜索符的产生式)，则表明GS是LALR(1)文法。在构造LR(1)项目集族之前，先求出GS中所有非终结符的FIRST集和FOLLOW集如下： FIRST(S)= FIRST(S)=a,; FIRST(A)=a FIRST(B)=a由FOLLOW集构造方法知FOLLOW(S)=#；由 SS得 FOLLOW(S) FOLLOW(S)，即FOLLOW(S)=#；第

71、三章第三章语法分析语法分析由SAd和SA得FOLLOW(A)=d,；由SBd和SB得FOLLOW(B)=d,。LR(1)的闭包CLOSURE(I)可按如下方法构造： I的任何项目都属于CLOSURE(I)；若项目AB,a属于CLOSURE(I)，B是一个产生式，对FIRST(a)中的每一个终结符b，如果B,b原来不在CLOSURE(I)中，则把它加进去。重复执行步骤，直至CLOSURE(I)不再增大为止。注意，b可能是从推出的第一个符号，若推出，则b就是a。第三章第三章语法分析语法分析 LR(1)项目集族构造如下：由FOLLOW(S)=#知S的向前搜索字符为“#”，即SS,#。令

72、SS,# CLOSURE(I0)，我们来求出属于I0的所有项目。已知SS,#CLOSURE(I0)，由LR(1)闭包CLOSURE(I)步骤知=，也即对产生式SaAd、S;Bd、SaB、S;A都有b=a=“#”。由此得到项目集I0如下：I0：SS,# SaAd,# S;Bd,# SaB,# S;A,#第三章第三章语法分析语法分析同理求得其他项目：I1: SS,# I4: SaAd,# I10: SaAd,# I2: SaAd,# I5: SaB,# I11: SaB,# SaB,# I6: Aa,d I12: S;Bd,# Aa,d Ba, I13: S;A,# 第三章第三章

73、语法分析语法分析 Ba, I7: S;Bd,# I3: S;Bd,# I8: S;A,#S;A,# I9: Aa,Aa, Ba,d Ba,d根据LR(1)项目集族，将同心集合并(即去掉向前搜索符后两个项目的产生式相同)。经检查，只有I6与I9同心，即将I6和I9合并为I69： I69：Aa,/d Ba,/d此时出现了“归约”/“归约”冲突，即对“”或“d”不知是用Aa归约，还是用Ba归约，故GS不是LALR文法。第三章第三章语法分析语法分析 (2) 当一个文法是LR(1)而不是LALR时，那么LR(1)项目集的同心集合并后只可能出现“归约”/“归约”冲突，而不会是“移进”/“归约”冲突。因为

74、如果存在这种冲突，则意味着面对当前输入符号a，有一个项目A,a要求采取归约动作，同时又有另一项目Ba,b要求把a移进。这两个项目既然同处在合并之后的一个集合中，就意味着在合并前必有某个c使得 A,a和 Ba,c同处于 (合并之前的 )某一集合中，然而这又意味着原来的LR(1)项目集已经存在着“移进”/“归约”冲突了。因此，同心集的合并不会产生新的“移进”/“归约”冲突(因为是同心合并，所以只改变了搜索符，而并没有改变“移进”或“归约”操作，故不可能存在“移进”/“归约”冲突)。第三章第三章语法分析语法分析但是，同心集的合并有可能产生新的“归约”/“归约”冲突。例如本题中，

75、对活前缀aa有效的项目集为I6： Aa,d, Ba,，对活前缀 ,a有效的项目集为I9： Aa, Ba,d，这两个集合都不含冲突，它们是同心的，但合并之后就变成 Aa,/d, Ba, /d，显然这是一个含有“归约”/“归约”冲突的集合，因为当面临“”或“d”时我们不知道该用Aa还是Ba进行归约。第三章第三章语法分析语法分析 3.29 给定文法GA: A(A)|a。 (1) 证明：LR(1)项目A(A),对活前缀“(a”是有效的；(2) 画出LR(1)项目识别所有活前缀的DFA；(3) 构造LR(1)分析表；(4) 合并同心集，构造LALR(1)分析表。【解答】 (1) 证明：首先将文法DA拓

76、广为GA：(0) A A(1) A (A)(2) A a第三章第三章语法分析语法分析其次，构造文法GA的FOLLOW集如下: FOLLOW(A)=#；由AA)得FIRST()FOLLOW(A)，即FOLLOW(A)=)；由AA得，FOLLOW(A) FOLLOW(A)，即FOLLOW(A)=),#。下面构造LR(1)项目集规范族，其构造方法如下： I的任何项目都是属于CLOSURE(I)的；第三章第三章语法分析语法分析若项目AB,a属于CLOSURE(I)，B是一个产生式，对FIRST(a)中的每个终结符b，如果B,b原来不在CLOSURE(I)中，则把它加进去；重复执行步骤，

77、直至CLOSURE(I)不再增大为止。注意，b可能是从推出的第一个符号；若推出，则b就是a。第三章第三章语法分析语法分析由此得到文法GA的LR(1)项目集规范族如下(项目集I0由AA，#开始)：I0: AA,# I4: A(A),#A(A),# I5: A(A),#Aa,# I6: A(A),)I1: AA,# A(A),)I2: A(A),# Aa,) A(A),) I7: A(A),) A a,) I8: A(A),)I3: Aa,# I9: Aa,)LR(1)识别所有活前缀的DFA如图3-18所示。第三章第三章语法分析语法分析而项目A(A),对应图3-18中的I7，即由I0到达I

78、7的活前缀 (即由 I0到达 I7道路上的字符组成 )为“(A”，其中“(”至少有两个“(”。由此得到项目A(A),)对活前缀“(A”有效。(2) LR(1)项目识别所有活前缀的DFA如图3-18所示。(3) 构造的LR(1)分析表见表3-14。第三章第三章语法分析语法分析图3-18识别活前缀的DFA第三章第三章语法分析语法分析表3-14 习题3.29的LR(1)分析表第三章第三章语法分析语法分析将I3、I9合并成I39：Aa，)/#；将 I2、 I6合并成 I26： A(A)， )/#， A(A)， )，Aa，)；将I4、I7合并成I47：A(A)，)

79、/#；将I5、I8合并成I58：A(A)，)/#。由此得到合并后集族所构成的LALR分析表，见表3-15。第三章第三章语法分析语法分析表3-15 合并后集族所构成的LALR分析表第三章第三章语法分析语法分析 3.30 下述文法GS是哪类LR文法？构造相应LR分析表。 GS: (1) SL=R(2) SR(3) L*R(4) Li(5) RL第三章第三章语法分析语法分析【解答】首先将文法GS拓广为GS：(0) SS(1) SL=R(2) SR(3) L*R(4) Li(5) RL第三章第三章语法分析语法分析构造文法GS的LR(0)项目集规范族如下：I0: SS I2: SL=R

80、I5: SRSL=R RL I6: SL=RSR I3: L*R RLL*R RL L*RLi L*R LiRL Li I7:SL=RI1: SS I4: Li I8:L*R第三章第三章语法分析语法分析我们知道，如果每个项目集中不存在既含移进项目又含归约项目，或者含有多个归约项目的情况，则该文法是一个LR(0)文法。检查上面的项目集规范族，发现I2存在既含移进项目SL=R又含归约项目RL的情况，故文法GS不是LR(0)文法。假定LR(0)规范族的一个项目集I中含有m个移进项目：A1a11, A2a22, Amamm同时I中含有n个归约项目:B1, B2, Bn如果集合a1,am，FOLLO

81、W(B1)，FOLLOW(Bn)两两不相交(包括不得有两个FOLLOW集含有“#”)，则要解决隐含在I中的动作冲突，可检查现行输入符号a属于上述n+1个集合中的哪个集合，这就是SLR(1)文法。第三章第三章语法分析语法分析因此，构造文法GS的FOLLOW集如下：(1) FOLLOW(S)=#；(2) 由SL=得FIRST(=)FOLLOW(L)，即FOLLOW(L)=；(3) 由 SS得 FOLLOW(S) FOLLOW(S)，即FOLLOW(S)=#；由SR得FOLLOW(S) FOLLOW(R)，即FOLLOW(R)=#；由LR得FOLLOW(L) FOLLOW(R)，即FOLLOW

82、(R)=,#；由RL得FOLLOW(R) FOLLOW(L)，即FOLLOW(L)=,#。由I2的移进项目SL=R和归约项目RL得到： =FOLLOW(L)=,#=所以文法GS不是SLR(1)文法。第三章第三章语法分析语法分析下面构造LR(1)项目集规范族，得到文法GS的LR(1)项目集规范族如下(项目集I0由SS,#开始)：I0: SS,# I6: SL=R,#SL=R,# RL,#SR,# L*R,#L*R,= Li,#Li,= I7: L*R,=RL,# I8: RL,=第三章第三章语法分析语法分析 I1: SS,# I9: SL=R,#I2: SL=R,# I10: RL,# R

83、L,# I11: L*R,#I3: SR,# RL,#I4: L*R,= L*R,# RL,= Li,#L*R,= I12: Li,#Li,= I13: L*R,#I5: Li,=第三章第三章语法分析语法分析此时，I2的移进项目SL=R,#和归约项目RL,#有：=#= 故文法GS是LR(1)文法。最后得到LR(1)分析表，见表3-16。第三章第三章语法分析语法分析表3-16 习题3.30的LR(1)分析表第三章第三章语法分析语法分析 3.31 已知布尔表达式的文法GB如下： GB: BABOBnot B(B)i rop ii AB and OB or试为GB构造LR分析表。【解答】

84、将文法GB拓广为文法GS：(0) SB(1) Bi(2) Bi rop I(3) B(B)第三章第三章语法分析语法分析 (4) Bnot B(5) AB and(6) BAB(7) OB or(8) BOB列出LR(0)的所有项目：1. SB 8. Bi rop i 15. Bnot B 22. OB or 2. SB 9. B(B) 16. AB and 23. OBor 3. Bi 10. B(B) 17. 第三章第三章语法分析语法分析 ABand 24. OB or 4. Bi 11. B(B) 18. AB and 25. BOB5. Bi rop i 12. B(B) 19.

85、BAB 26. BOB6. Bi rop i 13. Bnot B 20. BAB 27. BOB7. Bi rop i 14. Bnot B 21. BAB 用_CLOSURE方法构造出文法GS的LR(0)项目集规范族，并根据状态转换函数GO画出文法GS的DFA，如图3-19所示。第三章第三章语法分析语法分析图3-19习题3.31中文法GS的DFA第三章第三章语法分析语法分析下面，对文法GS中形如“A”的项目：I13 ： SB I12 ： B(B)I14 ： BABI1 ： BiI6 ： Bnot BI10 ： OB orI3 ： Bi rop iI9 ： AB andI15 ： B

86、OB求FOLLOW集。根据FOLLOW集构造方法，构造文法GS中非终结符的FOLLOW集如下：对文法开始符S，#FOLLOW(S)，即FOLLOW(S)=#。第三章第三章语法分析语法分析由BB)得FIRST() )FOLLOW(B)，即FOLLOW(B)= )；由 BB and得 FIRST(and)FOLLOW(B)，即 FOLLOW(B)= )，and; 由 OB or得 FIRST(or)FOLLOW(B)，即 FOLLOW(B)=)，and,or; 由BAB得FIRST(B)FOLLOW(A)，即FOLLOW(A)= i，(,not)(注：FIRST(B)= i，(,not

87、)；第三章第三章语法分析语法分析由 BOB得 FIRST(B)FOLLOW(O)，即 FOLLOW(O)= i，(,not)。由 SB得 FOLLOW(S)FOLLOW(B)，即 FOLLOW(B)= )，and，or,#，由此得到FOLLOW(B)= )，and，or,#，FOLLOW(A)=FOLLOW(O)= i，(,not)。分析图3-19，可知I1、I6、I14、I15存在矛盾。I1的“移进”/“归约”矛盾可以在SLR(1)下得到解决，因为FOLLOW(B)= )，and，or,#，而移进仅是在字符“rop”下进行的，即有FOLLOW(B) rop =，故移进与归约不发生

88、矛盾(归约是在字符“)”、“and”、“or”或“#”下进行的)。第三章第三章语法分析语法分析而I6、I14和I15的“移进”/“归约”矛盾无法得到解决(在字符“and”和“or”下既要“移进”又要“归约”)，故文法GS是一个二义文法。经分析，当B遇到后面的“and”或“or”时应移进，故服从右结合规则。由此得到布尔表达式的SLR(1)分析表见表3-17。第三章第三章语法分析语法分析表3-17 习题3.31的布尔表达式的SLR(1)分析表第三章第三章语法分析语法分析 3.32 给出文法GS: SSaSSbScSdeSf。(1) 请证实这是一个二义文法；(2) 给出什么样的约束条件可构

89、造无冲突的LR分析表？请证实你的论点。【解答】 (1)对于语句fafbf，该文法存在两棵不同的语法树，如图3-20所示。第三章第三章语法分析语法分析图3-20 语句fafbf的两棵不同语法树第三章第三章语法分析语法分析因此，GS是二义文法。(2) 首先将文法GS拓广为GS：(0) SS(1) SSaS(2) SSbS(3) ScSd(4) SeS(5) Sf该文法GS的DFA如图3-21所示。第三章第三章语法分析语法分析图3-21 习题3.32中GS的DFA第三章第三章语法分析语法分析状态I1、I8、I9和I10存在“移进”/“归约”冲突。计算GS中所有非终结符的FOLLOW集

90、：FOLLOW(S)=#FOLLOW(S)=a,b,d,# 对于I1：SSSSaSSSbS可以采用SLR(1)解决冲突，即当LR分析器处于状态1时，如果下一个输入符号是“#”，则按SS执行归约；如果下一个输入符号是“a”或“b”，则执行移进。第三章第三章语法分析语法分析对于I8：SeS SSaS SSbS该冲突无法采用SLR(1)解决，我们给出约束条件：让e的优先级比a和b高，则当LR分析器处于状态8时，若下一输入符号是FOLLOW(S)中的符号，就按SeS执行归约。第三章第三章语法分析语法分析对于I9：SSaS SSaS SSbS该冲突无法采用SLR(1)解决，我们给出约束条件：让a

91、的优先级比a和b高，即实行左结合，则当LR分析器处于状态9时，若下一输入符号是FOLLOW(S)中的符号，就按SSaS执行归约。对于I10：SSbSSSaSSSbS此时也给出约束条件：让b的优先级比a和b高，即实行左结合，则当LR分析器处于状态10时，若下一输入符号是FOLLOW(S)中的符号，就按SSbS执行归约。第三章第三章语法分析语法分析综上所述，统一给出构造无冲突的LR分析表的约束条件是：左边终结符的优先级比右边终结符高，即实行左结合。另外，我们也看到，消除左递归有助于解决LR分析表中的冲突。3.33 根据下面所给文法GS和表3-18分析ia;iaea# 的语义加工过程。 GS：(0) SS(1) SiSeS(2) SiS(3) SS;S(4) Sa【解答】 ia;iaea# 的语义加工过程见表3-19。第三章第三章语法分析语法分析表3-18 习题3.33的SLR(1)分析表第三章第三章语法分析语法分析表3-19 ia;iaea# 的语义加工过程

展开阅读全文

第三章语法分析

最新文档