哈工大编译原理习题及答案.pdf-淘文阁

资源描述

《哈工大编译原理习题及答案.pdf》由会员分享，可在线阅读，更多相关《哈工大编译原理习题及答案.pdf（129页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、1.1 何谓源程序、目标程序、翻译程序、编译程序和解释程序？它们之间可能有何种关系？1.2 一个典型的编译系统通常由哪些部分组成?各部分的主要功能是什么？1.3 选择一种你所熟悉的程序设计语言，试列出此语言中的全部关键字，并通过上机使用该语言以判明这些关键字是否为保留字。1.4 选取一种你所熟悉的语言，试对它进行分析，以找出此语言中的括号、关键字END以及逗号有多少种不同的用途。1.5 试用你常用的一种高级语言编写一短小的程序，上机进行编译和运行，记录下操作步骤和输出信息，如果可能，请卸出中间代码和目标代码。第一章习题解答1.解：源程序是指以某种程序设计语言所编写的程序。目标程序是指编译程序(

2、或解释程序)将源程序处理加工而得的另一种语言(目标语言)的程序。翻译程序是将某种语言翻译成另一种语言的程序的统称。编译程序与解释程序均为翻译程序，但二者工作方法不同。解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入卜一条语句继续进行解释、执行，如此反复。即边解释边执行，翻译所得的指令序列并不保存。编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。即先翻译、后执行。2.解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、

3、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。3.解：C 语言的关键字有：auto bre ak case char const continue de fault do double e lse e num e xte rnfloat for goto if int long re giste r re turn short signe d size of static struct switch type de f union unsigne dvoid volatile while。上述关键字在C 语言中均为保留字。4.解：C 语言中括号有三种：,()。其中，什用

4、于语句括号；口用于数组；()用于函数(定义与调用)及表达式运算(改变运算顺序)。C 语言中无END关键字。逗号在C 语言中被视为分隔符和运算符，作为优先级最低的运算符，运算结果为逗号表达式最右侧子表达式的值(如：(a,b,c,d)的值为 d)o5.略第二章前后文无关文法和语言21设有字母表A 1=a,b,z,A2=0,1,-.9),试回答下列问题:(1)字母表A1上长度为2 的符号串有多少个？(2)集合A1A2含有多少个元素？列出集合A 1(A1UA2)*中的全部长度不大于3 的符号串22试分别构造产生下列语言的文法。(1)anbn|nO；(2)anbmcp|n,m,p 0 ；(3)an#b

5、n|n O U cn#dn|nO；(4)w#wr#|we 0,1)*,wr是将w中的符号按逆序排列所得的符号串；(5)任何不是以0开始的所有奇整数所组成的集合；(6)所有由偶数个0和偶数个1所组成的符号串的集合。2 3试描述由下列文法所产生的语言的特点(文法的开始符号均为S)。(1)S TOSOSf aA A f bA A-a(2)S-SSS-1 A 0 A-1 A 0 A-e(3)S-1 A S-B OA-1 A A-CB-B OB C C-1 C 0 C-e(4)S-bA dcA f A G SG f e A-a(5)Sf aSSSf a2 4设已给文法G=(VN,VT,P,S),其中：V

6、N=(S)VT=a1,a2,an,V,A,L,)P=(S-ai|i=1,2,n)U(S-S,S-SVS,S-SA S ,试指出此文法所产生的语言。2 5考察文法G=(VN,VT,P,S),其中：VN=S,A,B,C,D,E,F,G VT=a,P=Sf A B C,C-B C,C-A,B A-G E,B G-G B F,A G-A D,D B-B D,D E-A E,F B-B F,F E-E a,A A e)(1)指出此文法的类型；(2)证明此文法所产生的语言为L(G)=at (n)|nN 1 t(n)=E n i=1 i2 6设已给文法G 程序:程序一分程序I 复合语句分程序一无标号分

