文档视界 最新最全的文档下载
当前位置:文档视界 › 编译原理平时作业-答案

编译原理平时作业-答案

编译原理平时作业-答案
编译原理平时作业-答案

平时作业

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) DFA M=({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*

DFA M=({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→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→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如下:

再构造SLR分析表如下:

表中没有多重定义的条目,因此该文法是SLR(1)的。

(2)下面左右两个文法都和(1)的文法等价

E → E + M id | id E → M E + id | id

M →εM →ε

请指出其中有几个文法不是LR(1)文法,并给出它们不是LR(1)文法的理由。

答:只有文法

E → M E + id | id

M →ε

不是LR(1)文法。因为对于句子id+id+…+id来说,分析器在面临第一个id时需要做的空归约次数和句子中+id的个数一样多,而此时句子中+id的个数是未知的。

8 根据自上而下的语法分析方法,构造下面文法的LL(1)分析表。

D → TL

T → int | real

L → id R

R → , id R | ε

答:先计算FIRST和FOLLOW

FIRST(D) = FIRST(T) = {int,real}

FIRST(L) = {id}

FIRST(R) = {,,ε}

FOLLOW(D) = FOLLOW(L) = {$}

FOLLOW(T) = {id}

FOLLOW(R) = {$}

9 下面的文法产生的表达式是对整型和实型常数应用算符+形成的。当两个整数相加时,结果仍为整数,否则就是实数。

E→E+T|T

T→num.num|num

(a)给出一个语法制导定义以确定每个子表达式的类型。

(b)扩充(a)中的语法制导定义把表达式翻译成前缀形式,并且决定类型。使用一元算符inttoreal 把整型值转换成相等的实型值,以使得前缀形式中的+的两个操作对象是同类型的。

答:

(b):

10 假设说明是由下列文法产生的:

D→id L

L→,id L|:T

T→integer |real

(a)建立一个翻译模式,把每一个标识符的类型加入到符号表中。(b)从(a)中的翻译模式构造一个预翻译程序。

答:

(a)

(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 R1R. 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}

答:

说明: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 类型的数据传递到被调用函数。被调用函数根据形式参数所声明的类型,决定是否要将实在参数向低级别类型转换。 在本例中,long 类型数据占4个字节,而short 类型数据只占2个字节。因此被调用函数把实在参数的低位字节的内容当成是自己所需的数据,见图5.2

注意,对于SUN 工作站来说,低地址存放整型数据的高位。

低地址 放高位

高地址 放低位

图5.2 长整型和短整型

对于实型来说。double 类型是8个字节,而float 类型4个字节。被调用函数把实在参数的前4个字节作为自己所需的数据,因为double 后面4个字节的内容都是为了增加精度用的,见图5.3。 这样在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)一棵语法树,

float

图5.3 双精度型和浮点型

e ,8个字节

在main 函数中参数压栈时的观点

在func 函数中存取形式参数时的观点

4个字节,起始地址35777772554

4个字节,起始地址35777772544

2个字节,起始地址35777772542 2个字节,起始地址35777772536 f ,8个字节

j ,4个字节 i ,4个字节 栈的增长方向

图5.4 参数在栈中的情况

(b)后缀式,

(c)三地址代码。

main() {

int i;

int a[10];

while (i<=10)

a[i]=0;

}

答:

(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 https://www.docsj.com/doc/4c4445774.html,st := newtemp S.curr:= newtemp S.code:=gen(S.first “:=” E.init) ||gen(https://www.docsj.com/doc/4c4445774.html,st “:=” E.final) ||gen(“if” S.first “>” https://www.docsj.com/doc/4c4445774.html,st “goto” S.next) ||gen(S.curr “:=” S.first) ||gen(S.begin “:” ) ||gen(“if ” S.curr “>” https://www.docsj.com/doc/4c4445774.html,st “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 https://www.docsj.com/doc/4c4445774.html,es_out:=?;

https://www.docsj.com/doc/4c4445774.html,eless := https://www.docsj.com/doc/4c4445774.html,eless;

Program.no_initial := https://www.docsj.com/doc/4c4445774.html,es_in;

StmtList → Stmt https://www.docsj.com/doc/4c4445774.html,es_out := https://www.docsj.com/doc/4c4445774.html,es_out;

https://www.docsj.com/doc/4c4445774.html,es_out := https://www.docsj.com/doc/4c4445774.html,es_in;

https://www.docsj.com/doc/4c4445774.html,es_in := https://www.docsj.com/doc/4c4445774.html,es_in

https://www.docsj.com/doc/4c4445774.html,eless := https://www.docsj.com/doc/4c4445774.html,eless ? https://www.docsj.com/doc/4c4445774.html,eless;

StmtList → Stmt https://www.docsj.com/doc/4c4445774.html,es_out := https://www.docsj.com/doc/4c4445774.html,es_out;

https://www.docsj.com/doc/4c4445774.html,es_in := https://www.docsj.com/doc/4c4445774.html,es_in;

https://www.docsj.com/doc/4c4445774.html,eless := https://www.docsj.com/doc/4c4445774.html,eless

Stmt →id := Exp; https://www.docsj.com/doc/4c4445774.html,eless :=if id.lexeme∈https://www.docsj.com/doc/4c4445774.html,es_out then?else{id.lexeme};

https://www.docsj.com/doc/4c4445774.html,es_in := if id.lexeme∈https://www.docsj.com/doc/4c4445774.html,es_out

then (https://www.docsj.com/doc/4c4445774.html,es_out–{id.lexeme})?https://www.docsj.com/doc/4c4445774.html,es else https://www.docsj.com/doc/4c4445774.html,es_out

Stmt →read (id ); https://www.docsj.com/doc/4c4445774.html,eless:=if id.lexeme∈https://www.docsj.com/doc/4c4445774.html,es_out then?else{id.lexeme};

https://www.docsj.com/doc/4c4445774.html,es_in := https://www.docsj.com/doc/4c4445774.html,es_out – {id.lexeme}

Stmt →write ( Exp ); https://www.docsj.com/doc/4c4445774.html,eless := ?, https://www.docsj.com/doc/4c4445774.html,es_in := https://www.docsj.com/doc/4c4445774.html,es_out ? https://www.docsj.com/doc/4c4445774.html,es

Exp →id https://www.docsj.com/doc/4c4445774.html,es:= {id.lexeme}

Exp →lit https://www.docsj.com/doc/4c4445774.html,es:= ?

Exp → Exp1 OP https://www.docsj.com/doc/4c4445774.html,es:= https://www.docsj.com/doc/4c4445774.html,es ? https://www.docsj.com/doc/4c4445774.html,es

20 为下列C程序生成目标代码。

main()

{

int i;

int a[10];

while(i<=10)

a[i]=0;

}

答:

21 试构造下面的程序的流图,并找出其中所有回边及循环。

read P

x := 1

c := P * P

if c < 100 goto L1

B := P * P

x := x + 1

B := B + x

write x

halt

L1: B:= 10

x := x + 2

B := B + x

write B

if B < 100 goto L2

halt

L2: x := x + 1

goto L1

答:

程序的流图如下

22 试求出如下四元式程序中的循环并进行循环优化.

I := 1

read J, K

L: A := K * I

B := J * I

C := A * B

write C

I := I + 1

if I < 100 goto L

halt

答:把本题的三地址代码划分成基本块并画出其程序流图显示在图9.4(1)中,其中有三个基本块B1,B2,B3,有一条回边B2 -> B2,相应的循环是{B2}。

(1)代码外提:由于循环中没有不变运算,故不做此项优化(2)强度削弱:B2中A和B都是I的归纳变量。优化结果显示在图9.4(2)中。

(3)删除归纳变量:变换循环控制条件,删除归纳变量I后的流图显示在图9.4(3)中

23 考虑下面的三地址语句序列:

b := 1

b := 2

if w <= x goto L2

e := b

goto L2

L1: goto L3

L2: c := 3

b := 4

c := 6

L3: if y <= z goto L4

goto L5

L4: g := g + 1

h := 8

goto L1

L5: h := 9

(1)在该代码中用水平的横线将代码分成基本块,并给每个基本块一个序号。

(2)画出该代码的控制流图,每个基本块就用(1)的序号表示。

(3)若有循环的话,列出构成每个循环的结点。

答:

(1)(2)

b := 1

b := 2

if w <= x goto L2 (1)

e := b

goto L2 (2)

L1: goto L3 (3)

L2: c := 3

b := 4

c := 6 (4)

L3: if y <= z goto L4 (5)

goto L5 (6)

L4: g := g + 1

h := 8

goto L1 (7)

L5: h := 9 (8)

(3)结点5、7和3构成一个循环,其中5是入口结点。

24 对下面的程序片段作出其程序流图并计算:

(1)各基本块的到达_定值集IN[B];

(2)各基本块中各变量引用点的ud链;

(3)各基本块出口的活跃变量集V_OUT[B];

(4)各基本块中变量定值点的du链。

I := 1

J := 0

L1: J := J + I

read I

if I < 100 goto L2

write J

halt

L2 : I := I * I

答:本题程序的程序流图如图9.6(1)所示。

(1)计算各基本块的到达-定值集IN[B]。公式为:

IN[B] = ∪ OUT[P]

P∈P[B]

OUT[B] = GEN[B] ∪ ( IN[B] - KILL[B] )

GEN[B]和KILL[B]由程序流图直接求出,显示在表9.6(1)中。

9.6(2)中。

假设在程序中某点u引用了变量a,则把能到达u的a的所有定值点,称为a在引用点u的引用-定值链(简称ud链)。可以利用到达-定值信息来计算各个变量在任何引用点的ud链。

由图9.6(1)的程序流图可知,I的引用点是d3、d5和d6,J的引用点是d3和d8。

B2中I和J的引用点d3前面没有对I和J的定值点,其ud链在IN[B2]={ d1, d2, d3, d6 }中,所以I在引用点d3的ud链是{ d1, d6 };J在引用点d3的ud链是{ d2, d3 }。

在B2中I的引用点d5前面有I的定值点d4,且在d4定值后到达d5,所以I在引用点d5的ud链是{ d4 }。

B3中I的引用点d6前面没有I的定值点,其ud链是IN[B3]中I的所有定值点,所以是{ d4 }。

B4中J的引用点d8前面没有对J的定值点,其ud链是IN[B4]中J的所有定值点。已知IN[B4] = { d3, d4},所以,J的引用点d8的ud链是{ d3 }。

(3)各基本块出口的活跃变量集v-OUT[B]:

对程序中某变量a和某点P,如果存在一条从P开始的道路,其中引用了a在P点的值,则称a在点P

是活跃的。计算公式如下:

V_IN[B] = USE[B] ∪ ( V_OUT[B] - DEF[B] )

编译原理56章作业答案

第五章 练习5.1.1: 对于图5-1中的SDD,给出下列表达式对应的注释语法分析树: 1)(3+4)*(5+6)n 练习5.2.4: 这个文法生成了含“小数点”的二进制数: S->L.L|L L->LB|B B->0|1 设计一个L属性的SDD来计算S.val,即输入串的十进制数值。比如,串101.101应该被翻译为十进制的5.625。提示:使用一个继承属性L.side来指明一个二进制位在小数点的哪一边。 答: 元文法消除左递归后可得到文法: S->L.L|L L->BL’ L’->BL’|ε B->0|1 使用继承属性L.side指明一个二进制位数在小数点的哪一边,2表示左边,1表示右边 使用继承属性m记录B的幂次 非终结符号L和L’具有继承属性inh、side、m和综合属性syn

练习5.3.1:下面是涉及运算符+和整数或浮点运算分量的表达式文法。区分浮点数的方法是看它有无小数点。 E-〉E+T|T T-〉num.num|num 1)给出一个SDD来确定每个项T和表达式E的类型 2)扩展(1)中得到的SDD,使得它可以把表达式转换成为后缀表达式。使用一个单目运算符intToFloat把一个整数转换为相等的浮点数 答: 练习5.4.4:为下面的产生式写出一个和例5.10类似的L属性SDD。这里的每个产生式表

示一个常见的C语言中的那样的控制流结构。你可能需要生成一个三地址语句来跳转到某个标号L,此时你可以生成语句goto L 1)S->if (C) S1 else S2 2)S->do S1 while (C) 3)S->’{’ L ‘}’; L -> LS|ε 请注意,列表中的任何语句都可以包含一条从它的内部跳转到下一个语句的跳转指令,因此简单地为各个语句按序生成代码是不够的。 第六章 练习6.1.1:为下面的表达式构造DAG ((x+y)-((x+y)*(x-y)))+((x+y)*(x-y)) 答:DAG如下

