《编译原理》课后习题答案-清华大学-第二版.pdf

精品锦程课后习题答案编译原理课后习题答案清华大学-第二版第1章引论第1题解释下列术语：(1)编译程序(2)源程序(3)目标程序(4)编译程序的前端(5)后端(6)遍答案：(1)编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。(2)源程序：源语言编写的程序称为源程序。(3)目标程序：目标语言书写的程序称为目标程序。(4)编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端 做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。(5)后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生 成，以及相关出错处理和符号表操作。(6)遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。第2题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程 序的总体结构 图。答案：一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主 要功能简述如下。词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代 码，如三元式或四元式。中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的各类信息和编译 各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出 的是，这里的“表格管理程序”并不意味着它就 是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行 适当的校正（修复），目的是 使编译程序能够继续向下进行分析和处理。注意：如果问编译程序有哪些主要构成成分，只要回答六部分就可以。如果搞不清楚，就回答八部分。第3题何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系?答案：翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，如编译程 序和汇编程序 等。编译程序是把用高级语言编写的源程序转换(加工)成与之等价的另一种用低级语言编写的目标程序 的翻译程序。解释程序是解释、执行高级语言源程序的程序。解释方式一般分为两种：一种方式是，源程序功能的 实现完全由解释程序承担和完成，即每读出源程序的一条语句的第一个单词，则依据这个单词把控制转移到 实现这条语句功能的程序部分，该部分负责完成这条语句的功 能的实现，完成后返回到解释程序的总控部分 再读人下一条语句继续进行解释、执行，如此反 复；另一种方式是，一边翻译一边执行，即每读出源程序的 一条语句，解释程序就将其翻译成一段机器指令并执行之，然后再读人下一条语句继续进行解释、执行，如 此反复。无论是哪种方式，其加工结果都是源程序的执行结果。目前很多解释程序采取上述两种方式的综合 实现方案，即先把源程序翻译成较容易解释执行的某种中间代码程序，然后集中解释执行中间代码程序，最 后得到运行结果。广义上讲，编译程序和解释程序都属于翻译程序，但它们的翻译方式不同，解释程序是边翻译(解 释)边执行，不产生目标代码，输出源程序的运行结果。而编译程序只负责把源程序 翻译成目标程序，输出 与源程序等价的目标程序，而目标程序的执行任务由操作系统来完成，即只翻译不执行。对下列错误信息，请指出可能是编译的哪个阶段(词法分析、语法分析、语义分析、代码生成)报告 的。(1)else没有匹配的if(2)数组下标越界(3)使用的函数没有定义(4)在数中出现非数字字符答案：(1)语法分析(2)语义分析(3)语法分析(4)词法分析第5题编译程序大致有哪儿种开发技术？答案：(1)自编译：用某一高级语言书写其木身的编译程序。(2)交叉编译：A机器上的编译程序能产生B机器上的目标代码。(3)自展：首先确定一个非常简单的核心语言L0,用机器语言或汇编语言书写出它的编译程序TO,再把 语言L0扩充到L1,此时LOcz LI，并用LO编写LI的编译程序T1,再把语言L1扩充为12,有LI u L2,并用L1编写L2的编译程序T2,，如此逐步扩展下去，好似滚雪球一样，直 到我们所要求的编译程序。(4)移植：将A机器上的某高级语言的编译程序搬到B机器上运行。第6题计算机执行用高级语言编写的程序有哪些途径?它们之间的主要区别是什么？答案：计算机执行用高级语言编写的程序主要途径有两种，即解释与编译。像Basic之类的语言，属于解释型的高级语言。它们的特点是计算机并不事先对高级语言进行全盘翻 译，将其变为机器代码，而是侮读入一条高级语句，就用解释器将其翻译为一条机器代码，予以执行，然后 再读入下一条高级语句，翻译为机器代码，再执行，如此反复。总而言之，是边翻译边执行。像C,Pascal之类的语言，属于编译型的高级语言。它们的特点是计算机事先对高级语言进行全盘翻 译，将其全部变为机器代码，再统一执行，即先翻译，后执行。从速度上看，编译型 的高级语言比解释型的 高级语言更快。第2章PL/O编译程序的实现第1题PL/O语言允许过程嵌套定义和递归调用，试问它的编译程序如何解决运行时的存储管理。答案：PI70语言允许过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动态存储管理。(数组 CODE存放的只读目标程序，它在运行时不改变。)运行时的数据区S是由解释程序定义的一维整型数组，解释执行时对数据空间S的管理遵循后进先出规则，当每 个过程(包括主程序)被调用时，才分配数据空间，退出过程时，贝I所分配的数据空间被释放。应用动态链和静态链的方式分别解决递归调用和非局部变量 的引用问题。第2题若PL/0编译程序运行时的存储分配策略采用栈式动态分配，并用动态链和静态链的方式分别解决递归 调用和非局部变量的弓I用问题，试写出下列程序执行到赋值语句b:=10时运行栈的布局示意图。var x,y;procedure p;var a;procedure q;var b;begin(q)b:=10;end(q);procedure s;var c,d;procedure r;var e,f;begin(r)call q;end(r);begin(s)call r;end(s);begin(p)call s;end(p);begin(main)call p;end(main).答案：程序执行到赋值语句b:=10时运行栈的布局示意图为:答案:写出题2中当程序2扁译到r的过程体时帕勺名字表table的内容。namekindlevel/vala drsize题2中当程序编译到r的过程体时的名字表table的内容为:namekindlevel/valadrsizeXvariable0dxyvariable0dx+1pprocedure0过程p的入口（待填）5avariable1 Jdxqprocedure1过程q的入口4sprocedure1过程s的入口（待填）5cvariable2dxdvariable2dxrprocedure2过程r的入口5evariable3dxfvariable3dx+1注意：q和s是并列的过程，所以q定义的变量b被覆盖。第4题指出栈顶指针T,最新活动记录基地址指针B,动态链指针DL,静态链指针SL与返 回地址RA的用途。答案：栈顶指针最新活动记录基地址指针B,动态链指针DL,静态链指针SL与返回地址RA的用途说明如 下：T：栈顶寄存器T指出了当前栈中最新分配的单元(T也是数组S的下标)。B:基址寄存器，指向每个过程被调用时，在数据区S中给它分配的数据段起始地址，也称基地址。SL:静态链，指向定义该过程的直接外过程(或主程序)运行时最新数据段的基地址，用以引用非局部(包围它的过程)变量时，寻找该变量的地址。DL:动态链，指向调用该过程前正在运行过程的数据段基地址，用以过程执行结束释放数据空间时，恢复调用该过程前运行栈的状态。RA：返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址，用以过程 执行结束后返回调用过程时的下一条指令继续执行。在每个过程被调用时在栈顶分配3个联系单元，用以存放SL,DL,RAo第5题PL/0编译程序所产生的目标代码是一种假想栈式计算机的汇编语言，请说明该汇编语言中下列指令各 自的功能和所完成的操作。(1)INT0A(2)OPROO(3)CALL A答案：PI70编译程序所产生的目标代码中有3条非常重要的特殊指令，这3条指令在code中的位置和功能以 及所完成的操作说明如下：INT OA在过程目标程序的入口处，开辟A个单元的数据段。A为局部变量的个数+3。OPROO在过程目标程序的出口处，释放数据段(退栈)，恢复调用该过程前正在运行的过程的 数据段基址寄存器 B和栈顶寄存器T的值，并将返回地址送到指令地址寄存器P中，以使调用前的程序从断点开始继续执行。CALL A调用过程，完成填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基址寄存器B中，目标程序的入口地址A的值送指令地址寄存器P中，使指令从A开始执行。第6题给出对PL/O语言作如下功能扩充时的语法图和MSF的语法描述。(1)扩充条件语句的功能使其为：if(条件then语句else语句(2)扩充repeat语句为：repeat语句；语句 until条件答案：对PL/O语言作如下功能扩充时的语法图和EBNF的语法描述如下:(1)扩充条件语句的语法图为:EBNF的语法描述为：条件语句：:=if条件then语句else语句(2)扩充repeat语句的语法图为:语句 until条 件第3章文法和语言第1题文法 G=(A,B,S,h,b,c,P,S)其中 P 为：SAc|aBAabBbc写出L(GS)的全部元素。答案：L(GSabc第2题文法GN为:ND|NDD-*0|l|2|3|4|5|6|7|8|9GN的语言是什么？答案：GN的语言是 V+o V=0,l,2,3,4,5,6,7,&9N=ND=NDD.=NDDDD.D=D.D或者：允许。开头的非负整数？第3题为只包含数字、加号和减号的表达式，例如9-2+5,3-1,答案：GS:S-S+D|S-D|DD-0|l|2|3|4|5|6|7|8|9第4题已知文法GZJ:ZkaZblab7等构造一个文法。写出L(GZ)的全部元素。答案：Z=aZb=aaZbb=aaa.Zbbb=aaa.ab.上bbL(GZ)=anb|ri=l第5题写一文法，使其语言是偶正整数的集合。要求：$允许。打头；0不允许0打头。答案：允许0开头的偶正整数集合的文法ENT|DTNT|DN-D|1|3|5|7|9D-0|2|4|6|8不允许0开头的偶正整数集合的文法ENT|DTFT|GN-D|1|3|5|7|9D-2|4|6|8FtN|0G-D|O第6题已知文法G:v表达式：二项v表达式+V项：=v因子IV项*V因子v因子：=(v表达式)|i试给出下述表达式的推导及语法树。(5)i+(i-H)(6)i+i*i（6）v表达式=x表达式+项二表达式+项*因子=V表达式+项*i答案：（5）v表达式=表达式+项二表达式+因子=V表达式+（V表达式）二表达式+（V表达式+项）=表达式+（V表达式+因 二表达式+（v表达式+i）二表达式+（丫项+。二x表达式+（因子+i）=表达式+（i+i）=项+（i+i）=因子+（i+i）=i+（i+i）表达式,表达式+项v因子 i=v表达式+*i=V表达式+i*i=x 项+i*j=x 因子+i*i=i+i*iv表达式,V因子第7题证明下述文法G 表达式是二义的。表达式：二创（表达式）I表达式运算符表达式运算符：二+卜I叩答案：可为句子a+a*a构造两个不同的最右推导：最右推导1 表达式二？表达式运算符表达式二表达式运算符a俵达式*a二表达式运算符表达式*am表达式运算符a*a=俵达式+a*a=a+a*a表达式+a*aa+a*最右推导2 表达式表达式运算符表达式=?表达式运算符表达式运算表达=表达式运算符表达式运算式=表达式）运算符表达式*a一表达式运算a*aa文法GS为：Sf Ac|aBA一abB-bc该文法是否为二义的？为什么？答案：对于串abc(1)S=Ac=abc(2)S=aB=abc即存在两不同的最右推导。所以，该文法是二义的。或者：对输入字符串abc,能构造两棵不同的语法树，所以它是二义的。第9题考虑下而上下文无关文法：S-*SS*|SS+|a(1)表明通过此文法如何生成串aa+a*,(2)GS的语言是什么？答案：此文法生成串aa+a*的最右推导如下S=SS*=SS*=Sa*=SS+a*=Sa4-a*=aa+a*S该文法生成的语言是：*和+的后缀表达式，即逆波兰式。第10题文法 S-S(S)S|(1)生成的语言是什么？(2)该文法是二义的吗？说明理由。答案：(1)嵌套的括号(2)是二义的，因为对于()()可以构造两棵不同的语法树。第11题令文法GE为：E-AT|E+T|ETTF|TF|T/F一(助i证明E+PF是它的一个句型，指出这个句型的所有短语、直接短语和句柄。答案：此句型对应语法树如右，故为此文法一个句型。或者：因为 存在推导序列：E=E+T=E+T*F,所以E+T*F句型此句型相对于E的短语有:E+T*F;相对于T的短语 有T*F直接短语为：T*F句柄为：T*F第13题一个上下文无关文法生成句子abbaa的推导树如下:(1)给出串abbaa最左推导、最右推导。(2)该文法的产生式集合P可能有哪些元素？S(3)找出该句子的所有短语、直接短语、句柄。A B S答案：b5 a串abbaa最左推导：S=AB S=aB S=aSBB S=aBB S=abB S=abbS=abbAa=abbaa 最右推导：S=ABS=ABAa=ABaa=AS BBaa=AS Bbaa=ASbbaa=Abb aa=abbaa产生式有：SABS|Aa|e Aa BSBB|b可能元素有：aa ab abbaa aaabbaa.该句子的短语有：a是相对A的短语是相对S的短语b是相对B的短语ebb是相对B的短语aa是相对S的短语aebbaa是相对S的短语直接短语有：aeb句柄是：a第14题给出生成下述语言的上下文无关文法：(1)anbnambm|n,m=0(2)lnOm lmOn|n,m=0(3)WaWr|W 属于0|a*,表示 W 的逆答案：(1)S-AAA-AaAb|e(2)S-1SO|AAtOA1|(3)SAOSO|1S1|第16题给出生成下述语言的三型文法:(1)an|n=0(2)anbm|n,m=l(3)anbmck|n,mJ=0答案：(1)S-aS|SaAAfA|BB-bB|b(3)A-AaA|B B-AbB|C C_cC|e第17题习题7和习题11中的文法等价吗？答案：等价。第18题解释下列术语和概念：(1)字母表(2)串、字和句子(3)语言、语法和语义答案：(1)字母表：是一个非空有穷集合。(2)串：符号的有穷序列。字：字母表中的元李句子：如果Z C=x,x eV*T则称x是文法G的一个句子。(3)语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所有该语言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规则构成的一切基 本符号串组成的集合。语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。附加题问题1:给出下述文法所对应的正规式：S-OA|1BBtOS|O答案：R=(01 I 10)(01 I 10)*问题2:已知文法GA,写出它定义的语言描述GA:A-OB|1CB 1|1A|OBBC-0|0A|lCC答案：GA定义的语言由0、1符号串组成，串中。和1的个数相同.问题3:给出语言描述，构造文法.构造一文法，其定义的语言是由算符+,*,(,)和运算对象a构成的算术表达式的集合.答案一：GE EE+T|TTtT*F|FF-(E)|a答案二GE ErE+E|E*E|(E)|a问题4:已知文法GS:S-*dABA!laA|aBy|bB相应的正规式是什么？GS能否改写成为等价的正规文法？答案：正规式是daa*b*;相应的正规文法为（由自动机化简来）：GS:SAdA Afa|aB BAaB|a|b|bC CbC|b 也可为（观察得来）:GS:SfdA A-a|aA|aB问题5:已知文法G:EAE+T|E-T|TT-aT*F|T/F|FF-（E）|i试给出下述表达式的推导及语法树BbB|exz x)z 12 3 4 z(x z(v z(v z(x答案：(1)E=T=F=i(2)E=E+T=T+T=T*F+T=F*F+T=i*F+T=i*i+T=i*i+F=i*i+i(3)E=E+T=T+T=F+T=i+T=H-T*F=i4-F*F=i4-i*F=i+i*i(4)E=E+T=T+T=F+T=i+T=i4-F=i+(E尸i+(E4-T)=i+(T+T尸i+(F+T)=H(i+T)=i+(i+F)=#(i+i)(4)I可题6:已知文法GE:EET+|TT TF*|FFAFAI a试证：FP，”是文法的句型，指出该句型的短语、简单短语和句柄.答案：E该句型对应的语法树如下：该句型相对于E的短语有FF*相对于T的短语有 FF*,F相对于F的短语有F%F心 简单短语有F;FA 句柄为F.问题7:适当变换文法，找到下列文法所定义语言的一个无二义的文法：SSaSA SbS ZScSZd答案：该文法的形式很典型，可以先采用优先级联规则变换文法，然后再规定结合性对文法做进一步变换，即 可消除二义性。设a、b和c的优先级别依次增高，根据优先级联规则将文法变换为：SSaSZAA-八AbA ZCCTCcCZd规定结合性为左结合，进一步将文法变换为：S SciA.Z.AA TAhC ZCCTCcFZFFT(1该文法为非二义的。问题8:构造产生如下语言的上下文无关文法:(1)ah2rlem n,m 0(2)anhmcm iif m 0(3)ambn Z.m n(4)am bn cp dil/.m+n=p+q(5)uawh Z uw eo,A*A 11=|w|答案：(1)根据上下文无关文法的特点，要产生形如相欣的串，可以分别产生形如废浜形如f的串。设计 好的文法是否就是该语言的文法？严格地说，应该给出证明。但若不是特别指明，通常可以忽略这一点。对于该语言，存在一个由以下产生式定义的上下文无关文法GS:STABA Z aAbbcB(2)同样，要产生形如冽的串，可以分别产生形如和形如人冽/冽的串。对于该语 言，存在一个由 以下产生式定义的上下文无关文法GS:STABA s Z aA3 Z hBcc(3)考虑在先产生同样数目的a,b,然后再生成多余的a0以下GS是一种解法：S aSb Z aS Z(4)以下GS是一种解法：SaSdZAZDA-AhAdZBD aDc Z BB hBc Z 8注：a不多于d时，b不少于c;反之，a不少于d时，b不多于c。前一种情形通过对应A,后一种情 形对应Do(5)以下GS是一种解法：St AbA B4B Z a问题9:下而的文法G(S)描述由命题变量p、q,联结词A(合取)、v(析取)、(否定)构成的命题公 式集合：StSvTZ tT-Ta FZ FF-iF Zp Zq试指出句型的直接短语(全部)以及句柄。答案：直接短语：p,q,iF句柄:-iF问题10:设字母表人=忸,符号串x=aaa,写出下列符号串及其长度：0,xx,x5以及A+.答案：x=(aaa)=|x|=0 xx=aaaaaa|xx|=6x5=aaaaaaaaaaaaaaa|x5|=15A+=A*U A2 U.U AnU.=a,aa,aaaAaaaa,aaaaa.A*=A0 U A1 U A2 U.U An U.=,a,aa,aaa,aaaa,aaaaa.问题11：令E=a,b,c,又令x=abc,y=b,z=aab,写出如下符号串及它们的长度：xy,xyz,(xy)3答案：xy=abcb|xy|=4xyz=abcbaab|xyzj=7(xy)3=(abcb)3=abcbabcbabcb|(xy)3l=12问题12:已知文法GZ:Z:=U0|VI U:=Z1|1 V:=Z0|0,请写出全部由此文 法描述的只含有四个符号的句子。答案：Z=UO=Z 10=U010-1010Z=UO=Z 10=VI 10=0110Z=V1=ZOO=UOOO=1000Z=V1=Z00=Vl 00-0100问题13:已知文法GS:S:=AB A:=aA|EB:=bBc I be，写出该文法描述的语言。答案：A:=aA|描述的语言：叫!1=0B:=bBc I be描述的语言:L(GS)=anbmcra|n=O,m=l问题14:已知文法 E:=T|E+T|ET T:=F|TF I T/F F:=(E)|i,写出该文法的开 始符号、终结符号集合v,非终结符号集合VN。答案：开始符号：EV尸+,，*,/,(,),iVn=E,F,T问题15:设有文法GS:S:=S*S|S+S|(S)|a,该文法是二义性文法吗？答案：根据所给文法推导出句子a+a*a,画出了两棵不同的语法树，所以该文法是二义性文法。问题16:写一文法，使其语言是奇正整数集合。答案：A:-1|3|5|7|9|NANN0|Nl|N2|N3|N4|N5|N6|N7|N8|N9|N-0|l|2|3|4|5|6|7|8|9第4章词法分析构造下列正规式相应的DFA.(1)1(0|1)*101(2)1(1010*11(010)*1)*0(3)a(a|b)*|ab*a)*b(4)b(ab)*|bb)*ab答案：先构造NFA:用子集法将NFA确定化01XAAAABABACABACAABYABYACAB除X,A外，重新命名其他状态，令AB为B、AC为C、ABY为D,因为D含有Y（NFA的终态），所以D 为终态。01XAAABBCBCADDCBDFA的状态图：先构造NFA:用子集法将NFA确定化01XXTo=XAAABFLT=ABFLYCGYYCGCGJT2=YT3=cgjDHKDHDHKABFKLT4=DHElElABEFILT5=abfklYCGT6=abefilEJYCGEJYABEFGJLYT7=abefgjlyEHYCGKEHYABEFHLYCGKABCFGJKLT8=abefhlyEYCGIEYABEFLYCGICGJIT9=abcfgjklDHYCGKDHYDHYTjo=abeflyEYCGTh=CGJIDHJKDHJDHJTJ2=DHYElT3=DHJEIKEIKABEFIKLTj4=ABEFIKLEJYCG将 To、Ti、T2、T3、T4、T5、丁 6、丁 7、丁 8、T9、T10、Til T12、T13、T14 重新命名，分别用 0、1、2、3、4、5、6、7、8、9、10、11、12、13、14 表示。因为 2、7、8、10、12 中含有 Y,所以它们都为 终态。01011232345465236737898101191291010311135126131414730先构造NFA:将To、Ti、T2 T3、T4 T5重新命名，分别用0、1、2、3、4、5表示。因为3、5中含有Y,所以它们都为用子集法将NFA确定化abXXTo=XAAABCDTj=ABCDBEBYBEABCDEBYABCDYT2=ABCDEBEFBEYBEFABCDEFBEYABCDEYT3=A BCDYBEBYT4=ABCDEFBEFBEYT5=A BCDEYBEFBEY终态。ab011232453234455450先构造NFA:用子集法将NFA确定化:8abXXTo=XAAABDEFTj=ABDEFCIGCICIGGT2=CIDYDYABDEF YT3=GHHABEFHT4=ABDEFYCIGT5=ABEFHCIG将T。、Ti、T2、T3 T4 T5重新命名，分别用0、1、2、3、4、5表示。因为4中含有Y,所以它 为终态。ab011232435423523DFA的状态图:已知 NTA=(x,%z,0J,M4x,z)淇中:M(x,O)=z,M(y,O)=x9y9,M(z9O)=x9z9 M(xJ)=x,M(y?l)=xz、y、xyxyz重新命名，分别用A、B、C、D、E、F表示。因为B、C、F中含有z,所以它为 终态。01ABABCDCCEDEEFAFFEDFA的状态图:第3题将下图确定化:答案：用子集法将NFA确定化:01SVQQUVQVZQUQUVQUZVZZZVZQUZVZQUZZZZ重新命名状态子集，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。01SABACBBDECFFDFECEFFF将下图的（Q和（b）分别确定化和最小化:答案:初始分划得no:终态组0,非终态组123,4,5对非终态组进行审查：l,2,3,4,5aJ0,l,3,5而0,1,3,5既不属于0,也不属于1,23,4,5 4aj0,所以得到新分划ni:0,4,1,2,3,5对1,2,3,5进行审查：L5bJ42,3bjl,2,3,5,故得到新分划n2:0,4,1,5,2,3l,5aul,52,3 ajl,3,故状态2和状态3不等价，得到新分划n3:0,2,3,4,1,5这是最后分划了最小DFA：第5题构造一个DFA,它接收=0,1上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该 语言的正规式。答案：按题意相应的正规表达式是（0*10）*0*,或0*（0|10）*0*构造相应的DFA,首先构造NFA为用子集法确定化:I10IIX,0,l,3,Y0 3,Y（2）0,l,3,Y0,l,3,Y（2）（2）1,3,Y1,3,丫1.3,Y2重新命名状态集:S0112322334443可将该DFA最小化：终态组为1,2,4,非终态组为,1,2,40 1,2,4,1,2,4 1 3,所以1,2,4为等价状态，可合并。设无符号数的正规式为e:6 二 dd*|dd*.dd*|.dd*|dd*10(s|w)dd*|10(s|E)dd*|.dd*10(s E)dd*|dd*.ddlO(s|)dd*化简0,画出 的 DFA淇中 d二0,1,2,9,s=+,-答案：先构造NF A:用子集法将NFA确定化:s10dXXATo=XABFABBFFGAATj=BCCCT2=FGGHGGHHT3=ABFAT4=CDCDDET5=GHT6=HHT7=DEEYEEYYT=EYT9=YY将 XA、B、FG.A、O G.H.DE、E、Y 重新命名，分别用 0、l、2、3、4、5、6.7、8、9 表示。终态有 0、3 4、6、9os10d012314256312347456667898999d第7题给文法GS:S-*aA|bQ Af A|bB|b BbD|aQQrQ|bD|b D*bB|aA EAaB|bFFbD|aE|b构造相应的最小的DFAo答案：先构造其NFA:用子集法将NFA确定化:将S、A、Q、BZ、DZ、D、B重新命名，分别用0、l、2、3、4、5、6表示。因为3、4中含有z,所以 它们为终态。abSAQAABZQQDZBZQDDZABDABBQDDFA的状态图:ab012113224325416516625a令 Po=(0,125,6,3,4)用 b 进行分割：Pi=(0,5,6,1,2,3,4)再用 b 进行分割:P2=(0,5,6,1,2,3,4)再用 a、b 进行分割，仍不变。再令 0 为 A,1,2为 B,(3,4 为C5,6为D。最小化为：第8题给出下述文法所对应的正规式：SOA|1BA1S|1B-OS|O答案：解方程组s的解：S=OA|1BA=1S|1B=OS|O将A、B产生式的右部代入S中S=01S|01|10S|10=(01|10)S|(01|10)所以：S=(01|10)*(01|10)第9题 将下图的DFA最小化，并用正规式描述它所识别的语言。aa令 Po=(123,4,5,6,7)用 b 进行分割：Pi=(1,2,3,4,5,6,7)再用 a、b、c、d进行分割,仍不变。B,5为 C,6,7为 Do最小化为：再令1,2为A,3,4为r=b*a(c|da)*bb*=b*a(c|da)*b+附加题问题1:为下边所描述的串写正规式，字母表是%的命以ab结尾的所有串耳包含偶数个b但不含a的所有串0包含偶数个b且含任意数目3的所有串0只包含一个发的所有串9包含ab子串的所有串f不包含ab子串的所有串答案：注意正规式不唯一a)(a|b)*abb)(bb)*c)(a*ba*ba*)*d)b*ab*e)(a|b)*ab(a|b)*f)b*a*问题2:请描述下而正规式定义的串-字母表0,1.a)0*(10+)*0*b)(0|1)*(00|11)(0|1)*c)1(0|1)*0答案：a)每个1至少有一个0跟在后边的串b)所有含两个相继的0或两个相继的1的串c)必须以1开头和。结尾的串问题3:构造有穷口动机.岔构造一个DFA,接受字母表.I)构造 0,1上的以01结尾的所有串一个DFA,接受字母表.0,1上的不包含01子串的所有串.0构造一个NFA,接受字母表.x,y上的正规式x(x|y)*xffi述的集合4构造一个NFA,接受字母表 8,b上的正规式(ab|a)*缺描述的集合并将其转换为等价的DFA 以及最小状态DFA答案:aa最小化的DFA问题4:设有如图所示状态转换图,求其对应的正规表达式。可通过消结法得出正规式R=(01)*(0011)(011)*|0)也可通过转换为正则文法，解方程得到正规式。问题5:已知正规式：(1)(a|b)*|aa)*b;(2)(a|b)*b.试用有限口动机的等价性证明正规式(1)和(2)是等价的，并给出相应的正规文法。分析：基本思路是对两个正规式，分别经过确定化、最小化、化简为两个最小DFA,如这两个最小DFA 一样，也就证明了这两个正规式是等价的。答案:状态转换表1abXI241234124Y12341234124Y124Y1234124Y状态转换表2ab12323而对正规式(2)可画NFA图，如图所示。abX121212Y121212Y12Y1212Y可化简得下表得DFA图两图完全一样，故两个自动机完全一样，所以两个正规文法等价。对相应正规文法，令A对应1,B对应2故为：AaA|bB|bBfaA|bB|b即为SaS|bS|B,此即为所求正规文法。问题6:考虑正规表达式r=a*b(a|b),构造可以生成语言L(r)的一个正规文法。答案：S T a*b(a|b)变换为 S T aA,S b(a|b),A T aA,A-b(a|b)变换为 S aA,S bB,B(a|b),A aA,A bC,C-(a|b)变换为 S aA,S 少 bB,B 少 a,B 少 b,A 少 aA,A)bC,C)所以，一个可能的正规文法为GS:S aA,S bB,B a,B b,A aA,A bC,C a,C/b或表示为：S T aA|bB,B-a|b,A T aA|bC,C-a|b(适当等价变换也可以，但要作说明，即要有步骤)问题7:考虑下图所示的NFAN,构造可以生成语言L(N)的一个正规文法。GP：PAOPZIPZIQQt 0RZ1 RR-8问题8:考虑如下文法GS:S T OS/1SZ1AA-0BZ1BB)a)试构造语言为L(G)的一个正规表达式。b)试构造语言为L(G)的一个有限口动机。答案:由 A-OB,B)由 A-IB,B、得 AtO;得 At 1;由 A-0,At 1得 AtO Zl;由S-1A,AtOZI得 St 1(OZ1);由 S-1A,AtOZI 得 由 St OS,StI(OZI)得 StO*1(OZ1);St 1(0 Zl);由 S-IS,StI(OZI)得 StPI(OZI);由 S-0*1(0 XI),St1*1(0Z1)得O*1(OZ1)Z1*1(OZ1);所以，一个可能的正规表达式为:0*1(0Z1)Z1*1(OZ1)b)第5章自顶向下语法分析方法对文法GSSAa|A|(1)T-T,S|S给出(a,(a,a)和(盼)，八，何)，町的最左推导。0对文法G,进行改写，然后对每个非终结符写出不带回溯的递归子程序。经改写后的文法是否是LL(1)的?给出它的预测分析表。9给出输入串(#)#的分析过程，并说明该串是否为G的句子。答案：(1)对(a,(a,a)的最左推导为:S=(T)=(T,S)=(S,S)=(a,S)二(而功=(a,(1S)=(a,(S,S)=(a,(a,S)zz(a,(a,a)对(他a),A,(a),a)的最左推导为:S=(T)=(1S)=(S,S)G(T),S)=(1S),S)=(T,S,S),S)(S,S,S),S)=(T),S,S),S)=(T,S),S,S),S)(S,S),S,S),S)=(a,S),S,S),S)=(a,a),S,S),S)B(a,a),A,S),S)-(a,a),A,C*,S)=(a,a)A(S),S)盛威网()7?业的计算机学习网站(2)改写文法为:0)Sa1)StA2)St(T)3)TtSN4)Nt,S N5)Nt非终结符FIRST 集FOLLOW 集S#,”)T)N)对左部为N的产生式可知：FIRST(f,SN)=,FIRST()=FOLLOW(N)=)由于 SELECT(N S N)ASELECT(N)=,C )Z 所以文法是 LL(1)的。预测分析表(Predicting Analysis Table)也可由预测分析表中无多重人口判定文法是LL的。aA()#Sa-(T)TtSNtSNtSNNSN(3)对输入串(篇a)#的分析过程为:栈(STACK当前输入符(CUR CHAR)剩余输入符(INOUTSTRING)所用产生式(OPERATION)#S(a,a)#Si(T)#)T(a,a)#)Ta,a)#TSN#)NSa,a)#Sa#)Naa,a)#)Na)#NSN#)NS,a)#)NSa)#Sa#)Naa)#)N)#Nt#)#11#可见输入串(a,a)#是文法的句子。盛威网()匕业的计算机学习网站已知文法GS:S-AMH|aHtLSo|KdML|LeHfMKIbLM判断G是否是LL(1)文法，如果是，构造LL(1)分析表。答案:文法展开为：0)SMH1)Sa2)HtLSo3)Hf4)KdML5)KF6)LeHf7)M-K8)MbLM非终结符FIRST 集FOLLOW 集S a,d,b,e,e#,0Md,8,b)e,#,oHs,e#,。Lea,d,b,e,o,#Kd同对相同左部的产生式可知：SELECT(StM H)ClSELECT(SAa)=d,b,e,#,oA a=0 SELECT(HfL S o)nSELECT(H-Ae)=e C1#,o=0 SELECT(Kd M L)ASELECT(K-Ae)=d A e,#,o SELECT(MAK)ASELECT(MAb LM)=d,e,#,o C1 b=E 所以文法是 LL(1)的。预测分析表:由预测分析表中无多重人口也可判定文法是LL(1)的。a0defb#SaMHMHMHMHMHM-KK-KbLMtKH8LSo*88L-eHfKidML88第7题对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法?试对下而文法