编译原理习题集与答案解析(整理后)

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

2、输入是。a.单词符号串b.源程序c.语法单位d.目标程序b.词法规则d.等价变换规则b.高级语言程序的解释执行 d.高级语言的翻译Ob.语法规则d.等价变换规则8、中间代码生成时所遵循的是a.语法规则c.语义规则9、编译程序是对a.汇编程序的翻译c.机器语言的执行10、语法分析应遵循.a.语义规则c.构词规则多项选择题1、编译程序各阶段的工作都涉及到 。a.语法分析b.表格管理c.出错处理d.语义分析e.词法分析2、编译程序工作时，通常有 阶段。a.词法分析b.语法分析c.中间代码生成d.语义检查e.目标代码生成三、填空题1、解释程序和编译程序的区别在于 。2、编译过程通常可分为 5个阶段，分

3、别是、语法分析 、代码优化和目标代码生成。3、编译程序工作过程中，第一段输入是 ,最后阶段的输出为 程序。4、编译程序是指将 程序翻译成 程序的程序。 单选解答1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选bo2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选do3、对编译而言，变量既持有左值又持有右值，故选 Co4、编译程序打交道最多的就是各种表格，因此选do5、目标代码包括汇编指令代码、可重定位指令代码和绝对指令代码3种，因此不是目标代码的只能选do6、词法分析遵循的是构词规则，语法分析遵循的是语法规则，中间代码生成遵循的是语义规则，并且语义规则可以定

4、义一个程序的意义。因此选a。7、b8、c9、d 10、c多选解答1. b、c2. a、b、c、e填空解答是否生成目标程序2、词法分析中间代码生成 3、源程序 目标代码生成4、源程序 目标语言第二章一、单项选择题1、文法G: SH> xSx|y所识别的语言是。a. xyxb. (xyx)* c. xnyxn(n R)d. x*yx*2、文法G描述的语言L(G)是指。b. L(G)=o|S?a ,a CVt*b. L(G)=o|S?*%a *t*c. L(G)=o|S?*a,”C(VtU Vn*)d. L(G)=a|S?去a (VtUVn*)3、有限状态自动机能识别 。a.上下文无关文法b.

5、上下文有关文法c.正规文法d.短语文法4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立 a.若 f(a)>g(b),则 a>b b.若 f(a)<g(b),则 a<bd. ab都不一定成立d. ab 一定应立5、如果文法 G是无二义的，则它的任何句子a 。a.最左推导和最右推导对应的语法树必定相同b.最左推导和最右推导对应的语法树可能不同c.最左推导和最右推导必定相同d.可能存在两个不同的最左推导，但它们对应的语法树相同6、由文法的开始符经0步或多步推导产生的文法符号序列是 。a.短语b.句柄c.句型 d.句子7、文法 G: E-E+T|TT一 T*P|PP

6、一 (E)|I则句型P+T+i的句柄和最左素短语为 。a.P+T 和 i b. P 和 P+T c. i 和 P+T+i d.P 和 T8、设文法为：S- SA|AAf a|b则对句子aba,下面 是规范推导。a.除 SA ： SAA ： AAA 二 aAA : abA ： abae. S= SA= SAA- AAA - AAa- Aba- abaf. fcSA : SAA=SAa : Sba=： Aba ： abag. S ： SA : Sa ： SAa : Sba : Aba ： aba9、文法 G: Sf b| A(T)T - T,S|S贝U FIRSTVT(T)。a. b,A ,(b.

7、 b, A,)10、产生正规语言的文法为 。a. 0型b.1型11、采用自上而下分析，必须 。a.消除左递归b.消除石逋归12、在规范归约中，用 来刻画可归约串。a.直接短语b.句柄13、有文法 G: E-E*T|TT-T+i|i句子1+2*8+6按该文法G归约，其值为 _a. 23 B. 42 c. 30 d14、规范归约指。a.最左推导的逆国】c.规范推导二、多项选择题1、下面哪些说法是错误的 。 a.有向图是一个状态转换图 c.有向图是一个DFAc.b, A ,(, d.b, A ,), c. 2型d.3型c.消除回溯d.提取公共左因子c.最左素短语d.素短语17b.最右推导的逆过程 d

8、.最左归约的逆过程b.状态转换图是一个有向图d.DFA可以用状态转换图表示2、对无二义性文法来说，一棵语法树往往代表了 。a.多种推导过程b.多种最左推导过程c.一种最左推导过程d.仅一种推导过程e.一种最左推导过程3、如果文法G存在一个句子，满足下列条件 之一时，则称该文法是二义文法。a.该句子的最左推导与最右推导相同b.该句子有两个不同的最左推导c.该句子有两棵不同的最右推导d.该句子有两棵不同的语法树 e该句子的语法树只有一个4、有一文法G: Sf ABAfaAb| £8- cBd| £ 它不产生下面 集合。b. anbncmdm|n,m>0d. anbncmd

9、m|n,m > 0开始分析。c.以单词为单位的程序有能力描述它。c.上下文无关文法d.右线性文法e左线性文法a. anbmcndm|n,m >0c. anbmcmdn|n,m > 0e. anbncndn|n > 05、自下而上的语法分析中，应从a.句型b.句子d.文法的开始符e.句柄6、对正规文法描述的语言，以下a.0型文法b.1型文法三、填空题1、文法中的终结符和非终结符的交集是 。词法分析器交给语法分析器的文法符号一定 是,它一定只出现在产生式的 部。2、最左推导是指每次都对句型中的 非终结符进行扩展。3、在语法分析中，最常见的两种方法一定是 分析法，另一是 分析

10、法。4、采用 语法分析时，必须消除文法的左递归。5、树代表推导过程， 树代表归约过程。6、自下而上分析法采用、归约、错误处理、等四种操作。7、Chomsky把文法分为种类型，编译器构造甲采丁和 文法，它们分别产生 和 语言，并分师一和自动机识别所产生的语言二四1、文法 与一 aS|bR| e描述的语言悬a|bc)*()Rf cS2、在自下而上的语法分析中，语法树与分析树一定相同。()3、二义文法不是上下文无关文法。()4、语法分析时必须先消除文法中的左递归。()5、规范归约和规范推导是互逆的两个过程。()6、一个文法所有句型的集合形成该文法所能接受的语言。()五、简答题1、句柄2、素短语3、语

11、法树4、归约 5、推导六、问答题 1、给出上下文无关文法的定义。2、文法 GS:* aSPQ|abQQ PQ bP一 bb bQ 一 bc cQf cc (1)它是Chomsky哪一型文法？ (2)它生成的语言是什么？ 3、按指定类型，给出语言的文法。L=a ibj|j >降1的上下文无关文法。4、有文法 G: Sf aAcB|BdAfAaB|c BfbScA|b (1)试求句型 aAaBcbbdcc和aAcbBdcc的句柄； (2)写出句子acabcbbdcc的最左推导过程。5、对于文法GS:Sf ( L) |aS|aL-L, S|S(1)画出句型(S, (a)的语法树。(2)写出上述

12、句型的所有短语、直接短语、句柄和素短语。6、考虑文法GT：T-T*F|F FfF T P|PP-(T) |i证明T*PT(t*f)是该文法的一个句型，并指出直接短语和句柄。 单选解答选选选、 、 、12 3Co aio Co4、虽然a与b没有优先关系，但构造优先函数后，a与b就一定存在优先关系了。 所以，由f(a)>g)(b) 或f(a)<g(b)并不能判定原来的 a与b之间是否存在优先关系：故选 c。5、如果文法G无二义性，则最左推导是先生长右边的枝叶：对于 d,如果有两个不同的是了左 推导，则必然有二义性。故选a。6、选c7、由图2-8-1的语法树和优先关系可以看出应选bo/

13、E + F/ / E + T PiP#< + >+< i >#图2-8-1句型P+T+I的语法及优先关系8、规范推导是最左推导，故选 do9、由 T-T,和 T一(得 FIRSTVT(T)尸代,);由 T-S得 FIRSTVT(S)? FIRSTVT(T),而 FIRSTVT(S尸b,八，(;即 FIRSTVT(T尸b,八，(,;因此选 c。10、d 11、c 12、b 13、b14、b多选解答1、e、a、c2、a、c、e 3、b、c、d4、a、c5、b、c6、a、b、c、d、e填空解答1、空集终结符右2、最左3、自上而上自下而上4、自上而上5、语法 分析6、移进 接受

