《编译原理》样卷及答案

一、简答题（每题4分，共24分）构造一个文法G，使得：L(G)={(m)m|m>0}解答：G[S]:s->()|(S)构造一个正规式，它接受={0，1}上符合以下规则的字符串：串内有且只有2个1的0、1字符串全体。解答：0*10*10* 消除文法G[S]中的直接左递归和回溯 S→(L)|aS|a L→L，S|S解答：S→(L)|aS' S'→S|ε L→SL' L'→，SL'|ε4、文法G[S]是乔姆斯基几型文法？S→ABS|ABAB→BAA→0B→1解答：1型文法/上下文有关文法5、按Thmopson算法构造与正则表达式(1*|0)*等价的NFA。解答：略6、设计一个状态转换图，其描述的语言规则为：如果以a开头，则其后是由a、b组成的任意符号串；如果以b开头，则其后是至少包含一个a的由a、b组成的任意符号串。解答：略二、（本题10分）对于文法G[E]：E→ET+|TT→TF*|FF→F^|a(1)给出句子FF^^*的最左推导和语法树；(2)给出句子FF^^*的短语、直接短语和句柄。解答：(1)2分：句子FF^^*的最左推导2分：句子FF^^*的语法树E=>T=>TF*=>FF*=>FF^*=>FF^^*(2)3分:句子FF^^*的短语FF^^*、FF^^*、F、F^、F^^2分:句子FF^^*的直接短语F、F^1分:句子FF^^*的句柄F三、（本题15分）构造与下列NFA等价的最小化DFA。解答：（1）10分：构造与NFA等价的DFA（2）5分：对DFA最小化首先，将所有的状态集合分成子集：k1={0,1,2,4}k2={3,5}四、（本题15分）对下列文法G[S]：s→eT|RTT→DR|εR→dR|εD→a|bd(1)写出文法G[S]每个非终结符的FIRST集和FOLLOW集；(2)判断文法G[S]是否LL(1)文法（注：必须给出判断过程，否则不得分）；(3)写出文法文法G[S]的预测分析表。解答：（1）8分：每个First集合和FOLLOW集合各1分FIRST集FOLLOW集s→eT|RT{e}{a,b,d,ε}#T→DR|ε{a,b}{ε}#R→dR|ε{d}{ε}a,b,#D→a|bd{a}{b}D,#(2)2分：判断文法G[S]是LL(1)文法。对于产生式s→eT|RT：FIRST(eT)∩FIRST(RT)-ε={e}∩{a,b,d}=ΦFIRST(eT)∩FOLLOW(S)={e}∩{#}=Φ对于产生式T→DR|ε：FIRST(DR)∩FOLLOW(T)={a,b}∩{#}=Φ`对于产生式R→dR|ε：FIRST(dR)∩FOLLOW(R)={d}∩{a,b,#}=Φ对于产生式D→a|bd：FIRST(a)∩FIRST(bd)={a}∩{b}=Φ所以，对于文法G[S]是LL(1)文法。(3)5分：文法G[S]的预测分析表。五、（本题18分）已知文法G[S]：S→rDD→D，i|i(1)画出识别文法活前缀的完整DFA，并判断该文法是否LR(0)文法(必须说明判断依据)；(2)构造该文法的SLR(1)分析表，并判断该文法是否SLR(1)文法(必须说明判断依据)。解答：(1)8分：画出识别文法活前缀的完整DFA文法拓展并对产生式编号：（0）S'→S（1）S→rD（2）D→D，i（3）D→i(2)2分：判断该文法不是LR(0)文法对于状态3，项目集中存在“移进-规约”冲突，所以该文法不是LR(0)文法。(3)6分：构造该文法的SLR(1)分析表状态ACTIONGOTOr，i#SD0S211acc2S433S5r14r3r35S66r2r2(4)2分：判断文法是SLR(1)分析表回答1：因为SLR(1)分析表不存在冲突，所以文法是SLR(1)分析表。回答2：对于状态3，FOLLOW(S)∩{,}=(#)∩{,}=Ф，“移进-规约”冲突可以用SLR(1)方法解决，所以文法是SLR(1)分析表。六、（本题8分）文法G[E]的LR分析表如下图所示：(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→(E)(6)F→i写出对输入串i*i+i的LR分析过程(即状态，符号，输入串的变化过程)。解答:七、（本题10分）写出下列语句的四元式序列if(y>z&&(c<d||m>n))while(a>b)x=x+y*a;elsem=m+n;解答：1(j>,y,z,3)2(j,-,-,13)3(j<,c,d,7)4(j,-,-,5)5(j>,m,n,7)6(j,-,-,13)7(j>,a,b,9)8(j,-,-,13/16)9(*,y,a,t0)10(+,x,t0,t1)11(=,t1,-,x)12(j,-,-,7)13(j,-,-,16)14(-,x,1,t5)15(=,t5,-,x)16..........华中师范大学网络教育学院《编译原理》练习测试题库一、填空1.若源程序是用高级语言编写的，目标程序是______，则其翻译程序称为编译程序。

