编译原理试题

二、填空题：

1、从功能上说，程序语言的语句大体可分为执行性语句和说明性语句两大类。

2、扫描器的任务是从源程序中识别出一个个单词符号0

3、所谓最右推导是指：任何一步a->B都是对a中最右非终结符进行替换的

4、语法分析最常用的两类方法是自上而下和自下而上分析法。

5、一个上下文无关文法所含四个组成部份是一组终结符号，一组非终结符号、一个开始符

号、一组产生式。

6、所谓语法制导翻译方法是为每一个产生式配上一个翻译子程序，并在语法分析的同时

执行这些子程序.

7、符号表中的信息栏中登记了每一个名字的有关的性质，如类型、种属、所占单元大小、

地址等等。

三.名词解释

1.遍一一指编译程序对源程序或者中间代码程序从头到尾扫描一次。

3.语法分析一一按文法的产生式识别输入的符号串是否为一个句子的分析过程。

4.短语一一令G是一个文法。S划文法的开始符号，假定aB3是文法G的一个句型，

如果有SaA"且AB,则称B是句型aB相对非终结符A的短语。

5.后缀式----种把运算量写在前面，把算符写在后面的表示表达式的方法。

四、简答题

3、写出表达式（a+b*c）/（a+b）—d的逆波兰表示及三元式序列。

逆波兰表示：

abc*+ab+/d一（2分）

三元式序列：

①（*,b,c）

②（+,a,①）

③（+,a,b）

④（/,②，③）

⑤（一，④，d）（2分）

4、已知文法G（S）

S-a|A|（T）

T-*T,S|S

写出句子（（a,a）,a）的规范归约过程及每一步的句柄。

句型归约规则句柄

((a,a),a)S-*aa

((S,a),a)T-SS

((T,a),a)S-*aa

((T,S),a)T-T,ST,S

((S),a)T-SS

((T),a)S^S(T)(T)

(S,a)T-SS

(T,a)S-*aa

(T,S)T-T,ST,S

(T)S一(T)(T)

S(4分)

5、何谓优化？按所涉及的程序范围可分为哪儿级优化？

答：优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目

标代码。(2分)

三种级别：局部优化、循环优化、全局优化。(2分)

6、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？

答：目标代码通常采用三种形式：机器语言，汇编:吾言，待装配机器语言模块。(2分)

应着重考虑的问题：

(1)如何使生成的FI标代码较短；

(2)如何充分利用寄存器，以减少访问内存次数；

(3)如何充分利用指仅系统的的特点。(2分)

五、计算题

1、写一个文法，使其语言是奇数集，且每一个奇数不以0开头。(5

分)解：文法G(N)：

N-*AB|B

A-AC|D

B-1|3|5|7|9

D-*B|2|4|6|8

C-*O|D(5分)

2、设文法G(S)：

S-*(L)|aS|a

LT,S|S

(1)消除左递归和回溯；

(2)计算每一个非终结符的FIRST和FOLLOW；

(3)构造预测分析表。

解：(1)

S-*(L)|aS'

S'-S|£

LTL，

L「SL'|e

评分细则：消除左递归2分,提公共因子2分。

⑵

FIRST)S)={(,a}FOLL»V(S)=寓，，)}

FIRSTS)={，&£}roLL»v(s,)={#,,,))

FIRST(L)={(,a}FOLLOW(L)={))

FIRST(L，)={…£}FOLLOW(f)={)}

3、Whilea>0orb<0do

Begin

X：=X+i；

ifa>0thena：=a—1

elseb：=b+l

End；

翻译成四元式序列。(7分)

解:

(1)(j>,a,0,5)

(2)(j,—,—,3)

(3)(j<,b,0,5)

(4)(j,—,—>15)

(5)(+,X,1,Tl)

(6)(：=,Tl,一，X)

(7)(户，a,0,9)

(8)(j,—,—,12)

(9)(-,a,1,T2)

(10)(:=,T2,a)

(11)(j,—,—,1)

(12)(+,b,1,T3)

(13)(：=,T3,一，b)

(14)(j,—♦—,1)

(15)

评分细则：控制结构4分，其它3分。

4、已知文法G(E)

EfE+T

T-*F|T*F

F-(E)|i

(1)给出句型(T*F+i)的最右推导及画出语法树；

(2)给出句型(T*F+i)的短语、素短语。(7分)

解：(1)最右推导：

ETF(E)(E+T)(E+F)(E+i)

(T+i)(T*F+i)

(2)短语：(W+i),T*F+i,T*F,i(2分)

素短语：T*F,i(1分)

二、填空题(每题2分，共20分)

1、语法分析是依据语言的语法规则进行的，中间代玛产生是依据语言的语义规则进行

的。

2、程序语言的单词符号普通可以分为关键字、标识符、常量、算符、界符等等。

3、语法分析器的输入是单词符号串，其输出是语法单位

4、所谓自上而下分析法是指从开始符号出发，向下推导，推出句子。

5、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。

6、对于文法G,仅含终结符号的句型称为句子

7、逆波兰式ab+c+d*c-所表达式为(a+b+c)*d-e。

8、一个名字的属性包括类型和作用域。

9、对于数据空间的存贮分配，FORTRAN采用静态存储分配策略，PASCAL采用动态存储分

配策略。

10、所谓优化是指对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的

四元式2分

(l).(+,a,b,T1)

(2).(-,a,b,T2)

(3).(/,T1,T2,T3)

(4).(*,b,c,T4)

(5).(+,a,T4T5)

