编译原理平时作业问题详解

1、编译原理平时作业-问题详解实用文档平时作业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) 具有偶数个

2、0 和奇数个 1 的有 0 和 1 组成的符号串的全体。答： 设 S是符合要求的串，|S|=2k+1 (k 0）。则 S S10|S 21，|S 1|=2k (k0）， |S 2|=2k (k0）。且 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) 等价的正规表达式，

3、即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的自动机如下：24 / 24实用文档对应的正规表达式：(1(01 * 0)1|0) *2 给出接受下列在字母表 0,1

4、 上的语言的 DFA。(1) 所有以 00 结束的符号串的集合。(2) 所有具有 3 个 0 的符号串的集合。答：(1) DFAM=(0， 1 ， q 0， q1，q2 ， q0， q 2 ， )其中定义如下:（ q0， 0） =q1 （ q1， 0） =q2 （ q2， 0） =q2（ q0， 1） =q0（ q1， 1） =q0（ q2， 1） =q0(2) 正则表达式 : 1 * 01* 01* 01*DFAM=(0 ， 1 ， q 0，q1， q2， q3 ， q0 ，q 3 ， )其中定义如下:（ q0， 0） =q1（ q0， 1） =q0（ q1， 0） =q2（ q1， 1）

5、=q1（ q2， 0） =q3（ q2， 1） =q2（ q3， 1） =q33 下面是用正规式表示的变量声明：( int | float ) id (, id )* ;请改用上下文无关文法表示，也就是写一个上下文无关文法，它和该正规式等价。答：DTL;T int | float L L, id | id实用文档4 试分析下面给出的 if-then-else 语句的文法，它的提出原本是为了矫正 dangling-else ( 悬而未决的 -else) 文法的二义性：stmt if expr then stmt|matched-stmtmatched-stmt if expr then matc

6、hed-stmt else stmt|other试说明此文法仍然是二义性的。答：考虑句子 if e then if e then other else if e then other else other它具有如下所示的两种分析树 stmt expr then e if stmt if matched-stmt expr then matched-stmt e other if eslestmt matched-stmt expr then matched-stmt e other esle stmt matched-stmt other stmtmatched-stmt if expr th

7、en matched-stmt e if esle stmt esle stmt matched-stmt expr then estmt other expr then matched-stmt e other if matched-stmt other 则上面给出的 if-then-else 文法仍是二义性的。5 证明下面文法是 SLR(1)文法，并构造其SLR分析表。EE+T|TTTF|FFF*|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 函数 (

8、识别活前缀的 DFA)如下 :I 0= E E,E E+T,E T,T TF,T F,F F*,F a, F bI1= EE , E E +TI2 = ET, T T F, F F*, F a, F bI3=T F, F F* I4 = F a I5 = F b I6= E E+ T, T TF, T F, F F*, F a, F bI7 = TTF, F F* I8 = FF* 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

9、分析表如下：显然，此分析表无多重定义入口，所以此文法是SLR文法。6 为下面的文法构造LALR(1)分析表SEEE+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

10、 T, )/+,T (E), )/+, T a, )/+I5=T a , $/+ I6 = E E+ T, $/+, T (E), $/+, T a, $/+I 7= T (E ), $/+, E E +T, )/+I8= E T , )/+I9=T ( E), )/+, E E+T, )/+, E T, )/+, T (E), )/+, T a, )/+I 10= T a, )/+ I11 = EE+T , $/+I12 = T (E) , $/+I 13= E E+T, )/+, T (E), )/+, T a, )/+I14 = T (E ), )/+, E E +T, )/+I 15=

11、 E E+T , )/+ I16 = T (E) , )/+实用文档合并同心的 LR(1) 项目集，得到LALR的项目集和转移函数如下：I0= S S, $, S E, $, E E+T, $/+, E T, $/+, T (E), $/+, T a, $/+I 1= S S, $ I2 = SE , $, EE +T, $/+I3,8 = E T , $/+/)I 4,9= T ( E), $/+/), E E+T, )/+, E T, )/+,T (E), )/+, T a, )/+I 5,10= T a , $/+/) I6,13 = EE+ T, $/+/), T (E), $/+/)