2.词法分析和语法分析本质上都是对源程序的______进行分析。

3.如果源语言(编写源程序的语言)是高级语言，而目标语言是某计算机的汇编语言或机器语言，则这种翻译程序称为_____。

4.对编译程序而言，输入数据是_______,输出结果是________。

5.______，是构成语言文法的单词，是语法成分的最小单位。

6.由PL／0的EBNF可知，PL／0语言可看成是PASCAL语言的子集，它的编译程序是一个__________。

7.由于PL／0编译程序采用_________，所以语法分析过程BLOCK是整个编译过程的核心。

8.用语法图描述语法规则的优点是______、________。

9.每个非终结符是一个语法成分，在书写语言程序时并不出现，它是由_________和_________、或终结符串定义的。

10.PL／0的目标程序为假想栈式计算机的汇编语言，与具体计算机______。

11.PL／0的编译程序和目标程序的解释执行程序都是用_______书写的，因此PL／0语言可在配备_________的任何机器上实现。

12.PL／0编译程序是用PASCAL语言书写的，整个编译程序(包括主程序)是由______个嵌套及并列的过程或函数组成

13.当源程序编译正确时，PL／0编译程序自动调用__________，对目标代码进行解释执行，并按用户程序要求输入数据和输出运行结果。

14.由于对某些非终结符可以递归定义，这就使得_________可用有穷的文法描述。

15.______的任务是识别由词法分析给出的单词符号序列在结构上是否符合给定的文法规则。

16.PL／0编译程序的语法分析采用了____________。

17.语法分析程序除总控外主要有两大部分的功能，即_________和__________.

18.PL／0的词法分析程序GETSYM，是一个独立的过程，其功能是为_________提供单词用的，是______的基础，它把输入的字符串形式的源程序分割成一个个单词符号。

19.每个过程应有过程首部以定义局部于它自己过程的常量、变量和过程标识符，也称_____。

20.词法分析程序GETSYM将完成的任务有:______,识别保留字；_______,拼数,拼复合词,输出源程序.

21.如果一个PL／0语言的单词序列在整个语法分析中，都能逐个得到匹配，直到_________，这时就说所输入的程序是正确的。

22.若要构造程序设计语言的编译程序，则首先要对程序设计语言本身有较为精确的描述。而关于程序设计语言的描述，将涉及_____、语义和______三个方面。

23.凡是具有某种特殊性质的客体的聚合，都可称为______。

24.如果集合中元素个数为零，即集合中不含有任何元素，这样的集合称为_______，记为φ。

25.设有集合A和B，如果A和B有相同的元素，则称这两个集合是_______.

26.设A、B为任意两个集合，由所有属于集合A或属于集合B的元素组成的集合，叫做集合A与B的_______．

27.设A、B为任意两个集合，由所有用于集合A且属于集合B的元素组成的集合，称为集合A与B的_______.

28.如果一个集合，它能包含我们所要考虑目标之内的所有元素，则称此集合为_____，记为E。

29.设A为一集合，由A的所有子集(包括空集及A本身)所组成的集合，称为A的______.

30.由两个按一定次序排列的客体组成的序列，称为_____.

31.设A和B为任意两个集合，若序偶的第一个成员是集合A的一个元素，第二个成员是集合B的一个元素，则所有这样的序偶组成的集合称为集合A和B的__________.

32.在集合X上的关系R，如对任意x∈X，均有(x，x)∈R，则称关系R是______。

33.在集合X上的关系R，如果合(x，y)∈R，便必有(y，x)∈R，则称关系R是________。

34.在集合X上的关系R，如果合(x，y)∈R且(y，z)∈R，必有(x，z)∈R，则称关系R是______。

35.例设P={（1，2），（3，4），（2，2）}Q={（4，7），（2，9），（3，1）}

则P·Q=____________________________

36.符号串与符号组成顺序______，如符号串ab______ba，符号申001也______010。

37.假设G是一个文法，S是文法的开始符号，如果S=>*x,则称x是________。

38.文法G产生的_______的全体是该文法描述的语言。

39.一个文法G[Z]若存在推导序列Z=>+···Z···,

则称G(z)→u中的左部符号U(U不是识别符号)，不在所属文法的任何其他规则右部出现，那么这条规则在推导中不起作用，即所有句子的推导始终不会用到此规则，显然这种规则是多余的。也称这种非终结符为_________.

55.从文法的某个非终结符号U推不出终结符号串，显然，所有含有U的规则是多余的。也称这种非终结符为________。

56.若L是上下文有关语言、上下文无关语言或正规语言，则L∪{ε}和L-{ε}分别是上下文有关语言、_____和正规语言。

57.设有文法G，对于其中某一非终结符号U可能作出一些不同推导U=>+Sx，其中S叫头符号，由于推导不同，由U产生的头符号S也可能不同，这些头符号S构成的集合，称为U的推导的__________.

58.一个上下文无关文法G包括四个组成部分依次是：_____,______,_______,_______.11

59.文法所描述的语言是_______的集合。

60.词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓冲区称________。二、选择1.编译程序是一种常用的_________软件。A.应用

B.系统C.工具D.测试

2.在使用高级语言编程时，首先可通过编译程序发现源程序的全部______错误和部分______错误。

A.语法B.语义

C.语用

D.运行

3.编译程序生成的目标程序_____是机器语言的程序。

A.一定

B.不一定C.某种情况下一定D.某种情况下不一定

4.编译程序生成的目标程序_______是可执行的程序。

A.一定

B.不一定C.某种情况下一定D.某种情况下不一定

5.一个语言的文法是_____.

A．惟一的

B．不惟一的

C.个数有限的D.无限的

6.巴科斯-诺尔范式(即BNF)是一种广泛采用的_____的工具。

A．描述规则

B.描述语言

C．描述文法

D．描述句子

7.设r=(a|b|c)(x|y|z)则L（r）中元素为个（）A．9B．6C．18D．278、正则集合L={an|n≧0}相应的正则表达式是（）A．a*B．a+C．aa*D．aa+9.编译过程中扫描器的任务包括______。

①组织源程序的输入

②按词法规则分割出单词，识别出其属性，并转换成属性字的形式输出

⑧删除注解

④删除空格及无用字符

⑤行计数、列计数

⑥发现并定位词法错误

⑦建立符号表

A．②③④⑦

B．②③④⑥⑦

C．①②③④⑥⑦

D．①②③④⑤⑥⑦

10、编译过程中，语法分析器的任务是______。

a.分析单词是怎样构成的

b.分析单词串是如何构成语句和说明的

c.分析语句和说明是如何构成程序的

d.分析程序的结构

A.bc

Bd

C．bcd

D．abcd

11、语法分析的常用方法是________。

a.自顶向下

b.自底向上

c.自左向右

d.自右向左

A．abcd

B．ab

C．cd

D．abc

12、编译程序中的语法分析器接受以________为单位的输入，并产生有关信息供以后各阶段使用。

A．表达式

B．产生式

C．单词

D．语句13、LL(1)文法的条件是_______。

A．对形如U->Xl|X2|…|Xn的规则，要求FIRST(Xi)∩FIRST(Xj)=Φ，(i≠j)

B．对形如U->Xl|X2|…|Xn的规则，若Xi=>*ε，则要求FIRST(Xj)∩FOLLOW(U)

=Φ

C．A和B

D．都不是

14、一个右线性文法G一定是（）A．LL（1）文法C．SLR（1）文法B．LR（1）文法D．上述三者都不是

15、算符文法是指______的文法。26

①没有形如U->…VW…的规则(U，V，W∈VN)

②终结符号集VT中任意两个符号对之间至多有一种优先关系成立

⑧没有相同的规则右部

④没有形如U->ε的规则

A.①

B．①②

C．①②③

D．①②③④

16、算符优先文法是指______的文法。

①没有形如U->…VW…的规则(U，V，W∈VN)

②终结符号集VT中任意两个符号对之间至多有一种优先关系成立

⑧没有相同的规则右部

④没有形如U->ε的规则

A.①②

B．①②③

C.①②③④

D．①②④

17、下列文法G[S]的句型aR／aSb／aTb／,b

的最左素短语

为______。

