编译基础学习知识原理平时课后复习-规范标准答案.doc

!- 平时作业 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 (k>0），|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）=q3 3 下面是用正规式表示的变量声明： ( int | float ) id (, id )* ; 请改用上下文无关文法表示，也就是写一个上下文无关文法，它和该正规式等价。 答：D T L ; T int | float L L, id | id 4 试分析下面给出的if-then-else语句的文法，它的提出原本是为了矫正dangling-else (悬而未决的-else)文法的二义性： stmt → if expr then stmt |matched-stmt matched-stmt→ if expr then matched-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 esle stmt matched-stmt expr then matched-stmt e other esle stmt matched-stmt other stmt matched-stmt if expr then matched-stmt e if esle stmt esle stmt matched-stmt expr then e stmt other expr then matched-stmt e other if matched-stmt other 则上面给出的if-then-else文法仍是二义性的。 5 证明下面文法是SLR(1)文法，并构造其SLR分析表。 E→E+T|T T→TF|F F→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→TF, 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→TF, F→F*, F→a, F→b} 求FOLLOW集：FOLLOW(E)={＋, ＄}FOLLOW(T)={＋, ＄, a, b} FOLLOW(F)={＋, ＄, a, b, *} 构造的SLR分析表如下： 显然，此分析表无多重定义入口，所以此文法是SLR文法。 6 为下面的文法构造LALR(1)分析表 S→E E→E+T|T T→(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如下： E E E E + id E id I0 E E E E+ id I1 E id I2 E id + E E +id I3 E E + id I4 id 再构造SLR分析表如下： 状态 动作 转移 id + $ E 0 s2 1 1 s3 acc 2 r2 r2 3 s4 4 r1 r1 表中没有多重定义的条目，因此该文法是SLR(1)的。 （2）下面左右两个文法都和（1）的文法等价 E E + M id | id E M E + id | id M e M e 请指出其中有几个文法不是LR(1)文法，并给出它们不是LR(1)文法的理由。 答：只有文法 E M E + id | id M e 不是LR(1)文法。因为对于句子id+id+…+id来说，分析器在面临第一个id时需要做的空归约次数和句子中+id的个数一样多，而此时句子中+id的个数是未知的。 8 根据自上而下的语法分析方法，构造下面文法的LL（1）分析表。 D TL T int | real L id R R , id R | e 答：先计算FIRST和FOLLOW FIRST(D) = FIRST(T) = {int,real} FIRST(L) = {id} FIRST(R) = {,,ε} FOLLOW(D) = FOLLOW(L) = {$} FOLLOW(T) = {id} FOLLOW(R) = {$} LL(1)分析表如下： int real id , $ D D -> TL D -> TL T T -> int T -> real L L -> idR R R -> ,idR R -> ε 9 下面的文法产生的表达式是对整型和实型常数应用算符+形成的。当两个整数相加时，结果仍为整数，否则就是实数。 E→E+T|T T→num.num|num （a）给出一个语法制导定义以确定每个子表达式的类型。 （b）扩充（a）中的语法制导定义把表达式翻译成前缀形式，并且决定类型。使用一元算符inttoreal把整型值转换成相等的实型值，以使得前缀形式中的+的两个操作对象是同类型的。 答： (a): 产生式 语义规则 EE1+T IF (E1.type=integer) and (T.type=integer) THEN E.type:=integer ELSE E.type:=real ET E.type:=T.type Tnum.num T.type:=real Tnum T.type:=integer (b): 产生式 语义规则 EE1+T IF (E1.type=integer) and (T.type=integer) THEN BEGIN E.type:=integer Print(‘+’,E1.val,T.val) END ELSE BEGIN E.type:=real IF E1.type=integer THEN Begin E1.type:=real E1.val:=inttoreal(E1.val) End IF T.type:=integer THEN Begin T.type:=real T.val:=inttoreal(T.val) End Print(‘+’,E1.val,T.val) END ET E.type:=T.type E.val:=T.val Tnum.num T.type:=real T.val:=num.num.lexval Tnum T.type:=integer T.val:=num.lexval 10 假设说明是由下列文法产生的： D→id L L→,id L|:T T→integer |real （a）建立一个翻译模式，把每一个标识符的类型加入到符号表中。 （b）从（a）中的翻译模式构造一个预翻译程序。 答： (a)： 产生式 翻译模式 Did L {D.Type:=L.Type} {addtype(id.entry, D.type)} L,id L1 {L.Type:=L1.Type} {addtype(id.entry, L.type)} L:T {L.type:=T.type} Tinteger {T.type:=integer} Treal {T.type:=real} (b)： Procedure D; begin If lookahead=id then Begin Match(id); D.type=L; addtype(id.entry,D.type) end else error end Function L: DataType; Begin If lookahead=’,’ then Begin Match(‘,’); If lookahead=id then begin match(id); L.Type=L; addtype(id.entry,L.type); return(L.type) end Else error End Else if lookahead=’:’ then Begin Match(‘:’); L.Type=T; return(L.Type) end else error End Function T: DataType; Begin If lookahead=integer then Begin Match(integer); return(integer) end else If lookahead=real then Begin Match(real); return(real) end else error end 11 为下面的算术表达式文法写一个语法制导的翻译方案，它将每个子表达式E的符号（即值大于零还是小于零）记录在属性E.sign中（属性值分别用POS或NEG表示）。你可以假定所有的整数都不为零，这样就不用担心零的符号。 E E *E | +E | -E | unsigned_integer 答： E E1 *E2{if E1.sign= E2.sign then E.sign := POS else E.sign := NEG } E +E1 { E.sign := E1.sign } E -E1 {if E1.sign= POS then E.sign := NEG else E.sign := POS} E unsigned_integer {E.sign := POS} 12 为下面文法写一个语法制导的定义，用S的综合属性val给出下面文法中S产生的二进制数的值。例如，输入101.101时，S. val := 5.625。（不得修改文法。） S L . R | L L L B | B R B R | B B 0 | 1 答： S L . R S. val := L. val + R. val S L S. val := L. val L L1 B L. val := L1. val 2 + B. val L B L. val := B. val R B R1 R. val := (R1. val + B. val)/2 R B R. val := B. val/2 B 0 B. val := 0 B 1 B. val := 1 13 试问下面的程序将有怎样的输出？分别假定： （a）传值调用（call-by-value）； （b）引用调用（call-by-reference）； （c）复制恢复（copy-restore）； （d）传名调用（call-by-name）。 program main(input,output）； procedure p（x,y,z）； begin y：＝y＋1； z：＝z＋x； end； begin a：＝2； b：＝3； p(a＋b,a,a)； print a end. 答：1)．传地址：所谓传地址是指把实在参数的地址传递给相应的形式参数。在过程段中每 个形式参数都有一对应的单元，称为形式单元。形式单元将用来存放相应的实在参数的地址。 当调用一个过程时，调用段必须领先把实在参数的地址传递到一个为被调用段可以拿得到的 地方。当程序控制转入被调用段之后，被调用段首先把实参地址捎进自己相应的形式单元中， 过程体对形式参数的任何引用1或赋值都被处理成对形式单元的间接访问。当调用段工作完毕返回时，形式单元(它们都是指示器)所指的实在参数单元就持有所指望的值。 2)．传结果：和“传地址”相似(但不等价)的另一种参数传递力法是所谓“传结果”。这种方法的实质是，每个形式参数对应有两个申元，第1个单元存放实参的地址，第2个单元 存放实参的值。在过程体中对形参的任何引用或赋值都看成是对它的第2个单元的直接访 问。但在过程工作完毕返回前必须把第2个单元的内容行放到第1个单元所指的那个实参单 元之中。 3)．传值：所谓传值，是一种简单的参数传递方法。调用段把实在参数的值计算出来并 存放在一个被调用段可以拿得到的地方。被调用段开始丁作时，首先把这些值抄入形式中元 中，然后就好像使用局部名一样使用这些形式单元。如果实在参数不为指示器，那末，在被 调用段中无法改变实参的值。 4)．传名：所谓传名，是一种特殊的形——实参数结合方式。解释“传名”参数的意义： 过程调用的作用相当于把被调用段的过程体抄到调用出现的地方，但把其中任一出现的形式 参数都替换成相应的实在参数(文字替换)。它与采用“传地址”或“传值”的方式所产生的结果均不相同。 (a)2； (b)8； (c)7； (d)9。 14 对以下的Pascal程序画出过程c第二次被激活时的运行栈，控制链和访问链。说明在c中如何访问变量x。 program env； procedure a； var x:integer； procedure b； procedure c； begin x:=2；b end；{procedure c} begin c end；{procedure b} begin b end；{procedure a} begin a end. {main} 答： env control link access link a control link access link x b control link access link c control link access link b control link access link c access link control link 说明：c中沿着存取链向前走两步，到过程a的活动记录中就可以访问到变量x。 15 下面给出一个 C 语言程序及其在 SPARC/SUN 工作站上经某编译器编译后的运行结果。从运行结果看，函数 func中 4个局部变量 i1, j1, f1, e1的地址间隔和它们类型的大小是一致的，而 4个形式参数 i, j, f, e的地址间隔和它们的类型的大小不一致，试分析不一致的原因。注意，输出的数据是八进制的。 func (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( "Address 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, 35777772542, 35777772544, 35777772554 Address of i1, j1, f1, e1 = 35777772426, 35777772424, 35777772420, 35777772414 Sizes of short, int, long, float, double = 2, 4, 4, 4, 8，请问为什么？ 答：C语言编译器是不做实在参数和形式参数的个数和类型是否一致的检查的，由程序员自己保证它们的一致性。但是对于形式参数和实在参数是不同的整型（如一个是short型，另一个是long型），或者是不同的实型，编译器则试图保证目标代码运行时能得到正确的结果，条件是，当需要高级别类型数据向低级别类型数据转换时，不出现溢出。这样，C编译器作的约定是，当整型或实型数据作为实在参数时，分别将它们提升到long和double类型的数据传递到被调用函数。被调用函数根据形式参数所声明的类型，决定是否要将实在参数向低级别类型转换。 低地址 放高位 高地址 放低位 short long 图5.2 长整型和短整型 在本例中，long类型数据占4个字节，而short类型数据只占2个字节。因此被调用函数把实在参数的低位字节的内容当成是自己所需的数据，见图5.2 注意，对于SUN工作站来说，低地址存放整型数据的高位。 float doublee 图5.3 双精度型和浮点型 对于实型来说。double类型是8个字节，而float类型4个字节。被调用函数把实在参数的前4个字节作为自己所需的数据，因为double后面4个字节的内容都是为了增加精度用的，见图5.3。 e，8个字节 在main函数中参数压栈时的观点 在func函数中存取形式参数时的观点 4个字节，起始地址35777772554 4个字节，起始地址35777772544 2个字节，起始地址35777772542 2个字节，起始地址35777772536 f，8个字节 j，4个字节 i，4个字节 栈的增长方向 图5.4 参数在栈中的情况 这样在main函数中依次将参数提升后反序进栈，大小分别为8, 8, 4, 4。在func函数中，按形式参数的类型，把这些存储单元的一部分看成是形式参数的存储单元，见图5.4。从这个图不难理解为什么形式参数的地址间隔和它们的类型大小不一致了。 注意，现在的编译器将需要进行类型转换的形式参数（类型是char、short、float等）另行分配在局部数据区，当控制进入被调用过程时，首先将调用过程压栈的需要进行类型转换的实在参数取出，把它们存入所分配的局部数据区存储单元，并同时完成必要的数据类型的转换。在这种情况下，不会出现本题所碰到的现象。 另外，在SPARC工作站上，整型数据的高位存放在低地址，而低位存放在高地址。如果是X86机器，数据的高低位不是按这样的次序存放，那也不会出现本题所碰到的现象。 下面是某个编译器的类型提升函数，供读者理解用（备注：int和long的大小一样）。 Type promote(Type ty) { switch(ty->op){ case ENUM: return inttype; case INT: if (ty->size < inttype->size) return inttype; break; case UNSIGNED: if (ty->size < inttype->size) return inttype; break; case FLOAT: if (ty->size < doubletype->size) return doubletype; } return ty; } 16 试把下列C语言程序的可执行语句翻译为 (a)一棵语法树， (b)后缀式， (c)三地址代码。 main() { int i; int a[10]; while (i<=10) a[i]=0; while } 答：(a).一棵语法树 赋值表达式 布尔表达式 表达式 表达式 数组元素 表达式 <= 下标表达式 1 10 a 0 1 (b) 后缀式为： i 10<= a i[] 0 = while 从理论上可以说while(i<=10) a[i]=0; 的后缀式如上面表示。但若这样表示，在执行while操作时，赋值语句已经执行，这显然与语义不符，因此改为： i 10 <=< 下一个语句开始地址>BM a i [] 0 =< 本语句地址 > BRL 其中BM操作为当表达式为假时转向<下一个语句开始地址>，BRL是一个一目运算，无条件转向<本语句始址>。 (c) 三地址代码序列为： 100 if i <= 10 got 102 101 goto 106 102 t1:=4*i 103 t2:=a 104 t2[t1]:=0 105 goto 100 106 17 Pascal语言中，语句： for v：＝initial to final do stmt 与下列代码序列有相同含义 begin t1:=initial;t2:=final; if t1<=t2 then begin v:=t1; stmt while v<>t2 do begin v：=succ（v)； stmt end end end (a)试考虑下述Pascal程序 program forloop(input, output); var i,initial,final: integer; begin read(initial, final); for i:= initial to final do write(i) end 对于initial=MAXINT-5和final= MAXINT，问此程序将做些什么？其中MAXINT为目标机器允许的最大整数。 (b)试构造一个翻译pascal的for语句为三地址代码的语法制导定义。 答： （a）程序将显示如下六个整数： MAXINT -5 MAXINT -4 MAXINT -3 MAXINT -2 MAXINT -1 MAXINT （b）为简单起见，for语句的三地址代码如下： t1 := initial t2 := final if 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:= newtemp S.code:=gen(S.first “:=” E.init) ||gen(S.last “:=” E.final) ||gen(“if” S.first “>” S.last “goto” S.next) ||gen(S.curr “:=” S.first) ||gen(S.begin “:” ) ||gen(“if ” S.curr “>” S.Last “goto” S.next) ||S1.code ||gen(S.curr := succ(S.curr)) ||gen(“goto” S.begin) E→v:=initial to final E.init := initial.place E.final := final.place 18 对于下面C语言文件s.c f1(int x) { long x; x = 1; } f2(int x) { { long x; x = 1; } } 某编译器编译时报错如下： s.c: In function ‘f1’: s.c:3: warning: declaration of ‘x’ shadows a parameter 请回答，对函数f2为什么没有类似的警告错误。 答： 对于函数f1，局部变量x声明的作用域是整个函数体，导致在函数体中不可能访问形式参数x。由于这是一个合法的C语言函数，因此编译器给出警告错误。 对于函数f2，由于局部变量x的作用域只是函数体的一部分，不会出现上述问题，因而编译器不报错。 19 考虑一个简单语言，其中所有的变量都是整型（不需要显式声明），并且仅包含赋值语句、读语句和写语句。下面的产生式定义了该语言的语法（其中lit表示整型常量；OP的产生式没有给出，因为它和下面讨论的问题无关）。 Program StmtList StmtList Stmt StmtList | Stmt Stmt id := Exp; | read (id ); | write ( Exp ); Exp id | lit | Exp OP Exp 我们把不影响write语句输出值的赋值（包括通过read语句来赋值）称为无用赋值，写一个语法指导定义，它确定一个程序中出现过赋予无用值的变量集合（不需要知道无用赋值的位置）和没有置初值的变量集合（不影响write语句输出值的未置初值变量不在考虑之中）。 非终结符StmtList和Stmt用下面3个属性（你根据需要来定义其它文法符号的属性）： （1）uses_in：在本语句表或语句入口点的引用变量集合，它们的值影响在该程序点后的输出。 （2）uses_out：在本语句表或语句出口点的引用变量集合，它们的值影响在该程序点后的输出。 （3）useless：本语句表或语句中出现的无用赋值变量集合。 答：Exp的属性uses表示它引用的变量集合。Program的useless和no_initial分别表示程序的无用赋值变量集合和未置初值变量集合。 Program StmtList StmtList.uses_out:=; Program.useless := StmtList.useless; Program.no_initial := StmtList.uses_in; StmtList Stmt StmtList1 StmtList1.uses_out := StmtList.uses_out; Stmt.uses_out := StmtList1.uses_in;