12、, T a, $/+/)I 7,14= T (E ), $/+/), E E+T, )/+ I11,15 = E E+T , $/+/)I 12,16 = T (E), $/+/)LALR分析表如下：实用文档7 （1）通过构造识别活前缀的DFA和构造分析表，来证明文法EE +id |id是 SLR(1)文法。答：先给出接受该文法活前缀的DFA如下：EEE E+idE idE E + ididE E + idI3I 4I2再构造 SLR分析表如下：动作转移状态id+$E0s211s3acc2r 2r 23s44r 1r 1表中没有多重定义的条目，因此该文法是SLR(1) 的。（ 2）下面左右两个

13、文法都和（1）的文法等价EE + Mid|idEM E +id|idMM请指出其中有几个文法不是LR(1) 文法，并给出它们不是LR(1) 文法的理由。答：只有文法EM E +id |id实用文档M不是 LR(1) 文法。因为对于句子个数一样多，而此时句子中+idid +id +id 来说，分析器在面临第一个的个数是未知的。id时需要做的空归约次数和句子中+id的8 根据自上而下的语法分析方法，构造下面文法的LL（1）分析表。D TLTint | realL id RR , id R |答： 先计算 FIRST 和 FOLLOWFIRST(D) = FIRST(T) = int,realFIR

14、ST(L) = idFIRST(R) = , FOLLOW(D) = FOLLOW(L) = $FOLLOW(T) = idFOLLOW(R) = $LL(1) 分析表如下：intrealid,$DD-TLD-TLTT -intT - realLL -id RRR - ,id RR - 9 下面的文法产生的表达式是对整型和实型常数应用算符 +形成的。当两个整数相加时，结果仍为整数，否则就是实数。EE+T|TTnum. num| num（a）给出一个语法制导定义以确定每个子表达式的类型。实用文档（b）扩充（ a）中的语法制导定义把表达式翻译成前缀形式，并且决定类型。使用一元算符 inttorea

15、l 把整型值转换成相等的实型值，以使得前缀形式中的 +的两个操作对象是同类型的。答： (a):产生式语义规则EE1+TIF (E1.type=integer) and (T.type=integer) THENE.type:=integerELSEE.type:=realETE.type:=T.typeTnum.numT.type:=realTnumT.type:=integer(b):产生式语义规则EE1+TIF (E1.type=integer) and (T.type=integer) THENBEGINE.type:=integerPrint( + ,E1.val,T.val)ENDE

16、LSE BEGINE.type:=realIF E1.type=integer THENBeginE1.type:=realE1.val:=inttoreal(E1.val)EndIF T.type:=integer THENBeginT.type:=realT.val:=inttoreal(T.val)EndPrint( + ,E1.val,T.val)ENDETE.type:=T.typeE.val:=T.valTnum.numT.type:=realT.val:=TnumT.type:=integerT.val:=num.lexval10 假设说明是由下列文法产生的：D id LL ,i

17、d L|:TT integer| real（ a）建立一个翻译模式，把每一个标识符的类型加入到符号表中。（b）从（ a）中的翻译模式构造一个预翻译程序。答：实用文档(a) ：产生式翻译模式DidLD.Type:=L.Typeaddtype(id .entry, D.type)L,idL1L.Type:=L1.Typeaddtype(id .entry, L.type)L: TL.type:=T.typeTintegerT.type:=integerTrealT.type:=real(b) ：Procedure D;beginIf lookahead=id thenBeginMatch(id);

18、D.type=L;addtype(id.entry,D.type)endelseerrorendFunction L: DataType;BeginIf lookahead=, thenBeginMatch(,);If lookahead=id thenbeginmatch(id);L.Type=L;addtype(id.entry,L.type);return(L.type)endElseerrorEndElse if lookahead= : thenBeginMatch( : );L.Type=T;return(L.Type)endelseerror实用文档EndFunction T:

19、DataType;BeginIf lookahead=integer thenBeginMatch(integer);return(integer)endelse If lookahead=real thenBeginMatch(real);return(real)endelseerrorend11 为下面的算术表达式文法写一个语法制导的翻译方案，它将每个子表达式 E 的符号（即值大于零还是小于零）记录在属性 E. sign 中（属性值分别用 POS或 NEG表示）。你可以假定所有的整数都不为零，这样就不用担心零的符号。EE*E| +E|E|unsignedinteger_答：EE1*E2 i

