大三下课件汇总编译原理习题集

1、习题一、单项选择题1、将编译程序分成若干个“遍”是为了 a提高程序的执行效率 b使程序的结构更加清晰。c利用有限的机器内存并提高机器的执行效率 d利用有限的机器内存但降低了机器的执行效率2、构造编译程序应掌握 a源程序 c编译方法。b目标语言 d以上三项都是3、变量应当 a持有左值。b持有右值 d既不持有左值也不持有右值上。b词法分析 d管理表格c既持有左值又持有右值 4、编译程序绝大多数时间花在a出错处理 c目标代码生成5、不可能是目标代码。a汇编指令代码 c绝对指令代码b可重定位指令代码 d中间代码6、使用可以定义一个程序的意义。a语义规则 c产生规则7、词法分析器的输入是 a单词符号串

2、c语法单位b词法规则 d词法规则。b源程序 d目标程序8、中间代码生成时所遵循的是- a语法规则c语义规则。b词法规则 d等价变换规则9、编译程序是对 a汇编程序的翻译 c机器语言的执行10、语法分析应遵循 a语义规则 c构词规则解答。b高级语言程序的解释执行 d高级语言的翻译。b语法规则 d等价变换规则1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选 b。2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选 d。3、对编译而言，变量既持有左值又持有右值，故选 c。4、编译程序打交道最多的就是各种表格，因此选 d。5、目标代码包括汇编指令代码、可重定位指令代码

3、和绝对指令代码 3 种，因此不是目标代码的只能选 d。6、词法分析遵循的是构词规则，语法分析遵循的是语法规则，中间代码生成遵循的是语义规则，并且语义规则可以定义一个程序的意义。因此选 a。7、b8、c9、d10、c二、多项选择题1、编译程序各阶段的工作都涉及到。a语法分析b表格管理c出错处理d语义分析2、编译程序工作时，通常有 a词法分析码生成d语义检查解答1b、c2. a、b、c、e三、填空题e词法分析阶段。 b语法分析c中间代e目标代码生成1、解释程序和编译程序的区别在于2、编译过程通常可分为 5 个阶段，分别是。、语法分析、代码优化，最后3、编译程序工作过程中，第一段输入是程序。和目标代

4、码生成。阶段的输出为4、编译程序是指将是否生成目标程序程序翻译成程序的程序。2、词法分析目标语言中间代码生成3、源程序目标代码生成4、源程序一、单项选择题1、文法 G：SxSx|y 所识别的语言是。c. xnyxn(n0)a. xyxb. (xyx)*d. x*yx*2、文法 G 描述的语言 L(G)是指a. L(G)=|S+ , VT*。b. L(G)=|S*, VT*c. L(G)=|S*,(VTVN*)d. L(G)=|S+ , (VTVN*)3、有限状态自动机能识别。a.b. 上下文有关文法d. 短语文法上下文无关文法c.正规文法4、设 G 为算符优先文法，G 的任意终结符对a、b 有

5、以下关系成立。a. 若 f(a)g(b)，则 abb.若 f(a)g(b)，则 ag)(b)或 f(a)0d. anbncmdm|n,m0c. anbmcmdn|n,m0e. dn|n05、自下而上的语法分析中，应从a. 句型词为单位的程序开始分析。句子b.c. 以单d. 文法的开始符e. 句柄6、对正规文法描述的语言，以下有能力描述它。c.上下文无关文法a.0 型文法性文法e.左线性文法b.1 型文法d.右线解答 1、e、a、c2、a、c、e3、b、c、d b、c、d、e三、填空题4、a、c5、b、c6、a、1、文法中的终结符和非终结符的交集是。词法分析器交给语法分析器的文法符号一定是，它一

6、定只出现在产生式的部。2、最左推导是指每次都对句型中的非终结符进行扩展。3、在语法分析中，最常见的两种方法一定是分析法，另一是分析法。4、采用5、语法分析时，必须消除文法的左递归。树代表推导过程，树代表归约过程。、归约、错误处理、6、自下而上分析法采用 7、Chomsky 把文法分为法，它们分别产生所产生的语言。等四种操作。种类型，编译器构造中采用和文和语言，并分别用和自动机识别解答1、空集2、最左3、自上而上自下而上4、自上而上终结符右5、语法6、移进7、4分析接受2型3 型上下文无关语言正规语言下推自动机有限四、判断题1、文法 SaS|bR| 描述的语言是(a|bc)* RcS2、在自下而

