编译原理期末总复习题

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

2、序的意义。b.词法规则d.词法规则a oa .语义规则c .产生规则7、词法分析器的输入是a .单词符号串c .语法单位8、中间代码生成时所遵循的是a .语法规则c.语义规则9、编译程序是对 d。a .汇编程序的翻译c .机器语言的执行10、语法分析应遵循 ba .语义规则c.构词规则解答b.源程序d.目标程序-d。b.词法规则d.等价变换规则b.高级语言程序的解释执行d.高级语言的翻译b.语法规则d.等价变换规则1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选bo2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选do3、对编译而言，变量既持有左值又持有右值

3、，故选c。4、编译程序打交道最多的就是各种表格，因此选do3种，因此不是目标代码5、目标代码包括汇编指令代码、可重定位指令代码和绝对指令代码 的只能选doa。6、词法分析遵循的是构词规则，语法分析遵循的是语法规则，中间代码生成遵循的是语义规 则，并且语义规则可以定义一个程序的意义。因此选7 、b 8 、c 9 、d 10 、c、多项选择题1、编译程序各阶段的工作都涉及到bca .语法分析b.表格管理d .语义分析e.词法分析2、编译程序工作时，通常有 abcec.出错处理d解答1. b、c.词法分析.语义检查2. a 、b、c、阶段。b.语法分析语义分析？ c.中间代码生成e.目标代码生成中间

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

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

6、应的语法树必定相同最左推导和最右推导对应的语法树可能不同最左推导和最右推导必定相同可能存在两个不同的最左推导，但它们对应的语法树相同6、由文法的开始符经0步或多步推导产生的文法符号序列是a.短语b.句柄c.句型d.句子7、文法 G:E+T|T T- T*P|P A (E)|I则句型P+T+i的句柄和最左素短语为+T 和 i b. P 和 P+T c. i 和 P+T+i8 、设文法为:S- SA|Aaba, a. S卜囹SA是规范推导。abaSAA AAAaAA abAb. SSASAA AAAAAa Abaabac. SSASAA SAaSba Abaabad. SSASa SAaSba A

7、baabaAf a|b则对句子9、文法G:Sf b| A (T) T一 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.消除布1归12、在规范归约中，用 来刻画可归约串。a.直接短语b.句柄13、有文法 G: E- E*T|TT- T+i|i句子1+2*8+6按该文法 G归约，其值为 。a. 23 B. 42 c. 30 d. 1714、规范归约指。a.最左推导的逆过可c.规范推导d.c. 2型c.消除回溯c.最左素短语d.

8、 3型d.提取公共左因子d.素短语b.最右推导的逆过程最左归约的逆过程解答1 、选 c。2、选 a。3、选 Co4、虽然a与b没有优先关系，但构造优先函数后，a与b就一定存在优先关系了。所以，由f(a)>g)(b) 或f(a)<g(b)并不能判定原来的 a与b之间是否存在优先关系：故选c。5、如果文法G无二义性，则最左推导是先生长右边的枝叶：对于 d,如果有两个不同的是了左 推导，则必然有二义性。故选 a。6、选 Co7、由图2-8-1的语法树和优先关系可以看出应选boE + F/Tx iE + T PIIT iIP#<- + - >+< i >#图2-8-