20、fE1.sign=E2signthenE sign:= POSelseE.sign:= NEG EE1.+E sign:=E1.sign .EE1 ifE1. sign = POS then E. sign:= NEG elseE . sign:= POSEunsignedintegerE sign:= POS_ .12 为下面文法写一个语法制导的定义， 用 S 的综合属性 val 给出下面文法中 S 产生的二进制数的值。例如，输入 101.101 时， S. val := 5.625 。（不得修改文法。）S L.R|L L LB|BRBR|BB0 | 1答：SL . RS. val:= L.

21、val+ R.valSLS. val:= L.valLL1BL.val1val2+B.val:=L .LBL.val:= B.valRB R 1R.val:= (R1 . val + B.val )/2RBR.val:= B.val /2B0B.val:= 0B1B.val:= 1实用文档13 试问下面的程序将有怎样的输出？分别假定：（a）传值调用（ call-by-value ）；（b）引用调用（ call-by-reference）；（ c）复制恢复（ copy-restore ）；（ d）传名调用（ call-by-name ）。program main(input,output）；pr

22、ocedure p （ x,y,z ）；beginy： y1；z： zx；end；begina： 2；b： 3；p(a b,a,a) ；print aend.答： 1) 传地址：所谓传地址是指把实在参数的地址传递给相应的形式参数。在过程段中每个形式参数都有一对应的单元，称为形式单元。形式单元将用来存放相应的实在参数的地址。当调用一个过程时，调用段必须领先把实在参数的地址传递到一个为被调用段可以拿得到的地方。当程序控制转入被调用段之后，被调用段首先把实参地址捎进自己相应的形式单元中，过程体对形式参数的任何引用 1 或赋值都被处理成对形式单元的间接访问。当调用段工作完毕返回时，形式单元 ( 它们都

23、是指示器 ) 所指的实在参数单元就持有所指望的值。2) 传结果：和“传地址”相似 ( 但不等价 ) 的另一种参数传递力法是所谓“传结果”。这种方法的实质是，每个形式参数对应有两个申元，第1 个单元存放实参的地址，第2 个单元存放实参的值。在过程体中对形参的任何引用或赋值都看成是对它的第2 个单元的直接访问。但在过程工作完毕返回前必须把第2 个单元的内容行放到第1 个单元所指的那个实参单元之中。3) 传值：所谓传值，是一种简单的参数传递方法。调用段把实在参数的值计算出来并存放在一个被调用段可以拿得到的地方。被调用段开始丁作时，首先把这些值抄入形式中元中，然后就好像使用局部名一样使用这些形式单元。

24、如果实在参数不为指示器，那末，在被调用段中无法改变实参的值。4) 传名：所谓传名，是一种特殊的形实参数结合方式。解释“传名”参数的意义：过程调用的作用相当于把被调用段的过程体抄到调用出现的地方，但把其中任一出现的形式参数都替换成相应的实在参数 ( 文字替换 ) 。它与采用“传地址”或“传值”的方式所产生的结果均不相同。(a)2 ；(b)8 ；(c)7 ；(d)9 。14 对以下的 Pascal 程序画出过程 c 第二次被激活时的运行栈， 控制链和访问链。 说明在 c 中如何访问变量 x。program env ；procedure a ；实用文档var x:integer；procedure

25、b ；procedure c ；begin x:=2 ；b end；procedure cbegin cend；procedure bbegin bend； procedure abegin aend. main答：envcontrol linkaccess linkacontrol linkaccess linkxbcontrol linkaccess linkccontrol linkaccess linkbcontrol linkaccess linkccontrol linkaccess link说明：c 中沿着存取链向前走两步，到过程a 的活动记录中就可以访问到变量x。15 下面给出