7、程序I 标号：分程序复合语句一无标号复合语句I 标号：复合语句无标号分程序一分程序首部；复合尾部)无标号复合语句一beg i n 复合尾部分程序首部一beg i n 说明|分程序首部；说明复合尾部一语句end|语句；复合尾部说明 d 语句f s 标号一L(1)给出句子L:L:beg i n d;d;s;s end的最左推导和最右推导。(2)画出上述句子的语法树。2 7设已给文法G S：S f aAcBSf BdSBaScAB-cABA f BaBAaB cA-aB-*b试检验下列符号串中哪些是G S 中的句子，给出这些句子的最左推导、最右推导和相应的语法树。(1)aacb(2

8、)aabacbadcd(3)aacbccb(4)aacabcbcccaacdca(5)aacabcbcccaacbca2 8设G=(VN,VT,P,S)为CFG,a 1,a 2,，a n为V上的符号串，试证明：若a 1 a 2 a n*B则存在V上的符号串B1,B 2,，B n,使8=B 1 B 2 B n,且有a i*P i(i=1,2,n)2 9设G=(VN,VT,P,S)为CFG,a和B都是V上的符号串，且a*B,试证明：当a的首符号为终结符号时，B的首符号也必为终结符号；当8的首符号为非终结符号时，则a的首符号也必为非终结符号。210试证明：文法S-A B S-D C A f a A

9、A f aB-b B c B-b c C-c C C cD f aDbDf ab为二义性文法。211对于下列的文法和相应的句子，试指出这些句子的全部短语；分别给出句子的最右推导，并指出各步直接推导所得句型的句柄。(1)S-A B S-c A f b A A f a B f aS bB f cbbaacb(2)S-(A S)S-(b)A-(S a A)A-(a)(b)a(a)(b)(3)E f E T+E-T T-T F*T f FF-FP t F-P P-E P ii i i*i+t212在自底向上的分析中，用来归约句型句柄的产生式称为句柄产生式。试证明：一个文法是无二义性的，当且仅当此文法的

10、每一句型至多只有一个句柄和一个句柄产生式。213化简下列各个文法。(1)S-a A B S S f bCACdA-bABA-cSAA-*cCCB-bABB-*cSBC f cSC-c(2)S-a A B S f E A f dDAAfeB-b E B-fC-c A B C f dSDC f a D f e A E f fA E f g(3)S-a c S-b A A f cBCBf SAC-b C C-d214消去下列文法中的e产生式。(1)S-a A S S f b A-c S A f e(2)S-aA A A-bA cA-dA eA-e215消去下列文法中的无用产生式和单产生式。(1)Sf

11、 a B Sf B C A f a A A f cA f a D b B f DB B-C D-BCi(2)Sf SA S-SB A-B B-SA-(S)S-A B f A-()(3)Ef E+TE-TT-T*F Tf FF f P t F F PP-(E)Pf i第二章习题解答1.答:26*26=676(2)答：26*10=260 答：a,b,c,.,z,a 0,a l,.,a 9,a a,.,a z,.,z z,a OO,a Ol,.,z z z ,共26+26*36+26*36*36=34 658 个2.构造产生下列语言的文法(1)a n b n|n O解：对应文法为 G(S)=(S,a

13、,2,3,4,5,6,7,8,9 ,S-J|I B J,B-OB|I B I e,I-J|2|4|6|8,Ja l|3|5|7|9),S)（6）所有偶数个0 和偶数个1所组成的符号串集合解：对应文法为 S-OA llB le,A-*OS|1C B-OC|1S C-1A|OB3.描述语言特点(1)S-lOSOS-a A A-b A A-a解:本文法构成的语言集为：L(G)=(10)n a b m a On|n,m0。(2)S SS S-1A 0A-1A 0A-*e解：L(G)=ln l0n lln 20n 2 I n m On m|n l,n 2,n m O；且 n l,n 2,n m 不全为零

14、该语言特点是：产生的句子中，0、1个数相同，并且若干相接的1后必然紧接数量相同连续的0。(3)S-1A S-B 0A-1A A-C B-B 0B-C C-1C 0C-e解：本文法构成的语言集为：L(G)=lp ln On|pL n0 U ln On Oq|q e l,n0,特点是具有I p ln On或I n On Oq形式,进一步，可知其具有形式I n Om n,m0,且n+m 0。(4)S-b A d c A f A G SG-e A-a解：可知,S=b a Sn d c n 0该语言特点是：产生的句子中，是以b a开头d e结尾的串，且b a、d e个数相同。(5)S-a SSS-*

15、a解：L(G)=a(2n-l)I n Nl可知：奇数个 a4.解：此文法产生的语言是：以终结符a l、a 2-an为运算对象，以A、V、为运算符，以、为分隔符的布尔表达式串5.5.1解：由于此文法包含以下规则：A A-e,所以此文法是0型文法。5.2证明：略6.解：(1)最左推导：程序 T 分程序 T：分程序TL：分程序TL：标号：分程序T L：L：分程序T L：L：无标号分程序T L：L：分程序首部；复合尾部T L：L：分程序首部；说明；复合尾部）T L：L：b e g i n 说明；说明；复合尾部T L：L：b e g i n d；说明；复合尾部T L：L：b e g i n d；d；复合

