编译原理期末试卷.doc

编译原理期中试卷1简答题（每题5分，共计15分）(1) 简述编译程序的概念及构成。编译程序是将高级语言程序翻译成等价的低级语言的翻译程序程序。编译程序的构成:(2) 什么是文法？（在编译原理课程中，文法可以认为是上下文无关文法）一个文法G是一个四元组(VN，VT，P，S)，其中： (1) VT是一个非空有穷终结符号集合； (2) VN 是一个非空有穷的非终结符号集合， 且VT VN ； (3) S VN开始符号。 (4) P是一个规则的非空有穷集合，每个产生式的形式是A:=，其中 A VN ，(VT VN )* ，开始符号S至必须在某个产生式的左部出现一次。(3) 自顶向下的语法分析和自底向上的语法分析解决的核心问题分别是什么？自顶向下的语法分析解决的核心问题是：（1） 消除左递归 (2) 避免回溯自底向上的语法分析解决的核心问题是： 寻找句柄2文法GE: E:=T|E+T|E-T T:=F|T*F|T/F F:=(E)|i给出句型i+T*F*i的短语与直接短语(简单短语)、句柄和最左素短语。 （10分）短语：i+T*F*i，T*F, T*F*i, i1, i2直接短语(简单短语)：i1,i2句柄：i1最左素短语：i13按指定类型给出下列语言的文法,并指出语言的类型。（每个5分，共10分）(1) L1= anbm| n0,m0 S:= aS|bS|b(2) L2= 0na1nbmcm| n0，m 0S:=AB A:=0A1|0a1 B:=bBc|4构造正则式a *b|(ab) *b对应的DFA并最小化。（要求步骤清楚，15分） 1 b 0 a 6 2 a 3 b 4 b 5abSABACDBCCDEBEFFEF IaIb0,1,2,4S1,35,61,3A12,4,65,6B1C12,4,6D35,63E2,42,4F35,65. 请在划线处填空。（5分）BEGIN /* Start Algorithms */ (1) PUSH(#),PUSH(S);把第一个输入符号读进b; FLAG = TRUE；WHILE FLAG DOBEGIN 把栈顶符号上托出去并放在X中； IF X Vt THEN IF X=b THEN 把下一个输入符号读进a ELSE ERRORELSE IF X=# THEN FLAG = FALSE ELSE ERRORELSE IF MX,b=X X1X2XK THEN (2) 将XkXk-1X1入栈 ELSEERROREND /* End Of While */END /* End of Algorithms */6为文法GE： E := E+V | V V := Na | NE N := i 构造递归下降识别程序（15分）构造程序（略，注意判断预测的符号）7请给出文法的First和Follow集合，若是LL(1)文法，给出分析表并分析句子abbe。（15分）GS: S:=aD D:= Te| T:=bH H:=D|略8文法GE： (1) ET+T (2) ET or T (3) Tn (4) T b，对应的LR(0)分析表如图，状态ActionGOTO+ornb#ET0s4s3121acc2s5s73r4r4r4r4r44r3r3r3r3r35s4s366r1r1r1r1r17s4s388r2r2r2r2r2 依据右边的表格格式，写出分析n + b or n的过程。（10分）答题格式如下：步骤符号栈状态栈输入串动作1#0n+born#Shift S42#n04+born#Reduce R33#T02+born#Shift S54#T+025b or n#Shift S35#T+b0253or n#Reduce R46#T+T0256or n#Reduce R17#E01Error 9. Chomsky文法分类将文法分为几类，分别什么文法？（5分）0型文法(短语结构文法PSG): u:=v ，其中: u (VNVT)+, v (VNVT)* 1型文法(上下文有关文法CSG): xUy:=xuy，其中: UVN,x, y(VNVT)*, u(VNVT)+ 2型文法(上下文无关文法CFG) : U:=xuy，其中: U