华师网络2014年9月课程考试《编译原理》练习测试题库及参考答案

1、华中师范大学网络教育学院编译原理练习测试题库及参考答案一、填空若源程序是用高级语言编写的目标程序是序。词法分析和语法分析本质上都是关于源程序的进行分析。言或机器语言，则这种翻译程序称为。关于编译程序而言，输入数据是,输出结果是。 ，是构成语言文法的单词，是语法成分的最小单位。由PL0的EBNF可知语言可看成是PASCAL语言的子集，它的编译程序是一个。由于PL0编译程序采，所以语法分析进程BLOCK是整个编译进程的核心。用语法图描述语法规则的优点是、。 、或终结符串定义的。PL0的目标程序为假想栈式计算机的汇编语言，与具体计算机。PL0的编译程序和目标程序的解释执行程序都是用书写的因此PL0语

2、言可在配备的任何机器上实现。PL0PASCAL 个嵌套及并且列的进程或函数组成当源程序编译正确时，PL0编译程序自动调用，关于目标代码行解释执行，并且按用户程序要求输入数据和输出运行结果。由于关于某些非终结符可以递归定义，这就使得描述。 定的文法规则。PL0编译程序的语法分析采用了。语法分析程序除总控外主要有两大部分的功能，即和.PL0的词法分析程序GETSYM，是一个独力的进程，其功能是为 提供单词用的， 是的基础，它把输入的字符串形式的源程序分隔成一个个单词符号。也称。词法分析程序GETSYM将完成的任务有:,识别保留字,拼数拼复合词,输出源程序.如果一个PL0语言的单词序列在整个语法分析

3、中，都能逐个得到匹配，直到，这时就说所输入的程序是正确的。若要构造程序设计语言的编译程序，则首先要关于程序设计语言本身有较为精确的描述而关于程序设计语言的描述将涉及语义和三个方面凡是具有某种特殊性质的客体的聚合，都可称为。如果集合中元素个数为零，即集合中不含有任何元素，这样的集合称为 ，记为 。设有集合A和B，如果A和B有相同的元素，则称这两个集合是.设AB为任意两个集合由一切属于集合A或属于集合B的元素组成的集合， 叫做集合A与B的设A、B为任意两个集合，由一切用于集合A且属于集合B的元素组成的集合，称为集合A与B的. ，记为E。设A为一集合，由A的一切子集(囊括空集及A本身)所组成的集合，

4、称为A 的.由两个按一定次序排列的客体组成的序列，称为.设ABA个成员是集合 B 的一个元素，则一切这样的序偶组成的集合称为集合 A 和 B 的 .在集合X上的关系如关于任意均有 则称关系R是。在集合X上的关系R，如果合(x，y)便必有(y，x)则称关系R 是。在集合X上的关系R，如果合(x，y)R且(y，z)必有(x，z)R， 则称关系R是。例则PQ= 符号串与符号组成顺序，如符号串 abba，符号申 001 也 。假设G是一个文法，S是文法的开始符号，如果S=*x,则称x是。文法G产生的法列,则称G(z)是文法，这类文法所产生的句子有个乔姆斯基把文法分成类型.四个文法类的定义是逐渐增加限制

5、的，因此每一种正规文法都是.最右推导常被称为。由规矩推导所得的句型称为。文法的二义性和语言的二义性是两个的概念。关于于上下文无关文法，是句型推导进程的几何表示。直接短语也称.每棵语法树的叶子组成一个.每棵子树的叶子组成一个.每棵简单子树的叶子组成一个.最左边简单子树的叶子组成.一个句型的最左直接短语称为该句型的。系，而且推导=+为直接推导=的。 是语言文法的等价表示，可用它来代替BNF某条规则Uu中的左部符号U(U不是识别符)，不在所属文法的任何其他到此规则，显然这种规则是多余的。也称这种非终结符为.从文法的某个非终结符号U推不出终结符号串，显然，一切含有U的规则是多余的。也称这种非终结符为。

6、若LL 和L 诀别是上下文有关语言、和正规语言。设有文法G，关于于其中某一非终结符号U可能作出一些不同推导U=+Sx， 其中S叫头符号由于推导不同由U产生的头符号S也可能不同这些头符号S构成的集合，称为U的推导的.一 个 上 下 文 无 关 文 法 G ,.11文法所描述的语言是的集合。中，这个缓冲区称。二、选择编译程序是一种常用的软件应用B. 系统C.工具.测试在使用高级语言编程时首先可经过编译程序发现源程序的全部错误部分错误。语法语义C.语用. 运行编译程序生成的目标程序一定不一定 某种情况下一定.某种情况下不一定编译程序生成的目标程序是可执行的程序。一定不一定某种情况下一定.某种情况下不

