编译原理期末考试试卷(C卷).pdf

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

1、编译原理期末考试试卷（C 卷）编译原理期末考试试卷（c卷）、单项选择题（每小题2分，共 30 分）1、编译程序是对程序进行翻译。A.自然语言B.汇编语言C.高级语言D.机器语言2、描述语言L=a mb nB.S-ABA-*aB 一 bA.S-A B A-A a|a B-B b|bf a S b|a b C.S D.S-a S b|e3、设有文法G=(b ,S,B ,S,S-*b B ,B-b S|e),下列哪个符号串不是该文法的句子。A.b B.b b C.b b b D.b b b b b4、下图D FA 所 识 别 的 语 言 为.A.含有偶数个0偶数个1 的二进制串B.含有偶数个0奇数个

2、1 的二进制串C.含有奇数个0偶数个1 的二进制串D.含有奇数个0奇数个1 的二进制串5、下述正规式等价的是。A.(a|b)与(a b)B.(a b)与 a b C.(a|b)与(a b)D.(a|b)与 a|b6、设有一个L R(1)项目集I=X f .b B,a B-.,a 则该项目集A.不含冲突项目B.含有移进-归约冲突C.含有归约-归约冲突D.含有移进-待约冲突7、L R 语法分析栈中存放的状态是识别文法规范句型_ _ _ _ _ _ _ _ _ _ 的 D FA 状态。A.句 柄 B.前 缀 C.活 前 缀 D.项目8、有 文 法 如 S -*r D1 *D f D,i|i贝 FIR

3、 S T V T (D)=。A.i B.i ,C.i r D.i r ,9、有 文 法 如 S -r DD -D,i i则 i和，的优先关系是。A.没有优先关系B.等 于 C.低 于 D.高于1 0、算符优先分析法从左到右扫描输入串，采用移进-归约的方式，当栈顶出现_ _ _ _ _ _ _ _ _ _ _时进行归约。A.素 短 语 B.最左素短语 C.句柄 D.直接短语1 1、局部优化是局限于一个 范围内的一种优化。A.程 序 B.函 数 C.基 本 块 D.循环1 2、在编译中，动 态 存 储 分 配 的 含 义 是。A.在运行阶段对源程序中的量进行存储分配B.在编译阶段对源程序中的量进行

4、存储分配C.在说明阶段对源程序中的量进行存储分配D.以上都不正确1 3、以下说法正确的是.一A.对任何一个编译程序来说，产生中间代码不是不可缺少的一部分。B.在属性文法中，文法的终结符只有综合属性，不存在继承属性。C.自下而上语法制导翻译中语法分析栈与语义分析栈必需同步操作。D.以上都正确1 4、后缀式a b c d+*的 中 缀 表 达 式 是。A.a b*(c+d)B,a (b*c+d)C.a (b*(c+d)D.a*(b+c)d1 5、有翻译模式如下：D f i n t L pr i n t (L.s);L -i d L.s=l;L f L I,i d L.s=L I.s +1;采用移进

5、归约的分析方法，当分析器的输入为i n t a,b.c 时，输出的结果是。A.4 B.3 C.2 D.1 2三、应 用 题(1、4、5 每 题 1 0 分，2、3 每 题 1 5分，共 60 分)2、有文法如下：S -T LT f i n t|f lo a tL -*i d RR f,i d R|e(1).计算文法的每个非终结符的FIR S T 和 FO L L O W集合：(1)(8 分)FIR S T(S)=i n t,f lo a t FO L L O W(S)=#FIR S T(T)=i n t,f lo a t FO L L O W(T)=i d FIR S T(L)=i d FO

6、L L O W(L)=#FIR S T(R)=,e FO L L O W(R)=#4、有定义算术表达式的文法如下：E-E+T E-T|TT -T*F T/F|FF -p F|PP -(E)i构造句型E-T*P F+i 的语法树；并指出该句型的所有短语、直接短语、素短语、句柄。4、句型E T*P F+i 的语法树：(5 分)短语：E-T*P F+i、E-T*P F、T*P F、P F、i直接短语：P F、i素短语：P F i句柄：P F312345678910111213cABDAACBI)BCAD编译原理期末考试试卷(B卷)一、简述编译程序的工作过程。(1 0)编译程序的工作过程，是指从输入源

7、程序开始到输出目标程序为止的整个过程，是非常复杂的，就其过程而言，一般可以划分为五个工作阶段：词法分析，对构成源程序的字符串进行扫描和分解，识别出一个个的单词；语法分析，根据语言的语法规则，把单词符号串分解成各类语法单位；语义分析与中间代码产生，即对各类语法单位，分析其汉一并进行初步翻译；代码优化，以期产生更高效的代码；目标代码生成，把中间代码变换成特定机器上的低级语言指令形式。二、给出下面的正规表达式(1 5)(1)以0 1结尾的二进制数串；(2)能被5整除的十进制整数；(3)包含偶数个1或偶数个0的二进制数串。(1)(0|1)*0 1(2)d i g i t=0|1|2|3|4|5|6 7

8、|8|9d i g i t*(0 5)(3)(0*1 0*1)*0*)|(1*0 1*0)*1*)三、对下面的文法 G：S-a I b (T)T-T,S|S(1)消去文法的左递归，得到等价的文法G 2；(2)判断文法G 2是否L L (1)文法，如果是，给出其预测分析表。(1 5)G 2：S-a b (T)T-S T V S T|e四、对下面的文法G：ab()sSaSbS (T)TT-STT ST，T-ST,rT 一，SS-A B 4A-A O O|0 B-B l l|1(1)消去文法的左递归，得到等价的文法G 2；(2)判断文法G 2 是否L L (1)文法，如果是，给出其预测分析表。(1

9、5)G ：S-A B A-O A,A f O O A|e B f I B B f 1 1 B|e文法G S 是 L L(1)文法。01#sS-A BAA-O A AA *0 0 A A BB T B B B f1 1 B B F五、设有文法G A ：A f B C c|g D BB-*b C D E|e C-*D a B c a D-*d D e E-g A f|cF I R S TF O L L O WAA,b,c,d,gBbA,c,dCA,c,dC,d,gDDA,b,c,gEC,g(1)计算该文法的每一个非终结符的F I R S T 集 和 F O L L O W 集；(2)(2)是 L

