编译原理期末复习题含答案

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

2、法规则d.词法规则7、词法分析器的输入是 a.单词符号串C.语法单位8、中间代码生成时所遵循的是a.语法规则C.语义规则9、编译程序是对a.汇编程序的翻译C.机器语言的执行10、语法分析应遵循.a.语义规则C.构词规则解答1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选3、对编译而言，变量既持有左值又持有右值，故选4、编译程序打交道最多的就是各种表格，因此选b.源程序d.目标程序 Ob.词法规则d.等价变换规则b.高级语言程序的解释执行d.高级语言的翻译b.语法规则d.等价变换规则boCo do5、 目标代码

3、包括汇编指令代码、可重定位指令代码和绝对指令代码3种，因此不是目标代码的只能选d o6、 词法分析遵循的是构词规则， 语法分析遵循的是语法规则， 中间代码生成遵循的是语义规则， 并且语义规则可以定义一个程序的意义。因此选a。7、b 8、C9、d10、C9c.出错处理c中间代码生成二、多项选择题1、编译程序各阶段的工作都涉及到 a.语法分析b .表格管理d.语义分析e.词法分析2、 编译程序工作时，通常有 阶段。a.词法分析b 语法分析d.语义检查e. 目标代码生成解答1. b、c2. a、b、c、e三、填空题1、解释程序和编译程序的区别在于 2、编译过程通常可分为 5个阶段，分别是3、 编译程

4、序工作过程中，第一段输入是_4、 编译程序是指将程序翻译成 解答是否生成目标程序2、词法分析中间代码生成 3、源程序 目标代码生成标语言_、语法分析，最后阶段的输出为程序的程序。、代码优化和目标代码生成。程序。4、源程序模拟习题2一、单项选择题1、 文法 G: St xSx|y所识别的语言是 oa. xyxb. (xyx)* c. x yx (n > 0)2、文法G描述的语言L(G)是指oa. L(G)= a |S? a, ac. L(G)= a |S? a ,a3、有限状态自动机能识别a.上下文无关文法C.正规文法4、设G为算符优先文法，d. x*yx*a |前 a , a Vt*a

5、|S? a , a (VtU Vn*) Vt*b. L(G)= (VtU Vn*) d. L(G)= ob.上下文有关文法d.短语文法G的任意终结符对a、b有以下关系成立b.若 f(a)<g(b)，贝U a<bd. ab 一定成立aa.若 f(a)>g(b)，则 a>bc. ab都不一定成立5、如果文法G是无二义的，则它的任何句子a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同6、 由文法的开始符经 0步或多步推导产生的文法符号序列是a.短语b

6、.句柄c.句型 d.句子7、文法 G : Et E+T|TTt T*P|P Pt (E)|I则句型P+T+i的句柄和最左素短语为 oa.P+T 和 i b. P 和 P+T c. i 和 P+T+i d.P 和 T8、设文法为：St SA|AA t a|b则对句子aba,下面是规范推导。a. SA= SAA = AAA = aAA=abab. S= SA= SAA = AAA 二 AAa = Aba= abac. S= SA= SAA = SAa= Sbu Aba= abad. S=SA二 Sa=SAa= Sbu Aba二 aba9、文法 G: St b|A (T)T t T,S|S则 FIR

7、STVT(T) oa. b, A ,(b. b, A ,)10、 产生正规语言的文法为 oa. 0型b. 1型11、 采用自上而下分析，必须 oa.消除左递归b.消除右递归12、 在规范归约中，用 来刻画可归约串。a.直接短语b.句柄13、有文法 G: EtE*T|TT t T+i|i句子1+2*8+6按该文法G归约，其值为 oa. 23 B. 42 c. 30 d. 1714、 规范归约指oa.最左推导的逆过程c.规范推导解答1、选2、选3、选c. 2型c.消除回溯c.最左素短语d.b, A ,), d. 3型d.提取公共左因子d.素短语b.最右推导的逆过程 d.最左归约的逆过程Coa。Co