7、一定一个语言的文法是.A惟一的B 不惟一的C. 个数有限的 .无限的巴科斯-诺尔范式(即BNF)是一种广泛采用的的工具A描述规则B.描述语言C 描述文法 描述句子中元素为 个（）A9278、正则集合L=an|n0相应的正则表达式是（ ）Aa* Ba+ Caa* aa+编译进程中扫描器的任务囊括。组织源程序的输入按词法规则分隔出单词，识别出其属性，并且转换成属性字的形式输出删除注解删除空格及无用字符行计数、列计数发现并且定位词法错误建立符号表A B C 10、编译进程中，语法分析器的任务是。分析单词是怎样构成的分析单词串是如何构成语句和说明的分析语句和说明是如何构成程序的分析程序的结构BC bc

8、 abc 、语法分析的常用方法是a. 自顶向下 b. 自底向上 c. 自左向右 . 自右向左A abcB abC c abc12、编译程序中的语法分析器接受以供以后各阶段使用。A 表达式B 产生式C 单词语句13、文法的条件是。A关于形如U-Xl|X2| |Xn 的规则，要求 FIRST(Xi)FIRST(Xj)= ，(ij) B关于形如 U-Xl|X2| |Xn 的规则，若 Xi=* ，则要求 FIRST(Xj)FOLLOW(U) =CA B 14、一个右线性文法G 一定是 （ ） ALL（1）文法 CSLR（1）文法BLR（1）文法 上述三者都不是15、算符文法是指的文法。26没有形如U-

9、 VW的规则 (U，V，WVN)终结符号集VT 中任意两个符号关于之间至多有一种优先关系成立没有相同的规则右部没有形如U- 的规则 B C 16、算符优先文法是指的文法。没有形如U- VW的规则 (U，V，WVN)终结符号集VT 中任意两个符号关于之间至多有一种优先关系成立没有相同的规则右部没有形如U- 的规则B C. 17、下列文法GS的句型aRaSbaTb,b的最左素短为。S-aTb| ，T-RR-R A.aTbB.aSbC.S.R 18算符优先分析法每次都是关于柄进行归约。A最左短语简单短语C. 最左素短浯素短19、+ce是赋值语句() 相应的后缀式20、方法是。从左到右分析，每次走K步

10、的一种编译方法K步的一种编译方法K步的一种编译方法从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法21、下面三个文法中，为SLR(1)文法的是。G1 ：P-PaP|bG2 ：P-bPb|cPc|b|c G3 ：P-bPb|bPc|仅GlB 仅G2C 仅G3 G2和22、有下列文法：11S-Pa|Pb|c P-P|Se|f该文法是。A.LL(1) 文法B.SLR(1) 文法C.a 和b.都不是23代码优化的主要目标是()12 如何减少目标程序运行所需的空间 如何协调和 如何使生成的目标代码尽可能短A BC 24、设文法G（S 为其开始符号）产生式如下： G 是一个（ ）文法 文

11、法C三型文法二型文法在编译程序采用的优化方法中，是在循环语句范围内进行的。12合并且已知常量删除多余运算，删除归纳变量强度削弱代码外提A BC合并且表达式中常量运算的目的是。12合并且常量，使表达式中的常量尽可能少合并且常量，使表达式尽可能简短将可在编译时刻计算的常量运算在编译时刻计算出来，然后用所计算出来的值替换表达式中出现的一切这种常量运算，使得生成的代码指令尽可能少A BC 下面的程序段可以进行哪些优化。i：=1j：=reakL ：x：= x*iy：= j*i z：= x*y write j i：= i+1 合并且已知常量删除多余运算删除归纳变量强度削弱代码外提可选项有：AB C ， 属

12、于低级语言的是（ ）AFortranB.PascalMasm设 oct 是字母表0，1，7中的任何一个元素，表示C 语言的八进制无符号整规表达式是（ 。A.(oct)8B.(oct)*C.(oct)+.(oct)#采用（）实现三地址代码时，不利于关于中间代码进行优化。间接三元式 C. .有向无循环图一个正规语言只能关于应(A 一个正规文法；B 一个最小有限状态自动机；C.一个下推自动机.一个确定的有限自动机文法Ba是(A 正规文法B 二型文法上下无关文法. 不确定下面说法正确的是(A SLR（1）文法B LR（1）LALR（1）文法无关文法消除了左递归，提取了左公共因子后是满文 法的()：必

