编译原理考试习题及答案

程序设计语言Chapter3.词法分析22020/5/13CH.3.练习题8(P64.)8.给出下面的正规表达式。(1)以01结尾的二进制数串;正规式(0|1)*01(2)能被5整除的十进制整数;允许任意0开头：(0|1|2|3|4|5|6|7|8|9)*(0|5)不允许0开头（0本身除外）：(0|5)|(1|2|3|…|9)(0|1|2|3|…|9)*(0|5)32020/5/13CH.3.练习题7(P64.)7.(1)1(0|1)*101构造DFA。解1:正规式对应的NFA:XY345110ε112ε10II0I1{X}{1,3,2}{1,3,2}{3,2}{3,4,2}{3,2}{3,2}{3,4,2}{3,4,2}{3,5,2}{3,4,2}{3,5,2}{3,2}{3,Y,4,2}{3,Y,4,2}{3,5,2}{3,4,2}II0I1初01123223343425终543(1)正规式1(0|1)*101DFA:x3,Y,4,23,4,23,5,211011,3,23,20100101II0I1{X}{1,3,2}{1,3,2}{3,2}{3,4,2}{3,2}{3,2}{3,4,2}{3,4,2}{3,5,2}{3,4,2}{3,5,2}{3,2}{3,Y,4,2}{3,Y,4,2}{3,5,2}{3,4,2}II0I1初01123223343425终543(1)正规式1(0|1)*101DFA:II0I1{X}{1,3,2}{1,3,2}{3,2}{3,4,2}{3,2}{3,2}{3,4,2}{3,4,2}{3,5,2}{3,4,2}{3,5,2}{3,2}{3,Y,4,2}{3,Y,4,2}{3,5,2}{3,4,2}II0I1初01123223343425终5430534110112010010162020/5/13CH.3.练习题7(P64.)7.构造下列正规式相应的DFA。(1)1(0|1)*101解2:正规式对应的NFA:04123110110II0I1{0}初0{1}1{1}1{1}1{1,2}2{1,2}2{1,3}3{1,2}2{1,3}3{1}1{1,2,4}4{1,2,4}终4{1,3}3{1,2}210423110110010DFA:72020/5/137.构造下列正规式相应的NFA。(P64.)(2)1(1010*|1(010)*1)*0XY20ε113ε1010*1(010)*1XY20ε113ε6451100*7811(010)*82020/5/137.构造下列正规式相应的NFA。(P64.)(2)1(1010*|1(010)*1)*0XY20ε113ε6451100*7811(010)*XY20ε113ε645110078119εε10010εεXY20ε113ε645110078119εε10010εεXY20ε113ε645110078119εε100εε1211017.(2)1(1010*|1(010)*1)*0的NFA。102020/5/13CH.3.练习题14(P64.)(1)正规式:(10|0)*(2)NFA:确定化:YX10ε0ε1201001012II0I1{X,1,Y}{1,Y}{2}{1,Y}{1,Y}{2}{2}{1,Y}II0I1初终012终11221DFA:112020/5/13CH.3.练习题14(P64.)(1)正规式:(10|0)*(2)NFA:YX10ε0ε1201001012DFA:构造一个DFA，它接受S＝{0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。10010DFA:(最简)程序设计语言Chapter2.高级语言及其语法描述13CH.2.练习题6(P36.)6.令文法G6为:N→D|NDD→0|1|2|3|4|5|6|7|8|9(1)G6的语言L(G6)是什么?注意：集合的写法不正确解：L(G6)={0,1,2,3,4,5,6,7,8,9}+={09数字构成的所有数字串，可以0开头}(2)给出句子0127、34和568的最左和最右推导。注意：1)步骤，和的区别；2)不能写为→解：0127的最左推导：NNDNDDNDDDDDDD0DDD01DD012D01270127的最右推导：NNDN7ND7N27ND27N127D1270127+14CH.2.练习题8(P36.)8.令文法为E→T|E+T|E-TT→F|T*F|T/FF→(E)|i(1)给出i+i*i、i*(i+i)的最左推导和最右推导。解：此处仅以i*(i+i)为例给出答案最左推导ETT*FF*Fi*Fi*(E)i*(E+T)i*(T+T)i*(F+T)i*(i+T)i*(i+F)i*(i+i)最右推导ETT*FT*(E)T*(E+T)T*(E+F)T*(E+i)T*(T+i)T*(F+i)T*(i+i)F*(i+i)i*(i+i)15CH.2.练习题8(P36.)8.令文法为E→T|E+T|E-TT→F|T*F|T/FF→(E)|iEE-TE-TTFFiFiii-i-i的语法树(2)给出i+i+i、i+i*i和i-i-i的语法树。EE+TE+TTFFiFiii+i+i的语法树i+i*i的语法树EE+TTTFFiFii*注意：树枝和符号均不可随意增减！162020/5/13CH.2.练习题9(P36.)9.证明下面的文法是二义的：S→iSeS|iS|i证明:因为存在句子iiiei，它对应两棵不同的语法树,如右图:所以该文法是二义文法。说明：按定义只要能给出一个反例即可，iiiei不是唯一的反例。SiSiSeSiiiSiSeSiSi程序设计语言Chapter5.自下而上语法分析182020/5/13CH.5.练习题1(P133.)1.令文法G1为：E→E+T|TT→T*F|FF→(E)|i证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。证明1:∵存在从开始符号E出发到E+T*F的推导：EE+TE+T*F∴E+T*F是G1的一个句型。短语:E+T*F是句型相对于非终结符E的短语;T*F是句型相对于非终结符T的短语。直接短语:T*F是句型相对于规则T→T*F的直接短语句柄:T*FEE+TT*F语法树192020/5/13CH.5.练习题1(P133.)1.令文法G1为：E→E+T|TT→T*F|FF→(E)|i证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。证明2:∵可构造出E+T*F的语法树，如右图所示，∴E+T*F是G1的一个句型。证明3:(也可用归约来证明)（概念熟悉后，短语、直接短语和句柄可直接列出而不用说明）短语:E+T*F，T*F直接短语:T*F句柄:T*FEE+TT*F语法树202020/5/13CH.5.练习题2(P133.)2.考虑下面的表格结构文法G2：S→a||(T)T→T,S|S(1)给出(a,(a,a))的最左和最右推导。(1)解:(a,(a,a))的最左推导：S(T)(T,S)(S,S)(a,S)(a,(T))(a,(T,S))(a,(S,S))(a,(a,S))(a,(a,a))最右推导：S(T)(T,S)(T,(T))(T,(T,S))(T,(T,a))(T,(S,a))(T,(a,a))(S,(a,a))(a,(a,a))212020/5/13CH.5.练习题2(P133.)2.(2)指出(a,(a,a))的规范归约及每一步的句柄。根据这个规范归约，给出“移进-归约”的过程，并给出它的语法树自下而上的构造过程。(2)解:(a,(a,a))的规范归约及每一步的句柄:(a,(a,a))(S,(a,a))(T,(a,a))(T,(S,a))(T,(T,a))(T,(T,S))(T,(T))(T,S)(T)S.........222020/5/13CH.5.练习题2(P133.)2.(2).给出(a,(a,a))“移进-归约”的过程。(2)解:(a,(a,a))的“移进-归约”过程:步骤符号栈输入串动作句柄1#(a,(a,a))#a2#(a,(a,a))#移进(3#(a,(a,a))#移进a4#(S,(a,a))#归约S→aS5#(T,(a,a))#归约T→Sa6#(T,(a,a))#移进,7#(T,(a,a))#移进(8#(T,(a,a))#移进a232020/5/13CH.5.练习题2(P133.)2.(2).给出(a,(a,a))“移进-归约”的过程。(2)解:(a,(a,a))的“移进-归约”过程:步骤符号栈输入串动作句柄9#(T,(S,a))#归约S→aS10#(T,(T,a))#归约T→Sa11#(T,(T,a))#移进,12#(T,(T,a))#移进a13#(T,(T,S))#归约S→aT,S14#(T,(T))#归约T→T,S(T)15#(T,(T))#移进)16#(T,S)#归约S→(T)T,S242020/5/13CH.5.练习题2(P133.)2.(2).给出(a,(a,a))“移进-归约”的过程。(2)解:(a,(a,a))的“移进-归约”过程:步骤符号栈输入串动作句柄17#(T)#归约T→T,S(T)18#(T)#移进)19#S#归约S→(T)20成功,分析结束,接受输入串252020/5/13CH.5.练习题2(P133.)2.(2).给出(a,(a,a))的语法树自下而上构造过程。(2)解:(a,(a,a))的语法树自下而上构造过程:用序号表示S(T)T,S①(T)T,SSaSaa②③④⑤⑥⑦⑧⑨262020/5/13CH.5.练习题3(P133.)3.(1)计算练习2文法G2的FIRSTVT和LASTVT。S→a||(T)T→T,S|S(1)解:（执行相应的算法可求得）FIRSTVT(S)={a,∧,(}FIRSTVT(T)={,a,∧,(}LASTVT(S)={a,∧,)}LASTVT(T)={,,a,∧,)},272020/5/13CH.5.练习题3(P133.)3.(2)计算文法G2的优先关系,G2是一个算符优先文法吗?S→a||(T)T→T,S|S(2)解:FIRSTVT(S)={a,∧,(}FIRSTVT(T)={,,a,∧,(}LASTVT(S)={a,∧,)}LASTVT(T)={,,a,∧,)}逐一考察S→(T)和T→T,S两两相邻的符号，得到算符优先关系,如右图；G2是算符优先文法。a∧(),#a∧(=),#=.......................282020/5/133.(4)给出输入串(a,(a,a))的算符优先分析过程。S→a||(T)T→T,S|S序号符号栈输入串优先关系下一步的动作0#(a,(a,a))##(移进(1#(a,(a,a))#(a移进a2#(a,(a,a))#(aa,归约S→a3#(S,(a,a))#(,移进,4#(S,(a,a))#,(移进(5#(S,(a,a))#(a移进a6#(S,(a,a))#(aa,归约S→a7#(S,(S,a))#(,移进,8#(S,(S,a))#,a移进aa∧(),#a∧(=),#=最左素短语..................................292020/5/13序号符号栈输入串优先关系下一步的动作9#(S,(S,a))#,(a)归约S→a10#(S,(S,S))#(,,)归约T→S,S11#(S,(T))#(=)移进)12#(S,(T))#,())归约S→(T)13#(S,S)#(,,)归约T→S,S14#(T)#(=)移进)15#(T)#*()#归约S→(T)16#S##=#接受17#S#停.......