编译原理作业答案

编译原理作业答案 Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】

《编译原理》第一次作业参考答案 一、下列正则表达式定义了什么语言(用尽可能简短的自然语言描述) 1.b*(ab*ab*)* 所有含有偶数个a的由a和b组成的字符串. 2.c*a(a|c)*b(a|b|c)* | c*b(b|c)*a(a|b|c)* 答案一:所有至少含有1个a和1个b的由a,b和c组成的字符串. 答案二:所有含有子序列ab或子序列ba的由a,b和c组成的字符串. 说明:答案一要比答案二更好,因为用自然语言描述是为了便于和非专业的人员交 流,而非专业人员很可能不知道什么是“子序列”,所以相比较而言,答案一要更 “自然”. 二、设字母表∑={a,b},用正则表达式(只使用a,b,?,|,*,+,)描述下列语言: 1.不包含子串ab的所有字符串. b*a* 2.不包含子串abb的所有字符串. b*(ab)* 3.不包含子序列abb的所有字符串. b*a*ba* 注意:关于子串(substring)和子序列(subsequence)的区别可以参考课本第119页方框中的内容. ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ 《编译原理》第二次作业参考答案

一、考虑以下NFA: 1.这一NFA接受什么语言(用自然语言描述) 所有只含有字母a和b,并且a出现偶数次或b出现偶数次的字符串. 2.构造接受同一语言的DFA. 答案一(直接构造通常得到这一答案): 答案二(由NFA构造DFA得到这一答案): 二、正则语言补运算