13、要 条 件 C. 充分条件无法确定PL/0语言的目标程序解释执行时用到的数据关于象有(A 目标代码COEB TABLE C 关键字表 数据栈SPL/0语言编译时产生或使用的数据关于象不囊括(A 目标代码COEB C 数据栈S 关键字表WOR37、编译程序是一种常用的软件应用系统C支撑.自动化38在使用高级语言编程时首先可经过编译程序发现源程序的全部错和部分语义错误。语法B语义C. 语用.运行39LALR（1）文法： A 则可能存在移进/归约冲突B 则可能存在归约/归约冲突C 则可能存在移进/归约冲突和归约/归约冲突 不存在冲突40、运算符与运算关于象类型不符属于。语法错误B. 语义错误C. 语

14、用错误.规41语言是A句子的集合产生式的集合C符号串的集合句型的集42编译程序前三个阶段完成的工作是词法分析、语法分析和代码优化一个句型中称为句柄的是该句型的最左A非终结符号B短语C句子直接短44下推自动机识别的语言是A0型语言B1型语言C2型语言3型语言扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独力含义的最小语法单位即A字符单词C句子句46关于应Chomsky四种文法的四种语言之间的关系是AL0L1L2L3BL3L2L1L0CL3=L2L1L0L0L1L2=L3词法分析的任务是A识别单词分析句子的含义C识别句子目标代码48常用的中间代码形式不含A三元式四元式C逆波兰式语法树代

15、码优化的目的是A节省时间节省空间C节省时间和空间交换50代码生成阶段的主要任务是把汇编语言翻译成机器语言51语言是A句子的集合B产生式的集合C符号串的集合句型的集编译程序前三个阶段完成的工作是AC53一个句型中称为句柄的是该句型的最左A非终结符号B短语C句子直接短下推自动机识别的语言是A0型语言B1型语言C2型语言3型语言的最小语法单位即A字符B单词C句子句关于应Chomsky四种文法的四种语言之间的关系是A3 B0C=0=357词法分析的任务是A识别单词B分析句子的含义C识别句子生成目标代常用的中间代码形式不含A三元式B四元式C逆波兰式语法树59 代码优化的目的是A节省时间B节省空间C节省时

16、间和空间代码生成阶段的主要任务是AC三、名词解释题1词法分析LL(1)文法语法树LR(0)分析器语言和文法四、判断题1 正 规 文 法 产 生 的 语 言 都 可 以 用 上 下 文 无 关 文 法来 描述。 ( )（）（）（）文法的二义性和语言的二义性是两个不同的概念。 （）一个LL(文法一定是无二的。 () 在 规 范 规 约 中 用 最 左 素 短 语 来 刻 划 可 归 约串。()目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。()9编译程序是关于汇编程序的翻译。（）10 逆波 兰 法 表示 的 表达 式 亦称 前 式。 ( )五、简答题有人认为编译程序的五个组成部分却一不可，

17、这种看法正确吗？解释程序定义哪些寄存器?PL0解释说明指令LITLOSTOCALINTJMPCOPR?5已知文法G(S) Sa|(T)TT，S|S目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？写出表达式(ab*c)/(ab)的逆波兰表示及三元式序列。0开头。编译程序的结构是什么?关系有哪些基本性质？解释字母表, 符号, 符号串,符号串的长度符号串联结？自下而上分析算法的基本思想是什么？试求HAR(S),HAR(Q),HAR(R).BNF范式表示下述文法以消去 规则：S:=aABb|ab A:=Aab| B:=Aa|a考虑下面程序； Proceure ； a：a1；X：aX En；B

18、egina：5； S(a)； Print(a)Ena 的值是什么？判断下面符号串中哪些是该文法的句子.(1) ab0 (2)a0c01 (3)aaa (4)bc10 (5)aabc (6)bbca?9什么是简单子树？什么是子树？什么是句型的分析？自下而上分析算法的基本思想是什么？试求HAR(S),HAR(Q),HAR(R).简述自下而上的分析方法。简述代码优化的目的和意义。六、综合题While a0 b0 o BeginX：X1；if a0 thena：a1elseb：b1En；翻译成四元式序列。E(1(2)E(1(2)E i假定它们将用于条件控制语句中，请改写文法，使之适合进行语法治导翻译和

19、实现回填；写出改写后的短个产生式的语义动作。设文法G(S)： S(L)|a S|a LL，S|S消除左递归和回溯；计算每个非终结符的FIRSTFOLLOW；关于下列文法G26 S-#S#S-(R)R-R; P|pP-S|i -i计算文法中每个非终结符的FIRSTVT 集和LASTVT 集 。Ai,j :=Bi,j + CAk,l +i+j6、设布尔表达式的文法为EE(1)E(2)EE(1)E(2)E i假定它们将用于条件控制语句中，请改写文法，使之适合进行语法治导翻译和实现回填；7（8）PASCALwhile ab o if a0 then a:=a-1 else a:=a+1;将该语句翻译成

20、逆波兰式；给出编译程序扫描到then如何计算FIRST集？表明下述文法G：是二义性文法。SaSbS|aS|关于于文法baSb句型baSb 的语法树如图五(2)所示。SABbBSa图五(2) 句型 baSb 的的语法树设有非确定的有自限动机NFAM=(A0)=C (A1)=A，B 1)=C (C1)=C。请画出状态转换距阵和状态转换图。华中师范大学网络教育学院编译原理练习测试题库参考答案一、填空机器语言程序或汇编程序结构编译程序源程序，目标程序。终结符编译解释执行系统一趟扫描方法直观、易读终结符和非终结符串无关PASCAL语言12.18语法分析自顶向下的递归子程序法说明部分的处理,程序体部分的处

21、理语法分析,语法分析局部量滤空格,识别标识符输出源程序程序结束符语法,语用相等的笛卡尔乘积.有关,不同于不同于递归(2) 无数四种上下文无关的不同语法树简单短语简单短语传递闭包语法图上下文无关语言头符号集合终结符号，非终结符号，开始符号，产生式由文法的识别符推出的一切终结符号串输入缓冲区二、选择1.B2.A3.B4.B5.B6.B7.B8.A9.10.C11.B12.C13.C14.A15.A16.17.B18.19.A20.21.C22.B23.B24.25.26.27.C28.29.30.C31.B32.B33.A34.A35.A36.C37.B38.A39.B40.A41.A42.C43

22、.44.C45.B46.B47.A48.49.C50.C51A52C5354C55B56B57A5859C60C三名词解释题从构成源程序的字符串中识别出一个个具有独力意义的最小语法单位， 并且转换成统一的内部表示Aa| b都满足下面两个条件：FIRST(a ) FIRST( b) =b*e FIRST(aFOLLOW( A) = 。我们把满足这两个条件的文法叫做 LL(1)斍泛，其中的第一个 L 代表从左向右扫描输入，第二个L 表示产生最左推导，1 代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些鲜明的性质，它不是二义的，也不含左递归。句子的树结构表

23、示法称为语法树(语法分析树或语法推导树)。给定文法G=(VN，VT，P，S)，关于于 G 的任何句型都能构造与之关联的语法树。这棵树具有下列特征：S。V中的一个符号。A，且其一切直接子孙的标记从左向右的排列次序为一定是P中的一条产生式。AAVN。wwG的句型；若w 中仅含终结符号，则w 为文法G 所产生的句子。所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的 每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并且至多再0个输入符号，就能确定相关于于某一产生式左部符号的句柄是否(是移进还是按某一产生式进行归约等)。文法G定义为四元组的形式：G=(VN，VT，P，S)其中

24、：VN 是非空有穷集合，称为非终结符号集合；VT 是非空有穷集合， 称为终结符号集合；P是产生式的集合(非空)；S是开始符号(或识别符号)。=VG文法G 所描述的语言用L(G)表示，它由文法 G 所产生的全部句子组成，即TS*xS x V + T简单的说，文法描述的语言是该文法一切句子的集合。四 判断题2356、9、五、简答题以，上述说法不关于。没有优化部分的编译程序也能生成目标代码。指令寄存器,程序地址寄存器,栈顶寄存器,基址寄存器以校正。校正的方式就是补上逗号或分号。为止。OPR：关系运还可以是读写等特殊功能的指令6.句型归约规则句柄(a，a)，a)Saa(S，a)，a)TSS(T，a)，

25、a)Saa(T，S)，a)TT，ST ，S(S)，a)TSS(T)，a)SS(T)(T)(S，a)TSS(T，a)Saa(T，S)TT，ST ，S(T)S(T)(T)S发，能产生更有效的目标代码。三种级别：局部优化、循环优化、全局优化。机器语言模块。应着重考虑的问题：如何使生成的目标代码较短；如何充分利用寄存器，以减少访问内存次数；如何充分利用指仅系统的的特点。逆波兰表示：abc*ab/(*，b，c) (，a，) (，a，b)(/，)(，)NAB|B AAC| B1|3|5|7|9 B|2|4|6|8 C0|程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序和出错处理程序。自