16、尾部T L：L：b e g i n d；d；语句；复合尾部T L：L：b e g i n d；d；s；复合尾部.T L：L：b e g i n d；d；s；语句）e n dT L：L：b e g i n d；d；s；s e n d最右推导:程序 T 分程序 T 标号：分程序T 标号：标号：分程序T 标号：标号：无标号分程序T 标号:标号：分程序首部；复合尾部）T 标号:标号：分程序首部；语句；复合尾部T 标号：标号：分程序首部：语句；语句；e n dT 标号）:标号：分程序首部）；语句；s；e n dT 标号:标号:分程序首部）;s；s；e n d以标号：标号：分程序首部）；说明；s；s；e

17、n dT 标号）:标号：分程序首部；d；s；s；e n dT 标号：标号：b e g i n 说明；d：s；s；e n dT 标号：标号：b e g i n d；d；s；s；e n d丁标号)：L：b e g i n d；c l；s；s；e n dTL：L：b e g i n d；d：s：s；e n d(2)句子L：L：b e g i n d；d；s；s e n d的相应语法树是:7.解:a a c b是文法G S中的句子，相应语法树是:最右推导：S=a A c B=a A c b=a a c b最左推导：S=a A c B=a a c B=a a c b(2)a a b a c b a

18、d c d 不是文法G S 中的句子因为文法中的句子不可能以非终结符d 结尾(3)a a c b c c b 不是文法G S 中的句子可知，a a c b c c b 仅是文法G$的一个句型的一部分，而不是一个句子。(4)a a c a b c b c c c a a c d c a 不是文法G S 中的句子因为终结符d 后必然要跟终结符a,所以不可能出现d e 这样的句子。(5)a a c a b c b c c c a a c b c a 不是文法G S 中的句子由(1)可知：a a c b 可归约为S,由文法的产生式规则可知，终结符c 后不可能跟非终结符S,所以不可能出现c a a c

19、b 这样的句子。8 .证明:用归纳法于n,n=l时，结论显然成立。设 n=k时对于 a 1 a 2 a kT*b,存在 B i：i=l,2,.,k,a i T*b i 成立，现在设a 1 a 2.a ka k+lT*b,因文法是前后文无关的，所以 a 1 a 2.a k 可推导出b的一个前缀b ,a k+1可推导出b的一个后缀=b”(不妨称为b k+1)。由归纳假设，对于b,存在 B i ：i=l,2,.,k,b =B 1 B 2.B k,使得a i T*b i 成立，另夕卜，我们有a k+lT*b”(=b k+1),即n=k+l时亦成立。i E毕。9 .证明：(1)用反证法。假

20、设 a首符号为终结符时，P 的首符号为非终结符。即设：a=a 3；p=A W且 a=*B。由题意可知：a=a 3 T T A 3,=p,由于文法是C F G,终结符a 不可能被替换空串或非终结符，因此假设有误。得证；(2)同(1),假设 P的首符号为非终结符时，a首符号为终结符。即设：a=a 3；B=A 3 且 a=a 3 T TA 3 =6,与(1)同理，得证。1 0.证明：因为存在句子：a b c,它对应有两个语法树(或最右推导)：S T A B T A b e T a b eS T DC T Dc T a b c所以，本文法具有二义性。11.解:(1)STABTAaSbTAacbTb

21、AacbTbbAacbTbbaacb上面推导中，下划线部分为当前句型的句柄。对应的语法树为:全部的短语：第一个a(a l)是句子bbaacb相对于非终结符:A(A l)(产生式A?a)的短语(直接短语)；bl a l是句子bbaacb相对于非终结符A2的短语；b 2 b la l是句f-bbaacb相对于非终结符A3的短语;c是句子b b a a c b相对于非终结符$1 (产生式S?c)的短语(直接短语)；a 2 c b 3是句子b b a a c b相对于非终结符B的短语；b 2 b la la 2 c b 3是句子b b a a c b相对于非终结符S 2的短语；注：符号的卜标是为了描述

