搜索
1．★已知文法G[S]：S→SaA|AA→AbB|BB→cSd|e请证实AacAbcBaAdbed是文法的一个句型，并写出该句型的所有短语、素短语以及句柄。解：本题考查“句型”、“短语”、“句柄”、“素短语”等概念。符号栈S关系输入串最左素短语S1S2S3S4S5S6S7R1R2R3R4R5R6＃(adb)##(adb)##(adb)#d#(Vdb)##(Vdb)##(Vdb)#b#(VdV)#VdV#(V=)##(=V)#(V)#V#接受因为存在从文法开始符号S到符号串AacAbcBaAdbed的推导过程（如图6.1中的语法树所示），所以符号串AacAbcBaAdbed是文法的句型。从图6.1中句型A1a1c1A2b1c2Ba2A3d1b2ed2的语法树可知，该句型的短语有：A1、B、Ba2A3、c2Ba2A3d1、A2b1c2Ba2A3d1、e、A2b1c2Ba2A3d1b2e、c1A2b1c2Ba2A3d1b2ed2、A1a1c1A2b1c2Ba2A3d1b2ed2该句型的素短语有：Ba2A3、e该句型的句柄为：B2．★已知文法G[S]：S→*AA→0A1|*（1）求文法G的各非终结符号的FIRSTVT集和LASTVT集;（2）构造文法G的优先关系矩阵，并判断该文法是否是算符优先文法；（3）分析句子*0*1，并写出分析过程。解：本题考查算符优先分析法中的有关知识：非终结符号的FIRSTVT集和LASTVT集的求法、算符优先关系的构造、算符优先文法的定义、算符优先分析过程等。（1）求文法G的各非终结符号的FIRSTVT集和LASTVT集。根据非终结符号的FIRSTVT集定义得到FIRSTVT（S）＝｛*｝FIRSTVT（S）＝｛0，*｝根据非终结符号的LASTVT集定义得到LASTVT（S）＝｛*，1｝LASTVT（S）＝｛1，*｝SSa1AA1Bc1Sd2AAb2BA2b1Bec2Sd1Sa2A3AB图6.1句型AacAbcBaAdbed的语法树（2）构造文法G的优先关系矩阵。根据（1）中的FIRSTVT集和LASTVT集及算符优先关系构造算法对S→*A，按算法第3种情形有：（*0），（**）对A→0A1，按算法第1种情形有：（0|＝1）按算法第3种情形有：（0|0）,(0|*)按算法第4种情形有：（1|1），(*|1),根据上述算符优先关系得到算符优先关系矩阵如表6.1所示。表中空白元素表示相应终结符号对之间没有算符优先关系，即它们不会在任何句型中相继出现。表6.1文法的算符优先关系矩阵01*0||=|1|*|||(3)对句子“*0*1#”分析过程如表6.2所示。表6.2分析输入符号串“*0*1#”的过程符号栈S关系输入串最左素短语S1S2S3S4S5S6S7R1R2R3R4R5#*0*1##*0*1##*0*1##*0*1#*#*0V=##*0V=1#0V1#*V#*V#V#接受3．试为下列优先矩阵构造优先函数。（1）S1S2S3S4S1S2±±S3S4(2)S1S2S3S4S1S2S3±S4±±解：本题考查优先函数的构造方法。（1）采用迭代法求优先函数，过程如下。（2）初始状态：S1S2S3S4f1111g1111第1次迭代：S1S2S3S4f1122g1111第2次迭代：S1S2S3S4f1122g1111第2次迭代没有变化，所以第2次迭代结果便是优先函数。（3）采用Bell有向图法构造优先函数(省略)。因为fs1可以到达的结点：gs3，gs4，fs4，gs3，gs2fs2可以到达的结点：gs3，fs3，gs2，fs4，gs1fs3可以到达的结点：gs2，fs3fs4可以到达的结点：gs1，gs3，fs3，gs2，fs4gs1可以到达的结点：fs3，fs4，gs2，gs1，gs3gs2可以到达的结点：fs3，gs2gs3可以到达的结点：fs4，fs3，gs1，gs3，gs2gs4可以到达的结点：无于是得到优先函数如表6.3所示。S1S2S3S4f7625g52514.试为文法G[Z]：Z→A()A→(|Ai|B)B→i构造算符优先关系和优先函数。解：本题考查算符优先关系的构造方法和优先函数的构造方法。（1）构造算符优先关系。首先构造FIRSTVT集和LASTVT集，根据定义有：FIRSTVT（Z）＝｛（，i，）｝FIRSTVT（A）＝｛（，i，）｝FIRSTVT（B）＝｛i｝和LASTVT（Z）＝｛｝｝LASTVT（A）＝｛（，），i｝LASTVT（B）＝｛i｝按照构造算符优先关系的算法得到如下算符优先关系：“＝”的构造∵有产生式Z→A（）∴按算法第1种情形有：（（＝））“”的构造文法没有满足“”的相邻符号“”的构造∵有产生式Z→A（）∴按算法第4种情形有：（(（），（）（），（i（）∵有产生式A→Ai∴按算法第4种情形有：（（i）,()i），（ii）∵有产生式A→B)∴按算法第4种情形有：(i))综合上述算符优先关系得到该文法的算符优先关系矩阵如表6.4所示。（）i（=）I(2)构造优先函数。①采用迭代法（先考虑所有的大于关系，再考虑所有的等于关系）。初始状态：（）if111g111第1次迭代：（）if222g121第2次迭代：（）if223g121第3次迭代：（）if223g121第3次迭代没有变化，所以第3次迭代的的结果便是优先函数。②采用Bell有向图法构造优先函数，其过程如图6.2所示。图6.2构造优先函数因为f（可以到达的节点：g（，g），gi，f（f）可以到达的节点：g（，gifi可以到达的节点：g（，g），gi，f（g（可以到达的节点：无g）可以到达的节点：g（，g），gi，f（gi可以到达的节点：无于是得到优先函数如表6.5所示。表6.5文法的优先函数（）iF435G1415.给出文法G2：S→SaS|SbS|cSd|eS|f（1）请证实这是一个二义文法；（2）给出什么样的约束条件，可构造出无冲突的LR分析表？请证实你的论点。解：本题考查“二义文法”及二义文法的LR分析法。（1）该文法是二义文法，因为它存在句子：fafbf该句子有两棵不同的语法树，如图6.3中的（a），（b）所示。（2）构造文法的无冲突的LR分析表。首先对文法进行拓广得到S’→S0S→SaS1S→SbS2S→cSd3S→eS4S→f5在此基础上构造文法的识别活前缀的有穷自动机(省略)。因为：FOLLOW(S)={#，a，b，d}构造文法的SLR(1)分析表如表6.6所示。表6.6文法的SLR(1)分析表状态ACTIONGOTOabcdef#S0S2S3S411S5S6acc2S2S3S493S2S3S4104r5r5r5r575S2S3S476S2S3S487r1/S5r1/S6r1r1SSbSfSaSffSSaSfSbSff图6.3句子fafbf的两棵语法树8r2/S5r2/S6r2r29S5S6S1110r4/S5r4/S6r4r411r3r3r3r36.已知文法：G[A]：A→AA|(A)|ε（1）该文法是LR(0)文法吗？为什么？（2）请构造该文法的以LR(0)项目集为状态的识别活前缀的DFA。（3）规定：出现“移进-归约”冲突时，移进优先；出现“归约-归约”冲突时，优先采用文法中出现在前的产生式进行归约。构造该文法的LR分析表。解：本题考查对二义性文法进行LR分析的方法。先构造出识别活前缀的有穷自动机，然后根据其中出现的冲突情况确定无二义规则的使用。首先构造拓广文法如下：0A’→A1A→AA2A→(A)3A→ε（1）该文法不是LR(0)文法。因为文法存在有相同左部的产生式A→AA和A→ε产生式A→ε在任何时候都只产生归约项目。当由项目A’→.A派生出新项目时，同时得到A→.(A)和A→.将出现“移进→归约”冲突。所以该文法不是LR(0)文法。（2）构造该文法的以LR(0)项目集为状态的识别活前缀的DFA如图6.4所示。（3）因为出现“移进－规约”冲突时，移进优先；出现“规约－规约”冲突时，优先采用文法中出现在前的产生式进行规约，所以得到该文法的LR分析表如表6.7所示。图6.4文法的以LR(0)项目集为状态的识别活前缀的DFAA(I0A’→．AA→．AAA→．(A)A→．I1A’→A．A→A．AA→．AAA→．（A）A→．I2A→(．A)A→．AAA→．（A）A→．I3A→AA．A→A．AA→．AAA→．（A）A→．I4I5A→(A)．(A(()A→(A．)A→A．AA→．AAA→．（A）A→．AA(A表6.7文法的LR分析表状态ACTIONGOTO()#A0S2r3r311S2r3acc22S2r3r333S2r1r144S2S5r355r2r2r27．★“算符优先分析采用“移进－归约”技术，其规约过程是规范的。”这种说法是否正确？解：本题考查算符优先分析法中句型的规约过程。在算符优先分析法中，每步自下而上分析、识别和归约的是当前句型的最左素短语，而不是严格地从左到右归约句柄。算符优先分析法只对算符优先文法进行，利用的是算符优先关系矩阵，该矩阵中只有终结符号间的优先关系，在归约过程中，利用算符优先关系矩阵无法找到句型中相应于产生式的句柄。因此，在算符优先分析法中，每次归约时，归约的是当前句型的最左素短语——所以产生式对归约没有起作用，因而算符优先分析不是规范规约。例如文法G[E]：E→E+T∣TT→T*F∣FF→P↑F∣PP→（E）∣i对句子i+i的归约过程如图6.5所示。从图6.5可见，算符优先分析中的归约不是规范规约。EEE+TP+PTFiiFii规范归约识别i+i的过程算符优先分析识别i+i的过程图6－5算符优先分析的归约8、★证明G[A]是LR(1)文法。G[A]:A→BA∣εB→Ab∣b解:本题考查“LR(1)文法”，涉及构造以LR（1）项目集为状态的识别活前缀的有穷自动机的方法。首先构造文法的托广文法，得到G[S]：S→A0A→BA1A→ε2B→aB3b→b4根据该托拓广文法构造以LR[1]项目集为状态的识别活动前缀的有穷自动机如图6.6所示。从图6.6中可知，所有的状态都不含有“移进－归约”、“归约－归约”冲突，因而该文法是LR(1)文法。图6.6有穷自动机BAabb[B→aB．，a/b/#]I2I1I5[A→BA．，#][A→B．A，#][A→．BA，#][A→．，#][B→．aB，a/b/#][B→．b，a/b/#]I4[B→b．，a/b/#]I3[B→a．B，a/b/#][B→．aB，a/b/#][B→．b，a/b/#]I6I0[S→．A，#][A→．BA，#][A→．，#][B→．aB，a/b/#][B→．b，a/b/#]ABabBa[S→A．，#]