S->aTb|，

T->R

R->R／S|S

A.aTb

B.aSb

C.S

D.R／

18、算符优先分析法每次都是对______进行归约，简单优先分析法每次都是对句柄进行归约。A．最左短语B.简单短语C.最左素短浯D．素短语19、xab+cde-*f/:=是赋值语句()相应的后缀式A．x:=a+b+c*d-e/fB．x:=a+(b+c)*d-e/fC．x:+a+b+c*(d-e)/fD．x:=a+b+c+(c*d)-e/f20、LR(K)方法是______。

A．从左到右分析，每次走K步的一种编译方法

B．从左到右分析，共经过K步的一种编译方法

C．从左到右分析，每次向前预测K步的一种编译方法

D．从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法

21、下面三个文法中，为SLR(1)文法的是______。10

G1：P->PaP|b

G2：P->bPb|cPc|b|c

G3：P->bPb|bPc|d

A.仅Gl

B．仅G2

C．仅G3

D．G2和G3

22、有下列文法：11

S->Pa|Pb|c

P->Pd|Se|f

该文法是______。

A.LL(1)文法

B.SLR(1)文法

C.a和b

D.都不是

23．代码优化的主要目标是()12

①如何提高目标程序的运行速度

②如何减少目标程序运行所需的空间

③如何协调①和②

④如何使生成的目标代码尽可能短

A①②

B①②③

C①②④

D

①②③④

24、设文法G（S为其开始符号）产生式如下：S→aSb|ab|ε则G是一个（）A．LR（1）文法B．SLR（1）文法C．三型文法D．二型文法25在编译程序采用的优化方法中，_____是在循环语句范围内进行的。12

①合并已知常量

②删除多余运算，

③删除归纳变量

④强度削弱

⑤代码外提

A①④

B①⑤

C①④⑤

D③④⑤

26合并表达式中常量运算的目的是_____。12

①合并常量，使表达式中的常量尽可能少

②合并常量，使表达式尽可能简短

③将可在编译时刻计算的常量运算在编译时刻计算出来，然后用所计算出来的值替换表达式中出现的所有这种常量运算，使得生成的代码指令尽可能少

A①

B②

C③

D

①②③

27

下面的程序段可以进行哪些优化_____。12

i：=1

j：=l0

read

k

L：x：=x*i

y：=j*i

z：=x*y

writej

i：=i+1

ifi<100

goto

L

halt

①合并已知常量

②删除多余运算

③删除归纳变量

④强度削弱

⑤代码外提

可选项有：

A．①④

B①⑤

C，①④⑤

D．③④⑤

28.属于低级语言的是（）AFortranB.PascalC.LispDMasm29.设oct是字母表{0，1，…，7}中的任何一个元素，表示C语言的八进制无符号整规表达式是（）。A.(oct)8B.(oct)*C.(oct)+D.(oct)#30.采用（）实现三地址代码时，不利于对中间代码进行优化。31.一个正规语言只能对应()？A一个正规文法；B一个最小有限状态自动机；32．文法G[A]：A→εA→aBB→AbB→a是()：A正规文法B二型文法C.上下无关文法D.不确定 33．下面说法正确的是()：A一个SLR（1）文法一定也是LALR（1）文法B一个LR（1）文法一定也是LALR（1）文法34．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的()：A．必要条件B．充分必要条件

C.充分条件D．无法确定35．PL/0语言的目标程序解释执行时用到的数据对象有()：A目标代码CODEB符号表TABLEC关键字表WORDD数据栈S36.PL/0语言编译时产生或使用的数据对象不包括()：A目标代码CODEB符号表TABLEC数据栈SD关键字表WORD

