编译原理题目模拟gai.doc

一、选择题：1.扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位是_。A 字符 B单词 C句子 D句型2编译程序前三个阶段完成的工作是_。A词法分析、语法分析和代码优化 B代码生成、代码优化和词法分析C词法分析、语法分析、语义分析和中间代码生成 D词法分析、语法分析和代码优化3语法分析所依据的是_。A 语义规则 B 词法规则 C 语法规则 D 等价变换规则4对应Chomsky四种文法的四种语言之间的关系是A L0L1L2L3 B L3L2L1L0C L3=L2L1L0 D L0L1L2=L35.给定文法G: AAb|cc，试问在下面的符号中,为该文法句子的是_.A ccbb B bcbcc C bccbcc D cbbcc6属于自上而下分析法的是（ ）A LL（1） B LR（0） C SLR D 算符优先 7在自下而上的语法分析中，应从 开始分析。A 最左素短语 B 句子 C文法的开始符号 D句柄二、简答题：1.在自上而下语法分析中遇到的问题是什么，又是如何对其进行分析解决的？答：在自上而下语法分析中遇到的问题是左递归与回溯问题，可以对其进行消除，如果能够判断其是LL（1）文法，则对其分析的每一步都是确定无疑的。2.什么是属性文法？属性分哪几类？答：属性文法是在文法的基础上，为每个文法符号配备若干相关的值称为属性，这些属性代表与文法符号相关的信息。属性文法包含S属性文法和L属性文法。（3分）3.给出下面两式的后缀式形式：1）a*(-b+c) 2）not A and B or C答：1） a buminus c+* 2) A not B and C or三、综合题：1.请给出在=a,b上b(a|b)*aa的DFA。(1) 构造NFA； （2）对NFA确定化得到DFA。 1)得到NFA （4分） 2） NFA转换成DFA 状态转换矩阵为：（4分） I Ia IbX-111,211,21,2,Y11,2,Y1,2,Y1重新命名后为：表格 1 （3分）Sab0-1121231331SBbBSab2.对于文法GS：SAB，AAa|bB，Ba|Sb求句型baSb的全部短语、直接短语和句柄。 A短语：a ba Sb baSb直接短语：a Sb句柄：a 规范规约的依据素短语：a Sb 最左素短语：a 算符优先分析法的依据3.对文法G(V): VN|NE EV|V+E Ni要求：1）消除回溯（公共左因子）；2）求出各非终结符的first集和follow集；3)判断改造后的方法是否是LL（1）文法。要求构造预测分析表。(12分)解：1）LL（1）文法的基本条件是不含左递归和回溯，而文法G中含在回溯，所以先消除回溯得到文法G(V)：（2分） First(V)= , First(E)= , +First（N）=iFirst(V)=iFirst(E)= iFollow(V)=#, ,+ Follow(N)= ,#, ,+Follow(V)在follow(V)中=,follow(V)=#, ,+Follow(E)= Follow(E)= VNV V|E EVE E|+E Ni2）求的first和follow集：（8分）First(N)=First(V)=first(E)=i;First(V)=, ;First(E)=+, ;Follow(V)=#，+Follow(V)=#,+Follow(E)= Follow(N)= ，#，+Follow(E)= 3）改造后的文法是LL（1）文法。 （2分）4）构造其预测分析表+i#VV-NVNN-iVV-EV-V-V-EV-NVEE -E-+EFirstVT(B)= (,)firstVT(A)= (,+,)firstVT(S)= (,+,),iLastVT(B)= (,*LastVT(A)= (,*,+LastVT(S)= i, (,*,+,4. （11分）设文法G(S)：1)构造各非终结符的FIRSTVT和LASTVT集合；2)构造优先关系表。i+*()i()=b and cd or ef的四元式序列，要求给出简单过程。(1)EE1 and M E2 backpatch(E1truelist,M.quad);E.truelist:=,E2.truelist)E.falselist:=merge(E1.falselist, E2.falselist ) (2) EE1 or M E2 backpatch(E1.falselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist)E.falselist:=E2.falselist (3)E1id1 relop id2 E.truelist:= makelist(nextquad);E.falselist:=makelist(nextquad+1);Emit(j relop.op , id1.place , id2.place , 0 );Emit(j,-,-,0)(4)M M.quad:=nextquad四元式序列为：（6分）100 （j，a，b，102）101 （j，-，-，104）102 (j，c，d，0)103 （j，-，-，104）104 (j，e，f，0)105 (j，-，-，0）课后习题讲解：P811.S-a|(T)T-T,S|S(1)消去G1的左递归，然后对每个非终结符号，写出不带回溯的递归子程序。解1：分析：从产生式S-a|(T)可以看出，不会形成间接递归，运用消除直接递归的方法，如下：S-a|(T)T-STT-,S T|其不带回溯的递归子程序如下：Procedure SIf sym=athen Advance;Else if sym= then Advance;Else if sym=( then BeginAdvance;T;If sym=) then advance;Else error;EndElse error;Procedure TBeginS,TEndProcedure TIf sym=,then BeginAdvance;S,T;end解2：运用递归消除算法对S,T排序，首先消掉S（第一个非终结符）的直接左递归，这里没有，故缺省，得到S-a|(T)然后，一次消掉后面非终结符号的左递归，对T-T,S|S中的T-S等价代换，得到T-T,S| a|(T)再消掉上面式子的直接左递归，得到T-aT|T|(T)TT-,ST|这样，消除左递归后的产生式为S-a|(T)T-aT|T|(T)TT-,ST|该产生式的递归下降子程序我们参考上面的进行书写即可。上述两种方法都是正确的求解方法，第二种方法繁琐一些，但容易寻找到其first和follow集（2）判断是否是LL(1)，给出其预测分析表先求解其first集First(S)=a, , ( follow(S)=#, )First(T)= a, , (follow(T)= )Fi