编译原理练习及答案

第一章练习 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 （绪论）一、选择题编译程序是一种常用的B—软件。A）应用B）系统C）实时系统D）分布式系统编译程序生成的目标代码程序B是可执行程序。A）—定B）不一定编译程序的大多数时间是花在D—上。A）词法 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 B）语法分析C）出错处理D） 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 格管理将编译程序分成若干“遍”将B。A）提咼编译程序的执行效率；B）使编译程序的结构更加清晰，提高目标程序质量；C）充分利用内存空间，提咼机器的执行效率。编译程序各个阶段都涉及到的工作有D。A）词法分析B）语法分析C）语义分析D）表格管理词法分析的主要功能是。A）识别字符串B）识别语句C）识别单词D）识别标识符若某程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 语言允许标识符先使用后说明，则其编译程序就必须A。A）多遍扫描B）一遍扫描编译方式与解释方式的根本区别在于B。A）执行速度的快慢B）是否生成目标代码C）是否语义分析多遍编译与一遍编译的主要区别在于D。A）多遍编译是编译的五大部分重复多遍执行，而一遍编译是五大部分只执行一遍；B）一遍编译是对源程序分析一遍就立即执行，而多遍编译是对源程序重复多遍分析再执行；C）多遍编译要生成目标代码才执行，而一遍编译不生成目标代码直接分析执行；D）多遍编译是五大部分依次独立完成，一遍编译是五大部分交叉调用执行完成。编译程序分成“前端”和“后端”的好处是DA）便于移植B）便于功能的扩充C）便于减少工作量D）以上均正确第二章 练习题 用券下载整式乘法计算练习题幼小衔接专项练习题下载拼音练习题下载凑十法练习题下载幼升小练习题下载免费 （文法与语言）1、直接推导、＋推导、＊推导2、句型和句子，文法定义（搞清楚）G=（VT,VN,S,P）3、语言的形式定义：L（G[S]）={xIS->x且xGVT*}若L是无穷的，则G一定是递归的4、最左推导、最右推导（规范推导）5、归约、规范归约6、递归：规则递归、文法递归（1）A->BAe->CA,・・・（2）A->B,B->CA,・・・文法的等价性：G1=G2（1）每棵子树的叶子组成一个短语；（2）每棵简单子树的叶子组成一个直接短语；简单子树：只有单层分支的子树（3）最左边简单子树的叶子是句柄一个句型不一定只对应一棵唯一的语法树。如果一个文法存在某个句子对应二棵不同的语法树或者二个不同的最左（右）推导，则这个文法是二义性的归约是推导的逆过程。即：将句型中的某一子串用一串非终结符代替的过程。若有A->a则XAY->XaY,于是XaY->XAY。称规范（最右）推导的逆过程为规范归约（先归约最左那一串（不是一个）符号）。规范归约：先归约最左那一串（不是一个）符号。1）文法的开始符一定写在文法的前面（第一条规则式中）；2）e是表示空符号串，不是终结符；3）L是语言，不要用作非终结符；4）文法的完整表示是G=（VT,VN,S,P）一、选择题文法G产生的D的全体是该文法描述的语言。A.句型B.终结符集C.非终结符集D.句子若文法G定义的语言是无限集，则文法必然是AA递归的B上下文无关的C二义性的D无二义性的Chomsky定义的四种形式语言文法中，0型文法又称为A文法;1型文法又称为C文法；2型语言可由G_识别。A短语结构文法B上下文无关文法C上下文有关文法D正规文法E图灵机F有限自动机G下推自动机一个文法所描述的语言是A；描述一个语言的文法是BA唯一的B不唯一的C可能唯一，也可能不唯一二、构造文法以生成下列语言：{anbnInMO}解：G=（{S},{a,b},S,P）,其中P={S-e|aSb}{anbmIn，mM1}解：G=（{S，A，B}，{a，b}，S，P），其中P={S—AB,A—aIaA,B—bIbB}{an,bmIn，mM1}解：G=（{S，A，B}，{a，b}，S，P），其中P={S—A|B,A—aIaA,B—bIbB}4.L={wIw是不含两个相邻1的0、1串}解：G=({S,A},{0,1},S,P),其中P={S-0|1|OS|1A,A—OS|0}5．能被5整除的整数集合。解：G[S]:S->FNCF->+I-IEC->0|5N->AMIEM->0IAIEA->1I2I3I4I5I6I7I8I9Ex1:设E={a,b},试设计一个文法G,定义语言L={a2n,b2nIn>1}解：G[A]：A->BIDB->aaIaBaD->bbIbDbEx3：设计一个表示所有标识符I的文法。解：G[I]：I->LIILDL->a|b|cz|A|B|C|ZED->1|2|3|9|E&设G[E]：E->E+EIE*E|(E)|i,试证明符号串(i*i+i)是文法G[E]的一个句子证明：从E出发，只要证明符号串x=(i*i+i)对于文法G[E]存在一个推导。E->(E)->(E+E)->(E＊E+E)->(i*E+E)->(i*i+E)->(i*i+i)以上从文法的开始符E->(i*i+i)，所以符号串(i*i+i)是G[E]的一个句子。Ex:已知:S->ABA->AaIbBB->aISb,给出句子babaab的最左、最右推导解：最左：S=>AB=>bBB=>baB=>baSb=>baABb=>babBBb=>babaBb=>babaabS=>AB=>ASb=>AABb=>AAabbabaab=>bBbaab=>Abaabi,j,k>=0}D->aDIE,C->bCcIE最右：=>AbBab=>Abaab=>bBbaab=>babaab归约：=>AbBab=>AAab=>AABb=>Asb=>AB=>S已知L={aibjckIi=j或j=k,求：文法G解：S->ABIDC,A->aAbIE,B->cBIE11・已知L={xx-1Ix^{a,b}+}，若x=ab,Mx-1=ba,求文法G。解：因为x={a9b}+={a,b,ab,ba9aa,bb,}则L={aa,bb,abba,baab,aaaa,bbbb,^4*所以：A->aaIbbIaAaIbAbEx3:P：S->A|BA->aAb|0B->aBbb|1求L?解.L（G）={amOb^,amlb2m|m>0}例题：Ex:已知G[N]:N^SEIES^SDIDETOI2I4I6I8I10DTOI1I2I3|……I8I91）济明文法是.[义性的；2）语百L=?3）找•个等价的无一义性的文法。解：1)找一个句子，使它能夠对应两棵不同的语法树，如102)L是所有偶数的集合；|NotE：某一语言可能对应两个文法，一个无二义，一个有二|义，所以同一语言其对应的文法不唯一口E&已知G[S]:ST(AS)I(b)求符号串(a))和(AUSaAMh)))的短语、也接灿语和旬解：因为—(AS)((a)S)(a))所以，符号串(a))不是句型，它没有短语、直接短语和句又因为S=(A)=(AAS：)=(A(A(b)))^(AUSaAHb)))所以，符号$(Aa&iAHb)))是文法G的句型.以第一个S为根:以第二个S为根:以第三个s为根:以A为根：3+L(a*)-{s，*…}4+(ab)L(ab)=L(a)uL(b)={a,b}5+(ab)(ab)L(a|b)L(a|b)—{}6+a•bL(a-b)=L(a)L(b)={ab}7+(ab)*(L(a|b))*={a?b}+第四章练习题(词法分析)1•正规式与正规集止规式£*申、A,BA|BABA*止规集{小{町{纵衣L(A).L(B)L(A|B)=L(A)uL(B)L(AB)=L(A)L(B)L(A*)=(L(A))*2.正规式的等价性若L(R1)=L(R2)，则R1与R2等价，记为：R1=R2利用等价公式化简(A|B)*=(A*|B*)*=(A*B*)A*=A*(BA*)*(A*)*=A*A*=AA*|AA*=A*AAA*=A+如果它们的最小化的DFA是相同的，则两正规式等价例题：证明：(alb)*=((ela)b*)*DFA与NFA的区别初态可不唯一f一t映射函数JNFAN=(S,X，S0N,严F)DFAM=(S,S0D,尸，F)正规式R->NFA，按如下规则分裂，直到保证一个唯一的初态结和唯一的终态结。注意：一定要一步一步来分裂，不可以跳过每一步！！！！！！！！ABABAABA*A分裂为分裂为分裂为例例题：Ex2:R=0(1*)*I01,求NFAo答案：先化简R,因为(A*)*=A*AIA*=A*所以0(1*)*I01=01*I01=0(1*I1)=01*设I是NFA的状态子集，定义E-closure(I)：若S^I,贝US丘E-closure(I)；若SEI,则从I出发经任意条E弧能到达的任意状态S',有S'eI；B.确定化NFAN为DFAM已知NFAN=(S,,S0,f,F),令①唯一的初态x=S0，②唯一的终态y=F；例题：解:1)令初始集D为空集，求DFA的初态：阵。{0,2,1}{0,1}{0,3,1}{0,2,1}B{0,2,1}B{0,2,1}B(0,2,1)B{0,1}c{0,3,1}D{0,1}C{0,y,1}e£-closure({x})={x.0.1},据此作如下矩确定初始状态与终态:只要有x即为初态,只要含y的即为终态。所以A为初态，E为终态。根据状态转换矩阵画DFA,如卜所小。厂abABCBBDcBCDBEBCBl^a(D>^a‘)bb6.DFA的化简(最小化DFA)采用分化法步骤：(1)将DFA的状态分成两个子集：终态集和非终态集。形成初始分划n。(2)由分划算法构造新的分划直到n中每一状态子集不能再分为止。接上题：第一步：形成初始分划：n=({AR,CR},{E})第二步：由分划算法构造新的分划：1)对{A,B,C,D}a输入a得{B}对{A,B,C}b输入b得{C,D}，而D输入b得到E,所以将D划分出来所以ni=({A,B,C},{D},{E})2）对{A,B,C}a输入{B}对{A,C}b输入b得到{C},而B输入b得到D,所以划分出B所以n2=（{A,C},{B},{D},{E}）3）对{A,C}a={B}对{A,C}b={C}不能再分划，说明A、C等价。可删除其中一个，如C,可得如下最小化的DFAExl:B知止规式R=“Z⑹笃求最小化的DFA。解:算「步，R^NFA（分裂法）。第一〔步，NFA^DFA（了集法）17Id0{X}{12y}1◎l{12y}{2,y}2{2,y}2'2{2,y}1{2,y}2t12y}2'=^@第二步，DFAAi小化（分划法）n=（{1},丄2}）=对丄2}円2}{1,2}广{2},说明1、2等价。删除状态2得如下愎小化DFAo解：正规集L（R）={anbmcl|n,m,l>=1}正规文法，P：S->aS|aA，A->bA|bB，B->cB|c一、设语言L是由奇数个a和偶数（可以是0）个b组成的符号串之集。课后答案p;花-6⑴£(即是咖讪的数亍出TrND-WD=>NDDD=>DDDDnODDDrUIDDc。12心二UI27©N=■NDnDD=3打=■34NnNDnNDD=DDD=5DD=56D=56S最卅推导:NnND二■N7二A/D7=>NUn,VD27=>Afl：?nD127^i.)：27MrNDrN4rD4r34N=NDnn\D8=A/68=/>68=568P36-71G(S)OT113151719TV^21416181(9DtOIJV20AOAADINP36-8文法：E^T\E+T\E-TTfF\T^F\T/FFT(E)lf最左推导：E、E+T->T+T、F+T->i+丁亠i+T*F\i+F*Fui+i姑F=i+i*iEnT=T*FnF*F"*Fni%E)=>i气E卜T)^i^(T+T)^i^(F+T)ni®r)^i*(i+F)=>i*G+O权右推导：EdE+T=E+F^FdE—T*idE+F*i=E—iBdF+iBdF+i*i=i—i喙E=F*T->LF」F*(E)」F*(E+T)iF^(E+F)F^(E+i)=F*(T十」)二>F*(F十f)二>十i)二沦(f+)STABAtaAbI£R―>ciBbIELI:SA\BA^OAllrB^\BO\AP36-11Jj哥《哥《^p»rn?"■-f""t■-t"-t"-f-•】”-f"LL:StACATuAbIabC.—>■c(2I£\：1-STABATMIFBtbBcIbe1.3：64页第六题也要看!确定化:01{1,2,3}巾申M2,3}⑵3}{2t3,4}^3}{2,3}⑵3,4}23,4}{2,3,5}⑵3,1}忆3,5}{2,3}忆3,4,Y}{2.3,4,¥}{2,3,5}23,4,}(j0023000(j51最小化:0,1,2,3,4,5,{6}0,1,2,3,4,5}。={1,3,5}{0,1,2,3,4,5}]={1,2,4,6}{0,1,2,3,4,{5},{6}{0,1,2,3,4°二{1,3,5}0,1,2,3},{4},5},{6}0,12,3}。={,3}{0,1,2,3}]={1,2,4}0,1,{2,3}{4},{5},{6}{0,1}0={1}{0,1}广{1,2}{2,3}°={3}{2,3}广{4}{0},{1},{2,3},{4},{5},{6}P64-8⑴(110)*01(2)(1I2I3I4I5I6I7I819)(01112131415I6171819)*(015)I(015)⑶0*1(0110ftl)'11*0(0110*1/P81-1(1)按照Tj的顺序消除左递归G\5)£T胡W)「fS厂2递归子程序：pffK'eciureS;begin1lic-ri!)rgl：irl(lVcl\f.C;T;iTsym1)htln\iadvance1elseerror;en(i(i1.Sf'v'：'：■o'：-pfid:prufeGurc1';h(?gins；r(rid；pro<(?duti'Tf;beginj丨synr,il)eginadvixnce:S;Fendend;其中；叩i:是输入串指针叩所指的符号advance:是把丁调金卜'-•个输入符弓error：S错诊察程序(2)FIRST(S)=feT\(]FIRST(T)={a/,()FIRST(D={!T£}FOLLOW⑸二■!)—#}FOLLOW(T)-D)FOLLOW(厂)打)}预测分析表第二题：E^TEfEJ+EIeT7FT厂tFIfFtPF"FJ*『上P^{E)\a\h\^⑴1rST(E)={(,a,b/}FIRST(ET)={+he}FIRST(T)={(tatb/jFIRSTS)-(C£}FIRST(F)={(,a,b,IFTRST(r)=(*,e}FIRST(P)={Gatb/}FOLLOW(E)=(pJ}FOLLOW(EJ)={#,)}FOLLOW(T)={4,),#}FOLLOW(T‘)={+,),#}FOLLOW(F)二{(,a,b/,+,),#}FOLLOttr(F,)={(,d,b,",+,),#}FOLLOW(P)={*,(,a,b/,+,),#}⑵©考虑下列产生式：EJ+El£r^T\ePT(E)SlalbFIRST(+E)DFIRST(e)={+)D{«}=4>FIRST(+E)QFOLLOW(E')={+}n{#,)}“FIRST(T)PFIRST(€)={(,a,b/}n{e}=4>FIRST(T)AFOLLOW(D={(,a,b/}0{+,),#}=4)FIRST(*F,)AFIRST(e)={*}n{e}=4>FIRST(*F‘)nFOLLOW(F')={*}门{(卫,b,；+,)，#}=FIRST((E))nFIRST(a)nFIRST(b)nFIRST(*)=所以，该文法式LL(1)文法.⑶+*()abAEEtTE'EtTE'EtTE'EfTE、E，E't+EE，T£E，T£TT—FTTlFTTtFT'TlFTVT，T£TJT厂T£T，tTTJTTJTT，T£IFFtPF'FtPF'FtPF'FIPF'F'F，T£FJ*F'F，T£F，T£F，T£F，I£F，T£F，I£1PPt(E)PtaPTbPt八(4)procedureE;beginifsym=，('orsym=,a*orsym='b'orsym=,thenbeginT;E'endelseerrorendprocedureE';beginifsym=，+，thenbegincidvance;Eend电elseifsym〈>')'andsyiiK>'#'thenerrorendprocedureT:beginifsym='('orsym='ti'orsym二'b'orsym二'thenbeginF;T'endelseerrorprocedureT';beginifsym=，('orsym=,