14、7、42型 3型上下文无关语言正规语言下推自动机 有限判断解答1、对2、错3、错 4、错5、错6、错简答解答1、句柄：一个句型的最左直接短语称为该句型的句柄。2、素短语：至少含有一个终结符的素短语，并且除它自身之外不再含任何更小的素短语。3、语法树：满足下面 4个条件的树称之为文法 GS的一棵语法树。每一终结均有一标记，此标记为Vn U Vt中的一个符号；树的根结点以文法 GS的开始符S标记；若一结点至少有一个直接后继，则此结点上的标记为Vn中的一个符号；若一个以A为标记的结点有 K个直接后继，且按从左至右的顺序， 这些结点的标记分别为Xi,X2，,Xk,则A-X i,X2，,Xk,必然是 G

15、的一个产生式。4、归约：我们称a 丫 3直接归约出A 3,仅当A 一丫是一个产生式，且a、3 C (VnUVt)*。归约过 程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。5、推导：我们称“A 3直接推出a 丫禺P “A战a 丫双当A一 丫是一个产生式，且a、3 C(Vn U V/。 如果oci= g=non,则我们称这个序列是从a 1至0C2的一个推导。若存在一个从a 1 on的推导，则 称“1可推导出an。推导是归约的逆过程。问答1解答一个上下文无关文法 G是一个四元式(Vt,Vn,S, P),其中： Vt是一个非空有限集，它的每个元素称为终结符号； Vn是

16、一个非空有限集，它的每个元素称为非终结符号，Vt A Vn=； S是一个非终结符号，称为开始符号； P是一个产生式集合(有限)，每个产生式的形式是 P-a,其中，PCVn, “VtUVn)*。开始符号S至少必须在某个产生式的左部出现一次。2解答(1)由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部的符号长度，所以文法 GS是Chomsky1型文法，即上下文有关文法。(2)按产生式出现的顺序规定优先级由高到低(否则无法推出句子)，我们可以得到：S : abQ ： abcS : aSPQ : aabQPQ : aabPQQ : aabbQQ二 aabbcQ : aabbc

17、cS ： aSPg aaSPQP牛 aaabQPQPQ : aaabPQQPQ ： aaabPQPQQ ： aaaPPQQQ- aaabbPqqq : aaabbQQQ, : aaabbbcQQ : aaabbbccQ : aaabbbccc于是得到文法GS生成的语言L=anbncn|n >13【解答】(1)由L=a ibj|j >降1知，所求该语言对应的上下文无关文法首先应有S- aSb型产生式，以保证b的个数不少于a的个数；其次，还需有S-Sb或S bS型的产生式，用以保证b的个数多于a 的个数；也即所求上下文无关文法GS为：GS: S aSb|Sb|b4【解答】(1)分别画出