9、1句型P+T+I的语法及优先关系8、规范推导是最左推导，故选 do9、由 T-T,和 T一( 得 FIRSTVT(T)=(, , );由 T一 S 得 FIRSTVT(S)? FIRSTVT(T),而 FIRSTVT(S)=b, A ,(;即因此选c。14 、bb.状态转换图是一个有向图 可以用状态转换图表示FIRSTVT(T尸b, A ,(, , ;10、d 11、c 12 、b 13 、b二、多项选择题1、下面哪些说法是错误的 。 a.有向图是一个状态转换图 c.有向图是一个 DFA2、对无二义性文法来说，一棵语法树往往代表了 。a.多种推导过程b.多种最左推导过程c. 一种最左推导过程d

10、.仅一种推导过程e. 一种最左推导过程3、如果文法G存在一个句子，满足下列条件 之一时，则称该文法是二义文法。a.该句子的最左推导与最右推导相同b.该句子有两个不同的最左推导 c.该句子有两棵不同的最右推导 d.该句子有两棵不同的语法树 e.该句子的语法树只有一个4、有一文法G: SfABA 一aAb| £Bf cBd| £它不产生下面 集合。a. a nbmcndm|n,m >0b. ac. a nbmcmdn|n,m >0d. ae. a nbncndnln >05、自下而上的语法分析中，应从 nbncmdmjn,m>0nbncmdmn,m>

11、;0开始分析。c.以单词为单位的程序d.文法的开始符 e.句柄6、对正规文法描述的语言，以下型文法 型文法 c.解答 1、e、a、c 2、a、c、e 3、有能力描述它。上下文无关文法d.右线性文法b、c、d 4 、a、c 5 、b、 c 6e.左线性文法a、b、c、d、 ea.句型b.句子三、填空题O词法分析器交给语法分析器的文法符号一定非终结符进行扩展。1、文法中的终结符和非终结符的交集是是,它一定只出现在产生式的 部。2T最左推导是指每次都对句型中的3、在语法分析中，最常见的两种方法一定是 分析法，另一是 分析法。4、采用 语法分析时，必须消除文法的左递归。5、FF代表推导过程, 树代表归

12、约过程。6、自下而上分析法采用 、归约、错误处理、 等四种操作。7、Chomsky把文法分为 种类型，编译器构造中采用 和 文法，它们分别产一答 生解.语言，并分别用 和 自动机识别所产生的语言。1IHX42终结符 右自下而上分析接受型3型上下文无关语言正规语言下推自动机有限四、判断题1、文法SfaS|bR| e描述的语言是 （a|bc）*（）RH c S2、在自下而上的语法分析中，语法树与分析树一定相同。（）3、二义文法不是上下文无关文法。（）4、语法分析时必须先消除文法中的左递归。（）5、规范归约和规范推导是互逆的两个过程。（）6、一个文法所有句型的集合形成该文法所能接受的语言。（）解答1

13、 、对 2 、错 3 、错 4 、错 5 、错 6 、错五、简答题1、句柄2、素短语3、语法树4、归约5、推导 解答1 、句柄：一个句型的最左直接短语称为该句型的句柄。2、素短语：至少含有一个终结符的素短语，并且除它自身之外不再含任何更小的素短语。3、语法树：满足下面 4个条件的树称之为文法 GS的一棵语法树。每一终结均有一标记，此标记为VnU Vt中的一个符号；树的根结点以文法 GS的开始符S标记；若一结点至少有一个直接后继，则此结点上的标记为中的一个符号；若一个以A为标记的结点有 K个直接后继，且按从左至右的顺序，这些结点的标记分别为K,X2，,Xk,则 ZX1,X2，,Xk,必然是 G的

14、一个产生式。4、归约：我们称“ 丫 3直接归约出aA3,仅当A-丫 是一个产生式，且a、3 C （VnU Vt）*归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。5、推导：我们称a A 3直接推出“丫3, 即aAB 口丫3,仅当A一 丫是一个产生式，且a、 3 C (VnU Vt)*。如果a i “2 an,则我们称这个序列是从a1至a 2的一个推导。若存在一个从a ian的推导，则称a 1可推导出a n。推导是归约的逆过程。六、问答题1、给出上下文无关文法的定义。解答一个上下文无关文法 G是一个四元式(Vt,Vn,S, P ),其中： VT是一个非空有限

15、集，它的每个元素称为终结符号； VN是一个非空有限集，它的每个元素称为非终结符号，VtAVn=； S是一个非终结符号，称为开始符号； P是一个产生式集合(有限)，每个产生式的形式是 P-a ,其中，PC X, a C (VtU Vn)*。开始符号S至少必须在某个产生式的左部出现一次。2、文法 GS:S 一 aSPQ|abQQA PQ bP- bb bQ 一 bc cCH cc(1)它是Chomsky哪一型文法？(2)它生成的语言是什么？解答(1)由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部的符号长度，所以文法 GS是Chomsky1型文法，即上下文有关文法。(2)

16、按产生式出现的顺序规定优先级由高到低(否则无法推出句子)，我们可以得到：S abQ abcS aSPQ aabQPQ aabPQQ aabbQQ aabbcQ aabbccS aSPQ aaSPQPQ aaabQPQPQ aaabPQQPQ aaabPQPQQ aaaPPQQQ aaabbPqqq aaabbQQQ aaabbbcQQ aaabbbccQ aaabbbccc于是得到文法 GS生成的语言L=anbncn|n >13、按指定类型，给出语言的文法。L=a1 bj |j > i > 1的上下文无关文法。【解答】(1)由L=aibj|j >i>1知，所求该语

17、言对应的上下文无关文法首先应有S 一 aSb型产生式，以保证b的个数不少于a的个数；其次，还需有S-Sb或S-bS型的产生式，用以保证b的个数多于a的个数；也即所求上下文无关文法GS为：GS : Sf aSb|Sb|b4、有文法 G: SfaAcB|BdZ AaB|cBf bScA|b(1)试求句型 aAaBcbbdcc和aAcbBdcc的句柄；(2)写出句子 acabcbbdcc的最左推导过程。【解答】(1)分别画出对应两句型的语法树，如图 2-8-2所示句柄：AaB BdSA c BA/八 /7(b)图2-8-2 语法树(2)句子acabcbbdcc的最左推导如下：S aAcB aAaBc

18、B acaBcB acabcB acabcbScA acabcbBdcAacabcbbdcA5、对于文法GS:acabcbbdccS(1) 语。【解答】(1)一 (L) |aS|a画出句型(S,句型(S, (a)(2)L, S|S(a)的语法树。(2)写出上述句型的所有短语、直接短语、句柄和素短的语法树如图由图2-8-3可知:S2-8-3 所示 /|(L )/ 短语：S、a、(a)、S,(a)、(S,(a);直接短语：a、S;句柄：S;a图2-8-3 句型(S, (a)的语法树素短语：素短语可由图2-8-3中相邻终结符之间的优先关系求得，即;# <(<； < (< a&

19、gt; )> ) A #因此素短语为a。6、考虑文法GT:T-T*F|F FfFT P|P P-( T) |i证明t*pT(t*f)是该文法的一个句型，并指出直接短 【解答】语和句柄。首先构造T*PT (T*F)的语法树如图2-8-4所示。由图2-8-4 可知，T*PT (T*F)是文法 GT直接短语有两个，即 P和T*F;句柄为P。的一个句型。I /l P )P2-8-4句型T*P T (T*F)的语法树、单项选择题1、词法分析所依据的是 a.语义规则b.构词规则c.语法规则d.等价变换规则2、词法分析器的输出结果是 a.单词的种别编码c.单词的种别编码和自身值 3、正规式M1和M等价

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

21、表3-6-3所示。解答 1 、 b 2 、 c二、多项选择题1、 a. d.2、在词法分析中, 基本字 逆波兰式 令汇=a,b,能识别出b.e.四元式 常数c.运算符则汇上所有以b开头，后跟若干个a. b(ab)*d. (ba) +bb. b(ab)e. b(a|b)ab的字的全体对应的正规式为 c.(ba)*b解答1、 a、c、e 2a、b、d、填空题1、确定有限自动机DFA是2、若二个正规式所表示的_的一个特例。相同，则认为二者是等价的。3、一个字集是正规的，当且仅当它可由解答1 四、判断题、NFA 2、正规集 3、DFA (NFA)所识别1、一个有限状态自动机中，有且仅有一个唯一终态。2

22、、设r和s分别是正规式,则有 L (r|s ) =L(r)|L(s)3、自动机M和M'的状态数不同，则二者必不等价。4、确定的自动机以及不确定的自动机都能正确地识别正规集。5、对任意一个右线性文法6、对任意一个右线性文法7、对任何正规表达式8、对任何正规表达式e,e,解答1、2、3、错4五、基本题G,都存在一个 NFA M,满足L(G尸L(M)。G,都存在一个 DFA M 满足L(G尸L(M)。 都存在一个 NFA M满足L(G)=L(e)。 都存在一个 DFA M满足L(G)=L(e)。、5、6、7、8、正确() ( ) ) ) )1、设 M= (x,y, a,b, f,x,y f

23、(x,a ) f (y,a )为一非确定的有限自动机，其中定义如下:=x,y=4f (x,b) =yf (y,b ) = x,y试构造相应的确定有限自动机解答：对照自动机的定义M=(S, N,f,S o,Z),由f的定义可知f(x,a)、f(y,b)均为多值函数，所以是一非确定有限自动机，先画出NFA M相应的状态图，如图 3-6-2所示。II aI bxx,yyy一x,yx,yx,yx,y将转换矩阵中的所有子集重新命名而形成表3-6-4所示的状态转换矩阵。表3-6-4 状态转换矩阵ab0211一2222即得到M, *,10, 如f,0, 1，2),其状态转换图如图3-6-5所示。1,2:令状

24、态1代表1,2,即把原来到达2的弧都导向 所示化简DFA M'。ab图3-6-6 化简后的DFA M'2、对给定正规式 b* (d|ad ) ( b|ab ) +,构造其 NFA M; 解答：首先用 A+=AA改造正规式得：b*(d|ad)(b|ab)(b|ab) 3-6-7所示。 *b(d|ad)(b|ab)(baqb* C)(d|ad.1 2)(b|ab.( 甘d 口 hwQt：4c1XI£j； adab& MEL aMfe1,并删除状态2。最后，得到如图3-6-6;其次，构造该正规式的 NFA M,如图01-b二 M d X 0a将图3-6-5的DFA

25、M最小化。首先，将M'的状态分成终态组1 , 2与非终态组0;其次，考察1,2。由于1,2a=1,2b=2? 1,2,所以不再将其划分了，也即整个划分只有两组0,图 3-6-7 的 NFA M1、构造下面文法的LL (1)分析表。A TLT一 int | realL 一 id RRH , id R |£解答：LL (1)分析表见表4-3-1分析 虽然这个文法很简单，我们还是从求开始符号集合和后继符号集合开始。FIRST (D) =FIRST (T) =int, real FOLLOW D =FOLLOW L) =#FIRST (L) =idFOLLOW T =idFIRST

26、( R = , , s FOLLOW R) =#有了上面每个非终结符的FIRST集合，填分析表时要计算一个产生式右部”的FIRST (a)就不是件难事了。填表时唯一要小心的时，£ 是产生式 Ae右部的一个开始符号，而 # FOLLOW R)中，所 以 -e填在输入符号#的栏目中。表4-3-1 LL (1)分析表非终结符输入符号intrealid#DA TLA TLTT- intT一 realLLfid RRRf ,id RR- £2、 下面文法GS是否为LL (1)文法？说明理由。S 一 A B | P Q xA 一 x y B 一 b cP 一 d P | eQ 一 a

27、Q | e解答：该文法不是LL (1)文法，见下面分析中的说明。分析只有三个非终结符有两个选择。1 、P的两个右部d P和e的开始符号肯定不相交。2、Q的两个右部a Q和e的开始符号肯定不相交。3、对S来说，由于 x C FIRST(A B),同时也有 x C FIRST(P Q x)(因为P和Q都可能为空) 所以该文法不是 LL (1)文法。3、 设有以下文法：GS : Sf aAbDe|dA 一 BSD|e B f SAc| cD| £ D 一 Se| e(1)求出该文法的每一个非终结符U的FOLLOW!。(2)该文法是 LL(1)文法吗？(3)构造CS的LL (1)分析表。解答

28、： (1)求文法的每一个非终结符U的FOLLOW!的过程如下：因为：S是识别符号，且有 Z BSD BfSAc、Df Se,所以FOLLOW S)应包含 FIRST(D) U FIRST(Ac) U FIRST(e) U # =a,d Ua,d,c,e U e U # =a,c,d,e#又因为A-BSD和 Ae,所以 FOLLOW还包含 FOLLOW(A) 因为S- aAbDe和B-SAc,所以 FOLLOW A) =FIRST (bDe) U FIRST ( c) =b,c综合、得 FOLLOWS) =a,d,c,e,# U a,b,c,d,e,# 因为 A- BSQ 所以 FOLLOW (

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

30、DBSDBSDeBSac/ ecDSac/ eDSe/ e££Se/ e£4、 将文法GV改造成为LL(1)的。GV : " N|NEE一 V|V+EN一 i解答： 对文法GV提取公共左因子后得到文法：G ' V ： V- NA2 £ |EVBBf s |+ENR i求出文法 G V中每一个非终结符号的FIRST集：FIRST(V)=iFIRST(A)=,£ FIRST(E)=iFIRST(B尸+,£ FIRST(N)=i求出文法G V中每一个非终结符号的FOLLOW!:FOLLOW(V)=# U FIRST(B)

31、£ 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- s |E,有 FIRST(E) A FOLLOW(A)= n +,#=?对产生式B- e |+E ,有FIRST(+E) A FOLLOW(B尸+ A = ?而文法的其他产生式都只有一个不为£的右

32、部，所以文法G' V是LL(1)文法。5、已知文法：GA :A- aAa| £(1)该文法是LL (1)文法吗？为什么？(2)若采用LL (1)方法进行语法分析，如何得到该文法的LL (1)分析表？(3)若输入符号串“ aaaa”，请给出语法分析过程。解答：(1)因为产生式 A- aAa| £有空产生式右部，而 FOLLOW(A)=# U FIRST(a尸a, #造成 FIRST(A) n FOLLOW(A尸A,£ n a, # w?所以该文法不是 LL (1)文法。(2)若采用LL (1)方法进行语法分析，必须修改该文法。因该文法产生偶数(可以为0)个a

33、,所以得到文法G A :Z aaA| £此时对产生式 A- aaA| s , 有 FOLLOW(A尸# U FOLLOW(A)=#,因而 FIRST(A) n FOLLOW(A尸a,£ n #= ?所以文法G A是LL (1)文法，按LL (1)分析表构造算法构造该文法的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对符号串“ aaaa”的分析过程步骤分析栈输入串产生式/动作1#Aa a a a #Z a

34、aA2#A a aa a a a #匹配3#A aa a a #匹配4#Aa a #Z aaA5#A a aa a #匹配6#A aa#匹配7#A#Ar> £8#接受第七节习题设有义法GS为:Sf a|b|(A)ab()d#a?b?(?)?d#?5-7-1 ,并判断GS是否为算符优先文法。算符优先关系表2 SdA|S完成下列算符优先关系表，见表表 5-7-1(2)给出句型(SdSdS)的短语、简单短语、句柄、素短语和最左素短语。(3)给出输入串(adb) #的分析过程。(1)解答：(1)先求文法 G网的FIRSTVT集和LASTVT集：由 S-a|b|(A)得：FIRSTVT(

35、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 得：LASTVT(A)=d,又由 A - S 得：LASTVT(S) ? LASTVT(A),即 LASTVT(A)=d,a,b,)。构造优先关系表方法如下：对ab，或4aQb，有a? b;对aR,而 bC FIRSTVT(R),有 a? b;对Rt> -,而 aC FIRSTVT(R),有 a? b。由此得到：由 S一 (A)得：(？); 由

36、S一(A得：(？ FIRSTVT(A),即：(？ d,( ? a ,( ? b,( ?(;由 A一dA得：d? FIRSTVT(A), 即：d? d,d ? a,d ? b,d ?(; 由 Sf A)得，LASTVT(A)?),即：d? ),a ? ),b ? ),) ?);由 A-Sd得：LASTVT(S)? d,即：a ? d,b ? d,) ? d;此外，由 #S#W： #? #；由#? FIRSTVT(S)得：#? a,# ? b,# ?(;脂由 LASTVT(S)? #得：d? #,a ? #,b ? #,) ? #。最后得到算符优先关系表，见表5-7-2 。表5-7-2算符优先关系

37、表ab()d#a?b?(?)?d?#?由表5-7-2可以看出，任何两个终结符之间至少只满足？、？、？三种优先关系之一，故 GS为算符优先文法。（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)#用Sfa归约# (S

38、db)#移进# (Sdb)#移进# (Sdb)#用Sfb归约# (SdS)#用A-S归约# (SdA)#用SdA归约# (A)#移进# (A)#用S-( A)归约#S#分析成功第四节 习题一、单项选择题1、若a为终结符，则A-“ ap为 项目a. 归约b.移进c.接受d.待约2、若项目集Ik含有A-a ,则在状态k时，仅当面临的输入符号 aCFOLLOW(A时，才采取“A 一 a ”动作的一定是。文法 (0)文法 (1)文法 (1)文法3、就文法的描述能力来说，有 一。a. SLR (1) ? LR (0) b. LR (1) ? LR (0) c. SLR (1) ? LR (1) d.无二

39、义文法？ LR ( 1)4、在LR (0)的ACTION子表中，如果某一行中存在标记“ 门”的栏，则 。a.该行必定填满口b.该行未填满rjc.其他行也有口子表中也有rj5、一个 指明了在分析过程中的某时刻所能看到产生式多大一部分。a.活前缀b.前缀c.项目d.项目集解答：1 、Aa 称为归约项目，对文法开始符 S'的归约项目，如S' a 称为接受项目，A- a a 3(a为终结符)称为移进项目。在此选 b.2、当用产生式 A-a归约时，LR (0)无论面临什么输入符号都进行归约；SLR (1)则仅当面临的输入符号aCFOLLOW(A时进行归约；LR (1)则当在把 “归约为A

40、的规范句型的前缀 3 Aa前 提下，当“后跟终结符a时，才进行归约；因此选 do3、由于 LR (0) ? SLR (1) ? LR (1) ?无二义文法，故选 c。4、选 a。5、选 Co 二、多项选择题1、一个LR分析器包括。a. 一个总控程序 b. 一个项目集c. 一个活前缀d. 一张分析表 e. 一个分析栈2、LR分析器核心部分是一张分析表，该表包括等子表。分析 b.优先关系3、每一项ACTIONS a所规定的动作包括。a.移进 b.比襄 c.接受 d.归约 e.报错4、对LR分析表的构造，有可能存在 动作冲突。a.移进 b.归约c.移进/归约d.移进/移进e.归约/归约5、就文法的描

41、述能力来说，有 。a. SLR (1) ? LR (1) b. LR (1) ? SLR (1)c. LR (0) ? LR (1)d. LR (1) ?无二义文法 e. SLR (1) ?无二义文法6、对LR分析器来说，存在 等分析表的构造方法。(0)(1)(0)(1)7、自上而下的语法分析方法有 。a.算符优先分析法(1)分析法(1)分析法(0)分析法(1)分析法解答：1 、一个LR分析器包括一个总控程序和一张分析表，选 a、d。2、选 c、 e。3、选 a、c、d、e。4、在LR分析表的构造中有可能存在“移进”/“归约”和“归约” / “归约”冲突；故选 c、e。5、选 a、b、c、d、

42、e。6、选 a、b、c、e。7、选 a、c、d、e。三、填空题1、对于一个文法，如果能够构造。使得它的均是唯一确定的，则称该文法为LR文法。2、字的前缀是指该字的 。3、活前缀是指 的一个前缀，这种前缀不含 之后的任何符号。4、在LR分析过程中，只要 的已扫描部分保持可归约成一个 ,则扫描过的部分正确。5、将识别 的NFA确定化，使其成为以 为状态的DFA这个DFA就是建立 的基础。6、A-> a ,称为项目；对文法开始符 S' -> a 为项目；若a为终结符，则称A- a , a 3为 项目；若B为诬结符，则称 A-a ap为 而：7 、LR (0)分析法的名字中“ L”

43、表示, "R'表示, “0”表示 解答：1 、一张分析表每个入口2、任意首部3、规范句型句柄4、输入串 活前缀5、活前缀 项目集合LR分析算法6、归约接受移进待约7、自左至右分析采用最右推导的逆过程即最左归约向右查看0个字符四、综合题1、对于文法 GS : SfAS|bAf SA|a(1)列出所有LR (0)项目(2)列出构成文法 LR (0)项目集规范族。解答：首先将文法G拓广为GS':S' 一 S项目是：5、S一 AS ,6、Sf b9、2 S - A10、A-SA-Sf AS|b Z SA|a (1)文法 GS'的 LR (0)1、S'

44、一 - S2、S' 一 S 3、S一 , AS7、S一 b ,11、Af a8、Af SA2、列出构成文法 LR (0)项目集规范族。用e -CLOSURE闭包)办法构造文法 G'白L LR (0)项目集规范族如下:0:1、S' 一 - SI 3： 9、Af S - A16： 12、Aa3、Sf AS8、Af SA17： 7、Sf b -8、Af SA3、Sf AS11、A一 a6、S 一 - b6、Sf , b11、2 . a1:2、S' -S-I 4： 10、ZSA-9、Af S - A4、SfA - S8、Z - SA3、Sf - AS11、A一 a6、S

45、 一 - b3、Sf AS8、Af SA6、Sf b11、Z . a2：4、Sf A- SI 5 :5、S-AS-3、Sf AS9、Af S - A6、Sf b8、Af SA8、Af SA11、Z . a11 、A一 a3、Sf - AS6、S 一 , b注意：Il中的S' -S 和A一 SA是由状态I。中的1和3读入一个S字符后得到的下一个项目；， 而I4中的A- SA和A- A- S则是由I3中的9和3读入一个A字符后得到的下一个项目；、中的S 一AS和A- S- A 则是由I4中的4和8读入一个S字符后得到的下一个项目。状态全体构成了文法 G'白L LR (0)规范族。第

46、八节 习题、单项选择题d.等价变换规则d.程序变量+b+c/d1、中间代码生成所依据的是。a.语法规则b.词法规则c.语义规则2、四元式之间的联系是通过 实现的。a.指示器b.临时变量c.符号表3、后缀式ab+cd+/可用表达式 来表示。+b/c+db.(a+b)/(c+d)+b/(c+d)4、表达式 3 AV B) A ( CV D)的逆波兰表示为 。a. r ABV A CDMb. A n BV CDV Ac. AB Vr CDV Ad. A r BV A CDV5、中间代码的树型表示A B C D所对应的表达式为+B+C+D +(B+C)+Dc.(A+B)+C+Dd.(A+B)+(C+D

47、)6、四元式表示法的优点为 。a.不便于优化处理，但便于表的更动c.便于优化处理，也便于表的更动7、终结符具有 属性。a.传递b.继承解答1 、选 c。b.不便于优化处理，但节省存储空间 d.便于表的更动，也节省存储空间c.抽象d.综合2、四元式之间的联系是通过临时变量实现的，故选bo3、选 bo4、选 bo5、选d6、四元式表示法的优点与间接三元式相同，故选c。7、选 do、多顶选择题1、中间代码主要有a.四元式d.后缀式e.间接三元式2、下面中间代码形式中，能正确表示算术表达式a+b+c的有a. ab+c+b. abc+ c.+/ + c / a b+a + /.a+b+c3、在下面的a.

48、赋值语句语法制导翻译中，采用拉链b c-回填技术。b. goto语句 c .条件语句4、下列中间代码形式有益于优化处理。a.三元式b.四元式 c.间接三元式d.逆波兰表示法e.树形表示法5、在编译程序中安排中间代码生成的目的是。b.利于目标代码的优化d.利于目标代码的移植能正确表示算术表达式a+b*c。题)a.便于进行存储空间的组织c.利于编译程序的移植e.利于提高目标代码的质量a. ab+c*b. abc*+6、下面的中间代码形式中， 7、三地址代码语句具体实现通常有 表示方法。a.逆波兰表示b.三元式 c.间接三元式d.树形表示e.四元式解答1、选 a、c、d、e。2、b、d的中间代码不能

49、正确表示 a+b+c,而e不是中间代码：故选 a、c。3、凡涉及到跳转的语句都需要采用拉链一一回填技术，故选 b、c、do4、选 b、c5、选 b、do6、选 b、 e。7、选 b、c、e。三、填空题1、中间代码有 等形式，生成中间代码主要是为了使 。2、语法制导翻译既可以用来产生 代码，也可以用来产生 指令，甚至可用来对输 入串进行。3、当源程序中的标号出现“先引用后定义”时，中间代码的转移地址须持 时才能确定, 因而要进行。4、文法符号的属性有两种，一种称为 ,另一种称为 。5、后缀式abc-/所代表的表达式是 ,表达式(a-b)*c 可用后缀式 表示。6、用一张 辅以 的办法来表示中间代

50、码，这种表示法称为间接三元式。解答1、逆波兰记号、树形表示、三元式、四元式目标代码的优化容易实现2、中间3、标号定义4、继承属性5、a/(b-c)6、间接码表 四、综合题目标解释执行回填综合属性ab-c*三兀式表1、给出下列表达式的逆波兰表示(后缀式) a*(-b+c)(A V B) A (CVrDA E)2、写出算术表达式： A+B*(C-D)+E/(C-D) TN的四元式序列；三元式序列；间接三元式序列 解答1、 abc+*; AB V CD EA V A2、表达式的四元式序列：(1) (-,C,D,T i) (*,B,T i,T2) (3) (+,A,T 2,T3) (4) (-,C,D,T 4) (5) ( T ,T4,N,T 5)(/，E，(4)(6) (/,E,T5,T6)(+,(3),(5)第三节一、单项选择题1、编译程序使用