FIRST(+E)∩FOLLOW(B)={+}∩{]}= ?
而文法的其他产生式都只有一个不为ε的右部，所以文法G′[V]是LL(1)文法。 5、已知文法： G[A]： A→aAa|ε
（1）该文法是LL（1）文法吗？为什么？
（2）若采用LL（1）方法进行语法分析，如何得到该文法的LL（1）分析表？ （3）若输入符号串“aaaa”，请给出语法分析过程。 解答：（1）因为产生式A→aAa|ε 有空产生式右部，而 FOLLOW(A)={#}∪FIRST(a)={a, #}
造成 FIRST(A)∩FOLLOW(A)={A, ε}∩{a, #}≠? 所以该文法不是LL（1）文法。
（2）若采用LL（1）方法进行语法分析，必须修改该文法。 因该文法产生偶数（可以为0）个a，所以得到文法 G′[A]： A→aaA|ε
此时对产生式A→aaA|ε， 有 FOLLOW(A)={#}∪FOLLOW(A)={#}，因而 FIRST(A)∩FOLLOW(A)={a, ε}∩{#}=? 所以文法G′[A]是LL（1）文法，按LL（1）分析表构造算法构造该文法的LL（1）分析表如表4-3-3所示。
表4-3-3 文法G′[A]的LL(1)分析表 A （3）若采用LL(1)方法进行语法分析，对符号串“aaaa”的分析过程如表4-3-4所示。
表4-3-4 对符号串“aaaa”的分析过程 步骤 1 2 3 4 5 6 7 8
分析栈 #A #A a a #A a #A #A a a #A a #A # 输入串 a a a a # a a a a # a a a # a a # a a # a# # # 产生式/动作 A→aaA 匹配 匹配 A→aaA 匹配 匹配 A→ε 接受 A A→aaA # A→ε 第七节 习题
设有文法G[S]为： S→a|b|(A)
A→SdA|S
（1） 完成下列算符优先关系表，见表5-7-1，并判断G[S]是否为算符优先文法。
表5-7-1 算符优先关系表
a b ( ) d # a ? ? b ? ? ( ? ? ) ? ? ? ? d # ? ? ? ?
（2）给出句型（SdSdS）的短语、简单短语、句柄、素短语和最左素短语。 （3）给出输入串（adb）#的分析过程。 解答：
（1）先求文法G[S]的FIRSTVT集和LASTVT集：
由S→a|b|(A)得：FIRSTVT(S)={a,b,( );
由A→Sd?得：FIRSTVT(A)={d};又由A→S?得：FIRSTVT(S) ? FIRSTVT(A)，即FIRSTVT(A)={d,a,b,(};
由S→a|b|(A)得；LASTVT(S)={a,b,}};
由A→?dA得：LASTVT(A)={d},又由A→S得：LASTVT(S) ? LASTVT(A)，即LASTVT(A)={d,a,b,)}。
构造优先关系表方法如下：
① 对P→?ab?，或P→?aQb?，有a?b; ② 对P→?aR?，而b∈FIRSTVT(R)，有a?b; ③ 对P→?Rb?，而a∈FIRSTVT(R)，有a?b。 由此得到：
① 由S→(A)得：(?);
② 由S→(A?得：(?FIRSTVT(A)，即：(?d,(?a ,(?b,(?(;由A→?dA得：d?FIRSTVT(A)， 即：d?d,d?a,d?b,d?(;
③ 由S→A)得，LASTVT(A)?)，即：d?),a?),b?),)?);由A→Sd?得：LASTVT(S)?d，即：a?d,b?d,)?d;
此外，由#S#得：#?#；
由#?FIRSTVT(S)得：#?a,#?b,#?(；脂由LASTVT(S)?#得：d?#,a?#,b?#,)?#。
最后得到算符优先关系表，见表5-7-2。
表5-7-2 算符优先关系表
a b ( ) d # a ? ? ? b ? ? ? ( ? ? ? ) ? ? ? ? ? d ? ? ? ? # ? ? ? ? ?
由表5-7-2可以看出，任何两个终结符之间至少只满足?、?、?三种优先关系之一，故G[S]为算符优先文法。
（2）为求出句型（SdSdS）的短语、简单短语、句柄，我们先画出该句型对应的语法树，如图5-7-3所示。由图5-7-3得到： 短语：S，SdS，SdSdS，（SdSdS）
S 简单短语（即直接短语）：S 句柄（即最左直接短语）：S
素短语：SdS，它同时也是该句型的最左素短语。
A （ ） S A d
S
d A S
（3）输入串（adb）#的分析过程见表5-7-4
表5-7-4 输入串（adb）#的分析过程 符号栈 # #（ #（a #（S #（Sd #（Sdb #（SdS #（SdA #（A #（A） #S
输入串 (adb)# adb)# db)# db)# b)# )# )# )# )# # # 说明 移进 移进 用S→a归约 移进 移进 用S→b归约 用A→S归约 用A→SdA归约 移进 用S→（A）归约 分析成功 第四节 习题
一、单项选择题
1、若a为终结符，则A→α·aβ为 项目 a.归约 b.移进 c.接受 d.待约
2、若项目集Ik含有A→α·，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α·”动作的一定是 。
a.LALR文法 b.LR（0）文法 c.LR（1）文法 d.SLR（1）文法 3、就文法的描述能力来说，有 。
a. SLR（1）?LR（0） b. LR（1）?LR（0）c. SLR（1）?LR（1）d.无二义文法?LR（1） 4、在LR（0）的ACTION子表中，如果某一行中存在标记“rj”的栏，则 。 a.该行必定填满rj b.该行未填满rj
c.其他行也有rj d.goto子表中也有rj
5、一个 指明了在分析过程中的某时刻所能看到产生式多大一部分。 a.活前缀 b.前缀 c.项目 d.项目集 解答：
1、A→α·称为归约项目，对文法开始符S′的归约项目，如S′→α·称为接受项目，A→α·aβ（a为终结符）称为移进项目。在此选b.
2、当用产生式A→α归约时，LR（0）无论面临什么输入符号都进行归约；SLR（1）则仅当面临的输入符号a∈FOLLOW(A)时进行归约；LR（1）则当在把α归约为A的规范句型的前缀βAa前提下，当α后跟终结符a时，才进行归约；因此选d。
3、由于LR（0）?SLR（1）? LR（1）?无二义文法，故选c。 4、选a。 5、选c。 二、多项选择题
1、一个LR分析器包括 。
a.一个总控程序 b.一个项目集 c.一个活前缀
d.一张分析表 e.一个分析栈
2、LR分析器核心部分是一张分析表，该表包括 等子表。 a.LL(1)分析 b.优先关系 c.GOTO d.LR e.ACTION
3、每一项ACTION[S，a]所规定的动作包括 。
a.移进 b.比较 c.接受 d.归约 e.报错 4、对LR分析表的构造，有可能存在 动作冲突。
a.移进 b.归约 c.移进/归约 d.移进/移进 e.归约/归约 5、就文法的描述能力来说，有 。 a. SLR（1）?LR（1） b. LR（1）?SLR（1） c. LR（0）?LR（1）
d. LR（1）?无二义文法 e. SLR（1）?无二义文法 6、对LR分析器来说，存在 等分析表的构造方法。 a.LALR b.LR（0） c.SLR（1） d.SLR（0） e.LR（1） 7、自上而下的语法分析方法有 。 a.算符优先分析法 b.LL（1）分析法 c.SLR（1）分析法
d.LR（0）分析法 e.LALR（1）分析法
解答：
1、一个LR分析器包括一个总控程序和一张分析表，选a、d。
2、选c、e。
3、选a、c、d、e。
4、在LR分析表的构造中有可能存在“移进”/“归约”和“归约”/“归约”冲突；故选c、e。 5、选a、b、c、d、e。 6、选a、b、c、e。 7、选a、c、d、e。 三、填空题
1、对于一个文法，如果能够构造 。使得它的 均是唯一确定的，则称该文法为LR文法。 2、字的前缀是指该字的 。
3、活前缀是指 的一个前缀，这种前缀不含 之后的任何符号。
4、在LR分析过程中，只要 的已扫描部分保持可归约成一个 ，则扫描过的部分正确。 5、将识别 的NFA确定化，使其成为以 为状态的DFA，这个DFA就是建立 的基础。
6、A→α·称为 项目；对文法开始符S′→α·为 项目；若a为终结符，则称A→α·aβ为 项目；若B为非终结符，则称A→α·aβ为 项目。 7、LR（0）分析法的名字中“L”表示 ，“R”表示 ，“0”表示 。 解答：
1、一张分析表 每个入口
2、任意首部
3、规范句型 句柄 4、输入串 活前缀
5、活前缀 项目集合 LR分析算法 6、归约 接受 移进 待约
7、自左至右分析 采用最右推导的逆过程即最左归约 向右查看0个字符 四、综合题
1、对于文法G[S]： S→AS|b A→SA|a （1）列出所有LR（0）项目
（2）列出构成文法LR（0）项目集规范族。 解答：
首先将文法G拓广为G[S′]： S′→S S→AS|b A→SA|a
（1）文法G[S′]的LR（0）项目是： 1、S′→·S 5、S→AS· 9、A→S·A 2、S′→S· 6、S→·b 10、A→SA· 3、S→·AS 7、S→b· 11、A→·a 4、S→A·S 8、A→·SA 12、A→a·
2、列出构成文法LR（0）项目集规范族。
用ε-CLOSURE（闭包）办法构造文法G′的LR（0）项目集规范族如下： I0：1、S′→·S I3： 9、A→S·A I6：12、A→a· 3、S→·AS 8、A→·SA I7：7、S→b· 8、A→·SA 3、S→·AS
11、A→·a 6、S→·b 6、S→·b 11、A→·a
I1：2、S′→S· I4：10、A→SA· 9、A→S·A 4、S→A·S 8、A→·SA 3、S→·AS 11、A→·a 6、S→·b 3、S→·AS 8、A→·SA 6、S→·b 11、A→·a I2：4、S→A·S I5： 5、S→AS· 3、S→·AS 9、A→S·A 6、S→·b 8、A→·SA 8、A→·SA 11、A→·a 11、A→·a 3、S→·AS 6、S→·b
注意：I1中的S′→S·和A→·SA是由状态I0中的1和3读入一个S字符后得到的下一个项目；，而I4中的A→SA和A→A·S则是由I3中的9和3读入一个A字符后得到的下一个项目；I5中的S→AS·和A→S·A 则是由I4中的4和8读入一个S字符后得到的下一个项目。
状态全体构成了文法G′的LR（0）规范族。
第八节 习题
一、单项选择题
1、中间代码生成所依据的是 。
a.语法规则 b.词法规则 c.语义规则 d.等价变换规则 2、四元式之间的联系是通过 实现的。 a.指示器 b.临时变量 c.符号表 d.程序变量 3、后缀式ab+cd+/可用表达式 来表示。
a.a+b/c+d b.(a+b)/(c+d) c.a+b/(c+d) d.a+b+c/d 4、表达式（┓A∨B）∧（C∨D）的逆波兰表示为 。 a. ┓AB∨∧CD∨ b. A┓B∨CD∨∧
c. AB∨┓CD∨∧
+ + 5、中间代码的树型表示A B + C D 所对应的表达式为 。
d. A┓B∨∧CD∨
a.A+B+C+D b.A+(B+C)+D c.(A+B)+C+D d.(A+B)+(C+D) 6、四元式表示法的优点为 。
a.不便于优化处理，但便于表的更动 b.不便于优化处理，但节省存储空间 c.便于优化处理，也便于表的更动 d.便于表的更动，也节省存储空间 7、终结符具有 属性。
a.传递 b.继承 c.抽象 d.综合
解答
1、选c。
2、四元式之间的联系是通过临时变量实现的，故选b。 3、选b。 4、选b。 5、选d。
6、四元式表示法的优点与间接三元式相同，故选c。 7、选d。 二、多顶选择题
1、中间代码主要有 。 a．四元式 b．二元式 c．三元式 d．后缀式 e．间接三元式 2、下面中间代码形式中，能正确表示算术表达式a+b+c的有 。