26、一个 C 语言程序及其在SPARC/SUN工作站上经某编译器编译后的运行结果。从运行结果看，函数 func中 4个局部变量 i1, j1, f1, e1的地址间隔和它们类型的大小是一致的，而个形式参数 i, j, f, e的地址间隔和它们的类型的大小不一致，试分析不一致的原因。注意，输出的数据是八进制的。4func (i, j, f, e)short i, j; float f, e;short i1, j1; float f1, e1;printf( Address of i, j, f, e = %o, %o, %o, %o n, &i, &j, &f, &e);printf( Addre

27、ss of i1, j1, f1, e1 = %o, %o, %o, %o n, &i1, &j1, &f1, &e1); printf( Sizes of short, int, long, float, double = %d, %d, %d, %d, %d n, sizeof(short), sizeof(int), sizeof(long), sizeof(float), sizeof(double) );main()short i, j; float f, e;func(i, j, f, e);运行结果是：实用文档Address of i, j, f, e = 35777772536

28、, 35777772542, 35777772544, 35777772554 Address of i1, j1, f1, e1 = 35777772426, 35777772424, 35777772420, 35777772414Sizes of short, int, long, float, double = 2, 4, 4, 4, 8，请问为什么？答： C 语言编译器是不做实在参数和形式参数的个数和类型是否一致的检查的，由程序员自己保证它们的一致性。但是对于形式参数和实在参数是不同的整型（如一个是short型，另一个是long 型），或者是不同的实型，编译器则试图保证目标代码运行时

29、能得到正确的结果，条件是，当需要高级别类型数据向低级别类型数据转换时，不出现溢出。这样，C 编译器作的约定是，当整型或实型数据作为实在参数时，分别将它们提升到long 和 double 类型的数据传递到被调用函数。被调用函数根据形式参数所声明的类型，决定是否要将实在参数向低级别类型转换。在本例中， long 类型数据占4 个字节， 而 short类型数据只占2 个字节。 因此被调用函数把实在参数的低位字节的内容当成是自己所需的数据，见图5.2long低地址高地址放高位放低位short图 5.2 长整型和短整型注意，对于SUN工作站来说，低地址存放整型数据的高位。对于实型来说。 double 类

30、型是 8 个字节， 而 float类型 4 个字节。 被调用函数把实在参数的前4 个字节作为自己所需的数据，因为double 后面 4 个字节的内容都是为了增加精度用的，见图5.3 。这样在 main 函数中依次将参数提升后反序进栈，大小分别为8, 8, 4, 4。在 func 函数中，按形式参数的类型，doublefloat图 5.3 双精度型和浮点型把这些存储单元的一部分看成是形式参数的存储单元，见图它们的类型大小不一致了。在 main 函数中参数压栈时的观点i ， 4个字节j， 4个字节f ， 8个字节栈 的 增长方向e， 8 个字节5.4 。从这个图不难理解为什么形式参数的地址间隔和在

31、 func 函数中存取形式参数时的观点2 个字节，起始地址357777725362 个字节，起始地址357777725424 个字节，起始地址357777725444 个字节，起始地址35777772554图 5.4 参数在栈中的情况注意，现在的编译器将需要进行类型转换的形式参数（类型是char 、 short 、 float等）另行分配在局部数据区，当控制进入被调用过程时，首先将调用过程压栈的需要进行类型转换的实在参数取出，把它们存入所分配的局部数据区存储单元，并同时完成必要的数据类型的转换。在这种情况下，不会出现本题所碰到的现象。另外，在SPARC工作站上，整型数据的高位存放在低地址，而低

32、位存放在高地址。如果是X86 机器，数据的高低位不是按这样的次序存放，那也不会出现本题所碰到的现象。下面是某个编译器的类型提升函数，供读者理解用（备注：int和 long 的大小一样）。Type promote(Type ty)实用文档switch(ty-op)case ENUM:return inttype;case INT:if (ty-size size)return inttype;break;case UNSIGNED:if (ty-size size)return inttype;break;case FLOAT:if (ty-size size)return doubletype

33、;return ty;16 试把下列 C 语言程序的可执行语句翻译为(a) 一棵语法树，(b) 后缀式，(c) 三地址代码。 main() int i;int a10;while (i=10)ai=0;答： (a). 一棵语法树while布尔表达式表达式=表达式赋值表达式数组元素表达式a110下标表达式01(b)后缀式为： i 10= a i 0 = while从理论上可以说while(i=10)ai=0;的后缀式如上面表示。 但若这样表示， 在执行 while 操作时，赋值语句已经执行，这显然与语义不符，因此改为：i 10 =BM a i 0 = BRL其中 BM操作为当表达式为假时转向 ，