22、方便加上去的。(2)句子(b)a (a)(b)的最右推导：S T (A S)T (A (b)T (S a A)(b)T (S a (a)(b)T (b)a (a)(b)相应的语法树是：(3)解：i i i*i+t对应的语法树略。最右推导：E T T=F=FP t T FE t T FET+t T FEF+t T FEP+t T FEi+tT FT i+t T FT F*i+t T FT P*i+f T FT i*i+t T FFi*i+t T FP i*i+tT Fi i*i+t T P i i*i+f T i i i*i+t1 2.证明:充分性：当前文法下的每一符号串仅有一个句柄和一个句柄

24、 5 .消除下列文法中的无用产生式和单产生式(1)消除后的产生式如下：S-a B|B CB-DB|bCiD i|DB(2)消除后的产生式如下：S-S A|S B|()|(S)I D|S A T)|(S)|S B a S(3)消除后的产生式如下：E-E+T|T*F|(E)|P t F|iT-T*F|(E)|P t F|iF-P t F|(E)|iP T E)|i第三章词法分析及词法分析程序3.1试用某种高级语言编写一个FORTRAN源程序的预处理子程序，其功能是：每调用它一次，即把源程序中的一个完整语句送入扫描缓冲区。要求删去语句中的注释行;删去续行标记字符，把语句中的各行连接起来，并在语句的末

25、端加上语句结束符。此外，还要求此程序具有组织源程序列表输出的功能。3.2画出用来识别如下三个关键字的状态转移图。STEP STRING SWITCH3.3假定有一个猎人带着一只狼、头山羊和一棵白菜来到条河的左岸，拟摆渡过河，而岸边只有一条小船，其大小仅能装载人和其余三件东西中的一件，也就是说,每一次猎人只能将随行者中的一件带到彼岸。若猎人将狼和山羊留在同一岸上而无人照管，那么，狼就会将羊吃掉；如果猎人把山羊和白菜留在同一岸，山羊也会把白菜吃掉。现在，请你用状态转换图作为工具，描述猎人可能采取的种种摆渡方案，并从中找出可将上述三件东西安全地带到右岸的方案来。3.4设已给文法G=(V N,V T,

26、P,S),其中,P仅含形如A-a BA-a a V*T,BVN的产生式，试证明：由此种文法所产生的语言是一正规语言。3.5试证明：任何有限个符号串所组成的集合L=xl,x3,xnxi e +都是3型语言。3.6试构造一右线性文法，使得它与如卜的文法等价S-ABAUTUf a|aUT-b|bT B-c|cB并根据所得的右线性文法，构造出相应的状态转换图。3.7对于如题图37所示的状态转换图(1)写出相应的右线性文法；(2)指出它接受的最短输入串；(3)任意列出它接受的另外四个输入串；(4)任意列出它拒绝接受的四个输入串。题图373.8对于有限自动机M=(K,S,f,SO,Z)其中,K=SO)

27、S1,S2,S3,S4,S5),S=a,b,Z=Sl,S4,S5.f由如下的状态转移矩阵给出：a b S 0 S 2 S l S l S 3 S l S 2 S 0 S 4 S 3 S 0 S 0 S 4 S 5 S 4 S 5 S 4 S 0试找出一个长度最小的输入串，使得：(1)在识别此输入串的过程中，每一状态至少经历一次；(2)每一状态转换至少经历一次。3.9 对于下列的状态转换矩阵：口 a b S A S A A B B B B(i)初态:S终态：B a b S A B A B A B B B(i i)初态：S终态：A a b S A B A C A B B C C n C C(i

28、i i)初态：S终态：A,C a b S A S A C B B B C C C C(i v)初态：S终态：C(1)分别画出相应的状态转换图；(2)写出相应的3 型文法；(3)用自然语言分别描述它们所识别的输入串的特征。3.1 0 对于下面所给的文法：G 1=(S,A,B,C,D ,a,b,c,d ,P l,S)P l 由如下产生式组成：S a A S f B A f a b SA b B B b B c CC-D D-*d D-*b B以及 G 2=(S,A,B,C,D),a,b,c,d ,P 2,S)P 2 由如下产生式组成：S f A a S C cA-B b B-*B b B-aC-D

