编译原理第四章.ppt

1、1,第四章词法分析,4.1 词法分析程序的设计 4.2 单词的描述工具 4.3 有穷自动机 4.4 正规式和有穷自动机的等价性 4.5 正规文法和有穷自动机的等价性 4.6 词法分析程序的自动构造工具,2,4.1 词法分析程序,4.1.1 词法分析程序与语法分析程序 的关系,3,4.1.2 词法分析程序的输出格式 词法分析程序的功能是读入源程序,输出单词. 单词一般有5种: 1.单词的种类 (1). 关键字. 如PASCAL中的begin , end等 (2). 标志符: 变量名, 过程名等. (3). 常数: 如25, 3.14等 (4). 运算符: 如 +, -, *, / 等 (5).

2、界符: 如 , , ; , ( , ) 等,4,2. 输出格式 输出的单词以二元式表示: (单词的种类, 单词自身的值) 但是,当为标识符时,为该标识符所在的符号表的入口地址.,5,设,6,例:设程序段 if i = 5 then x := y ; 经词法分析后输出如下: If (3, if ) i (1, i所在的符号表的入口地址 ) = (4, = ) 5 (2, 5 ) then (3, then ) X (1, x所在的符号表的入口地址 ) := (4, :=) y (1, y所在的符号表的入口地址 ) ; (5, ; ),7,4.2 单词的描述工具,4.2.1 正规文法: 正规文法

