编译原理习题及答案(整理后)

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、编译程序各阶段的工作都涉及到 。 a语法分析b表格管理c出错处理 d语义分析e词法分析2、编译程序工作时，通常有 阶段。 a词法分析b语法分析c中间代码生成 d语义检查e目标代码生成三、填空题 1、解释程序和编译程序的区分在于 。2、编译过程通常可分为5个阶段，分别是

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

4、序的意义。因此选a。 7、b 8、c 9、d 10、c多选解答1b、c 2. a、b、c、e填空解答 是否生成目标程序 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为算

5、符优先文法，G的任意终结符对a、b有以下关系成立 。a. 若f(a)g(b)，则abb.若f(a)g(b)，则a0c. anbmcmdn|n,m0d. anbncmdm|n,m0e. anbncndn|n05、自下而上的语法分析中，应从 开头分析。a. 句型b. 句子c. 以单词为单位的程序d. 文法的开头符e. 句柄6、对正规文法描述的语言，以下 有力量描述它。a.0型文法b.1型文法 c.上下文无关文法 d.右线性文法 e.左线性文法 三、填空题1、文法中的终结符和非终结符的交集是 。词法分析器交给语法分析器的文法符号肯定是 ，它肯定只消灭在产生式的 部。2、最左推导是指每次都对句型中的

6、非终结符进行扩展。3、在语法分析中，最常见的两种方法肯定是 分析法，另一是 分析法。4、接受 语法分析时，必需消退文法的左递归。5、 树代表推导过程， 树代表归约过程。6、自下而上分析法接受 、归约、错误处理、 等四种操作。 7、Chomsky把文法分为 种类型，编译器构造中接受 和 文法，它们分别产生 和 语言，并分别用 和 自动机识别所产生的语言。四、推断题1、文法 SaS|bR|描述的语言是(a|bc)* ( ) RcS2、在自下而上的语法分析中，语法树与分析树肯定相同。 （ ）3、二义文法不是上下文无关文法。 （ ）4、语法分析时必需先消退文法中的左递归。（ ）5、规范归约和规范推导是

7、互逆的两个过程。（ ）6、一个文法全部句型的集合形成该文法所能接受的语言。（ ）五、简答题1、句柄2、素短语3、语法树4、归约5、推导六、问答题1、给出上下文无关文法的定义。2、文法GS： SaSPQ|abQ QPPQ bPbb bQbc cQcc（1）它是Chomsky哪一型文法？（2）它生成的语言是什么？3、按指定类型，给出语言的文法。L=aibj|ji1的上下文无关文法。4、有文法G：SaAcB|BdAAaB|cBbScA|b（1）试求句型aAaBcbbdcc和aAcbBdcc的句柄；（2）写出句子acabcbbdcc的最左推导过程。5、对于文法GS： S（L）|aS|a LL, S|S

8、（1）画出句型（S,（a）的语法树。（2）写出上述句型的全部短语、直接短语、句柄和素短语。6、考虑文法GT：TT*F|FFFP|PP（T）|i证明T*P（T*F）是该文法的一个句型，并指出直接短语和句柄。单选解答 1、选c。2、选a。3、选c。4、虽然a与b没有优先关系，但构造优先函数后，a与b就肯定存在优先关系了。所以，由f(a)g)(b)或f(a)g(b)并不能判定原来的a与b之间是否存在优先关系：故选c。EE + FE + T PT iP #+#图2-8-1 句型P+T+I的语法及优先关系5、假如文法G无二义性，则最左推导是先生长右边的枝叶：对于d，假如有两个不同的是了左推导，则必定有二

9、义性。故选a。6、选c。7、由图2-8-1的语法树和优先关系可以看出应选b。8、规范推导是最左推导，故选d。9、由TT,和T( 得FIRSTVT(T)=(,，)； 由TS得FIRSTVT(S)FIRSTVT(T)，而FIRSTVT(S)=b,(；即 FIRSTVT(T)=b,(,，； 因此选c。 10、d 11、c 12、b 13、b 14、b多选解答 1、e、a、c 2、a、c、e 3、b、c、d 4、a、c 5、b、c 6、a、b、c、d、e填空解答 1、空集 终结符 右 2、最左 3、自上而上 自下而上 4、自上而上 5、语法 分析 6、移进 接受 7、4 2 型 3型 上下文无关语言

10、正规语言 下推自动机 有限推断解答 1、对 2、错 3、错 4、错 5、错 6、错 简答解答 1、句柄：一个句型的最左直接短语称为该句型的句柄。2、素短语：至少含有一个终结符的素短语，并且除它自身之外不再含任何更小的素短语。3、语法树：满足下面4个条件的树称之为文法GS的一棵语法树。每一终结均有一标记，此标记为VNVT中的一个符号；树的根结点以文法GS的开头符S标记；若一结点至少有一个直接后继，则此结点上的标记为VN中的一个符号；若一个以A为标记的结点有K个直接后继，且按从左至右的挨次，这些结点的标记分别为X1,X2,XK，则AX1,X2,XK，必定是G的一个产生式。4、归约：我们称直接归约出

11、A，仅当A 是一个产生式，且、(VNVT)*。归约过程就是从输入串开头，反复用产生式右部的符号替换成产生式左部符号，直至文法开头符。5、推导：我们称A直接推出，即A，仅当A 是一个产生式，且、(VNVT)*。假如12n，则我们称这个序列是从1至2的一个推导。若存在一个从1n的推导，则称1可推导出n。推导是归约的逆过程。 问答1解答一个上下文无关文法G是一个四元式（VT,VN,S, P），其中：VT是一个非空有限集，它的每个元素称为终结符号；VN是一个非空有限集，它的每个元素称为非终结符号，VTVN=；S是一个非终结符号，称为开头符号；P是一个产生式集合（有限），每个产生式的形式是P，其中，PV

12、N，(VTVN)*。开头符号S至少必需在某个产生式的左部消灭一次。 2解答 （1）由于产生式左部存在终结符号，且全部产生式左部符号的长度均小于等于产生式右部的符号长度，所以文法GS是Chomsky1型文法，即上下文有关文法。（2）按产生式消灭的挨次规定优先级由高到低（否则无法推出句子），我们可以得到： SabQabc SaSPQaabQPQaabPQQaabbQQaabbcQaabbcc SaSPQaaSPQPQaaabQPQPQaaabPQQPQaaabPQPQQaaaPPQQQaaabbPqqqaaabbQQQaaabbbcQQaaabbbccQaaabbbccc 于是得到文法GS生成的语

13、言L=anbncn|n13【解答】（1）由L=aibj|ji1知，所求该语言对应的上下文无关文法首先应有SaSb型产生式，以保证b的个数不少于a的个数；其次，还需有SSb或SbS型的产生式，用以保证b的个数多于a的个数；也即所求上下文无关文法GS为：GS：SaSb|Sb|b4【解答】（1）分别画出对应两句型的语法树，如图2-8-2所示句柄:AaB Bd Sa A c B AaB b S c AB d cb(a)S a A c BB S c AB d c(b)图2-8-2 语法树（2）句子acabcbbdcc的最左推导如下： SaAcBaAaBcBacaBcBacabcBacabcbScAaca

14、bcbBdcA acabcbbdcAacabcbbdcc S（ L ）L ， SS ( L ) S a图2-8-3 句型（S,（a）的语法树5【解答】（1）句型（S,（a）的语法树如图2-8-3所示（2）由图2-8-3可知：短语：S、a、(a)、S,(a)、(S,(a)；直接短语：a、S；句柄：S；素短语：素短语可由图2-8-3中相邻终结符之间的优先关系求得，即；# （，（a ） ） #因此素短语为a。TT * FF PP （ T ）T * F图2-8-4 句型T*P（T*F）的语法树6【解答】首先构造T*P（T*F）的语法树如图2-8-4所示。由图2-8-4可知，T*P（T*F）是文法GT的

15、一个句型。直接短语有两个，即P和T*F；句柄为P。第三章一、单项选择题1、词法分析所依据的是 。a. 语义规章b. 构词规章c. 语法规章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. 含奇

16、数个0的二进制数组成的集合 d. 含偶数个0的二进制数组成的集合5、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此， 。a. 词法分析器应作为独立的一遍 b. 词法分析器作为子程序较好c. 词法分析器分解为多个过程，由语法分析器选择使用 d. 词法分析器并不作为一个独立的阶段二、多项选择题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、确定有限自动机DFA是 的

17、一个特例。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)。（ ）6、对任意一个右线性文法G，都存在一个DFA M，满足L(G)=L(M)。（ ）7、对任何正规表达式e，都存在一个NFA M，满足L(G)=L(e)。（ ）8、对任何

18、正规表达式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）yf（y,a） f（y,b）x,y 试构造相应的确定有限自动机M。2、对给定正规式b*（d|ad）（b|ab）+，构造其NFA M； 单选解答 1、b 2、c 3、c 4、d 5、b多选解答 1、a、c、e 2、a、b、d填空解答 1、NFA 2、正规集 3、DFA（NFA）所识别推断解答 1 、2、3、错 4、5、6、7、8、正确 a a b b b图3-6-2 NFA MXY基本1解答：对比自动机的定义

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

20、成终态组1，2与非终态组0；其次，考察1,2。由于1,2a=1,2b=21,2，所以不再将其划分了，也即整个划分只有两组0，1,2：令状态1代表1,2，即把原来到达2的弧都导向1，并删除状态2。最终，得到如图3-6-6所示化简DFA M。aadb*b*(d|ad)(b|ab)(b|ab)*XYX123YX4135Y678(d|ad)(b|ab)(b|ab)*2dbadabb|abbX4135Y2bdbbabb图3-6-7 的NFA M2解答：首先用A+=AA*改造正规式得：b*(d|ad)(b|ab)(b|ab)*；其次，构造该正规式的NFA M，如图3-6-7所示。第四章1、 构造下面文法的

21、LL（1）分析表。D TLT int | realL id RR , id R | 2、 下面文法GS是否为LL（1）文法？说明理由。S A B | P Q x A x y B b cP d P | Q a Q | 3、 设有以下文法： GS：SaAbDe|d ABSD|e BSAc| cD| DSe| （1）求出该文法的每一个非终结符U的FOLLOW集。（2）该文法是LL（1）文法吗？（3）构造CS的LL（1）分析表。4、 将文法GV改造成为LL(1)的。 GV：VN|NE EV|V+E Ni5、已知文法：GA：AaAa|（1）该文法是LL（1）文法吗？为什么？（2）若接受LL（1）方法进行

22、语法分析，如何得到该文法的LL（1）分析表？（3）若输入符号串“aaaa”，请给出语法分析过程。1解答： LL（1）分析表见表4-3-1分析 虽然这个文法很简洁，我们还是从求开头符号集合和后继符号集合开头。 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填在输入符号#

23、的栏目中。表4-3-1 LL（1）分析表非终结符输入符号int realid，#DDTLDTLTTintTrealLLid RRR,id RR 2解答： 该文法不是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解答： （1）求文法的每一个非终结符U的FOLLOW集的过程如下：由于： S是识别符号，且有ABSD、BSAc、DSe，所以F

24、OLLOW（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 由于SaAbDe | d、ABSD| e和BSAc | cD，所以FOLLOW（D）=FIRST（e）FOLLOW（A）FOLLOW（B） =eb,ca,d=a,b,c,d,e（2

25、）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提取公共左因子后得到文法： GV：VNAA|EEVBB|+ENi求出文法GV中每一个非终结符号的FIRST集： FIRST(V)=iFIRST(A)=, FIRST(E)=iFIRST(B)=+, FIRST(N)=i求出文法GV中每一个非终

26、结符号的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的产生式A|E，有FIRST(E)FOLLOW(A)=+,#= 对产生式B|+E，有FIRST(+E)FOLLOW(B)=+= 而文法的其他产生式都只有一个不为的右部，所以文法GV是LL(1)文法。5解答：（1）由于产生式AaAa| 有空产

27、生式右部，而 FOLLOW(A)=#FIRST(a)=a, #造成 FIRST(A)FOLLOW(A)=A, a, #所以该文法不是LL（1）文法。（2）若接受LL（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)方法进行语法分析，对符号串

28、“aaaa”的分析过程如表4-3-4所示。 表4-3-4对符号串“aaaa”的分析过程步骤分析栈输入串产生式/动作1#Aa a a a #AaaA2#A a aa a a a #匹配3#A aa a a #匹配4#Aa a #AaaA5#A a aa a #匹配6#A aa#匹配7#A#A8#接受第五章1.设有文法GS为：Sa|b|(A)ASdA|S（1） 完成下列算符优先关系表，见表5-7-1，并推断GS是否为算符优先文法。表5-7-1 算符优先关系表ab()d#ab()d# （2）给出句型（SdSdS）的短语、简洁短语、句柄、素短语和最左素短语。（3）给出输入串（adb）#的分析过程。解答

29、： （1）先求文法GS的FIRSTVT集和LASTVT集：由Sa|b|(A)得：FIRSTVT(S)=a,b,( );由ASd得：FIRSTVT(A)=d;又由AS得：FIRSTVT(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)

30、得：(); 由S(A得：(FIRSTVT(A)，即：(d,(a ,(b,(;由AdA得：dFIRSTVT(A)，即：dd,da,db,d(; 由SA)得，LASTVT(A)，即：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 句

31、型（SdSdS）的语法树（2）为求出句型（SdSdS）的短语、简洁短语、句柄，我们先画出该句型对应的语法树，如图5-7-3所示。由图5-7-3得到：短语：S，SdS，SdSdS，（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

32、）归约#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、就文法的描述力量来说，有 。 a. SLR（1）LR（0） b. LR（1）LR（0）c. SLR（1）LR（1）d.无二义文法LR（1）4、在LR（0）的ACTION子表中，假如某一行中存在标记“rj”的栏，则 。 a.该行必定填满rjb.该行未填满rjc.其他行也有rjd.goto子表中也有rj5、一个

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

34、SLR（1）c. LR（0）LR（1）d. LR（1）无二义文法 e. SLR（1）无二义文法6、对LR分析器来说，存在 等分析表的构造方法。 a.LALRb.LR（0）c.SLR（1）d.SLR（0）e.LR（1）7、自上而下的语法分析方法有 。 a.算符优先分析法b.LL（1）分析法c.SLR（1）分析法d.LR（0）分析法e.LALR（1）分析法三、填空题1、对于一个文法，假如能够构造 。使得它的 均是唯一确定的，则称该文法为LR文法。2、字的前缀是指该字的 。3、活前缀是指 的一个前缀，这种前缀不含 之后的任何符号。4、在LR分析过程中，只要 的已扫描部分保持可归约成一个 ，则扫描过的

35、部分正确。5、将识别 的NFA确定化，使其成为以 为状态的DFA，这个DFA就是建立 的基础。6、A称为 项目；对文法开头符S为 项目；若a为终结符，则称Aa为 项目；若B为非终结符，则称Aa为 项目。 7、LR（0）分析法的名字中“L”表示 ，“R”表示 ，“0”表示 。四、综合题1、对于文法GS： SAS|b ASA|a （1）列出全部LR（0）项目（2）列出构成文法LR（0）项目集规范族。单项解答： 1、A称为归约项目，对文法开头符S的归约项目，如S称为接受项目，Aa（a为终结符）称为移进项目。在此选b.2、当用产生式A归约时，LR（0）无论面临什么输入符号都进行归约；SLR（1）则仅当

36、面临的输入符号aFOLLOW(A)时进行归约；LR（1）则当在把归约为A的规范句型的前缀Aa前提下，当后跟终结符a时，才进行归约；因此选d。3、由于LR（0）SLR（1） LR（1）无二义文法，故选c。4、选a。5、选c。多选解答： 1、一个LR分析器包括一个总控程序和一张分析表，选a、d。2、选c、e。3、选a、c、d、e。4、在LR分析表的构造中有可能存在“移进”/“归约”和“归约”/“归约”冲突；故选c、e。5、选a、b、c、d、e。6、选a、b、c、e。7、选a、c、d、e。填空解答： 1、一张分析表 每个入口2、任意首部3、规范句型 句柄4、输入串 活前缀5、活前缀 项目集合 LR分

37、析算法6、归约 接受 移进 待约7、自左至右分析 接受最右推导的逆过程即最左归约 向右查看0个字符综合解答：首先将文法G拓广为GS：SSSAS|bASA|a（1）文法GS的LR（0）项目是： 1、SS5、SAS9、ASA 2、SS6、Sb10、ASA 3、SAS7、Sb11、Aa 4、SAS8、ASA12、Aa2、列出构成文法LR（0）项目集规范族。用-CLOSURE（闭包）方法构造文法G的LR（0）项目集规范族如下：I0：1、SS I3：9、ASAI6：12、Aa 3、SAS8、ASAI7：7、Sb 8、ASA3、SAS 11、Aa6、Sb 6、Sb11、AaI1：2、SSI4：10、ASA

38、 9、ASA4、SAS8、ASA3、SAS11、Aa6、Sb3、SAS8、ASA6、Sb 11、AaI2：4、SASI5：5、SAS 3、SAS9、ASA6、Sb8、ASA 8、ASA11、Aa 11、Aa3、SAS6、Sb留意：I1中的SS和ASA是由状态I0中的1和3读入一个S字符后得到的下一个项目；，而I4中的ASA和AAS则是由I3中的9和3读入一个A字符后得到的下一个项目；I5中的SAS和ASA则是由I4中的4和8读入一个S字符后得到的下一个项目。状态全体构成了文法G的LR（0）规范族。第七章一、单项选择题1、中间代码生成所依据的是 。a.语法规章b.词法规章c.语义规章d.等价变换规章2、四元式之间的联系是通过 实现的。 a.指示器b.临时变量c.符号表d.程序变量3、后缀式ab+cd+/可用表达式 来表示。a.a+b/c+db.(a+b)/(c+d)c.a+b/(c+d)d.a+b+c/d4、表达式（AB）（CD）的逆波兰表示为 。 a. ABCDb. ABCDc. ABCDd. ABCD5、中间代码的树型表示+ABCD+ 所对应的表达式为 。 a.A+B+C+Db.A+(B+C)+Dc.(A+B)+C+Dd.(A+B)+(