编译原理—应用题

题型一四、现有文法G[E]：(共10分)E→E+T|E-T|TT→T*F|T/F|FF→i|(E)1、证明：E-F*(i)是文法的一个句型。(3分)2、构造句型E-F*(i)的语法推导树。(2分)1、指出该句型所有短语、直接短语和句柄。(5分)第四题：（10分）1、证明（3分）：因为存在推导序列E=E-T=E-T*F=E-F*F=E-F*(E)=E-F*(T)=E-F*(F)=E-F*(i)，即有E*E-F*(i)成立，所以，E-F*(i)是文法的一个句型。2、语法树（2分）：3、句型分析（5分）句型E-F*(i)相对于E的短语有:E-F*(i),i。句型E-F*(i)相对于T的短语有:F*(i),F，i。句型E-F*(i)相对于F的短语有:(i),i。（3分）句型E-F*(i)相对于T→F的直接短语有:F。EE-TT*FF（E）TFi句型E-F*(i)相对于F→i的直接短语有:i。（2分）句型E-F*(i)的句柄为:F。（1分）三、现有文法G[E]：(共12分)E→E+T|E-T|TT→T*F|T/F|FF→i|(E)3、证明：F+T*(E)是文法的一个句型。(3分)4、构造句型F+T*(E)的语法推导树。(3分)5、指出该句型所有短语、直接短语和句柄。(6分)第三题：（12分）2、证明（3分）：因为存在推导序列E=E+T=T+T=F+T=F+T*F=F+T*(E)，即有E*F+T*(E)成立，所以，F+T*(E)是文法的一个句型。2、语法树（3分）3、句型分析（6分）句型F+T*(E)相对于E的短语有:F+T*(E),F。句型F+T*(E)相对于T的短语有:F,T*(E)。句型F+T*(E)相对于F的短语有:(E)。（3分）句型F+T*(E)相对于T→F的直接短语有:F。句型F+T*(E)相对于F→(E)的直接短语有:(E)。（2分）EE+TTT*FF（E）句型F+T*(E)的句柄为:F。（1分）1、有文法G[S]：(12分)S→aAS|aA→SbA|SS|ba(1)证明aabbaa是文法的一个句子。(3分)(2)构造句子aabbaa的语法树。(3分)(3)指出该句子的所有短语、直接短语和句柄。(6分)答：（1）证明(3分)：因为存在推导序列S=aAS=aSbAS=aabAS=aabbaS=aabbaa，即有S=*aabbaa成立，所以，是文法的一个句子。（2）语法树（3分）：（3）句型分析（6分）：将句型改写为a1a2b1b2a3a4，则：该句型相对于S的短语：a1a2b1b2a3a4和a4；相对于A的短语：a2b1b2a3和b2a3；对于S→a的直接短语：a2，a4；相对于A→ba的直接短语：b2a3；句柄：a2。1、有文法G[E]：(16分)E→T+E｜TT→T*F｜FF→(E)｜i(1)证明T+T*F+i是文法的一个句型。(3分)(2)构造型T+T*F+i的语法树。(3分)(3)指出该句型的所有短语、直接短语和句柄。(7分)(4)指出该句型的所有素短语和最左素短语。(3分)答：1）证明(3分)：因为存在推导序列：E=T+E=T+T+E=T+T*F+E=T+T*F+T=T+T*F+F=T+T*F+i，即有E=*T+T*F+i成立，所以，T+T*F+i是文法的一个句型。（2）语法树（3分）：（3）句型分析（7分）：该句型相对于E的短语：T+T*F+i、T*F+i和i；相对于T的短语有：T*F和i，相对于F的短语有i。相对于T→T*F的直接短语：T*F,相对于F→i的直接短语：i。句柄：T*F。(4)该句型的所有素短语：T*F和I；T*F为最左素短语。(3分)二、现有文法G[S]：(共10分)S→SS*S→SS+S→a6、证明aa+a*是文法的一个句子。(2分)7、构造句型aa+a*的语法推导树。(2分)8、指出该句型所有短语、直接短语和句柄。(6分)第二题：（10分）3、证明（3分）：因为存在推导序列S=SS*=SS+S*=aS+S*=aa+S*=aa+a*，即有S*aa+a*成立，且aa+a*全部由终结符构成，所以aa+a*是文法的一个句子。2、语法树（2分）：SSS*SS+a3a1a23、句型分析（5分）句型aa+a*相对于S的短语有:a1a2+a3*,a1a2+,a1,a2,a3。（2分）句型aa+a*相对于S→a的直接短语有:a或a1,a2,a3。（2分）句型aa+a*的句柄为:a1。（1分）三、现有文法G[E]：(共12分)E→EE+E→EE*E→FF→i9、证明ii*i+是文法的一个句子。(3分)10、构造句型ii*i+的语法推导树。(3分)11、指出该句型所有短语、直接短语和句柄。(6分)第三题：（12分）1、证明（3分）：因为存在推导序列E=EE+=EE*E+=FE*E+=iE*E+=iF*E+=ii*E+=ii*F+=ii*i+，即有E*ii*i+成立（2分），且ii*i+所含符号全部为终结符（1分），所以，ii*i+是文法的一个句子。2、语法树（3分）3、句型分析（6分）句型ii*i+相对于E的短语有:i1i2*i3+,i1i2*,i1,i2,i3（3分）句型ii*i+相对于F的短语有:i1,i2,i3（1分）句型ii*i+相对于F→i的直接短语有:i或i1,i2,i3（1分）句型ii*i+的句柄为:i1（1分）说明：（1）短语、直接短语的说明可不具体指明所相对的非终结符或规则。（2）没用下标区分i1,i2,i3的扣1分。（3）短语每错两个扣1分。EEE+EE*FFFi3i1i2题型二三、给定正规式R=(01|10)(01|10)*，要求：(10分)2、构造对应的正规文法G，使得L(G)=L(R)。(4分)3、构造对应的NFAM状态图，使得L(M)=L(R)。(3分)3、将所得NFAM确定化为DFA。(3分)第三题：（10分）1、正规文法G[S]（4分）：S→0A|1BA→1S|1B→0S|02、NFA（3分）：3、DFA（3分）：步骤如下表所示（可省）：标记新状态I0I1T0{S}{A}{B}T1{A}φ{S,Z}T2{B}{S,Z}φT3{S,Z}{A}{B}将集合T0至T3各用一个状态表示，确定化后所得DFAM如下：四、给定正规式R=d(a|bc)*d，要求：(12分)4、构造对应的NFAM状态图，使得L(M)=L(R)。(4分)5、将所得NFAM确定化和最小化。(8分)第四题：（12分）1、NFAM（4分）2、(1)确定化（4分）步骤如下表所示（可省）：标记新状态IaIbIcIdT0{1}φφφ{2,4}T1{2,4}{2,4}{3}φ{5}T2{3}φφ{2,4}φT3{5}φφφφ将集合T0至T3各用一个状态表示，确定化后所得DFAM如下：(2)最小化（4分）步骤如下表所示（可省）：步骤分割根据分割结果1是否终态P1={1，2，3}；P2={4}2P1根据d弧映射P11={1}；P12={2}；P13={3}最后还有4个不可再分割的子集，每个子集中只包含一个状态，即原DFAM已经是最小化DFA。说明：此大题答案只供参考，可以是其他答案，只要功能等价即可。3、有正规文法G[S]：(12分)S→aA|bBA→bS|bB→aS|a(1)构造对应的正规式R，使得L(R)=L(G)。(3分)(2)构造对应的NFA状态图，使得L(M)=L(R)。(3分)(3)将所得NFA确定化为DFA。(3分)(4)将所得DFA最小化。(3分)答：(1)代入后有S的规则右部=a（bS|b）|b(aS|a)=ab（S|ε）|ba（S|ε）=（ab|ba）（S|ε）,故对应的正规式R=(ab|ba)(ab|ba)*。(3分)(2)对应的NFA状态图如下左图所示：(3分)(3)将所得NFA确定化为DFA状态图如上右图所示：(3分)(4)将所得DFA最小化：首先根据是否终态划分为非终态集P1={S,A,B}和终态集P2={Z}；然后对P1根据a弧划分为P11={S},P12={A}，P13={B}。可见原DFA已是最小化的DFA。(3分)三、给定正规式R=0(0|1)0*1，要求：(12分)1、构造对应的NFAM状态图，使得L(M)=L(R)。(4分)2、将所得NFAM确定化和最小化。(8分)第三题：（12分）1、NFA（4分）：2、确定化（4分）：标记新状态I0I1T0{A}{B,C,E}φT1{B,C,E}{D,G}{F,G}T2{D,G}{G}{H}T3{F,G}{G}{H}T4{G}{G}{H}T5{H}φφ将集合T0至T5各用一个状态表示，确定化后所得DFAM如下：3、最小化（4分）：步骤如下表所示（可省）：步骤分割根据分割结果1是否终态P1={A,B,C,D,E}；P2={F}2P1根据1弧映射P11={A}；P12={B}；P13={C,D,E}最后有四个不可再分割的子集，每个子集对应一个状态，即有最小化DFA如下：说明：此大题答案只供参考，可以是其他答案，只要功能等价即可。四、将正规式R=bb(a|bb)a*b转换为相应的NFAM状态图，使得L(M)=L(R)，并将所得NFAM确定化和最小化。(12分)第四题：（12分）1、NFAM（3分）2、确定化（3分）步骤如下表所示（可省）：标记新状态IaIbT0{1}φ{2}T1{2}φ{3,4,6}T2{3,4,6}{5,9}{7}T3{5,9}{9}{10}T4{7}φ{8,9}T5{9}{9}{10}T6{10}φφT7{8,9}{9}{10}将集合T0至T7各用一个状态表示，确定化后所得DFAM如下：3、最小化（3分）步骤如下表所示（可省）：步骤分割根据分割结果1是否终态P1={1，2，3，4，5，6，8}；P2={7}2P1根据a弧映射P11={3，4，6，8}；P12={1，2，5}3P11根据b弧映射P111={3}；P112={4，6，8}4P12根据b弧映射P121={1}；{2}；P122={5}最后有六个不可再分割的子集，每个子集对应一个状态，得最小化DFA如下：说明：此大题答案只供参考，可以是其他答案，只要功能等价即可。题型三五、任意给定一个文法G[S]：(10分)1、给出判断G[S]是否为LL(1)文法的步骤。(4分)2、如果G[S]是LL(1)文法，怎样构造它的预测分析表？(3分)3、怎样根据预测分析表对给定的某个输入串进行预测分析？(3分)第五题：(10分)对任意给定的一个文法G[S]：1、判断是否为LL(1)文法的步骤：(4分)1）画出各非终结符能否推导出ε的情况表。2）用定义法或关系图法计算FIRST、FOLLOW集。3）计算各规则的SELECT集。4）检查所有左部相同的规则的SELECT集是否相交，如果不相交，则G[S]为LL(1)文法。否则，说明G[S]不是LL(1)文法。2、构造G[S]预测分析表：(3分)预测分析表为一个二维矩阵,其形式为M[A,a],其中A∈VN,a∈VT或#。对文法中的规则A→α,若有终结符a∈SELECT(A→α),则将A→α填入M[A,a]中。(书写时，通常省略规则左部，只填→α)。对所有没有值的M[A,a]标记为出错。3、根据预测分析表M对给定的某个输入串进行预测分析的过程，可用下述算法表示：(3分)#,S进栈;//初始化工作，S为开始符do{X=当前栈顶符号;a=当前输入符号；if(X∈ＶT∪{#}){if(X==a){if(X!=#){将X弹出,且前移输入指针}}elseerror()}else{if(M[X,a]==Y1Y2…Yk){将X弹出;依次Yk…Y2Y1将压入栈;}elseerror()};}while(X!=#);说明：此答案只供参考，可以是其他答案，只要意思相近即可。六、已知G[S]：(18分)S→(A)|a|bA→A,S|S1、给出(a,(b,b))的最左推导。(3分)2、判断该文法是否为LL(1)文法。若是，直接给出它的预测分析表；若不是，先将其改写为LL(1)文法，再给出它的