3、G=（,）的特征: A aB或A a 例： ,*,8,4.2.2 正规式和正规集 设字母表为，正规式和它所表示的正规集的定义如下:, ，都是上的正规式,它们所表示的正规集分 别为 ,. 任何a 正规式,它所表示的正规集为a.,9, 如果e1和e2都是上的正规式,它们所表示的正规集分别为L(e1)和(e2), e1|e2是正规式,它所表示的正规集为 L(e1|e2)=L(e1)L(e2)； e1e2是正规式,它所表示的正规集为 L(e1e2)=L(e1)L(e2) ； (e1)*是正规式,它所表示的正规集为 L(e1)*)=(L(e1)*. 仅由有限次使用上述三步骤而定义的表达式才是上的正规式,

4、仅由这些正规式所表示的字集才是上的正规集.,10,例： 正规式的性质： 1. r | s = s | r 2. r | (s | t ) = ( r | s ) | t 3. ( r s ) t = r ( s t ) 4. r ( s | t ) = r s | r t ( s | t ) r = s r | t r 5. r=r r=r,11,4.2.3 正规文法和正规式的等价性 1. 正规式转换成正规文法: 对给定的正规式，写产生式S r,并 将S作为文法的开始符号. 若x和y都是正规式,对形如Axy的产生式, 写成AxB,By 对形如Ax*y的产生式，写成 , Ay x|y, 写为x,

5、Ay. 不断利用上述规则做变换，直到每个产生式都符合正规文法的形式为止,12,例： 例正规文法转换成正规式： 过程是正规式转换成正规文法的的逆过程,最后只剩下一个开始符号定义的正规式,用的的转换规则有: AxB By 转换成 A=xy AxA, A y 转换成 A=x*y x Ay 转换成 A=x|y 例：,13,4.3 有限自动机,有限自动机(FA)可以认为是由一个带阅读头的控制器和一条字符输入带组成. 阅读头从左到右读入字符,每读入一个字符, 自动机的状态就改变一次. 自动机的状态是有限的,故称为有限自动机. 当前状态: 自动机当前所处的状态 后继状态: 读入一个字符后,自动机转换后的 状

6、态,14,开始状态(初始状态) 结束状态(终止状态) 如果每次转换后的状态是唯一的,则称该自动机是确定的有限自动机(DFA),否则是不确定的有限自动机(NFA).,15,确定的有穷自动机 一个确定的有穷自动机M是一个五元组: M=(K, , f, S, Z) , 其中 1. K: 状态的有限集合. 2. : 字母表, 每个元素称为一个输入符号; 3. f: 转换函数 KK 或 f(ki, a)=kj 4. SK, 唯一的初态; 5. Z: K的子集, 终态集合.,16,例题 DFA M=(S,U,V,Q,a,b,f,S,Q) f: f(S,a)=U f(V,a)=U f(S,b)=V f(V,

7、b)=Q f(U,a)=Q f(Q,a)=Q f(U,b)=V f(Q,b)=Q,状态图表示: U S Q V,a,a,a,b,b,b,a,b,矩阵表示:,0 0 0 1,符号,状态,17,定义: 对字符串 t*, 若存在一条从初态到某一终态的标有 t 的路径,则称 t 能被自动机所识别(接受),若自动机的初态同时又是终态,则认为空字符也能被自动机所识别. 例:,18,不确定的有限自动机(NFA) 一个NFA是一个五元组 M=(K, , f, S, Z)，其中 1. K: 状态集合. 2. ; 字母表. 3. f: 转换函数, 是K* K子集的映像. 4. S: K的子集, 初态集合. 5.

8、Z: K的子集, 终态集合. 例,*,k,19,定义: 自动机M所识别的符号串的集合,称为M所识别的语言,用L(M)表示. 对任何的两个自动机M和M , 若L(M)=L(M), 则称M和M等价.,20,NFA转换成等价的DFA 定理:设L为一个由不确定的有穷自动机接受的集合,则存在一个接受L的确定的有穷自动机. 转换算法:子集法 在NFA中,表项通常是一个状态的集合,而在DFA中,表项是一个状态,NFA到相应的DFA的构造的基本思想是让DFA的每一个状态对应NFA的一组状态.也就是让DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态.,21,有穷自动机的化简 1. 去掉多余的

9、状态 例 合并等价状态 状态S和T等价的条件: (1). S和T必须同时为终态或非终态. (2).对于每一个输入符号, S和T的后继状态 必须在等价状态中.,22,有穷自动机的化简: (1) 把自动机的状态分成终态和非终态两 个集合. (2) 对某一集合,某一输入符号,若它们的后 继状态在多个集合中,则把该集合分裂. (3) 重复(2),直到不再产生新的集合为止. 每一集合为化简后的一个状态. 例,23,4.4 正规式和有穷自动机的等价性,正规式和有穷自动机的等价性有两点说明: 1.对于上的NFA M,可以构造一个上的正规式r,使得L(r)=L(m); 2.对于每个上的正规式r,可以构造一个上

10、的NFA M,使得L(m)=L(r).,24,1. 由自动机构造正规式 (1). 在自动机的状态转换图上加进两个结点, 一个为x结点,一个为y结点. 从x结点用弧连接到自动机的所有初态结点,从自动机的所有终态结点用弧连接到y结点.,25,(2). 用以下三条规则,逐步消除自动机中的所有结点,直至只剩下x和y结点. 对于 1 2 3 代之为: 1 3 对于 代之为: 1 3 对于 1 2 3 代之为: 1 3 在结点X和Y之间的正规式就是所要求的正规式. 例:,1 2,r1,r1r2 r3,r1,r2,r1,r1r2,r3,*,r1,r1|r2,r2,26,2. 由正规式构造相应的自动机 首先将

11、正规式分解成一系列子表达式,然后使用如下规则为r构造NFA: 1.对于正规式,构造的NFA为: x y 对于正规式,构造的NFA为: x y 对于正规式 a,构造的NFA为: x y 2.若s,t是正规式,相应的自动机分别为N(s) 和 N(t),则 对正规式r=s|t,构造,a,27,x y 其中x是NFA(r)的初态,y是NFA(r)的终态,x到N(s)和N(t)的初态各有一个弧,从N(s)和N(t)的终态各有一个弧到y,现在N(s)和N(t)的初态或终态已不作为N(r)的初态和终态了. 对正规式r=st,构造 x y 其中N(s)的初态成了N(r)的初态,N(t)的终态变成了N(r)的终

12、态,N(s)的终态与N(t)的初态合并为N(r)的一个既不是初态也不是终态的状态.,N(s),N(t),N(s),N(t),28, 对正规式r=s*,构造 x y 这里x和y分别是NFA(r)的初态和终态,从N(s)的终态引弧到y,从x到y引弧,同样N(s)的初态可沿弧的边直接回到N(s)的初态.N(s)的初态或终态不再是N(r)的初态和终态 例:,N(s),29,4.5 正规文法和有穷自动机的等价性,1. 从正规文法构造自动机 自动机的字母表与文法的终结符集相同; 文法中的每个非终结符为自动机的一个状态,文法 的开始符是自动机开始状态. 增加一个新状态Z,作为自动机的终态; 对形如AtB的规则,画一条从A到B的有向弧,并 标记为 t . 对形如At的产生式,画一条从A到Z的有向弧,并 标记为 t. 例,30,2.由自动机构造正规文法 规则 (1)对转换函数 f(A,t)=B, 写产生式 AtB. (2)对终态,增加一条产生式 Z. (3)自动机的开始状态为文法的开始符号, 自动机的字母表为文法的终结符集合. 例:,31,4.6 词法分析程序的自动构造工具,对于描述单词的结构来说，正规式已经足够，而把一个正规式编译成一个NFA进而转换成相应的DFA,这个NFA或DFA就是识别正规式所表示的语言的句子的识别器.基于这种方法来构造词法分析程序的工具很多,我们以LEX为