北方工业大学编译原理习题集Word格式文档下载.docx
- 文档编号:7120309
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:51
- 大小:268.78KB
北方工业大学编译原理习题集Word格式文档下载.docx
《北方工业大学编译原理习题集Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《北方工业大学编译原理习题集Word格式文档下载.docx(51页珍藏版)》请在冰点文库上搜索。
ND8=>
N68=>
D68=>
7、写一个文法,使其语言是奇数集,且每个奇数不以0开头。
本题要构造一个文法,由它产生的句子是奇数,且不以0开头。
也就是说它的每个句子都以1、3、5、7、9中某数结尾。
如果数字只有一位,则满足要求;
如果有多位,则要求第一位不能是0;
而中间有多少位,每位是什么数字则没有要求。
因此我们可以把这个文法分3部分完成,分别用3个非终结符来产生句子的第一位、中间部分和最后一位。
引入几个非终结符,其中,一个
第三章词法分析
1、编写一个对于Pascal源程序的预处理程序。
该程序的作用是,每次被调用时都将下一个完整的语句送进扫描缓冲区,去掉注释行,同时要对源程序列表打印。
2、请给出以下C++程序段中的单词符号及其属性值。
intCInt:
:
nMulDiv(intn1,intn2)
{
if(n3==0)return0;
elsereturn(n1*n2)/n3;
}
3、用类似C或Pascal的语言编写过程GetChar,GetBC和Concat。
4、用某种高级语言编写并调试一个完整的词法分析器。
5、证明3.3.1中关于正规式的交换律、结合律等五个关系。
6、令A、B和C是任意正规式,证明以下关系成立:
A∣A=A
(A*)*=A*
A*=ε∣AA*
(AB)*A=A(BA)*
(A∣B)*=(A*B*)*=(A*∣B*)*
A=b∣aA当且仅当A=a*b
证明:
(1)、A∣A=A
L(A∣A)=L(A)∪L(A)=L(A),所以有A∣A=A。
(2)、(A*)*=A*
(3)、A*=ε∣AA*
通过证明两个正规式所表示的语言相同来证明两个正规式相等。
L(ε∣AA*)=L(ε)∪L(A)L(A*)=L(ε)∪L(A)(L(A))*
=L(ε)∪L(A)((L(A))0∪(L(A))1∪(L(A))2∪(L(A))3∪…)
=L(ε)∪(L(A))1∪(L(A))2∪(L(A))3∪(L(A))4∪…
=(L(A))*=L(A*)
即:
L(ε∣AA*)=L(A*),所以有:
A*=ε∣AA*
(4)、(AB)*A=A(BA)*
利用正规式的分配率和结合律直接推导。
(AB)*A=((AB)0∣(AB)1∣(AB)2∣(AB)3∣…)A
=εA∣(AB)1A∣(AB)2A∣(AB)3A∣…
=Aε∣A(BA)1∣A(BA)2∣A(BA)3∣…
=A(ε∣(BA)1∣(BA)2∣(BA)3∣…)
=A(BA)*
(AB)*A=A(BA)*
(5)、(A∣B)*=(A*B*)*=(A*∣B*)*
证明:
先证(A∣B)*=(A*B*)*
因为L(A)
L(A)*L(B)*,L(B)
L(A)*L(B)*
故:
L(A)∪L(B)
于是由本题第二小题结论可知(L(A)∪L(B))*
(L(A)*L(B)*)*①
又L(A)
L(A)∪L(B),L(B)
L(A)∪L(B)
L(A)*
(L(A)∪L(B))*
L(B)*
因此有:
L(A)*L(B)*
(L(A)∪L(B))*(L(A)∪L(B))*=((L(A)∪L(B))*)2
故(L(A)*L(B)*)*
((L(A)∪L(B))*)*
由本题第二小题得:
((L(A)∪L(B))*)*=(L(A)∪L(B))*
故得:
(L(A)*L(B)*)*
(L(A)∪L(B))*②
则由①②得:
(L(A)∪L(B))*=(L(A)*L(B)*)*
由于L((A*B*))*=(L(A*B*))*=(L(A*)L(B*))*=(L(A)*L(B)*)*
即有(L(A)∪L(B))*=L((A*B*))*③
而(A|B)*对应的语言为(L(A)∪L(B))*,且(A*B*)*对应的语言为L((A*B*))*
则根据③得(A|B)*=(A*B*)*
再证:
(A*|B*)*=(A*B*)*
因为:
A,B是任意正规式,由以上结论得:
(A*|B*)*=((A*)*(B*)*)*
又由本题第二小题目的结论可得:
(A*)*=A*,(B*)*=B*
因此,(A*|B*)*=(A*B*)*
综合上述两种结论,最后得:
(A∣B)*=(A*B*)*=(A*∣B*)*
(6)、A=b∣aA当且仅当A=a*b
7、构造下列正规式相应的DFA
1(0∣1)*101
1(1010*∣1(010)*1)*0
0*10*10*10*
(00∣11)*((01∣10)(00∣11)*(01∣10)(00∣11)*)*
(1)、1(0∣1)*101
第一步:
根据正规式构造NFA,先引入初始状态X和终止状态Y:
再对该转换图进行分解,得到分解后的NFA如下图:
第二步:
对NFA进行确定化,获得状态转换矩阵:
状态
1
{X}
Ø
{1,2,3}
{2,3}
{2,3,4}
{2,3,5}
{2,3,4,Y}
根据转换矩阵获得相应的DFA:
第三步:
化简该DFA,获得最简的DFA即为所求。
首先根据是否终止状态将所有状态分为两个集合{0,1,2,3,4}和{5},这里集合{5}已经不可划分,只需考虑集合{0,1,2,3,4}。
{0,1,2,3,4}0={2,4,-},{0,1,2,3,4}1={1,3,5}
因为{1,3,5}和{2,4,-}不在一个集合里面,所以需要对集合{0,1,2,3,4}进行进一步的划分,检查其中的所有状态。
状态0不能接受字符0,需要把状态0划分出来;
另外,只有状态4读入字符1后进入状态5,因此将状态4划分出来,划分的结果为4个集合:
{0},{1,2,3},{4},{5}。
检查集合{1,2,3},{1,2,3}0={2,4},不属于同一个集合,因此要对集合{1,2,3}进行进一步划分,划分结果为5个集合:
{0},{1,2},{3},{4},{5}。
检查集合{1,2},{1,2}0={2},{1,2}1=3,不需要进行进一步划分。
所以最终划分结果为5个集合:
所以,最终所求DFA如下图示:
(2)、1(1010*∣1(010)*1)*0
(3)、0*10*10*10*
(4)、(00∣11)*((01∣10)(00∣11)*(01∣10)(00∣11)*)*
8、给出下面正规表达式:
(1)以01结尾的二进制数串;
(2)能被5整除的十进制整数;
(3)包含奇数个1或奇数个0的二进制数串;
(4)英文字母组成的所有字符串,要求符号串中的字母依照字典序排列;
(5)没有重复出现的数字的数字符号串的全体;
(6)最多有一个重复出现的数字的数字符号串的全体;
(7)不包含子串abb的由a和b组成的符号串的全体。
解:
分析题意,要求的是二进制数串,即由0和1构成的串,并且必须以01结尾,所以本题可以分两步完成:
一部分实现由0和1构成的任意串,一部分即01,然后将它们连结在一起就可以了,所以所求为(1︱0)*01。
分析题意,本题要求的是十进制整数,也就是由0至9这10个数字组成的字符串,并且不能以0开头(整数“0”除外),要求能被5整除,则该串必须以0或者5结尾。
根据分析,可以把本题分成两种情况考虑:
一种情况时该整数只有一位,则该整数有0和5两种可能;
另一种情况是该整数有多位,则该整数可以分成三部分考虑:
一是第一位必须不为0;
二是最后一位必须为0或5;
三是中间部分可有可无,并且可以由0到9之间任意数字构成,所以所求为(1︱2︱3︱4︱5︱6︱7︱8︱9)(0︱1︱2︱3︱4︱5︱6︱7︱8︱9)*(0︱5)(0︱5)。
本题求二进制串,并且要求包含奇数个0或奇数个1,由于0和1都可以在二进制串中任何地方出现,所以本题只需要考虑一种情况,另一种情况也可以类似求得。
考虑包含奇数个0的字符串:
由于只关心0的个数的奇偶数,我们可以把二进制串分成多段来考虑,第一段为二进制串的开始到第一个0为止,这一段包含一个0,并且0的前面有0个或多个1。
对于剩下的二进制串按照每段包含两个0的方式去划分,即以0开始,以0结尾,中间可以有0个或多个1。
如果一个二进制串被这样划分完后,剩下的部分如果全部是全1串(这些全1串在前面划分的串之间或最后),则该二进制串就有奇数个0,所以该二进制串可以这样描述:
以第一段(1*0)开始,后面由全1串(1*)以及包含两个0的串(01*0)组成,所以包含奇数个0的正规表达式为1*0(1︱01*0)*。
所以本题所求为1*0(1︱01*0)*︱0*1(0︱10*1)*。
9、对下面情况给出DFA及正规表达式:
(1){0,1}上的含有子串010的所有串;
(2){0,1}上不含子串010的所有串。
(1)、
(2)、直接写出满足条件的正规表达式。
考虑满足条件的字符串中的1:
在串的开始部分可以有0个或多个1,串的尾部也可以有0个或多个1,但串的中间只要出现1则至少在两个以上,所以满足条件的正规表达式为1*(0∣111*)*1*。
所求的DFA如下图所示:
10、一个人带着狼、山羊和白菜在一条河的左岸。
有一条船,大小正好能装下这个人和其他三件东西中的一件。
人和他的随行物都要过到河的右岸。
人每次只能将一件东西摆渡过河。
但若人将狼和羊留在同一岸而无人照顾的话,狼将把羊吃掉。
类似地,若羊和白菜留下来无人照看,羊将会吃掉白菜。
请问是否有可能渡过河去,使得羊和白菜都不被吃掉?
如果可能,请用有限自动机写出渡河的方法。
11、
12、将图3.18的(a)和(b)分别确定化和最小化。
(1)、图(a)中为一个NFA,所以需要先对它进行确定化,得到DFA,然后再对DFA进行最小化。
首先进行确定化,如下两个表所示:
a
b
{0}
{0,1}
{1}
2
根据状态转换矩阵得到如下图所示的DFA:
化简后的DFA为:
(2)、题中所给即为一个DFA,不需要确定化,只对它进行最小化即可。
首先将状态划分为两个集合{{0,1},{2,3,4,5}}。
有{0,1}a={1},{0,1}b={2,4}和{2,3,4,5}a={1,3,0,5},{2,3,4,5}b={2,3,4,5},所以可以进一步划分为{{0,1},{2,4},{3,5}},然后有{0,1}a={1},{0,1}b={2,4},{2,4}a={1,0},{2,4}b={3,5},{3,5}a={3,5},{3,5}b={2,4}。
因此,最后划分结果是{{0,1},{2,4},{3,5}}。
最小化后的DFA如下图所示:
13、
(1)给出描述C浮点数的DFA;
14、构造一个DFA,它接受∑={0,1}上所有满足如下条件的字符串:
每个1都有0直接跟在右边。
对这类题型的固定解法分4步进行:
首先根据语言写出正规表达式;
然后根据正规表达式构造相应的NFA;
然后,对NFA进行确定化得到DFA;
最后对DFA化简得到最简DFA。
写出正规表达式。
根据题意,该DFA接受的字符串由0和1组成,并且每个1的后面都有0直接跟在右边,因此,可以将该字符串理解为由0和10构成的串,则相应的正规表达式就是(0︱10)*。
构造NFA。
首先得出下图:
然后对上图进行分解后得到如下图所示的NFA。
确定化,得到DFA。
确定化结果如表14.1所列;
给状态编号,得到表14.2所示的状态转换矩阵:
{X,1,Y}
{1,Y}
{2}
表14.1状态转换矩阵
表14.2新的状态转换矩阵
根据状态转换矩阵得到DFA如下图所示:
第四步:
对该DFA进行最小化。
其分析过程如下:
{0,1},{2}
{0,1}0={1},{0,1}1={2}
最小化后的DFA如图所示,该DFA即为所求。
15、给定右线性文法G:
S→0S∣1S∣1A∣0B
A→1C∣1
B→0C∣0
C→0C∣1C∣0∣1
求出一个与G等价的左线性文法。
根据右线性文法求左线性文法没有直接的方法,但可以通过状态转换图去转换。
可以先求出文法G的状态转换图,再根据状态转换图写出相应的左线性文法。
文法G对应的状态转换图如下所示:
对状态转换图进行确定化,得到状态转换矩阵:
{S}
{S,B}
{S,A}
{S,B,C,Z}
{S,A,C,Z}
给状态编号,得到新的状态转换矩阵:
3
4
根据状态转换矩阵获得DFA如下:
还可以对上图的DFA进行化简,状态3和4可以合并,化简后的DFA如下图所示:
不难看出,该DFA接受的语言是{0,1}上包含00或11的字符串。
根据化简后的DFA,我们可以写出相应的左线性文法G’:
T→A0∣B1∣T0∣T1
A→B0∣0
B→A1∣1
16、*非形式的说明
17、*下面的字集是否为正规集?
或写出其正规式,或给出否证。
(1)L1={anbn∣n≥0};
(2)L2={x};
(3)L3={}。
18、假定L和M都是正规集:
(1)证明L∪M、L∩M和~M(补集)也是正规的;
(2)L′是L中每个字的逆转,证明L也是正规的。
19、写出描述ANSIC的单词符号的LEX程序。
20、假定有正规定义式
A0→a∣b
A1→A0A0
……
An→An-1An-1
考虑词形An
(1)把An中所有简名都换掉,最终所得的正规式的长度是多少?
(2)字集An的元素是什么?
把它们非形式的表示成n的函数;
(3)证明识别An的DFA只需用2n+1个状态就足够了。
21、把LEX的“动作”成分加以充实使得可用它来编写语法制导编辑器。
第四章语法分析——自上而下分析
1、考虑下面的文法
G1:
S→a∣∧∣(T)
T→T,S∣S
(1)消去G1的左递归。
然后对每个非终结符,写出不带回溯的递归子程序。
(2)经改写后的文法是否是LL
(1)的?
给出它的预测分析表。
(1)按照T、S的顺序消除左递归,得到文法:
G’(S)
S→a∣∧∣(T)
T→ST’
T’→,ST’∣ε
对于非终结符S,T,T’的递归子程序如下:
ProcedureS;
Begin
Ifsym=‘a’orsym=‘^’
Thenadvance
Elseifsym=‘(‘
Thenbegin
Advance;
T;
Ifsym=’)’
Thenadvance
Elseerror
End
Elseerror
Ends;
ProcedureT;
S;
T’;
ProcedureT’
Begin
Ifsym=‘,’
Thenbegin
Advance;
S;
T’
Ends
ends;
(2)计算每个非终结符的FIRST集合和FOLLOW集合:
FIRST(S)={a,∧,(}
FIRST(T)={a,∧,(}
FIRST(T’)={,,ε}
FOLLOW(S)={),’,’,#}
FOLLOW(T)={)}
FOLLOW(T’)={)}
从而可见改造后的文法符合LL
(1)文法的充分必要条件,所以是LL
(1)的。
该文法的预测分析表
^
(
)
#
S
S->
(T)
T
T->
ST’
T’
T’->
ξ
ST’
2、对下面的文法G:
E→TE’
E’→+E∣ε
T→FT’
T’→T∣ε
F→PF’
F’→*F’∣ε
P→(E)∣a∣b∣∧
(1)计算这个文法的每个非终结符的FIRST和FOLLOW。
(2)证明这个文法是LL
(1)的。
(3)构造它的预测分析表。
(4)构造它的递归下降分析程序。
分析:
对于这类题目,我们首先应当检查文法是否符合LL
(1)文法的条件,根据需要,先通过消除左递归、提取右公因子的方法,把文法改造成符合LL
(1)文法的条件,在此基础上,我们才能构造出不带回溯的递归下降识别程序。
注意,本题在构造子程序时,对于每个产生式候选,在调用第一个非终结符对应的子程序之前,检查了首符集。
(1)计算每个非终结符的FIRST集合和FOLLOW集合如下:
FIRST(E)={(,a,b,∧}
FIRST(E’)={+,ε}
FIRST(T)={(,a,b,∧}
FIRST(T’)={(,a,b,∧,ε}
FIRST(F)={(,a,b,∧}
FIRST(F’)={*,ε}
FIRST(P)={(,a,b,∧}
FOLLOW(E)={#,)}
FOLLOW(E’)={#,)}
FOLLOW(T)={+,),#}
FOLLOW(T’)={+,),#}
FOLLOW(F)={(,a,b,∧,+,),#}
FOLLOW(F’)={(,a,b,∧,+,),#}
FOLLOW(P)={*,(,a,b,∧,+,),#}
(2)本文法是LL
(1)文法。
通过观察可知文法中不含有左递归,满足LL
(1)文法定义的第一个条件。
考虑下列产生式:
因为:
FIRST(+E)∩FIRST(ε)={+}∩{ε}=Ø
FIRST(E’)∩FOLLOW(E’)={+}∩{#,)}=Ø
FIRST(T)∩FIRST(ε)={(,a,b,∧}∩{ε}=Ø
FIRST(T’)∩FOLLOW(T’)={(,a,b,∧}∩{+,),#}=Ø
FIRST(*F’)∩FIRST(ε)={*}∩{ε}=Ø
FIRST(F’)∩FOLLOW(F’)={*}∩{(,a,b,∧,+,),#}=Ø
FIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(∧)=Ø
所以该文法是LL
(1)文法。
(3)构造其预测分析表:
预测分析表
+
*
(
)
a
b
^
#
E
E→TE’
E’
E’→+E
E’→ξ
E’->
T→FT’
T’→FT’
T→FT’
T’→ξ
T’→T
T’→T
T’→T
F
F→PF’
F→PF’
P→PF’
F’
F’→ξ
F’→*F’
F’→ξ
P
P→(E)
P→a
P→b
P→^
(4)构造其递归下降分析程序:
ProcedureE;
T;
E’
End;
ProcedureE’;
Ifsym=‘+’
Thenbegin
Acvance
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北方工业 大学 编译 原理 习题集
![提示](https://static.bingdoc.com/images/bang_tan.gif)