7、上的语法分析中，语法树与分析树一定相同。（）3、二义文法不是上下文无关文法。（）4、语法分析时必须先消除文法中的左递归。5、规范归约和规范推导是互逆的两个过程。6、一个文法所有句型的集合形成该文法所能接受的语言。（解答1、对五、简答题 1、句柄解答）2、错3、错4、错5、错6、错2、素短语3、语法树4、归约5、推导1、句柄：一个句型的最左直接短语称为该句型的句柄。2、素短语：至少含有一个终结符的素短语，并且除它自身之外不再含任何更小的素短语。3、语法树：满足下面 4 个条件的树称之为文法 GS的一棵语法树。每一终结均有一标记，此标记为 VNVT 中的一个符号；树的根结点以文法 GS的开始符 S

8、 标记；若一结点至少有一个直接后继，则此结点上的标记为 VN 中的一个符号；若一个以 A 为标记的结点有 K 个直接后继，且按从左至右的顺序，这些结点的标记分别为 X1,X2,XK，则 AX1,X2,XK，必然是 G 的一个产生式。 4、归约：我们称 直接归约出 A，仅当 A是一个产生式，且 、 (VNVT)*。归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。5、推导：我们称 A 直接推出 ，即 A，仅当 A 是一个产生式，且 、(VNVT)*。如果 12n，则我们称这个序列是从 1 至 2的一个推导。若存在一个从 1n 的推导，则称 1 可推导出 n。推

9、导是归约的逆过程。六、问答题1、给出上下文无关文法的定义。 解答一个上下文无关文法 G 是一个四元式（VT,VN,S, P），其中：VT 是一个非空有限集，它的每个元素称为终结符号；VN 是一个非空有限集，它的每个元素称为非终结符号，VTVN=；S 是一个非终结符号，称为开始符号；P 是一个产生式集合（有限），每个产生式的形式是 P，其中，PVN， (VTVN)*。开始符号 S 至少必须在某个产生式的左部出现一次。2、文法 GS：SaSPQ|abQ QPPQbPbb bQbc cQcc它是 Chomsky 哪一型文法？它生成的语言是什么？解答（1）由于产生式左部存在终结符号，且所有产生式左部符

10、号的长度均小于等于产生式右部的符号长度，所以文法 GS是 Chomsky1 型文法，即上下文有关文法。（2）按产生式出现的顺序规定优先级由高到低（否则无法推出句子），我们可以得到：SabQabc SaSPQaabQPQaabPQQaabbQQaabbcQaabbccSaSPQaaSPQPQaaabQPQPQaaabPQQPQaaabPQPQQaaaPPQQ QaaabbPqqqaaabbQQQaaabbbcQQaaabbbccQaaabbbccc于是得到文法 GS生成的语言 L= 3、按指定类型，给出语言的文法。 L=aibj|ji1的上下文无关文法。【解答】|n1（1）由 L=aibj|ji

11、1知，所求该语言对应的上下文无关文法首先应有 SaSb型产生式，以保证 b 的个数不少于 a 的个数；其次，还需有 SSb 或 SbS 型的产生式，用以保证 b 的个数多于 a 的个数；也即所求上下文无关文法 GS为： GS：SaSb|Sb|b4、有文法 G：SaAcB|Bd AAaB|cBbScA|b试求句型 aAaBcbbdcc 和 aAcbBdcc 的句柄；写出句子 acabcbbdcc 的最左推导过程。【解答】（1）分别画出对应两句型的语法树，如图 2-8-2 所示句柄:AaBBd图 2-8-2语法树（2）句子 acabcbbdcc 的最左推导如下： SaAcBaAaBcBacaBcB

