编译原理例题与习题解答

1例题与习题解答第二章编译原理2回顾程序语言的定义一个程序语言是一个记号系统,它主要由以下方面定义：语法语义每个句子构成的规律研究语言每个句子的含义语法语义编译原理3语法={词法规则+语法规则}词法规则：单词符号的形成规则。单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。描述工具：正规式和有限自动机理论语法规则：语法单位的形成规则。语法单位通常包括：表达式、语句、子程序、过程、函数、程序等;描述工具：上下文无关文法回顾编译原理4标识符与名字标识符：以字母开头的，由字母数字组成的字符串。标识符与名字两者有本质区别：标识符是语法概念名字有确切的意义和属性回顾编译原理5上下文无关文法的定义：一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VTVN=S：文法的开始符号，SVNP：产生式集合(有限)，每个产生式形式为P，PVN，(VTVN)*开始符S至少必须在某个产生式的左部出现一次。回顾编译原理6假定G是一个文法，S是它的开始符号。如果S，则称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)L(G)=｛|S&∈VT*｝文法产生语言*+回顾编译原理7定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。可能存在G和G’，一个为二义的，一个为无二义的。但L(G)=L(G’)回顾文法和语言的二义性编译原理8例题2.1：有一个文法G=({S,A,B},{a,b},P,S),其中P:SaB|bAAa|aS|bAABb|bS|aBB采用最左推导产生句子aabbab并画出相应的语法树。SaBaaBBaabSBaabbABaabbaBaabbabSaBaBBbSbbAa编译原理9例题2.2试构造生成语言L={anbnci|n1,i0}的文法分析：要求a和b的个数一样多，并至少为一个，而c的个数为0个以上即可，所以可以用一个终结符去生成anbn串，用另一个非终结符去生成ci。G(Z):ZABAaAb|abBcB|编译原理10例题2.3请证实文法G(E):EEiT|TTT+F|iF|FFE*|(是一个二义文法。编译原理11P36-6.文法G6为:N→D|NDD→0|1|2|3|4|5|6|7|8|9（1）G6的语言L(G6)是什么?G6的语言是：0~9的数字组成的任意非空数字串L(G6)={x|x∈{0,1,2,3,4,5,6,7,8,9}+}（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+编译原理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)编译原理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*注意：树枝和符号均不可随意增减！编译原理189、证明文法:S→iSeS|iS|i是二义的。二义性的含义:如果文法存在某个句子对应两棵以上不同的语法树，或者两种以上不同的最左/右推导，则称这个文法是二义的。首先：找到此文法对应的一个句子iiiei其次：构造与之对应的两棵语法树SiSeSiSiiSiSiSeSii结论：因为该文法存在句子iiiei对应两棵不同的语法树，因而该文法是二义的。编译原理1910.把下面文法改写成无二义性的文法S-SS|(S)|()解答：S-TS|TT-(S)|()编译原理20L2={aibncn|n≥1,i≥0}G2(S):S→ABA→aA|εB→bBc|bcL3={anbnambm|m,n≥0}G3(S):S→ABA→aAb|εB→aBb|ε11、给出下面语言的相应文法编译原理21L4={1n0m1m0n|n,m≥0}可以看成是两部分：剩下两边的部分就是：S→1S0中间部分是0m1m：A→0A1|ε所以G4[S]可以写为：S→1S0|AA→0A1|ε|A22例题与习题解答第三章编译原理231.假定NFAM=S,,,S0,F，我们对M的状态转换图进行以下改造：1)引进新的初态结点X和终态结点Y，X,YS，从X到S0中任意状态结点连一条箭弧，从F中任意状态结点连一条箭弧到Y。2)对M的状态转换图进一步施行替换，其中k是新引入的状态。非确定有限自动机状态图的改造编译原理24代之为ikABjijAB代之为ijA|BijBA代之为ijA*ikjA按下面的三条规则对V进行分裂:逐步把这个图转变为每条弧只标记为上的一个字符或，最后得到一个NFAM’，显然L(M’)=L(M)编译原理25确定有限自动机的确定化——采用子集法设I是M’的状态集的一个子集，定义I的-闭包-closure(I)为:i)若sI，则s-closure(I)；ii)若sI，则从s出发经过任意条弧而能到达的任何状态s’都属于-closure(I)即：-closure(I)=I{s’|从某个sI出发经过任意条弧能到达s’}编译原理26设a是中的一个字符，定义Ia=-closure(J)其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。把确定化的过程:不失一般性，设字母表只包含两个a和b，我们构造一张表:IIaIb-Closure({X})编译原理27对一个DFAM最少化的基本思想:把M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。DFAM最少化编译原理28具体做法:对M的状态集进行划分首先，把S划分为终态和非终态两个子集，形成基本划分。假定到某个时候，已含m个子集，记为={I(1)，I(2)，，I(m)}，检查中的每个子集看是否能进一步划分:对某个I(i)，令I(i)={s1,s2,,sk}，若存在一个输入字符a使得Ia(i)不会包含在现行的某个子集I(j)中，则至少应把I(i)分为两个部分。编译原理29例如，假定状态s1和s2经a弧分别到达t1和t2，而t1和t2属于现行中的两个不同子集，说明有一个字，t1读出后到达终态，而t2读出后不能到达终态，或者反之，那么对于字a，s1读出a后到达终态，而s2读出a不能到达终态，或者反之，所以s1和s2不等价。s1t1as2t2aij编译原理30例题3.1给出下面描述的正规表达式以01结尾的二进制数串能被5正除的十进制整数包含奇数个1或者奇数个0的二进制数串编译原理31例题3.2构造下面正规式相应的DFA1(0|1)*101步骤:①.根据正规式画出对应的状态转换图;②.根据状态转换图画出对应的状态转换矩阵;③.根据状态转换矩阵得到重命名后的状态转换矩阵;④.根据重命名后的状态转换矩阵得出最后的DFA.编译原理321(0|1)*101①.状态转换图abadb1(0|1)*101a1(0|1)*101dcef1εε01101ggg编译原理33②.状态转换矩阵II0I1{a}Φ{b,c,d}{b,c,d}{c,d}{c,d,e}{c,d}{c,d}{c,d,e}{c,d,e}{c,d,f}{c,d,e}{c,d,f}{c,d}{c,d,e,g}{c,d,e,g}{c,d,f}{c,d,e}1abdcef1εε0101g编译原理34II0I1{a}Φ{b,c,d}{b,c,d}{c,d}{c,d,e}{c,d}{c,d}{c,d,e}{c,d,e}{c,d,f}{c,d,e}{c,d,f}{c,d}{c,d,e,g}{c,d,e,g}{c,d,f}{c,d,e}③.重命名后的状态转换矩阵S01A(始态)ΦBBCDCCDDEDECF(终态)F(终态)EDAB10C1D010E10101F④.DFA编译原理35例题3.3设M=({x,y},{a,b},f,x,{y})，其中f定义如下：f(x,a)={x,y}f(x,b)={y}f(y,a)=φf(y,b)={x,y}请构造对应的确定有限自动机。编译原理36【解答】对照自动机的定义，由f的定义可知f(x,a)、f(y,b)均为多值函数，因此M是一非确定有限自动机。先画出NFAM相应的状态图，编译原理37用子集法构造状态转换矩阵IIaIb{x}{x,y}{y}{y}-{x,y}{x,y}{x,y}{x,y}编译原理38重命名后的状态转换矩阵Sab0211-2222编译原理39编译原理401(1010*|1(010)*1)*0abdc1εε0e0101fghiεε01110jklmnεε①.状态转换图P64-7.构造下列正规式相应的DFA。编译原理41②.状态转换矩阵II0I1{0}Φ{1,2,3}{1,2,3}{4}{5,9,10,11}{5,9,10,11}{6,12}{2,3}{6,12}Φ{2,3,7,8,13}{2,3}{4}{5,9,10,11}{2,3,7,8,13}{2,3,4,8,10,11}{5,9,10,11}{2,3,4,8,10,11}{2,3,4,8,12}{2,3,5,9,10,11}{2,3,4,8,12}{2,3,4,8}{5,9,10,11,13}{2,3,5,9,10,11}{4,6,12}{2,3,5,9,10,11}{2,3,4,8}{2,3,4,8}{5,9,10,11}{5,9,10,11,13}{6,10,11,12}{2,3}{4,6,12}Φ{2,3,7,8,13}{6,10,11,12}{12}{2,3,7,8,13}{12}Φ{13}{13}{10,11}Φ{10,11}{12}{2,3}编译原理42③.重命名后的状态转换矩阵II0I11Φ22344565Φ7634784891091112101310111141214613Φ71415715Φ161617Φ17156④.DFA编译原理438、给出下面正规表达式（4）英文字母组成的所有符号串，要求符号串中的字母按字典序排列。(A|a)*(B|b)*(C|c)*…(Z|z)*（5）没有重复出现的数字的数字符号串的全体。令ri=i|,i=0,1,2,...,9R0|R1|R2|...|R9记为P(0,1,2...,9)表示0,1,2...,9的全排列(01,2,...,9)iiR019019...(01,2,...,9)...iiiiiiPrrr编译原理44（6）最多有一个重复出现的数字的数字符号串全体019019(01,2,...,9)...(01,2,...,9)...iiiiiiiiPrrrr(7)不包含子串abb的由a和b组成的符号串的全体b*(a|ab)*编译原理4512、将图3.18的(a)和(b)分别确定化和最少化。(a)aaa,b10①.状态转换矩阵IIaIb{0}{0,1}{