29、 C-B a b D-d(1)试分别对G 1 和 G 2 构造相应的状态转换图(提示:对于右线性文法,可将形如C D的产生式视为C-e D；而对左线性文法，则可将它视为C-D e)。(2)对于G 1,构造一等价的左线性文法G 1 ；对于G 2 构造一等价的右线性文法G 2 。(3)对于G 1 和 G J ,分别给出如卜符号串的推导序列：a b b a a b a b b b c d c b b对于G 2 和 G 2 分别给出如下符号串的推导序列：a a b a a a b c a d c a(4)试给出若干个不能由G 1 或 G 2 产生的符号串，并验证它们同样不能用G 1 和 G 2 产生。

30、3.1 1 分别构造将左线性文法转换为右线性文法以及将右线性文法转换为左线性文法的算法。3.1 2 将如题图3 1 2 所示的N F A 确定化和最小化。题图3 1 23.1 3将如题图3 1 3所示的具有e动作的N F A确定化。题图3 1 33.1 4将如题图3 1 4所示的有限自动机最小化。3.1 5试用一种高级语言分别写出将N F A确定化以及将D F A最小化的算法。3.1 6构造一产生F O R T R A N语言C O M M O N语句的3型文法(假定分别用人和口代表标识符和整常数，它们都是终结符号，且假定数组的维数不加限定)，构造相应的D F A,并写出描述C O MMO N

31、语句的正规式。3.1 7设r,s等为任意的正规式，试证明下列的关系式成立：(1)r*=(e!r)*=e r r*=(r*)*(2)(r s)*r=r(s r)*(3)(r|s)*=(r*s*)*=(r*|s*)*3.18对于解习题3 6所得的文法，试用正规式描述它所产生的语言。a bS 0 S l S 5S l S 2 S 7S 2 S 3 S 5S 3 S 5 S 7S 4 S 5 S 5S 5 S 3 S 1S 6 S 3 S O S 7 S O S 1S 8 S 3 S 8(1)初态：S O终态：S I,S 2,S 6,S 7 a bS 0 S 5 S 2S l S 6 S 2S 2 S

32、 0 S 4S 3 S 3 S 5S 4 S 6 S 2S 5 S 3 S 0 S 6 S 3 S 1(2)初态：S O终态：S 4,S 5,S 6题图3143.19对于习题310所给的文法G 1和G 2,试分别用正规式描述它们所产生的语言。3.2 0设有如下的文法G 标号说明:标号说明一 L ABEL 标号表标号表一d 标号段)标号段一d 标号段I,标号|；标号一d 标号段其中LA B E L d等为终结符号。(1)试求出描述此文法所产生语言的正规式；(2)构造识别此语言的具有最少状态的D F A。3.2 1求出描述习题3 7所给有限自动机所识别语言的正规式。3.2 2分别构造识别如下正规

33、语言的D F A：(0*|1)(1*0)*(2)(b|a(aa*b)*b)*(3)a(abab*|a(bab)*a)*b(4)(b|aa|ac|aaa|aac)*(5)a(a|b)*b(a|b)*a(a|b)*b(a|b)*3.23试设计一个识别器，它识别由下列英语单词：O NE,TW O,THR E E,，NINE,TE N,E LE V E N,TW E LV E,THIR TE E N,，NINE TE E N,TW E NTY,THIR TY,F O R TY,，NINE TY,HU ND R E D所表示的从1到 9 9 9 间的任何整数（各单词间用空格分隔,如THR E E HU

34、ND R E D F IF TYS IX）,并将它们翻译为相应的阿拉伯数字（如 356）作为输出。3.24 设有辅助定义式D 0=a|bD 1=D O D OD 2=D 1D 1D n=D n-lD n-l试回答如卜问题：（1）由D n 所表述的正规集是什么？（2）如果将D n 中所出现的D n-1用前面已定义的辅助定义式反复进行替换，则可最终将 D n 化为 =a,b 上的正规式，此正规式有多长？（3）用来识别D n 的D F A 至多需要几个状态？3.25试将LE X 中的“动作子程序”A i 的功能加以扩充，使之可用来生成文本编辑程序。3.26 指出下列LE X 正规式所匹配的字符串：

35、*（2）a-z A-Z 0-9$-0-9 ：r n （口 n、）+（L n E n ）*3.27写出一个LE X 正规式，它能匹配C 语言的所有无符号整数（例如：O X 89 ab,0 123,45,7,t,xab 0 12,等等）。3.28写出一个LE X 正规式，它能匹配C语言的标识符。3.29 编写一个LE X 源程序,它将一个正文文件中的全部小写字母均换为大写字母,并将其中的制表字符、空白字符序列均用单个空格字符进行替换（提示：在语义动作中使用全程变量yytex t）。3.3 0 编写一个LE X 源程序,它能统计一个P A S C A L程序中所含用户定义之标识符个数，并能找出最长标

