编译原理总复习题.doc

《编译原理总复习题.doc》由会员分享，可在线阅读，更多相关《编译原理总复习题.doc（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章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、使用 可以定义一个程序的意义。 a语义规则b语法规则 c产生规则d词法规则7、词法分析器的

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

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

4、入是 ，最后阶段的输出为 程序。4、编译程序是指将 程序翻译成 程序的程序。解答 是否生成目标程序 2、词法分析 中间代码生成 3、源程序目标代码生成4、源程序 目标语言第二章一、单项选择题1、文法G：SxSx|y所识别的语言是 。a. xyxb. (xyx)*c. xnyxn(n0)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. 上下文有关文法c.正规文法d. 短语文法4、设G为算符优先文法，G的任意

5、终结符对a、b有以下关系成立 。a. 若f(a)g(b)，则abb.若f(a)g(b)，则ag)(b)或f(a)g(b)并不能判定原来的a与b之间是否存在优先关系：故选c。5、如果文法G无二义性，则最左推导是先生长右边的枝叶：对于d，如果有两个不同的是了左推导，则必然有二义性。故选a。6、选c。7、由图2-8-1的语法树和优先关系可以看出应选b。EE + FE + T PT iP #+#图2-8-1 句型P+T+I的语法及优先关系8、规范推导是最左推导，故选d。9、由TT,和T( 得FIRSTVT(T)=(,，)； 由TS得FIRSTVT(S)FIRSTVT(T)，而FIRSTVT(S)=b,

