第一章 引论
1．高级程序设计语言的翻译主要有两种方式： 和 ，二
者的根本区别在于 。
答：解释 编译 是否生成目标程序。
2．编译程序决大多数时间是花在 方面。 A 词法分析 B 语法分析 C 语义分析 D 代码生成 E 中间代码生成 F 代码优化 G 表格管理 H 出错管理 答：G
3．什么是遍？是否任何一种高级语言都能通过一遍扫描完成编译？ 答：
遍是对源程序或源程序的中间表示从头到尾地扫描一次，并做相关的处理工作，生成新的源程序的中间形式或目标文件。
并非所有的语言都能通过一遍扫描完成编译。如果该语言结构复杂，那么必须通过多次扫描才能真正完成编译工作。影响编译遍的次数的主要因素有：? 源语言；? 机器（目标机）；? 编译方法。
第二章 高级语言及其语法描述
1．巴科斯—瑙尔范式（EBNF）是一种广泛采用的 工具。
A 描述规则 B 描述语言 C 描述文法 D 描述句子 答： C
2．由文法的开始符号经0步或多步推导产生的文法符号序列是 。 A 短语 B 句柄 C 句型 D 句子 答： C
2m+1m+1 2m+1m+2
3．请给出描述语言L={ab|m>=0}∪{ab|m>=0}的文法。
2mm 2mm
解答：将语言句子的描述稍做变形，得：aabb和aabbb
于是，得到文法如下：
G[Z]:Z→aaZb|ab|bb 4.文法G[S]:
S→aSPQ|abQ
QP→PQ bP→bb bQ→bc cQ→cc
它是乔姆斯基哪一型文法？它生成的语言是什么？
答：从规则形式上可以看出，文法G是乔姆斯基1型文法，即上下文有关文法。
nnn
它生成的语言是L={abc|n>=1}。
第三章 词法分析
1. 不是NFA的成分。
A 有穷字母表 B初始状态集合 C 终止状态集合 D 有限状态集合 答：B。
2．构造一个DFA，其输入字母表是{0，1}，它能接受以0开始以1结尾的所有序列，要求写出正规式。 答：r=0(0|1)*1 NFA 为：
1
0，1 ε ε
x 0 1 2 3 1 y
确定化
I I0 I1 {x } {1,2，3} Φ {1,2,3} {2,3} {2,3,y} {2,3} {2,3 } {2,3,y} {2,3,y} {2,3} {2,3,y}
重命名
0 1 1+ 2 Φ 2 3 4 3 3 4 4- 3 4 确定化后的DFA如图： 0 3
0
1 0 2 0 1
1 1 化简：{1，2,3} {4}
4 {1，2,3}0={2,3} {2，3}1={4} {1}1=Φ 分两组 {2，3} {1}
{2,3}不可再分 留2删3 得化简后的DFA为：
0 1 0 1
1 2 4 0
第四章 语法分析——自上而下分析
1．自顶向下语法分析方法会遇到的主要问题有 和 。
答：左递归 回溯
2. LL（1）分析法中，第一个L的含义是 ，第二个L的含义是 ， “1”的含义是 。
答：从左到右扫描输入串 最左推导 分析时每一步只需向前查看一个符号
2
3. 下列文法是左递归文法，试消除其左递归。
G[S]：
S→ SaA| bB A → aB | c B → Bb | d 解答：S→bB S’
S’→aA S’|ε A→aB|c B→dB’
B’→bB’|ε 4.考虑下面的文法G：
S→ a|∧| (T) T→T,S|S
⑴ 消去G的左递归；
⑵ 经改写后的文法是否是LL（1）的？给出它的预测分析表。 解答：
⑴ 按照T，S 的顺序消除左递归，得到文法：
,
G[S]： S→ a|∧| (T)
,
T→ST
,,
T →,S T| ε
⑵ 首先计算每个非终结符的FIRST集合和FOLLOW集合： FIRST（S）={a, ∧,(} FOLLOW(S)={,, ),#} FIRST（T）={a, ∧,(} FOLLOW(T)={ )}
,,
FIRST（T）={,,ε} FOLLOW(T)={ )} 构造预测分析表如下表所示：
S T T ,A S→ a T→ST ,∧ S→∧ T→ST ,( S→(T) T→ST ,,) T →ε ,, T →,S T ,# 从表中可以看出没有多重入口，所以改造后的文法是LL（1）文法。
第五章 语法分析——自下而上分析
1．自下而上语法分析的基本思想是：从待输入的符号串出发，利用文法的产生式步步向上 ，试图 到文法的 。 答：直接归约，归约 开始符号
2．规范归约每次归约的是当前句型的 ，算符优先文法每次归约的是当前句型的 ，二者都是不断移进输入符号，直到符号栈的栈顶出现 的尾，再向前找到 的头，然后归约。 答： 句柄 最左素短语 可归约串 可归约串 3．对下列文法G[ S′]：（1）计算文法中每个非终结符的FIRSTVT和LASTVT集合；
（2）构造文法的算符优先关系表；（3）给出输入串cadbc的算符优先分析过程。 文法G[S]： S′→ #S#
S → SaF | F
3
F → FbP | P P → c | d
解答： (1)
FIRSTVT(S)={a,b,c,d} LASTVT(S)={a,b,c,d} FIRSTVT(F)={b,c,d} LASTVT(F)={b,c,d} FIRSTVT(P)={c,d} LASTVT(P)={c,d} FIRSTVT(S’)={ # } LASTVT(S’)= {#}
(2) 文法G的优先关系表 a b c d # a b > < < < > > < < < > c > > d > > > # c < < < < =
⑶分析过程
步骤 符号栈 输入串 动作
0 # cadbc# # 1 #c adbc# c>a,归约P→c 2 #P adbc# # 4 #Pad bc# d>b,归约P→d 5 #PaP bc# a 8 #PaPbP # b>#,规约F→FbP 9 #PaF # a>#,规约S→SaF 10 #S # 接受 4．已知文法 G[A]： A→(A)|a (1)请构造该文法的以LR(0)项日集为状态的识别活前缀的DFA。 (2)构造该文法的LR(0)分析表，并回答该文法是LR(O)文法吗? (3)构造该文法的SLR(1)分析表，并回答该文法是SLR(1)文法吗？(4)构造该文法的以LR(1)项目集为状态的识别活前缀的DFA。 (5)构造该文法的LR（1）分析表。 (6)构造该文法的LALR(1)分析表。 解答： (1)首先构造拓广文法如下： 0 A’→A 4 l A→(A) 2 A→a 构造该文法的以LR(0)项日集为状态的识别活前缀的DFA如图所示 文法的以LR[0]项目集为状态的识别活前缀的DFA (2) 构造文法的LR(0)分析表如表所示。 表中无多重定义，所以该文法是LR(0)文法。 文法的LR(0)分析表 (3) 因为FOLLOW(A)＝{)，#}，所以得到文法的SLR(1)分析表如表所示。表中无 多重定义，所以该文法是SLR(1)文法。 文法的SLR(l)分析表 5