36、识符中的字符个数（提示：使用全程变量yytex t及 yyleng）。上机实习题对于如下文法所定义的P A S C A L语言子集，试编写并上机调试一个词法分析程序：程序变量说明B E G I N 语句表E N D.变量说明-V A R 变量表：类型；|空)变量表一变量表，变量I 变量类型-I N T E G E R 语句表一语句表；语句I 语句语句一赋值语句)|条件语句|W H I LE 语句|复合语句|过程定义赋值语句一变量：=(算术表达式条件语句一I F 关系表达式T H E N 语句E LS E 语句 W H I LE 语句-W H I LE(关系表达式D O

37、语句复合语句-B E G I N 语句表E N D 过程定义-P R O C E D U R E 标识符参数表；B E G I N 语句表E N D 参数表一(标识符表)1 空标识符表一标识符表，标识符I 标识符算术表达式一算术表达式+项|项项一项*初等量|初等量初等量一(算术表达式)1 变量I 无符号数关系表达式一算术表达式关系符算术表达式变量一标识符标识符一标识符字母I 标识符数学I 字母无符号数一无符号数数字I 数字关系符-=|=|字母/A|B|C|X|Y|Z 数字-O i l|8|9 空一要求和提示：(1)单词的分类。可将所有标识符归为一

38、类；将常数归为另一类；保留字和分隔符则可采取一词一类。(2)符号表的建立。可事先建立一保留字表，以备在识别保留字时进行查询。变量名表及常数表则在词法分析过程中建立。(3)单词串的输出形式。所输出的每一单词，均按形如(C LA S S,V A LU E)的二元式编码。对于变量标识符和常数，C LA S S 字段为相应的类别码，V A LU E 字段则是该标识符、常数在其符号表中登记项的序号(要求在变量名表登记项中存放该标识符的字符串，其最大长度为四个字符；常数表登记项中则存放该整数的二进制形式)。对于保留字和分隔号，由于采用一词一类的编码方式，所以仅需在二元式的C LA S S 字段上放置相应的

39、单词的类别码，V A LU E 字段则为“空”。不过，为便于查看由词法分析程序所输出的单词串，也可以在C LA S S 字段上直接放置单词符号串本身。(4)可以仿照程序3 4 的结构来编写上述词法分析程序，但其中的若干语义过程有待于具体编写。(5)写出它的LE X 源程序，并上机进行处理。第三章习题解答1.从略2.3假设W:表示载狐狸过河，G:表示载山羊过河，C:表示载白菜过河用到的状态1：狐狸和山羊在左岸2：狐狸和白菜载左岸3:羊和白菜在左岸4:狐狸和山羊在右岸5:狐狸和白菜在右岸6:山羊和白菜在右岸F:全在右岸4证明：只须证明文法G:A-a B或A-a (A,B GV N,a GV T+)

40、等价于 Gl:A a B 或 A f a (a GV T+)G 1的产生式中A a B,则B也有B b C ,C-c D.所以有 A -a b c-B,a,b,c-GV T,B,e V N所以与G 等价。2)G 的产生式A-a B,a S V T+,因为a是字符串，所以肯定存在着一个终结符a,可见两者等价，所以由此文法产生的语言是正规语言。56根据文法知其产生的语言是L=a mb nc i m,n,i S1可以构造如下的文法V N=S,A,B,C,V T=a,b,c)P-S f a A,A-*a A,A-b B,B-b B,B-c C,C-c C,C-c)其状态转换图如下：使 A-a B7

42、C(i v)S-b S S-a A A-a C A-b B B-a B B-b C C-a|a C C-b|b C(3)用自然语言描述输入串的特征(i)以任意个(包括0)b 开头，中间有任意个(大于1)a,跟一个b,还可以有一个由a,b 组成的任意字符串(i i)以a 打头，后跟任意个(包括0)b（iii）以a 打头，中间有任意个（包括0）b,再跟a,最后由一个a,b 所组成的任意串结尾或者以b 打头，中间有任意个（包括0）a,再跟b,最后由一个a,b 所组成的任意串结尾（iv）以任意个（包括0）b 开头，中间跟aa最后由一个a,b 所组成的任意串结尾或者以任意个（包括0）b 开头，中间跟ab

