(完整版)编译原理[张素琴]第2版-答案-清华大学出版社

T→T+S|S

(1) 构造G[S]的算符优先关系表,并判断G[S]是否为算符优先文法。 (2) 给出句型a(T+S);H;(S)的短语、句柄、素短语和最左素短语。

(3) 给出a;(a+a)和(a+a)的分析过程,说明它们是否为G[S]的句子。

(4) 给出(3)中输入串的最右推导,分别说明两输入串是否为G[S]的句子。 (5) 由(3)和(4)说明了算符优先分析的哪些缺点。

(6) 算符优先分析过程和规范归约过程都是最右推导的逆过程吗? 答案:(1)构造文法G[S]的算符优先关系矩阵:

在上表中可看出终结符之间的优先关系是唯一的,或称G[S]的算符优先关系矩阵不含多重入口,因此,G[S]是一个算符优先文法。

(2)

(3)对输入串(a+a)#的分析过程如下:

说明是它的句子。

(4)试用规范推导:

S? G?H?(S)由此往下S 不可能推导出a+a,所以 (a+a)不是G[S]的句子。

(5)结果说明:由于算符优先分析法去掉了单非终结符之间的归约,尽管在分析过程中, 当决定是否为句柄时采取一些检查措施,但仍难完全避免把错误的句子得到正确的归约。 (6)算符优先分析过程不是最右推导的逆过程。规范归约过程是最右推导的逆过程。

第7 章 LR 分析

第1 题已知文法A→aAd|aAb|ε

判断该文法是否是SLR(1)文法,若是构造相应分析表,并对输入串ab#给出分析过程。 答案:文法:A→aAd|aAb|ε

拓广文法为G′,增加产生式S′→A 若产生式排序为: 0 S' →A 1 A →aAd 2 A →aAb 3 A →ε

由产生式知:

First (S' ) = {ε,a} First (A ) = {ε,a} Follow(S' ) = {#} Follow(A ) = {d,b,#}

G′的LR(0)项目集族及识别活前缀的DFA 如下图所示:

在I0 中:A →.aAd 和A →.aAb 为移进项目,A →.为归约项目,存在移进-归约冲突,因此所给文法不是LR(0)文法。

在I0、I2 中:Follow(A) ∩{a}= {d,b,#} ∩{a}=

所以在I0、I2 中的移进-归约冲突可以由Follow 集解决,所以G 是SLR(1)文法。 构造的SLR(1)分析表如下:题目1 的SLR(1)分析表

题目1 对输入串ab#的分析过程

分析成功,说明输入串ab 是文法的句子。

第2 题若有定义二进制数的文法如下: S→L·L|L L→LB|B B→0|1

(1) 试为该文法构造LR 分析表,并说明属哪类LR 分析表。 (2) 给出输入串101.110 的分析过程。 答案:文法: S→L.L|L L→LB|B B→0|1

拓广文法为G′,增加产生式S′→S 若产生式排序为: 0 S' →S 1 S →L.L 2 S →L 3 L →LB 4 L →B 5 B →0 6 B →1

由产生式知:

First (S' ) = {0,1} First (S ) = {0,1} First (L ) = {0,1} First (B ) = {0,1} Follow(S' ) = {#} Follow(S ) = {#}

Follow(L ) = {.,0,1,#} Follow(B ) = {.,0,1,#}

G′的LR(0)项目集族及识别活前缀的DFA 如下图所示:

在I2 中:B →.0 和 B →.1 为移进项目,S →L.为归约项目,存在移进-归约冲突,因此所给文法不是LR(0)文法。

在I2、I8 中:Follow(s) ∩{0,1}= { #} ∩{0,1}=

所以在I2 、I8 中的移进-归约冲突可以由Follow 集解决,所以G 是SLR(1)文法。 构造的SLR(1)分析表如下:题目2 的SLR(1)分析表

题目2 对输入串101.110#的分析过程

分析成功,说明输入串101.110 是题目2 文法的句子。 题目3考虑文法S-> A S | b

A -> S A | a

(1)列出这个文法的所有LR(0)项目

(2)按(1)列出的项目构造识别这个文法活前缀的NFA,把这个NFA 确定化为DFA,说明

这个DFA 的所有状态全体构成这个文法的LR(0)规范族 (3)这个文法是SLR 的吗?若是,构造出它的SLR 分析表 (4)这个文法是LALR 或LR(1)的吗? 答:

(1)令拓广文法G’为 (0) S’ -> S (1)S-> A S (2)S-> b (3)A -> S A (4)A -> a

其LR(0)项目:

(2) 识别这个文法活前缀的NFA 如上图所示: 确定化为DFA 如下图所示:

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4