10、L(1)文法。5编译原理期末考试试卷(D 卷)三、应 用 题(1、4、5 每 题 1 0 分，2、3每 题 1 5 分，共 6 0 分)1、为正规式(a|b)a(a|b)构造等价且状态最少的确定有限自动机。(要求给出主要步骤)*2、有文法如下：S f B A A f B S dB -a A|b S|c(1).计算文法的每个非终结符的F I R S T 和 F O L L O W 集合；(2).判断文法是否L L(1)文法，如果是，给出其预测分析表，否则说明理由。4、有文法如下：T -T*F F F -P F P P -(T)|i证 明 T*i P是该文法的一个句型，但不是规范句型；指出T*i

11、P的所有短语、直接短语、素短语、句柄。三、应 用 题(1、4、5 每 题 1 0 分，2、3每 题 1 5 分，共 6 0 分)1、（a|b）*a（a|b）状态最少的 D F A。NFA如 图（5分）：c=（也可是其它等价的FA）a用子集法得到的状态转换矩阵:确 定 化（3分）后 的DFA如图，已是状态最少的。如不说明是最简的扣1分。化 简（2分）注：初态或终态错扣1分Ilalb1 AJA,BA2 A,B)A,B,CA,C3 A,B,C)A,B,CA,C4 A,CA,BA62、(1)(6 分)F I R S T(S)=a,b,c F O L L O W(S)=#,a,b,c,d F I R S

12、 T (A)=a,b,c,d F O L L O W (A)=#,a,b,c,d F I R S T (B)=a,b,c F O L L O W (B)=a,b,c,d（2）因为文法不含左递归，关于A的两个规则的S E L E C T集不相交，关于B的3个规则的S E L E C T集两两不相交，所以文法是L L （1）文 法（2分）。4、对于符号串T*i P 存在如下推导：(或画一颗语法树证明是句型)abc(i#sS BAS f BAS BAAA-BSA-BSA-BSA f dBB f aAB f bSB cT T*F T*P F T*P P T*i P所 以 T*i P 是该文法的一个句型

13、，但不存在一个规范推导能推导出该句型，所以不是规范句型。(5 分)短语：T*i P、i P、i、p直接短语：i、p素短语：i句柄：i2.考 虑 文 法 GS:S-(T)a+S|aT-T,S S消除文法的左递归及提取公共左因子。解：消除文法GS的左递归：S-(T)|a+S|aT T T，丁-*.ST,I e提取公共左因子：S f (T)|aSzS f+S|T-S T T;-.S T*e 72 4.已知文法G S S-S*a F|a F|*a FF f+a F|+a消除文法左递归和提公共左因子。答：消除左递归S-a F S *a F S S f*a F S，|Ff+a F|+a提公共左因子,文法G

14、 (S)S-a F S *a F S S -*a F S，|eF-+a F F -F|e1、设文法G(S):S-a (T)T-T,S|S消除左递归；构造相应的F I R S T 和 F O L L O W 集合;构造预测分析表(1)消除左递，文法变为G，S ：S-|a (T)T-S T,|Sr -.S T)|e此文法无左公共左因子。1 0.设文法G(S):S-(T)|a S|aTT,S|S消除左递归和提公共左因子；构造相应的F I R S T和F O L L O W集合；构造预测分析表。.(1)S f (L)|a S，S，f S|L fS L f f S L，|e(2)F I R S T(S)

15、=a,(F I R S T(S*)=a,(,e F I R S T(L)=a,(F I R S T(L )=,e F O L L O W(S)=,),#F O L L O W(S*)=,),#F O L L O W(L)=)F O L L O W(f)=)(3)8()a#sS-(L)S-*aSs，S-SS-S-SS-LL-S L L-*S LL,S LE一sT)-T,SIs(T)I 小a I,SI IS aIa1.已知文法G(S)：S a (T)T T,S|S给出句子(a,a),a)的最左推导并画出语法树；给出句型(T,a,(T)所有的短语、直接短语、素短语、最左素短语、句柄和活前缀。解：(1

16、)最左推导：S (T)(T,S)(S,S)(a,S)(a,(T)(a,(T,S)(a,(S.S)(a,(a,S)(a,(a,a)语法树：如 图 A-1 6 所示。图 A-1 6 (a,(a,a)的语法树(2)句型(T,a,(T)的短语、直接短语、素短语、最左素短语、句柄、活前缀及语法树(图 AT7)。短语：a|T,a|(T)|T ,a ,(T)|(T ,a ,(T)直接短语：a|(T)素短语：a|(T)最左素短语：a句柄：a活前缀：I(T|I(T ,|I(T ,aS(T )T ,S(T )9图 A T 7 (T,a,(T)的语法树二、构造下列正则表达式的确定性的有限状态自动机。(1 2%)a ba (a|b)*a答:二、设=0,1 上的正规集S由倒数第二个字符为1 的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的D F A。（8分）答：构造相应的正规式：（0 1）*1（0 I D （3 分）N F A:（2 分）I0,1,2)1.2(1,2,3)121,2(1,2,3)(1,2,3)(1,2,4)123,4(1,2,4)1,21,2,3)1,2,3,4)1,2,4)(1,2,3,410 0 1 0