编译原理第六章答案.doc

第6 章 自底向上优先分析第1 题已知文法GS为：Sa|(T)TT,S|S(1) 计算GS的FIRSTVT 和LASTVT。(2) 构造GS的算符优先关系表并说明GS是否为算符优先文法。(3) 计算GS的优先函数。(4) 给出输入串(a,a)#和(a,(a,a)#的算符优先分析过程。答案：文法展开为：SaSS(T)TT,STS(1) FIRSTVT - LASTVT 表：表中无多重人口所以是算符优先（OPG）文法。友情提示：记得增加拓广文法 S#S#，所以# FIRSTVT(S)，LASTVT(S) #。(3)对应的算符优先函数为：Success!对输入串（a,(a,a)）# 的算符优先分析过程为：Success!第2 题已知文法GS为：Sa|(T)TT,S|S(1) 给出(a,(a,a)和(a,a)的最右推导，和规范归约过程。(2) 将(1)和题1 中的(4)进行比较给出算符优先归约和规范归约的区别。答案：(2)算符优先文法在归约过程中只考虑终结符之间的优先关系从而确定可归约串，而与非终结符无关，只需知道把当前可归约串归约为某一个非终结符，不必知道该非终结符的名字是什么，因此去掉了单非终结符的归约。规范归约的可归约串是句柄，并且必须准确写出可归约串归约为哪个非终结符。第题：有文法GS：SVVT|ViTTF|T+FF)V*|(1) 给出(+(i(的规范推导。(2) 指出句型 F+Fi(的短语，句柄，素短语。(3) GS是否为OPG？若是，给出(1)中句子的分析过程。因为该文法是OP，同时任意两个终结符的优先关系唯一，所以该文法为OPG。(+(i(的分析过程第题文法GS为：SS;GGGG(T)HHa(S)TT+SS（） 构造GS的算符优先关系表，并判断GS是否为算符优先文法。（） 给出句型a(T+S);H;(S)的短语、句柄、素短语和最左素短语。（） 给出a;(a+a)和(a+a)的分析过程，说明它们是否为GS的句子。（） 给出（）中输入串的最右推导，分别说明两输入串是否为GS的句子。（） 由（）和（）说明了算符优先分析的哪些缺点。（） 算符优先分析过程和规范归约过程都是最右推导的逆过程吗？答案：（1）构造文法GS的算符优先关系矩阵：