编译原理作业答案

《编译原理》第一次作业参考答案 一、下列正则表达式定义了什么语言(用尽可能简短的自然语言描述)? 1.b*(ab*ab*)* 所有含有偶数个a的由a和b组成的字符串. 2.c*a(a|c)*b(a|b|c)* | c*b(b|c)*a(a|b|c)* 答案一:所有至少含有1个a和1个b的由a,b和c组成的字符串. 答案二:所有含有子序列ab或子序列ba的由a,b和c组成的字符串. 说明:答案一要比答案二更好,因为用自然语言描述是为了便于和非专业的人员交流,而非专业人员很可能不知道什么是“子序列”,所以相比较而言,答案一要更“自然”. 二、设字母表∑={a,b},用正则表达式(只使用a,b, ,|,*,+,?)描述下列语言: 1.不包含子串ab的所有字符串. b*a* 2.不包含子串abb的所有字符串. b*(ab?)* 3.不包含子序列abb的所有字符串. b*a*b?a* 注意:关于子串(substring)和子序列(subsequence)的区别可以参考课本第119页方框中的内容. ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ 《编译原理》第二次作业参考答案 一、考虑以下NFA: 1.这一NFA接受什么语言(用自然语言描述)? 所有只含有字母a和b,并且a出现偶数次或b出现偶数次的字符串. 2.构造接受同一语言的DFA. 答案一(直接构造通常得到这一答案):

答案二(由NFA构造DFA得到这一答案): 二、正则语言补运算 3.画出一个DFA,该DFA恰好识别所有不含011子串的所有二进制串. 1.画出一个DFA,该DFA恰好识别所有不含011子串的所有二进制串.

编译原理课后习题答案(第三版)

