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

《编译原理分知识点习题 自下而上语法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1．★已知文法G[S]：S→SaA

2、AA→AbB

3、BB→cSd

4、e请证实AacAbcBaAdbed是文法的一个句型，并写出该句型的所有短语、素短语以及句柄。解：本题考查“句型”、“短语”、“句柄”、“素短语”等概念。符号栈S关系输入串最左素短语S1S2S3S4S5S6S7R1R2R3R4R5R6＃<(adb)##<(db)#d#<(V)#b#<(V)#VdV#<(V=)##<(=V)>#(V)#V#接受因为存在从文法开始符号S到符号串AacAbcBaAdbed的推导过程

5、（如图6.1中的语法树所示），所以符号串AacAbcBaAdbed是文法的句型。从图6.1中句型A1a1c1A2b1c2Ba2A3d1b2ed2的语法树可知，该句型的短语有：A1、B、Ba2A3、c2Ba2A3d1、A2b1c2Ba2A3d1、e、A2b1c2Ba2A3d1b2e、c1A2b1c2Ba2A3d1b2ed2、A1a1c1A2b1c2Ba2A3d1b2ed2该句型的素短语有：Ba2A3、e该句型的句柄为：B2．★已知文法G[S]：S→*AA→0A1

6、*（1）求文法G的各非终结符号的FIRSTVT集和LASTVT集;（2）构造文法G的优先

7、关系矩阵，并判断该文法是否是算符优先文法；（3）分析句子*0*1，并写出分析过程。解：本题考查算符优先分析法中的有关知识：非终结符号的FIRSTVT集和LASTVT集的求法、算符优先关系的构造、算符优先文法的定义、算符优先分析过程等。（1）求文法G的各非终结符号的FIRSTVT集和LASTVT集。根据非终结符号的FIRSTVT集定义得到FIRSTVT（S）＝｛*｝FIRSTVT（S）＝｛0，*｝根据非终结符号的LASTVT集定义得到LASTVT（S）＝｛*，1｝LASTVT（S）＝｛1，*｝SSa1AA1Bc1Sd2AAb2BA2b1Bec2Sd1

8、Sa2A3AB图6.1句型AacAbcBaAdbed的语法树（1）构造文法G的优先关系矩阵。根据（1）中的FIRSTVT集和LASTVT集及算符优先关系构造算法对S→*A，按算法第3种情形有：（*<0），（*<*）对A→0A1，按算法第1种情形有：（0

9、＝1）按算法第3种情形有：（0

10、<0）,(0

11、<*)按算法第4种情形有：（1

12、>1），(*

13、>1),根据上述算符优先关系得到算符优先关系矩阵如表6.1所示。表中空白元素表示相应终结符号对之间没有算符优先关系，即它们不会在任何句型中相继出现。表6.1文法的算符优先关系矩阵01*0

14、<

15、=

16、<1

17、>*

18、

19、<

20、>

21、<(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±±S3>>S4>>(2)S1S2S3S4S1>>S2>S3<±

22、4f1111g1111第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可以到达的结点

23、：fs4，fs3，gs1，gs3，gs2gs4可以到达的结点：无于是得到优先函数如表6.3所示。S1S2S3S4f7625g52514.试为文法G[Z]：Z→A()A→(

24、Ai

25、B)B→i构造算符优先关系和优先函数。解：本题考查算符优先关系的构造方法和优先函数的构造方法。（1）构造算符优先关系。首先构造FIRSTVT集和LASTVT集，根据定义有：FIRSTVT（Z）＝｛（，i，）｝FIRSTVT（A）＝｛（，i，）｝FIRSTVT（B）＝｛i｝和LASTVT（Z）＝｛｝｝LASTVT（A）＝｛（，），i｝LASTVT（B）＝｛i｝按照构造算符优先

26、关系的算法得到如下算符优先关系：“＝”的构造∵有产生式Z→A（）∴按算法第1种情形有：（（＝））“<”的构造文法没有满足“