37、编译程序是一种常用的_________软件。A.应用B.系统C支撑D.自动化38、在使用高级语言编程时，首先可通过编译程序发现源程序的全部______错误和部分语义错误。A.语法B语义C.语用D.运行39.一个LR（1）文法合并同心集后若不是LALR（1）文法：A则可能存在移进/归约冲突B则可能存在归约/归约冲突C则可能存在移进/归约冲突和归约/归约冲突D不存在冲突40、运算符与运算对象类型不符"属于______。A.语法错误B.语义错误C.语用错误D.规则41．语言是A．句子的集合B．产生式的集合C．符号串的集合D．句型的集合42．编译程序前三个阶段完成的工作是A．词法分析、语法分析和代码优化B．代码生成、代码优化和词法分析C．词法分析、语法分析、语义分析和中间代码生成D．词法分析、语法分析和代码优化43．一个句型中称为句柄的是该句型的最左A．非终结符号B．短语C．句子D．直接短语44．下推自动机识别的语言是A．0型语言B．1型语言C．2型语言D．3型语言45．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即A．字符B．单词C．句子D．句型46．对应Chomsky四种文法的四种语言之间的关系是A．L0L1L2L3B．L3L2L1L0C．L3=L2L1L0D．L0L1L2=L347．词法分析的任务是A．识别单词B．分析句子的含义C．识别句子D．生成目标代码48．常用的中间代码形式不含A．三元式B．四元式C．逆波兰式D．语法树49．代码优化的目的是A．节省时间B．节省空间C．节省时间和空间D．把编译程序进行等价交换50．代码生成阶段的主要任务是A．把高级语言翻译成汇编语言B．把高级语言翻译成机器语言C．把中间代码变换成依赖具体机器的目标代码D．把汇编语言翻译成机器语言51．语言是A．句子的集合B．产生式的集合C．符号串的集合D．句型的集合52．编译程序前三个阶段完成的工作是A．词法分析、语法分析和代码优化B．代码生成、代码优化和词法分析C．词法分析、语法分析、语义分析和中间代码生成D．词法分析、语法分析和代码优化53．一个句型中称为句柄的是该句型的最左A．非终结符号B．短语C．句子D．直接短语54．下推自动机识别的语言是A．0型语言B．1型语言C．2型语言D．3型语言55．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即A．字符B．单词C．句子D．句型56．对应Chomsky四种文法的四种语言之间的关系是A．L0L1L2L3B．L3L2L1L0C．L3=L2L1L0D．L0L1L2=L357．词法分析的任务是A．识别单词B．分析句子的含义C．识别句子D．生成目标代码58．常用的中间代码形式不含A．三元式B．四元式C．逆波兰式D．语法树59．代码优化的目的是A．节省时间B．节省空间C．节省时间和空间D．把编译程序进行等价交换60．代码生成阶段的主要任务是A．把高级语言翻译成汇编语言B．把高级语言翻译成机器语言C．把中间代码变换成依赖具体机器的目标代码D．把汇编语言翻译成机器语言三、名词解释题1．词法分析2．LL(1)文法3．语法树4．LR(0)分析器5．语言和文法四、判断题1．正规文法产生的语言都可以用上下文无关文法来描述。

……

(

)2．仅考虑一个基本块，不能确定一个赋值是否真是无用的。………（）3．如果一个文法是递归的，则其产生的语言的句子是无穷个。

…（）4．四元式之间的联系是通过符号表实现的。…………（）5．文法的二义性和语言的二义性是两个不同的概念。

…………（

）6．一个LL(l)文法一定是无二义的。………………

(

)7．在规范规约中用最左素短语来刻划可归约串。…

……………

(

)8．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。……………

(

)9．编译程序是对汇编程序的翻译。

……（）10．逆波兰法表示的表达式亦称前缀式。

……………

(

)五、简答题1.“含有优化部分的编译程序的执行效率高”，这种说法正确吗？

2.有人认为编译程序的五个组成部分却一不可，这种看法正确吗？

3.解释程序定义哪些寄存器?

4.PL／0编译程序对语法错误的处理采用哪两种办法?

5.解释说明指令LIT?LOD?STO?CAL?INT?JMP?JPC?OPR?5

6.已知文法G(S)

S→a|∧|(T)

T→T，S|S

写出句子((a，a)，a)的规范归约过程及每一步的句柄。7.何谓优化？按所涉及的程序范围可分为哪几级优化？

8.目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？9.写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。

10.写一个文法，使其语言是奇数集，且每个奇数不以0开头。11.编译程序的结构是什么?12.关系有哪些基本性质？

13.解释字母表,符号,符号串,符号串的长度,符号串联结？

14.自下而上分析算法的基本思想是什么？15.设有文法G：

s::=Qc|c

Q::=Rb|b

R::=Sa|a

试求HARD(S),HARD(Q),HARD(R).16.用扩充的BNF范式表示下述文法以消去ε规则：

S::=aABb|ab

A::=Aab|ε

B::=Aa|a

17.考虑下面程序

…………

Vara：integer；

ProcedureS(X)；

VarX：integer；

Begin

a：＝a＋1；

X：＝a＋X

End；

Begin

a：＝5；

S(a)；

Print(a)

End．