18、对应两句型的语法树，如图 2-8-2所示句柄：AaB BdS(b)图2-8-2 语法树(2)句子acabcbbdcc的最左推导如下：S : aAcB，： aAaBcB : acaBcB : acabcB : acabcbScA: acabcbBdcA= acabcbbdcA : acabcbbdcc5【解答】(1)句型(S, (a)的语法树如图2-8-3所示S(2)由图2-8-3可知：短语：S a、(a)、S,(a) (S,(a)直接短语：a、S;句柄：S;a图2-8-3 句型(S, (a)的语法树素短语:、单项选择题1、词法分析所依据的是。a.语义规则 b.构词规则2、词法分析器的输出结果是

19、 <a.单词的种别编码c.单词的种别编码和自身值素短语可由图2-8-3中相邻终结符之间的优先关系求得，即;# < (<, V (V a > ) > ) > #因此素短语为a。6【解答】首先构造T*P T (T*F)的语法树如图 2-8-4所示。由图2-8-4可知，T*P T (T*F)是文法GT的一个句型。直接短语有两个，即 P和T*F；句柄为P。图2-8-4 句型T*P T (T*F )的语法树第三章c.语法规则d.等价变换规则b.单词在符号表中的位置d.单词自身值3、正规式 M1和”2等价是指。a. Mi和M2的状态数相等b. Mi和M2的有向弧条数相等

20、c. Mi和M2所识别的语言集相等d. Mi和M2状态数和有向弧条数相等4、状态转换图(见图 3-6-1)接受的字集为 。a.以0开头的二进制数组成的集合b.以0结尾的二进制数组成的集合c.含奇数个0的二进制数组成的集合d.含偶数个0的二进制数组成的集合5、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，。a.词法分析器应作为独立的一遍b.词法分析器作为子程序较5千c.词法分析器分解为多个过程，由语法分析器选择使用d.词法分析器并不作为一个独立的阶段二、多项选择题1、在词法分析中，能识别出。a.基本字b.四元式c.运算符d.逆波兰式e.常数2、令汇=a,b,则汇上所有以b开头，

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

22、。()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、设M= ( x,y, a,b, f,x,y)为一非确定的有限自动机，其中f定义如下：f (x,a) = x,y f (x,b) = y f (y,a) = 4f (y,b) = x,y试构造相应的确定有限自动机M'。2、对给定正规式 b* (d|ad) (b|ab) +,构造其 NFA M;单选解答1、b2、c3、c 4、d5、b多选解答 1、

23、a、c、e2、a、b、d填空解答1、NFA2、正规集3、DFA (NFA)所识别判断解答 1、2、3、错 4、5、6、7、8、正确基本1解答：对照自动机的定义 M=(S, 2 f,S),由f的定义可知f(x,a)、f(y,b)均为多值函数，所以是 一非确定有限自动机，先画出 NFA M相应的状态图，如图 3-6-2所示。将转换矩阵中的所有子集重新命名而形成表3-6-4所示的状态转换矩阵。表3-6-4状态转换矩阵ab0211一2222ab将图3-6-5的DFA M '最小化。首先，将 M '的状态分成终态组1 , 2与非终态组 考察1,2。由于1,2a=1,2b=2 ? 1,2,

24、所以不再将其划分了，也即整个划分只有两组0；其次，0 , 1,2：令状态1代表1,2,即把原来到达 2的弧都导向1,并删除状态2。最后，得到如图3-6-6所示化简DFA M 。a0a,bb化简后的DFA M'图 3-6-62解答：首先用3-6-7所示。A+=AA *改造正规式得:b*(d|ad)(b|ab)(b|ab) *;其次，构造该正规式的NFA M ,如图b (d|ad)(b|ab)(b|ab)3235Y口adab4X.*b4db23a图 3-6-7 的 NFA MA二rOb8即得到M' = (0,1,2,a,b, f,0, 1,2)，其状态转换图如图3-6-5所示。第四

25、章1、构造下面文法的LL (1)分析表。Df TLT 一 int | realL 一 id RRf , id R |£2、 下面文法GS是否为LL (1)文法？说明理由。S 一 A B | P Q xA 一 x y B 一 b cP 一 d P | eQ 一 a Q | e3、 设有以下文法：GS: S- aAbDe|dA - BSD|eB一 SAc| cD| £D 一 Se| e(1)求出该文法的每一个非终结符U的FOLLOW 集。(2)该文法是LL (1)文法吗？(3)构造CS的LL (1)分析表。4、 将文法GV改造成为LL的。GV : V-N|NEE-V|V+EN

26、f i5、已知文法：GA :AfaAa| £(1)该文法是LL (1)文法吗?为什么？(2)若采用LL (1)方法进行语法分析，如何得到该文法的LL (1)分析表?(3)若输入符号串“ aaaa，请给出语法分析过程。1解答：LL (1)分析表见表4-3-1FIRST (D) =FIRST (T)FIRST (L) =idFIRST (R) = , , s有了上面每个非终结符的 是件难事了。填表时唯一要小心的时，£分析 虽然这个文法很简单，我们还是从求开始符号集合和后继符号集合开始。=int, realFOLLOW (D) =FOLLOW (L) =#FOLLOW (T) =

27、idFOLLOW (R) =#FIRST集合，填分析表时要计算一个产生式右部a的FIRST ( a )就不是产生式R-e右部的一个开始符号，而 #在FOLLOW (R)中，所以R一 £填在输入符号#的栏目中。表4-3-1 LL (1)分析表非终结符输入符号intrealid#DD f TLD f TLTT-intT 一 realLLfid RRRf,id RR 一 £2解答：该文法不是LL (1)文法，见下面分析中的说明。分析只有三个非终结符有两个选择。1、P的两个右部d P和e的开始符号肯定不相交。2、Q的两个右部a Q和e的开始符号肯定不相交。3、对S来说，由于 x C

28、 FIRST(A B),同时也汨C FIRST(P Q x) (国 Q都可能为空) 所以该文法不是 LL (1)文法。3解答： (1)求文法的每一个非终结符U的FOLLOW 集的过程如下：因为： S是识别符号，且有 AfBSD、BfSAc、D - Se,所以FOLLOW ( S)应包含FIRST(D) U FIRST(Ac) U FIRST(e) U #=a,d U a,d,c,e U e U #=a,c,d,e# 又因为A - BSD和D-e,所以FOLLOW 中还包含 FOLLOW(A)。 因为Sf aAbDe和B-SAc所以 FOLLOW (A) =FIRST (bDe) U FIRST

29、 (c) =b,c综合、得 FOLLOW (S) =a,d,c,e,# U a,b,c,d,e,#因为 A-BSD,所以 FOLLOW (B) =FIRST (SD) =a,d因为 S-aAbDe | d、A-BSD| e 和 B-SAc | cD ,所以FOLLOW (D) =FIRST (e) U FOLLOW (A) U FOLLOW (B)=e U b,c U a,d=a,b,c,d,e(2) GS不是 LL (1)文法。因为产生式BfSAc|cD| e中FIRST (SAc) n FOLLOW (B) =a,d w?(3)构造GS的LL (1)分析表。按照LL (1)分析表的构造算法

30、构造方法GS的LL (1)分析表如表4-3-2所示。表4-3-2 GS的LL (1)分析表abcde#SaAbDedABSDBSDBSDeBSac/ ecDSac/ eDSe/£££Se/££4解答：对文法GV提取公共左因子后得到文法:G' V : V-NA A 一 或EEfVBBf H+ENT求出文法G' V中每一个非终结符号的FIRST集：FIRST(V)=iFIRST(A)=,FIRST(E)=iFIRST(B尸+,FIRST(N)=i求出文法G' V中每一个非终结符号的FOLLOW 集：FOLLOW(V)=# U

31、 FIRST(B) U FOLLOW(E尸#,+,FOLLOW(A)= FOLLOW(V尸+,#FOLLOW(E)= FIRST() U FOLLOW(B)= FIRST() U FOLLOW(E)=FOLLOW(B)= FOLLOW(E)= FOLLOW(N)= FIRST(A) U FOLLOW(V)=,+,#可以看到，对文法 G' V的产生式A一或E,有FIRST(E) A FOLLOW(A)= n +,#= ?对产生式B-d+E ,有FIRST(+E) A FOLLOW(B尸+ n = ?而文法的其他产生式都只有一个不为e的右部，所以文法 G' V是LL(1)文法。5解

32、答：(1)因为产生式 A-aAa| e有空产生式右部，而 FOLLOW(A)=# U FIRST(a)=a, #造成 FIRST(A) n FOLLOW(A尸A, n a, # w?所以该文法不是 LL (1)文法。(2)若采用LL (1)方法进行语法分析，必须修改该文法。因该文法产生偶数(可以为0)个a,所以得到文法G' A: A - aaA| £此时对产生式 A-aaA| £ ,有 FOLLOW(A)=# U FOLLOW(A)=#,因而 FIRST(A) n FOLLOW(A尸a, n #=?所以文法G' A是LL (1)文法，按LL (1)分析表构造

33、算法构造该文法的LL (1)分析表如表4-3-3所示。表4-3-3文法G' A的LL(1)分析表A#AA 一 aaAA-> £(3)若采用LL(1)方法进行语法分析，对符号串“aaaa的分析过程如表 4-3-4所示。表4-3-4对符号串“ aaa-的分析过程步骤分析栈输入串产生式/动作1#Aa a a a #A 一 aaA2#A a aa a a a #匹配3#A aa a a #匹配4#Aa a #A 一 aaA5#A a aa a #匹配6#A aa#匹配7#A#A-> £8#接受第五章1 .设有文法GS为：Sf a|b|(A)ab()d#a?b?(

34、?)?5-7-1,并判断GS是否为算符优先文法。 算符优先关系表A 一 SdA|S(1) 完成下列算符优先关系表，见表表 5-7-1d#?(2)给出句型(SdSdS的短语、简单短语、句柄、素短语和最左素短语。(3)给出输入串(adb) #的分析过程。解答：(1)先求文法 GS的FIRSTVT集和LASTVT集：由 S-a|b|(A)得：FIRSTVT(S尸a,b,();由 A - Sd得：FIRSTVT(A)=d;又由 A - S得：FIRSTVT(S) ? FIRSTVT(A),即 FIRSTVT(A尸d,a,b,(;由 S-a|b|(A)得；LASTVT(S尸a,b,;由 A 一 dA 得

35、：LASTVT(A尸d, 又由 A - S 得：LASTVT(S) ? LASTVT(A),即 LASTVT(A)=d,a,b,)。构造优先关系表方法如下：对P一ab，或PfaQb，有a? b;对 P-aR，而 bC FIRSTVT(R)，有 a? b; 对 P-Rb，而 aC FIRSTVT(R)，有 a? b。由此得到：由 S一 (A)得：(?); 由 S一 (A得：(？ FIRSTVT(A),即：(? d,(? a ,(? b,(?(油 A一dA 得：d? FIRSTVT(A), 即：d? d,d? a,d? b,d?(; 由 S一A)得，LASTVT(A) ?),即：d? ),a? )

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

37、5-7-3句型（SdSdS）的语法树短语：S, SdS, SdSdS （SdSdS简单短语（即直接短语）：S句柄（即最左直接短语）：S素短语：SdS，它同时也是该句型的最左素短语。（3）输入串（adb） #的分析过程见表 5-7-4表5-7-4 输入串(adb) #的分析过程符号栈输入串说明#(adb)#移进# (adb)#移进# (adb)#用S-a归约# (Sdb)#移进# (Sdb)#移进# (Sdb)#用S-b归约# (SdS)#用A - S归约# (SdA)#用A - SdA归约# (A)#移进# (A)#用S- ( A)归约#S#分析成功第六章、单项选择题1、若a为终结符，则A-“

38、 就 项目a.归约b.移进c.接受d.待约2、若项目集Ik含有A-a ；则在状态k时，仅当面临的车入符号 aC FOLLOW(A)时，才采取“A 动作的一定是。a.LALR 文法 b.LR (0)文法 c.LR (1)文法 d.SLR (1)文法3、就文法的描述能力来说，有 。a. SLR (1) ? LR (0) b. LR ( 1) ? LR (0) c. SLR (1) ? LR (1) d.无二义文法？ LR (1)4、在LR (0)的ACTION子表中，如果某一行中存在标记"j'的栏，则 。a.该行必定填满rjb.该行未填满口c.其他行也有rjd.goto子表中也有

39、rj5、一个 指明了在分析过程中的某时刻所能看到产生式多大一部分。a.活前缀b.前缀c.项目d.项目集二、多项选择题1、一个LR分析器包括。a.一个总控程序b.一个项目集c. 一个活前缀d.一张分析表e.一个分析栈2、LR分析器核心部分是一张分析表，该表包括 等子表。a.LL(1)分析b.优先关系c.GOTOd.LRe.ACTION3、每一项ACTIONS , a所规定的动作包括。a移进b.比较c接受d.归约4、对LR分析表的构造，有可能存在 动作冲突。a移进b.归约5、就文法的描述能力来说，有a. SLR (1) ? LR (1)d. LR (1) ?无二义文法6、对LR分析器来说，存在a.

40、LALR b.LR (0)7、自上而下的语法分析方法有 a.算符优先分析法d.LR (0)分析法三、填空题c.移进/归约d.移进/移进Ob. LR (1) ? SLR (1)e. SLR (1) ?无二义文法 等分析表的构造方法。c.SLR (1) d.SLR (0)b.LL (1)分析法e.LALR (1)分析法e报错e.归约/归约c. LR (0) ? LR (1)e.LR ( 1)c.SLR (1)分析法1、对于一个文法，如果能够构造 。使得它的 均是唯一确定的，则称该文法为LR文法。2、字的前缀是指该字的 Q3、活前缀是指 的一下前缀，这种前缀不含 之后的任何符号。4、在LR分析过程币

41、，只要 _的已扫描部分保而明约成一个 _ ,则扫描过的部分正确。5、将识别 的NFA确定旧7i其成为以 为状态的DFA,起不DFA就是建立 的基础。6、A一 a 称为 项目；对文法开始符 S' 一 a 为 项目；若a为终结符，则称 A-a a 3为项目；若B为菲终结符，则称 A-a 彝项目一7、LR (0)分析法的名字中“ L”表示；“R”表示，“0”表示。四、综合题1、对于文法 GS: SfAS|bA一 SA|a(1)列出所有LR (0)项目(2)列出构成文法 LR (0)项目集规范族。 单项解答：1、A一 a 称为归约项目，对文法开始符 S'的归约项目，如 S' a

42、 称为接受项目，A- a 3 (a为终结符)称为移进项目。在此选 b.2、当用产生式 A-a归约时，LR (0)无论面临什么输入符号都进行归约； SLR (1)则仅当面 临的输入符号aC FOLLOW(A)时进行归约；LR (1)则当在把“归约为A的规范句型的前缀 3Aa前 提下，当“后跟终结符a时，才进行归约；因此选 do3、由于 LR (0) ? SLR (1) ? LR (1) ?无二义文法，故选 c。4、选 a。5、选 c。 多选解答：1、一个LR分析器包括一个总控程序和一张分析表，选a、do2、选 c、e。3、选 a、c、d、e。4、在LR分析表的构造中有可能存在“移进” / “归约

43、”和“归约” / “归约”冲突；故选 c、e。5、选 a、b、c、d、e。6、选 a、b、c、e。7、选 a、c、d、e。 填空解答：1、一张分析表每个入口2、任意首部3、规范句型 句柄4、输入串 活前缀5、活前缀 项目集合 LR分析算法6、归约接受移进待约7、自左至右分析采用最右推导的逆过程即最左归约向右查看0个字符 综合解答:首先将文法 G拓广为GS':S' 一 SSf AS|bA 一 SA|a(1)文法GS'的LR (0)项目是:1、S' f S2、S 一 S 5、S- AS -6、SH> ' b9、A - S A10、A-SA-3、S一 A

44、S7、S- b ,11、A 一 a4、Sf A , S8、Af SA12、A一 a ,2、用 10：列出构成文法 LR (0)项目集规范族。项目集规范族如下：16 ： 12、A 一 a ,I7： 7、Sb -CLOSURE (闭包)办法构造文法 G'的LR (0)1、S' 一 - SI3： 9、A - S- A3、SH - AS8、A 一 SA3、Sf AS6、S 一 b8、A 一 SA11、A 一 a11、A 一 aI1： 2、S' -S9、AfS AI4： 10、A -SA 4、S A , S8、Af SA11、A 一 a3、SH - AS6、SH b12： 4、S

45、f A S3、SH - AS3、S一 AS6、S 一 b8、A 一 SA11、A 一 aI5： 5、S-AS -9、A - S- A6、SH - b8、A 一 SA11、A 一 a8、Af SA11、A 一 a3、Sf AS6、S 一 b注意：I1中的S' -S 和Af SA是由斗犬态I。中的1和3读入一个S字符后得到的下一个项目；， 而I4中的A - SA和A - A-S则是由I3中的9和3读入一个A字符后得到的下一个项目；I5中的S 一 AS和A - S-A则是由I4中的4和8读入一个S字符后得到的下一个项目。状态全体构成了文法 G'白L LR (0)规范族。第七章、单项选

46、择题1、中间代码生成所依据的是。a.语法规则b.词法画Tc.语义规则d.等价变换规则2、四元式之间的联系是通过 实现的。a.指示器b.临时变亶c.符号表d.程序变量3、后缀式ab+cd+/可用表达式来表示。a.a+b/c+d4、表达式3 A V B) a. r AB V A CD Vb.(a+b)/(c+d)c.a+b/(c+d) d.a+b+c/dA (C V D)的逆波兰表示为。c. AB Vn CD V Ad. Ar BV A CD Vb. Ar B VCDV A+5、中间代码的树型表示A B C D所对应的表达式为a.A+B+C+D b.A+(B+C)+D6、四元式表示法的优点为 。a

47、不便于优化处理，但便于表的更动c.便于优化处理，也便于表的更动7、终结符具有 属性。a.传递b.继承、多顶选择题1、中间代码主要有 。a.四元式b.二元式c.(A+B)+C+Dd.(A+B)+(C+D)b.不便于优化处理，但节省存储空间 d.便于表的更动，也节省存储空间c抽象d.综合c.三兀式d.后缀式e.间接三元式2、下面中间代码形式中，能正确表示算术表达式a+b+c的有a. ab+c+b. abc+ ca be. a+b+cb c3、在下面的 语法制导翻译中，采用拉链 -回填技术。a.赋值语句b. goto语句 c.条件语句d.循环语句4、下列 中间代码形式有益于优化处理。a.三元式b.四

48、元式c.间接三元式d.逆波兰表示法e.树形表示法5、在编译程序中安排中间代码生成的目的是 。a.便于进行存储空间的组织b.利于目标代码的优化c.利于编译程序的移植d.利于目标代码的移植e.利于提高目标代码的质量6、下面的中间代码形式中， 能正确表示算术表达式a+b*c。题)7、三地址代码语句具体实现通常有表示方法。a逆波兰表示b.三元式"CTll接三元式d.树形表示e.四元式三、填空题1、中间代码有等形式，生成中间代码主要是为了使。2、语法制导翻译既可以用来产生一 代码,也可以用来产生指令，甚至可用来对输入串进行。3、当源程序中的标号出现“先引用后定义”时，中间代码的转移地址须持 时

49、才能确定,因而要进行。4、文法符号的属性有两种,一种称为 ,另一种称为 。5、后缀式abc-/所代表的表达式是，表达式(a-b)*c可用后缀式表不。6、用一张辅以的办法来表示中间代码,这种表示法称为间接三元式。四、综合题1、给出下列表达式的逆波兰表示(后缀式) ： a*(-b+c)(AVB)A(CVr DAE)2、写出算术表达式：A+B*(C-D)+E/(C-D) TN的四元式序列；三元式序列；间接三元式序列单选解答1、选c2、四元式之间的联系是通过临时变量实现的，故选 bo3、选b4、选 bo5、选d6、四元式表示法的优点与间接三元式相同，故选 Co7、选 do多选解答1、选 a、c、d、e

50、。2、b、d的中间代码不能正确表示a+b+c ,而e不是中间代码：故选 a、c。3-凡涉及到跳转的语句都需要采用拉链一一回填技术，故选b、c、do4、选 b、Co5、选 b、do6、选 b、e。7、选 b、c、e。填空解答1、逆波兰记号、树形表示、三元式、四元式目标代码的优化容易实现2、中间目标解释执行3、标号定义回填4、继承属性综合属性5、a/(b-c)ab-c*6、间接码表三兀式表综合解答1、 abc+*;2、表达式的四元式序列: AB VCDr EA V A(1)(-,C,D,T 1)(1)(-,C,D)(1)(-,C,D)(2)(*,B,T i,T2)(2)(*,B,(1)(2)(*,

51、B,(1)(3)(+,A,T 2,T3)(3)(+,A,(2)(3)(+,A,(2)表达式的二兀式序列间接三元式序列第八章一、单项选择题1、编译程序使用 区别标识符的作用域。a.说明标识符的过程或函数名b.说明标识符的过程或函数的静态层次c.说明标识符的过程或函数的动态层次d.标识符的行号2、在目标代码生成阶段，符号表用于 。a.目标代码生成b.语义检查c.语法检查d.地址分配3、过程信息表不包含。a.过程入口地址 b.过程的静态层次 c.过程名 d.过程参数信息4、下列关于标识符和名字叙述中，正确的是 。a.标识符有一定的含义b.名字是一个没有意义的字符序列c.名字有确切的属性d. ac都不正确二、多项选择题1、符号表的每一项均包含 。a.名字栏 b.类型栏c.信息栏d.值栏 e. ad均包含2、对编译程序所用到的符号表，涉及的操作有 。a.填写或更新信息栏内容b.填入新