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

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

2、则d.词法规则7、 词法分析器的输入是 。a.单词符号串b.源程序c.语法单位d.目标程序8、 中间代码生成时所遵循的是-。a .语法规则c .语义规则b.词法规则d.等价变换规则9、 编译程序是对。a 汇编程序的翻译c .机器语言的执行10、语法分析应遵循a 语义规则c 构词规则b.高级语言程序的解释执行d.高级语言的翻译b.语法规则d.等价变换规则则，并且语义规则可以定义一个程序的意义。因此选a。二、多项选择题1、 编译程序各阶段的工作都涉及到 。a .语法分析b.表格管理c.出错处理d .语义分析e .词法分析2、编译程序工作时，通常有 阶段。a .词法分析b.语法分析c.中间代码生成d

3、 .语义检查e .目标代码生成三、填空题1 、解释程序和编译程序的区别在于 。2、 编译过程通常可分为 5个阶段，分别是、语法分析、代码优化和目标代码生成。3、 编译程序工作过程中，第一段输入是 ，最后阶段的输出为 程序。4、 编译程序是指将 程序翻译成 程序的程序。单选解答1、 将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选b。2、 构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选d。3、 对编译而言，变量既持有左值又持有右值，故选c。4、 编译程序打交道最多的就是各种表格，因此选do5、 目标代码包括汇编指令代码、可重定位指令代码和绝对指令代码3种，因此不是