试问：若参数传递方式分别采取传名和传值时，程序执行后输出a的值是什么？

18.设有文法G[I]:8

I->I1/I0/Ia/Ic/a/b/c

判断下面符号串中哪些是该文法的句子.

(1)ab0

(2)a0c01

(3)aaa

(4)bc10

(5)aabc

(6)bbca

19.为了正确地对源程序进行编译，不允许文法有二义性，那么怎样才能排除文法的二义性呢?9

20.什么是简单子树？

21.什么是子树？

22.什么是句型的分析？

23.自下而上分析算法的基本思想是什么？

24.设有文法G：

s::=Qc|c

Q::=Rb|b

R::=Sa|a

试求HARD(S),HARD(Q),HARD(R).25．编译程序和高级语言有什么区别?26．编译程序的工作分为那几个阶段?27．简述自下而上的分析方法。28．简述代码优化的目的和意义。

六、综合题1.Whilea＞0∨b＜0do

Begin

X：＝X＋1；

ifa＞0thena：＝a－1

elseb：＝b＋1

End；

翻译成四元式序列。

2.设布尔表达式的文法为

E→E(1)∨E(2)

E→E(1)∧E(2)

E→i

假定它们将用于条件控制语句中，请

(1)改写文法，使之适合进行语法制导翻译和实现回填；

(2)写出改写后的短个产生式的语义动作。

3.设文法G(S)：

S→(L)|aS|a

L→L，S|S

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

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

对下列文法G:26

S'->#S#

S->D(R)

R->R;P|p

P->S|i

D->i

计算文法中每个非终结符的FIRSTVT集和LASTVT集。5.将下列赋值语句译成三地址代码。A[i,j]:=B[i,j]+C[A[k,l]]+D[i+j]

6、设布尔表达式的文法为

E→E(1)∨E(2)

E→E(1)∧E(2)

E→i

假定它们将用于条件控制语句中，请

(1)改写文法，使之适合进行语法制导翻译和实现回填；

(2)写出改写后的短个产生式的语义动作。7、（8分）给定PASCAL程序语句whilea>bdoifa>0thena:=a-1elsea:=a+1;1.将该语句翻译成逆波兰式；2.给出编译程序扫描到then处及分号处时所得的四元式序列。8.如何计算FIRST集？9．证明下述文法G：SaSbS|aS|d是二义性文法。10．对于文法G[S]：SAB，AAa|bB，Ba|Sb求句型baSb的全部短语、直接短语和句柄？句型baSb的语法树如图五(2)所示。AASBbBSab图五(2)句型baSb的的语法树11．设有非确定的有自限动机NFAM=({A，B，C}，{0，1}，，{A}，{C})，其中：(A，0)={C}(A，1)={A，B}(B，1)={C}(C，1)={C}。请画出状态转换距阵和状态转换图。华中师范大学网络教育学院《编译原理》练习测试题库参考答案一、填空1.机器语言程序或汇编程序

2.结构

3.编译程序

4.源程序，目标程序。

5.终结符

6.编译解释执行系统

7.一趟扫描方法

8.直观、易读

9.终结符和非终结符串

10.无关

11.PASCAL语言

12.18

13.解释执行程序

14.无穷的句子集

15.语法分析

16.自顶向下的递归子程序法

17.说明部分的处理,程序体部分的处理

18.语法分析,语法分析

19局部量

20滤空格,识别标识符,输出源程序

21程序结束符

22.语法,语用

23.集合

24.空集

25.相等的

26.并集

27.交集

28.全集

29.幂集

30.序偶

31.笛卡尔乘积

32.自反的

33.对称的

34.传递的

35.{（1，9），（3，7），（2，5）}

36.有关,不同于,不同于

37.句型

38.句子

39.(1)递归

(2)无数

40.四种

41.上下文无关的

42.规范推导

43.规范句型

44.不同

45.语法树

46.简单短语

47.句型

48.短语

49.简单短语

50.句柄

51.句柄

52.传递闭包

53.语法图

54.不可达到的

55.不可终止的

56.上下文无关语言

57.头符号集合

58.终结符号，非终结符号，开始符号，产生式

59.由文法的识别符推出的所有终结符号串

60.输入缓冲区

