编译原理参考练习题目

1、写出非负整数的正规表达式。例子：1234或0或10230123或－123非法非负整数→数字|非0数字整数整数→数字|整数数字数字→0|1|2|…|9非0数字→1|2|…|92、写出以非5数字为开头的所有非负整数之集的正规表达式。例子：1234或0或10230123或5123非法解：D=1|2|…|9E=1|2|3|4|6|7|8|9L=0|E(0|D)*8、把下列NDFA转化为DFA:解：A1设改为A,B,C状态ab+1222,3-2,322,312a3ba+-b12a3ba+-bA2设改为A,B状态15、写出下面DFA的正规表达式ABaCba+-aABa+-bab+12,3-2,32,3得到确定DFA：最小化DFA：12b3ab+-b4aaaab+1222,3-2,32,32,3,4-2,3,42,32,3,4-2,3,42,32,3,4123ab+-b4aab-得到正规表达式：结果：ab(a|b)*1、构造下列正则式相应的DA:(1)1(0|1)*101(2)1(1010*|1(010)*1)*0(3)a((a|b)*|ab*a)b(4)b((ab)*|bb)*ab解：1）123a+-bab13+-aba|b13+-ab(a|b)*SZ+-1(0|1)*101SZ+-101121(0|1)*SZ+-10112113εε0SZ+-112113εε04510SZ+-112113110451002、已知NDFA=({x,y,z},{0,1},M,{x},{z}),其中:M(x,0)={z},M(y,0)={x,y},M(z,0)={x,z},M(x,1)={x},M(y,1)=Φ,M(z,1)={y},构造相应的DFA。1:写出状态转换矩阵10+S113333,433,43,43,53,53,4,Z3-3,4,Z3,43,516+-121131104500001确定自动机：01+xzxyx,y-zx,zyx-10z01000+y01+xzx-zx,zy-x,zx,zx,yyx,yx,yx,y,zx-x,y,zx,y,zx,y1、设有文法G[N]:N→D|NDD→0|1|2|…|9(1)试写出021和4321的最右推导和最左推导。解:(1)021的最左推导：NNDNDDDDD0DD02D021021的最右推导：NNDN1ND1N21D21021解:4321的最左推导：NNDNDDNDDDDDDD4DDD43DD432D43214321的最右推导：NNDN1ND1N21ND21N321D32143213、设有文法G[E]:E→T|E+T|E-TT→F|T*F|T/FF→i|(E)(1)试写出i*i/(i+i*i)的语法树。(2)试写出句型T*F*(T+i)的最右推导。解：(1)i*i/(i+i*i)的语法树：（见下页）(2)最右推导x-1y0A010+z001BC10--ETT*FT*(E)T*(E+T)T*(E+F)T*(E+i)T*(T+i)T*F*(T+i)5、对下面的文法G:E→TE’E’→+E|εT→FT’T’→T|εF→PF’F’→*F’|εP→(E)|A|B|∧A→aB→b(1)计算这个文法的每个非终结符的First集和follow集。解：first(E)=first(T)=first(F)=first(P)={(,a,b,∧}first(E’)={+,ε}first(T’)=first(T)∪{ε}={(,a,b,∧,ε}first(F’)={*,ε}follow(E)=follow(E’)∪{}}∪{#}={),#}ET/FT*FTFiE)(+TE*FTFiTFiiifollow(E’)=follow(E)={),#}follow(T)=first(E’)-ε∪follow(E)∪follow(T’)={+,),#}follow(T’)=follow(T)={+,),#}follow(F)=first(T’)-ε∪follow(T)={(,a,b,∧,+,),#}follow(F’)=follow(F)={(,a,b,∧,+,),#}follow(P)=first(F’)-ε∪follow(F)={*,(,a,b,∧,+,),#}三、化简下列自动机。解：化为确定自动机：2和4等价，3和(4,5)等价例子：设有正则表达式e为：(a|b)*(aa|bb)(a|b)*构造确定有穷自动机A，使L(A)=L(e)解：求e的转换系统首先，利用求闭包的方法转化为确定自动机。得出如下表格：Move([s，3，1]，a)=(3，5)-closure(3，5)=[1，3，5]得到确定自动机如下图：化简后如下图，其中3，4，5，6四个状态等价。求first(X)的算法：(X∈VN∪VT)1、若X∈VT，则first(X)=｛X｝。2、若X∈VN，且有产生式X→t…，则把t加入到first(X)中；若X→也是产生式，则把也加入到first(X)中。其中t∈VT。3、若有产生式X→Y……，(Y∈VN)，则把first(Y)～{ε}中的元素全部加到first(X)中；若X→Y1Y2…Yn是一产生式，同时Y1，…，Yi-1是非终极符，且对一切j=1，2，…，i-1，都有first(Yj)，则把first(Yi)～{ε}的元素全部加到first(X)中；特别是对一切j=1，2，…，n，都有first(Yj)时，要把加first(X)中。例子1：X→ABCA→aB→bC→c解：ABCaBC，abC，abc，AbC，Abc，aBc，ABc……first(X)=first(ABC)=｛a｝例子2：X→ABCA→a|B→bC→c解：ABCaBC，abC，abc，AbC，Abc，aBc，ABc，bC，bc，BC，Bc……first(X)=first(ABC)=｛a，b｝例子3：X→ABCA→a|B→b|C→c解：ABCaBC，abC，abc，AbC，Abc，aBc，ABc，bC，bc，BC，Bc，c，C……first(X)=first(ABC)=｛a，b，c｝例子4：X→ABCA→a|B→b|C→c|解：ABCaBC，abC，abc，AbC，Abc，aBc，ABc，bC，bc，BC，Bc，c，C，ε……first(X)=first(ABC)=｛a，b，c，ε｝例子5：X→ABcA→aA→bB→cB→DD→d解：first(X)=first(ABc)=first(A)∪first(B)=｛a,b｝∪｛c,d｝=｛a,b,c,d｝求first()的算法：(α=X1X2…Xn)1、若n=0，即=ε，则令first()={ε}2、否则，对1≤i≤n，求first(Xi)。3、若n≥2，且对一切j=1，2，…，i-1都有ε∈first(Xj)，则令first(Xi)～{ε}first(d)，其中2≤i≤n。若对一切j=1，2，…，n都有ε∈first(Xj)，则令ε∈first(α)。例子：X→ABCA→a|B→b|C→c|解：first(ABC)=first(A)～{ε}∪first(B)～{ε}∪first(C)=｛a,b,c,ε｝求follow(B)的算法：(B∈VN)1、对文法初始符S，令#∈follow(S)2、若A→xBy是一个产生式，则令first(y)～εfollow(B)3、若A→xB是一个产生式，或A→xBy是一个产生式且有ε∈first(y)，则令follow(A)follow(B)例子1：G[X]：X→ABA→a|aAaB→b则：follow(X)={#}follow(A)=first(B)∪{a}={b}U{a}={b，a}follow(B)=follow(X)={#}例子2：G[X]：X→ABCA→a|aAaB→bC→c|ε则：first(C)={c，ε}follow(B)=first(C)～{ε}∪follow(X)={c}∪{#}={c，#}例子：考虑文法，分别求first，follow集G[E]：E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→i|(E)first(E)=first(T)=first(F)={i，(}first(E’)=｛+，ε｝first(T')=｛*，ε｝follow(E)={)，#}follow(E')=follow(E)=｛)，#｝follow(T)=first(E')∪follow(E)=｛+，}∪{)，#｝={+，)，#}follow(T')=follow(T)=｛+，)，#｝follow(F)=first(T')∪follow(T)=｛*，}∪{+，)，#｝={*，+，)，#}