编译原理第六章答案.doc

第6 章 自底向上优先分析
第1 题
已知文法G[S]为：
S→a|∧|(T)
T→T,S|S
(1) 计算G[S]的FIRSTVT 和LASTVT。
(2) 构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法。
(3) 计算G[S]的优先函数。
(4) 给出输入串(a,a)#和(a,(a,a))#的算符优先分析过程。
答案：
文法展开为：
S→a
S→∧
S→(T)
T→T,S
T→S
(1) FIRSTVT - LASTVT 表：

表中无多重人口所以是算符优先（OPG）文法。
友情提示：记得增加拓广文法 S`→#S#，所以# FIRSTVT(S)，LASTVT(S) #。
(3)对应的算符优先函数为：

Success!
对输入串（a,(a,a)）# 的算符优先分析过程为：

Success!
第2 题
已知文法G[S]为：
S→a|∧|(T)
T→T,S|S
(1) 给出(a,(a,a))和(a,a)的最右推导，和规范归约过程。
(2) 将(1)和题1 中的(4)进行比较给出算符优先归约和规范归约的区别。
答案：

(2)算符优先文法在归约过程中只考虑终结符之间的优先关系从而确定可归约串，而与
非终结符无关，只需知道把当前可归约串归约为某一个非终结符，不必知道该非终结符的名
字是什么，因此去掉了单非终结符的归约。
规范归约的可归约串是句柄，并且必须准确写出可归约串归约为哪个非终结符。
第３题：
有文法G[S]：
S􀃆V
V􀃆T|ViT
T􀃆F|T+F
F􀃆)V*|(
(1) 给出(+(i(的规范推导。
(2) 指出句型 F+Fi(的短语，句柄，素短语。
(3) G[S]是否为OPG？若是，给出(1)中句子的分析过程。

因为该文法是OP，同时任意两个终结符的优先关系唯一，所以该文法为OPG。
(+(i(的分析过程

第４题
文法G［S］为：
S→S;G｜G
G→G(T)｜H
H→a｜(S)
T→T+S｜S
（１） 构造G［S］的算符优先关系表，并判断G［S］是否为算符优先文法。
（２） 给出句型a(T+S);H;(S)的短语、句柄、素短语和最左素短语。
（３） 给出a;(a+a)和(a+a)的分析过程，说明它们是否为G［S］的句子。
（４） 给出（３）中输入串的最右推导，分别说明两输入串是否为G[S]的句子。
（５） 由（３）和（４）说明了算符优先分析的哪些缺点。
（６） 算符优先分析过程和规范归约过程都是最右推导的逆过程吗？
答案：
（1）构造文法G［S］的算符优先关系矩阵：