34、BRL是一个一目运算，无条件转向 。实用文档(c) 三地址代码序列为：100 if i = 10 got 102101 goto 106102 t1:=4*i103 t2:=a104 t2t1:=0105 goto 10010617 Pascal 语言中，语句： for v ： initial to final do stmt 与下列代码序列有相同含义begint1:=initial;t2:=final;if t1=t2 then beginv:=t1;stmtwhile vt2 do beginv ：=succ（ v) ；stmtendendend(a) 试考虑下述 Pascal 程序pro

35、gram forloop(input, output);var i,initial,final: integer;beginread(initial, final);for i:= initial to final dowrite(i)end对于 initial=MAXINT-5和大整数。final=MAXINT，问此程序将做些什么？其中MAXINT为目标机器允许的最(b) 试构造一个翻译 pascal 的 for 语句为三地址代码的语法制导定义。答：（ a）程序将显示如下六个整数：MAXINT -5 MAXINT -4 MAXINT -3 MAXINT -2 MAXINT -1 MAXINT

36、（ b）为简单起见， for 语句的三地址代码如下：t1 := initial t2 := finalif t1 t2 goto S.next v := t1 stmt.code S.begin:if v t2 goto S.next v := succ(v) stmt.code goto S.begin语法制导定义如下：产生式动作 S for E do S1 S.begin := newlabel S.first := newtemp S.last := newtemp S.curr:= newtempS.code:=gen(S.first“ := ” E.init)|gen(S.last“

37、 := ” E.final)|gen( “ if ” S.first“ ” S.lastS.next) |gen(S.curr“ := ” S.first) |gen(S.begin“ : ” ) |gen(“ if” S.curr“ ” S.LastS.next)|S1.code|gen(S.curr:= succ(S.curr)|gen(“ goto ” S.begin)E v:=initialto final“goto ”“ goto ”E.init:=initial.place E.final := final.place实用文档18对于下面 C语言文件f1(int x)s.clong

38、 x;x = 1;f2(int x)long x;x = 1;某编译器编译时报错如下：s.c: In functionf1 :s.c:3: warning: declaration of xshadows a parameter请回答，对函数f2 为什么没有类似的警告错误。答：对于函数 f1 ，局部变量 x 声明的作用域是整个函数体，导致在函数体中不可能访问形式参数x。由于这是一个合法的C 语言函数，因此编译器给出警告错误。对于函数 f2 ，由于局部变量 x 的作用域只是函数体的一部分，不会出现上述问题， 因而编译器不报错。19 考虑一个简单语言，其中所有的变量都是整型（不需要显式声明），并且

39、仅包含赋值语句、读语句和写语句。下面的产生式定义了该语言的语法（其中 lit 表示整型常量； OP的产生式没有给出，因为它和下面讨论的问题无关）。ProgramStmtListStmtListStmt StmtList | StmtStmtid := Exp; | read (id ); | write ( Exp );Expid | lit| Exp OP Exp我们把不影响write语句输出值的赋值（包括通过read 语句来赋值）称为无用赋值，写一个语法指导定义， 它确定一个程序中出现过赋予无用值的变量集合（不需要知道无用赋值的位置）和没有置初值的变量集合（不影响write语句输出值的未置

40、初值变量不在考虑之中）。非终结符 StmtList和 Stmt 用下面 3 个属性（你根据需要来定义其它文法符号的属性）：（1）uses_in ：在本语句表或语句入口点的引用变量集合，它们的值影响在该程序点后的输出。（2）uses_out ：在本语句表或语句出口点的引用变量集合，它们的值影响在该程序点后的输出。（3）useless ：本语句表或语句中出现的无用赋值变量集合。答： Exp 的属性 uses 表示它引用的变量集合。Program 的 useless和 no_initial分别表示程序的无用赋值变量集合和未置初值变量集合。ProgramStmtListStmtListStmtList.uses_out:=;Program.useless := StmtList.useless;Program.no_initial := St