编译原理―应用题.docVIP

题型一 四、现有文法G[E]： (共10分) E→E+T|E-T|T T→T*F|T/F|F F→i|(E) 证明：E-F*(i)是文法的一个句型。(3分) 构造句型E-F*(i)的语法推导树。(2分) 指出该句型所有短语、直接短语和句柄。(5分) 第四题：（10分） 证明（3分）：因为存在推导序列E=E-T=E-T*F=E-F*F=E- F*(E) =E- F*(T)=E-F*(F)=E-F*(i)，即有EE-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 。 　句型E-F*(i)相对于F→i的直接短语有: i 。（2分） 句型E-F*(i)的句柄为: F。 （1分） 三、现有文法G[E]： (共12分) E→E+T|E-T|T T→T*F|T/F|F F→i|(E) 证明：F+T*(E)是文法的一个句型。(3分) 构造句型F+T*(E)的语法推导树。(3分) 指出该句型所有短语、直接短语和句柄。(6分) 第三题：（12分） 　证明（3分）：因为存在推导序列E = E+T = T+T =F+T =F+T*F = F+T*(E)，即有 EF+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分） 　句型F+T*(E)的句柄为: F。 （1分） 1、有文法G[S]：(12分) S→aAS|a A→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｜T T → T * F｜F F → ( 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→a 证明aa+a*是文法的一个句子。(2分) 构造句型aa+a*的语法推导树。(2分) 指出该句型所有短语、直接短语和句柄。(6分) 第二题：（10分） 证明（3分）：因为存在推导序列S=SS*=SS+S*=aS+S* =aa+S*=aa+a*，即有 Saa+a*成立，且aa+a*全部由终结符构成，所以aa+a*是文法的一个句子。 2、语法树（2分）： S S S * 　 S S + a3 a1 a2 3、句型分析（5分） 句型aa+a*相对于S的短语有: a1a2+a3*, a1a2+, a1,a2,a3。（2分） 句型aa+a*相对于S→a的直接短语有: a或 a1,a2,a3。（2分） 句型aa+