精品文档 第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法: E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导: E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树:/********************************

编译原理第4章作业答案

编译原理第4章作业 答案 本页仅作为文档封面,使用时可以删除 This document is for reference only-rar21year.March

第四章 习题4.2.1:考虑上下文无关文法: S->S S +|S S *|a 以及串aa + a* (1)给出这个串的一个最左推导 S -> S S * -> S S + S * -> a S + S * -> a a + S * -> aa + a* (3)给出这个串的一棵语法分析树 习题4.3.1:下面是一个只包含符号a和b的正则表达式的文法。它使用+替代表示并运算的符号|,以避免和文法中作为元符号使用的竖线相混淆: rexpr→ rexpr + rterm | rterm rterm→rterm rfactor | rfactor rfactor→ rfactor * | rprimary rprimary→a | b 1)对这个文法提取公因子 2)提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗? 3)提取公因子之后,原文法中消除左递归 4)得到的文法适用于自顶向下的语法分析吗? 解

1)提取左公因子之后的文法变为 rexpr→ rexpr + rterm | rterm rterm→rterm rfactor | rfactor rfactor→ rfactor * | rprimary rprimary→a | b 2)不可以,文法中存在左递归,而自顶向下技术不适合左递归文法 3)消除左递归后的文法

rexpr -> rterm rexpr’ rexpr’-> + rterm rexpr’|ε rterm-> rfactor rterm’ rterm’-> rfactor rterm’|ε rfactor-> rprimay rfactor’ rfactor’-> *rfactor’|ε rprimary-> a | b 4)该文法无左递归,适合于自顶向下的语法分析 习题4.4.1:为下面的每一个文法设计一个预测分析器,并给出预测分析表。可能要先对文法进行提取左公因子或消除左递归 (3)S->S(S)S|ε (5)S->(L)|a L->L,S|S 解 (3) ①消除该文法的左递归后得到文法 S->S’ S’->(S)SS’|ε ②计算FIRST和FOLLOW集合 FIRST(S)={(,ε} FOLLOW(S)={),$} FIRST(S’)={(,ε} FOLLOW(S’)={),$} ③构建预测分析表

编译原理作业

编译原理作业 P7:1.1;1.2自编2.1;2.2自编2.3;2.4自编2.5自编3.1 自编3.2自编3.3;3.4P100.4.1;4.2自编4.3;4.4自编5.1 自编5.2自编7.1;7.2 自编8.1 P7:1.1 P7;1.2 自编2.1 文法G[S]:S→xSx│y所识别的语言是。 a. xyx b. (xyx)* c. x n yx n(n≥0) d. x*yx* 【解答】 自编2.2 令文法G[N]为 G[N]: N→D∣ND D→0∣1∣2∣3∣4∣5∣6∣7∣8∣9 (1) G[N]的语言L(G)是什么? (2) 给出句子0127、34和568的最左推导和最右推导。 【解答】 自编2.3 对于文法G[S]: S→(L)∣aS∣a L→L, S∣S (1) 画出句型(S,(a))的语法树; (2) 写出上述句型的所有短语、直接短语、句柄。 【解答】 自编2.4 已知文法G[S]为S→SaS∣ε,试证明文法G[S]为二义文法。 【解答】 自编2.5 按指定类型,给出语言的文法。 (1) L={a i b j│j>i≥1}的上下文无关文法; (2) 字母表∑={a,b}上的同时只有奇数个a和奇数个b的所有串的集合的正规文法;

自编3.1 什么是扫描器?扫描器的功能是什么? 自编3.2 结合自动机证明:正规式(ab)*a与正规式a(ba)*是否等价?给出分析过程。 自编3.3 已知自动机DFA如图3-4所示 图3-4 DFA 写出其对应的语言,分别用正规文法和自然语言描述。 【解答】 自编3.4 设有L(G)={a2n+1b2m a2p+1| n≥0,p≥0,m≥1}。 (1) 给出描述该语言的正规表达式; (2) 构造识别该语言的确定有限自动机(可直接用状态图形式给出)。【解答】 P100:4.1 P100;4.2 自编4.3 在算符优先分析法中,为什么要在找到最左素短语的尾时才返回来确定其对应的头,能否按扫描顺序先找到头后再找到对应的尾,为什么? 【解答】 自编4.4 设有文法G[S]: S→a|b|(A) A→SdA|S (1) 构造算符优先关系表;

编译原理作业参考答案

第1章引言 1、解释下列各词 源语言:编写源程序的语言(基本符号,关键字),各种程序设计语言都可以作为源语言。 源程序: 用接近自然语言(数学语言)的源语言(基本符号,关键字)编写的程序,它是翻译程序处理的对象。 目标程序: 目标程序是源程序经过翻译程序加工最后得到的程序。目标程序 (结果程序)一般可由计算机直接执行。 低级语言:机器语言和汇编语言。 高级语言:是人们根据描述实际问题的需要而设计的一个记号系统。如同自然语言(接近数学语言和工程语言)一样,语言的基本单位是语句,由符号组和一组用来组织它们成为有确定意义的组合规则。 翻译程序: 能够把某一种语言程序(源语言程序)改变成另一种语言程序(目 标语言程序),后者与前者在逻辑上是等价的。其中包括:编译程序,解释程序,汇编程序。 编译程序: 把输入的源程序翻译成等价的目标程序(汇编语言或机器语言), 然后再执行目标程序(先编译后执行),执行翻译工作的程序称为编译程序。 解释程序: 以该语言写的源程序作为输入,但不产生目标程序。按源程序中语句动态顺序逐句的边解释边执行的过程,完成翻译工作的程序称为解释程序。 2、什么叫“遍” 指对源程序或源程序的中间形式(如单词,中间代码)从头到尾扫描一次,并作相应的加工处理,称为一遍。

3、简述编译程序的基本过程的任务。 编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程,整个过程可以划分5个阶段。 词法分析:输入源程序,进行词法分析,输出单词符号。 语法分析:在词法分析的基础上,根据语言的语法规则把单词符号串分解成各类语法单位,并判断输入串是否构成语法正确的“程序”。 中间代码生成:按照语义规则把语法分析器归约(或推导)出的语法单位翻译成一定形式的中间代码。 优化:对中间代码进行优化处理。 目标代码生成:把中间代码翻译成目标语言程序。 4、编译程序与解释程序的区别 编译程序生成目标程序后,再执行目标程序;然而解释程序不生成目标程序,边解释边执行。 5、有人认为编译程序的五个组成部分缺一不可,这种看法正确吗 编译程序的5个阶段中,词法分析,语法分析,语义分析和代码生成生成是必须完成的。而中间代码生成和代码优化并不是必不可少的。优化的目的是为了提高目标程序的质量,没有这一部分工作,仍然能够得到目标代码。 6、编译程序的分类 目前基本分为:诊断编译程序,优化编译程序,交叉编译程序,可变目标编译程序。

蒋立源 编译原理第三版第二章 习题与答案(修改后)

第2章习题 2-1 设有字母表A1 ={a,b,c,…,z},A2 ={0,1,…,9},试回答下列问题: (1) 字母表A1上长度为2的符号串有多少个? (2) 集合A1A2含有多少个元素? (3) 列出集合A1(A1∪A2)*中的全部长度不大于3的符号串。 2-2 试分别构造产生下列语言的文法: (1){a n b n|n≥0}; (2){a n b m c p|n,m,p≥0}; (3){a n#b n|n≥0}∪{c n#d n|n≥0}; (4){w#w r# | w∈{0,1}*,w r是w的逆序排列 }; (5)任何不是以0打头的所有奇整数所组成的集合; (6)所有由偶数个0和偶数个1所组成的符号串的集合。 2-3 试描述由下列文法所产生的语言的特点: (1)S→10S0S→aA A→bA A→a (2)S→SS S→1A0A→1A0A→ε (3)S→1A S→B0A→1A A→C B→B0B→C C→1C0C→ε (4)S→aSS S→a 2-4 试证明文法 S→AB|DC A→aA|a B→bBc|bc C→cC|c D→aDb|ab 为二义性文法。 2-5 对于下列的文法 S→AB|c A→bA|a B→aSb|c 试给出句子bbaacb的最右推导,并指出各步直接推导所得句型的句柄;指出句子的全部短语。

2-6 化简下列各个文法 (1) S→aABS|bCACd A→bAB|cSA|cCC B→bAB|cSB C→cS|c (2) S→aAB|E A→dDA|e B→bE|f C→c AB|dSD|a D→eA E→fA|g (3) S→ac|bA A→c BC B→SA C→bC|d 2-7 消除下列文法中的ε-产生式 (1) S→aAS|b A→cS|ε (2) S→aAA A→bAc|dAe|ε 2-8 消除下列文法中的无用产生式和单产生式 (1) S→aB|BC A→aA|c|aDb B→DB|C C→b D→B (2) S→SA|SB|A A→B|(S)|( ) B→[S]|[ ] (3) E→E+T|T T→T*F|F F→P↑F|P P→(E)|i 第2章习题答案 2-1 答: (1) 26*26=676 (2) 26*10=260 (3) {a,b,c,...,z, a0,a1,...,a9, aa,...,az,...,zz, a00,a01,...,zzz},共有26+26*36+26*36*36=34658个 2-2 解: (1) 对应文法为G(S)=({S},{a,b},{ S→ε| aSb },S) (2) 对应文法为G(S)=({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε },S) (3)对应文法为G(S)=({S,X,Y},{a,b,c,d,#}, {S→X,S→Y,X→aXb|#, Y→cYd|# },S)

编译原理复习题及参考答案

中南大学网络教育课程考试复习题及参考答案 编译原理 一、判断题: 1.一个上下文无关文法的开始符,可以是终结符或非终结符。 ( ) 2.一个句型的直接短语是唯一的。 ( ) 3.已经证明文法的二义性是可判定的。 ( ) 4.每个基本块可用一个DAG表示。 ( ) 5.每个过程的活动记录的体积在编译时可静态确定。 ( ) 6.2型文法一定是3 型文法。 ( ) 7.一个句型一定句子。 ( ) 8.算符优先分析法每次都是对句柄进行归约。 ( ) 9.采用三元式实现三地址代码时,不利于对中间代码进行优化。 ( ) 10.编译过程中,语法分析器的任务是分析单词是怎样构成的。 ( ) 11.一个优先表一定存在相应的优先函数。 ( ) 12.目标代码生成时,应考虑如何充分利用计算机的寄存器的问题。 ( ) 13.递归下降分析法是一种自下而上分析法。 ( ) 14.并不是每个文法都能改写成 LL(1)文法。 ( ) 15.每个基本块只有一个入口和一个出口。 ( ) 16.一个 LL(1)文法一定是无二义的。 ( ) 17.逆波兰法表示的表达试亦称前缀式。 ( ) 18.目标代码生成时,应考虑如何充分利用计算机的寄存器的问题。 ( ) 19.正规文法产生的语言都可以用上下文无关文法来描述。 ( ) 20.一个优先表一定存在相应的优先函数。 ( ) 21.3型文法一定是 2型文法。 ( ) 22.如果一个文法存在某个句子对应两棵不同的语法树,则文法是二义性的。 ( ) 二、填空题: 1.( )称为规范推导。 2.编译过程可分为(),(),(),()和()五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树,则称这个文法是()。 4.从功能上说,程序语言的语句大体可分为()语句和()语句两大类。 5.语法分析器的输入是(),其输出是()。 6.扫描器的任务是从()中识别出一个个()。 7.符号表中的信息栏中登记了每个名字的有关的性质,如()等等。 8.一个过程相应的DISPLAY表的内容为()。 9.一个句型的最左直接短语称为句型的()。 10.常用的两种动态存贮分配办法是()动态分配和()动态分配。 11.一个名字的属性包括( )和( )。 12.常用的参数传递方式有(),()和()。 13.根据优化所涉及的程序范围,可将优化分成为(),()和()三个级别。 14.语法分析的方法大致可分为两类,一类是()分析法,另一类是()分析法。 15.预测分析程序是使用一张()和一个()进行联合控制的。 16.常用的参数传递方式有(),()和()。 17.一张转换图只包含有限个状态,其中有一个被认为是()态;而且实际上至少要有一个()态。 18.根据优化所涉及的程序范围,可将优化分成为(),()和()三个级别。 19.语法分析是依据语言的()规则进行。中间代码产生是依据语言的()规则进行的。 20.一个句型的最左直接短语称为句型的()。 21.一个文法G,若它的预测分析表M不含多重定义,则该文法是()文法。 22.对于数据空间的存贮分配, FORTRAN采用( )策略, PASCAL采用( )策略。

哈工大编译原理习题及答案

1.1何谓源程序、目标程序、翻译程序、编译程序和解释程序?它们之间可能有何种关系? 1.2一个典型的编译系统通常由哪些部分组成?各部分的主要功能是什么? 1.3选择一种你所熟悉的程序设计语言,试列出此语言中的全部关键字,并通过上机使用该语言以判明这些关键字是否为保留字。 1.4选取一种你所熟悉的语言,试对它进行分析,以找出此语言中的括号、关键字END以及逗号有多少种不同的用途。 1.5试用你常用的一种高级语言编写一短小的程序,上机进行编译和运行,记录下操作步骤和输出信息,如果可能,请卸出中间代码和目标代码。 第一章习题解答 1.解:源程序是指以某种程序设计语言所编写的程序。目标程序是指编译程序(或解释程序)将 源程序处理加工而得的另一种语言(目标语言)的程序。翻译程序是将某种语言翻译成另一种语言的程序的统称。编译程序与解释程序均为翻译程序,但二者工作方法不同。解释程序的特点是并不先将高级语言程序全部翻译成机器代码,而是每读入一条高级语言程序语句,就用解释程序将其翻译成一段机器指令并执行之,然后再读入下一条语句继续进行解释、执行,如此反复。即边解释边执行,翻译所得的指令序列并不保存。编译程序的特点是先将高级语言程序翻译成机器语言程序,将其保存到指定的空间中,在用户需要时再执行之。即先翻译、后执行。 2.解:一般说来,编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成 程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。 3.解:C语言的关键字有:auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while。上述关键字在C语言中均为保留字。 4.解:C语言中括号有三种:{},[],()。其中,{}用于语句括号;[]用于数组;()用于函数(定 义与调用)及表达式运算(改变运算顺序)。C语言中无END关键字。逗号在C语言中被视为分隔符和运算符,作为优先级最低的运算符,运算结果为逗号表达式最右侧子表达式的值(如:(a,b,c,d)的值为d)。 5.略 第二章前后文无关文法和语言 21设有字母表A1={a,b,…,z},A2={0,1,…,9},试回答下列问题: (1) 字母表A1上长度为2的符号串有多少个? (2) 集合A1A2含有多少个元素? (3) 列出集合A1 (A1∪A2)*中的全部长度不大于3的符号串。

编译原理作业集-第七章

第七章语义分析和中间代码产生 本章要点 1. 中间语言,各种常见中间语言形式; 2. 说明语句、赋值语句、布尔表达式、控制语句等的翻译; 3. 过程调用的处理; 4. 类型检查; 本章目标 掌握和理解中间语言,各种常见中间语言形式;各种语句到中间语言的翻译;以及类型检查等内容。 本章重点 1.中间代码的几种形式,它们之间的相互转换:四元式、三元式、逆波兰表示; 3.赋值语句、算术表达式、布尔表达式的翻译及其中间代码格式; 4.各种控制流语句的翻译及其中间代码格式; 5.过程调用的中间代码格式; 6.类型检查; 本章难点 1. 各种语句的翻译; 2. 类型系统和类型检查; 作业题 一、单项选择题: 1. 布尔表达式计算时可以采用某种优化措施,比如A and B用if-then-else可解释为_______。 a. if A then true else B; b. if A then B else false; c. if A then false else true; d. if A then true else false; 2. 为了便于优化处理,三地址代码可以表示成________。 a. 三元式 b. 四元式 c. 后缀式 d. 间接三元式 3. 使用三元式是为了________:

a. 便于代码优化处理 b. 避免把临时变量填入符号表 c. 节省存储代码的空间 d. 提高访问代码的速度 4. 表达式-a+b*(-c+d)的逆波兰式是________。 a. ab+-cd+-*; b. a-b+c-d+*; c. a-b+c-d+*; d. a-bc-d+*+; 5. 赋值语句x:=-(a+b)/(c-d)-(a+b*c)的逆波兰式表示是_______。 a. xab+cd-/-bc*a+-:=;a. xab+/cd-bc*a+--:=;a. xab+-cd-/abc*+-:=;a. xab+cd-/abc*+--:=; 6. 在一棵语法树中结点的继承属性和综合属性之间的相互依赖关系可以由________来描述。 a. 抽象语法树; b. 语法规则; c. 依赖图; d. 三地址代码; 7. 按照教材中的约定,三地址语句if x relop y then L表示成四元式为。 a. (relop,x,y,L); b. (relop,L,x,y); c. (relop,x,L,y); d. (L,x,y,relop); 8. 在编译程序中,不是常见的中间语言形式。 a.波兰式; b. 三元式; c. 四元式; d. 抽象语法树; 9. 在编译程序中安排中间代码生成的目的是________。 a. 便于提高编译效率; b. 便于提高分析的正确性; c. 便于代码优化和目标程序的移植; d.便于提高编译速度; 10. 按照教材中的约定,下面不是类型表达式: a. boolean; b. type-error; c. real; d. DAG; 11. 一个Pascal函数 function f ( a, b:char ) :↑integer; …… 其作用域类型是: a. char×integer; b. char×char; c. char×pointer(integer); d. integer×integer; 12. 因为标识符可用于多种情况,比如常量标识符、变量标识符、过程标识符等等。因此,在符号表中为了给出各个符号的标志,常给标识符引入一个属性kind,然后在相应产生式的语义动作中添加给kind属性赋值的语句。比如,在在产生式D id:T的语义动作中添加赋值语句id.kind= 。 a. V AR; b. CONSTANT; c. PROC; d. FUNC; 13. 下面情况下,编译器需要创建一张新的符号表。 a. 过程调用语句; b. 标号说明语句; c. 数组说明语句; d.记录说明语句; 14. 函数function f(a,b:char):↑integer;… 所以f函数的类型表达式为: a. char×char→pointer(integer); b. char×char→pointer; c. char×char→integer; d. char×char→integer (pointer) 15. 如果一个语言的编译器能保证编译通过的程序,在运行时不会出现类型错误,则称该语言是。 a. 静态的; b. 强类型的; c. 动态的; d. 良类型的; 一.答案:1. b;2. d;3. b;4. d;5. c;6. c.;7. a;8. a;9. c;10. d;11. b;12. a;13. d; 14. a;15. b;

编译原理第8章作业及习题参考答案

第八章 语法制导翻译和中间代码生成 1.给出下面表达式的逆波兰表示(后缀式): (1) a*(-b+c) (4) (A ∧B) ∨(?C ∨ D) (7) if(x+y)*z=0 then s ∶=(a+b)*c else s ∶=a*b*c 解(1) ab-c+* (4) AB ∧C ?D ∨∨ (7) xy+z*0=sab+c*:=sab*c*:=¥(注:¥表示if-then-else 运算) 2. 请将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。 答案:三元式 (1) (+ a, b) (2) (+ c, d) (3) (* (1), (2)) (4) (- (3), /) (5) (+ a, b) (6) (+,(5),c) (7) (- (4), (6)) 间接三元式 间接三元式序列 间接码表 (1) (+ a, b) (1) (2) (+ c, d) (2) (3) (* (1), (2)) (3) (4) (- (3), /) (4) ¥ = := * := + x y z s + c x a b s * c * a b

(5) (- (4), (1)) (1) (6) (- (4), (5)) (5) (6) 四元式 (1) (+, a, b, t1) (2) (+, c, d, t2) (3) (*, t1, t2, t3) (4) (-, t3, /, t4) (5) (+, a, b, t5) (6) (+, t5, c, t6) (6) (-, t4, t6, t7) 3. 采用语法制导翻译思想,表达式E 的"值"的描述如下: 产生式 语义动作 (0) S ′→E {print E.VAL} (1) E →E1+E2 {E.VAL ∶=E1.VAL+E2.VAL} (2) E →E1*E2 {E.VAL ∶=E1.VAL*E2.VAL} (3) E →(E1) {E.VAL ∶=E1.VAL} (4) E →n {E.VAL ∶=n.LEXVAL} 如果采用LR 分析法,给出表达式(5 * 4 + 8) * 2的语法树并在各结点注明语义值VAL 。 4. 假如习题3中表达式E 的“值”有两种类型:整型和实型。语义处理增加"类型匹配检查",请给出相应的语义描述。 S ’ * E1 E2 E0 E3 2 E5.V AL=5 8 5 * E5 E6 + E4 4 E6.V AL=4 E4.V AL=8 E3.V AL=20 E1.V AL=28 E2.V AL=2 E0.V AL=56 Print(56)

编译原理课程作业

编译原理课程作业 一、单选题 1. (4分)文法G所描述的语言是______的集合。 A. 文法G的字符表V中所有符号组成的符号串 B. 文法G的字符表V的闭包V*中的所有符号串 C. 由文法的识别符号推出的所有符号串 D. 由文法的识别符号推出的所有终结符号串 得分:0 知识点:第六章 收起解析 答案 D 解析 第六章属性文法 2. (4分)在LR 分析法中,分析栈中存放的状态是识别规范句型_____的DFA 状态。 A. 句柄 B. 前缀 C. 活前缀 D. LR(0) 项目 得分:0 知识点:第五章 收起解析 答案 C 解析 第五章LR分析法 3. (4分)下面关于解释程序的描述正确的是____. (1) 解释程序的特点是处理程序时不产生目标代码(2) 解释程序适用于COBOL 和FORTRAN 语言(3) 解释程序是为打开编译程序技术的僵局而开发的 A. (1)(2) B. (1) C. (1)(2)(3) D. (2)(3) 得分:0 知识点:第一章 收起解析 答案 B 解析 第一章绪论

4. (4分)动态存储分配可采用的分配方案是()。 A. 队式存储分配 B. 栈式存储分配 C. 线性存储分配 D. 链式存储分配 得分:0 知识点:第八章 收起解析 答案 B 解析 第八章存储空间组织 5. (4分)正规式M 1 和M 2 等价是指_____。 A. M1和M2的状态数相等 B. M1和M2的有向边条数相等 C. M1和M2所识别的语言集相等 D. M1和M2状态数和有向边条数相等 得分:0 知识点:第三章 收起解析 答案 C 解析 第三章正规文法 6. (4分)编写一个计算机高级语言的源程序后,到正式上机运行一般要经过____这几步. (1) 编辑(2) 编译(3) 连接(4) 运行 A. (1)(2)(3)(4) B. (1)(2)(3) C. (1)(3) D. (1)(4) 得分:0 知识点:第一章 收起解析 答案 B 解析 第一章绪论 7. (4分)文法G 产生的()的全体是该文法描述的语言。 A. 句型 B. 终结符集

编译原理(清华大学 第2版)课后习题答案

第三章 N=>D=> {0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD L={a |a(0|1|3..|9)n且 n>=1} (0|1|3..|9)n且 n>=1 {ab,} a n b n n>=1 第6题. (1) <表达式> => <项> => <因子> => i (2) <表达式> => <项> => <因子> => (<表达式>) => (<项>) => (<因子>)=>(i) (3) <表达式> => <项> => <项>*<因子> => <因子>*<因子> =i*i (4) <表达式> => <表达式> + <项> => <项>+<项> => <项>*<因子>+<项> => <因子>*<因子>+<项> => <因子>*<因子>+<因子> = i*i+i (5) <表达式> => <表达式>+<项>=><项>+<项> => <因子>+<项>=i+<项> => i+<因子> => i+(<表达式>) => i+(<表达式>+<项>) => i+(<因子>+<因子>) => i+(i+i) (6) <表达式> => <表达式>+<项> => <项>+<项> => <因子>+<项> => i+<项> => i+<项>*<因子> => i+<因子>*<因子> = i+i*i 第7题

第9题 语法树 s s s* s s+a a a 推导: S=>SS*=>SS+S*=>aa+a* 11. 推导:E=>E+T=>E+T*F 语法树: E +T * 短语: T*F E+T*F 直接短语: T*F 句柄: T*F 12.

短语: 直接短语: 句柄: 13.(1)最左推导:S => ABS => aBS =>aSBBS => aBBS => abBS => abbS => abbAa => abbaa 最右推导:S => ABS => ABAa => ABaa => ASBBaa => ASBbaa => ASbbaa => Abbaa => a1b1b2a2a3 (2) 文法:S → ABS S → Aa S →ε A → a B → b (3) 短语:a1 , b1 , b2, a2 , , bb , aa , abbaa, 直接短语: a1 , b1 , b2, a2 , , 句柄:a1 14 (1) S → AB A → aAb | ε B → aBb | ε (2) S → 1S0 S → A A → 0A1 |ε 第四章 1. 1. 构造下列正规式相应的DFA (1)1(0|1)*101 NFA (2) 1(1010*|1(010)*1)*0 NFA

编译原理课后习题答案+清华大学出版社第二版

第 1 章引论 第1 题 解释下列术语: (1)编译程序 (2)源程序 (3)目标程序 (4)编译程序的前端 (5)后端 (6)遍 答案: (1)编译程序:如果源语言为高级语言,目标语言为某台计算机上的汇编语言或机器语言,则此翻译程序称为编译程序。 (2)源程序:源语言编写的程序称为源程序。 (3)目标程序:目标语言书写的程序称为目标程序。 (4)编译程序的前端:它由这样一些阶段组成:这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段,某些优化工作也可在前端做,也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 (5)后端:指那些依赖于目标机而一般不依赖源语言,只与中间代码有关的那些阶段,即目标代码生成,以及相关出错处理和符号表操作。 (6)遍:是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2 题 一个典型的编译程序通常由哪些部分组成?各部分的主要功能是什么?并画出编译程序的总体结构图。 答案: 一个典型的编译程序通常包含8个组成部分,它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序:输人源程序,拼单词、检查单词和分析单词,输出单词的机内表达形式。 语法分析程序:检查源程序中存在的形式语法错误,输出错误处理信息。 语义分析程序:进行语义检查和分析语义信息,并把分析的结果保存到各类语义信息表中。 中间代码生成程序:按照语义规则,将语法分析程序分析出的语法单位转换成一定形式的中间语言代码,如三元式或四元式。 中间代码优化程序:为了产生高质量的目标代码,对中间代码进行等价变换处理。目标代码生成程序:将优化后的中间代码程序转换成目标代码程序。

编译原理习题答案

《编译原理》习题答案: 第一次: P14 2、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序?它们之间可能有何种关系? 答:被翻译的程序称为源程序; 翻译出来的程序称为目标程序或目标代码; 将汇编语言和高级语言编写的程序翻译成等价的机器语言,实现此功能的程序称为翻译程序; 把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序; 解释程序不是直接将高级语言的源程序翻译成目标程序后再执行,而是一个个语句读入源程序,即边解释边执行; 编译程序是将高级语言写的源程序翻译成目标语言的程序。 关系:汇编程序、解释程序和编译程序都是翻译程序,具体见P4 图 1.3。 P14 3、编译程序是由哪些部分组成?试述各部分的功能? 答:编译程序主要由8个部分组成:(1)词法分析程序;(2)语法分析程序;(3)语义分析程序;(4)中间代码生成;(5)代码优化程序;(6)目标代码生成程序;(7)错误检查和处理程序;(8)信息表管理程序。具体功能见P7-9。 P14 4、语法分析和语义分析有什么不同?试举例说明。 答:语法分析是将单词流分析如何组成句子而句子又如何组成程序,看句子乃至程序是否符合语法规则,例如:对变量 x:= y 符合语法规则就通过。语义分析是对语句意义进行检查,如赋值语句中x与y类型要一致,否则语法分析正确,语义分析则错误。 P15 5、编译程序分遍由哪些因素决定? 答:计算机存储容量大小;编译程序功能强弱;源语言繁简;目标程序优化程度;设计和实现编译程序时使用工具的先进程度以及参加人员多少和素质等等。 补充: 1、为什么要对单词进行内部编码?其原则是什么?对标识符是如何进行内部编码的? 答:内部编码从“源字符串”中识别单词并确定单词的类型和值;原则:长度统一,即刻画了单词本身,也刻画了它所具有的属性,以供其它部分分析使用。对于标识符编码,先判断出该单词是标识符,然后在类别编码中写入相关信息,以表示为标识符,再根据具体标识符的含义编码该单词的值。 补充: 2、赋值语句: A:= 5 * C的语法和语义指的是什么? 答:语法分析将检查该语句是否符合赋值语句规则,语义是指将 5 * C 的结果赋值为 A 。

编译原理作业参考答案

编译原理作业参考答案 作业一 一、是非题 1.(×) 2.(×) 3.(×) 4.(×) 5.(×) 6.(√) 7. (√) 8.(√) 9.(√) 10.(×) 11.(√) 12.(√) 13.(√) 二、填空题 1.(词法分析),(语法分析),(中间代码生成),(代码优化),(目标代码生成) 2.(单词符号),(语法单位)。 3.(源程序),(单词符号) 4.(语法),(语义) 5. (词法分析)、(语法分析)、(语义分析),(中间代码产生),(代码优化),(目标代码生成) 6.(解释方式) 7. (语法规则) 8. (上下文无关文法) 9. (自上而下分析法),(自下而上分析法) 10. (规范推导) 11. (最左归约) 三、名词解释题: 1.词法分析器-----执行词法分析的程序。 2. 自编译方式------先对语言的核心部分构造一个小小的编译程序,再以它为工具构造一个能够编译更多语言成分的较大编译程序。如此扩展下去,就像滚雪球一样,越滚越大,最后形成人们所期待的整个编译程序。 3. 遍-----所谓“遍”就是对源程序或中间结果长头到尾扫描一次,并作有关的加工处理,生成新的中间结果或目标程序。 4. 编译程序-----一种翻译程序: 能够把某一种语言程序(称为源语言程序)转换成另一种语言(成为目标程序),而后着与前者在逻辑上是等价的。 5. 超前搜索-----所谓超前搜索是在词法分析过程中,有时为了确定词性,需超前扫描若干个字符。 6. 短语------令G是一个文法,S划文法的开始符号,假定αβδ是文法G的一个句型,如果

有SαAδ且Aβ,则称β是句型αβδ相对非终结符A的短语。 7. 规范句型------由规范推导所得到的句型。 8. 句柄------一个句型的最左直接短语。 9. -规范推导-----最右推导又称为规范推导。 四、简答题: 1. 正规式a ( a | b )*。 2.(a*b|b*a)={a,b,ab,ba,aab,bba……} 3.状态转换图是一张有限方向图。在状态转换图中,有一个初态,至少一个终态。(用双 圈表示)。一个状态转换图可用于识别(或接受)一定的字符串。 4. 证明: 因为 L(b(ab)*)={b}{ε, ab, abab, ababab, …} ={b, bab, babab, bababab, …} L(ba)*b)={ε, ba, baba, bababa, …}{b} ={b, bab, babab, bababab, …} = L(b(ab)*) 所以, b(ab)*=( ba)*b 5. 正规表达式为b(a|b)*aa 6. 词法分析器的功能输入源程序,按照构词规则分解成一系列单词符号。 7. 词法分析是编译过程中的一个阶段,在语法分析前进行。词法分析作为一遍,可以简化设计,改进编译效率,增加编译系统的可移植性。也可以和语法分析结合在一起作为一遍,由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。 8. 编译预处理:滤掉空格,跳过注释、换行符等。 9. 句子adccd 的分析过程:

相关文档
相关文档 最新文档