26、反的在集合X上的关系R，如关于任意xX，均R，则称关系R是自反的。非自反的 在集合X上的关系R，如关于任意xX，均有R，则称系R是非自反。关于称的在集合X上的关系R，如果(x，y)R，便必 R，则称关系R是关于称的。非关于称的 在集合X 上的关系R R，则称关系R 是非关于称的。传递的 在集合 X 上的关系 R，如果合(x，y) R 且(y，z) R，必有(x，z) R，则称关系R 是传递的。13元素的非空有穷集合。字母表中的元素。由字母表中的符号组成的任何有穷序列，惯用小写字母tuvxy表示符号串。长度是符号串所含符号的 xyyx 的符号之后所得的符号串，叫做x与yxy。答：从所给符号串x开

27、始，在其中寻找与文法的某条规则右部相匹配的子串， 并且用该规则的左部取代此子串(即归约将符号串x归约到文法的识别符号Zx是文法的句子。HAR(S)=S,Q,R,a,b,cHAR(Q)=S,Q,R,a,b,cHAR(R)=S,Q,R,a,b,c17传名：a12传值：a618. (1)错误法中原有的语法规则。文法。这样做，需要改造原有文法。只有单层分支的子树称为简单子树。由某一结点及其一切分支组成的部分，成为原语法树的一棵子树。x 开始，在其中寻找与文法的某条规则右部相匹配的子串，并且用该规则的左部取代此子串(即归约)，反复此进程，步步向上归约，最后试x Zx 是文法的句子。HAR(S)=S,Q,

28、R,a,b,c HAR(Q)=S,Q,R,a,b,c HAR(R)=S,Q,R,a,b,c语言表示的目标程序（这个进程即编译），才能由计算机执行。执行转换进程的程序叫编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序转换过的叫目标程序，也就是机器语言。编译程序的工作情况有三种：汇编型、解释型和编译型。汇编型编译程序用来将汇编语言编写的程序，依照一一关于应的关系，转换成用机器语言表示的程序。关于话语言就是解释型高级语言。编译型编译程序将在进程中，不能进行人机关于话修改。语言就是编译型高级语言。词法分析、语法分析和语义分析是关于源程序进行的分析(称为编译程序的前端(称为编译程序的后端)，它

29、们从源程序的中间表示建立起和源程序等价的目标程序 27所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根节点。28代码优化是尽快生成“好的代码的编译阶段。也就是要关于程序代码进行一种等价变幻，在保证变幻前后代码执行结果相同的前提下，尽快使目 标程序运行时所需要的时间短，同时所占用的存储空间少。五、综合题每题 10 分，3 题共 30 分1. 解：(1) (2) (3) (4) (5) (，1，T1)(6) (：，T1，)(7) (j，a，0，9)(8) (j，12)(9) (，a，1，T2)(10) (：，T2，a

30、)(11) (j，1)(12)(13) (：，T3，b)(14) (j，1)2. 解：(1) E0E(1)EE0E(2) EAE(1) EEAE(2)Ei (2) EE(1)BACKPATCH(E(1)FC，NXQ)； E0TC：E(1)TCEE0E(2)EFC：E(2)FC； ETC：MERG(E0TC，E(2)TC)EAE(1)BACKPATCH(E(1)TC，NXQ)； E0FC：E(1)FCEEAE(2)ETC：E(2)TC； EFC：MERG(EAFC，E(2)FC)EiETC：NXQ；EFC：NXQ1； GEN(jn2，entry(i)，0)；GEN(j，0)3(1)S(L)|aS

31、 SS| LSLLSL|(2)FIRST)S)(，aFOLLOW(S)#，)FIRST(S)，a,FIRST(L)(，aFOLLOW(S)#，)FOLLOW(L) )FIRST(L)，FOLLOW(L )(3)a，()SSaSS(L)SSSSSSSSLLSLLSLLLL4.(1) 文法G 中每个非终结符的FIRSTVT 集和LASTVT 集为： FIRSTVT(s)=# FIRSTVT(P)=i,()FIRSTVT(s)=(,i) FIRSTVT()=iFIRSTVT(R)=;,(,i)(2) 文法GLASTVT5.t11 := i * 20t12 := t11+j t13 := A-84; t14 := 4*t12t15 := t13t14 /Ai,j t21 := i*