(6).(-,T3,T5,T6)

5、符号表的作用是什么？

答：作用：登记源程序中浮现的各种名字及其信息，以及编译各阶段的发展状况v(2分)

五、计算题(共41分)

1、写一个文法，使其语言是偶数集，且每一个偶数不以0开头。(5分)

文法G(S):

S->AB|B|A()

A—ADIC

B->2|4|6|8

CTi|3|5|7|9|B

D->O|C

2、己知文法G(S):

S-a|A|(T)

T->T,S|S

⑴给出句子(a,(a,a))的最左推导并画出语法树；

⑵给出句型((T,S),a)的短语、直接短语、句柄。(8分)

最左推导：(2分)

S=>(T)=>(T,S)=>(S,S)

=>(a,S)=>(a,(T))=>(a,(T,S)|

=>(a,(S,S))=>(a,(a,S))

=>(a,(a,a))

3、把语句

ifx>0Ay>0thenz:=x+y

elsebegin

x:=x+2;

y：=y+3

END;

翻译成四元式序列。(6分)

⑴(j>,x,0,3)

(3)(j>,y,0,5)

⑷(，丁,8)

(5)(+,x,y,T1)

⑹(：=,T1,-,Z)

⑺。丁,12)

(8)(+,x,2,T2)

(9)(:=,t2,-,X)

(10)(+,Y,3,t3)

(11)(:=,T3,-,y)

⑫

(控制结构3分，其它3分)

4、设文法G(S):

S->S+aF|aF|+aF

F—*aFl*a

⑴消除左递归和回溯；

⑵构造相应的FIRST和FOLLOW集合；

(3)构造预测分析表(10分)

4、答:

(1)(消除左递归2分，提公共左因子2分)

S—aFS'|+aFS'

S'->+aFS'|e

F—»*aF

F-F|£

⑵(3分)

FIRST(S)={a,+}FOLLOW(S)={#}

FIRST(S')={+,E}FOLLOW(S')={#}

FIRST(F)={*}FOLLOW(F)={+,#}

FIRST(F)={*,E)FOLLOW(F')={+,#}

⑶3分)____________________

a+*#

S-

s—>+

SaFS

aFS1

1

S'

SJ+

S'―►

aFS'

c

FT*

F

aF

F

F'->

F'FJ£—►

F

£

一选择题(每空2分，共20分)

1、文法G产生的⑴的全体是该文法描述的语言，

A.句型B.终结符集C.非终结符集D.句子

2、若文法G定义的语言是无限集，则文法必然是⑵：

A.递归的R先言文无关的C.二义性的D.无二义性的

3、Chomsky定义的四种形式语言文法中，0型文法又称为⑶文法；1型文法又称

为⑷文法；2型语言可由⑸识别。

(3):A.短语结构文法B.先后文无关文法C.先后文有关文法D.正规文法

E.图灵机F.有限自动机G.下推刍动机

(4)A.短语结构文法B.先后文无关文法C.先后文有关文法D.正规文法

E.图灵机F.有限自动机G.下推刍动机

(5)A.短语结构又法B.先后文无关文法C.先后文有关文法D.正规文法

E图灵机F.有限自动机G.下推自动机

4、一个文法所描述的语言是⑹；描述一个语言的文法是⑺。

(6):A.惟一的B.不惟一的C.可能惟一，可能不惟一

(7):A.惟一的B.不惟一的C.可能惟一，可能不惟一

5、数组的内情向量中肯定不含有数组的⑻的信息

A.维数B.类型C.维上下界D.各维的界差

6、在下述的编译方法中，自底向上的方法有⑼，白顶向下的分析方法有(10)o

①简单优先分析②算符优先分析③递归下降分析④预测分析技术

⑤LR(K)分析⑥SLR(k)分析⑦LL(k)分析⑧LALR(K)分析

(9):A.③B.③④⑧C.①②⑧D.③④⑤⑥⑦

E.@@⑤⑥⑦F.⑥⑧

(10):A.③④⑦B.③④⑧C.®®⑧D.®®⑤⑥⑦

E.0@⑤⑥⑦F.①©⑤⑥⑧

1D2A3A4C5C6A7B8A9F10A

一、简答题

1.LL(1)分析法对文法有哪些要求？

对于G中的每一个产生式A-*Y1|Y2|...|ym,其各候选式均应满足：

(1)不同的候选式不能推出以同一终结符号打头的符号串，即FIRST(yi)AFIRST(y

j><P(1<i»j<m：iWj)

(2)若有yj£,则其余候选式yi所能推出的符号串不能以FOLLOW(A)中的终结符

号开始,即有FIRST(yiIAFOLLOW(A)=(p(i<l,2,...,m:i/j)

三、(8分)化简文法G[S]：

S->ASe|BCaD|aD|AC

ACb|DBS

C->bC|d

B—>Ac

D->aD

化简后：S->ASe|ACA->CbC->bC|d

五、(12分)已给文法G[S]：S->SaP|Sf|PP->qbP|q

将G[S]改造成LL(1)文法，并给出LL(1)分析表

改造后的文法：S-PSS—aPS||fS」eP—qPP—bP|e

各候选式的FIRST集，各非终结符的FOLLOW集为

产生式FIRST集FOLLOW集

STPS{q}{#}

S'TaPS'{a}{#}

TfS'{f}

—>e{e}

P—qP{q}{a,f,#)

P'—bP{b}{a,f,#)

—e{e}

LL(1)分析表为:

abfq用

SPS，

S'fS，z

P