编译原理习题(后)

第一章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、词法剖析器的输入是。a．单词符号串b．源程序c．语法单位d．目标程序8、中间代码生成时所依照的是-。a．语法例则b．词法例则c．语义规则

d．等价变换规则9、编译程序是对

。a．汇编程序的翻译

b．高级语言程序的解说履行c．机器语言的履行

d．高级语言的翻译10、语法剖析应依照

。a．语义规则

b．语法例则c．构词规则

d．等价变换规则二、多项选择题1、编译程序各阶段的工作都波及到a．语法剖析b．表格管理d．语义剖析e．词法剖析2、编译程序工作时，往常有阶段。a．词法剖析b．语法剖析d．语义检查e．目标代码生成

。

c．犯错办理c．中间代码生成三、填空题成。

1、解说程序和编译程序的差别在于2、编译过程往常可分为5个阶段，分别是3、编译程序工作过程中，第一段输入是

。

、语法剖析、代码优化和目标代码生，最后阶段的输出为程序。4、编译程序是指将程序翻译成程序的程序。单项选择解答1、将编译程序分红若干个“遍”是为了使编译程序的结构更为清楚，应选b。2、结构编译程序应掌握源程序、目口号言及编译方法等三方面的知识，应选d。3、对编译而言，变量既拥有左值又拥有右值，应选c。4、编译程序打交道最多的就是各样表格，所以选

d。5、目标代码包含汇编指令代码、可重定位指令代码和绝对指令代码

3种，所以不是目标代码的只好选d。6、词法剖析依照的是构词规则，语法剖析依照的是语法例则，中间代码生成依照的是语义规则，而且语义规则能够定义一个程序的意义。所以选a。7、b8、c9、d10、c多项选择解答1．b、c2.a、b、c、e填空解答能否生成目标程序

2、词法剖析

中间代码生成

3、源程序目标代码生成

4、源程序

