《编译原理》考试试卷A
适用专业：考试日期：闭卷
所需时间：120分钟总分：100分
一、填空题：（每空1分，共10分）
1.解释系统与编译系统的区别在于和。
2.在编译过程中始终伴随着管理和出错处理过程。
3.语法分析的方法为和两大类。
4.LL(1)文法中不能有和。
5.词法分析器中单词的描述工具是 ,单词的识别工具。
6.算符优先语法分析，在符号栈栈顶出现时，进行规约处理。
二、单选题（每小题2分，共10分）
1.词法分析器的加工对象是（）
A.中间代码
B.单词
C.源程序
D.元程序
2.同正则表达式a*b*等价的文法是（）
A. G1:S→aS|bS|ε
B. G2: S→aSb|ε
C. G3:S→aS|Sb|ε
D. G4: S→abS|ε
3.文法G[A]:A→bH H→BA B→Ab H→a 不是（）
A. 2型文法
B. 3型文法
C. 0型文法
D.1型文法
4.算符优先分析每次都是对（）进行规约。
A.短语
B.最左素短语
C.素短语
D.句柄
5.( )不是DFA的成分。
A.有穷字母表
B. 初始状态集合
C.终止状态集合
D.有限状态集合
三、问答题（第1,5小题每题15分，其余每小题10分，共80分）
1. （15分）解释下列术语：
（1）编译程序
（2）句柄
（3）上下文无关文法
2.编译程序主要有哪些构成成分？（10分）
3.给出描述语言L={a n b2n c m|n,m≥0}的cfg。
（10分）
4.（10分）将下图中的DFA M最小化。
5. （15分）判断文法G[S]:
S→aH
H→aMd|d
M→Ab|ε
A→aM|e
是否为LL(1)文法？给出判断过程。
6. （10分）改写文法G[E]：
E → E+T|T
T →T*F|F
F →(E)| a
为无左递归文法。
7. （10分）已知文法G[S]为：
S→V
V→T|ViT
T→F|T+F
F→)V*|(
请指出句型(+(i( 规范推到，并指出句型F+Fi( 中的短语、句柄和素短语。
《编译原理》考试试卷A参考答案
适用专业：考试日期：闭卷
所需时间：120分钟总分：100分
一、填空题：（每空1分，共10分）
1. 边翻译边执行和不生成目标代码。
2. 表格。
3. 自上而下和自底向上。
4. 左递归和回溯。
5. 正则式或正规文法, 有穷自动机。
6. 最左素短语。
二、单选题（每小题2分，共10分）
1-5：CCBBB
三、问答题（每小题10分，共80分）
1.
（1）编译程序
一个编译程序就是一个语言翻译程序，它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的程序
（2）句柄
一个句型的最左直接短语称为该句型的句柄
（3）上下文无关文法
对任一产生式α→β，α为非终结符，β为终结符和非终结符组成的符号串。
2.
编译程序一般由词法分析程序，语法分析程序，语义分析程序，中间代码生成程序，目标代码生成程序，代码优化程序，符号表管理程序和错误处理程序等成分构成。
3.
G[S]:
S→AB
A→aAbb|ε
B→cB|ε
4.
初始划分：I1={1,2,3,4},I2={5,6,7}
因为
move(I1,a)={6,1,7,4}→move({1,2},a)={6,7} move({3,4},a)={1,4}
所以第二次划分：I1={1,2},I2={3,4},I3={5,6,7}
又因为
move({3,4},a)={1,4}→ move({3},a)={1}, move({4},a)={4}
所以，将{3,4}划分为集合：{3}，{4}
move({5,6,7},a)={4,7}→move({5},a)={7}, move({6,7},a)={4} 所以将集合{5,6,7}划分为：{5}，{6,7}
最终划分结果：I1={1,2},I2={3},I3={4},I4={5},I5={6,7}
产生式的Select集交集都为空集，所以该文法是LL(1)文法。
6. G[ E]: (1) E →TE’ (2) E’ →+TE’
(3) E’ →ε (4) T →FT’
(5) T’ →*FT’ (6) T’ →ε
(7) F → (E) (8) F →a
7.
S → V → ViT→ViF→Vi(→Ti(→T+Fi(→T+(i(→F+(i(→(+(i( 句型F+Fi(
短语：F,F+F,(,F+Fi( 句柄：F
素短语：F+F，（。