系运算符优先级高):
100(j<,A,C,102)
101(j,_,_,113)/*E1为F*/
102(j<,B,D,104)/*El为T*/
103(j,_,_,113)/*El为F*/
104(j=,A,1,106)/*Ez为T*/
105(j,_,_,108)/*EZ为F*/
106(+,C,1,C)/*C:
=C+1*/
107(j,_,_,112)/*跳过else后的语句*/
108(j≤,A,D,110)/*E3为T*/
109(j,_,_,112)/*E3为F*/
110(+,A,2,A)/*A:
=A+2*/
111(j,_,_,108)/*转回内层while语句开始处*/
112(j,_,_,100)/*转回外层while语句开始处*/
113
9.【解答】
(1)流图中各结点N的必经结点集D(n),
D(l)={1},D
(2)={1,2},D(3)={1,2,3},D(4)={1,2,3,4},D(5)={1,2,5},
D(6)={1,2,5,6}
(2)求出流图中的回边,5->2,4->3
(3)求出流图中的循环:
回边5->2对应的循环:
2、5、3、4;
回边4->3对应的循环:
3、4
《编译原理》模拟试题一
一、是非题(请在括号内,正确的划√,错误的划×)(每个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.简单优先文法允许任意两个产生式具有相同右部。
(×)
二、选择题(请在前括号内选择最确切的一项作为答案划一个勾,多划按错论)(每
个4分,共40分)
1.一个编译程序中,不仅包含词法分析,_____,中间代码生成,代码优化,
目标代码生成等五个部分。
A.()语法分析B.()文法分析C.()语言分析D.()解释分析
2.词法分析器用于识别_____。
A.()字符串B.()语句C.()单词D.()标识符
3.语法分析器则可以发现源程序中的_____。
A.()语义错误B.()语法和语义错误
C.()错误并校正D.()语法错误
4.下面关于解释程序的描述正确的是_____。
(1)解释程序的特点是处理程序时不产生目标代码
(2)解释程序适用于COBOL和FORTRAN语言
(3)解释程序是为打开编译程序技术的僵局而开发的
A.()
(1)
(2)B.()
(1)C.()
(1)
(2)(3)D.()
(2)(3)
5.解释程序处理语言时,大多数采用的是_____方法。
A.()源程序命令被逐个直接解释执行
B.()先将源程序转化为中间代码,再解释执行
C.()先将源程序解释转化为目标程序,再执行
D.()以上方法都可以
6.编译过程中,语法分析器的任务就是_____。
(1)分析单词是怎样构成的
(2)分析单词串是如何构成语句和说明的
(3)分析语句和说明是如何构成程序的(4)分析程序的结构
A.()
(2)(3)B.()
(2)(3)(4)C.()
(1)
(2)(3)D.()
(1)
(2)(3)(4)
7.编译程序是一种_____。
A.()汇编程序B.()翻译程序C.()解释程序D.()目标程序
8.文法G所描述的语言是_____的集合。
A.()文法G的字母表V中所有符号组成的符号串
B.()文法G的字母表V的闭包V*中的所有符号串
C.()由文法的开始符号推出的所有终极符串
D.()由文法的开始符号推出的所有符号串
9.文法分为四种类型,即0型、1型、2型、3型。
其中3型文法是_____。
A.()短语文法B.()正则文法C.()上下文有关文法D.()上下文
无关文法
10.一个上下文无关文法G包括四个组成部分,它们是:
一组非终结符号,一
组终结符号,一个开始符号,以及一组_____。
A.()句子B.()句型C.()单词D.()产生式
三、填空题(每空1分,共10分)
1.编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码
生成,代码优化等几个基本阶段,同时还会伴有__表格处理___和___出错处理__。
2.若源程序是用高级语言编写的,___目标程序__是机器语言程序或汇编程序,
则其翻译程序称为___编译程序__。
3.编译方式与解释方式的根本区别在于__是否生成目标代码___。
4.对编译程序而言,输入数据是___源程序__,输出结果是__目标程序___。
5.产生式是用于定义___语法成分__的一种书写规则。
6.语法分析最常用的两类方法是___自上而下__和___自下而上__分析法。
四、简答题(20分)
1.什么是句子?
什么是语言?
答:
(1)设G是一个给定的文法,S是文法的开始符号,如果Sx(其中x∈VT*),则称x是文
法的一个句子。
(2)设G[S]是给定文法,则由文法G所定义的语言L(G)可描述为:
L(G)={x│Sx,x∈VT*}。
2.写一文法,使其语言是偶正整数的集合,要求:
(1)允许0打头;
(2)不允许0打头。
解:
(1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S)
P:
S->PD|D
P->NP|N
D->0|2|4|6|8
N->0|1|2|3|4|5|6|7|8|9
(2)G[S]=({S,P,R,D,N,Q},{0,1,2,…,9},P,S)
P:
S->PD|P0|D
P->NR|N
R->QR|Q
D->2|4|6|8
N->1|2|3|4|5|6|7|8|9
Q->0|1|2|3|4|5|6|7|8|9
3.已知文法G[E]为:
E→T|E+T|E-T
T→F|T*F|T/F
F→(E)|i
①该文法的开始符号(识别符号)是什么?
②请给出该文法的终结符号集合VT和非终结符号集合VN。
③找出句型T+T*F+i的所有短语、简单短语和句柄。
解:
①该文法的开始符号(识别符号)是E。
②该文法的终结符号集合VT={+、-、*、/、(、)、i}。
非终结符号集合VN={E、T、F}。
③句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i;简单短语为i、T*F、第一个T;句
柄为第一个T。
4.构造正规式相应的NFA:
1(0|1)*101
解1(0|1)*101对应的NFA为
5.写出表达式(a+b*c)/(a+b)-d的逆波兰表示和三元式序列。
逆波兰表示:
abc*+ab+/d-
三元式序列:
①(*,b,c)②(+,a,①)③(+,
a,b)④(/,②,③)⑤(-,④,d)
五.计算题(10分)
构造下述文法G[S]的自动机:
S->A0A->A0|S1|0
该自动机是确定的吗?
若不确定,则对它确定化。
解:
由于该文法的产生式S->A0,A->A0|S1中没有字符集VT的输入,所以不是确定的自
动机。
要将其他确定化,必须先用代入法得到它对应的正规式。
把S?
A0代入产生式A?
S1
有:
A=A0|A01|0=A(0|01)|0=0(0|01)*。
代入S->A0有该文法的正规式:
0(0|01)*0,所以,改
写该文法为确定的自动机为:
由于状态A有3次输入0的重复输入,所以上图只是NFA,下面将它确定化:
下表由子集法将NFA转换为
DFA:
由上表可知DFA为:
《编译原理》模拟试题二
一、是非题(请在括号内,正确的划√,错误的划×)(每个2分,共20分)
1.“用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法。
(×)
2.若一个句型中出现了某产生式的右部,则此右部一定是该句型的句柄。
(×)
3.一个句型的句柄一定是文法某产生式的右部。
(√)
4.在程序中标识符的出现仅为使用性的。
(×)
5.仅考虑一个基本块,不能确定一个赋值是否真是无用的。
(√)
6.削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。
(√)
7.在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。
(×)
8.算符优先关系表不一定存在对应的优先函数。
(×)
9.数组元素的地址计算与数组的存储方式有关。
(×)
10.编译程序与具体的机器有关,与具体的语言无关。
(×)
二、选择题(请在前括号内选择最确切的一项作为答案划一个勾,多划按错论)(每个4分,共
40分)
1.通常一个编译程序中,不仅包含词法分析,语法分析,中间代码生成,代码优化,目
标代码生成等五个部分,还应包括_____。
A.()模拟执行器B.()解释器
C.()表格处理和出错处理D.()符号执行器
2.文法G[N]=({b},{N,B},N,{N→b│bB,B→bN}),该文法所描述
的语言是
A.()L(G[N])={bi│i≥0}B.()L(G[N])={b2i│i≥0}
C.()L(G[N])={b2i+1│i≥0}D.()L(G[N])={b2i+1│i≥1}
3.一个句型中的最左_____称为该句型的句柄。
A.()短语B.()简单短语C.()素短语D.()终结符号
4.设G是一个给定的文法,S是文法的开始符号,如果S->x(其中x∈V*),则称x是
文法G的一个_____。
A.()候选式B.()句型C.()单词D.()产生式
5.文法G[E]:
E→T∣E+T
T→F∣T﹡F
F→a∣(E)
该文法句型E+F﹡(E+T)的简单短语是下列符号串中的_____。
①(E+T)②E+T③F④F﹡(E+T)
A.()①和③B.()②和③C.()③和④D.()③
6.若一个文法是递归的,则它所产生的语言的句子_____。
A.()是无穷多个B.()是有穷多个
C.()是可枚举的D.()个数是常量7.词法分析器用于识别_____。
A.()句子B.()句型C.()单词D.()产生式
8.在语法分析处理中,FIRST集合、FOLLOW集合、SELECT集合均是_____。
A.()非终极符集B.()终极符集C.()字母表D.()状态集
9.在自底向上的语法分析方法中,分析的关键是_____