2022年编译原理考试试 .pdf

西安邮电学院 2007 2008 学年第 二 学期编译原理课程期中考试卷（ A）考核形式：闭卷班级：姓名：学号：一、填空题（ 30 分，每空 2 分）1由文法开始符号经0 步或多步推导产生的文法符号序列是_句型_。2编译器通常经历 _词法分析 _、_语法分析 _、_语义分析和中间代码生成_、_优化_、_目标代码生成 _等几个阶段；其中第一个阶段是以_源程序 _为输入， _单词符号 _为输出；最后一阶段是以_中间代码 _为输入， _机器语言程序或汇编语言程序_为输出。同时 _表格管理 _和_出错处理 _贯穿编译器的各个阶段。3解释器与编译器的主要区别是：_编译程序生成目标代码，而解释程序不生成目标代码_。4高级语言到低级语言的翻译过程称为_编译 _。汇编语言到机器语言的翻译过程称为_汇编_。二、单项选择题（ 20 分，每小题 2 分）1正规表达式 ( |a|b)2表示的集合是（D ） 。A ，ab，ba，aa，bb Bab，ba，aa，bb Ca，b，ab，aa ，ba，bb D ，a，b，aa，bb，ab，ba 2分析树的内部结点仅由（C ）组成。A开始符号和非终结符号B终结符号和非终结符号C非终结符号D终结符号3文法S(L)|a LL，S|S 的终结符号是（ C） 。AS BS L C a , ( ) Da , ( ) | 4NFA M 所识别的语言是（D ） 。A0 型语言B上下文有关语言C上下文无关语言D正规语言5同正规式 a*b* 等价的文法是（C ） 。ASaS|bS| BSaSb|CSaS|Sb| DSabS|6对 LR 分析表的构造，不可能存在( C )动作冲突。A移进 /归约B归约 /归约C移进 /移进D.以上都不对7LR 分析模式中，改变格局变化的动作不包括（B ） 。A移进B匹配终结符C归约D接受8如果一个文法 G 是二义文法，则必存在某个句子XL（G ） ，该句子（） 。A存在两个不同的最右推导和一个最左推导题号一二三四五六七八九十十一总分得分名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - B存在两个不同的最左推导和一个最右推导C最左推导和最右推导不同D存在两个不同的最左推导和两个不同的最右推导9一个句型的最左直接短语称为（D ） 。A句型B句子C语言D句柄10下图所能接受的字集所对应的正规式是（B ）Aa*b* （aabb）a*b* B （ab）*（aabb） （ab）* C（ a*b*） （aabb） （a*b*）D（a* b*）aa（a*b*）（ a*b*）bb（ a*b*）b b b b a a a 1 2 3 4 a 三、判断题（ 10 分，每小题 1 分）（ T ）1一个 LL（1）文法是一个无二义性和无回溯文法。（ F ）2每个非终结符产生的终结符号串都是该语言的子集。（ F ）3正规式所描述的语言结构均可以用CFG描述，反之也成立。（ T ）4一个非确定的有限自动机NFA，可以通过多条路识别一个符号串（ F ）5自动机 M 和 M的状态数不同，则二者必不等价。（ F ）6最小化的 DFA所识别接受的正规集最小。（ F ）7一个状态转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（ F ）8语法分析时必须先消除文法中的左递归。（ T ）9确定的自动机和不确定的自动机都能正确的识别正规集。（ T ）10规范归约是最右推导的逆过程。四、对于正规式（ ab）* a (ab) (ab) 1画出此正规式的NFA； （5 分）2构造此正规式的DFA； （5 分）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - I Ia Ib x,1,2 1,2,3 1,2 1,2,3 1,2,3,4 1,2,4 1,2 1,2,3 1,2 1,2,3,4 1,2,3,4 1,2,4,y 1,2,4 1,2,3,y 1,2,y 1,2,3,4,y1,2,3,4,y1,2,4,y 1,2,4,y1,2,3,y1,2,y1,2,3,y1,2,3,41,2,41,2,y1,2,31,2DFA 那个图不太好画，在这就不画了五、文法 G 如下：SaBcD|cd BBb|b Dd|dD1改写 G 为等价的 LL(1)文法 G； （5 分）2求 G中每个非终结符的FIRST 集合和 FOLLOW 集合； （5 分）3构造预测分析表。（5 分）答： 1、SaBCD|cd BbBBbB |空D dDD 空 |D 2、FIRST(S)=a,c FOLLOW(S)=# FIRST(B)=b FOLLOW(B)=c FIRST(B )=b, 空 FOLLOW(B )=c S a b 0 1 2 1 3 4 2 1 2 3 5 6 4 7 8 5 5 6 6 7 8 7 3 4 8 1 2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - FIRST(D)=d FOLLOW(D)=# FIRST(D )=d, 空 FOLLOW(D )=# 3、预测分析表a b c d # S S aBcDScdB BbBBBbBB空D DdDDDDD空名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - 六、给出接受文法： S（L）|a LL，S|S 的活前缀的 DFA，并构造 LR（0）分析表。 （10 分） 。解：将文法 GS拓广为文法 G S: G S:(0)SS (1)S(L)(2)Sa (3)LL,S(4)LS状态action goto a ( ) , # S L 0 S3 S2 1 1 all 2 S3 S2 5 4 3 r 2 r 2 r 2 r 2 r 2 4 S6 S7 5 r 4 r 4 r 4 r 4 r 4 6 r 1 r 1 r 1 r 1 r 1 7 S3 S2 8 8 r 3 r 3 r 3 r 3 r 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 七、证明文法SAaAb|BbBa A B是 LL（1）文法，但不是SLR （1）文法（5 分） 。证明：非终结符 S 产生的 2 个不同的产生式S1 AaAb S2BbBa 得 FIRST(S1)=空,a FIRST(S2)=空,b 且 FIRST(S1)FIRST(S2)=空集又因为 S 为无左递归，无公共左因子S 是 LL(1)文法GS的拓广文法 SS SAaAb SBbBa A 空B空其 DFA 中其中：FLLOW(A)=a,b FOLLOW(B)=a,b FOLLOW(A) FOLLOW(B) 空集S 文法有规约 -规约冲突，不能由SLR（1）解决S 不是 SLR（1）文法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -