广工编译原理试题

1编译原理试题计算机学院_____级班学号姓名题号一二三四五六七八九十总分满分得分一选择题1有限状态自动机能识别：A.上下文无关语言B.上下文有关语言C.正规语言D.0型文法定义的语言2已知文法G是无二义的，则对G的任意句型α：A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能相同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导，但他们对应的语法树相同3______不是DFA的成分A.有穷字母表B.多个初始状态的集合C.多个终态的集合D.转换函数4有文法G＝({S},{a},{S::=SaS,S::=ε},S)，该文法是_________A.LL(1)文法B.二义性文法C.算符优先文法D.正规文法5有一语法制导翻译如下所示:S-bAb{print“1”}A-(B{print“2”}A-a{print“3”}B-Aa){print“4”}若输入序列为b(((aa)a)a)b,则采用自下而上的分析方法,则输出为:A.32224441B.34242421C.12424243D.34442212二判断题1、一个LL(l)文法一定是无二义的。2、逆波兰法表示的表达式亦称前缀式。----后缀式3、算符优先关系表不一定存在对应的优先函数。4、同心集的合并有可能产生“移进/归约”冲突。只能是归约/归约5、若主程序为0层,过程p层次为k，则p的DISPLAY表中就有k+1个元素。三填空题1、词法分析的任务是从__源程序_中识别出一个个__单词符号__。2、在LR(0)分析法中，若,βV*且aTV则称“S.A”为待约项目，称“S.aβ”2为移进项目。3、规范规约每次规约的是句型的____句柄__________。算符优先分析法每次规约的是当前句型的__最左素短语__________。四写一个文法，使其语言是奇数集，且每个奇数不以0开头。五已知文法G（S）：S→a|(T)T→T，S|S（1）给出句子（a，（a，a））的最左推导并画出语法树；（2）给出句型（（T，s）,a）的短语、直接短语、句柄。六把语句ifx＞0y＞0thenz：＝x＋yelseBeginx：＝x＋2y：＝y＋3End；翻译成四元式序列。七设文法G（S）：S→S＋aF|aF|＋aFF→*aF|*a（1）消除左递归和左因子；（2）构造相应的FIRST和Follow集合；（3）构造预测分析表。八为下面的文法构造它的LR(1)项目集规范族，并判断它是否为LR(1)文法？若是，请构造它的分析表。SEEE+T|TT(E)|a九下列文法是否为SLR(1)文法？若是，请构造相应的分析表。若不是，请说明理由。SSab|bRRS|a十文法S(L)|aLL,S|S(a)给出句子(a,((a,a),(a,a)))的一个最右推导；(b)按照(a)的最右推导，给出移进－归约分析器的工作步骤。3答案一选择题c,a,b,b,b二判断题√×√×√三填空题源程序单词符号待约项目移进项目句柄最左素短语四.解：文法G（S）：S→AB|B|A0A→AD|CB→2|4|6|8C→1|3|5|7|9|BD→0|C五（2）短语：（2分）（（T，S），a）（T，S），a（T，S）4T，Sa直接短语：（1分）T，Sa句柄：（1分）T，S六解：（1）（j＞0，x，0，3）（2）（j，－，－，8）（3）（j＞，y，0，5）（4）（j，－，－，8）（5）（＋，x，y，T1）（6）（：＝，T1，－，z）（7）（j，－，－，12）（8）（＋，x，2，T2）（9）（：＝，T2，－，x）（10）（＋，y，3，T3）（11）（：＝，T3，－，y）（12）七.解：（1）（消除左递归，提公因左因子）S→aFS'|＋aFS'S'→＋aFS'|εF→*aF'F'→F|ε（2）FIRST（S）＝｛a，十｝FOLLOW（S）＝｛＃｝FIRST（50）＝｛＋，ε｝FOLLOW（S'）＝｛＃｝FIRST（F）＝｛*｝FOLLoW（F）＝（＋，＃｝FIRST（F'）＝｛*，ε｝FOLLOW（＋，＃｝（3）八解：文法的拓广文法G’为：(0)S’S(1)SE(2)EE+T(3)ET5(4)T(E)(5)Ta该文法的LR(1)项目集规范族为：I0={[S’•S,$],[S•E,$],[E•E+T,$|+],[E•T,$|+],[T•(E),$|+],[T•a,$|+]}I1={[S’S•,$]}I2={[SE•,$],[EE•+T,$|+]}I3={[ET•,$|+]}I4={[T(•E),$|+],[E•E+T,)|+],[E•T,)|+],[T•(E),)|+],[T•a,)|+]}I5={[Ta•,$|+]}I6={[EE+•T,$|+],[T•(E),$|+],[T•a,$|+]}I7={[T(E•),$|+],[EE•+T,)|+]}I8={[ET•,)|+]}I9={[T(•E),)|+},[E•E+T,)|+],[E•T,)|+],[T•(E),)|+],[T•a,)|+]}I10={[Ta•,)|+]}I11={[EE+T•,$|+]}I12={[T(E)•,$|+]}I13={[EE+•T,)|+],[T•(E),)|+],[T•a,)|+]}I14={[T(E•),)|+],[EE•+T,)|+]}I15={[EE+T•,)|+]}I16={[T(E)•,)|+]}识别该文法所有活前缀的DFA如下图所示：I0I1I10I9I2I3I5I4I14I6I12I7I8I16I11I13I15Sa(ETa(a(+a(ETTE)+)T+T(a不存在冲突入口，∴该文法是LR(1)文法。构造LR(1)分析表如下：STATEactiongotoa+()$SET60S5S41231acc2S6r13r3r34S10S9785r5r56S5S4117S13S128r3r39S10S914810r5r511r2r212r4r413S10S91514S13S1615r2r216r4r4构造LALR文法如下：首先合并同心的项目集，I0={[S’•S,$],[S•E,$],[E•E+T,$|+],[E•T,$|+],[T••(E),$|+],[T•a,$|+]}I1={[S’S•,$]}I2={[SE•,$],[EE•+T,$|+]}I3,8={[ET•,$|+|)]}I4,9={[T(•E),$|+|)],[E•E+T,)|+],[E•T,)|+],[T•(E),)|+],[T•a,)|+]}I5,10={[Ta•,$|+|)]}I6,13={[EE+•T,$|+|)],[T•(E),$|+|)],[T•a,$|+|)]}I7,14={[T(E•),$|+|)],[EE•+T,)|+]}I11,15={[EE+T•,$|+|)]}I12,16={[T(E)•,$|+|)]}DFA如下图所示：7I1I0I4,9I2I3,8I5,10I7,14I6,13I11,15I12,16S((ETaa+TE)+a(T构造LALR分析表如下：STATAEactiongotoA+()$SET0S5,10S4,9123,81acc2S6,13r13,8r3r3r34,9S5,10S4,97,143,85,10r5r5r56,13S5,10S4,911,157,14S6,13S12,1611,15r2r2r212,16r4r4r4九.该文法的拓广文法G’为：(0)S’S(1)SSab(2)SbR(3)RS(4)Ra其LR(0)项目集规范族如下:I0:S’S·I3:SSa·bS·SabI4:SbR·S·bRI5:RS·SS·abI1:S’S·I6:Ra·SS·abI2:Sb·RI7:SSab·R·SR·aS·SabS·bR8文法G’的识别活前缀的DFA如下所示：SabRababSI0I1I2I3I5I4I7I6FOLLOW(S)=FOLLOW®={a,$}构造的SLR分析表如下：观察左表，对状态5，可归纳又可移进，即存在为重定义的入口。所以，该文法不是SLR(1)文法。十.(a)S(L)(L,S)(L,(L))(L,(L,S))(L,(L,(L)))(L,(L,(L,S)))(L,(L,(L,a)))(L,(L,(S,a)))(L,(L,(a,a)))(L,(S,(a,a)))(L,((L),(a,a)))(L,((L,S),(a,a)))(L,((L,a),(a,a)))(L,((S,a),(a,a)))(L,((a,a),(a,a)))(S,((a,a),(a,a)))(a,((a,a),(a,a)))(注：下划线部分为句柄)(b)步骤栈输入动作1$(a,((a,a),(a,a)))$移进2$(a,((a,a),(a,a)))$移进3$(a,((a,a),(a,a)))$归约，Sa4$(S,((a,a),(a,a)))$归约，LS5$(L,((a,a),(a,a)))$移进6$(L,((a,a),(a,a)))$移进7$(L,((a,a),(a,a)))$移进8$(L,((a,a),(a,a)))$移进9$(L,((a,a),(a,a)))$归约，Sa10$(L,((S,a),(a,a)))$归约，LS11$(L,((L,a),(a,a)))$移进12$(L,((L,a),(a,a)))$移进13$(L,((L,a),(a,a)))$归约，Sa状态actiongotoab$SR0S211S3acc2S6S2543S74r2r25r3/S3r36r4r47r1r1914$(L,((L,S),(a,a)))$归约，LL,S15$(L,((L),(a,a)))$移进16$(L,((L),(a,a)))$归约，S(L)17$(L,(S,(a,a)))$归约，LS18$(L,(L,(a,a)))$移进19$(L,(L,(a,a)))$移进20$(L,(L,(a,a)))$移进21$(L,(L,(a,a)))$归约，Sa22$(L,(L,(S,a)))$归约，LS23$(L,(L,(L,a)))$移进24$(L,(L,(L,a)))$移进25$(L,(L,(L,a)))$归约，Sa26$(L,(L,(L,S)))$归约，LL,S27$(L,(L,(L)))$移进28$(L,(L,(L)))$归约，S(L)29$(L,(L,S))$归约，LL,S30$(L,(L))$移进31$(L,(L))$归约，S(L)32$(L,S)$归约，LL,S33$(L)$移进34$(L)$归约，S(L)35$S$接受