2022年编译原理阶段练习一 .pdf

编译原理练习一一、填空题1编译程序的工作过程一般可以划分为词法分析、语法分析、语义分析、代码生成、代码优化等几个基本阶段，同时还会伴有表格处理和出错处理。2若源程序是用高级语言编写的，目标程序是机器或汇编语言的程序，则其翻译程序称为编译程序。3编译程序与解释程序的根本区别在于是否生成目标代码。4如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段：编译阶段和运行阶段。如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分为三个阶段：编译阶段、汇编阶段和运行阶段。5词法分析的任务是：依据语言的词法规则，分析由字符组成的源程序，把它识别为一个一个具有独立意义的最小语法单位，即“单词”，并识别出与其相关的属性。6确定的有限自动机是一个五元组（五元式），通常表示为 DFA=（K，M，S，Z）。7高级程序设计语言的单词通常分为五类，它们是关键字、标识符、常量以及运算符、界限符。8词法分析程序的输出形式是一个单词，每个单词由单词类别和单词自身值两部分组成。9高级语言的语言的处理程序分为解释程序和编译程序两种。编译程序有五个阶段，而解释程序通常缺少代码优化和目标代码生成。其中，代码优化的目的是使最后阶段产生的目标代码更为高效。与编译系统相比，解释系统比较简单，可移植性好，执行速度慢。解释程序处理语言时，大多数采用的是先将源程序转化为中间代码，再解释执行方法。BASIC 就是一种典型的解释型语言。10编译程序与具体的机器有关，与具体的语言无关。二、选择题（单项或多项）1在使用高级语言编程时，首先可通过编译程序发现源程序的全部a 错误和部分b 错误。a、语法b、语义c、语用d、运行2程序语言的语言处理程序是一种（1）a。（2）b 是两类程序处理程序，它们的主要区别在于（3）d。（1）a、系统软件b、应用软件c、实时系统d、分布式系统名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 6 页 -（2）a、高级语言程序和低级语言程序b、解释程序和编译程序c、编译程序和操作系统d、系统程序和应用程序（3）a、单用户和多用户的差别b、对用户程序的差错能力c、机器执行效率d、是否生成目标代码3下面关于解释程序的描述正确的是a。a、解释程序的特点是处理程序时不产生目标代码b、解释程序适用于COBOL 和 FORTRAN 语言c、解释程序是为打开编译程序技术的僵局而开发的4要在某一台机器上为某种语言构造一个编译程序，必须掌握下述三方面的内容：c、d、f。a、汇编语言b、高级语言c、源语言d、目标语言e、程序设计方法学f、编译方法g、测试方法h、机器语言5由于受到具体机器主存容量的限制，编译程序几个不同阶段的工作往往被组合成b，诸阶段的工作往往是h 进行的。a、过程b、遍c、批量d、程序e、顺序f、并行g、成批h、穿插6编译程序必须完成的工作有a b c d。a、词法分析b、语法分析c、语义分析d、代码生成e、中间代码生成f、代码优化7编写一个计算机高级语言的源程序后，到正式上机运行之前，一般要经过a b c 这几步。a、编辑b、编译c、连接d、运行8“用高级语言书写的源程序都必须通过编译，产生目标代码后才能投入运行。”这种说法a。a、不正确b、正确9编译程序生成的目标程序b 是机器语言的程序。a、一定b、不一定10编译程序生成的目标程序b 是可执行的程序。a、一定b、不一定11编译过程中词法分析器的任务包括a b c d e f g。a、组织源程序的输入b、按词法规则分割出单词，识别出其属性，并转换成属性字的形式输出c、删除注解d、删除空格及无用字符名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 6 页 -e、行记数、列记数f、发现并定位词法错误g、建立符号表12 正则式的“|”读作b，“”读作c，“*”读作d。a、并且b、或者c、连接d、闭包13设有如图所示的有穷自动机，状态为开始状态，状态为终止状态，假设digit 代表数字 0 到 9。则下述实数中d 可被该有穷自动机识别。a、+47 b、-1 c、.5 d、-11.47 e、至少两个14设有穷自动机的状态转换图如下状态为开始状态，状态为终止状态，则下述正则表达式中a b 可被该有穷自动机识别a、0（10）*0 b、11（01）*1 c、1（101）*00 15b 这样一些语言，它们能被确定的有限自动机识别，但不能用正则表达式表示。a、存在b、不存在c、无法判定是否存在三、构造下列正则式相应的DFA 11(0|1)*101 DFA 为：1 2 3 4 5 digit digit digit+.digit a 0 1 2 4 3 0 1 0 1 0 1 1 5-S B C D 10110E A 010101名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 6 页 -2b(ab)*|bb)*ab NFA 为：子集法求 DFA.略四、将所示的 NFA 确定化子集法求 DFA 得：S Z 1 0 0 0，1 Q V U 1 0 1 0,1 0，1 I A bB C D bbE F abG H abA B C D E 0110000111名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 6 页 -五、将所示的 DFA 最小化最小 DFA 为：六、构造一个DFA，它接受的符号串集合等于正则表达式(ab*c)|(abc*)所示的符号串集合。要求先构造NFA，其次转换成 DFA，最后加以简化。NFA 为：DFA 为：7 6 1 b a c 5 3 4 d 2 a d a b b b c b b 1 3 5 6 aadbcbb1 2 3 aabc4 b5 c名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 6 页 -最小 DFA 为：A B C E abbcccccbD F G A B C E abbccccbD F 名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 6 页 -