编译原理例题与习题解答语法={词法规则+语法规则}标识符与名字上下文无关文法得定义:一个上下文无关文法G就是一个四元式G=(VT,VN,S,P),其中VT:终结符集合(非空)VN:非终结符集合(非空),且VTVN=S:文法得开始符号,SVNP:产生式集合(有限),每个产生式形式为P,PVN,(VTVN)*开始符S至少必须在某个产生式得左部出现一次。假定G就是一个文法,S就是它得开始符号。如果S,则称就是一个句型。仅含终结符号得句型就是一个句子。文法G所产生得句子得全体就是一个语言,将它记为L(G)L(G)=｛|S&∈VT*｝定义:如果一个文法存在某个句子对应两颗不同得语法树,则说这个文法就是二义得。语言得二义性:一个语言就是二义性得,如果对它不存在无二义性得文法。可能存在G与G’,一个为二义得,一个为无二义得。但L(G)=L(G’)例题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aabbab例题2、2试构造生成语言L={anbnci|n1,i0}得文法例题2、3请证实文法G(E):EEiT|TTT+F|iF|FFE*|(就是一个二义文法。P36-6、文法G6为:N→D|NDD→0|1|2|3|4|5|6|7|8|9(1)G6得语言L(G6)就是什么?注意:1)步骤,与得区别;2)不能写为→解:0127得最左推导:NNDNDDNDDDDDDD0DDD01DD012D01270127得最右推导:NNDN7ND7N27ND27N127D1270127大家有疑问的，可以询问和交流P36-7写一文法,使其语言就是奇数集,但不允许出现以0打头得奇数。解:将奇数划分为三个部分:最高位允许出现1～9,用非终结符B表示;中间部分可出现任意多位数字0～9,每一位用非终结符D表示;最低位只出现1,3,5,7,9,用A表示。由于中间部分可任意位,故需另引入一非终结符M,它包括最高位与中间部分。M解:奇数集文法G[N]为:G=({0,1,…,9},{N,A,M,B,D},N,ξ)ξ:N→A|MAM→B|MDA→1|3|5|7|9B→1|2|3|4|5|6|7|8|9D→0|B8、令文法为E→T|E+T|E-TT→F|T*F|T/FF→(E)|i8、令文法为E→T|E+T|E-TT→F|T*F|T/FF→(E)|i10、把下面文法改写成无二义性得文法S->SS|(S)|()解答:S->TS|TT->(S)|()L2={aibncn|n≥1,i≥0}L4={1n0m1m0n|n,m≥0}例题与习题解答第三章1、假定NFAM=<S,,,S0,F>,我们对M得状态转换图进行以下改造:1)引进新得初态结点X与终态结点Y,X,YS,从X到S0中任意状态结点连一条箭弧,从F中任意状态结点连一条箭弧到Y。2)对M得状态转换图进一步施行替换,其中k就是新引入得状态。代之为确定有限自动机得确定化——采用子集法设a就是中得一个字符,定义Ia=-closure(J)其中,J为I中得某个状态出发经过一条a弧而到达得状态集合。对一个DFAM最少化得基本思想:把M得状态集划分为一些不相交得子集,使得任何两个不同子集得状态就是可区别得,而同一子集得任何两个状态就是等价得。最后,让每个子集选出一个代表,同时消去其她状态。具体做法:对M得状态集进行划分首先,把S划分为终态与非终态两个子集,形成基本划分。假定到某个时候,已含m个子集,记为={I(1),I(2),,I(m)},检查中得每个子集瞧就是否能进一步划分:对某个I(i),令I(i)={s1,s2,,sk},若存在一个输入字符a使得Ia(i)不会包含在现行得某个子集I(j)中,则至少应把I(i)分为两个部分。例如,假定状态s1与s2经a弧分别到达t1与t2,而t1与t2属于现行中得两个不同子集,说明有一个字,t1读出后到达终态,而t2读出后不能到达终态,或者反之,那么对于字a,s1读出a后到达终态,而s2读出a不能到达终态,或者反之,所以s1与s2不等价。例题3、1例题3、21(0|1)*101②、状态转换矩阵例题3、3【解答】对照自动机得定义,由f得定义可知f(x,a)、f(y,b)均为多值函数,因此M就是一非确定有限自动机。先画出NFAM相应得状态图,用子集法构造状态转换矩阵重命名后得状态转换