二、选择1.B2.A3.B4.B5.B6.B7.B8.A9.D10.C11.B12.C13.C14.A15.A16.D17.B18.D19.A20.D31.B32.B33.A34.A35.A36.C37.B38.A39.B40.A51A52C53D54C55B56B57A58D59C60C名词解释题1词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。2若文法的任何两个产生式A|都满足下面两个条件：（1）FIRST()FIRST()=；（2）若*，那么FIRST()FOLLOW(A)=。我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。3句子的树结构表示法称为语法树(语法分析树或语法推导树)。给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的语法树。这棵树具有下列特征：(1)根节点的标记是开始符号S。(2)每个节点的标记都是V中的一个符号。(3)若一棵子树的根节点为A，且其所有直接子孙的标记从左向右的排列次序为A1A2…AR，那么AA1A2…AR一定是P中的一条产生式。(4)若一标记为A的节点至少有一个除它以外的子孙，则AVN。(5)若树的所有叶节点上的标记从左到右排列为字符串w，则w是文法G的句型；若w中仅含终结符号，则w为文法G所产生的句子。4所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作(是移进还是按某一产生式进行归约等)。5文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法G定义为四元组的形式：G=(VN，VT，P，S)其中：VN是非空有穷集合，称为非终结符号集合；VT是非空有穷集合，称为终结符号集合；P是产生式的集合(非空)；S是开始符号(或识别符号)。这里，VN∩VT=，SVN。V=VN∪VT，称为文法G的字母表，它是出现文法产生式中的一切符号的集合。文法G所描述的语言用L(G)表示，它由文法G所产生的全部句子组成，即L(G)={x|SÞ*x，其中S为文法开始符号，且}简单的说，文法描述的语言是该文法一切句子的集合。四判断题

1、×

2、√

3、√

4、×

5、√

6、√

7、×

8、√

9、×

10、×五、简答题1.答：含有优化功能的编译程序，其优化是指对生成的目标代码进行优化，而不是编译程序本身得到优化，它提高目标代码的效率，而不是编译程序的效率。所以，上述说法不对。

2.答：不正确。编译程序的五个组成部分中，词法分析，语法分析，语义分析和代码生成是必须完成的，而代码优化是为了提高目标程序的质量，它不是必需的，没有优化部分的编译程序也能生成目标代码。

3.指令寄存器,程序地址寄存器,栈顶寄存器,基址寄存器

4.(1)对于一些易于校正的错误，如丢了逗号、分号等，则指出出错位置，并加以校正。校正的方式就是补上逗号或分号。

(2)对某些错误，编译程序难于确定校正的措施，为了使当前的错误不致影响整个程序的崩溃，把错误尽量局限在一个局部的语法单位中。这样就需跳过一些后面输入的单词符号，直到读入一个能使编译程序恢复正常语法分析工作的单词为止。

5.LIT：将常量值取到运行栈顶。LOD：将变量放到栈顶。STO：将栈顶的内容送入某变量单元中。CAL：调用过程的指令。INT：为被调用的过程(或主程序)在运行栈中开辟数据区。JMP：无条件转移指令。JPC：条件转移指令。OPR：关系运算和算术运算指令。将栈顶和次栈顶的内容进行运算，结果存放在次栈顶，此外还可以是读写等特殊功能的指令

6.句型归约规则句柄

