《编译原理词法分析习题集带答案》由会员分享，可在线阅读，更多相关《编译原理词法分析习题集带答案（7页珍藏版）》请在金锄头文库上搜索。
1、编译原理习题（一）词法分析一、是非题（请在括号内，正确的划，错误的划）1编译程序是对高级语言程序的解释执行。( )2一个有限状态自动机中，有且仅有一个唯一的终态。()9两个正规集相等的必要条件是他们对应的正规式等价。 ( )二、选择题1词法分析器的输出结果是_。A( ) 记号 B( ) 相应条目在符号表中的位置 C( ) 记号和属性二元组 D ( ) 属性值2 正规式 M 1 和 M 2 等价是指_。 A( ) M1 和 M2 的状态数相等 B( ) M1 和 M2 的有向边条数相等C ( ) M1 和 M2 所识别的语言集相等 D ( ) M1 和 M2 状态数和有向边条数相等 3语言是A句
2、子的集合 B产生式的集合 C符号串的集合 D句型的集合4编译程序前三个阶段完成的工作是A词法分析、语法分析和代码优化 B代码生成、代码优化和词法分析C词法分析、语法分析、语义分析和中间代码生成 D词法分析、语法分析和代码优化5扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即A 字符 B单词 C句子 D句型6构造编译程序应掌握_。A( )源程序 B( ) 目标语言 C ( ) 编译方法 D( ) 以上三项都是 7词法分析的任务是A识别单词 B分析句子的含义C识别句子 D生成目标代码三、填空题1计算机执行用高级语言编写的程序主要有两种途径：_解释_和_编译_。 3
3、.编译过程可分为 （ 词法分析） ， （语法分析） ， （语义分析与中间代码生成 ） ， （优化）和（目标代码生成 ）五个阶段。6.扫描器的任务是从（ 源程序中 ）中识别出一个个（ 单词符号 ） 。17.一张转换图只包含有限个状态,其中有一个被认为是（初）态;而且实际上至少要有一个（终 ）态。1编译程序首先要识别出源程序中每个(单词) ，然后再分析每个 (句子)并翻译其意义。 3通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析) ，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。5对编译程序而言，输入数据是(源程序) ，输出结果是(目标程序)。
4、四、名词解释题：1词法分析词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。13.扫描器- 执行词法分析的程序。五、简答题(一)、描述由正规式 b*(abb*)*(a| )定义的语言，并画出接受该语言的最简 DFA。答：由正规式 b*(abb*)*(a| )定义的语言是字母表a, b上不含子串 aa 的所有串的集合。最简 DFA 如下：(二)、描述由正规式 ba(bba) b定义的语言，并画出接受该语言的最简 DFA。答：正规式 ba(bba) b体现的特点是，每个
5、 a 的左边都有若干 b，除非 a 是第一个字母。该正规式定义的语言是：至少含一个 a，但不含子串 aa 的所有 a 和 b 的串集。最简 DFA 如下：(三). 一字母表 =a, b，试写出 上所有以 a 为首的字组成的正规集相对应的正规式。答：正规式 a ( a | b )*。(四).令 =a,b，则正规式 a*b|b*a 表示的正规集是什么？答：.(a*b|b*a)=a,b,ab,ba,aab,bba(五)、构造下列正规式相应的 DFA（用状态转换图表示）（1）0（0 | 1） *1（2）0*10*10*10*1（3）letter（letter | digit）*（1）start 1 a
6、bb2start2 abb10ab（2）（3）(六)设有非确定的有自限动机 NFA M=(A，B ，C，0，1，A，C) ，其中： (A，0)=C (A，1)=A ，B (B，1)=C (C，1)=C。请画出状态转换距阵和状态转换图。解：状态转换距阵为： 0 1A C A，BB CC C状态转换图为(七)编译程序和高级语言有什么区别?用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器语言表示的目标程序（这个过程即编译） ，才能由计算机执行。执行转换过程的程序叫编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序转换过的叫目标程序，也就是机器语言。编译程序的工作情况有三种：
7、汇编型、解释型和编译型。汇编型编译程序用来将汇编语言编写的程序，按照一一对应的关系，转换成用机器语言表示的程序。解释型编译程序将高级语言程序的一个语句，先解释成为一组机器语言的指令，然后立即执行，执行完了，取下一组语句解释和执行，如此继续到完成一个程序止。用解释型编译程序，执行速度很慢，但可以进行人和计算机的对话 ，随时可以修改高级语言的程序。BASIC 语言就是解释型高级语言。编译型编译程序将级语言编写的程序，一次就会部翻译成机器语言表示的程序，而且过程进行很快，在过程中，不能进行人机对话修改。FORTRAN 语言就是编译型高级语言。(八)编译程序的工作分为那几个阶段?A B 1C11011
8、 词法分析、语法分析和语义分析是对源程序进行的分析(称为编译程序的前端) ，而中间代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合(称为编译程序的后端)，它们从源程序的中间表示建立起和源程序等价的目标程序。(九)、有穷自动机 M 接受字母表0,1 上所有满足下述条件的串：每个 1 都有 0 直接跟在右边。构造一个最小的 DFA M 及和 M 等价的正规式。【】 【】(十)、 证明正规式(ab)*a 与正规式 a(ba)*等价 （用构造他们的最小的 DFA 方法） 。【答案：】 (十一)、设=0，1上的正规集 S 由倒数第二个字符为 1 的所有字符串组成，请给出该字集对应的正规式，并构
9、造一个识别该正规集的 DFA。(8 分)答：构造相应的正规式：(0|1)*1(0|1) (3 分)NFA: (2 分)1 1 1 0 0确定化：(3 分)I 0I1I0,1,2 1,2 1,2,31,2 1,2 1,2,31,2,3 1,2,4 1,2,3,41,2,4 1,2 1,2,31,2,3,4 1,2,4 1,2,3,4010 1 0 00 11 1（十二） 、处于/* 和 */之间的串构成注解，注解中间没有*/ 。画出接受这种注解的 DFA 的状态转换图。（十三）设有字母表a，b上的正规式 R=(ab|a)*。构造 NFA，确定化，化简 (2014A)解：（1）0 123baa -
10、 +（2）将（1）所得的非确定有限自动机确定化 a b-0 11 3 120 1 2 3 40 1 2 3 42 1+30 12aaba-+（3）对（2）得到的 DFA 化简，合并状态 0 和 2 为状态 2：12aab-+(十四)、给定文法 GS： SaA|bQ； AaA|bB|b；BbD|aQ ；QaQ|bD|b；DbB|aA ；EaB|bF FbD|aE|b构造相应的最小的 DFA 。 解：先构造其 NFA： 用子集法将 NFA 确定化： 将 S、A、Q、BZ、DZ、D、B 重新命名，分别用 0、1、2、3、4、5、6 表示。因为 3、4 中含有 z，所以它们为终态。a b-+013 123+123 123 13+13 123a bS A QA A BZQ Q DZBZ Q DDZ A BD A BB Q Da b0 1 21 1 32 2 43 2 54 1 6 令P 0（0,1,2,5,6 ,3,4 ）用b进行分割： P1（0,5, 6,1,2,3,4）再用b进行分割： P2（0,5, 6,1,2,3,4）再用a、b 进行分割，仍不变。再令为A，1，2为B，3，4为C，5，6为D。 最小化为右上图。5 1 66 2 5