4、目标代码 的只能选do6、词法分析遵循的是构词规则，语法分析遵循的是语法规则，中间代码生成遵循的是语义规7、b 8c 9、 d 10 、 c多选解答1. b、c 2. a 、b、c、e填空解答4、源程序 目是否生成目标程序2、词法分析中间代码生成3、源程序 目标代码生成标语言第二章、单项选择题1、文法 G StxSx|y所识别的语言是a. xyxb. (xyx)*c. xn n,yx (n > 0)d. x*yx*2、文法G描述的语言L(G)是指a. L(G)= a |S? a c. L(G)= a |S?* a ,a Vt*a (VtU Vn*)b. L(G)= a |S ?d. L(

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

6、0步或多步推导产生的文法符号序列是 a.短语 b.句柄c. 句型 d.句子7、文法 G Et E+T|TTt T*P|PPt (E)|I则句型P+T+i的句柄和最左素短语为 。+T 和 i b. P 和 P+T c. i 和 P+T+i 和 T8 、设文法为：St SA|A9、文法GStb| A (T)Tt T,S|SAt a|b则对句子aba,卜面是规范推导。a.sSAsaaAAAaAAabAabab.ssasaaAAAAAaAbaabac.ssasaaSAaSbaAbaabad.ssaSaSAaSbaAbaaba则 FIRSTVT(T)10、a. 011、a. b, A ,(b. b, A

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

8、以用状态转换图表示2、对无二义性文法来说，一棵语法树往往代表了 a.多种推导过程b.多种最左推导过程c. 一种最左推导过程FHcS3、如果文法G存在一个句子，满足下列条件 之一时，则称该文法是二义文法。a. 该句子的最左推导与最右推导相同b. 该句子有两个不同的最左推导c. 该句子有两棵不同的最右推导d. 该句子有两棵不同的语法树e. 该句子的语法树只有一个4、有一文法G: St ABA t aAb| e它不产生下面集合。a.d.a. ac. ae. anbmcndmn,m >0 n m m .n,b c d |n,m >0nbncndn|n >0自下而上的语法分析中,句型b

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

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

11、bbbQ tbccQtcc（1）它是Chomsky哪一型文法（ 2）它生成的语言是什么3、按指定类型，给出语言的文法。L=aibj |j > i > 1的上下文无关文法。4、有文法 G： St aAcB|BdAt AaB|cBtbScA|b（ 1）试求句型 aAaBcbbdcc 和 aAcbBdcc 的句柄；（ 2）写出句子 acabcbbdcc 的最左推导过程。5、对于文法 GS ：S t（ l） |aS|a L t l, S|S（1）画出句型（S, （a）的语法树。（2）写出上述句型的所有短语、直接短语、句柄和素短语。6、考虑文法 GT ：TtT*F|FFt Ff P|PPt（

12、 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。d，如果有两个不同的是了左推导，则必然有二义性。故选a。6、选 c。7、 由图2-8-1的语法树和优先关系可以看出应选bo5、如果文法G无二义性，则最左推导是先生长右边的枝叶：对于E/|E + F/匕IE + T PIT iP#< + >+< i >#8、 规范推

13、导是最左推导，故选d。9、由 TtT,和 ( 得 FIRSTVT(T)=(, , );由 Tt S 得 FIRSTVT(S)? FIRSTVT(T)，而 FIRSTVT(S)=b, A ,(;即10、dFIRSTVT(T)=b, A ,(,;因此选c。13 、b 14 、b11、c12、b多选解答1 、 e、 a、c 2、a、c、e 3、b、c、d 4 、a、c5 、b、c 6、a、b、c、d、e填空解答1、空集终结符右2 、最左3、自上而上自下而上4、自上而上5、语法分析6 、移进接受7、4 2 型3型上下文无关语言正规语言下推自动机有限判断解答1、对 2、错 3、错 4、错 5、错 6、错

14、简答解答1 、句柄：一个句型的最左直接短语称为该句型的句柄。2、素短语：至少含有一个终结符的素短语，并且除它自身之外不再含任何更小的素短语。3、语法树：满足下面 4个条件的树称之为文法 GS的一棵语法树。 每一终结均有一标记，此标记为VnU Vt中的一个符号； 树的根结点以文法 GS的开始符S标记； 若一结点至少有一个直接后继，则此结点上的标记为M中的一个符号； 若一个以A为标记的结点有 K个直接后继，且按从左至右的顺序，这些结点的标记分别 为X,X2,Xk,贝U AXi,X2,Xk,必然是 G的一个产生式。4、 归约：我们称仏丫直接归约出a AB,仅当Ay 是一个产生式，且a、B(VnU V

15、t)* 归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。5、 推导：我们称a A B直接推出ayB, 即a A B ayB,仅当丫是一个产生式，且a、(VnU Vt)*。如果a 1 a 2 a n,则我们称这个序列是从a1至a 2的一个推导。若存在一个从a ia n的推导，则称a 1可推导出a n。推导是归约的逆过程。问答1解答一个上下文无关文法 G是一个四元式(Vt,Vn,S, P )，其中： Vt是一个非空有限集，它的每个元素称为终结符号； Vn是一个非空有限集，它的每个元素称为非终结符号，VtA Vn=； S是一个非终结符号，称为开始符号； P是一个

16、产生式集合(有限)，每个产生式的形式是 Pa,其中，P Vn, a (VtU Vn)*。开始符号S至少必须在某个产生式的左部出现一次。2解答(1) 由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部的符 号长度，所以文法 GS是Chomsky1型文法，即上下文有关文法。(2) 按产生式出现的顺序规定优先级由高到低(否则无法推出句子)，我们可以得到：S abQ abcS aSPQ aabQPQ aabPQQ aabbQQ aabbcQ aabbccS aSPQ aaSPQPQ aaabQPQPQ aaabPQQPQ aaabPQPQQ aaaPPQQQaaabbPqqq

17、aaabbQQQ aaabbbcQQ aaabbbccQ aaabbbccc于是得到文法 GS生成的语言L=anbncn|n >13【解答】(1)由L=ai bj |j > i > 1知，所求该语言对应的上下文无关文法首先应有St aSb型产生式，以保证b的个数不少于a的个数；其次，还需有 St Sb或StbS型的产生式，用以保证 b的个数多 于a的个数；也即所求上下文无关文法GS为：GS : St aSb|Sb|b4【解答】(1 )分别画出对应两句型的语法树，如图2-8-2所示(1)句型(S,(a)的语法树如图2-8-3 所示(2)由图2-8-3可知:(L)L，SIS (

18、L )IS短语:S、a、(a)、S,(a)、 直接短语：a、S； 句柄：S； 素短语：素短语可由图2-8-3中相邻终结符之间的优先关系求得，即;#<( <(<$) #因此素短语为a。6【解答】/1句柄：AaB Bda /I A zVW/ IA a B b S cAB d c图2-8-2 语法树(2) 句子acabcbbdcc的最左推导如下：S aAcB aAaBcB acaBcB acabcB acabcbScA acabcbBdcAacabcbbdcA acabcbbdcc5【解答】/1首先构造T*P f( T*F)的语法树如图2-8-4所示。由图2-8-4可知，T*Pf(

19、 T*F)是文法GT的一个句型。直接短语有两个，即 P和T*F ;句柄为P。第三章单项选择题1、 词法分析所依据的是_。a. 语义规则b.构词规则2、 词法分析器的输出结果是_。a.单词的种别编码c.单词的种别编码和自身值3、 正规式M和M等价是指 。a. M i和M2的状态数相等c. M i和M所识别的语言集相等c.语法规则d.等价变换规则b. 单词在符号表中的位置d.单词自身值b. M i和M的有向弧条数相等d. M i和M状态数和有向弧条数相等4、状态转换图(见图 3-6-1 )接受的字集为1a.以0开头的二进制数组成的集合b. 以0结尾的二进制数组成的集合c. 含奇数个0的二进制数组成

20、的集合d. 含偶数个0的二进制数组成的集合5、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，_。a.c.词法分析器应作为独立的一遍b.词法分析器作为子程序较好词法分析器分解为多个过程，由语法分析器选择使用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是的一个特例。2、 若二个正规式所表示的

21、 相同，则认为二者是等价的。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,都存在一个NFAM,满足L(G)=L(e)。()8、对任何正规表达式e，都存在一个

22、DFAM,满足L(G)=L(e)。()五、基本题1、设M=( x,y, a,b, f,x,y)为一非确定的有限自动机，其中f定义如下：f (x,a )= x,yf (x,b ) = yf (y,a )=0f (y,b ) = x,y试构造相应的确定有限自动机M 。2、对给定正规式 b* (d|ad ) (b|ab ) +，构造其 NFA M;单选解答1、b 2、c 3、c4、d 5、b多选解答 1、a、c、e 2、a、b、d填空解答1、NFA2、正规集3、DFA (NFA)所识别判断解答1、2、3、错4、5、6、7、8正确基本1解答：对照自动机的定义M=S,工,f,S 0,Z)，由f的定义可知

23、1：(x,a)、f(y,b)均为多值函数，所以是一非确定有限自动机，先画出NFA M相应的状态图，如图3-6-2所示。.用子集法构造状态转换矩阵表3-6-3所示。匚IIabI bbxx,yyy一x,yx,yx,yx,y将转换矩阵中的所有子集重新命名而形成表3-6-4所示的状态转换矩阵。21考察1,2。由于1,2a=1,2b=2? 1,2，所以不再将其划分了，也即整个划分只有两组0，1,2:令状态1代表1,2所示化简DFA M'。，即把原来到达.2的弧都导向1，并删除状态2。最后，得到如图3-6-6a,b2解答：首先用3-6-7所示。A+=aA改造正规式得：b (d|ad)(b|ab)(

24、b|ab) ;其次，构造该正规式的NFAM如图b*(d|ad)(b|ab)(b|23Yadab12££bbaa-a d仟g K Y”厂J£ 4£表3-6-4状态转换矩阵ab0211一2222即得到 M =(0,1,2,a,b,f,0,1,2)，其状态转换图如图3-6-5所示。将图3-6-5的DFA M最小化。首先，将M'的状态分成终态组1 , 2与非终态组0;其次,图 3-6-7 的 NFA M第四章1、构造下面文法的 LL( 1)分析表。“ TLTt int | realLt i d RRt , id R |£2、下面文法GS是否为L

25、L (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|dA tBSD|eB tSAc| cD| eD tSe| e(1) 求出该文法的每一个非终结符U的FOLLOW集。(2) 该文法是LL( 1)文法吗(3) 构造CS的LL( 1 )分析表。4、将文法GV改造成为LL(1)的。GV：VtN|NEEtV|V+ENti5、已知文法：GA:At aAa| &(1 )该文法是LL (1)文法吗为什么(2) 若采用LL (1)方法进行语法分析，如何得到该文法的LL (1)分析表(3

26、) 若输入符号串“ aaaa”，请给出语法分析过程。1解答：LL (1)分析表见表4-3-1分析 虽然这个文法很简单，我们还是从求开始符号集合和后继符号集合开始。FOLLOW D =FOLLOV( L) =#FIRST ( D) =FIRST (T) =int, realFIRST ( L) =idFOLLOW T) =idFIRST ( R) = , , £ FOLLOW/ R) =#有了上面每个非终结符的FIRST集合，填分析表时要计算一个产生式右部a的FIRST (a )就不是件难事了。填表时唯一要小心的时，&是产生式FHs右部的一个开始符号，而 #在 FOLLO( R

27、)中，所 以FTs填在输入符号#的栏目中。表4-3-1 LL (1)分析表非终结符输入符号intrealid#Ddt tldt tlTTt intTt realLLt id RRRt ,id RRt&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的FO

28、LLOW的过程如下：因为： S是识别符号，且有 2 BSDSAc、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# 又因为At BSD和D£,所以 FOLLOV中还包含 FOLLOW(A) 因为St aAbDe和Bt SAc,所以FOLLOW A) =FIRST (bDe)U FIRST ( c) =b,c综合、得 FOLLO(S) =a,d,c,e,# U a,b,c,d,e,#因为 At BSD 所以 FOLLOW ( B) =FIRST (SD) =a,d因为

29、 St aAbDe | d、At BSD| e 和 Bt SAc | cD，所以FOLLOW D) =FIRST (e)U FOLLO( A)U FOLLOV/ B)=e U b,c U a,d=a,b,c,d,e(2) GS不是 LL ( 1)文法。因为产生式Bt SAc|cD| £中FIRST(SAc)n FOLLO( B) =a,d工?(3) 构造GS的LL (1)分析表。按照LL (1)分析表的构造算法构造方法GS的LL (1)分析表如表4-3-2所示。表4-3-2 GS 的LL (1)分析表abcde#saAbDedABSDBSDBSDeBSac/ ecDSac/ eDSe

30、/ eeeSe/ ee4解答： 对文法GV提取公共左因子后得到文法:V : Vt NAAf |Ei VBBf |+ENR i求出文法G V中每一个非终结符号的FIRST集：FIRST(V)=iFIRST(A)=,£ FIRST(E)=iFIRST(B)=+,£ FIRST(N)=i求出文法G V中每一个非终结符号的FOLLOWI:FOLLOW(V)=# U FIRST(B) £ U FOLLOW(E)=#,+,FOLLOW(A)= FOLLOW(V)=+,#FOLLOW(E)= FIRST() £ U FOLLOW(B)= FIRST() £

31、U FOLLOW(E)=FOLLOW(B)= FOLLOW(E)= FOLLOW(N)= FIRST(A) £ U FOLLOW(V)=,+,#可以看到，对文法 G V的产生式Ar£ |E，有FIRST(E) A FOLLOW(A)= n +,#=?对产生式Br£ |+e，有FIRST(+E) n FOLLOW(B)=+n =?而文法的其他产生式都只有一个不为&的右部，所以文法G V是LL(1)文法。5解答：(1)因为产生式 Ar aAa| £有空产生式右部，而FOLLOW(A)=# U FIRST(a)=a, #造成 FIRST(A) A FO

32、LLOW(A)=A, £ A a, #工?所以该文法不是 LL( 1 )文法。(2)若采用LL (1)方法进行语法分析，必须修改该文法。因该文法产生偶数(可以为0 )个a，所以得到文法G A :Ar aaA| £此时对产生式 Ar aaA| £, 有 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#AAt aa

33、AAt£(3)若采用LL(1)方法进行语法分析，对符号串“aaaa”的分析过程如表 4-3-4所示。表4-3-4对符号串“ aaaa”的分析过程步骤分析栈输入串产生式/动作1#Aa a a a #At aaA2#A a aa a a a #匹配3#A aa a a #匹配4#Aa a #At aaA5#A a aa a #匹配6#A aa#匹配7#A#At£8#接受第五章1. 设有文法GS为：St a|b|(A)A SdA|S5-7-1 ,并判断GS是否为算符优先文法。算符优先关系表(1) 完成下列算符优先关系表，见表表 5-7-1ab()d#a?b?(?)?d#?(2)

34、给出句型(SdSdS的短语、简单短语、句柄、素短语和最左素短语。(3) 给出输入串(adb) #的分析过程。解答：(1)先求文法 GS的FIRSTVT集和LASTVT集：由 Sta|b|(A)得：FIRSTVT(S)=a,b,();由 At Sd 得：FIRSTVT(A)=d;又由 At S 得：FIRSTVT(S) ? FIRSTVT(A),即 FIRSTVT(A)=d,a,b,(;由 St a|b|(A)得；LASTVT(S)=a,b,;由 A t dA 得：LASTVT(A)=d,又由 A t S 得：LASTVT(S) ? LASTVT(A),即 LASTVT(A)=d,a,b,)。构

35、造优先关系表方法如下： 对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,( ?(;由 AtdA得：d? FIRSTVT(A), 即：d? d,d ? a,d ? b,d ?(; 由 St A)得，LASTVT(A)?)，即：d? ),a ? ),b ? ),) ?);由 At Sd 得：LASTVT(S)? d，即：a ? d,b ? d,) ? d;此外，由#

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