((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

7.优化：对程序进行各种等价变换，使得从变换后的程序出

发，能产生更有效的目标代码。三种级别：局部优化、循环优化、全局优化。8.目标代码通常采用三种形式：机器语言，汇编语言，待装配

机器语言模块。应着重考虑的问题：

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

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

(3)如何充分利用指仅系统的的特点。9.逆波兰表示：

abc*＋ab＋/d－三元式序列：

①(*，b，c)

②(＋，a，①)

③(＋，a，b)

④(/，②，③)

⑤(－，④，d)10.文法G(N)：

N→AB|B

A→AC|D

B→1|3|5|7|9

D→B|2|4|6|8

C→0|D11编译过程的六个阶段的任务，再加上表格管理和出错处理的工作可分别由几个模块或程序完成，它们分别称作词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序和出错处理程序。12自反的

在集合X上的关系R，如对任意x∈X，均有(x，x)∈R，则称关系R是自反的。

非自反的

在集合X上的关系R，如对任意x∈X，均有(x，x)R，则称关系R是非自反。对称的

在集合X上的关系R，如果合(x，y)∈R，便必有(y，x)∈R，则称关系R是对

称的。

非对称的

在集合X上的关系R，如果有(x，y)∈R丛x≠y，便必有(y，x)R，则称关系R是非对称的。

传递的

在集合X上的关系R，如果合(x，y)∈R且(y，z)∈R，必有(x，z)∈R，则称关系R是传递的。13.

元素的非空有穷集合。字母表中的元素。由字母表中的符号组成的任何有穷序列，惯用小写字母t、u、v、x、y…表示符号串。长度是符号串所含符号的个数。设有符号串x和y，把y的符号写在x的符号之后所得的符号串，叫做x与y的联结，记为xy。14答：从所给符号串x开始，在其中寻找与文法的某条规则右部相匹配的子串，并用该规则的左部取代此子串(即归约)，重复此过程，步步向上归约，最后试图将符号串x归约到文法的识别符号Z。如归约成功，则符号串x是文法的句子。15

HARD(S)={S,Q,R,a,b,c}

HARD(Q)={S,Q,R,a,b,c}

HARD(R)={S,Q,R,a,b,c}16S::=aABb|ab

A::={ab}

B::=Aa|a17传名：a＝12传值：a＝618.(1)错误

(2)正确

(3)正确

(4)正确

(5)错误

(6)错误

(7)错误19.(1)在语义上加些限制，或者说加一些语法的非形式规定。这样做不必改变文法中原有的语法规则。

(2)把排除二义性的规则合并到原有文法中，即构造一个等价的无二义性的文法G'。这样做，需要改造原有文法。20.只有单层分支的子树称为简单子树。21.由某一结点及其所有分支组成的部分，成为原语法树的一棵子树。22.句型的分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。23.从所给符号串x开始，在其中寻找与文法的某条规则右部相匹配的子串，并用该规则的左部取代此子串(即归约)，重复此过程，步步向上归约，最后试图将符号串x归约到文法的识别符号Z。如归约成功，则符号串x是文法的句子。24.

HARD(S)={S,Q,R,a,b,c}

HARD(Q)={S,Q,R,a,b,c}

HARD(R)={S,Q,R,a,b,c}25用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器语言表示的目标程序（这个过程即编译），才能由计算机执行。执行转换过程的程序叫编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序转换过的叫目标程序，也就是机器语言。编译程序的工作情况有三种：汇编型、解释型和编译型。汇编型编译程序用来将汇编语言编写的程序，按照一一对应的关系，转换成用机器语言表示的程序。解释型编译程序将高级语言程序的一个语句，先解释成为一组机器语言的指令，然后立即执行，执行完了，取下一组语句解释和执行，如此继续到完成一个程序止。用解释型编译程序，执行速度很慢，但可以进行人和计算机的"对话"，随时可以修改高级语言的程序。BASIC语言就是解释型高级语言。编译型编译程序将级语言编写的程序，一次就会部翻译成机器语言表示的程序，而且过程进行很快，在过程中，不能进行人机对话修改。FORTRAN语言就是编译型高级语言。26词法分析、语法分析和语义分析是对源程序进行的分析(称为编译程序的前端)，而中间代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合(称为编译程序的后端)，它们从源程序的中间表示建立起和源程序等价的目标程序27所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根节点。28代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行一种等价变换，在保证变换前后代码执行结果相同的前提下，尽量使目标程序运行时所需要的时间短，同时所占用的存储空间少。五、综合题每题10分，3题共30分1.解：

(1)(j＞，a，0，5)

(2)(j，－，－，3)

(3)(j＜，b，0，5＝

(4)(j，－，－，15)

(5)(＋，×，1，T1)

(6)(：＝，T1，－，×)

(7)(j≥，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)2.解：(1)E0→E(1)

E→E0E(2)

EA→E(1)

E→EAE(2)

E→i

(2)E→E(1)

{BACKPATCH(E(1)·FC，NXQ)；

E0·TC：＝E(1)·TC}

E→E0E(2)

{E·FC：＝E(2)·FC；

E·TC：＝MERG(E0·TC，E(2)·TC)}

EA→E(1)

{BACKPATCH(E(1)·TC，NXQ)；

E0·FC：＝E(1)·FC}

E→EAE(2)

{E·TC：＝E(2)·TC；

E·FC：＝MERG(EA·FC，E(2)·FC)

E→i

{E·TC：＝NXQ；E·FC：＝NXQ＋1；

GEN(jn2，entry(i)，－0)；

GEN(j，－，－，0)3解：(1)

S→(L)|aS’

S’→S|ε

L→SL’

L’→SL’|ε

(2)

FIRST)S)＝{(，a}FOLLOW(S)＝{#，，，)}

FIRST(