河南科技大学电信科卷A
一． 填空题（每空2分，共20分）
1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为（1） 和 （2） 。
2. 规范规约是最（3）规约。
3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4） 、语义分析与中间代码生成，代码优化及（5） 。另外还有（6）和出错处理。
4．表达式x+y*z/(a+b)的后缀式为 （7） 。 5．文法符号的属性有综合属性和 （8）。
6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i ，j]的地址计算公式为（9）。 7．局部优化是局限于一个（10）范围内的一种优化。 二． 选择题（1-6为单选题，7-8为多选题，每问2分，共20分）
1. 一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，一个（ ），以及一组（ ）。 A ． 字符串 B ． 产生式 C ． 开始符号 D ． 文法
2.程序的基本块是指（ ）。
A ． 一个子程序
B ． 一个仅有一个入口和一个出口的语句
C ． 一个没有嵌套的程序段
D ． 一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（ ）分析方法。 A ． 自左向右 B ． 自顶向下 C ． 自底向上 D ． 自右向左 4．在通常的语法分析方法中，（ ）特别适用于表达式的分析。 A ． 算符优先分析法 B ． LR 分析法 C ． 递归下降分析法 D ． LL （1）分析法 5．经过编译所得到的目标程序是（ ）。
A ． 四元式序列
B ． 间接三元式序列
C ． 二元式序列
D ． 机器语言程序或汇编语言程序 6． 一个文法所描述的语言是（ ）；描述一个语言的文法是（ ）。
A．唯一的 B．不唯一的 C．可能唯一，也可能不唯一
7．如果在文法G中存在一个句子，当其满足下列条件（）之一时，则称该文法是二义文法。
A．其最左推导和最右推导相同 B．该句子有两个不同的最左推导
C．该句子有两个不同的最右推导 D．该句子有两棵不同的语法树
E．该句子对应的语法树唯一
8．下面（）语法制导翻译中，采用拉链—回填技术。
A. 赋值语句
B. 布尔表达式的计算
C. 条件语句
D. 循环语句
1．（共15分）已知文法G[E]:
E→ETE|（E）|i
T→*|+
（1）将文法G改造成LL（1）文法；（5分）
（2）构造文法G中每个非终结符的FIRST集合及FOLLOW集合；（5分）
（3）构造LL（1）分析表。（5分）
2．（共12分）给定文法G[S]：S→S(S)|ε
（1）给出句子(()())()()的规范推导过程；（4分）
（2）指出每步推导所得句型的句柄；（4分）
（3）画出该句子的语法推导树。（4分）
3．（共8分）在一个移入-规约分析过程中采用以下的语法制导翻译模式，在按一个产生式规约时，立即执行括号中的动作。
A→aB {print “0”；}
A→c {print “1”；}
B→Ab {print “2”；}
（1）当分析器的输入为aacbb时，打印的字符串是什么？（3分）
（2）写出分析过程。（5分）
4．（10分）翻译循环语句 while (a
参考以下部分翻译模式：
(1) S→if E then M S1 {backpatch(E.truelist,M.quad);
S.nextlist:=merge(E.falselist,S1 .nextlist)}
(2) S→while M1 E do M2 S1 {backpatch(S1.nextlist,M1,.quad);
backpatch(E.truelist,M2,.quad);
S.nextlist:=E.falselist
emit (‘j,-,-,’M1 .quad)}
(3) S→A {S.nextlist:=makelist()}
(4) L→S {L.nextlist:=S.nextlist}
(5) M→ε{M.quad:=nextquad}
(6) E→id1 relop id2 {E.truelist:=makelist(nextquad);
e.falselist:=makelist(nextquad+1);
emit(‘j’relop.op,‘,’id1.place ‘,’id2.place‘,’‘0’);
emit(‘j,-,-,0’)}
(7) S→L:=E {emit(:=,E.place,-,L.place)}
(8) E→E1+E2 {E.place:=newtemp;
emit(+,E1.place,E2.place,E.place,)}
5．（共15分）设有表格构造文法G[S]：
S→a|∧|(T)
T→T,S|S
(1)计算文法G[S]的FIRSTVT集和LASTVT集。（5分）
(2)构造G[S]的优先关系表，并判断G[S]是否为算符优先文法。（5分）
(3)计算G[S]的优先函数。（5分）
1. 设有文法G[I]：I→I1|I0|Ia|Ic|a|b|c
下列符号串中是该文法句子的有（）。
① ab0 ② a0c01 ③ aaa ④ bc10
可选项有：
A．① B．②③④ C．③④ D．①②③④
2.程序的基本块是指（）。
A．一个子程序 B．一个仅有一个入口和一个出口的语句
C．一个没有嵌套的程序段 D．一组顺序执行的程序段，仅有一个入口和一个出口
3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（）分析方法。
A．自左向右 B．自顶向下 C．自底向上 D．自右向左
4．经过编译所得到的目标程序是（）。
A．四元式序列 B．间接三元式序列
C．二元式序列 D．机器语言程序或汇编语言程序
5．运行阶段的存储组织与管理的目的是（）。
①提高编译程序的运行速度②节省编译程序的存储空间
③提高目标程序的运行速度④为运行阶段的存储分配做准备
可选项有：
A. ①②
B. ②③
C. ③④
D. ④②
2. （10分）已知文法G[S]:
S→aBc|bAB
A→aAb|b
B→b|ε
（4）构造其LL（1）分析表；
（5）判断符号串baabbb是否为该文法的句子（写出含有符号栈、输入串和规则的分析过程）。
3. (10分) 已知文法G为：
E→E+T|T
T→T*P|P
P→i
（1）构造该文法的优先关系表（不考虑语句括号#），并指出此文法是否为算符优先文法。
（2）构造文法G的优先函数表。
4．（8分）在一个移入-规约分析过程中采用以下的语法制导翻译模式，在按一个产生式规约时，立即执行括号中的动作。
S→bAb {print “1”}
A→(B {print “2”}
A→a {print “3”}
B→Aa) {print “4”}
（3）当输入序列为b(((aa)a)a)b时，打印的字符串是什么？
（4）写出移入-规约分析过程。
5．（12分）翻译循环语句 while (x>y) do if (a=b) then x:=2*y+a 。要求：给出加注释的分析树、三地址码序列及相应的四元式序列。
参考以下部分翻译模式：
(1) S→if E then M S1 {backpatch(E.truelist,M.quad);
S.nextlist:=merge(E.falselist,S1 .nextlist)}
(2) S→while M1 E do M2 S1 {backpatch(S1.nextlist,M1,.quad);
backpatch(E.truelist,M2,.quad);
S.nextlist:=E.falselist
emit (‘j,-,-,’M1 .quad)}
(3) S→A {S.nextlist:=makelist()}
(4) L→S {L.nextlist:=S.nextlist}
(5) M→ε{M.quad:=nextquad}
(6) E→id1 relop id2 {E.truelist:=makelist(nextquad);
e.falselist:=makelist(nextquad+1);
emit(‘j’relop.op,‘,’id1.place ‘,’id2.place‘,’‘0’);
emit(‘j,-,-,0’)}
(7) S→L:=E {emit(:=,E.place,-,L.place)}
(8) E→E1+E2 {E.place:=newtemp;
emit(+,E1.place,E2.place,E.place,)}
6.(8分) Generate assembly code for the following sequence assuming that x,y and z are in memory
locations(noticing only two registers R1 and R2).
S=0
I=0
L1: if x>y goto L2
Z=s+a[i]
I=i+1
Goto L1
L2:
7． (6分) Give out the all basic blocks of the following program fragment and construct the relevant flow graph(DAG).
read C
A=0
B=1
L4: A=A+B
if B>C goto L2
B=B+1
goto L4
L2: write A
8.(8分)Translate the assignment statement b[i]=b*c-b*d into
(1) A syntax tree.
(2)Three address instructions.
答案：：
(1)栈式动态存储分配
(2)堆式动态存储分配
(3)左
(4)语法分析
(5)目标代码生成
(6)表格管理
(7)xyz*ab+/+
(8)继承属性
(9)a+(i-1)*20+j-1
(10)基本块
一、选择题（每问2分，共20分）
1.C B
2.D
3.B
4.A
5.D
6.A,C
7.BCD,选对一个得1分且不超过满分，选错一个扣一分，扣完为止。
8.BCD，选对一个得1分且不超过满分，选错一个扣一分，扣完为止。
二、解答题
1．（1）文法存在左递归，消除左递归后的文法为：
E→(E)E’|i E’（2分）
E’→TEE’|ε（2分）
T→*|+ （1分）
（2）(5分)没考虑#扣0.5分，其它错或少写一个扣0.5分
FIRST(E)={(,i} FIRST(E’)={*,+, ε} FIRST(T)={*,+}
FOLLOW(E)={),*,+,#} FOWLLOW(E’)= {),*,+,#} FOLLOW(T)={(,i} （3）每错一个扣0.5分，全错或不写不得分，扣完为止，共5分
2．（1）规范推导过程如下。写错推导符号扣0.5分,错写或少写一步推导扣0.5分，扣完为止，最左推导扣2分，共4分。
(()())()()
)())()()(()())()()((())()())(())()()(()()())((()())()()(())()()(εεεεεε???????????S S S S S S S S S S S S S S S S S S S S （2）（1）
中加下划线的部分是句柄，标识如（1）。每少写一个句柄扣0.5分，扣完为止，共4分。 （3）每少写步扣0.5分，扣完为止，共4分。
3．
（1）打印的字符串是：12020（错一个扣0.5分，共3分） （2）归约过程中错一步扣0.5分，扣完为止。（共5分） 4．（1）每少写一步扣0.5分，扣完为止，共5分。
while M1.q=100 E1.t=102 do M2.q=102 S1 E1.f=107 S
ε a
E2.f=103
S
S ( S )
)
S ( S ) ε )
S ( S ) ε )
ε S ( S ) ) S ( S ) ε
) ε ε
（2）少写一个四元式扣0.5分，全错或不写不得分，回填错误扣0.5分，共5分。 四元式序列为：
)100_,_,,(106)_,,1,(:105)1,,,(104)106_,_,,((103)104,,,(102)107_,_,,(101)b,102a,,j (100j x T T z y j d c j j =+><
5．（1）少写一个扣1分，全错或不写不得分，共5分。 FIRSTVT(S)={a,∧,(} FIRSTVT(T)={, a,∧,(} LASTVT(S)={ a,∧,)} LASTVT(T)={ a,∧,), ,}
(2)优先表如下。每错一个扣0.5分，全错或不写不得分，扣完为止，共3分
文法G[S]没有两个非终结符相邻的情况，且其优先表中任一对终结符之间最多满足?、?
、 三种关系中的一种，因此是G[S]算符优先文法。（2分） 或者
5分。
三、填空题（每空2分，共20分）
1目标程序（target code）语法分析（syntax analyzer）代码优化器（code optimizer）代码产生器（code generator）符号表管理（symbol table manager）
2 继承属性（inherited attribute）
3 局部优化（local optimization）
4 四元式（quatriple）
5 E + * ( ) id
四、单项选择题（每题2分，共10分）
1.B
2.D
3.B
4.D
5.C
五、解答题（共70分）
1．（1） L(G)={0m1m|M≥1} 共2分，≥写成＞扣1分
（2）S=>0S1=>00S11=>000111，共3分， =>写成->扣1分
（3）共3分，错处扣0.5分，扣完为止
(2) 共4分，错一个扣0.5分，扣完为止
4．（1）34242421 ，共4分，错一个扣0.5分
（2）共4分，错一个扣0.5分，扣完为止
5．共12分，其中带注释的分析树、三地址码序列和四元式序列分别为4分，错一个序列扣0.5分，而错某点（某项）少于或等于5个扣0.5分
带注释语法树(略)
三地址码序列四元式序列
M1: if (x>y) goto M2 100 (j>, x,y,102) goto M4 101 (j,-,-,108) M2: if (a=b) goto M3 102 (j=,a,b,104) goto M1 103 (j,-,-,100) M3: t1=2*y 104 (*,2,y,t1)
t2=t1+a 105 (+,t1,a,t2) x=t2 106 (=,t2,-,x)
goto M1 107 (j,-,-,100) M4: 108 (-,-,-,-) 6．共8分，错一个扣0.5分，扣完为止
LD R1,0
ST S,R1
ST I,R1
L1: LD R1,X
SUB R1,R1,Y (OR SUB R1,Y)
BGTZ R1,L2
LD R2,a(R1)
ADD R2,R2,S (OR ADD R2,S)
ST Z,R2
LD R1,I (从这开始，下面的语句中的R1也可以全部变成R2) ADD R1,R1,1 (OR INC R1)
ST I,R1
BR L1
L2:
7．共6分，基本块划分和流图各为3分，错一处扣 1分，扣完为止
8. （1）共4分，错一项扣1分，扣完为止（2）共4分，错一项扣1分，扣完为止
t1=b*c
t2=b*d
t3=t1-t2
t4=i+1 (or t4=i)
b[t4]=t3
科技大学 期末考试 批次专业：202001-土木工程(专升本)课程：计算机应用基础(专升本) 总时长：120分钟 1. (单选题) 计算机网络是一门综合技术的合成,其主要技术是( )。(本题 2.0分) A、计算机技术与多媒体技术 B、计算机技术与通信技术 C、电子技术与通信技术 D、数字技术与模拟技术 学生答案： B 标准答案：B 解析： 得分： 2 2. (单选题) 下列哪一个描述是Internet比较恰当的定义?( )(本题2.0分) A、一个协议 B、一个由许多个网络组成的网络 C、OSI模型的下三层 D、一种部网络结构
标准答案：B 解析： 得分： 2 3. (单选题) Internet上,访问Web信息时用的工具是浏览器。下列( )就是目前常用的Web浏览器之一。(本题2.0分) A、Internet B、Outlook C、Yahoo D、FrontPage 学生答案： A 标准答案：A 解析： 得分： 2 4. (单选题) 计算机病毒程序没有文件名,是靠( )识别的。(本题2.0分) A、长度 B、标记 C、特征码 D、症状
标准答案：C 解析： 得分： 2 5. (单选题) 操作系统的主要功能包括( )。(本题2.0分) A、存储管理、设备管理、运算器管理、处理器管理 B、文件管理、存储管理、设备管理、处理器管理 C、文件管理、存储管理、设备管理、系统管理 D、存储管理、设备管理、程序管理、处理器管理 学生答案： C 标准答案：C 解析： 得分： 2 6. (单选题) 下列关于回收站的正确说法是( )。(本题2.0分) A、回收站可以暂时存放硬盘上被删除的信息 B、放入回收站的信息不可恢复 C、放入回收站的信息不能清除 D、回收站可以存放软盘上被删除的信息
一、填空题|（每题4分，共20分） 1. 乔母斯基定义的3型文法（线性文法）产生式形式 A→Ba|a,或A→aB|a，A，B∈Vn, a,b∈Vt 。 2.语法分析程序的输入是单词符号，其输出是语法单位。 3 型为 B → .aB 的LR（0）项目被称为移进项目，型为 B → a.B 的LR（0） 项目被称为待约项目， 4.在属性文法中文法符号的两种属性分别为继承属性和综合属性。 5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。 二.已知文法 G(S) (1) E → T | E+T (2) T → F | F*F (3) F →（E）| i （1）写出句型（T*F+i）的最右推到并画出语法树。（4分） （2）写出上述句型的短语，直接短语和句柄。（4分） 答：（1）最右推到（2分） E ==> T ==> F ==> (E) ==> (E+T) ==> (E+F) ==> (E+i) ==> (T+i) ==> (T*F+i) (2) 语法树（2分） （3）（4分） 短语：（T*F+i），T*F+i ，T*F ， i 直接短语：T*F ， i 句柄：T*F 三. 证明文法G(S) ：S → SaS |ε是二义的。（6分） 答：句子aaa对应的两颗语法树为：
因此，文法是二义文法 四.给定正规文法G（S）： (1) S → Sa | Ab |b (2) A → Sa 请构造与之等价的DFA。（6分） 答：对应的NFA为：（6分） 状态转换表： a b {F} Φ{S} {S} {S,A} Φ {S,A} {S,A} {S} 五. 构造识别正规语言b*a(bb*a)*b* 最小的DFA（要求写出求解过程）。（15分）答：（1）对应的NFA（5分） a b {0} {1，3} {0} {1,3} Φ{2，3} {2,3} {1,3} {2,3} （5分） 六. 已知文法G(S) : (1) S → ^ | a | (T) (2) T → T,S | S 试：（1）消除文法的左递归；（4分） （2）构造相应的first 和 follow 集合。（6分） 答：（1）消除文法的左递归后文法 G’（S）为： (1) S → ^ | a | (T)
编译原理期末复习 鉴于编译原理马上就要期末考试，我将手中集中的一些资料上的题目进行了整理归类，每种类型题目给出了所涉及到的基本知识，然后对每类题目中的第一道例题进行了做法进行了讲解，剩下的例题请给大家作为练习，答案也都给出，希望对大家复习有所帮助，最后由于时间很紧，整理的有些仓促，整理中难免有遗漏或错误，请大家见谅。 注：下面出现的字母中，若无特别说明，小写英文字母为终结符，大写英文字母为非终结符，希腊字母为终结符与非终结符的任意组合。 1、简答题（或者名词解释） 下面涉及到的概念中，加下划线的都是在以往一些试卷中出现的原题，务必掌握。 注：这类题目老师说答案不会超过一百个字，否则写的再多也不给分，有些点到即可，不要重复啰嗦。（1）简述编译程序的概念及其构成 答：1）编译程序：它特指把某种高级程序设计语言翻译成等价的低级程序设计语言的翻译程序。 2)构成： （2）简述词法分析阶段的主要任务（也有可能问语法分析阶段主要任务）答：词法分析的任务是输入源程序，对源程序进行扫描，识别其中的单词符号，把字符串形式的源程序转换成单词符号形式的源程序。 语法分析的主要任务是对输入的单词符号进行语法分析（根据语法规则进行推导或者归约），识别各类语法单位，判断输入是不是语法上正确的程序 (3) 简述编译程序的构造过程（这个大家看看，是对（1）和（2）的综合） 答：1）构造词法分析器：用于输入源程序进行词法分析，输出单词符号； 2）构造语法分析器：对输入的单词符号进行语法分析，识别各类语法单位，判断输入是不是语法上正确的程序 3）构造语义分析和中间代码产生器：按照语义规则对已归约出的语法单位进行语义分析并把它们翻译成中间代码。 4）构造优化器：对中间代码进行优化。 5) 构造目标代码生成器：把中间的代码翻译成目标程序。 6) 构造表格管理程序：登记源程序的各类信息和编译各阶段的进展情况。 7)构造错误处理程序：对出错进行处理。 (4) 说明编译和解释的区别： 1)编译要程序产生目标程序，解释程序是边解释边执行，不产生目标程序； 2)编译程序运行效率高而解释程序便于人机对话。 （5）文法：描述语言语法结构的形式规则，一般用一个四元式表示： G=(V T，V N，S，P)，其中V T：终结符集合(非空) V N：非终结符集合(非空)，且V T ?V N=? S：文法的开始符号，S?V N P：产生式集合(有限)。
2001年编译原理试题 1．（10分）处于/* 和 */之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。 2．（10分）为语言 L ＝{a m b n | 0 ≤ m ≤ 2n}（即a的个数不超过b的个数的两倍） 写一个LR（1）文法，不准超过6个产生式。（若超过6个产生式，不给分。若所写文法不是LR（1）文法，最多给5分。） 3．（10分）构造下面文法的LL（1）分析表。 D → TL T → int | real L → id R R → , id R | ε 4．（15分）就下面文法 S → ( L) | a L → L , S | S ?给出一个语法制导定义，它输出配对括号的个数。 ?给出一个翻译方案，它输出每个a的嵌套深度。 如句子(a, (a, a) )，第一小题的输出是2，第二小题的输出是1 2 2。 5．（10分）Pascal语言for语句的含义见教材第222页习题7.13。请为该语句设计一种合理的中间代码结构。你可以按第215页图7.17的方式或者第219页图7.19的方式写出你的设计，不需要写产生中间代码的语法制导定义。 6．（5分）一个C语言程序如下： func(i1,i2,i3) long i1,i2,i3; { long j1,j2,j3; printf("Addresses of i1,i2,i3 = %o,%o,%o\n",&i1,&i2,&i3); printf("Addresses of j1,j2,j3 = %o,%o,%o\n",&j1,&j2,&j3); } main() { long i1,i2,i3;
一、填空题（每空2分，共20分） 1．编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。 2．编译器常用的语法分析方法有自底向上和自顶向下两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。 5．对编译程序而言，输入数据是源程序，输出结果是目标程序。 1．计算机执行用高级语言编写的程序主要有两种途径：解释和编译。 2．扫描器是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。 3．自下而上分析法采用移进、归约、错误处理、接受等四种操作。 4．一个LL（1）分析程序需要用到一张分析表和符号栈。 5．后缀式abc-/所代表的表达式是a/(b-c)。 二、单项选择题（每小题2分，共20分） 1．词法分析器的输出结果是__C。 A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 2．正规式M 1 和M 2 等价是指__C_。 A．M1和M2的状态数相等 B．M1和M2的有向边条数相等 C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等 3．文法G：S→xSx|y所识别的语言是_C____。 A．xyx B．(xyx)* C．xnyxn(n≥0) D．x*yx* 4．如果文法G是无二义的，则它的任何句子α_A____。 A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握____D__。 A．源程序B．目标语言C．编译方法D．以上三项都是 6．四元式之间的联系是通过__B___实现的。 A．指示器B．临时变量C．符号表D．程序变量 7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。 A．┐AB∨∧CD∨B．A┐B∨CD∨∧ C．AB∨┐CD∨∧D．A┐B∨∧CD∨ 8. 优化可生成__D___的目标代码。 A．运行时间较短 B．占用存储空间较小 C．运行时间短但占用内存空间大D．运行时间短且占用存储空间小 9．下列___C___优化方法不是针对循环优化进行的。 A. 强度削弱B．删除归纳变量C．删除多余运算D．代码外提 10．编译程序使用_B_区别标识符的作用域。 A. 说明标识符的过程或函数名B．说明标识符的过程或函数的静态层次 C．说明标识符的过程或函数的动态层次 D. 标识符的行号 三、判断题（对的打√，错的打×，每小题1分，共10分） 2．一个有限状态自动机中，有且仅有一个唯一的终态。x
编译原理考试题及答案汇总 一、选择 1．将编译程序分成若干个“遍”是为了_B__。 A . 提高程序的执行效率 B.使程序的结构更加清晰 C. 利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2．正规式 MI 和 M2 等价是指__C__。 A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。 C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等 3．中间代码生成时所依据的是 _C_。 A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 4．后缀式 ab+cd+/可用表达式__B_来表示。 A． a+b/c+d B．(a+b)/(c+d) C． a+b/(c+d) D． a+b+c/d 6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析 7．词法分析器用于识别__C___。 A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符 8．语法分析器则可以发现源程序中的___D__。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正 D．( ) 语法错误 9．下面关于解释程序的描述正确的是__B___。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3) 10．解释程序处理语言时 , 大多数采用的是__B___方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 11．编译过程中 , 语法分析器的任务就是__B___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4)C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 12．编译程序是一种___C__。 A. ( ) 汇编程序 B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 13．文法 G 所描述的语言是_C____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 14．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是___B__。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 __D___。 A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式 16．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括_C____。
河南科技大学电信科卷A 一． 填空题（每空2分，共20分） 1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为（1） 和 （2） 。 2. 规范规约是最（3）规约。 3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4） 、语义分析与中间代码生成，代码优化及（5） 。另外还有（6）和出错处理。 4．表达式x+y*z/(a+b)的后缀式为 （7） 。 5．文法符号的属性有综合属性和 （8）。 6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i ，j]的地址计算公式为（9）。 7．局部优化是局限于一个（10）范围内的一种优化。 二． 选择题（1-6为单选题，7-8为多选题，每问2分，共20分） 1. 一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，一个（ ），以及一组 （ ）。 A ． 字符串 B ． 产生式 C ． 开始符号 D ． 文法 2.程序的基本块是指（ ）。 A ． 一个子程序 B ． 一个仅有一个入口和一个出口的语句 C ． 一个没有嵌套的程序段 D ． 一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（ ）分析方法。 A ． 自左向右 B ． 自顶向下 C ． 自底向上 D ． 自右向左 4．在通常的语法分析方法中，（ ）特别适用于表达式的分析。 A ． 算符优先分析法 B ． LR 分析法 C ． 递归下降分析法 D ． LL （1）分析法 5．经过编译所得到的目标程序是（ ）。 A ． 四元式序列 B ． 间接三元式序列 C ． 二元式序列 D ． 机器语言程序或汇编语言程序 6． 一个文法所描述的语言是（ ）；描述一个语言的文法是（ ）。
一． 填空题（每空2分，共20分） 1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静 态存储分配方案和动态存储分配方案，而后者又分为（1） 和 （2） 。 2. 规范规约是最（3）规约。 3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4） 、语义分析与中间代码生成，代码优化及（5） 。另外还有（6）和出错处理。 4．表达式x+y*z/(a+b)的后缀式为 （7） 。 5．文法符号的属性有综合属性和 （8）。 6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i ，j]的地址 计算公式为（9）。 7．局部优化是局限于一个（10）范围内的一种优化。 二． 选择题（1-6为单选题，7-8为多选题，每问2分，共20分） 1. 一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，一个（ ），以及一组 （ ）。 A ． 字符串 B ． 产生式 C ． 开始符号 D ． 文法 2.程序的基本块是指（ ）。 A ． 一个子程序 B ． 一个仅有一个入口和一个出口的语句 C ． 一个没有嵌套的程序段 D ． 一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（ ）分析方法。 A ． 自左向右 B ． 自顶向下 C ． 自底向上 D ． 自右向左 4．在通常的语法分析方法中，（ ）特别适用于表达式的分析。 A ． 算符优先分析法 B ． LR 分析法 C ． 递归下降分析法 D ． LL （1）分析法 5．经过编译所得到的目标程序是（ ）。 A ． 四元式序列 B ． 间接三元式序列 C ． 二元式序列 D ． 机器语言程序或汇编语言程序 6． 一个文法所描述的语言是（ ）；描述一个语言的文法是（ ）。 A ． 唯一的 B ． 不唯一的 C ． 可能唯一，也可能不唯一 7． 如果在文法G 中存在一个句子，当其满足下列条件（ ）之一时，则称该文法是二义文法。 A ． 其最左推导和最右推导相同 B ． 该句子有两个不同的最左推导 C ． 该句子有两个不同的最右推导 D ． 该句子有两棵不同的语法树
考试成绩构成：卷面（70%）+实验（20%）+平时（10%） 考试题型：1、填空题（20分）（20空） 2、单项选择题（20分）（10题） 3、名词解释（20分）（4个） 4、简答题（20分）（3个） 5、计算题或者应用题（20） 填空题： 信息的特征：事实性、时效性、不完全性、等级性、非零和性、增殖性 系统的特点：①、系统是由若干要素（部分）组成的②、系统具有一定的结构。要素间相互联系、相互制约，形成系统的结构。 ③、系统具有一定的功能。【系统一般都具有集合性、相关性、层次性、整体性、目的性、动态性和适应性。】系统的分类： ①、根据复杂程度可将系统分为简单系统和复杂系统； ②、根据系统的自然性将系统分为自然系统和人造系统； ③、根据系统的抽象程度将系统分为实体系统和抽象系统； ④、静态系统和动态系统 ⑤、开放系统和封闭系统 信息系统的特点： 1、信息系统是一种“人-机系统” 2、信息系统是一个动态系统 3、信息系统是一个相对封闭的系统 4、信息系统是一个综合系统 决策过程模型：决策科学先驱西蒙（Simon）在著名的决策过程模型论著中指出：以决策者为主体的管理决策过程分成了三个阶段：1、情报收集2、方案设计3、方案抉择 决策问题的分类: 1、从决策的重要性来看，可将决策问题分为:（1）战略决策（2）战术决策（3）业务决策 2、从问题的结构化程度可以将决策问题分成：（1）结构化问题决策（2）非结构化问题决策（3）半结构化问题决策 管理信息系统的功能结构（纵向和横向）: 管理信息系统的功能结构可以从两方面看，一个是纵向管理职能，一个是横向的管理层次。 从纵向管理职能来看，主要就是涉及到企业的人、财、物、产、供、销 从横向的管理层次看，有战略管理、战术管理、运行控制和业务处理 信息系统的发展: 信息系统经历了由单机到网络，由低级到高级，由电子数据处理到管理信息系统、再到决策支持系统，由数据处理到智能处理的过程。这个发展过程大致经历了以下几个阶段：1、电子数据处理系统（1）单项数据处理阶段（2）综合数据处理阶段2、管理信息系统3、决策支持系统 逻辑结构的四种基本类型: 集合结构、线性结构、树状结构和网络结构。表（线性结构）和树（非线性结构）是最常用的两种高效数据结构，许多高效的算法可以用这两种数据结构来设计实现的。 计算机网络的主要功能（5大功能）:1、资源共享2、网络通信3、分布处理4、集中管理5、均衡负荷 网络协议的三要素： 1、语法。规定如何进行通信，即对通信双方采用的数据格式、编码等进行定义 2、语义。规定用于协调双方动作的信息及其含义 3、时序。规定事件实现顺序的详细说明 OSI参考模型（开放系统互连参考模型）的7个层次: 由下往上依次为：物理层-二进制传输、链路层-接入介质、网络层-寻址与路由、传输层-端到端连接、表示层-数据表示、应用层-网络应用 TCP/IP参考模型4个层次: 应用层、传输层、互联层、网络接口层 数据组织的四个层次: 从层次上看，数据组织包括数据项、记录、文件、数据库四个层次；从方式上看，数据组织包括文件组织和数据库组织两种方式 文件的组织方式: 主要有顺序文件、索引文件和散列文件三种 数据库的数据模型（概念模型和数据模型）P105 数据库系统的三级模式: 指外模式、模式和内模式 新奥尔良法的的四个阶段）: 需求分析、概念结构设计、逻辑结构设计和物理结构设计 实体集的联系: 一对一联系、一对多联系、多对多联系常见的战略规划的方法: 主要是企业系统规划法(BSP)、战略目标集转化法(SST)和关键成功因素法(CSF)。其他还有企业信息分析与集成技术(BIAIT)、产出／方法分析(E ／MA)、投资回收法(ROI)、征费法(charg out)、零线预算法、阶石法等。在此，我们只介绍企业系统规划法、关键成功因素法这两种最常用方法的基本原理。 信息系统发展的阶段论: 信息系统进化的阶段模型，即诺兰模型。诺兰在1974年首先提出了信息系统发展的四阶段论，之后经过实践的进一步验证和完善，又于1979年将其调整为六阶段论。诺兰强调，任何组织在实现以计算机为基础的信息系统时都必须从一个阶段发展到下一个阶段，不能实现跳跃式发展。诺兰模型的六个阶段分别是：初装阶段、蔓延阶段、控制阶段、集成阶段、数据管理阶段和成熟阶段。 管理信息系统的开发原则: 1、完整性原则 2、相关性原则 3、适应性原则 4、可靠性原则 5、经济实用性原则 管理信息系统的开发策略: 1、“自上而下”的开发策略 2、“自下而上”的开发策略 3、综合开发策略
《编译原理》期末考试复习题 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） ×1．计算机高级语言翻译成低级语言只有解释一种方式。() ×2．在编译中进行语法检查的目的是为了发现程序中所有错误。() √3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 () ×4．正则文法其产生式为 A->a ， A->Bb, A,B∈VN ， a 、b∈VT 。 () √5．每个文法都能改写为 LL(1) 文法。 () √6．递归下降法允许任一非终极符是直接左递归的。 () ×7．算符优先关系表不一定存在对应的优先函数。 () ×8．自底而上语法分析方法的主要问题是候选式的选择。 () ×9．LR 法是自顶向下语法分析方法。 () ×10．简单优先文法允许任意两个产生式具有相同右部。 () 三、填空题(每空1分，共10分) 1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有__ ___和 ___ _。 表格管理出错处理_ 2．若源程序是用高级语言编写的,__ __是机器语言程序或汇编程序,则其翻译程序称为 __ __ 。 _目标程序_编译程序 3．编译方式与解释方式的根本区别在于__ __。 是否生成目标代码_ 4．对编译程序而言,输入数据是__ __, 输出结果是__ ___。 _源程序目标程序
5．产生式是用于定义__ __的一种书写规则。 _语法成分 6．语法分析最常用的两类方法是___ __和__ __分析法。 自上而下_自下而上 四、简答题（20分） 1. 什么是句子？什么是语言 ? 答：(1)设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈VT*),则称x是文法的一个句子。 (2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│S x,x∈VT*} 。 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） ×1．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。() ×2．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。() √3．递归下降分析法是自顶向上分析方法。() ×4．产生式是用于定义词法成分的一种书写规则。() √5．LR 法是自顶向下语法分析方法。() √6．在SLR （1 ）分析法的名称中，S的含义是简单的。() ×7．综合属性是用于“ 自上而下” 传递信息。() ×8．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。() ×9．程序语言的语言处理程序是一种应用软件。() ×10．解释程序适用于COBOL 和FORTRAN 语言。() 三、填空题(每空1分，共10分) 1．一个句型中的最左简单短语称为该句型的___句柄__。
<编译原理>历年试题及答案 一．（每项选择 2 分，共 20 分）选择题 1．将 编译程序分成若干个“遍”是为了_b__。 a.提 高程序的执行效率 b.使程序的结构更加清晰 c. 利用有限的机器内存并提高机器的执行效率 d. 利用有限的机器内存但降低了机器的执行效率 2．构造编译程序应掌握__d__。 a.源程序 b.目标语言 c.编译方 法 d.以上三项都是 3．变量应 当 c＿。 a.持有左值 b.持有右值 c.既持有左值又持有右值 d.既不持 有左值也不持有右值 4．编译程序绝大多数时间花在 _d___上。 a.出错处理 b.词法分析 c.目标代码 生成 d.管理表格 5．词法分析器的输 出结果是_c___。 a.单词的种别编码 b.单词在符号表中的位置 c.单词 的种别编码和自身值 d.单词自身值 6．正规式 MI 和 M2 等价是指__c__。 a. MI 和 M2 的状态数相等 b.Ml 和 M2 的有向弧条数相等。 C.M1 和 M2 所识别的语言集相等 d. Ml 和 M2 状态数和有向弧条数相等7．中间代码生成时所依据的是—c。 a．语法规则 b．词法规则c．语义规则 d．等价变换规则 8．后缀式 ab+cd+/可用表达式__b_来表示。 a． a+b/c+d b． (a+b)/(c+d) c． a+b/(c+d) d． a+b+c/d 9．程序所需 的数据空间在程序运行前就可确定，称为____c_＿管理技术。 a.动态存储 b.栈式存储 c.静态存储 d.堆式存储 10.堆式 动态分配申请和释放存储空间遵守___d____＿原则。 a.先请先放 b.先请后放 c.后请先放 d.任意 二（每小题 10 分，共 80 分）简答题 1.画出编译程序的 总体结构图，简述各部分的主要功能。 2. 已知文法 G[E]: E→ET+|T T→TF* | F F→F^ | a 试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄.
南京工业大学继续教育学院编译原理期末考试试卷 (2012-2013学年) A卷 一、选择题（每题2分，共20分） 得分 1. 一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个_____，以及一组产生式。 A．字符串 B．运算符号 C．开始符号 D．文法 2.程序的基本块是指_____。 A．一个子程序 B．一个仅有一个入口和一个出口的语句 C．一个没有嵌套的程序段 D．一组顺序执行的程序段，仅有一个入口和一 个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于_____分析方法。 A．自左向右 B．自顶向下 C．自底向上 D．自右向左 4．经过编译所得到的目标程序是_____。 A．四元式序列 B．间接三元式序列 C．二元式序列 D．机器语言程序或汇编语言程序 5．运行阶段的存储组织与管理的目的是_____。 ①提高编译程序的运行速度②节省编译程序的存储空间 ③提高目标程序的运行速度④为运行阶段的存储分配做准备 A. ①② B. ②③ C. ③④ D. ④②6．词法分析器的输出结果是_____。 A．( ) 单词的种别编码B．( ) 单词在符号表中的位置C．( ) 单词的种别编码和自身值D．( ) 单词自身值 7．正规式M 1 和M 2 等价是指_____。
A．( ) M1和M2的状态数相等B．( ) M1和M2的有向边条数相等 C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等 8．文法G：S→xSx|y所识别的语言是_____。 A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 9．语言是_____。 A．句子的集合B．产生式的集合 C．符号串的集合D．句型的集合 10．编译程序前三个阶段完成的工作是 A．词法分析、语法分析和代码优化 B．代码生成、代码优化和词法分析 C．词法分析、语法分析、语义分析和中间代码生成 D．词法分析、语法分析和代码优化 二、名词解释（每题2分，共20分） 得分 1.最左推导： 2.语法： 3.文法： 4.基本块： 5.语法制导翻译： 6.短语： 7.规范句型：
1、选择题：9题 1、要求用JavaScript实现下面的功能：在一个文本框中内容发生改变后，单击页面的其他部分将弹出一个消息框显示文本框中的内容，下面语句正确的是（） A． B． C． D． 正确答案是: B 2、在HTML页面中，下面关于Window对象的说法不正确的是（）。 A．Window对象表示浏览器的窗口，可用于检索有关窗口状态的信息 B．Window对象是浏览器所有内容的主容器 C．如果文档定义了多个框架，浏览器只为原始文档创建一个Window对象，无须为每个框架创建Window对象 D．浏览器打开HTML文档时，通常会创建一个Window对象 正确答案是: C 3、window的哪个方法可以显示输入对话框？（） A．confirm() B．alert() C．prompt() D．open() 正确答案是: C 4、open()方法的哪个外观参数可以设置是否显示滚动条？（） A．location B．menubar C．scrollbars D．toolbar 正确答案是: C 5、在Javascript语言中，当元素失去了焦点时激发的事件是( ) A.Focus B.UnLoad C.MouseOver D.Blur 正确答案是: D 6、DHTML不具备的优点是（） A.动态样式 B.动态语法 C.动态内容 D.动态定位
《编译原理》期末试题（二） 一、是非题： 1.一个上下文无关文法的开始符，可以是终结符或非终结符。 ( ) 2.一个句型的直接短语是唯一的。（） 3.已经证明文法的二义性是可判定的。（） 4.每个基本块可用一个DAG表示。（） 5.每个过程的活动记录的体积在编译时可静态确定。（） 6.2型文法一定是3型文法。（） 7.一个句型一定句子。 ( ) 8.算符优先分析法每次都是对句柄进行归约。 X ( ) 9.采用三元式实现三地址代码时，不利于对中间代码进行优化。（） 10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( ) 11.一个优先表一定存在相应的优先函数。 X ( ) 12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 13.递归下降分析法是一种自下而上分析法。 ( ) 14.并不是每个文法都能改写成LL(1)文法。 ( ) 15.每个基本块只有一个入口和一个出口。 ( ) 16.一个LL(1)文法一定是无二义的。 ( ) 17.逆波兰法表示的表达试亦称前缀式。 ( ) 18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 19.正规文法产生的语言都可以用上下文无关文法来描述。 ( ) 20.一个优先表一定存在相应的优先函数。 ( ) 21.3型文法一定是2型文法。 ( ) 22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。 ( ) 答案：1.× 2.× 3.× 4.√ 5.√ 6.×7.×8.× 9.√10.× 11.× 12.√ 13.× 14.√ 15.√ 16.√ 17.× 18.√19.√ 20.×21.√22.√ 二、填空题： 2.编译过程可分为（词法分析），（语法分析），（语义分析与中间代码生成），（优化）和（目标 代码生成）五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（二义性的）。 4.从功能上说，程序语言的语句大体可分为（执行性）语句和（说明性）语句两大类。 5.语法分析器的输入是（单词符号），其输出是（语法单位）。 6.扫描器的任务是从（源程序中）中识别出一个个（单词符号）。 7.符号表中的信息栏中登记了每个名字的有关的性质，如(类型、种属、所占单元大小、地址）等等。 8.一个过程相应的DISPLAY表的内容为(现行活动记录地址和所有外层最新活动记录的地址) 10.常用的两种动态存贮分配办法是（栈式）动态分配和（堆式）动态分配。 11.一个名字的属性包括( 类型)和(作用域 )。 12.常用的参数传递方式有(传地址），（传值），（传名） 13.根据优化所涉及的程序范围，可将优化分成为(局部优化），（循环优化），（全局优化）三个级别。 14.语法分析的方法大致可分为两类，一类是（自上而下）分析法，另一类是（自下而上） 分析法。 15.预测分析程序是使用一张（分析表）和一个（符号栈）进行联合控制的。 17.一张转换图只包含有限个状态,其中有一个被认为是（初）态;而且实际上至少要有一个（终）态。 19.语法分析是依据语言的（语法）规则进行。中间代码产生是依据语言的（语义）规则进行的。 21.一个文法G，若它的预测分析表M不含多重定义，则该文法是（LL(1) 文法）文法。 22.对于数据空间的存贮分配， FORTRAN采用( 静态策略， PASCAL采用( 动态)策略。
试卷三（第一页） 河南科技大学 二00五至二00六学年第一学期期终试卷（A） 课程机械原理年级、专业03级机械类各专业分数_________ 特别提示：所有答案均写在次此试卷上 得分一．选择题(每题2分，共20分,把正确选项的序号填在“____”处) 1.机构具有确定运动的条件是自由度F＞0，并且____ 。 ① F = 1② F＞1③ F = 原动件的数目 2.机械自锁行程的效率____ 。 ① ② ③ 3.图示四拐曲轴____ 。 ① 静平衡②动平衡③既不静平衡又不动平衡 第3题图第4、5题图 4.图示铰链四杆机构ABCD 中，已知各杆长，该机构为____ 。 ① 曲柄摇杆机构② 双曲柄机构③ 双摇杆机构 5.图示机构ABCD中，以杆____为主动件，机构有死点位置。 ① AB ② BC ③ CD 6.机器中的飞轮能够____ 周期性速度波动。 ① 消除② 增大③ 减小 7.机械系统的等效动力学模型中，等效力矩M e____ 。 ① 产生的瞬时功率等于原系统中相应外力和力矩产生的瞬时功率 ② 等于原系统中的力矩之和③ 等于原系统中的力和力矩之和 8.反转法设计滚子从动件盘形凸轮机构时，凸轮的实际轮廓曲线是____ 。
① 滚子中心的轨迹② 滚子圆的包络线③ 理论轮廓曲线沿导路减去滚子半径后的曲线 9.当齿轮的安装中心距a ′大于标准中心距a时，其传动比____ 。 ① 增大② 不变③ 减小 10.用齿条形刀具范成法切削直齿圆柱齿轮时，发生根切的原因是____ 。 ① 刀具的齿顶线超过了啮合极限点② 被切齿轮的齿数Z ＜Z min③ Z ＞Z min 得分二．(7分)试计算图示机构的自由度，如有复合铰链、局部自由度、虚约束，须在图中指出。 得分 三．(7分)图示为一摆动推杆盘形凸轮机构，凸轮1在驱动力矩M d的作用下逆时针方向回转，Q为作用 在 推杆2上的外载荷，试确定各运动副中的总反力(F R31、F R12、F R32)的方位。图中虚线圆为摩擦圆，摩擦角为φ。 下一页
2011～ 2012 学年第 1 学期期末考试试卷答案 《编译原理》（共 4 页） （考试时间： 2011 年 12 月 25 日） 一、选择题（每题 1 分，共 10 分） 1.B 2.D 3.A 4.D 5.D 6.C 7.B 8.C 9.D 10.B 二、简答题（每题 5 分，共 20 分） 1．何谓二义性文法？试举一例说明。 答：若文法G 的一个句子对应有两棵或两棵以上不同的推导树，则称该句子是 二义性的。产生二义性句子的文法称为二义性文法，否则该文法是无二义性的。 例子：给定文法G[）是上下文无关文法，产生式集合P 中任意一个产生式应具有什么样的形式？若G 是正则文法呢？ 答：上下文无关文法的产生式形式为： A →α，其中， A ∈ V N，α∈（ V N∪V T）* 正则文法产生式形式为： N，a∈V T A→，或→ （右线性文法）其中，A,B ∈V aBA a A→Ba，或 A → a（左线性文法）其中， A,B ∈ V N， a∈V T 三、推导题（共70 分） 1．对于文法 G[S]：
期末考试试卷（A）卷 一、填空题（每小题2分，共20分） 1、字母表∑，用∑*表示∑上所有有穷长的串集合，∑*称为∑的①。 2、设z=abc，则z的固有头是①。 3、如何由语言基本符号组成程序中各个语法成分（包括程序）的一组规则叫 ①。 4、设∑＝{a,b}，∑上的正规式(a|b)(a|b) 相应的正规集为① 5、NFA的映象f是从"状态×字"映射到"状态子集"，f为①值函数。 6、LR分析是按规范句型的①为可归约串。 7、结点的①属性值由该结点的兄弟结点和父结点的属性值计算。 8、如果分析树中一结点的属性b依赖于属性c，那么这个结点的属性b的语义规 则的计算必须在定义属性c的语义规则的计算①。 9、对于栈式符号表，引入一个显示嵌套层次关系表- ①表，该表总是 指向当前正在处理的最内层的过程的子符号表在栈符号表中的起始位置。 10、任一有向边序列n1 → n2,n2 → n3,…,nk-1 → nk为从结点n1到结点nk 的一条通路。如果n1=nk，则称该通路为①。 二、单项选择（每小题2分，共14分） 1、乔姆斯基把文法分成4种类型，即0型、1型、2型和3型。其中3型文法也称 为（）。 A．上下无关文法 B.正规文法 C．上下文有关文法 D.无限制文法 2、生成非0开头的正偶数集的文法是（）。 A． Z::=ABC B. Z::=ABC C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|ε B::=BA|B0|0 A::=1|2|3|…|9 A::=1|2|3|…|9 C. Z::=ABC|2|4|6|8 D. Z::=ABC|2|4|6|8 C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|0 B::=BA|B0|ε A::=1|2|3|…|9 A::=1|2|3|…|9 3、简单优先分析法从左到右扫描输入串,当栈顶出现（）时进归约。
一、填空题（每空 2分，共20分） 1编译程序首先要识别出源程序中每个 单词，然后再分析每个句子并翻译其意义。 2?编译器常用的语法分析方法 有自底向上 和自顶向下 两种。 3?通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的 分析，中间代码生成、代码 优化与目标代码的生成则是对源程序的 综合。 4?程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即 静态存储分配 方案和动态存储分配 5?对编译程序而言，输入数据是 源程序，输出结果是目标程序。 1计算机执行用高级语言编写的程序主要有两种途径： 解释和编译。 2?扫描器是词法分析器，它接受输入的 源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符 号，供语法 分析器使用。 3?自下而上分析法采用 移进、归约、错误处理、 接受等四种操作。 4?一个LL （1）分析程序需要用到 一张分析表 和符号栈。 5. 后缀式abc-/所代表的表达式是 a/（b-c ）。 3 . 文法G : S T xSx|y 所识别的语言是 _C _________ 。 A ? xyx B ? (xyx)* C ? xnyxn(n > 0) D ? x*yx* 4 ?如果文法 G 是无二义的，则它的任何句子 a_ ______ 。 A ?最左推导和最右推导对应的语法树必定相同 B ?最左推导和最右推导对应的语法树可能不同 C ?最左推导和最右推导必定相同 D ?可能存在两个不同的最左推导，但它们对应的语法树相同 5 ?构造编译程序应掌握 _____ D_。 A ?源程序 B ?目标语言 C ?编译方法 6. 四元式之间的联系是通过 __B —实现的。 A .指示器 B .临时变量 C ?符号表 7. 表达式（「A B ） A （C V D ）的逆波兰表示为__B_。 A . 「AB VA CD V B . AqB V CD VA 9. 下列—C —优化方法不是针对循环优化进行的。 A.强度削弱 B .删除归纳变量 10 .编译程序使用_B_区别标识符的作用域。 A.说明标识符的过程或函数名 C .说明标识符的过程或函数的动态层次 三、判断题（对的打"，错的打X,每小题 1分，共10 分） 2 . 一个有限状态自动机中，有且仅有一个唯一的终态。 二、单项选择题（每小题 2分，共20分） 1词法分析器的输出结果是 _C 。 A ?单词的种别编码 B ? C ?单词的种别编码和自身值 D ? 2. 正规式 M 1和M 2等价是指__C_。 A ? M1和M2的状态数相等 C ? M1和M2所识别的语言集相等 单词在符号表中的位置 单词自身值 B ? M1和M2的有向边条数相等 D ? M1和M2状态数和有向边条数相等 D .以上三项都是 D .程序变量 C . AB V 「C D VA D . AqB VA CD V 8. 优化可生成__D_的目标代码。 A .运行时间较短 C .运行时间短但占用内存空间大 B .占用存储空间较小 D .运行时间短且占用存储空间小 C .删除多余运算 D ?代码外提 B .说明标识符的过程或函数的静态层次 D.标识符的行号