37、S句柄（即最左直接短语）：S素短语：SdS,它同时也是该句型的最左素短语。（3）输入串（adb） #的分析过程见表 5-7-4表5-7-4 输入串（adb）#的分析过程符号栈输入串说明#(adb)#移进#（adb)#移进#( adb)#用Sa归约#( Sdb)#移进#( Sdb)#移进#( Sdb)#用Sb归约#( SdS)#用At S归约#( SdA)#用At SdA归约# (A)#移进# (A)#用Sf( A)归约#S#分析成功第六章一、单项选择题1、若a为终结符，则Aaa 3为项目a. 归约b.移进c.接受d.待约2、 若项目集Ik含有Aa，则在状态k时，仅当面临的输入符号a FOLLO

38、W(A时，才采取“ Afa ”动作的一定是。文法(0)文法 (1)文法 (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 的栏，贝U 。a. 该行必定填满rjb.该行未填满rjc.其他行也有rj子表中也有rj5、 一个 指明了在分析过程中的某时刻所能看到产生式多大一部分。a.活前缀b.前缀c.项目d.项目集、多项选择题1、一个LR分析器包括。a.一个总控程序b. 一个项目集c. 一个

39、活前缀d. 一张分析表e. 一个分析栈2、LR分析器核心部分是一张分析表，该表包括 等子表。(1)分析b.优先关系3、每一项ACTIONS, a所规定的动作包括a.移进b. 比较c. 接受d. 归约e.报错4、对LR分析表的构造，有可能存在动作冲突。a.移进b.归约c.移进/归约d.移进/移进e.归约/归约d. LR (1) ?无二义文法e. SLR (1) ?无二义文法5、就文法的描述能力来说，有a. SLR (1) ? LR (1)b. LR ( 1) ? SLR( 1)c. LR ( 0) ? LR (1)6、对LR分析器来说，存在 _等分析表的构造方法。(0)(1) ( 0)(1)7、

40、 自上而下的语法分析方法有 。a.算符优先分析法(1)分析法(1)分析法(0)分析法(1)分析法三、填空题1、 对于一个文法，如果能够构造 _。使得它的 _均是唯一确定的，则称该文法为LR文法。2、 字的前缀是指该字的 。3、 活前缀是指 的一个前缀，这种前缀不含 之后的任何符号。4、 在LR分析过程中，只要 的已扫描部分保持可归约成一个 ，则扫描过的部分正确。5、 将识别 的NFA确定化，使其成为以 为状态的DFA这个DFA就是建立 的基础。6、 Aa称为项目；对文法开始符 S'fa为项目；若a为终结符，则称Aaa B为项目；若B为非终结符，则称 Aaa 3为项目。7、LR ( 0)

41、分析法的名字中“ L”表示, “ R”表示, “ 0”表示。四、综合题1、对于文法 GS : S t AS|bAt SA|a(1) 列出所有LR ( 0)项目(2) 列出构成文法 LR ( 0)项目集规范族。单项解答：1 、At%称为归约项目，对文法开始符 S'的归约项目，如S't%称为接受项目，ATaa3 (a为终结符)称为移进项目。在此选b.2、 当用产生式 ATa归约时，LR ( 0 )无论面临什么输入符号都进行归约；SLR( 1)则仅当面 临的输入符号a FOLLOW(A时进行归约；LR ( 1)则当在把 a归约为A的规范句型的前缀 3 Aa前 提下，当a后跟终结符a时

42、，才进行归约；因此选 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 分析算法6、归约接受 移进 待约7、自左至右分析采用最右推导的逆过程即

43、最左归约 向右查看 0 个字符综合解答：首先将文法G拓广为GS':S't SSt AS|b3 SA|a(1)文法GS'的LR (0)项目是:1、s5、St AS *9、At s A2、S't S 6、St. b10、At SA-3、AS7、St b 11、At. a4、St A S8、At. SA12、At a 2、列出构成文法 LR( 0)项目集规范族。用&-CLOSURE闭包)办法构造文法G'的 LR (0)项目集规范族如下:I 0:1、S't. sI 3 :9、At S AI 6: 12、 At a3、St as8、At. SA17

44、: 7、St b 8、At SA3、St. AS11 、a6、St. b6、St b11、Ar aI 1:2、S't S-I 4 :10、At SA-9、At S A4、St A S8、At SA3、St. as11、At. a6、St. b3、St. AS8、At. SA6、St. b11、Ar aI 2:4、St A SI 5 :5、St AS 3、St as9、At S A8 、SA11、a11 、a3、AS6、S» b注意：I1中的S't S和AtSA是由状态Io中的1和3读入一个S字符后得到的下一个项目；， 而丨4中的At SA和At A- S则是由I 3中

45、的9和3读入一个A字符后得到的下一个项目；丨5中的 AS -和At S- A 则是由I 4中的4和8读入一个S字符后得到的下一个项目。状态全体构成了文法 G的LR (0)规范族。第七章、单项选择题1、中间代码生成所依据的是 _c.语义规则d.等价变换规则a. 语法规则b.词法规则2、 四元式之间的联系是通过_实现的。a.指示器b.临时变量c.符号表d.程序变量3、后缀式ab+cd+/可用表达式 来表示。+b/c+db.(a+b)/(c+d)+b/(c+d)+b+c/d4、 表达式鬥 AV B)A( CV D)的逆波兰表示为 。a. n ABVA CDVb. A n BV CDVAc. AB V

46、n CDVAd. A n BVA CDV4+1皂一f5、 中间代码的树型表示A B C D 所对应的表达式为。7、终结符具有属性。a.传递b.继承、多顶选择题1、中间代码主要有。a.四兀式b .二兀式+B+C+D +(B+C)+D6、四元式表示法的优点为a.不便于优化处理，但便于表的更动c.便于优化处理，也便于表的更动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+c.+ c+d 八a

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

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