43、后再接任意（包括0）a 再接b,最后由一个a,b 所组成的任意串结尾10（1）G1的状态转换图：(2)G1等价的左线性文法：S-Bb,S f Dd,D f C,B-Db,CBc,B f Ab,B-e ,2 aG2等价的右线性文法:S-*dD,S-*aB,D-C,B f abC,B-*bB,B-*bA,B-*,C-*cA,A-*a(3)对G1文法,ab b的推导序列是：S=aA=abB二 abb对G l 文法，ab b的推导序列是：S=Bb=Abb=abb对G2文法，aabca的推导序列是：S=Aa=Cca=Babca=aabca对G 2 文法，aabca的推导序列是：S=aB=aabC=aab

44、cA=aabca(4)对串acbd来说，G l.G r文法都不能产生。11将右线性文法化为左线性文法的算法：o(1)对于G中每一个形如Aa B的产生式且A是开始符，将其变为Ba,否则若A不是开始符，B-A a;o(2)对于G中每一个形如A-a的产生式，将其变为SAa12(1)as(S.A)A申B状态矩阵是：B 6记S=qO B=ql A B=q2 S A=q3，最小化和确定化后如图(2)记 S =qO,A =ql,B S =q2最小化和确定化后的状态转换图如下13(1)将具有e动作的NFA 确定化后，其状态转换图如图:记 S 0,S l,S 3=q0 S l=ql S 2 S 3=q2 S 3

45、=q3(2)记 S=qO Z=ql U R=q2 S X=q3 Y U R=q4 X S U=q5 Y U R Z=q6 Z S=q714(1)从略化简后SO和S1作为一个状态，S5和S6作为一个状态。状态转换图如图15从略。16从略。(1)r*表示的正规式集是,r,rr,rrr,.(e I r)*表示的正规式集是 e ,e e ,U r,rr,rrr,)=s,r,rr,rrr,)e|rr*表示的正规式集是 e ,r,rr,rrr,)(r*)*=r*=e,r,rr,rrr,)所以四者是等价的。(2)(rs)*r 表示的正规式集是 e ,rs,rsrs,rsrsrs,r=r,rsr,rsr

46、sr,rsrsrsr,r(sr)*表示的正规式集是 r e ,sr,srsr,srsrsr,)=r,rsr,rsrsr,rsrsrsr,所以两者等价。1 8 写成方程组S=aT+aS(l)B=cB+c(2)T=bT+bB(3)所以 B=c*cT=b*bc*cS=a*ab*bc*c Gl:S=aA+B(l)B=cC+b(2)A=abS+bB(3)C=D(4)D=bB+d(5)把(4)(5)代入(2),得 B=c(bB+d)+b=cbB+cd+b 得 B=(cb)*(cd|b),代入(3)得A=abS+b(cb)*(cd|b)把它打入得S=a(abS+b(cb)*(cd i b)+(cb)*

48、2,3,10,20,100的例子,读者可以推而广之。%(i nc lu d e#i nc lu d e#i nc lu d e#d e f i ne O NI#d e f i ne T W 2#d e f i ne T HR E 3#d e f i ne T E 10#d e f i ne T W ENT 20#d e f i ne HU NDR E 100t t d e f i ne W HT T E9999%u ppe r A Z%O NEr e t u r n O N;T W O r e t u r n T W;T HR EEr e t u r n T HR E;T ENr e t u

49、r n T E;T W ENT Y r e t u r n T W ENT;HU NDR EDr e t u r n HU NDR E;z，+|t r e t u r n W HI T E;nr e t u r n0;%ma i n(i nt a r g c,c h a r *a r g v )i nt c,i=0char tmp30;if(argc=2)(if(yyin=fope n(argv1,r )-NULL)(p rin tf(，can，t ope n%snz/,argv 1);e xit(0);Iwhile (c=yyle x()!=0)(switch(c)(case ON:c=yy

50、le x();if(c=0)goto i+=l;lab e l;c=yyle x();if(c=HUNDRE)i+=100;e lse i+=l;bre ak;case TW:c=yyle x();c=yyle x();if(c=HUNDRE)i+=200;e lse i+=2;bre ak;case TW ENT:i+=20;bre ak;case TE:i+=10;bre ak;de fault:bre ak;/*while*/labe l:printf(%dn,i);re turn;24(1)Dn表示的正规集是长度为2n任意a 和 b 组成的字符串。此正规式的长度是2n 用来识别Dn的

展开阅读全文