2022年编译原理期末试 .pdf

《2022年编译原理期末试 .pdf》由会员分享，可在线阅读，更多相关《2022年编译原理期末试 .pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理期中试卷1简答题（每题5 分，共计 15 分）(1)简述编译程序的概念及构成。编译程序是将高级语言程序翻译成等价的低级语言的翻译程序程序。编译程序的构成:(2)什么是文法？（在编译原理课程中，文法可以认为是上下文无关文法）一个文法 G是一个四元组(VN，VT，P，S)，其中：(1)VT是一个非空有穷终结符号集合；(2)VN 是一个非空有穷的非终结符号集合，且 VT VN ；开始符号。(4)P是一个规则的非空有穷集合，每个产生式的形式是A:=，其中 A VN，(VT VN)*，开始符号S至必须在某个产生式的左部出现一次。(3)自顶向下的语法分析和自底向上的语法分析解决的核心问题分别是什么

2、？自顶向下的语法分析解决的核心问题是：（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 最左素短语：i1 3按指定类型给出下列语言的文法,并指出语言的类型。（每个5 分，共 10 分）(1)L1=anbm|n 0,m0 S:=aS|bS|b 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 4

3、 页 -(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 5 Ia Ib 0,1,2,4S 1,3 5,6 1,3A 1 2,4,6 5,6B 1C 1 2,4,6D 3 5,6 3E 2,4 2,4F 3 5,6 a b S A B A C D B C C D E B E F F E F 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 4 页 -5.请在划线处填空。（5 分）BEGIN/*Start Algor

4、ithms*/(1)PUSH(#),PUSH(S);把第一个输入符号读进b;FLAG=TRUE；WHILE FLAG DO BEGIN 把栈顶符号上托出去并放在X中；IF X Vt THEN IF X=b THEN 把下一个输入符号读进a ELSE ERROR ELSE IF X=#THENFLAG=FALSE ELSE ERROR ELSE IF X,b=X X1X2 XK THEN(2)将 XkXk-1X1入栈ELSEERROR END/*End Of While*/END/*End of Algorithms*/6为文法 GE：E:=E+V|V V:=Na|NE N:=i 构造递归下降识

5、别程序（15 分）构造程序（略，注意判断预测的符号）7请给出文法的First和 Follow 集合，若是 LL(1)文法，给出分析表并分析句子 abbe。（15分）GS:S:=aD D:=Te|T:=bH H:=D|略名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 4 页 -8文法 GE：(1)ET+T (2)ET or T (3)Tn (4)T b，对应的 LR(0)分析表如图，状态Action GOTO+or n b#E T 0 s4 s3 1 2 1 acc 2 s5 s7 3 r4 r4 r4 r4 r4 4 r3 r3 r3 r3 r3 5 s4 s3 6 6 r1 r

6、1 r1 r1 r1 7 s4 s3 8 8 r2 r2 r2 r2 r2 依据右边的表格格式，写出分析n+b or n的过程。（10 分）答题格式如下：9.Chomsky 文法分类将文法分为几类，分别什么文法？（5 分）0 型文法(短语结构文法PSG):u:=v，其中:u(VN VT)+,v(VNVT)*1 型文法(上下文有关文法CSG):xUy:=xuy，其中:UVN,x,y(VNVT)*,u(VNVT)+2 型文法(上下文无关文法CFG):U:=xuy，其中:U VN,x,y(VNVT)*,u(VNVT)+3 型文法(正则文法 RG):左线性：U:=Va 或 U:=a，右线性：U:=aV 或 U:=a，其中:U,VVN,aVT 步骤符号栈状态栈输入串动作1#0 n+born#Shift S4 2#n 04+born#Reduce R3 3#T 02+born#Shift S5 4#T+025 b or n#Shift S3 5#T+b 0253 or n#Reduce R4 6#T+T 0256 or n#Reduce R1 7#E 01 Error 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 4 页 -