下载文档原格式
《编译原理》习题(一)——词法分析一、就是非题(请在括号内,正确得划√,错误得划×)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.句子得集合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、编译过程可分为( 词法分析) ,(语法分析),(语义分析与中间代码生成),(优化)与(目标代码生成)五个阶段。
6、扫描器得任务就是从( 源程序中)中识别出一个个( 单词符号)。
17、一张转换图只包含有限个状态,其中有一个被认为就是(初)态;而且实际上至少要有一个(终)态。
1.编译程序首先要识别出源程序中每个(单词),然后再分析每个(句子)并翻译其意义。
第二章 词法分析2.1 完成下列选择题： (1) 词法分析器的输出结果是 。
a. 单词的种别编码 b. 单词在符号表中的位置 c. 单词的种别编码和自身值 d. 单词自身值 (2) 正规式M1和M2等价是指 。
a. M1和M2的状态数相等 b. M1和M2的有向边条数相等 c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向边条数相等 (3) DFA M(见图2-1)接受的字集为 。
a. 以0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合 c. 含奇数个0的二进制数组成的集合 d. 含偶数个0的二进制数组成的集合 【解答】 (1) c (2) c (3) d图2-1 习题的DFA M2.2 什么是扫描器？扫描器的功能是什么？ 【解答】 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。
通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。
每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。
2.3 设M=({x,y}, {a,b}, f, x, {y})为一非确定的有限自动机，其中f 定义如下： f(x,a)={x,y} f {x,b}={y} f(y,a)=Φ f{y,b}={x,y} 试构造相应的确定有限自动机M ′。
【解答】 对照自动机的定义M=(S,Σ,f,So,Z)，由f 的定义可知f(x,a)、f(y,b)均为多值函数，因此M 是一非确定有限自动机。
先画出NFA M 相应的状态图，如图2-2所示。
图2-2 习题的NFA M用子集法构造状态转换矩阵，如表表2-1 状态转换矩阵1b将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到 M ′=({0,1,2},{a,b},f,0,{1,2})，其状态转换图如图2-3所示。
《编译原理》习题（一）——词法分析一、是非题（请在括号内，正确的划√，错误的划×）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．句子的集合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.编译过程可分为（词法分析），（语法分析），（语义分析与中间代码生成），（优化）和（目标代码生成）五个阶段。
6.扫描器的任务是从（源程序中）中识别出一个个（单词符号）。
17.一张转换图只包含有限个状态,其中有一个被认为是（初）态;而且实际上至少要有一个（终）态。
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.句子的集合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、编译过程可分为( 词法分析) ,(语法分析),(语义分析与中间代码生成),(优化)与(目标代码生成)五个阶段。
6、扫描器的任务就是从( 源程序中)中识别出一个个( 单词符号)。
17、一张转换图只包含有限个状态,其中有一个被认为就是(初)态;而且实际上至少要有一个(终)态。
1.编译程序首先要识别出源程序中每个(单词),然后再分析每个(句子)并翻译其意义。
习题参考答案 第4章 词法分析（注：部分解题过程略）4.1 编写以下字符串集的正规式（若没有正规式则说明原因）： （1）以a 开头和结尾的所有小写字母串； （2）以a 开头或/和结尾的所有小写字母串； （3）不以0开头的所有数字串；（4）每个5均在每个1之前的所有数字串；（可能有两种理解：a ，每个1前面总有个5；b ，所有5都在所有的1前面） （5）a 和b 的个数相等的所有ab 串。
解：（1）a(a|b|c|…|z)*a|a（2）a(a|b|c|…|z)*|(a|b|c|…|z)*a （3）(1|…|9)(0|1|2|…|9)*（4）((0|2|3|4|6|7|8|9)*51)*(0|2|3|4|6|7|8|9)* （按a 的理解） （5）“a 和b 的个数相等的所有ab 串”属上下文有关，正规式不能描述。
4.2 简述由下列正规式生成的语言： （1）(a|b)*a(a|b|ε) （2）(A|B|…|Z)(a|b|…|z)* （3）(aa|b)*(a|bb)*（4）(0|1|…|9|A|B|C|D|E|F)+(x|X) 解：（1）以a ，aa 或ab 结尾的ab 串； （2）以1个大写字母打头的小写字母串；（3）由若干个a 串和b 串交替出现的串，其中前段的a 串和后段的b 串的长度均为偶数； （4）十六进制数的一种表示形式，以x 或X 结尾。
4.3 构造4.1题的每个字符串集的DFA ，或说明不存在DFA 的原因。
解：（1）由正规式a(a|b|c|…|z)*a|a 构造的NFA1，以及确定化得到的DFA1分别为：（2）由正规式a(a|b|c|…|z)*|(a|b|c|…|z)*a 构造的NFA2，以及确定化简得到的DFA1…,zDFA2分别为：（3）由正规式(1|…|9)(0|1|2|…|9)*构造的DFA3为：（4）依题意构造的DFA4为：（5）确定有限自动机与3型文法等价。
而“a 和b 的个数相等的所有ab 串”属上下文有关，需要1型文法描述，故确定有限自动机不能描述。
第4章词法分析作业参考答案4.7练习（P72）1．构造下列正规式相应的DFA：(4) b((ab)*|bb)*ab解：先将正规式转换为NFA，转换过程如下：以下为最终所得的NFA图：然后，将此NFA转换为DFA：转换关系矩阵如下表：所得DFA图如下：最后，将此DFA化简后如下：4、把图4.21（a）和（b）分别确定化和最小化：(a)图【解】子集法：重命名：确定化的DFA为：(b)图【解】【解】初始划分得Π0：终态组{0}，非终态组{1,2,3,4,5}对非终态组进行分割：{1,2,3,4,5}a ={0,1,3,5}而{0,1,3,5}既不属于{0}，也不属于{1,2,3,4,5}∵{4} a {0}，所以得新划分Π1：{0}，{4}，{1,2,3,5}对{1,2,3,5}进行分割：∵{1,5} b {4}{2,3} b {1,2,3,5}，故得新划分Π2：{0}，{4}，{1, 5}，{2,3}{1, 5} a {1, 5}{2,3} a {1,3}，故状态2和状态3不等价，得新划分：Π3：{0}，{2}，{3}，{4}，{1, 5}这是最后划分最小DFA：7．给文法G[S]：S→aA|bQA→aA|bB|bB→bD|aQQ→aQ|bD|bD→bB|aAE→aB|bFF→bD|aE|b构造相应的最小的DFA。
【解】首先，将正规式转换成NFA如下：然后，将此NFA转换为DFA：转换关系矩阵如下表：所得DFA图如下：化简后的最后划分为：T0={T0},T1={T1,T2},T3={T3,T4},T5={T5,T6},其中T3为终态。
最后，将此DFA化简后如下：8．给出下述文法所对应的正规式：S→0A|1BA→1S|1B→0S|0【解】由题意得：A=>1S|1，B=>0S|0 ，S→0A|1B，将A，B右端代入S的产生式得：S→0(1S|1)|1(0S|0)=01S|01|10S|10=(01|10)| (01|10)S∴S→(01|10)| (01|10)S∴S=(01|10)| (01|10)*∴该文法所对应的正规式为：(01|10)| (01|10)*9将图4.22的DFA最小化，并用正则式描述所识别的语言。
词法分析习题(总5页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--词法分析补充习题1. 构造与正规式(a|ba)*等价的状态最少的DFA 。
2. 构造与正规式(a|b)*a(a|b)等价的状态最少的DFA 。
3. 构造与正规式(a|b)* aa 等价的状态最少的DFA 。
1. 解答：(1)构造NFA 如图1所示：I Ia Ib ①{S, A, Z} ②{A, Z} ③{B} ②{A, Z} ②{A, Z} ③{B} ③{B} ②{A, Z} Φ图2（a ｜ba ）*的DFA（3）DFA 最小化首先得到两个子集K1 = {3} 和 K2 = {1，2}。
考察K2，由于{1，2}a = {2} K2，{1，2}b = {3} K1，所以K2不可再分。
用1来代表K2并删除3，得到最小化DFA 的状态图，图3所示.A Z S a Ba b ε ε2 13 a ab ab图3 正规式（a ｜b a ）*的最小化DFA2. 解答（1）构造NFA ，见图1图1 正规式(a|b)*a (a|b)的NFA（2）NFA 确定化为DFA 的过程表和相应DFA 的状态图，见图2a ab图2 正规式(a|b)*a (a|b)的DFA（3）将DFA 最小化并得到最小化的状态图，见图3首先进行初始划分得到两个子集：K 1 = {1,2,3} 和 K 2 = {4，5}考察K 1：因{1,2,3}a={2,4} K 1，也 K 2，所以{1,2,3}可被重新划分。
由于状态1和状态3输入a 都到达状态2，输入b 都到达状态3，而状态2输入a 到达状态4，输入b 到达状态5，所以将K1分割成：K 11 = {1,3} 和 K 12 = {2}目前划分得到的子集为：K 11 = {1,3} , K 12 = {2}, K 2 = {4，5}考察K 11：{1,3}a={2} K 1，{1,3}b={3} K 1，所以{1,3}无需重新划分。