8、4、 虽然a与b没有优先关系，但构造优先函数后，a与b就一定存在优先关系了。所以，由f(a)>g)(b)或f(a)<g(b)并不能判定原来的a与b之间是否存在优先关系：故选5、如果文法G无二义性，则最左推导是先生长右边的枝叶：对于 推导，则必然有二义性。故选Cod,如果有两个不同的是了左a。6、7、选Co由图2-8-1的语法树和优先关系可以看出应选8、9、EFEI|T#< + >+<i >#图2-8-1句型P+T+I的语法及优先关系规范推导是最左推导，故选d O由 TtT,和 Tt( 得 FIRSTVT(T)=(, 由 T t S 得 FIRSTVT(S)

9、? FIRSTVT(T)，而FIRSTVT(T)=b, A ,(, ;11、 c 12、 b13、 b因此选)；FIRSTVT(S)=b,CoA ,(；即10、d二、多项选择题1、 下面哪些说法是错误的 Oa.有向图是一个状态转换图C.有向图是一个DFA14、bb.状态转换图是一个有向图 d.DFA可以用状态转换图表示2、对无二义性文法来说，一棵语法树往往代表了a.多种推导过程b.多种最左推导过程d.仅一种推导过程e.种最左推导过程3、如果文法G存在一个句子，满足下列条件 _a. 该句子的最左推导与最右推导相同b. 该句子有两个不同的最左推导C.该句子有两棵不同的最右推导d. 该句子有两棵不同

10、的语法树e. 该句子的语法树只有一个4、有一文法G : St ABA t aAb| £Bt cBd| £它不产生下面集合。,n. m n .m,、a. a b c d |n,m0c. anbmcmdn| n,m0.n n n n、e. a b c d |n> 05、自下而上的语法分析中，应从句型b.句子文法的开始符e.句柄对正规文法描述的语言，以下a.0型文法b.1型文法_ OC. 一种最左推导过程.之一时，则称该文法是二义文法。.,n. n m . m,b. abed |n,m>0d. anbncmdm|n,m0.d.、.开始分析。C.以单词为单位的程序解答1

11、、三、填空题.有能力描述它。 C.上下文无关文法d.右线性文法e.左线性文法e、a、c2、a、c、e3、b、c、d4、a、c5、b、c 6、a、b、c、d、 e1、文法中的终结符和非终结符的交集是是，它一定只出现在产生式的 部。2、 最左推导是指每次都对句型中白非终结符进行扩展。3、 在语法分析中，最常见的两种方法一定是 分析法，另4、 采用 语法分析时，必须消除文法的左递归。5、 树代表推导过程， 树代表归约过程。6、 自下而上分析法采用 、归约、错误处理、 等四种操作。7、 Chomsky把文法分为 种类型，编译器构造中采用 和_生和语言，并分 和自动机识别所产生的语言。解空集终结符 右2

12、、最左3、自上而上4、自上而上5、语法6、移进7、42四、判断题自下而上。词法分析器交给语法分析器的文法符号一定分析接受型 3型上下文无关语言正规语言1、文法.StaS|bR|£描述的语言是(a|bc)*gc S2、在自下而上的语法分析中，语法树与分析树一定相同。3、二义文法不是上下文无关文法。4、语法分析时必须先消除文法中的左递归。5、规范归约和规范推导是互逆的两个过程。6、一个文法所有句型的集合形成该文法所能接受的语言。解答 1、对2、错3、错 4、错 5、错 6、错五、简答题1、句柄解答2、素短语3、语法树4、归约分析法。文法，它们分别产下推自动机有限()5、推导1、句柄：一个

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

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

15、限集，它的每个元素称为非终结符号， S是一个非终结符号，称为开始符号； P是一个产生式集合(有限)，每个产生式的形式是 Pt a，其中，P Vn , a (VtU Vn)*。开始符号S至少必须在某个产生式的左部出现一次。2、文法 GS:St aSP Q|abQQP PQbPT bb bQT bc cQt cc(1) 它是Chomsky哪一型文法？(2) 它生成的语言是什么？解答(1) 由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部的符 号长度，所以文法 GS是Chomskyl型文法，即上下文有关文法。，我们可以得到:(2) 按产生式出现的顺序规定优先级由高到低(否则

16、无法推出句子)abjj abc匚 aSPQiJ aabQ PJ aab PQJ aabbQg aabbcg aabbcc匚 aSPQ aaSPQPQ;； aaabQPQPQ;； aaabPQQPQ> aaabPQPQ aaaPPQQQz； aaabb Pqqg aaabbQQ3 aaabbbcQfe aaabbbccQ;； aaabbbccc于是得到文法 GS生成的语言L=a nbncn|nA 13、按指定类型，给出语言的文法。L=a ibj|j > i A 1的上下文无关文法。【解答】Sf aSb型产生式，以 用以保证 b的个数多于GS为：GS : Sf aSb|Sb|b(1)由

17、L=aibj|j > i A 1知，所求该语言对应的上下文无关文法首先应有 保证b的个数不少于a的个数；其次，还需有 Sf Sb或Sf bS型的产生式, a的个数；也即所求上下文无关文法4、有文法 G: SfaAcB|BdA f AaB|c Bf bScA|b(1) 试求句型 aAaBcbbdcc和aAcbBdcc的句柄;(2) 写出句子 acabcbbdcc的最左推导过程。2-8-2所示【解答】(1 )分别画出对应两句型的语法树，如图 句柄:AaBBdcB d11图2-8-3 句型(S, (a)的语法树(b)图2-8-2 语法树(2)句子acabcbbdcc的最左推导如下：S=aAcB

18、= aAaBcB= acaBcB= acabc姑 acabcbScfc； acabcbBdcA =acabcbbdcA= acabcbbdcc5、对于文法GS: Sf( L) |aS|aLf L, S|S(1)画出句型(S, (a)的语法树。(2)写出上述句型的所有短语、直接短语、句柄和素短语。 【解答】(1)句型(S, (a)的语法树如图2-8-3所示(Sa(2)由图2-8-3可知： 短语：S、a、(a)、S,(a)、(S,(a); 直接短语：a、S; 句柄：S; 素短语：素短语可由图2-8-3中相邻终结符之间的优先关系求得,即;# C (V, V (V a A) A) A#因此素短语为a。

19、6、考虑文法GT:T 7 T*F|FFt F t P|PP7( T) |i证明T*P t( T*F )是该文法的一个句型，并指出直接短语和句柄。【解答】首先构造T*P t( T*F )的语法树如图2-8-4所示。由图2-8-4可知，T*P t( T*F)是文法 直接短语有两个，即 P和T*F ;句柄为GT的一个句型。P。图 2-8-4句型T*P t (T*F )的语法树23模拟习题3、单项选择题1、 词法分析所依据的是_Oa.语义规则 b.构词规则2、词法分析器的输出结果是 _Oa.单词的种别编码c.单词的种别编码和自身值3、正规式M1和M2等价是指a. M1和M2的状态数相等c.语法规则d.

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

21、二、多项选择题1、在词法分析中，a.基本字d.逆波兰式2、令刀=a,b.b(abyd. (ba) b解答 1、a、c、e三、填空题能识别出Ob.四元式e.常数，则刀上所有以b开头，后跟若干个b. b(ab)+c.(ba)*be. b(a|b)a、b、dc.运算符ab的字的全体对应的正规式为2、1、确定有限自动机2、若二个正规式所表示的3、一个字集是正规的，当且仅当它可由解答 1、NFA2、正规集四、判断题1、一个有限状态自动机中，有且仅有一个唯一终态。2、设r和s分别是正规式，则有 L (r|s) =L(r)|L(s) o3、自动机M和M的状态数不同，则二者必不等价。4、确定的自动机以及不确定

22、的自动机都能正确地识别正规集。5、对任意一个右线性文法、对任意一个右线性文法7、对任何正规表达式8、对任何正规表达式 解答五、基本题1、设M =( x,y, a,b, f,x,y)为一非确定的有限自动机，其中f定义如下:f (x,b)= y f (y,b)= x,y1、NFADFA是的一个特例。.相同，则认为二者是等价的。所 O3、DFA (NFA)所识别e,e,G,都存在一个NFA M , G,都存在一个DFA M , 都存在一个NFA M，满足 都存在一个DFA M，满足满足 L(G)=L(M) O 满足 L(G)=L(M) O L(G)=L(e) O L(G)=L(e) O()1、2、3

23、、错 4、5、6、7、8、正确f (x,a)= x,yf (y,a)= 0试构造相应的确定有限自动机M。解答：对照自动机的定义 M=(S, Zf,S0,Z)，由确定有限自动机，先画出f的定义可知f(x,a)、f(y,b)均为多值函数，所以是一非 NFA M相应的状态图，如图 3-6-2所示。a图 3-6-2 NFA MX丫b用子集法构造状态转换矩阵表3-6-3 示。IlaIbXx,yyy一x,yx,yx,yx,y将转换矩阵中的所有子集重新命名而形成表3-6-4所示的状态转换矩阵。表3-6-4状态转换矩阵ab0211一2222即得到M '= (0,1,2, a,b, f,0, 1,2),

24、其状态转换图如图3-6-5所示。M的状态分成终态组1 , 2与非终态组0;其次，考 0 , 1,2: 即把原来到达2的弧都导向1,并删除状态2。最后，得到如图3-6-6所示化简a,b图3-6-6 化简后的DFA M 2、对给定正规式 b*解答：首先用A+=AA 所示。(d|ad) ( b|ab) +，构造其 NFA M ;* * * . _ .改造正规式得：b (d|ad)(b|ab)(b|ab)；其次，构造该正规式的 NFA M ,如图3-6-7将图3-6-5的DFA M最小化。首先，将察1,2。由于1,2a=1,2b=2?1,2，所以不再将其划分了，也即整个划分只有两组令状态1代表1,2,

25、DFA M '。b (d|ad)(b|ab)(b|ab)a b)(d|a%G)(b|a%(?)(b|ab)工9 d U bjXbb|ab4 匸 gQO GoadX426的 NFA M图 3-6-7ab b"dY853、构造下面文法的D f TLLL (1 )分析表。T f int | realL f id RRf , id R |£LL (1)分析表见表4-3-1分析 虽然这个文法很简单，我们还是从求开始符号集合和后继符号集合开始。=i nt, realFIRST ( D) =FIRST (T)FIRST ( L) =idFIRST (R) = , , £

26、有了上面每个非终结符的不是件难事了。填表时唯一要小心的时，FOLLOW (D) =FOLLOW ( L) =#FOLLOW (T) =idFOLLOW (R) =#FIRST集合，填分析表时要计算一个产生式右部a 的 FIRST ( a)就£是产生式Rf £右部的一个开始符号，而 #在FOLLOW ( R)中，所解答：4、以Rf £填在输入符号#的栏目中。表4-3-1 LL (1)分析表非终结符输入符号intrealid#DDf TLD f TLTT f intT f realLL f id RRR f ,id RR f £F面文法GS是否为LL (1)

27、文法？说明理由。S f A B | P Q xA f x yB f b cP f d P | £Q f a Q | £解答：该文法不是LL (1)文法，见下面分析中的说明。分析只有三个非终结符有两个选择。1、P的两个右部d P和£的开始符号肯定不相交。2、Q的两个右部a Q和£的开始符号肯定不相交。3、对 S 来说，由于 X FIRST(A B),所以该文法不是 LL (1)文法。5、设有以下文法：GS : S7 aAbDeldA 7 BSD|eB 7 SAc| cD|£D 7 Se| £求出该文法的每一个非终结符U该文法是LL (1

28、)文法吗？ 构造CS的LL (1)分析表。(1)求文法的每一个非终结符同时也有x FIRST(P Q X)(因为P和Q都可能为空)。(1)(2)(3)解答：因为：的 FOLLOW 集。U的FOLLOW 集的过程如下:S是识别符号，且有 A 7 bSD、B7 SAc、FIRST(D) U FIRST(Ac) U FIRST(e) U # =a,d U a,d,c,e U e U #=a,c,d,e#又因为A7BSD和D7 £,所以FOLLOW 因为S7 aAbDe和B7 SAc,所以D7 Se,所以FOLLOW (S)应包含中还包含 FOLLOW(A)。FOLLOW (A) =FIRS

29、T ( bDe)U FIRST得 FOLLOW (S) =a,d,c,e,# U a,b,c,d,e,#(C)=b,c综合、因为A7 BSD，所以因为 S7 aAbDe | d、A7 bSD| e 和 B7SAc | 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)文法。因为产生式 B7SAc|cD| £中 FIRST ( SAc)n FOLLOW ( B)(3) 构造GS的LL (1 )分析表。按照LL ( 1)分析表的构造算法构造方法表 4-3-

30、2FOLLOW ( B)=FIRST( SD)=a,d=a,d丰?abcde#SaAbDedABSDBSDBSDeBSac/ £cDSac/£DSe/£££Se/££6、GS的LL ( 1)分析表如表4-3-2所示。GS的LL (1)分析表将文法GV改造成为LL(1)的。GV : V7 N|NEE 7 V|V+EN 7 i解答： 对文法GV提取公共左因子后得到文法:G V : V 7 NAA 7£ EE 7 VBBT d +E N 7 i求出文法G V中每一个非终结符号的 FIRST集：FIRST(V)=iFIRS

31、T(A)=,dFIRST(E)=iFIRST(B)=+,dFIRST(N)=i求出文法G V中每一个非终结符号的 FOLLOW 集：FOLLOW(V)=# U FIRST(B) & U FOLLOW(E)=#,+,FOLLOW(A)= FOLLOW(V)=+,#FOLLOW(E)= FIRST()& U FOLLOW(B)= FIRST() d U FOLLOW(E)=FOLLOW(B)= FOLLOW(E)= FOLLOW(N)= FIRST(A)& U FOLLOW(V)=,+,#可以看到，对文法 G V的产生式A7乱E，有FIRST(E) n FOLLOW(A)=

32、 n +,#= ?对产生式B7 d +E，有FIRST(+E) n FOLLOW(B)=+ n = ?而文法的其他产生式都只有一个不为的右部，所以文法 G V是LL(1)文法。7、已知文法：GA : A 7 aAa| s(1 )(2)(3)解答:该文法是LL (1 )文法吗？为什么？若采用LL ( 1)方法进行语法分析，如何得到该文法的LL (1 )分析表？若输入符号串“ aaaa ”，请给出语法分析过程。(1 )因为产生式 A 7aAa| s有空产生式右部，而FOLLOW(A)=# U FIRST(a)=a, #造成所以该文法不是 LL (1)文法。(2)若采用LL (1)方法进行语法分析，

33、必须修改该文法。因该文法产生偶数(可以为0)个a,所以得到文法G' A :A7aaA| s此时对产生式 A 7 aaA| s,有 FOLLOW(A)=# U FOLLOW(A)=#，因而 FIRST(A) n FOLLOW(A)=a, S n #=?所以文法G A是LL( 1)文法，按LL( 1)分析表构造算法构造该文法的LL( 1)分析表如表4-3-3所示。表 4-3-3FIRST(A) n FOLLOW(A)=A, S n a,#丰?A#AA 7 aaAA 7 s文法G A的LL(1)分析表(3)若采用LL(1)方法进行语法分析，对符号串“aaaa的分析过程如表 4-3-4所示。步

34、骤分析栈输入串产生式/动作1#Aa a a a #A 7 aaA2#A a aa a a a #匹配3#A aa a a #匹配4#Aa a #A 7 aaA对符号串“ aaaa”的分析过程表 4-3-45#A a aa a #匹配6#A aa#匹配7#A#A f £8#接受&设有文法 GS为:(1)Sf a|b|（A）A f SdA|S完成下列算符优先关系表，见表表 5-7-15-7-1，并判断GS是否为算符优先文法。 算符优先关系表ab()d#a?b?(?)?d#?给出句型（SdSdS）的短语、简单短语、句柄、素短语和最左素短语。 给出输入串（adb） #的分析过程。(2

35、)(3)解答：(1)由 Sf a|b|(A)得：FIRSTVT(S)=a,b,();由 A f Sd 得：FIRSTVT(A)=d;FIRSTVT(A)=d,a,b,(;由 Sf a|b|(A)得；LASTVT(S)=a,b,;由 A f dA 得：LASTVT(A)=d,LASTVT(A)=d,a,b,)。构造优先关系表方法如下： 对Pfab，或 对PfaR，而 对PfRb，而由此得到：由 Sf (A)得：(?);由 Sf (A 得：(?FIRSTVT(A)，即：(?d,(?a ,(?b,(?(;由 Af dA 得：d?FIRSTVT(A), d?d,d?a,d?b,d?(;由 Sf A)得

36、，LASTVT(A) ?)，即：d?),a?),b?),)?);由 Af 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先求文法GS的FIRSTVT集和LASTVT 集:又由 A f S 得：FIRSTVT(S) ? FIRSTVT(A),即又由 A f S 得：LASTVT(S)Pf - aQb，有 a? b; b FIRSTVT(R)，有 a?b; a FIRSTVT(R)

37、，有 a?b。LASTVT(A),即 即:ab()d#a?b?(?)?d?#?算符优先关系表、?、？三种优先关系之一，故 GS为由表5-7-2可以看出，任何两个终结符之间至少只满足 算符优先文法。（2）为求出句型（SdSdS）的短语、简单短语、句柄，我们先画出该句型对应的语法树，如图5-7-3所示。由图5-7-3得到：A )dd图5-7-3句型（SdSdS）的语法树 短语：S，SdS，SdSdS，（ SdSdS）简单短语（即直接短语）句柄（即最左直接短语）：S素短语：SdS,它同时也是该句型的最左素短语。（3）输入串（adb） #的分析过程见表5-7-4表5-7-4 输入串（adb）#的分析过

38、程符号栈输入串说明#(adb)#移进#（adb)#移进#( adb)#用St a归约#( Sdb)#移进#( Sdb)#移进#( Sdb)#用St b归约#( SdS)#用AtS归约#( SdA)#用A t SdA归约#( A)#移进#（ A）#用St（ a ）归约#S#分析成功模拟习题4一、单项选择题1、若a为终结符，则A 7 a - a 3为项目a.归约b.移进C.接受d.待约2、 若项目集Ik含有A7 a-,则在状态k时，仅当面临的输入符号a&OLLOW(A)时，才采取“A 7 a ”动作的一定是_。a.LALR文法BLR (0)文法c丄R ( 1)文法 d.SLR (1)文法?

39、LR (1) d.无二义文法？LR (1) rj”的栏，则。3、 就文法的描述能力来说，有。a. SLR ( 1) ?LR (0) b. LR (1) ?LR (0) c. SLR (1)4、在LR ( 0)的ACTION子表中，如果某一行中存在标记“a.该行必定填满rjb.该行未填满rjrjC.其他行也有rjd.goto子表中也有5、 一个 指明了在分析过程中的某时刻所能看到产生式多大一部分。a.活前缀b.前缀解答：1、A 7 a 称为归约项目，对文法开始符(a为终结符)称为移进项目。在此选b.2、当用产生式A 7 a归约时，LR ( 0) 临的输入符号a CFOLLOW(A)时进行归约；c

40、.项目d.项目集S的归约项目，如 S'Ta称为接受项目， A a - a 3提下，当a后跟终结符a时，才进行归约；因此选3、由于LR (0) ?SLR (1) ? LR (1) ?无二义文法，故选4、选 a。5、选 C。二、多项选择题1、一个LR分析器包括。a.一个总控程序b.一个项目集d.一张分析表e.一个分析栈无论面临什么输入符号都进行归约；SLR (1 )则仅当面LR (1)则当在把 a归约为A的规范句型的前缀 3Aa前doc. 一个活前缀2、 LR分析器核心部分是一张分析表，该表包括a.LL(1)分析b.优先关系C.GOTOd.LRe.ACTION3、 每一项 ACTIONS

41、, a所规定的动作包括 。a.移进b.比较C.接受d.归约4、 对LR分析表的构造，有可能存在 动作冲突。a.移进b.归约5、就文法的描述能力来说，有a. SLR (1) ?LR (1)d. LR (1) ?无二义文法6、对LR分析器来说，存在a.LALRb.LR (0)7、自上而下的语法分析方法有 a.算符优先分析法 d.LR (0)分析法解答:c。等丁表。e扌报错C.移进/归约 d.移进/移进。b. LR( 1)?SLR( 1)e. SLR( 1)?无二义文法 一等分析表的构造方法。c. SLR( 1)d.SLR( 0) 。b.LL( 1)分析法e.LALR ( 1)分析法e.归约/归约c

42、. LR (0) ?LR (1)e.LR (1)c.SLR (1)分析法1、一个LR分析器包括一个总控程序和一张分析表，选a、d。2、选C、e o3、选a、c、d、e。4、在LR分析表的构造中有可能存在 移进/ “归约”和“归约”5、选a、b、c、d、e。6、选a、b、c、e。7、选a、c、d、e。/ “归约”冲突；故选C、 e。25三、填空题。使得它的 均是唯一确定的，则称该文法为LR文法。1、对于一个文法，如果能够构造2、 字的前缀是指该字的 。3、活前缀是指 的一个前缀，这种前缀不含 之后的任何符号。4、 在LR分析过程中，只要 的已扫描部分保持可归约成一个 ，则扫描过的部分正确。5、

43、将识别 的NFA确定化，使其成为以 为状态的DFA ,这个DFA就是建立的基础。6、 A7 a 称为项目；对文法开始符 S'Ta为项目；若a为终结符，则称 Aa a 3模拟习题5为 项目；若B为非终结符，则称 A7 a aB为 项目。 厂 LR ( 0)分析法的名字中“ L”表示“ R”表示解答：1、 一张分析表每个入口2、任意首部3、规范句型4、输入串5、活前缀,“ 0”表示6、归约接受7、自左至右分析四、综合题1、对于文法GS:句柄 活前缀 项目集合 LR分析算法移进待约 采用最右推导的逆过程即最左归约向石查看0个字符S7 AS|bA 7 SA|aLR (0)项目(1) 列出所有(

44、2) 列出构成文法 LR (0)项目集规范族。 解答：首先将文法G拓广为GS :S 7 SS7 AS|b A 7 SA|a(0)项目是：S7 AS S7. bS7 b A 7 SA(1)文法GS的LR1、S '7. S2、S 7 S 3、S7. AS4、S7 A S5、6、7、8、9、A 7 S A10、A 7 SA 11、A 7. a12、A 7 a 2、列出构成文法 LR (0) 用I0：(0)1、S'7.SI3： 9、A 7 S-A3、S7-AS&A 7-SA8、A 7-SA3、S7.AS11、A 7-a6、S7-b6、S7.b11、A 7-a2、S'7

45、S l4：10、A 7 SA -9、A 7 S A4、S7 A-S8、A 7SA3、S7-AS11、A 7-a6、S7-b3、S7.AS&A 7-SA6、S7b11、A 7-a4、S7 A Sl5：5、S7 AS -3、S7.AS9、A 7 S-A6、S7-b&A 7-SA8、A 7-SA11、A 7-a11、A 7-a3、S7-AS6、S7 -bG'的 LRIi：I2：项目集规范族。£ -CLOSURE (闭包)办法构造文法项目集规范族如下：16： 12、A7a 17: 7、S7 b 注意：I1中的S7S 和A7. SA是由状态I0中的1和3读入一个S字符后

46、得到的下一个项目；，而 |4中的A7SA和A7A S则是由l3中的9和3读入一个A字符后得到的下一个项目；I5中的S7 AS 和A7S A则是由I4中的4和8读入一个S字符后得到的下一个项目。状态全体构成了文法 G的LR (0)规范族。仃一、单项选择题1、 中间代码生成所依据的是_Oa.语法规则b.词法规则C.语义规则2、 四元式之间的联系是通过 实现的。a.指示器b.临时变量C.符号表3、 后缀式ab+cd+/可用表达式 来表示。b.(a+b)/(c+d)c.a+b/(c+d)Ad.等价变换规则d.程序变量a.a+b/c+d4、表达式(-| A V B)a. n AB VA CD V c. AB Vn CD VAd.a+b+c/d(CV D)的逆波兰表示