编译原理课后答案——第二章 词法分析ppt课件.ppt

第二章 词法分析
完成下列选择题：
(1) 词法分析器的输出结果是 。
a. 单词的种别编码 b. 单词在符号表中的位置
c. 单词的种别编码和自身值 d. 单词自身值
(2) 正规式M1和M2等价是指 。
a. M1和M2的状态数相等
b. M1和M2的有向边条数相等
c. M1和M2所识别的语言集相等
d. M1和M2状态数和有向边条数相等
1
完整版PPT课件
(3) DFA M(见图2-1)接受的字集为 。
a. 以0开头的二进制数组成的集合
b. 以0结尾的二进制数组成的集合
c. 含奇数个0的二进制数组成的集合
d. 含偶数个0的二进制数组成的集合
【解答】
(1) c (2) c (3) d
2
完整版PPT课件
图2-1 M
3
完整版PPT课件
什么是扫描器？扫描器的功能是什么？
【解答】 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。
4
完整版PPT课件
设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所示。
5
完整版PPT课件
图2-2 M
6
完整版PPT课件
用子集法构造状态转换矩阵，如表2-1所示。
表2-1 状态转换矩阵
7
完整版PPT课件
将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到
M′=({0,1,2},{a,b},f,0,{1,2})，其状态转换图如图2-3所示。
8
完整版PPT课件
表2-2 状态转换矩阵
9
完整版PPT课件
将图2-3所示的DFA M′最小化。首先，将M′的状态分成终态组{1,2}与非终态组{0}。其次，考察{1,2}，由于{1,2}a={1,2}b={2}{1,2}，所以不再将其划分了，也即整个划分只有两组：{0}和{1,2}。令状态1代表{1,2}，即把原来到达2的弧都导向1，并删除状态2。最后，得到如图2-4所示的化简了的DFA M′。
10
完整版PPT课件