编译原理作业

1对于下列语言分别写出它们的正规表达式。(1)英文字母组成的所有符号串，要求符号串中顺序包含五个元音。答：令Letter表示除这五个元音外的其它字母。((letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter))*(2)英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。答：A*B*....Z*(3)Σ={0,1}上的含偶数个1的所有串。答：(0|10*1)*(4)Σ={0,1}上的含奇数个1的所有串。答：(0|10*1)*1(5)具有偶数个0和奇数个1的有0和1组成的符号串的全体。答：设S是符合要求的串，|S|=2k+1(k≥0）。则S→S10|S21，|S1|=2k(k0），|S2|=2k(k≥0）。且S1是{0,1}上的串，含有奇数个0和奇数个1。S2是{0,1}上的串，含有偶数个0和偶数个1。考虑有一个自动机M1接受S1，那么自动机M1如下：和L(M1)等价的正规表达式，即S1为：((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*类似的考虑有一个自动机M2接受S2，那么自动机M2如下：和L(M2)等价的正规表达式，即S2为：((00|11)|(01|10)(00|11)*(01|10))*因此，S为：((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*0|((00|11)|(01|10)(00|11)*(01|10))*1(6)不包含子串011的由0和1组成的符号串的全体。答：1*|1*0(0|10)*(1|ε)(7)由0和1组成的符号串,把它看成二进制数，能被3整除的符号串的全体。答：假设w的自动机如下：对应的正规表达式：(1(01*0)1|0)*2给出接受下列在字母表{0,1}上的语言的DFA。(1)所有以00结束的符号串的集合。(2)所有具有3个0的符号串的集合。答：(1)DFAM=({0，1}，{q0，q1，q2}，q0，{q2}，δ)其中δ定义如下:δ（q0，0）=q1δ（q0，1）=q0δ（q1，0）=q2δ（q1，1）=q0δ（q2，0）=q2δ（q2，1）=q0(2)正则表达式:1*01*01*01*DFAM=({0，1}，{q0，q1，q2，q3}，q0，{q3}，δ)其中δ定义如下:δ（q0，0）=q1δ（q0，1）=q0δ（q1，0）=q2δ（q1，1）=q1δ（q2，0）=q3δ（q2，1）=q2δ（q3，1）=q33下面是用正规式表示的变量声明：(int|float)id(,id)*;请改用上下文无关文法表示，也就是写一个上下文无关文法，它和该正规式等价。答：DTL;Tint|floatLL,id|id4试分析下面给出的if-then-else语句的文法，它的提出原本是为了矫正dangling-else(悬而未决的-else)文法的二义性：stmt→ifexprthenstmt|matched-stmtmatched-stmt→ifexprthenmatched-stmtelsestmt|other试说明此文法仍然是二义性的。答：考虑句子ifethenifethenotherelseifethenotherelseother它具有如下所示的两种分析树stmtexprtheneifstmtifmatched-stmtexprthenmatched-stmteotherifeslestmtmatched-stmtexprthenmatched-stmteothereslestmtmatched-stmtotherstmtmatched-stmtifexprthenmatched-stmteifeslestmteslestmtmatched-stmtexprthenestmtotherexprthenmatched-stmteotherifmatched-stmtother则上面给出的if-then-else文法仍是二义性的。5证明下面文法是SLR(1)文法，并构造其SLR分析表。E→E+T|TT→TF|FF→F*|a|b答：该文法的拓广文法G'为(0)E'→E(1)E→E+T(2)E→T(3)T→TF(4)T→F(5)F→F*(6)F→a(7)F→b其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:I0={E'→·E,E→·E+T,E→·T,T→·TF,T→·F,F→·F*,F→·a,F→·b}I1={E'→E·,E→E·+T}I2={E→T·,T→T·F,F→·F*,F→·a,F→·b}I3={T→F·,F→F·*}I4={F→a·}I5={F→b·}I6={E→E+·T,T→·TF,T→·F,F→·F*,F→·a,F→·b}I7={T→TF·,F→F·*}I8={F→F*·}I9={E→E+T·,T→T·F,F→·F*,F→·a,F→·b}求FOLLOW集：FOLLOW(E)={＋,＄}FOLLOW(T)={＋,＄,a,b}FOLLOW(F)={＋,＄,a,b,*}构造的SLR分析表如下：显然，此分析表无多重定义入口，所以此文法是SLR文法。6为下面的文法构造LALR(1)分析表S→EE→E+T|TT→(E)|a答：其拓广文法G'：(0)S'→S(1)S→E(2)E→E+T(3)E→T(4)T→(E)(5)T→a构造其LR(1)项目集规范族和goto函数(识别活前缀的DFA)如下:I0={[S’→·S,$],[S→·E,$],[E→·E+T,$/+],[E→·T,$/+],[T→·(E),$/+],[T→·a,$/+]}I1={[S’→S·,$]}I2={[S→E·,$],[E→E·+T,$/+]}I3={[E→T·,$/+]}I4={[T→(·E),$/+],[E→·E+T,)/+],[E→·T,)/+],[T→·(E),)/+],[T→·a,)/+]}I5={[T→a·,$/+]}I6={[E→E+·T,$/+],[T→·(E),$/+],[T→·a,$/+]}I7={[T→(E·),$/+],[E→E·+T,)/+]}I8={[E→T·,)/+]}I9={[T→(·E),)/+},[E→·E+T,)/+],[E→·T,)/+],[T→·(E),)/+],[T→·a,)/+]}I10={[T→a·,)/+]}I11={[E→E+T·,$/+]}I12={[T→(E)·,$/+]}I13={[E→E+·T,)/+],[T→·(E),)/+],[T→·a,)/+]}I14={[T→(E·),)/+],[E→E·+T,)/+]}I15={[E→E+T·,)/+]}I16={[T→(E)·,)/+]}合并同心的LR(1)项目集，得到LALR的项目集和转移函数如下：I0={[S’→·S,$],[S→·E,$],[E→·E+T,$/+],[E→·T,$/+],[T→··(E),$/+],[T→·a,$/+]}I1={[S’→S·,$]}I2={[S→E·,$],[E→E·+T,$/+]}I3,8={[E→T·,$/+/)]}I4,9={[T→(·E),$/+/)],[E→·E+T,)/+],[E→·T,)/+],[T→·(E),)/+],[T→·a,)/+]}I5,10={[T→a·,$/+/)]}I6,13={[E→E+·T,$/+/)],[T→·(E),$/+/)],[T→·a,$/+/)]}I7,14={[T→(E·),$/+/)],[E→E·+T,)/+]}I11,15={[E→E+T·,$/+/)]}I12,16={[T→(E)·,$/+/)]}LALR分析表如下：7（1）通过构造识别活前缀的DFA和构造分析表，来证明文法EE+id|id是SLR(1)文法。答：先给出接受该文法活前缀的DFA如下：再构造SLR分析表如下：动作转移id+$E0s211s3acc2r2r23s44r1r1表中没有多重定义的条目，因此该文法是SLR(1)的。（2）下面左右两个文法都和（1）的文法等价EE+Mid|idEME+id|idMM请指出其中有几个文法不是LR(1)文法，并给出它们不是LR(1)文法的理由。答：只有文法EME+id|idME·EE·E+idE·idI0EE·EE·+idI1Eid·I2Eid+EE+·idI3EE+id·I4id状态不是LR(1)文法。因为对于句子id+id+…+id来说，分析器在面临第一个id时需要做的空归约次数和句子中+id的个数一样多，而此时句子中+id的个数是未知的。8根据自上而下的语法分析方法，构造下面文法的LL（1）分析表。DTLTint|realLidRR,idR|答：先计算FIRST和FOLLOWFIRST(D)=FIRST(T)={int,real}FIRST(L)={id}FIRST(R)={,,ε}FOLLOW(D)=FOLLOW(L)={$}FOLLOW(T)={id}FOLLOW(R)={$}LL(1)分析表如下：intrealid,$DD-TLD-TLTT-intT-realLL-idRRR-,idRR-ε9下面的文法产生的表达式是对整型和实型常数应用算符+形成的。当两个整数相加时，结果仍为整数，否则就是实数。E→E+T|TT→num.num|num（a）给出一个语法制导定义以确定每个子表达式的类型。（b）扩充（a）中的语法制导定义把表达式翻译成前缀形式，并且决定类型。使用一元算符inttoreal把整型值转换成相等的实型值，以使得前缀形式中的+的两个操作对象是同类型的。答：(a):产生式语义规则EE1+TIF(E1.type=integer)and(T.type=integer)THENE.type:=integerELSEE.type:=realETE.type:=T.typeTnum.numT.type:=realTnumT.type:=integer(b):产生式语义规则EE1+TIF(E1.type=integer)and(T.type=integer)THENBEGINE.type:=integerPrint(‘+’,E1.val,T.val)ENDELSEBEGINE.type:=realIFE1.type=integerTHENBeginE1.type:=realE1.val:=inttoreal(E1.val)EndIFT.type:=integerTHENBeginT.type:=realT.val:=inttoreal(T.val)EndPrint(‘+’,E1.val,T.val)ENDETE.type:=T.typeE.val:=T.valTnum.numT.type:=realT.val:=num.num.lexvalTnumT.type:=integerT.val:=num.lexval10假设说明是由下列文法产生的：D→idLL→,idL|:TT→integer|real（a）建立一个翻译模式，把每一个标识符的类型加入到符号表中。（b）从（a）中的翻译模式构造一个预翻译程序。答：(a)：产生式翻译模式DidL{D.Type:=L.Type}{addtype(id.entry,D.type)}L,idL1{L.Type:=L1.Type}{addtype(id.entry,L.type)}L:T{L.type:=T.type}Tinteger{T.type:=integer}Treal{T.type:=real}(b)：ProcedureD;beginIflookahead=idthenBeginMatch(id);D.type=L;addtype(id.entry,D.type)endelseerrorendFunctionL:DataType;BeginIflookahead=’,’thenBeginMatch(‘,’);Ifloo