编译原理分知识点习题自下而上语法分析.doc

1已知文法GS： SSaA|A AAbB|B BcSd|e请证实AacAbcBaAdbed是文法的一个句型，并写出该句型的所有短语、素短语以及句柄。解：本题考查“句型”、“短语”、“句柄”、“素短语”等概念。符号栈S关系输入串最左素短语S1 S2 S3 S4 S5 S6 S7R1 R2 R3 R4 R5 R6( a d b ) #(a d b ) #(d b ) #d#( Vd b ) #( Vdb ) #( Vd) #b#( V) #VdV#( V=) #(V)# V#接受因为存在从文法开始符号S到符号串AacAbcBaAdbed的推导过程（如图6.1中的语法树所示），所以符号串AacAbcBaAdbed是文法的句型。从图6.1中句型A1a1c1 A2b1c2Ba2 A3d1b2ed2的语法树可知，该句型的短语有：A1、B、Ba2 A3、c2Ba2 A3d1、A2b1c2Ba2 A3d1、e、A2b1c2Ba2 A3d1b2e、c1 A2b1c2Ba2 A3d1b2ed2、A1a1c1 A2b1c2Ba2 A3d1b2ed2该句型的素短语有：Ba2 A3、e该句型的句柄为：B2已知文法GS： S*A A0A1|*（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，*SS a1 AA1 B c1 S d2 A A b2 BA2 b1 B e c2 S d1 S a2 A3AB图6.1句型AacAbcBaAdbed的语法树（2） 构造文法G的优先关系矩阵。根据（1）中的FIRSTVT集和LASTVT集及算符优先关系构造算法对S*A，按算法第3种情形有：（*0），（*）对A0A1，按算法第1种情形有：（0|1）按算法第3种情形有：（0|0）,(0|1），(*|1),根据上述算符优先关系得到算符优先关系矩阵如表6.1所示。表中空白元素表示相应终结符号对之间没有算符优先关系，即它们不会在任何句型中相继出现。表6.1 文法的算符优先关系矩阵01*0|=|*|(3)对句子“*0*1#”分析过程如表6.2所示。表6.2 分析输入符号串“*0*1#”的过程符 号 栈S关 系输 入 串最左素短语S1 S2 S3 S4 S5 S6 S7R1 R2 R3 R4 R5#* 0 * 1 # *0 * 1 # * 0* 1 # * 01 #*# * 0 V=# *#0V1#*V# V#接受3试为下列优先矩阵构造优先函数。（1）S1S2S3S4S1S2S3S4(2) S1S2S3S4S1S2S3S4解：本题考查优先函数的构造方法。（1） 采用迭代法求优先函数，过程如下。（2） 初始状态：S1S2S3S4f1111g1111第1次迭代：S1S2S3S4f1122g1111第2次迭代：S1S2S3S4f1122g1111第2次迭代没有变化，所以第2次迭代结果便是优先函数。（3） 采用Bell有向图法构造优先函数(省略)。因为fs1可以到达的结点：gs3，gs4，fs4，gs3，gs2 fs2可以到达的结点：gs3，fs3，gs2，fs4，gs1 fs3可以到达的结点：gs2，fs3fs4可以到达的结点：gs1，gs3，fs3，gs2，fs4gs1可以到达的结点：fs3，fs4，gs2，gs1，gs3gs2可以到达的结点：fs3，gs2gs3可以到达的结点：fs4，fs3，gs1，gs3，gs2gs4可以到达的结点：无于是得到优先函数如表6.3所示。S1S2S3S4f7625g52514.试为文法GZ：ZA( )A(|Ai|B)Bi构造算符优先关系和优先函数。解：本题考查算符优先关系的构造方法和优先函数的构造方法。（1） 构造算符优先关系。首先构造FIRSTVT集和LASTVT集，根据定义有：FIRSTVT（Z）（， i， ）FIRSTVT（A）（， i， ）FIRSTVT（B）i和 LASTVT（Z）LASTVT（A）（， ）， iLASTVT（B）i按照构造算符优先关系的算法得到如下算符优先关系：“”的构造有产生式ZA（） 按算法第1种情形有： （ （） ）“”的构造文法没有满足“”的构造有产生式ZA（） 按算法第4种情形有： （ (（） ，（）（），（i（）有产生式AAi 按算法第4种情形有： （ （i）, ( )i） ，（ii）有产生式AB) 按算法第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：SSaS|SbS|cSd|eS|f（1）请证实这是一个二义文法；（2）给出什么样的约束条件，可构造出无冲突的LR分析表？请证实你的论点。解：本题考查“二义文法”及二义文法的LR分析法。（1）该文法是二义文法，因为它存在句子：fafbf该句子有两棵不同的语法树，如图6.3中的（a），（b）所示。 SSaSfSbSffSSbSfSaSff图6.3 句子fafbf的两棵语法树（2）构造文法的无冲突的LR分析表。首先对文法进行拓广得到SS0SSaS1SSbS2ScSd3SeS4Sf5在此基础上构造文法的识别活前缀的有穷自动机(省略)。因为：FOLLOW(S)=#，a，b，d构造文法的SLR(1)分析表如表6.6所示。表6.6 文法的SLR(1)分析表状态ACTIONGOTOabcdef#S0S2S3S411S5S6acc2S2S3S493S2S3S4104r5r5r5r575S2S3S476S2S3S487r1/S5r1/S6r1r18r2/S5r2/S6r2r29S5S6S1110r4/S5r4/S6r4r411r3r3r3r36.已知文法：GA：AAA|(A)|（1）该文法是LR(0)文法吗？为什么？（2）请构造该文法的以LR(0)项目集为状态的识别活前缀的DFA。（3）规定：出现“移进-归约”冲突时，移进优先；出现“归约-归约”冲突时，优先采用文法中出现在前的产生式进行归约。构造该文法的LR分析表。解：本题考查对二义性文法进行LR分析的方法。先构造出识别活前缀的有穷自动机，然后根据其中出现的冲突情况确定无二义规则的使用。首先构造拓广文法如下：0 AA1 AAA2 A(A)3 A（1）该文法不是LR(0)文法。因为文法存在有相同左部的产生式AAA和A产生式A在任何时候都只产生归约项目。当由项目A.A派生出新项目时，同时得到A.(A)和A.将出现“移进归约”冲突。所以该文法不是LR(0)文法。（2）构造该文法的以LR(0)项目集为状态的识别活前缀的DFA如图6.4所示。（3）因为出现“移进规约”冲突时，移进优先；出现“规约规约”冲突时，优先采用文法中出现在前的产生式进行规约，所以得到该文法的LR分析表如表6.7所示。A(I0AAAAAA(A)AI1A AAAAAAAA（A）AI2A(A)AAAA（A）AI3AA AAAAAAAA（A）AI4I5A(A) (A()A( A)AAAAAAA（A）AAA(A图6.4 文法的以LR(0)项目集为状态的识别活前缀的DFA表6.7 文法的LR分析表状态ACTIONGOTO()#A0S2r3r311S2r3acc22S2r3r333S2r1r144S2S5r355r2r2r27“算符优先分析采用“移进归约”技术，其规约过程是规范的。”这种说法是否正确？解：本题考查算符优先分析法中句型的规约过程。在算符优先分析法中，每步自下而上分析、识别和归约的是当前句型的最左素短语，而不是严格地从左到右归约句柄。算符优先分析法只对算符优先文法进行，利用的是算符优先关系矩阵，该矩阵中只有终结符号间的优先关系，在归约过程中，利用算符优先关系矩阵无法找到句型中相应于产生式的句柄。因此，在算符优先分析法中，每次归约时，归约的是当前句型的最左素短语所以产生式对归约没有起作用，因而算符优先分析不是规范规约。例如文法GE： EE+TT TT*FF FPFP P（E）i对句子i+i的归约过程如图6.5所示。从图6.5可见，算符优先分析中的归约不是规范规约。 E E E + T P + P T F i i F i i 规范归约识别i+i的过程 算符优先分析识别i+i的过程 图65 算符优先分析的归约8、证明GA是LR(1)文法。 GA:ABA BAbb解:本题考查“LR(1)文法”，涉及构造以LR（1）项目集为状态的识别活前缀的有穷自动机的方法。首先构造文法的托广文法，得到 GS：SA 0 ABA 1 A 2 BaB 3 bb 4根据该托拓广文法构造以LR1项目集为状态