2022年编译原理半期考试答案 .pdf

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

1、毕节学院课程考试试卷纸毕节学院编译原理课程试卷第页 共 8 页1 一、填空题（每空1 分，共 20 分）1 编译程序的工作过程一般可以划分为词法分析,语法分析 ,语义分析 ,中间代码生成 ,代码优化等几个基本阶段,同时还会伴有 _表格处理_和 _出错处理_。2若源程序是用高级语言编写的,_目标程序_是机器语言程序或汇编程序,则其翻译程序称为_编译程序_ 。3编译方式与解释方式的根本区别在于_是否生成目标代码_。4对编译程序而言,输入数据是 _源程序 _, 输出结果是 _目标程序_。5若两个正规式e1和 e2 所表示的正规集相同,则 e1和 e2 等价,写作 e1=e2。6一个句型中的最左简单短

2、语称为该句型的_句柄_。7词法分析基于_正则_文法进行，即识别的单词是该类文法的句子。二、是非题（请在括号内，正确的划 ，错误的划 ） （每个 1 分，共 10 分）1计算机高级语言翻译成低级语言只有解释一种方式。( ) 2在编译中进行语法检查的目的是为了发现程序中所有错误。( ) 3甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。( ) 4正则文法其产生式为A-a ， A-Bb, A,BVN ， a 、 bVT 。 ( ) 5每个文法都能改写为LL(1) 文法。( )（2 班做）得分评卷人得分评卷人毕节学院期中课程试卷2009 2010 学年度第 二学期 编

3、译原理 计科系 07级计算机科学与技术专业班姓名学号得分主考教师：黄正鹏试卷类型：（半期考试）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 毕节学院课程考试试卷纸毕节学院编译原理课程试卷第页 共 8 页2 6.有穷自动机接受的语言是正规语言。( )（1 班做）7.对任何一个NFA M 都存在一个DFA M ,使得 L(M )=L(M).( ) 8设 r 和 s 分别是正规式，则有L(r|s)=L(r)L(s) 。( ) 9确定

4、的自动机以及不确定的自动机都能正确地识别正规集。( )10词法分析作为单独的一遍来处理较好。( ) 11有穷自动机接受的语言是正规语言。（ ）三、选择题（每小题2 分，共 20 分）1 文法 G 产生的 _的全体是该文法描述的语言。A ( ) 句型B ( ) 终结符集C ( ) 非终结符集D( ) 句子2 若文法G 定义的语言是无限集，则文法必然是_。A( ) 递归的B( ) 前后文无关的C( ) 二义性的D( ) 无二义性的3 四种形式语言文法中，1 型文法又称为_文法。A( ) 短语结构文法B( ) 前后文无关文法C( ) 前后文有关文法D( ) 正规文法4 一个文法所描述的语言是_。A(

5、 ) 唯一的B( ) 不唯一的 C( ) 可能唯一，好可能不唯一D( ) 都不对5 _和代码优化部分不是每个编译程序都必需的。A( ) 语法分析B( ) 中间代码生成 C( ) 词法分析D( ) 目标代码生成6_是两类程序语言处理程序。A( ) 高级语言程序和低级语言程序B( ) 解释程序和编译程序C( ) 编译程序和操作系统D( ) 系统程序和应用程序7 编译程序是对_。A( ) 汇编程序的翻译B( ) 高级语言程序的解释执行 C( ) 机器语言的执行D( ) 高级语言的翻译8 采用自上而下分析，必须_。（2 班做）A( ) 消除左递归B( ) 消除右递归 C( ) 消除回溯D( ) 提取

6、公共左因子9在规范归约中，用_来刻画可归约串。（2 班做）A( )直接短语B( )句柄 C( )最左素短语D( )素短语得分评卷人名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - 毕节学院课程考试试卷纸毕节学院编译原理课程试卷第页 共 8 页3 10词法分析器用于识别_。A( ) 字符串B( )语句C( )单词D( )标识符11文法分为四种类型，即0 型、1 型、2 型、 3 型。其中 0 型文法是 _。A. ( ) 短语文法B(

7、 ) 正则文法C( ) 上下文有关文法D( ) 上下文无关文法12一个上下文无关文法G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组_。A( ) 句子B( ) 句型C( ) 单词D( ) 产生式四、简答题（每小题5 分，共 30 分）1.高级语言程序有哪两种执行方式？其特点是什么？答：高级语言程序有编译程序和解释程序两种执行方式；编译程序 （Compiler ） 将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言 )程序的翻译程序。解释程序（ Interpreter） 将高级程序设计语言写的源程序作为输入，边解释边执行源程序本身，而不产生目标