6、(；即 FIRSTVT(T)=b,(,，； 因此选c。 10、d 11、c 12、b 13、b 14、b二、多项选择题1、下面哪些说法是错误的 。a. 有向图是一个状态转换图b. 状态转换图是一个有向图c.有向图是一个DFAd.DFA可以用状态转换图表示2、对无二义性文法来说，一棵语法树往往代表了 。a. 多种推导过程b. 多种最左推导过程c.一种最左推导过程d.仅一种推导过程e.一种最左推导过程3、如果文法G存在一个句子，满足下列条件 之一时，则称该文法是二义文法。a. 该句子的最左推导与最右推导相同b. 该句子有两个不同的最左推导c. 该句子有两棵不同的最右推导d. 该句子有两棵不同的语法

7、树 e.该句子的语法树只有一个4、有一文法G：SAB AaAb| BcBd|它不产生下面 集合。a. anbmcndm|n,m0b. anbncmdm|n,m0c. anbmcmdn|n,m0d. anbncmdm|n,m0e. anbncndn|n05、自下而上的语法分析中，应从 开始分析。a. 句型b. 句子c. 以单词为单位的程序d. 文法的开始符e. 句柄6、对正规文法描述的语言，以下 有能力描述它。a.0型文法b.1型文法 c.上下文无关文法 d.右线性文法 e.左线性文法解答 1、e、a、c 2、a、c、e 3、b、c、d 4、a、c 5、b、c 6、a、b、c、d、e 三、填空题

8、1、文法中的终结符和非终结符的交集是 。词法分析器交给语法分析器的文法符号一定是 ，它一定只出现在产生式的 部。2、最左推导是指每次都对句型中的 非终结符进行扩展。3、在语法分析中，最常见的两种方法一定是 分析法，另一是 分析法。4、采用 语法分析时，必须消除文法的左递归。5、 树代表推导过程， 树代表归约过程。6、自下而上分析法采用 、归约、错误处理、 等四种操作。 7、Chomsky把文法分为 种类型，编译器构造中采用 和 文法，它们分别产生 和 语言，并分别用 和 自动机识别所产生的语言。解答 1、空集 终结符 右 2、最左 3、自上而上 自下而上 4、自上而上 5、语法 分析 6、移进

9、 接受 7、4 2 型 3型 上下文无关语言 正规语言 下推自动机 有限四、判断题1、文法 SaS|bR|描述的语言是(a|bc)* ( ) RcS2、在自下而上的语法分析中，语法树与分析树一定相同。 （ ）3、二义文法不是上下文无关文法。 （ ）4、语法分析时必须先消除文法中的左递归。（ ）5、规范归约和规范推导是互逆的两个过程。（ ）6、一个文法所有句型的集合形成该文法所能接受的语言。（ ）解答 1、对 2、错 3、错 4、错 5、错 6、错五、简答题1、句柄2、素短语3、语法树4、归约5、推导解答 1、句柄：一个句型的最左直接短语称为该句型的句柄。2、素短语：至少含有一个终结符的素短语，

10、并且除它自身之外不再含任何更小的素短语。3、语法树：满足下面4个条件的树称之为文法GS的一棵语法树。每一终结均有一标记，此标记为VNVT中的一个符号；树的根结点以文法GS的开始符S标记；若一结点至少有一个直接后继，则此结点上的标记为VN中的一个符号；若一个以A为标记的结点有K个直接后继，且按从左至右的顺序，这些结点的标记分别为X1,X2,XK，则AX1,X2,XK，必然是G的一个产生式。4、归约：我们称直接归约出A，仅当A 是一个产生式，且、(VNVT)*。归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。5、推导：我们称A直接推出，即A，仅当A 是一个产生

11、式，且、(VNVT)*。如果12n，则我们称这个序列是从1至2的一个推导。若存在一个从1n的推导，则称1可推导出n。推导是归约的逆过程。六、问答题1、给出上下文无关文法的定义。解答一个上下文无关文法G是一个四元式（VT,VN,S, P），其中：VT是一个非空有限集，它的每个元素称为终结符号；VN是一个非空有限集，它的每个元素称为非终结符号，VTVN=；S是一个非终结符号，称为开始符号；P是一个产生式集合（有限），每个产生式的形式是P，其中，PVN，(VTVN)*。开始符号S至少必须在某个产生式的左部出现一次。 2、文法GS： SaSPQ|abQ QPPQ bPbb bQbc cQcc（1）它是

12、Chomsky哪一型文法？（2）它生成的语言是什么？解答 （1）由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部的符号长度，所以文法GS是Chomsky1型文法，即上下文有关文法。（2）按产生式出现的顺序规定优先级由高到低（否则无法推出句子），我们可以得到： SabQabc SaSPQaabQPQaabPQQaabbQQaabbcQaabbcc SaSPQaaSPQPQaaabQPQPQaaabPQQPQaaabPQPQQaaaPPQQQaaabbPqqqaaabbQQQaaabbbcQQaaabbbccQaaabbbccc 于是得到文法GS生成的语言L=anbncn

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

14、S c AB d cb(a)S a A c BB S c AB d c(b)图2-8-2 语法树（2）句子acabcbbdcc的最左推导如下： SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcA acabcbbdcAacabcbbdcc 5、对于文法GS： S（L）|aS|a LL, S|S（1）画出句型（S,（a）的语法树。（2）写出上述句型的所有短语、直接短语、句柄和素短语。S（ L ）L ， SS ( L ) S a图2-8-3 句型（S,（a）的语法树【解答】（1）句型（S,（a）的语法树如图2-8-3所示（2）由图2-8-3可知：短语：S、a、(a)

15、、S,(a)、(S,(a)；直接短语：a、S；句柄：S；素短语：素短语可由图2-8-3中相邻终结符之间的优先关系求得，即；# （，（a ） ） #因此素短语为a。6、考虑文法GT：TT*F|FFFP|PP（T）|iTT * FF PP （ T ）T * F图2-8-4 句型T*P（T*F）的语法树证明T*P（T*F）是该文法的一个句型，并指出直接短语和句柄。【解答】首先构造T*P（T*F）的语法树如图2-8-4所示。由图2-8-4可知，T*P（T*F）是文法GT的一个句型。直接短语有两个，即P和T*F；句柄为P。第三章一、单项选择题1、词法分析所依据的是 。a. 语义规则b. 构词规则c. 语

16、法规则d. 等价变换规则2、词法分析器的输出结果是 。a. 单词的种别编码b. 单词在符号表中的位置c. 单词的种别编码和自身值d. 单词自身值3、正规式M1和M2等价是指 。a. M1和M2的状态数相等b. M1和M2的有向弧条数相等c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向弧条数相等4、状态转换图（见图3-6-1）接受的字集为 。 0 1 0图3-6-1YXa. 以 0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合c. 含奇数个0的二进制数组成的集合 d. 含偶数个0的二进制数组成的集合5、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，

17、 。a. 词法分析器应作为独立的一遍 b. 词法分析器作为子程序较好c. 词法分析器分解为多个过程，由语法分析器选择使用 d. 词法分析器并不作为一个独立的阶段解答 1、b 2、c 3、c 4、d 5、b二、多项选择题1、在词法分析中，能识别出 。a. 基本字b. 四元式c. 运算符d. 逆波兰式e. 常数2、令=a,b，则上所有以b开头，后跟若干个ab的字的全体对应的正规式为 。a. b(ab)*b. b(ab)+c.(ba)*bd. (ba)+be. b(a|b)解答 1、a、c、e 2、a、b、d三、填空题1、确定有限自动机DFA是 的一个特例。2、若二个正规式所表示的 相同，则认为二者

18、是等价的。3、一个字集是正规的，当且仅当它可由 所 。解答 1、NFA 2、正规集 3、DFA（NFA）所识别四、判断题1、一个有限状态自动机中，有且仅有一个唯一终态。（ ）2、设r和s分别是正规式，则有L（r|s）=L(r)|L(s)。（ ）3、自动机M和M的状态数不同，则二者必不等价。（ ）4、确定的自动机以及不确定的自动机都能正确地识别正规集。（ ）5、对任意一个右线性文法G，都存在一个NFA M，满足L(G)=L(M)。（ ）6、对任意一个右线性文法G，都存在一个DFA M，满足L(G)=L(M)。（ ）7、对任何正规表达式e，都存在一个NFA M，满足L(G)=L(e)。（ ）8、对

19、任何正规表达式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（x,b）yf（y,a） f（y,b）x,y 试构造相应的确定有限自动机M。解答：对照自动机的定义M=(S,f,S0,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，所以是一非确定有限自动机，先画出NFA M相应的状态图，如图3-6-2所示。 a a b b b图3-6-2 NFA MXY用子集法构造状态转换矩阵表3-6-3所示。IIaIbxx,yyyx

20、,yx,yx,yx,y将转换矩阵中的所有子集重新命名而形成表3-6-4所示的状态转换矩阵。表3-6-4 状态转换矩阵ab02112222 a a,b b b图3-6-5 DFA M021即得到M=（0,1,2, a,b, f,0, 1,2），其状态转换图如图3-6-5所示。 a a,b b图3-6-6 化简后的DFA M01将图3-6-5的DFA M最小化。首先，将M的状态分成终态组1，2与非终态组0；其次，考察1,2。由于1,2a=1,2b=21,2，所以不再将其划分了，也即整个划分只有两组0，1,2：令状态1代表1,2，即把原来到达2的弧都导向1，并删除状态2。最后，得到如图3-6-6所示

21、化简DFA M。2、对给定正规式b*（d|ad）（b|ab）+，构造其NFA M； aadb*b*(d|ad)(b|ab)(b|ab)*XYX123YX4135Y678(d|ad)(b|ab)(b|ab)*2dbadabb|abbX4135Y2bdbbabb图3-6-7 的NFA M解答：首先用A+=AA*改造正规式得：b*(d|ad)(b|ab)(b|ab)*；其次，构造该正规式的NFA M，如图3-6-7所示。第四章1、 构造下面文法的LL（1）分析表。D TLT int | realL id RR , id R | 解答： LL（1）分析表见表4-3-1分析 虽然这个文法很简单，我们还是

22、从求开始符号集合和后继符号集合开始。 FIRST（D）=FIRST（T）=int, real FOLLOW（D）=FOLLOW（L）=#FIRST（L）=id FOLLOW（T）=idFIRST（R）=，, FOLLOW（R）=#有了上面每个非终结符的FIRST集合，填分析表时要计算一个产生式右部的FIRST（）就不是件难事了。填表时唯一要小心的时，是产生式R右部的一个开始符号，而#在FOLLOW（R）中，所以R填在输入符号#的栏目中。表4-3-1 LL（1）分析表非终结符输入符号int realid，#DDTLDTLTTintTrealLLid RRR,id RR 2、 下面文法GS是否为L

23、L（1）文法？说明理由。S A B | P Q x A x y B b cP d P | Q a Q | 解答： 该文法不是LL（1）文法，见下面分析中的说明。分析 只有三个非终结符有两个选择。 1、P的两个右部d P 和 的开始符号肯定不相交。2、Q的两个右部a Q 和 的开始符号肯定不相交。3、对S来说，由于x FIRST(A B)，同时也有x FIRST(P Q x)（因为P和Q都可能为空）。所以该文法不是LL（1）文法。3、 设有以下文法： GS：SaAbDe|d ABSD|e BSAc| cD| DSe| （1）求出该文法的每一个非终结符U的FOLLOW集。（2）该文法是LL（1）文

24、法吗？（3）构造CS的LL（1）分析表。解答： （1）求文法的每一个非终结符U的FOLLOW集的过程如下：因为： S是识别符号，且有ABSD、BSAc、DSe，所以FOLLOW（S）应包含FIRST(D)FIRST(Ac) FIRST(e) #=a,da,d,c,ee#=a,c,d,e# 又因为ABSD和D，所以FOLLOW中还包含FOLLOW(A)。因为SaAbDe和BSAc,所以FOLLOW（A）=FIRST（bDe）FIRST（c）=b,c综合、得FOLLOW（S）=a,d,c,e,#a,b,c,d,e,#因为ABSD，所以 FOLLOW（B）=FIRST（SD）=a,d 因为SaAbD

25、e | d、ABSD| e和BSAc | cD，所以FOLLOW（D）=FIRST（e）FOLLOW（A）FOLLOW（B） =eb,ca,d=a,b,c,d,e（2）GS不是LL（1）文法。因为产生式BSAc|cD| 中 FIRST（SAc）FOLLOW（B）=a,d（3）构造GS的LL（1）分析表。按照LL（1）分析表的构造算法构造方法GS的LL（1）分析表如表4-3-2所示。表4-3-2 GS的LL（1）分析表abcde#SaAbDedABSDBSDBSDeBSac/cDSac/DSe/Se/4、 将文法GV改造成为LL(1)的。 GV：VN|NE EV|V+E Ni解答： 对文法GV提

26、取公共左因子后得到文法： GV：VNAA|EEVBB|+ENi求出文法GV中每一个非终结符号的FIRST集： FIRST(V)=iFIRST(A)=, FIRST(E)=iFIRST(B)=+, FIRST(N)=i求出文法GV中每一个非终结符号的FOLLOW集：FOLLOW(V)=#FIRST(B)FOLLOW(E)=#,+,FOLLOW(A)= FOLLOW(V)=+,#FOLLOW(E)= FIRST()FOLLOW(B)= FIRST()FOLLOW(E)=FOLLOW(B)= FOLLOW(E)= FOLLOW(N)= FIRST(A)FOLLOW(V)=,+,#可以看到，对文法GV

27、的产生式A|E，有FIRST(E)FOLLOW(A)=+,#= 对产生式B|+E，有FIRST(+E)FOLLOW(B)=+= 而文法的其他产生式都只有一个不为的右部，所以文法GV是LL(1)文法。5、已知文法：GA：AaAa|（1）该文法是LL（1）文法吗？为什么？（2）若采用LL（1）方法进行语法分析，如何得到该文法的LL（1）分析表？（3）若输入符号串“aaaa”，请给出语法分析过程。解答：（1）因为产生式AaAa| 有空产生式右部，而 FOLLOW(A)=#FIRST(a)=a, #造成 FIRST(A)FOLLOW(A)=A, a, #所以该文法不是LL（1）文法。（2）若采用LL（

28、1）方法进行语法分析，必须修改该文法。因该文法产生偶数（可以为0）个a，所以得到文法GA：AaaA|此时对产生式AaaA|， 有 FOLLOW(A)=#FOLLOW(A)=#，因而FIRST(A)FOLLOW(A)=a, #=所以文法GA是LL（1）文法，按LL（1）分析表构造算法构造该文法的LL（1）分析表如表4-3-3所示。表4-3-3 文法GA的LL(1)分析表A#AAaaAA（3）若采用LL(1)方法进行语法分析，对符号串“aaaa”的分析过程如表4-3-4所示。 表4-3-4对符号串“aaaa”的分析过程步骤分析栈输入串产生式/动作1#Aa a a a #AaaA2#A a aa a

29、 a a #匹配3#A aa a a #匹配4#Aa a #AaaA5#A a aa a #匹配6#A aa#匹配7#A#A8#接受第五章设有文法GS为：Sa|b|(A)ASdA|S（1） 完成下列算符优先关系表，见表5-7-1，并判断GS是否为算符优先文法。表5-7-1 算符优先关系表ab()d#ab()d# （2）给出句型（SdSdS）的短语、简单短语、句柄、素短语和最左素短语。（3）给出输入串（adb）#的分析过程。解答： （1）先求文法GS的FIRSTVT集和LASTVT集：由Sa|b|(A)得：FIRSTVT(S)=a,b,( );由ASd得：FIRSTVT(A)=d;又由AS得：F

30、IRSTVT(S) FIRSTVT(A)，即FIRSTVT(A)=d,a,b,(;由Sa|b|(A)得；LASTVT(S)=a,b,;由AdA得：LASTVT(A)=d,又由AS得：LASTVT(S) LASTVT(A)，即LASTVT(A)=d,a,b,)。构造优先关系表方法如下： 对Pab，或PaQb，有ab; 对PaR，而bFIRSTVT(R)，有ab; 对PRb，而aFIRSTVT(R)，有ab。由此得到： 由S(A)得：(); 由S(A得：(FIRSTVT(A)，即：(d,(a ,(b,(;由AdA得：dFIRSTVT(A)，即：dd,da,db,d(; 由SA)得，LASTVT(A

31、)，即：d),a),b),);由ASd得：LASTVT(S)d，即：ad,bd,)d;此外，由#S#得：#；由#FIRSTVT(S)得：#a,#b,#(；脂由LASTVT(S)#得：d#,a#,b#,)#。最后得到算符优先关系表，见表5-7-2。表5-7-2 算符优先关系表ab()d#ab()d#由表5-7-2可以看出，任何两个终结符之间至少只满足、三种优先关系之一，故GS为算符优先文法。SASASd（）ASd图5-7-3 句型（SdSdS）的语法树（2）为求出句型（SdSdS）的短语、简单短语、句柄，我们先画出该句型对应的语法树，如图5-7-3所示。由图5-7-3得到：短语：S，SdS，Sd

32、SdS，（SdSdS）简单短语（即直接短语）：S句柄（即最左直接短语）：S素短语：SdS，它同时也是该句型的最左素短语。（3）输入串（adb）#的分析过程见表5-7-4表5-7-4 输入串（adb）#的分析过程符号栈输入串说明#(adb)#移进#（adb)#移进#（adb)#用Sa归约#（Sdb)#移进#（Sdb)#移进#（Sdb)#用Sb归约#（SdS)#用AS归约#（SdA)#用ASdA归约#（A)#移进#（A）#用S（A）归约#S#分析成功第六章一、单项选择题1、若a为终结符，则Aa为 项目 a.归约b.移进c.接受d.待约2、若项目集Ik含有A，则在状态k时，仅当面临的输入符号aFOLLOW(A)时，才采取“A”动作的一定是 。 a.LALR文法b.LR（0）文法c.LR（1）文法d.SLR（1）文法3、就文法的描述能力来说，有 。