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］的算符优先关系矩阵：

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

（２）

（3）对输入串(a+a)＃的分析过程如下：

说明是它的句子。

（４）试用规范推导：

S? G?H?（S）由此往下S 不可能推导出a+a，所以 (a+a)不是G［S］的句子。

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

第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 如下图所示：