8、程序的翻译程序。2、考虑文法GS：SaSbS|bSaS|(1)试用最左推导说明此文法是二义性的（2）对于句子abab 构造两个相应的最右推导（3）对于句子abab 构造两个相应的分析树解答：(1) 句子 abab 有如下两个不同的最左推导：S = aSbS = abS=abaSbS = ababS = abab S = aSbS = abSaSbS= abaSbS= ababS = abab 所以此文法是二义性的。(2) 句子 abab 的两个相应的最右推导： S= aSbS= aSbaSbS= aSbaSb= aSbab = abab S= aSbS= aSb= abSaSb= abSab

9、= abab (3) 句子 abab 的两棵分析树：得分评卷人名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - 毕节学院课程考试试卷纸毕节学院编译原理课程试卷第页 共 8 页4 (a) (b) 3、已知文法GE 为：ET|E+T| E-T TF|T*F|T/F F(E) |i 该文法的开始符号（识别符号）是什么？ 请给出该文法的终结符号集合VT和非终结符号集合VN。 找出句型T+T*F+i 的所有短语、简单短语和句柄。解：该文法的

10、开始符号（识别符号）是E。该文法的终结符号集合VT=+ 、-、 *、/、 （、 ） 、 i 。 非终结符号集合VN=E 、T、F。句型 T+T*F+I 的短语为 i、T*F 、第一个 T、T+T*F+i; 简单短语为i、T*F、第一个T;句柄为第一个T。4. 构造正规式相应的NFA : 1(0|1)*101 解： 1(0|1)*101 对应的 NFA 为5.画出接受以 /*和*/括起来的注释的状态转换图。解答：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - -

11、 - - - - - - - 毕节学院课程考试试卷纸毕节学院编译原理课程试卷第页 共 8 页5 6.用状态转换图表示识别偶数个0 或偶数个 1 的字符串的有穷自动机。解答：五.计算题（ 10 分）1、构造下述文法GS 的自动机：S-A0 A-A0|S1|0 该自动机是确定的吗？若不确定，则对它确定化。解：由于该文法的产生式S-A0，A-A0|S1 中没有字符集VT 的输入，所以不是确定的自动机。 要将其他确定化， 必须先用代入法得到它对应的正规式。把 S-A0 代入产生式A-S1有： A=A0|A01|0=A(0|01)|0=0(0|01)*。 代入 S-A0 有该文法的正规式：0(0|01)

12、*0 ，所以，改写该文法为确定的自动机为：由于状态 A 有 3 次输入 0 的重复输入，所以上图只是NFA，下面将它确定化：下表由子集法将NFA 转换为DFA:得分评卷人名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - 毕节学院课程考试试卷纸毕节学院编译原理课程试卷第页 共 8 页6 由上表可知DFA 为：2、设计一个状态数最小的DFA,其输入字母表是0,1 ，它能接受以00 或 01 结尾的所有序列，并给出相应的正规文法。（1

13、班做）解答：正规式为： (0|1)*(00|01) 化简： (0|1)*0(0|1) 不确定的有穷自动机为：确定化，并最小化得到：正规文法为：S1S | 0A A0B | 0 | 1C | 1 B0B | 0 | 1C | 1 C1S | 0A 3、对下面的文法G: ETE E +E|名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - 毕节学院课程考试试卷纸毕节学院编译原理课程试卷第页 共 8 页7 TFT T T|FPF F *F

14、 |P(E)|a|b|(1) 计算这个文法的每个非终结符的First 集和 Folow 集；(2) 证明这个文法是LL(1) 的；(3) 构造它的预测分析表。解答：(1) 求 First 和 Follow 集First(E)=First(T)=(,a,b, First(E)=+, First(T)=First(F)=(,a,b, First(T)= (,a,b, , First(F)=First(P)=(,a,b, First(F)= *， First(P)=(,a,b, （计算顺序）Follow(E)= #, ) Follow(E)= Follow(E)=#，) (1)（使用的产生式）Fol

15、low(T) = First(E) Follow(T) (1,2) = + ),#=+,),# Follow(T)= Follow(T)=+,# (3) Follow(F)= First(T) Follow(T) (3,4) = (,a,b,+ ,),# Follow(F)= Follow(F) (5) = (,a,b, ,+ ,),# Follow(P)= First(F) Follow(F) (5,6) =*,(,a,b, ,+ ,),# (2) 证明 :a. 文法不含左递归；b. 每个非终结符的各个侯选式的First 集不相交；c. First(E) Follow(E)=+, #,),=

16、First(T) Follow(T)=(,a,b, , +,)=First(F)Follow(F)=*, ,a,( ,+,#= 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - 毕节学院课程考试试卷纸毕节学院编译原理课程试卷第页 共 8 页8 改造后的文法满足LL(1) 文法的三个条件，是LL(1) 文法。(3) 预测分析表如下所示。a b * + ( ) # E ETEETEETEE E +EE E T TFTTFTTFTTFTT T TT TT TT TT T F FPFFPFFPFFPFF F F F *FF F F F F P PaPbPP(E)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -