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

1、第一章1、将编译程序分成若干个“遍”是为了 。b. 使程序的结构更加清晰2、 构造编译程序应掌握 。a. 源程序b. 目标语言c. 编译方法3、 变量应当。c.既持有左值又持有右值4、 编译程序绝大多数时间花在 上。d. 管理表格5、 不可能是目标代码。d 中间代码6、 使用可以定义一个程序的意义。a. 语义规则7、 词法分析器的输入是 。b 源程序8、中间代码生成时所遵循的是 -。c.语义规则9、 编译程序是对。d.高级语言的翻译10、 语法分析应遵循 。c.构词规则二、多项选择题1、 编译程序各阶段的工作都涉及到 。b. 表格管理c.出错处理2、 编译程序工作时，通常有 阶段。a. 词法分

2、析b 语法分析c.中间代码生成e.目标代码生成三、填空题1、 解释程序和编译程序的区别在于是否生成目标程序 。2、 编译过程通常可分为 5个阶段，分别是一词法分析 、语法分析 中间代码生成 _、代码优化和目标代码生成。3、编译程序工作过程中， 第一段输入是源程序,最后阶段的输出为 标代码生成 程序。4、编译程序是指将 源程序 程序翻译成 目标语言 程序的程序。、单项选择题1、 文法G: StxSx|y所识别的语言是 。a. xyxb. (xyx)* c. xnyxn(n > 0)d. x*yx*2、文法G描述的语言L(G)是指。a. L(G)= a |S+ a, a Vt*b. L(G)

3、= a |S a , a Vt*a |S? a , a (VtU Vn*)c. L(G)= a |S?* a ,a (VtU Vn*)d. L(G)=3、有限状态自动机能识别15 / 27a.上下文无关文法b. 上下文有关文法c.正规文法d.短语文法4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立a.若 f(a)>g(b)，贝U a>bb.若 f(a)<g(b)，贝U a<bc. ab都不一定成立d. ab 一定成立5、如果文法 G是无二义的，则它的任何句子aa.最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导

4、和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同6、由文法的开始符经 0步或多步推导产生的文法符号序列是a.短语b.句柄c. 句型d. 句子7、文法 G : Et E+T|TTt T*P|PPt (E)|I则句型P+T+i的句柄和最左素短语为 a.P+T 和 i b. P 和 P+T c. i 和 P+T+i d.P 和 T8、设文法为：St SA|A则对句子aba,A t a|b卜面是规范推导。a.sSAsaaAAAaAAabA abab.ssasaaAAAAAaAba abac.ssasaaSAaSbaAba abad.ssaSaSAa Sba Aba aba9、

5、文法 G: St b|A (T)Tt T,S|S贝U FIRSTVT(T) 。a. b, A ,(b. b, A ,)c.b, A ,(, d.b, A ,), 10、 产生正规语言的文法为_a. 0型b. 1型11、采用自上而下分析，必须a.消除左递归b.消除右递归12、在规范归约中，用来刻画可归约串。a.直接短语b.句柄13、有文法G:Et e*T|TT t T+i|ic. 2型d.3型c.消除回溯d.提取公共左因子c.最左素短语d.素短语句子1+2*8+6按该文法G归约，其值为a. 23 B. 42 c. 30 d.14、规范归约指。a.最左推导的逆过程c.规范推导、多项选择题1、下面哪

6、些说法是错误的 。a.有向图是一个状态转换图c.有向图是一个DFA17b.最右推导的逆过程d.最左归约的逆过程b.状态转换图是一个有向图d.DFA可以用状态转换图表示2、对无二义性文法来说，一棵语法树往往代表了a.多种推导过程b.多种最左推导过程。C. 一种最左推导过程d.仅一种推导过程e.种最左推导过程3、如果文法G存在一个句子，满足下列条件a. 该句子的最左推导与最右推导相同b. 该句子有两个不同的最左推导c. 该句子有两棵不同的最右推导d. 该句子有两棵不同的语法树之一时，则称该文法是二义文法。e.该句子的语法树只有一个4、有一文法G : St ABA t aAb| eBt cBd| e

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

