东师《编译原理》练习题一

编译原理练习题一、选择题.下列文法中，—C不是产生语言｛abna∣n≥1｝的文法。A.A→aBa B→b∣bB B.A-aB B-ba∣bBC.A→aB B-ba∣bBa D.A→aB B→bC C→bC∣a.设有文法G［S］：S→aAB A-bAc∣ε B-bB∣Ae∣ε则经消去ε-产生式后与G等价的文法G1［S］为A。S→aA∣aB∣aAB∣aA→bc∣bAcB-bB∣Ae∣b∣eS→aAB A→bAc B-bB∣AeS→aA∣aBA→bcB-b∣eS→aA∣aB∣aA→bc∣bAcB-bB∣Ae∣b∣e.下列文法中，D是LL⑴文法。S→bBS'aS'-aBS/∣εA→S∣a B→AcS→bS∣bA∣bA→aA∣aE→E+T∣TT→T*F∣FF→(E)∣iS→bBS'S'-aBS/∣εA→S∣a B→Ac.下列文法中，_D是简单优先文法。E→E+T∣TT-T*F∣FF-(E)∣iS→A/A→aA∣AS∣/E→E+E∣E*E∣(E)∣iE→E1E1→E1+T1∣T1 T1→TT-T*F∣FF-(E)∣i.当扫视到数组说明进行语义处理时，必须把一个数组的如维数、各维的上、下界等记录下来。为了便于引用，通常是把上述内容存放于数组相应的—B之中。A.信息向量B.内情向量C.地址向量D.指针向6.设有文法G[S]：S→aS∣W∣UU→aV→bV∣ac W→aW则经化简后与G等价的文法GJS］为BS→aS∣W V→bV∣acW→aWS→aS∣U U→aS→aS∣W∣UU→a W→aWD.S→aSV→bV∣ac.下列文法中，D是LL(1)文法。S→aS∣aA A-bA∣acS→AS∣b A→SA∣aC.E→E+E∣E*E∣(E)∣iD.S→aS∣bA A→bA∣ac.所谓相容，是指在一个项目集中，不出现这样的情况，—A和归约项目并存，或多个归约项目并存。A.移进项目B.基本项目C.待约项目D.后继项目.下列表示中，C不是目前经常使用的中间语言的形式。A.逆波兰式B.四元式C.五元式D.树形表示10.如果从流程图的首结点到流程图中某一结点n的所有通路都要经过结点d,我们就说结点d控制了结点n,或者把d称为n的必经结点，记作BA.dDFAnB.dDOMnC.dDAGnD.dDAMn二、证明题1、试证明文法S→aB∣bAA→aS∣bAA∣aB→aBB∣bS∣b为二义性文法。证明：因为文法G[S]的一个句子aaabaaba对应如下的两个最左推导序列：SnaBnaaBBnaabSBnaabbABnaabbaBnaabbabSnaBnaaBBnaabBnaabbSnaabbaBnaabbab所以文法G[S]为二义性文法。三、简答题对于如下文法，求各候选式的FIRST集和各非终结符号的FOLLOW集。S→ACAB∣bA∣ε A-aAd∣eB-bB∣cC-cC∣1、解：文法G[S]的各候选式的FIRST集和各非终结符号的FOLLOW集如表所示。产生式FIRSTFOLLOWS→ACABS→bA{a,e}{b}{#}A→aAdA→e{e}{a,b,c,e,#}B→bBB→c{b}{c}{#}C→cCC→ε{c}{ε}{a,e}四、应用题1、对于如下的状态转换矩阵ΞABCDA AB CAAADA初态：Ξ终态：BjCjD分别画出相应的状态转换图；(10分)(2)写出相应的3型文法。1、解：(1)相应的状态转换图如图所示:(2)相应的3型文法为:S→aA∣bA∣cAA→aB∣bC∣cD∣a∣b∣cB→aAC→bAD→cA2、将如图所示的DFA最小化。解：现将DFAM最小化：(i)初始分划由两个子集组成，即：∏0N1,2,4},{3,5}(ii)为得到下一分划，考察子集{1,2,4}。因为{1}a={3}u{3,5}而 {2,4}a={4}u{1,2,4}故1与2,4可区分，于是便得到下一分划：∏1:{1},{2,4},{3,5}(iii)为得到下一分划，考察子集{3,5}。因为{3}a={5}a={4}又因为⑶b={3}u{3,5}, {5}b={5}u{3,5}故3和5等价，于是得到的下一分划与∏1相同：∏2:{1},{2,4},{3,5}(iv)再考察子集{2,4},因为{2}a={4}a={4}又因为{2}b={5}, {4}b={3},且3与5等价，故2和4等价，于是得到的下一分划与∏2相同：∏3:{1},{2,4},{3,5}此时子集已全部分裂，故最小化的过程宣告结束。(V)现选择状态4作为{2,4}的代表，状态3作为{3,5}的代表，将状态2,5从状态转换图中删去，并将原来引至2的矢线都引至4,将原来引至5的矢线都引至3,这样，我们就得到了最小化后的DFA 如下图所示。五、应用题1、设有文法G[E]： E→E+rT T→T*F∣F F→(E)|i其相应的算符优先矩阵如下图所示，试给出对符号串i*i+i进行算符优先分析的过程。( i * + ) #(QQQQQQQQ*QQQQQQ-QQQQQQ-QQQ Q-二QQQQ1、解：对符号串i*i+i进行算符优先分析的过程如下表所示。因为分析成功，所以符号串i*i+i是文法G[E]的合法句子。步骤分析栈当前栈顶终结符号优先关系当前输入符号余留输入串最左素短语0##Qi*i+i#1#QiiQ*i+i#i2#F#Q*i+i#3#Qf**Qi+i#4#Qf*QiiQ+i#i5#Qf*f*Q+i#F*F6#T#Q+i#7#Qt++Qi#8#Qt+QiiQ#i9#Qt+f+Q#T+F10#E##分析成功2、试描述由文法：S→aAd A→aAd∣bBcB→bBc∣e 所产生的语言。解：产生的语言为：L(G)={anbmeCmdn∣m,n≥1}六、应用题1、设有文法G[S]：S→aABb A→Acd∣dB→Bce∣e(1)将其改写为LL⑴文法；1、解：(1)消除A-产生式和B-产生式中的直接递归性后，我们便得到了与原文法等价的文法G'[S]：S→aABbA→dAzAz→cdAz∣εB→eBzBz→ceBz|ε文法G'[S]的各候选式的FIRST集和各非终结符号的FOLLOW集如下表所示:产生式FIRSTFOLLOWS→aABb{a}{#}A→dA,{d}{e}A-cdA，A'→ε{c}{ε}{e}B→eB,{e}{b}B,→ceB∕B'→ε{c}{ε}{b}下面来验证文法G'[S]是否是LL⑴文法。对于文法G'[S]，因为有：对于产生式A‘→cdA'∣ε，有FIRST(CdA')∩FOLLOW(A')={c}∩{e}二0；对于产生式B'fceB'|£，有FIRST(CeB')∩FOLLOW(B′)={c}∩{b}=0；所以文法G'[S]即为所求的与G等价的LL(1)文法。(2)构造改写后文法的LL⑴分析表。(2)文法G/[S]的LL(1)分析表如下表所示:abcde#SS→aABbAA→dA,A’A'→cdA'A'→εBB→eB'B，B'→εB'→ceB'2、已知文法G[S]：S-aABA-bA∣aB-cB∣b 的LR(0)项目集及状态转换图如下图所示，(1)构造LR(0)分析表； (2)给出对输入符号串abacb的LR分析过程。解：(1)给文法G[S]的各产生式添加编号如下:0.S'→S 3.A→a1.S→aAB 4.B→cB2.A→bA 5.B→b则文法G[S]的LR(O)分析表如下表所示：状态ACTIONGOTOabC#SAB0S211acc2S5s433S8S764S5S495r3r3r3r36r1r1r1r1710「2「2「4;r2r4r5r2r410(2)对输入符号串abacb的LR分析过程如下表所示。因为分析成功，所以符号串abacb是文法G[S]的合法句子。步骤状态栈符号栈余留输入串分析动作下一状态1I0#abacb#S2221012#abacb#S443101214#abacb#S55410121415#abacb#r3GOTO[I4,A]=9510121419#abAcb#r2GOTO[I2,A]=36101213 #aAcb#S77710121317#aAcb#S7871012131718#aAcb#r5GOTO[I7,B]=10910121317110#aAcB#r4GOTO[I3,B]=61010121316#aAB#r1GOTO[I0,S]=111iJ#S#acc七、简答题1、设有二维PASCAL数组A[1・・10,1・∙20],给出赋值语句 A[I,J]:=X+Y*Z的四元式序列。1、解：相应的四元式序列为：(*,I,20,T1)(+,J,T1,T1)(-,a,C,T2)(*,Y,Z,T3)(+,X,T3,T4)([]=,T4,0,T2[T1])2、将逆波兰式：ABCD/-*EF*+改写为中缀式。解：相应的中缀式为：A*(B-C/D)+E*F八、简答题1、设有如下的三地址码(四元式)序列：A:=5I:=1J:=2L1:ifI≤JgotoL3X:=I*AL2: I:=I-JifI