编译原理第四章.ppt
第四章词法分析v4.1 词法分析程序的设计v4.2 单词的描述工具v4.3 有穷自动机v4.4 正规式和有穷自动机的等价性v4.5 正规文法和有穷自动机的等价性v4.6 词法分析程序的自动构造工具14.1 词法分析程序v4.1.1 词法分析程序与语法分析程序 的关系 2v4.1.2 词法分析程序的输出格式 词法分析程序的功能是读入源程序,输出单词.单词一般有5种:1.单词的种类 (1).关键字.如PASCAL中的begin,end等 (2).标志符:变量名,过程名等.(3).常数:如25,3.14等 (4).运算符:如+,-,*,/等 (5).界符:如,;,(,)等 32.输出格式输出的单词以二元式表示:(单词的种类,单词自身的值)但是,当为标识符时,为该标识符所在的符号表的入口地址.4设 种种 类类 编编 码码标识符1常数2关键字3运算符4界符55例:设程序段 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,;)64.2 单词的描述工具v4.2.1 正规文法:正规文法 G=（,）的特征:A aB或A a例：*7v4.2.2 正规式和正规集设字母表为，正规式正规式和它所表示的正规集正规集的定义如下:,，都是上的正规式,它们所表示的正规集分别为,.任何a 正规式,它所表示的正规集为a.8 如果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)*.仅由有限次使用上述三步骤而定义的表达式才是上的正规式,仅由这些正规式所表示的字集才是上的正规集.9例：正规式的性质：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=r10v4.2.3 正规文法和正规式的等价性1.正规式转换成正规文法:对给定的正规式，写产生式S r,并将S作为文法的开始符号.若x和y都是正规式,对形如Axy的产生式,写成AxB,By 对形如Ax*y的产生式，写成 ,Ay x|y,写为x,Ay.不断利用上述规则做变换，直到每个产生式都符合正规文法的形式为止11例：例正规文法转换成正规式：过程是正规式转换成正规文法的的逆过程,最后只剩下一个开始符号定义的正规式,用的的转换规则有:AxB By 转换成 A=xy AxA,A y 转换成 A=x*y x Ay 转换成 A=x|y例：124.3 有限自动机v有限自动机(FA)可以认为是由一个带阅读头的控制器和一条字符输入带组成.阅读头从左到右读入字符,每读入一个字符,自动机的状态就改变一次.自动机的状态是有限的,故称为有限自动机有限自动机.当前状态当前状态:自动机当前所处的状态 后继状态后继状态:读入一个字符后,自动机转换后的 状态13 开始状态开始状态(初始状态初始状态)结束状态结束状态(终止状态终止状态)如果每次转换后的状态是唯一的,则称该自动机是确定的有限自动机确定的有限自动机(DFA),否则是不确定不确定的有限自动机的有限自动机(NFA).14v确定的有穷自动机v一个确定的有穷自动机M是一个五元组:M=(K,f,S,Z),其中 1.K:状态的有限集合.2.:字母表,每个元素称为一个输入符号;3.f:转换函数 KK 或 f(ki,a)=kj 4.SK,唯一的初态;5.Z:K的子集,终态集合.15v例题 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,b)=Q f(U,a)=Q f(Q,a)=Q f(U,b)=V f(Q,b)=Q v状态图表示:U S Q V aaabbba,bv矩阵表示:abSUVUQVVUQQQQ0001符号状态16v定义:对字符串 t*,若存在一条从初态到某一终态的标有 t 的路径,则称 t 能被自动机所识别(接受接受),若自动机的初态同时又是终态,则认为空字符也能被自动机所识别.v例:17v不确定的有限自动机(NFA)一个NFA是一个五元组 M=(K,f,S,Z)，其中 1.K:状态集合.2.;字母表.3.f:转换函数,是K*K子集的映像.4.S:K的子集,初态集合.5.Z:K的子集,终态集合.例*k18v定义:自动机M所识别的符号串的集合,称为M所识别的语言语言,用L(M)表示.对任何的两个自动机M和M,若L(M)=L(M),则称M和M等价等价.19vNFA转换成等价的DFAv定理:设L为一个由不确定的有穷自动机接受的集合,则存在一个接受L的确定的有穷自动机.v转换算法:子集法 在NFA中,表项通常是一个状态的集合,而在DFA中,表项是一个状态,NFA到相应的DFA的构造的基本思想是让DFA的每一个状态对应NFA的一组状态.也就是让DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态.20v有穷自动机的化简1.去掉多余的状态 例2.合并等价状态 状态S和T等价的条件:(1).S和T必须同时为终态终态或非终态非终态.(2).对于每一个输入符号,S和T的后继状态 必须在等价状态中.21v有穷自动机的化简:(1)把自动机的状态分成终态终态和非终态非终态两 个集合.(2)对某一集合,某一输入符号,若它们的后 继状态在多个集合中,则把该集合分裂.(3)重复(2),直到不再产生新的集合为止.(4)每一集合为化简后的一个状态.例例224.4 正规式和有穷自动机的等价性v正规式和有穷自动机的等价性有两点说明:1.对于上的NFA M,可以构造一个上的正规式r,使得L(r)=L(m);2.对于每个上的正规式r,可以构造一个上的NFA M,使得L(m)=L(r).231.由自动机构造正规式 (1).在自动机的状态转换图上加进两个结点,一个为x结点,一个为y结点.从x结点用弧连接到自动机的所有初态结点,从自动机的所有终态结点用弧连接到y结点.24v(2).用以下三条规则,逐步消除自动机中的所有结点,直至只剩下x和y结点.对于 1 2 3 代之为:1 3 对于 代之为:1 3 对于 1 2 3 代之为:1 3 在结点X和Y之间的正规式就是所要求的正规式.例:1 2r1r1r2 r3r1r2r1r1r2r3*r1r1|r2r2252.由正规式构造相应的自动机 首先将正规式分解成一系列子表达式,然后使用如下规则为r构造NFA:1.对于正规式,构造的NFA为:x y 对于正规式,构造的NFA为:x y 对于正规式 a,构造的NFA为:x y 2.若s,t是正规式,相应的自动机分别为N(s)和 N(t),则 对正规式r=s|t,构造 a26 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)的终态,N(s)的终态与N(t)的初态合并为N(r)的一个既不是初态也不是终态的状态.N(s)N(t)N(s)N(t)27 对正规式r=s*,构造 x y 这里x和y分别是NFA(r)的初态和终态,从N(s)的终态引弧到y,从x到y引弧,同样N(s)的初态可沿弧的边直接回到N(s)的初态.N(s)的初态或终态不再是N(r)的初态和终态 例:N(s)284.5 正规文法和有穷自动机的等价性1.从正规文法构造自动机 自动机的字母表与文法的终结符集相同;文法中的每个非终结符为自动机的一个状态,文法 的开始符是自动机开始状态.增加一个新状态Z,作为自动机的终态;对形如AtB的规则,画一条从A到B的有向弧,并 标记为 t.对形如At的产生式,画一条从A到Z的有向弧,并 标记为 t.例例292.由自动机构造正规文法 规则 (1)对转换函数 f(A,t)=B,写产生式 AtB.(2)对终态,增加一条产生式 Z.(3)自动机的开始状态为文法的开始符号,自动机的字母表为文法的终结符集合.例:304.6 词法分析程序的自动构造工具v对于描述单词的结构来说，正规式已经足够，而把一个正规式编译成一个NFA进而转换成相应的DFA,这个NFA或DFA就是识别正规式所表示的语言的句子的识别器.基于这种方法来构造词法分析程序的工具很多,我们以LEX为例来进行介绍.vLEX编译系统的作用:LEX LEX 词法 源程序 编译系统 分析程序L 输入串 词法 单词 分析程序L 符号串31vLEX程序由三部分组成:说明部分,转换规则和辅助过程,用%做间隔,格式为:说明部分%转换规则%辅助过程v使用LEX生成词法分析程序:Lex.1 LEX编译系统 Lex.yy.c Lex.yy.c C编译程序 a.out 输入字符流 a.out token流32