8、、 在语法分析中，最常见的两种方法一定是 分析法，另一是 分析法。4、 采用 语法分析时，必须消除文法的左递归。5、 树代表推导过程， 树代表归约过程。6、 自下而上分析法采用 、归约、错误处理、 等四种操作。7、 Chomsky把文法分为 种类型，编译器构造中采用 和文法，它们分别产生和语言，并分别用 和自动机识别所产生的语言。四、判断题1、文法 St aS|bR&描述的语言是（a|bc）*（）Rc S2、 在自下而上的语法分析中，语法树与分析树一定相同。（）3、 二义文法不是上下文无关文法。（）4、 语法分析时必须先消除文法中的左递归。（）5、 规范归约和规范推导是互逆的两个过程。

9、（）6、 一个文法所有句型的集合形成该文法所能接受的语言。（）五、简答题1、句柄2、素短语3、语法树4、归约 5、推导六、问答题1、给出上下文无关文法的定义。2、文法 GS:St aSPQ|abQQi PQbPT bbbQT bccQt cc（1）它是Chomsky哪一型文法？（2）它生成的语言是什么？3、按指定类型，给出语言的文法。L=a ibj|j > i > 1的上下文无关文法。4、有文法 G: StaAcB|BdA t AaB|cBt bScA|b(1) 试求句型 aAaBcbbdcc和aAcbBdcc的句柄；(2) 写出句子 acabcbbdcc的最左推导过程。5、对于文

10、法GS:St( l ) |aS|aLt l, S|S(1) 画出句型(S, (a)的语法树。(2)写出上述句型的所有短语、直接短语、句柄和素 短语。6、考虑文法GT:T t t*F|F Ft F f P|PPt( T) |i证明T*P f( T*F )是该文法的一个句型，并指出直接短语和句柄。 单选解答1、选 c。2、选 a。3、选 c。4、虽然a与b没有优先关系，但构造优先函数后，a与b就一定存在优先关系了。所以,由f(a)>g)(b)或f(a)<g(b)并不能判定原来的a与b之间是否存在优先关系：故选c。5、如果文法 G无二义性，则最左推导是先生长右边的枝叶：对于d，如果有两个

11、不同的是了左推导，则必然有二义性。故选 a。6、选 c。7、由图2-8-1的语法树和优先关系可以看出应选EE + F /l I E + T P IItiP#< + >+< >#图2-8-1句型P+T+I的语法及优先关系8、 规范推导是最左推导，故选d。9、由 Tt T,和 T t( 得 FIRSTVT(T)=(, , );由 Tt S 得 FIRSTVT(S) ? FIRSTVT(T)，而 FIRSTVT(S)=b, A ,(; 即 FIRSTVT(T)=b, A ,(, ;因此选 c。10、d 11、c 12、b 13、b 14、b多选解答 1、e、a、c 2、a、c

12、、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 型上下文无关语言 正规语言下推自动机 有限判断解答 1、对 2、错3、错 4、错5、错 6、错简答 解答 1、句柄：一个句型的最左直接短语称为该句型的句柄。2、素短语：至少含有一个终结符的素短语，并且除它自身之外不再含任何更小的素短语。3、语法树：满足下面 4个条件的树称之为文法 GS 的一棵语法树。 每一终结均有一标记，此标记为VnU Vt中的一个符号； 树的根结点以文法 GS 的开始符 S 标记； 若一结点至少有

13、一个直接后继，则此结点上的标记为Vn中的一个符号； 若一个以 A 为标记的结点有 K 个直接后继，且按从左至右的顺序，这些结点的标 记分别为Xi,X2,Xk，贝U AX i,X2,Xk，必然是G的一个产生式。4、 归约：我们称仏丫直接归约出aA 仅当 A y 是一个产生式，且a、B(VnU VT)* 。归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。5、推导：我们称a A B直接推出aY3，即a A 3仏丫，仅当A宀丫是一个产生式，且a、3 (Vn U Vt)*。如果a 1 a 2 a n,则我们称这个序列是从a1至a 2的一个推导。若存在一个从a 1 a

14、 n的推导，则称a 1可推导出a n。推导是归约的逆过程。问答 1解答 一个上下文无关文法 G是一个四元式(Vt,Vn,S, P),其中： Vt是一个非空有限集，它的每个元素称为终结符号； Vn是一个非空有限集，它的每个元素称为非终结符号，Vt A Vn=； S是一个非终结符号，称为开始符号； P是一个产生式集合(有限)，每个产生式的形式是 Pt a,其中，P Vn, a (VtU Vn)*。开始符号S至少必须在某个产生式的左部出现一次。2解答( 1)由于产生式左部存在终结符号,且所有产生式左部符号的长度均小于等于产生式右 部的符号长度，所以文法GS是Chomsky1型文法，即上下文有关文法。

15、(2) 按产生式出现的顺序规定优先级由高到低(否则无法推出句子)，我们可以得到:S abQ abcSaSPQaabQPQaabPQQ aabbQQ aabbcQaabbccSaSPQaaSPQPQaaabQPQPQ aaabPQQPQaaabPQPQQ aaaPPQQQaaabbPqqqaaabbQQQ aaabbbcQQ aaabbbccQaaabbbccc于是得到文法 GS生成的语言L=anbncn|n13【解答】(1)由L=a ibj|j > i > 1知，所求该语言对应的上下文无关文法首先应有St aSb型产生式, 以保证b的个数不少于 a的个数；其次，还需有 St Sb或

16、StbS型的产生式，用以保证 b的个数多于a的个数；也即所求上下文无关文法GS为：GS: St aSb|Sb|b4【解答】(1 )分别画出对应两句型的语法树，如图2-8-2所示句柄：AaBBd(2)SB d cA(b)图 2-8-2语法树句子acabcbbdcc的最左推导如下:S aAcB aAaBcB acaBcBacabcBacabcbScA acabcbBdcAacabcbbdcA acabcbbdcc5【解答】(1)句型(S, (a)的语法树如图2-8-3 所示S-(L )L I S/ lL )a图2-8-3 句型(S, (a)的语法树(2)由图2-8-3可知： 短语：S、a、(a)、

17、S,(a)、(S,(a); 直接短语：a、S; 句柄：S; 素短语：素短语可由图2-8-3中相邻终结符之间的优先关系求得，即;# *严 a ) #因此素短语为a。6【解答】首先构造T*P f( T*F )的语法树如图2-8-4所示。直接短语有两个，即P和T*F ;句柄为P。由图2-8-4可知，T*P f( T*F )是文法 GT的一个句型。图2-8-4 句型T*P f (T*F )的语法树第三章、单项选择题1、 词法分析所依据的是。a.语义规则 b.构词规则2、词法分析器的输出结果是 。a.单词的种别编码c.单词的种别编码和自身值3、正规式Mi和M2等价是指ca. Mi和M2的状态数相等c.

18、Mi和M2所识别的语言集相等c. 语法规则d.等价变换规则b. 单词在符号表中的位置d. 单词自身值b. Mi和M2的有向弧条数相等d. Mi和M2状态数和有向弧条数相等4、状态转换图(见图 3-6-i)接受的字集为a.以0开头的二进制数组成的集合b.以0结尾的二进制数组成的集合c. 含奇数个0的二进制数组成的集合d.含偶数个0的二进制数组成的集合5、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，_。a.词法分析器应作为独立的一遍b.词法分析器作为子程序较好c词法分析器分解为多个过程，由语法分析器选择使用d.词法分析器并不作为一个独立的阶段、多项选择题1、在词法分析中,能识别

19、出。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是的一个特例。2、 若二个正规式所表示的 相同，则认为二者是等价的。3、 一个字集是正规的，当且仅当它可由 所。四、判断题1、一个有限状态自动机中，有且仅有一个唯一终态。()2、设r和s分别是正规式，则有 L ( r|s) =L(r)|L(s)。()3、自动机M和M'的状态数不同，则二者必不等价。()4、确定的自动机以及不确定的自动

20、机都能正确地识别正规集。()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、对任何正规表达式 e,都存在一个 DFA M，满足L(G)=L(e)。()五、基本题1、设M =( x,y, a,b, f,x,y)为一非确定的有限自动机，其中f定义如下:f (x,a)= x,yf (x,b)= yf (y,a)=©f (y,b)= x,y试构造相应的确定有限自动机M'。2、对给定正规式b

21、*(d|ad)(b|ab)+构造其NFA M ;单选解答1、b2、c3、c4、d5、b多选解答1、a、c、e2、a、b、d填空解答1、NFA2、正规集3、DFA ( NFA )所识别判断解答1 、2、3、错4、5、6、7、8、正确基本1解答：对照自动机的定义 M=(S,工,f,S0,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数,所以是一非确定有限自动机，先画出NFA M相应的状态图，如图 3-6-2所示。用子集法构造状态转换矩阵表3-6-3所示。II aIbXx,yyy一x,yx,yx,yx,y将转换矩阵中的所有子集重新命名而形成表3-6-4所示的状态转换矩阵。表3-6-4状态转

22、换矩阵bb将图3-6-5的DFA M '最小化。首先，将M 的状态分成终态组1 , 2与非终态组0;其次,考察1,2。由于1,2a=1,2b=2 ?1,2，所以不再将其划分了，也即整个划分只有两组0,2。最后，得到如图3-6-62解答：首先用如图3-6-7所示。A+=AA *改造正规式得：b*(d|ad)(b|ab)(b|ab) *;其次，构造该正规式的NFA M ,b*(d|ad)(b|ab)(b|ab)'ab0211一22k-22即得到M = (0,1,2, a,b, f,0, 1,2)，其状态转换图如图3-6-5所示。第四章1、构造下面文法的 LL ( 1)分析表。D t

23、 TLT t int | realLt id RRt , id R |£2、下面文法GS是否为LL (1)文法？说明理由。S t A B | P Q xA t x y B t b cP t d P | eQ t a Q | e3、设有以下文法：GS ： StaAbDe|dAtBSD|eBtSAc| cD| eDtSe| e( 1)求出该文法的每一个非终结符 U 的 FOLLOW 集(2) 该文法是 LL (1)文法吗？(3) 构造CS的LL (1)分析表。4、将文法 GV 改造成为 LL(1) 的。GV ：VtN|NEEtV|V+E5、已知文法:GA :A t aAa| &(

24、1 )该文法是LL (1 )文法吗？为什么？(2)若采用LL ( 1)方法进行语法分析，如何得到该文法的LL (1 )分析表？(3 )若输入符号串“ aaaa ”请给出语法分析过程。1解答：LL (1)分析表见表4-3-1分析 虽然这个文法很简单，我们还是从求开始符号集合和后继符号集合开始。FIRST( D)=FIRST(T)=int,realFOLLOW( D)=FOLLOW( L) =#FIRST( L)=idFOLLOW(T)=idFIRST(R)=, , £FOLLOW(R)=#有了上面每个非终结符的FIRST集合，填分析表时要计算一个产生式右部a的FIRST ( a)就不是

25、件难事了。填表时唯一要小心的时，&是产生式Rt £右部的一个开始符号，而#在 FOLLOW (R)中,所以Rt &填在输入符号#的栏目中。表4-3-1 LL (1)分析表非终结符输入符号intrealid#DDt tlD t TLTTt intT t realLL t id RRR t ,id RR t &2解答： 该文法不是LL (1)文法，见下面分析中的说明。分析只有三个非终结符有两个选择。1、P的两个右部d P和&的开始符号肯定不相交。2、Q的两个右部a Q和&的开始符号肯定不相交。3、对S来说，由于 x FIRST(A B)，同时也有

26、x FIRST(P Q x)(因为P和Q都可能 为空)。所以该文法不是 LL (1)文法。3解答： (1)求文法的每一个非终结符U的FOLLOW 集的过程如下：因为： S是识别符号，且有 A t BSD、Bt SAc、Dt 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# 又因为AtBSD和Dt &所以FOLLOW 中还包含 FOLLOW(A)。因为St aAbDe和B f SAc,所以FOLLOW (A) =FIRST (bDe )U FIRST (c) =b,c

27、综合、得 FOLLOW (S) =a,d,c,e,# U a,b,c,d,e,#因为 A f BSD，所以 FOLLOW ( B) =FIRST (SD) =a,d因为 St aAbDe | d、A f BSD| e 和 B f 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)文法。因为产生式 Bf SAc|cD| £中FIRST ( SAc)n FOLLOW ( B) =a,d工?(3) 构造GS的LL (1 )分析表。按照LL (1

28、)分析表的构造算法构造方法GS的LL (1)分析表如表4-3-2所示。表4-3-2 GS的LL (1)分析表abcde#saAbDedABSDBSDBSDeBSac/ ecDSac/ eDSe/ eeeSe/ ee4解答： 对文法GV提取公共左因子后得到文法:G ' V : V f NAAf 乱 EEf VBBf d +EN f i求出文法G ' V中每一个非终结符号的FIRST集：FIRST(V)=iFIRST(A)=,dFIRST(E)=iFIRST(B)=+,£FIRST(N)=i求出文法G ' V中每一个非终结符号的FOLLOW 集：FOLLOW(V)

29、=# U FIRST(B) d U FOLLOW(E)=#,+,FOLLOW(A)= FOLLOW(V)=+,#FOLLOW(E)= FIRST() d U FOLLOW(B)= FIRST()£ U FOLLOW(E)=FOLLOW(B)= FOLLOW(E)= FOLLOW(N)= FIRST(A) d U FOLLOW(V)=,+,#可以看到，对文法 G ' V的产生式A f乱E，有FIRST(E) n FOLLOW(A)= n +,#= ?对产生式B宀耳+E,有FIRST(+E) A FOLLOW(B)=+ n = ?而文法的其他产生式都只有一个不为舶右部，所以文法

30、G ' V是LL(1)文法。5解答：(1 )因为产生式 AtaAa| &有空产生式右部，而FOLLOW(A)=# U FIRST(a)=a, #造成 FIRST(A) A FOLLOW(A)=A, & A a,#工?所以该文法不是 LL (1)文法。(2)若采用LL ( 1)方法进行语法分析，必须修改该文法。因该文法产生偶数(可以为0 )个a，所以得到文法G ' A :AtaaA| &此时对产生式 A t aaA| &,有 FOLLOW(A)=# U FOLLOW(A)=#，因而FIRST(A) A FOLLOW(A)=a, & A #=

31、?所以文法G ' A是LL (1)文法，按LL ( 1)分析表构造算法构造该文法的LL (1 )分析表如表4-3-3所示。表4-3-3文法G ' A的LL(1)分析表A#AA t aaAA t &(3)若采用LL(1)方法进行语法分析，对符号串“aaaa”的分析过程如表 4-3-4所示。表4-3-4对符号串“ aaaa ”的分析过程步骤分析栈输入串产生式/动作1#Aa a a a #A t aaA2#A a aa a a a #匹配3#A aa a a #匹配4#Aa a #A t aaA5#A a aa a #匹配6#A aa#匹配7#A#A t &8#接受第

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

33、 St a|b|(A)得；LASTVT(S)=a,b,;由 At.dA 得：LASTVT(A)=d, 又由 A t S 得：LASTVT(S) ? LASTVT(A)，即 LASTVT(A)=d,a,b,)。构造优先关系表方法如下： 对Ptab，或 PtaQb，有a? b; 对 PtaR，而 b FIRSTVT(R)，有 a?b; 对 PtRb ，而 a FIRSTVT(R)，有 a?b。由此得到： 由 St (A)得：(?); 由 St(A 得：(?FIRSTVT(A)，即：(?d,(?a ,(?b,(?(;由 A宀dA 得：d?FIRSTVT(A),即：d?d,d?a,d?b,d ?(;

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

35、3所示。由图5-7-3得到： 短语：S，SdS, SdSdS，（SdSdS） 简单短语（即直接短语）：S 句柄（即最左直接短语）：S素短语：SdS,它同时也是该句型的最左素短语。图5-7-3句型（SdSdS）的语法树（3）输入串（adb） #的分析过程见表 5-7-4表5-7-4 输入串（adb）#的分析过程符号栈输入串说明#(adb)#移进#（adb)#移进#( adb)#用St a归约#( Sdb)#移进#( Sdb)#移进# (Sdb)#用St b归约# (SdS)#用AtS归约# (SdA)#用A t SdA归约# (A)#移进# (A)#用St( A)归约#S#分析成功第六章一、单项

36、选择题1、若a为终结符，则A faa B为项目a. 归约b.移进c.接受d.待约2、 若项目集Ik含有Aa，则在状态k时，仅当面临的输入符号 a扌OLLOW(A)时，才采 取"A t a ”动作的一定是。a.LALR文法b丄R (0)文法c丄R (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. 其他行

37、也有rjd.goto子表中也有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.归约e.报错4、 对LR分析表的构造，有可能存在 动作冲突。40 / 27a.移进b.归约c.移进/归约d.移进/移进e.归约/归约5、就文法的描述能

38、力来说，有a. SLR (1) ?LR (1)d. LR (1) ?无二义文法6、对LR分析器来说，存在a.LALRb.LR( 0)7、自上而下的语法分析方法有a.算符优先分析法d.LR( 0)分析法三、填空题b. LR( 1)?SLR( 1)e. SLR( 1)?无二义文法_等分析表的构造方法。c. SLR( 1)d.SLR( 0)b.LL( 1)分析法e.LALR ( 1)分析法c. LR（ 0） ?LR（ 1）e.LR（ 1）c.SLR（ 1）分析法1、对于一个文法，如果能够构造 文法。使得它的均是唯一确定的，则称该文法为LR2、 字的前缀是指该字的 。3、 活前缀是指 的一个前缀，这种

39、前缀不含 之后的任何符号。4、 在LR分析过程中，只要 的已扫描部分保持可归约成一个 ，则扫描过的部分正确。5、将识别的NFA确定化，使其成为以 为状态的DFA，这个DFA就是建立的基础。6、A fa 称为项目；对文法开始符 S'fa为项目；若a为终结符，则称A a a 3为项目；若B为非终结符，则称 Af a a 3为项目。7 、LR(0)分析法的名字中“L”表示，“R”表示，“0”表示。四、综合题1、对于文法 GS : Sf AS|bA f SA|a(1) 列出所有LR ( 0)项目(2) 列出构成文法 LR (0)项目集规范族。单项解答：1 、Af a 称为归约项目，对文法开始符

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

41、有可能存在“移进”/“归约”和“归约” /“归约”冲突；故选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:SJ SSt AS|bA t SA|a(1文法GS的LR (0)项目是：1、S'tS5、St AS 9、AtS. A2、S't S6、St. b10、AtSA.3、St.AS7、St b

42、11、At. a4、StAS8、A t. SA12、Ata.2、列出构成文法 LR ( 0)项目集规范族。用 & -CLOSURE(闭包)办法构造文法 G'的LR ( 0)项目集规范族如下：Io： 1、S't. SI 3： 9、 A t S. AI 6： 12 、 A t a3、 St. AS8、 At. SAI 7： 7、 St b.8、 At. SA3、 St. AS11、 At. a6、 St. b6、 St. b11、 At. a2、S'jS I4：10、A j SA 9、AjS- A4、Sj A S8、ASA3、s j.as11、Aa6、s j.b3、

43、SAS8、A jSA6、Sb11、A j-a4、S J A SI5： 5、Sj AS 3、SAS9、A j S a6、Sb8、A jsa8、ASA11、A j-a11、Aa3、s j.as6、S jb注意：丨1中的SJ S和AtSA是由状态Io中的1和3读入一个S字符后得到的下一个项目；， 而14中的A jSA和A jA S则是由I3中的9和3读入一个 A字符后得到的下一个项目； I5 中的Sj AS 和A J S A则是由I4中的4和8读入一个S字符后得到的下一个项目。状态全体构成了文法 G'的LR ( 0)规范族。第七章、单项选择题1、 中间代码生成所依据的是。d.等价变换规则d.

44、程序变量d.a+b+c/da语法规则b词法规则c语义规则2、 四元式之间的联系是通过实现的。a. 指示器b.临时变量c.符号表3、 后缀式ab+cd+/可用表达式来表示。a.a+b/c+db.(a+b)/(c+d)c.a+b/(c+d)4、表达式鬥 A V B)A( CV D)的逆波兰表示为a. n AB VA CD Vb. A n B V CD VAc. AB Vn CD VAd. A n B VA CD V5、中间代码的树型表示A B C D所对应的表达式为a.A+B+C+D b.A+(B+C)+D6、四元式表示法的优点为 c.(A+B)+C+Dd.(A+B)+(C+D)a.不便于优化处理

45、，但便于表的更动b.不便于优化处理，但节省存储空间c.便于优化处理，也便于表的更动d.便于表的更动，也节省存储空间7、终结符具有属性。a.传递b.继承二、多顶选择题1、中间代码主要有 。a.四元式b .二元式式c.抽象c .二兀式d.综合d .后缀式e.间接三元2、下面中间代码形式中，能正确表示算术表达式a+b+c的有a. ab+c+ b. abc+O3、 在下面的 语法制导翻译中，采用拉链 -回填技术。a.赋值语句b. goto语句 c.条件语句d .循环语句4、 下列中间代码形式有益于优化处理。a.三元式b.四元式 c.间接三元式d.逆波兰表示法5、 在编译程序中安排中间代码生成的目的是

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

47、、 文法符号的属性有两种，一种称为 ，另一种称为 。表示。5、 后缀式abc-/所代表的表达式是 ，表达式(a-b)*c可用后缀式 6、 用一张 辅以的办法来表示中间代码，这种表示法称为间接三元式。四、综合题1、 给出下列表达式的逆波兰表示(后缀式)： a*(-b+c) (A V B) A (C D A E)2、 写出算术表达式：A+B*(C-D)+E/(C-D) f N的四元式序列；三元式序列；间接三元式序列单选解答1、选 c。2、 四元式之间的联系是通过临时变量实现的，故选b。3、选 b。4、选 b。5、选 d。6、 四元式表示法的优点与间接三元式相同，故选c。7、选 d。多选解答1、选

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

49、B,(1)(3)(+,A,T 2,T3)(3) (+,A,(2)(3)(+,A,(2)(4)C，C,D,T 4)(4) (-,C,D)(f ,(1),N)(5)(f ,T4,N,T5)(5) (f ,(4),N)(/,E,(4)(/,E,T5,T6)(/,E,(5)(+,(3),(5)(+,T3,T6,T7)(+,(3),(6)表达式的二兀式序列间接三元式序列2、表达式的四兀式序列:第八章、单项选择题1、编译程序使用区别标识符的作用域。a.说明标识符的过程或函数名b.说明标识符的过程或函数的静态层次c.说明标识符的过程或函数的动态层次d.标识符的行号2、在目标代码生成阶段，符号表用于。a.目标代码生成b.语义检杳c.语法检杳d.地址分配3、过程信息表不包含。a.过程