发布时间 : 星期一 文章编译原理期末复习题（含答案）更新完毕开始阅读2e03a82d647d27284b73518b
（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的有 。
+ + + c a b a +
a．ab+c+ b．abc++ c． d． e．a+b+c
3、在下面的 语法制导翻译中，采用拉链-回填技术。 a．赋值语句 b．goto语句 c．条件语句 d．循环语句 4、下列 中间代码形式有益于优化处理。 a．三元式 b．四元式 c．间接三元式 d．逆波兰表示法 e．树形表示法 5、在编译程序中安排中间代码生成的目的是 。 a．便于进行存储空间的组织 b．利于目标代码的优化
c．利于编译程序的移植 d．利于目标代码的移植 e．利于提高目标代码的质量 6、下面的中间代码形式中， 能正确表示算术表达式a+b*c。题） * +
a．ab+c*
b．abc*+
c．a+b*c
d． + c e． a *
7、三地址代码语句具体实现通常有 表示方法。 a．逆波兰表示 b．三元式 c．间接三元式 d．树形表示 e．四元式 解答
1、选a、c、d、e。
2、b、d的中间代码不能正确表示a+b+c，而e 不是中间代码：故选a、c。 3、凡涉及到跳转的语句都需要采用拉链——回填技术，故选 b、c、d。 4、选b、c。 5、选b、d。 6、选b、e。 7、选b、c、e。
三、填空题
1、中间代码有 等形式，生成中间代码主要是为了使 。 2、语法制导翻译既可以用来产生 代码，也可以用来产生 指令，甚至可用来对输入串进行 。
3、当源程序中的标号出现“先引用后定义”时，中间代码的转移地址须持 时才能确定，因而要进行 。
4、文法符号的属性有两种，一种称为 ，另一种称为 。
5、后缀式abc-/所代表的表达式是 ，表达式(a-b)*c可用后缀式 表示。 6、用一张 辅以 的办法来表示中间代码，这种表示法称为间接三元式。 解答
1、逆波兰记号、树形表示、三元式、四元式 目标代码的优化容易实现 2、中间 目标 解释执行 3、标号定义 回填 4、继承属性 综合属性 5、a/(b-c) ab-c* 6、间接码表 三元式表 四、综合题
1、给出下列表达式的逆波兰表示（后缀式）： ① a*(-b+c)
② (A∨B)∧(C∨┑D∧E)
2、写出算术表达式：A+B*(C-D)+E/(C-D)↑N的 ①四元式序列；②三元式序列；③间接三元式序列 解答1、
① ab@c+*;
② AB∨CD┑E∧∨∧