12、acabcBacabcbScAacabcbBdcA acabcbbdcAacabcbbdcc5、对于文法 GS：S（L）|aS|aLL, S|S（1）画出句型（S,（a）的语法树。（2）写出上述句型的所有短语、直接短语、句柄和素短语。【解答】（1）句型（S,（a）的语法树如图 2-8-3 所示（2）由图 2-8-3 可知：短语：S、a、(a)、S,(a)、(S,(a)；直接短语：a、S；句柄：S；素短语：素短语可由图 2-8-3 中相邻终结符之间的优先关系求得，即；因此素短语为 a。 6、考虑文法 GT：TT*F|F FFP|P P（T）|i证明 T*P（T*F）是该文法的一个句型，并指出直接

13、短语和句柄。【解答】首先构造 T*P（T*F）的语法树如图 2-8-4 所示。由图 2-8-4 可知，T*P（T*F）是文法 GT的一个句型。直接短语有两个，即 P 和 T*F；句柄为 P。一、单项选择题1、词法分析所依据的是。a. 语义规则d. 等价变换规则b. 构词规则c. 语法规则2、词法分析器的输出结果是。a.c.b. 单词在符号表中的位置d. 单词自身值单词的种别编码单词的种别编码和自身值3、正规式 M1 和 M2 等价是指a. M1 和 M2 的状态数相等相等c. M1 和 M2 所识别的语言集相等。b. M1 和 M2 的有向弧条数d. M1 和 M2 状态数和有向弧条数相等4、

14、状态转换图（见图 3-6-1）接受的字集为。a.c.合以 0 开头的二进制数组成的集合含奇数个 0 的二进制数组成的集合b. 以 0 结尾的二进制数组成的集合d. 含偶数个 0 的二进制数组成的集5、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，。a. 词法分析器应作为独立的一遍子程序较好c. 词法分析器分解为多个过程，由语法分析器选择使用为一个独立的阶段b.词法分析器作为d.词法分析器并不作解答1、b2、c3、c4、d5、b二、多项选择题1、在词法分析中，能识别出。b. 四元式e. 常数a.d.基本字 逆波兰式c. 运算符2、令=a,b，则上所有以 b 开头，后跟若干个 a

15、b 的字的全体对应的正规式为。a. b(ab)*c.(ba)*bd. (ba)+b解答 1、a、c、e三、填空题b. b(ab)+e. b(a|b)2、a、b、d1、确定有限自动机 DFA 是2、若二个正规式所表示的的一个特例。相同，则认为二者是等价的。3、一个字集是正规的，当且仅当它可由所。解答1、NFA四、判断题2、正规集3、DFA（NFA）所识别1、一个有限状态自动机中，有且仅有一个唯一终态。2、设 r 和 s 分别是正规式，则有 L（r|s）=L(r)|L(s)。3、自动机 M 和 M的状态数不同，则二者必不等价。4、确定的自动机以及不确定的自动机都能正确地识别正规集。5、对任意一个右

16、线性文法 G，都存在一个 NFA M，满足 L(G)=L(M)。（）（）6、对任意一个右线性文法 G，都存在一个 DFA M，满足 L(G)=L(M)。（）7、对任何正规表达式 e，都存在一个 NFA M，满足 L(G)=L(e)。（）8、对任何正规表达式 e，都存在一个 DFA M，满足 L(G)=L(e)。（）解答1 、2、3、错4、5、6、7、8、正确五、基本题1、设 M（x,y, a,b, f,x,y）为一非确定的有限自动机，其中 f 定义如下：f（x,a）x,y f（y,a）f（x,b）y f（y,b）x,y试构造相应的确定有限自动机 M。解答：对照自动机的定义 M=(S,f,S0,

17、Z)，由 f 的定义可知 f(x,a)、f(y,b)均为多值函数，所以是一非确定有限自动机，先画出 NFA M 相应的状态图，如图 3-6-2所示。用子集法构造状态转换矩阵表 3-6-3 所示。Ixyx,yIax,yx,yIbyx,yx,y将转换矩阵中的所有子集重新命名而形成表 3-6-4 所示的状态转换矩阵。表 3-6-4状态转换矩阵a 2 2b 122012即得到 M=（0,1,2, a,b, f,0, 1,2），其状态转换图如图 3-6-5 所示。将图 3-6-5 的 DFA M最小化。首先，将 M的状态分成终态组1，2与非终态组0；其次，考察1,2。由于1,2a=1,2b=21,2，所

18、以不再将其划分了，也即整个划分只有两组0，1,2：令状态 1 代表1,2，即把原来到达 2 的弧都导向 1，并删除状态 2。最后，得到如图 3-6-6 所示化简 DFA M。2、对给定正规式 b*（d|ad）（b|ab）+，构造其 NFAM；解答：首先用 A+=AA*改造正规式得：b*(d|ad)(b|ab)(b|ab)*；其次，构造该正规式的 NFA M，如图 3-6-7 所示。【 历年试题附参考答案 】来源： 刘龙的日志历年试题及答案一 （每项选择 2 分，共 20 分）选择题1将编译程序分成若干个“遍”是为了b。 a.提高程序的执行效率b.使程序的结构更加清晰c.利用有限的机器内存并提高

19、机器的执行效率 d.利用有限的机器内存但降低了机器的执行效率 2构造编译程序应掌握d。a.源程序 b.目标语言c.编译方法 d.以上三项都是 3变量应当c。a.持有c.既持有b.持有右值又持有右值 d.既不持有也不持有右值4编译程序绝大多数时间花在d 上。a.出错处理 b.词法分析c.目标代码生成 d.管理表格 5词法分析器的输出结果是c。a.单词的种别编码 b.单词在符号表中的位置 c.单词的种别编码和自身值 d.单词自身值 6正规式MI 和M2 等价是指c。a. MI 和M2 的状态数相等 b.Ml 和M2 的有向弧条数相等。C.M1 和M2 所识别的语言集相等 d. Ml 和 M2 状态

20、数和有向弧条数相等7中间代码生成时所依据的是c。a语则 b词则 c语义规则 d等价变换规则8后缀式ab+cd+/可用表达式b 来表示。a a+b/c+d b (a+b)/(c+d) c a+b/(c+d) d a+b+c/d 9程序所需的数据空间在程序运行前就可确定，称为c 管理技术。a.动态b.栈式c.静态d.堆式空间遵守d 原则。10.堆式动态分配申请和a.先请先放 b.先请后放 c.后请先放 d.任意二（每小题 10 分，共 80 分）简答题1.画出编译程序的总体结构图，简述各部分的主要功能。2. 已知文法GE:EET+|T TTF* | | a试证：FF*是文法的句型，该句型的短语、简

21、单短语和句柄.3为正规式(a|b) *a(a|b)构造一个确定的有限自。设文法G(S)： S(L)|a S|aLL，S|S消除左递归和回溯；计算每个非终结符的和 FOLLOW；(3) 构造分析表。5 已知文法A-aAd| aAb|判断该文法是否SLR（1）文法，若是构造相应分析表，并对输入串ab#给出分析过程。6 构造算符文法GH的算符优先关系（含）。 GH：HH;M|MMd|aHb7已构造出文法G（S）（1）S BB（2）B aB（3）B b 1）。给出DFA 图2）.给出LR 分析表3）假定输入串为abaab，请给出LR 分析过程（即状态，符号，输入串的变化过程）。8 将下面的语句翻译成四

22、元式序列：while ACBA (1) A-aAd (2)A- aAb (3)A-(2)构造识别活前缀的DFAFOLLOW(A)=d,b,#对于状态I0：FOLLOW(A)a=对于状态I1：FOLLOW(A)a=因为，在DFA 中无的现象，所以该文法是SLR(1)文法。 (3)SLR(1)分析表状态 ACTION GOTOa B d # A 0 S2 r3 r3 r3 1 1 acc2 S2 r3 r3 r3 3 3 S5 S4r1 r1 r1r2 r2 r2(4)串ab#的分析过程步骤 状态栈 符号栈 当前字符 剩余字符串 动作1 0 # a b# 移进02 #a b # 归约A-023 #aA b # 移进0235 #aAb # 归约A- aAb5 01 #A # 接受6 【解答】由Md 和Ma得：VT(M)=d,a；由H-H;得：由HM 得：VT(H)=；VT(M) cVT(H)，即VT(H)=;,d,a由Md 和Mb 得：LASTVT(M)=d,b；由H-，；m 得：LA