目口号言第二章一、单项选择题1、文法G：S→xSx|y所识其余语言是。a.xyxb.(xyx)*c.xnyxn(n≥0)d.x*yx*2、文法G描绘的语言L(G)是指。a.L(G)={α|S+α,α∈VT*}b.L(G)={α|S*α,α∈Vc.L(G)={α|S*α,α∈(VTNd.L(G)={α|S+α,α∈(VTN∪V*)}∪V*)}3、有限状态自动机能辨别。a.上下文没关文法b.上下文有关文法c.正规文法d.短语文法4、设G为算符优先文法，G的随意终结符对a、b有以下关系成立。a.若f(a)>g(b)，则a>bb.若f(a)<g(b)，则a<bc.a~b都不必定成立d.a~b必定成立5、假如文法G是无二义的，则它的任何句子α。最左推导和最右推导对应的语法树必然同样最左推导和最右推导对应的语法树可能不一样最左推导和最右推导必然同样可能存在两个不一样的最左推导，但它们对应的语法树同样6、由文法的开始符经0步或多步推导产生的文法符号序列是a.短语b.句柄c.句型d.句子7、文法G：E→E+T|T

。T→T*P|PP→(E)|I则句型P+T+i的句柄和最左素短语为。+T和ib.P和P+Tc.i和P+T+i8、设文法为：S→SA|AA→a|b则对句子aba，下边是规范推导。

和

TSSASAAAAAaAAabAabaSSASAAAAAAAaAbaabaSSASAASAaSbaAbaabaSSASaSAaSbaAbaaba9、文法G：S→b|∧(T)T→T,S|S则FIRSTVT(T)。a.{b,∧,(}b.{b,∧,)}c.{b,∧,(,，}d.{b,∧,),，}10、产生正规语言的文法为。a.0型b.1型c.2型d.3型11、采纳自上而下剖析，一定。a.除去左递归b.除去右递归c.除去回溯d.提取公共左因子12、在规范归约中，用来刻画可归约串。a.直接短语b.句柄c.最左素短语d.素短语13、有文法G：E→E*T|TT→T+i|i句子1+2*8+6按该文法G归约，其值为。14a.23B.42c.30d.17、规范归约指。a.最左推导的逆过程b.最右推导的逆过程c.规范推导d.最左归约的逆过程二、多项选择题1、下边哪些说法是错误的。a.有向图是一个状态变换图b.状态变换图是一个有向图c.有向图是一个DFA能够用状态变换图表示2、对无二义性文法来说，一棵语法树常常代表了。a.多种推导过程b.多种最左推导过程c.一种最左推导过程d.仅一种推导过程e.一种最左推导过程3、假如文法G存在一个句子，知足以下条件之一时，则称该文法是二义文法。该句子的最左推导与最右推导同样该句子有两个不一样的最左推导该句子有两棵不一样的最右推导该句子有两棵不一样的语法树e.该句子的语法树只有一个4、有一文法G：S→ABA→aAb|εB→cBd|ε它不产生下边

会合。a.{anbmcndm|n,m

≥0}

b.{anbncmdm|n,m>0}c.{anbmcmdn|n,m

≥0}

d.{anbncmdm|n,m

≥0}e.{anbncndn|n

≥0}5、自下而上的语法剖析中，应从开始剖析。a.句型b.句子c.以单词为单位的程序d.文法的开始符e.句柄6、对正规文法描绘的语言，以下有能力描绘它。型文法型文法c.上下文没关文法d.右线性文法e.左线性文法三、填空题1、文法中的终结符和非终结符的交集是。词法剖析器交给语法剖析器的文法符号必定是，它必定只出此刻产生式的部。2、最左推导是指每次都对句型中的非终结符进行扩展。3、在语法剖析中，最常有的两种方法必定是剖析法，另一是剖析法。4、采纳语法剖析时，一定除去文法的左递归。5、树代表推导过程，树代表归约过程。6、自下而上剖析法采纳、归约、错误办理、等四种操作。7、Chomsky把文法分为种种类，编译器结构中采纳和文法，它们分别产生和语言，并分别用和自动机辨别所产生的语言。四、判断题1、文法S→aS|bR|ε描绘的语言是(a|bc)*()R→cS2、在自下而上的语法剖析中，语法树与剖析树必定同样。（）3、二义文法不是上下文没关文法。（）4、语法剖析时一定先除去文法中的左递归。（）5、规范归约和规范推导是互逆的两个过程。（）6、一个文法全部句型的会合形成该文法所能接受的语言。（）五、简答题1、句柄

2、素短语

3、语法树

4、归约

5、推导六、问答题1、给出上下文没关文法的定义。2、文法G[S]：S→aSPQ|abQQP→PQbP→bbbQ→bccQ→c1）它是Chomsky哪一型文法2）它生成的语言是什么3、按指定种类，给出语言的文法。L={aibj|j＞i≥1}的上下文没关文法。4、有文法G：S→aAcB|BdA→AaB|cB→bScA|b1）试求句型aAaBcbbdcc和aAcbBdcc的句柄；2）写出句子acabcbbdcc的最左推导过程。5、对于文法G[S]：S→（L）|aS|aL→L,S|S（1）画出句型（S,（a））的语法树。（2）写出上述句型的全部短语、直接短语、句柄和素短语。6、考虑文法G[T]：T→T*F|FF→F↑P|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。5、假如文法G无二义性，则最左推导是先生长右侧的枝叶：对于d，假如有两个不一样的是了左推导，则必然有二义性。应选a。6、选c。E7、由图2-8-1的语法树和优先关系能够看出应选b。E+FE+TPTiP#<·+·>+<·i·>#图2-8-1句型P+T+I的语法及优先关系8、规范推导是最左推导，应选d。9、由T→T,和T→(得FIRSTVT(T))={(,，)}；由T→S得FIRSTVT(S)FIRSTVT(T)，而FIRSTVT(S)={b,∧,(}；即10、d

FIRSTVT(T)={b,∧,(,，}；所以选c。11、c12、b13、b14、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、42型3型上下文没关语言判断解答1、对2、错3、错4、错

正规语言5、错6、错

下推自动机

有限简答[解答]1、句柄：一个句型的最左直接短语称为该句型的句柄。2、素短语：起码含有一个终结符的素短语，而且除它自己以外不再含任何更小的素短语。3、语法树：知足下边4个条件的树称之为文法G[S]的一棵语法树。①每一终结均有一标志，此标志为VN∪VT中的一个符号；②树的根结点以文法G[S]的开始符S标志；VN中的一个符号；③若一结点起码有一个直接后继，则此结点上的标志为④若一个以A为标志的结点有K个直接后继，且按从左至右的次序，这些结点的标志分别为X12K12K,X,,X，则A→X,X,,X，必然是G的一个产生式。4、归约：我们称αγβ直接归约出αAβ，仅当A→γ是一个产生式，且α、β∈NT(V∪V)*。归约过程就是从输入串开始，频频用产生式右部的符号替代成产生式左部符号，直至文法开始符。5、推导：我们称αAβ直接推出αγβ，即αAβαγβ，仅当A→γ是一个产生式，且α、β∈(VN∪VT)*。假如α1α2αn，则我们称这个序列是从α1至α2的一个推导。若存在一个从α1αn的推导，则称α1可推导出αn。推导是归约的逆过程。问答1[解答]G是一个四元式（VT,VN,S,P），此中：一个上下文没关文法●TV是一个非空有限集，它的每个元素称为终结符号；VT∩VN=Φ；●VN是一个非空有限集，它的每个元素称为非终结符号，●S是一个非终结符号，称为开始符号；●P是一个产生式会合（有限），每个产生式的形式是P→α，此中，P∈VN，α∈(VT∪VN)*。开始符号S起码一定在某个产生式的左部出现一次。2[解答]1）因为产生式左部存在终结符号，且全部产生式左部符号的长度均小于等于产生式右部的符号长度，所以文法G[S]是Chomsky1型文法，即上下文有关文法。2）按产生式出现的次序规定优先级由高到低（不然没法推出句子），我们能够获得：SabQabcSaSPQaabQPQaabPQQaabbQQaabbcQaabbccSaSPQaaSPQPQaaabQPQPQaaabPQQPQaaabPQPQQaaaPPQQQaaabbPqqqaaabbQQQaaabbbcQQaaabbbccQaaabbbccc于是获得文法G[S]生成的语言L={anbncn|n≥1}3【解答】（1）由L={aibj|j＞i≥1}知，所求该语言对应的上下文没关文法第一应有S→aSb型产生式，以保证b的个数许多于a的个数；其次，还需有S→Sb或S→bS型的产生式，用以保证b的个数多于a的个数；也即所求上下文没关文法G[S]为：G[S]：S→aSb|Sb|b4【解答】（1）分别画出对应两句型的语法树，如图2-8-2所示句柄:AaBBdSSaAcBaAcBAaBbScABd

c

BScBd

Acb(b)(a)图2-8-2语法树2）句子acabcbbdcc的最左推导以下：SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcAacabcbbdcAacabcbbdcc5【解答】S（1）句型（S,（a））的语法树如图2-8-3所示（L）L，SS(L)（2）由图2-8-3可知：S①短语：S、a、(a)、S,(a)、(S,(a))；a②直接短语：a、S；图2-8-3句型（S,（a））的语法树③句柄：S；④素短语：素短语可由图2-8-3中相邻终结符之间的优先关系求得，即；#·（·，·（·a·）·）·#所以素短语为a。6【解答】T第一结构T*P↑（T*F）的语法树如图2-8-4所示。由图2-8-4可知，T*P↑（T*F）是文法G[T]的一个句型。T*FF↑P直接短语有两个，即P和T*F；句柄为P。P（T）T*F图2-8-4句型T*P↑（T*F）的语法树第三章一、单项选择题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）接受的字集为。0X1Y0图3-6-1a.以0开头的二进制数构成的会合b.以0结尾的二进制数构成的会合c.含奇数个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是的一个特例。2、若二个正规式所表示的同样，则认为两者是等价的。3、一个字集是正规的，当且仅当它可由所。四、判断题1、一个有限状态自动机中，有且仅有一个独一终态。（）2、设r和s分别是正规式，则有L（r|s）=L(r)|L(s)。（）3、自动机M和M′的状态数不一样，则两者必不等价。（）4、确立的自动机以及不确立的自动机都能正确地辨别正规集。（）5、对随意一个右线性文法G，都存在一个NFAM，知足L(G)=L(M)。（）6、对随意一个右线性文法G，都存在一个DFAM，知足L(G)=L(M)。（）7、对任何正规表达式e，都存在一个NFAM，知足L(G)=L(e)。（）8、对任何正规表达式e，都存在一个DFAM，知足L(G)=L(e)。（）五、基此题1、设M＝（{x,y},{a,b},f,x,{y}）为一非确立的有限自动机，此中f定义以下：f（x,a）＝{x,y}f（x,b）＝{y}f（y,a）＝φf（y,b）＝{x,y}试结构相应确实定有限自动机M′。2、对给定正规式b*（d|ad）（b|ab）+，结构其NFAM；单项选择解答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的定义可知f(x,a)、f(y,b)均为多值函数，所以是一非确立有限自动机，先画出NFAM相应的状态图，如图3-6-2所示。aa用子集法结构状态变换矩阵表3-6-3所示。XYIIabIbb{x}{x,y}{y}b{y}—{x,y}{x,y}{x,y}{x,y}将变换矩阵中的全部子集从头命名而形成表3-6-4所示的状态变换矩阵。表3-6-4状态变换矩阵ab0211—2222即获得M′=（{0,1,2},{a,b},f,0,{1,2}），其状态变换图如图3-6-5所示。aa,b021bb将图3-6-5的DFAM′最小化。第一，将M′的状态分红终态组{1，2}与非终态组{0}；其次，观察{1,2}。因为{1,2}a={1,2}b={2}{1,2}，所以不再将其区分了，也即整个区分只有两组{0}，{1,2}：令状态1代表{1,2}，即把本来抵达2的弧都导向1，并删除状态2。最后，获得如图3-6-6所示化简DFAM′。aa,b01b2解答：第一用A+=AA*改造正规式得：b*(d|ad)(b|ab)(b|ab)*；其次，结构该正规式的NFAM，如图3-6-7所示。Xb*(d|ad)(b|ab)(b|abYXb*1(d|ad2(b|ab3(b|ab)*Y))b|abbdbXε4ε123ε5εYbadabbdbXε4ε123ε5εYaaab7b86d图3-6-7的NFAM第四章1、结构下边文法的LL（1）剖析表。D→TLT→int|realL→idRR→,idR|ε2、下边文法G[S]能否为LL（1）文法说明原因。S→AB|PQxA→xyB→bcP→dP|εQ→aQ|ε3、设有以下文法：G[S]：S→aAbDe|dA→BSD|eB→SAc|cD|εD→Se|ε（1）求出该文法的每一个非终结符U的FOLLOW集。2）该文法是LL（1）文法吗3）结构C[S]的LL（1）剖析表。4、将文法G[V]改造成为LL(1)的。G[V]：V→N|N[E]E→V|V+EN→i5、已知文法：G[A]：A→aAa|ε1）该文法是LL（1）文法吗为何2）若采纳LL（1）方法进行语法剖析，怎样获得该文法的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）={id}FIRST（R）={，,}εFOLLOW（R）={#}有了上边每个非终结符的FIRST会合，填剖析表时要计算一个产生式右部α的FIRST（α）就不是件难事了。填表时独一要当心的时，ε是产生式R→ε右部的一个开始符号，而#在FOLLOW（R）中，所以R→ε填在输入符号#的栏目中。表4-3-1LL（1）剖析表非终结符输入符号intrealid，#DD→TLD→TLTT→intT→realLL→idRRR→,idRR→ε2解答：该文法不是LL（1）文法，见下边剖析中的说明。剖析只有三个非终结符有两个选择。1、P的两个右部dP和ε的开始符号必定不订交。2、Q的两个右部aQ和ε的开始符号必定不订交。3、对S来说，因为x∈FIRST(AB)，同时也有x∈FIRST(PQx)（因为以该文法不是LL（1）文法。3解答：（1）求文法的每一个非终结符U的FOLLOW集的过程以下：

P和

Q都可能为空）。所因为：①S是辨别符号，且有A→BSD、B→SAc、D→Se，所以FOLLOW（S）应包含FIRST(D)∪FIRST(Ac)∪FIRST(e)∪{#}={a,d}∪{a,d,c,e}∪{e}∪{#}={a,c,d,e#}②又因为A→BSD和D→ε，所以FOLLOW中还包含FOLLOW(A)。因为S→aAbDe和B→SAc,所以FOLLOW（A）=FIRST（bDe）∪FIRST（c）={b,c}综合①、②得FOLLOW（S）={a,d,c,e,#}∪{a,b,c,d,e,#}因为A→BSD，所以FOLLOW（B）=FIRST（SD）={a,d}因为S→aAbDe|d、A→BSD|e和B→SAc|cD，所以FOLLOW（D）=FIRST（e）∪FOLLOW（A）∪FOLLOW（B）={e}∪{b,c}∪{a,d}={a,b,c,d,e}（2）G[S]不是LL（1）文法。因为产生式B→SAc|cD|ε中FIRST（SAc）∩FOLLOW（B）={a,d}≠（3）结构G[S]的LL（1）剖析表。依照LL（1）剖析表的结构算法结构方法G[S]的LL（1）剖析表如表表4-3-2G[S]的LL（1）剖析表

4-3-2所示。a

b

c

d

e

#S

aAbDe

dA

BSD

BSD

BSD

eB

Sac/ε

cD

Sac/εD4解答：

Se/εεε对文法G[V]提取公共左因子后获得文法：G′[V]：V→NA

Se/ε

εA→ε|[E]E→VBB→ε|+EN→i求出文法

G′[V]中每一个非终结符号的

FIRST集：FIRST(V)={i}

FIRST(A)={[,

ε}FIRST(E)={i}

FIRST(B)={+,ε}FIRST(N)={i}求出文法

G′[V]中每一个非终结符号的

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)={[,],+,#}能够看到，对文法G′[V]的产生式A→ε|[E]，有FIRST([E])∩FOLLOW(A)={[}∩{+,],#}=对产生式B→ε|+E，有FIRST(+E)∩FOLLOW(B)={+}∩{]}=而文法的其余产生式都只有一个不为ε的右部，所以文法G′[V]是LL(1)文法。5解答：（1）因为产生式A→aAa|ε有空产生式右部，而FOLLOW(A)={#}∪FIRST(a)={a,#}造成FIRST(A)∩FOLLOW(A)={A,ε}∩{a,#}≠所以该文法不是LL（1）文法。2）若采纳LL（1）方法进行语法剖析，一定改正该文法。因该文法产生偶数（能够为0）个a，所以获得文法G′[A]：A→aaA|ε此时对产生式A→aaA|ε，有FOLLOW(A)={#}∪FOLLOW(A)={#}，因此FIRST(A)∩FOLLOW(A)={a,ε}∩{#}=所以文法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#Aaaaa#A→aaA2#Aaaaaaa#般配3#Aaaaa#般配4#Aaa#A→aaA5#Aaaaa#般配6#Aaa#般配7#A#A→ε8##接受第五章1.设有文法

G[S]为：S→a|b|(A)A→SdA|S（1）

达成以下算符优先关系表，见表表5-7-1

5-7-1，并判断G[S]能否为算符优先文法。算符优先关系表a

b

(

)

d

#ab()d#2）给出句型（SdSdS）的短语、简单短语、句柄、素短语和最左素短语。3）给出输入串（adb）#的剖析过程。解答：1）先求文法G[S]的FIRSTVT集和LASTVT集：由S→a|b|(A)得：FIRSTVT(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,)}。结构优先关系表方法以下：①对P→ab，或P→aQb，有ab;②对P→aR，而b∈FIRSTVT(R)，有ab;③对P→Rb，而a∈FIRSTVT(R)，有ab。由此获得：由S→(A)得：();②由S→(A得：(FIRSTVT(A)，即：(d,(a,(b,((;由A→dA得：dFIRSTVT(A)，即：dd,da,db,d(;③由S→A)得，LASTVT(A))，即：d),a),b),));由A→Sd得：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能够看出，任何两个终结符之间起码只知足、、三种优先关系之一，故G[S]为算符优先文法。（2）为求出句型（SdSdS）的短语、简单短语、句柄，我们先画出该句型对应的语法树，如图5-7-3所示。由图5-7-3获得：短语：S，SdS，SdSdS，（SdSdS）简单短语（即直接短语）：S句柄（即最左直接短语）：S素短语：SdS，它同时也是该句型的最左素短语。

S（A）SdASdAS（3）输入串（adb）#的剖析过程见表5-7-4图5-7-3句型（SdSdS）的语法树表5-7-4输入串（adb）#的剖析过程符号栈输入串说明#(adb)#移进#（adb)#移进#（adb)#用S→a归约#（Sdb)#移进#（Sdb)#移进#（Sdb)#用S→b归约#（SdS)#用A→S归约#（SdA)#用A→SdA归约#（A)#移进#（A）#用S→（A）归约#S#剖析成功第六章一、单项选择题1、若a为终结符，则A→α·aβ为项目a.归约b.移进c.接受d.待约2、若项目集Ik含有A→α·，则在状态k时，仅当面对的输入符号a∈FOLLOW(A)时，才采纳“→α·”动作的必定是。文法（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子表中，假如某一行中存在标志“rj”的栏，则。a.该行必然填满rjb.该行未填满rj

Ac.其余行也有rj子表中也有rj5、一个指了然在剖析过程中的某时刻所能看到产生式多大一部分。a.活前缀b.前缀c.项目d.项目集二、多项选择题1、一个LR剖析器包含。a.一个总控程序b.一个项目集c.一个活前缀d.一张剖析表e.一个剖析栈2、LR剖析器核心部分是一张剖析表，该表包含等子表。(1)剖析b.优先关系3、每一项ACTION[S，a]所规定的动作包含。a.移进b.比较c.接受d.归约e.报错4、对LR剖析表的结构，有可能存在动作矛盾。a.移进b.归约c.移进/归约d.移进/移进e.归约/归约5、就文法的描绘能力来说，有。a.SLR（1）LR（1）b.LR（1）SLR（1）c.LR（0）LR（1）6、对LR剖析器来说，存在平剖析表的结构方法。0）（1）（0）（1）7、自上而下的语法剖析方法有。a.算符优先剖析法（1）剖析法（0）剖析法（1）剖析法

（1）剖析法三、填空题1、对于一个文法，假如能够结构

。使得它的

均是独一确立的，则称该文法为

LR文法。2、字的前缀是指该字的。3、活前缀是指的一个前缀，这类前缀不含以后的任何符号。4、在LR剖析过程中，只需的已扫描部分保持可归约成一个，则扫描过的部分正确。5、将识其余NFA确立化，使其成为认为状态的DFA，这个DFA就是成立的基础。6、A→α·称为项目；对文法开始符S′→α·为项目；若

a为终结符，则称

A→α·

aβ为项目；若B为非终结符，则称A→α·aβ为项目。7、LR（0）剖析法的名字中“

L”表示

，“R”表示

，“0”表示

。四、综合题1、对于文法G[S]：S→AS|bA→SA|a1）列出全部LR（0）项目2）列出构成文法LR（0）项目集规范族。单项解答：1、A→α·称为归约项目，对文法开始符S′的归约项目，如S′→α·称为接受项目，A→α·aβ（a为终结符）称为移进项目。在此选b.2、当用产生式A→α归约时，LR（0）不论面对什么输入符号都进行归约；SLR（1）则仅当面临的输入符号a∈FOLLOW(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剖析算法6、归约接受移进待约7、自左至右剖析采纳最右推导的逆过程即最左归约向右查察0个字符综合解答：G拓广为G[S′]：第一将文法S′→SS→AS|bA→SA|a（1）文法G[S′]的1、S′→·S2、S′→S·3、S→·AS4、S→A·S

LR（0）项目是：5、S→AS·6、S→·b7、S→b·8、A→·SA

9、A→S·A10、A→SA·11、A→·a12、A→a·2、列出构成文法LR（0）项目集规范族。用ε-CLOSURE（闭包）方法结构文法G′的LR（0）项目集规范族以下：I0：1、S′→·SI3：9、A→S·AI6：12、A→a·3、S→·AS8、A→·SAI7：7、S→b·8、A→·SA

3、S→·AS11、A→·a6、S→·b

6、S→·b11、A→·aI1：2、S′→S·

I4：10、A→SA·9、A→S·A

4、S→A·S8、A→·SA

3、S→·AS11、A→·a

6、S→·b3、S→·AS6、S→·b

8、A→·SA11、A→·aI2：4、S→A·S

I5：

5、S→AS·3、S→·AS

9、A→S·A6、S→·b8、A→·SA

8、A→·SA11、A→·a11、A→·a

3、S→·AS6、S→·b注意：I1中的S′→S·和A→·SA是由状态I0中的1和3读入一个S字符后获得的下一个项目；，而I4中的A→SA和A→A·S则是由I3中的9和3读入一个A字符后获得的下一个项目；I5中的S→AS·和A→S·A则是由I中的4和8读入一个S字符后获得的下一个项目。4G′的LR（0）规范族。状态全体构成了文法第七章一、单项选择题1、中间代码生成所依照的是。a.语法例则b.词法例则c.语义规则d.等价变换规则2、四元式之间的联系是经过实现的。a.指示器b.暂时变量c.符号表d.程序变量3、后缀式ab+cd+/可用表达式来表示。+b/c+db.(a+b)/(c+d)+b/(c+d)+b+c/d4、表达式（┓A∨B）∧（C∨D）的逆波兰表示为。a.┓AB∨∧CD∨b.A┓B∨CD∨∧c.AB∨┓CD∨∧d.A┓B∨∧CD∨+++5、中间代码的树型表示ABCD所对应的表达式为。+B+C+D+(B+C)+Dc.(A+B)+C+Dd.(A+B)+(C+D)6、四元式表示法的长处为。a.不便于优化办理，但便于表的更动b.不便于优化办理，但节俭储存空间c.便于优化办理，也便于表的更动d.便于表的更动，也节俭储存空间7、终结符拥有属性。a.传达b.继承c.抽象d.综合二、多顶选择题1、中间代码主要有。a．四元式b．二元式c．三元式d．后缀式e．间接三元式2、下边中间代码形式中，能正确表示算术表达式a+b+c的有。a．ab+c+b．abc++c．+d．+e．a+b+c+ca+abbc3、在下边的语法制导翻译中，采纳拉链-回填技术。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

d．

+

c

e．

a

*7、三地点代码语句详细实现往常有

表示方法。a．逆波兰表示b．三元式

c．间接三元式

d．树形表示

e．四元式三、填空题1、中间代码有等形式，生成中间代码主假如为了使。2、语法制导翻译既能够用来产生代码，也能够用来产生指令，甚至可用来对输入串进行。3、当源程序中的标号出现“先引用后定义”时，中间代码的转移地点须持时才能确立，因此要进行。4、文法符号的属性有两种，一种称为，另一种称为。5、后缀式abc-/所代表的表达式是，表达式(a-b)*c可用后缀式表示。6、用一张辅以的方法来表示中间代码，这类表示法称为间接三元式。四、综合题1、给出以下表达式的逆波兰表示（后缀式）：a*(-b+c)(A∨B)∧(C∨┑D∧E)2、写出算术表达式：A+B*(C-D)+E/(C-D)↑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、凡波及到跳转的语句都需要采纳拉链——回填技术，应选b、c、d。4、选b、c。5、选b、d。6、选b、e。7、选b、c、e。填空解答1、逆波兰记号、树形表示、三元式、四元式2、中间目标解说履行

目标代码的优化简单实现3、标号定义4、继承属性

回填综合属性5、a/(b-c)

ab-c*6、间接码表三元式表综合解答1、①ab@c+*;AB∨CD┑E∧∨∧2、①表达式的四元式序列：②表达式的三元式序列③间接三元式序列（1）(-,C,D,T1)（1）(-,C,D)⑴（1）(-,C,D)（2）(*,B,T,T)（2）(*,B,(1))⑵（2）(*,B,(1))12（3）(+,A,T,T)（3）(+,A,(2))⑶（3）(+,A,(2))23（4）(-,C,D,T4)（4）(-,C,D)⑴⑷(↑,(1),N)第八章一、单项选择题1、编译程序使用差别表记符的作用域。a.说明表记符的过程或函数名c.说明表记符的过程或函数的动向层次

b.说明表记符的过程或函数的静态层次d.表记符的行号2、在目标代码生成阶段，符号表用于。a.目标代码生成b.语义检查c.语法检查d.地点分派3、过程信息表不包含。a.过程进口地点b.过程的静态层次c.过程名d.过程参数信息4、以下对于表记符和名字表达中，正确的选项是。a.表记符有必定的含义b.名字是一个没存心义的字符序列c.名字有切实的属性d.a~c都不正确二、多项选择题1、符号表的每一项均包含a.名字栏b.种类栏

。

c.信息栏

d.值栏

e.a~d均包含2、对编译程序所用到的符号表，波及的操作有。a.填写或更新信息栏内容b.填入新名c.给命名字，接见它的有关信息d.杂凑技术e.线性表和排序二叉树3、源程序中的错误一般有。a.词法错误b.语法错误c.d.编译错误e.违犯环境限制的错误

语义错误三、填空题1、符号表中名字栏内容有两种填写方式，它们是填写和填写。2、词法剖析阶段的错误主假如，可经过的方法纠正错误。3、符号表中名字的有关信息在和过程中陆续填入。4、在目标代码生成阶段，符号表是的依照。四、问答题：1、在编译过程中为何要成立符号表单项选择解答：1、b2、d3、b4、c多项选择解答：1、a、c2、a、b、c3、a、b、c、e填空解答：1、表记符表记符地点及长度2、拼写错误

最小距离般配

3、词法剖析

语法语义剖析4、地点分派问答题解答：在编译过程中一直要波及到对一些语法符号的办理，这就需要用到语法符号的有关属性。为了在需要时能找到这些语法成分及其有关属性，就一定使用一些表格来保留这些语法成分及其属性，这些表格就是符号表。第九章一、单项选择题1、程序所需的数据空间在程序运转前可确立，称为a.动向储存b.栈式储存c.静态储存2、堆式动向分派申请和开释储存空间恪守原则。a.先请先放b.先请后放c.后请先放

管理技术。d.堆式储存d.随意3、静态分派同意程序出现。a.递归过程b.可变体积的数据项目

c.静态变量

d.待定性质的名字4、在编译方法中，动向储存分派的含义是

。在运转阶段对源程序中的数组、变量、参数等进行分派在编译阶段对源程序中的数组、变量、参数进行分派在编译阶段对源程序中的数组、变量、参数等进行分派，在运转时这些数组、变量、参数的地点可依据需要改变以上都不正确5、在编译时有传名功能的高级程序语言是。a.Fortran

b.Basic

c.Pascal

d.ALGOL6、栈式动向分派与管理在过程返回时应做的工作有。a.保护SPb.恢复SPc.保护TOPd.恢复二、多项选择题1、下边需要在运转阶段分派储存空间。a.数组b.指针变量c.动向数组d.静态变量e.动向变量2、栈式动向分派同意。a.递归过程b.分程序结构c.动向变量d.动向数组e.静态数组

TOP3、动向储存分派可采纳的分派方案有a.队式储存分派b.栈式储存分派d.堆式储存分派e.线性储存分派

。

c.链式储存分派4、