第4章词法分析.ppt

《第4章词法分析.ppt》由会员分享，可在线阅读，更多相关《第4章词法分析.ppt（129页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、词法分析器,词法分析是任何编译程序的第一步工作，因此编译程序都有完成词法分析的程序部分，称这种程序为词法分析器或扫描器。,词法分析器的共同特点是把每个单词转换成其内部形式，称它为符号或记号(TOKEN)。,4.1 词法分析程序的设计,词法分析器的功能可图示如下。其charsequence表示字符序列。,词法分析器的设计,TOKEN的通常结构是一个二元组:,其中CLASS示种类部分，VAL是值部分,TOKEN结构的一种方法可如下图，其中n是从4开始的编码，且一特殊符一码。,单词的识别,词法分析的关键之一是如何识别单词的问题，其中最重要的是标识符的识别问题。,4.2 单词的描述工具,定义2.1 正

2、则表达式 设为给定字母表,RE表示上正则表达式之集,则定义： 1.,RE 2.若a,则aRE 3.若e1,e2RE,则(e1|e2)RE,(e1e2)RE,(e1)*RE,例子： =a,b 正则式e L(e) b+ b, bb, bbb b* ,b, bb, bbb,例子：(a|b)* a,aa,ab,aaa,(a|b)0 (a|b)1 a, b ,(a|b)2 =(a|b) (a|b) aa,ab,ba,bb,定义2.2 设eRE,则定义函数L(e)如下： L()= L()= L(a)=a L(e*)= L(e)* L(e1|e2)= L(e1)L(e2) L(e1 e2)= L(e1)L(

3、e2),定理2.1 设e1 ,e2RE,则有： 1：L(e1|e2)=L(e2|e1) 2：L(e1|e2)|e3)=L(e1|(e2|e3) 3：L(e1e2)e3)=L(e1(e2e3) 4：L(e1(e2|e3)=L(e1e2|e1e3) 5：L(e1|e2)e3)=L(e1e3|e2e3) 6：L(e1)=L(e1)=L(e1),例子： 正则式e L(e) ab* a,ab,abb,abbb ab+ ab,abb,abbb a(a|b)+ aa,ab,aaa a(a|b)* a,aa,ab,aaa,语法图文法正则式,自动机状态图编程,a(a|b)* a,aa,ab,aaa标识符：(|)

4、*,例子：=a,b L(a*)=,a,aa L(ba*)=b,ba,baa L(a|ba*)=a,b,ba L(aa|bb|ab|ba)=aa,bb,ab,ba,例子：=a,b,正则表达式所定义的集合，称为正则集。,4.3 确定自动机,定义2.3 确定自动机(DA)A是一个五元组A=(S,s0,F),自动机,有穷自动机,无穷自动机,确定自动机,非确定自动机,自动机应用：广泛应用在人工智能，推理逻辑等领域。,4.3.1 确定自动机,每个DA均可用矩阵(状态转换矩阵)或状态转换图来表示。,S 是状态集s0,s1,sn(n1) 是字母表a1,a2,an(n1) 是映射：SS,且为单值的 s0 是初始

5、状态，s0S F 是终止状态集，FS,例子：A=(S,s0,F)S=s0,s1,s2 ,s3 =a,b F=s2,s3(s0,a)=s1 (s0,b)=s2(s1,b)=s1 (s2,a)=s3(s2,b)=s0 (s3,a)=s2,状态转换图如下：,前一条表明自动机的推理作用，后一条表明其词法分析的作用。如果L(A),则称可被A所接受。其中表示映射，表示推导。,例子：标识符的正则式: 字母(字母|数字)*状态转换图如下：,可为每个状态设计一段处理程序，得出标识符的分析程序。,出错处理,读入字符子程序,N,Y,例子:FA=(s0,s1,s2,s3,(a,b),f,S0,s3)其中映射f为：f(

6、s0，a)= s1 f(s0，b)= s2f(s1，a)= s3 f(s1，b)= s2f(s2，a)= s1 f(s2，b)= s3f(s3，a)= s3 f(s3，b)= s3,状态转换图：,a,b,b,a,a|b,可以识别=aa，abaaa等。,4.3.2 非确定自动机,定义2.5 NDA 一个非确定自动机(NDA)A是一个五元组A=(S, ,S0,F) S 是状态集s0,s1,sn(n1)。 是字母表a1,a2,an(n1)。 是映射:SS,不要求是单值的S0 是初始状态集(非空) F 是终止状态集，FS。,定义2.6 设A是一个NDAA=(S,s0,F),则定义：,定义2.7 设A1

7、和A2是同一字母表上的自动机，如果有L(A1)=L(A2),则称A1和A2等价。,例子：考虑下图所示的非确定自动机。A2=(S,S0,F)S=0,1,2 S0=0,1 =a,bF=1,2(0,a)=0,1 (0,b)=2 (1,a)= (1,b)=1,2(2,a)=1 (2,b)=2 ,定理2.2 对于每一个非确定自动机A,存在一个确定自动机A使得L(A)=L(A),4.3.3 NFA转换为等价的DFA,证明：构造算法如下：1. 令A的初始状态为s0=s10,s20, s0k,其中s10,s20,s0k是A的全部初始状态。 2. 若I=s1,sm是A的一个状态， a,则定义(I,a)=Ia,其

8、中为A的转换函数。 3. 重复步骤2直至不出现新的状态I为止。,4. 若I=s1,s2,sn是A的一状态，且存在一个I使得S是A的终止状态，则令I为 A的终止状态。,例子：考虑下图所示的非确定自动机。,由不确定自动机A构造等价的确定自动机A过程如下图所示。,由上述表格可以得出确定自动机A。确定自动机如下图所示。,为方便，将扩充自动机使得在边上有符号。我们称这种自动极为-自动机。并记为DA或NDA。,定理2.3 对任给DA均可构造一个DA,使得这两个自动机等价，既有L(DA)=L(DA),构造算法：,2.3如果B标有“-”，则给A标上“-”。,2.4如果存在一条从始点到A点的路，则给B标上“+”

9、。,3. 重复步骤2直至不出现步骤1所指的边为止。,4. 如果还有边，则肯定有闭路。这时要把闭路中的点合并为一个点，边也作相应处理。,例子：下图是从DA到DA的过程,例子：下图是从DA到DA的过程,转化过程如下：,确定化：,例子：求闭包，将DA转化到DA, 计算闭包-closure(0)=0,1,2,4,7/由该状态出发经过边所达到的状态。,转化如下：T0 =0,1,2,4,7 T1 =1,2,3,4,6,7,8T2 =1,2,4,5,6,7 T3 =1,2,4,5,6,7,9T4 =1,2,4,5,6,7,10, 转化为确定自动机：,转换后的DA图如下：,NFA的确定化,例子,等价的DFA,

10、a,a,b,总结： 对于简单的自动机，利用构造算法消除边，然后进行确定化。 对于复杂的自动机，利用闭包的算法进行处理。,确定自动机的化简的步骤：DA NDA DA 最小化DA,去除多余状态：从自动机的开始状态出发，任何输入也不能达到的状态，或从该状态到达不了终止状态。,4.3.4 确定自动机的化简,去除等价状态：从状态A出发，能读出某一字符串x而停于终态，从状态B出发也能得出同一字符串停止于终态；反之亦然。,例子：简化自动机,设PQ、P、QZ、Z、QPZ分别为A、B、C、D、E。则转化为一个起点得到下图：,去除等价状态：按终止状态和非终止状态可将其分为两部分：A,B，C,D,E。,最终得到的状

11、态图如下：,例子：将下图中的DFA M最小化。,按终止状态和非终止状态可将其分为两部分：1,2,3,4，5,6,7。,在1,2和6,7之中去除一个即可得到最小化的DA。,例子：确定化和最小化下面自动机,由此可知该自动机为确定自动机。 根据状态分为：01,2,3,4,5,所以1、5状态等价。,最小化自动机如下图：,例子：将下图最小化，并描述它所标识的语言。,根据状态分为1,2,3,4,5和6,7两组。,所以，1、2状态等价，3、4状态等价，6、7状态等价。,最小化结果为：,例子：设有正则表达式e为:(a|b)*(aa|bb)(a|b)* 构造确定有穷自动机A,使L(A)=L(e),解：求e的转换

12、系统,首先，利用求闭包的方法转化为确定自动机。得出如下表格:,Move(s,3,1,a)=(3,5)-closure(3,5)=1,3,5,得到确定自动机如下图:,化简后如下图，其中3，4，5，6四个状态等价。,4.4 自动机与正则表达式的关系,定理2.4 对于任一确定自动机A，存在以正则表达式e，使得L(A)=L(e)。反之亦然。,证明：()设A为给定确定自动机,则构造相应正则表达式的主要算法如下图。,()由给定正则表达式构造相应自动机的主要方法是：首先构造如下扩展转换图,然后利用下列规则加进节点和边，直至得到-自动机为止。,在运用上述转换规则前引入一新结点W,并从所有终止结点引出边到W结点

13、，并令w为唯一的终止结点。他显然等价于原自动机。,正则式至自动机的转换系统：即一种特殊的状态图，具有唯一的开始状态S和唯一的终止状态Z，没有弧引至S，也没有弧自Z引出，弧可以用标记。,例子：将自动机DA转化为正则式,例子：考虑将前例中的正则式: (a|b)(d|c)* (e|f) 转换化为自动机如下图：,4.4 正则文法与自动机定理3.7 3型文法的句型形如X,其中VT+，X(VNVT)。定理3.8 3型文法与产生式的形式为AB或C型的文法等价,其中VT+。,例子: SabS|aaB|d BbbB|b转化：SaS|aR|d SbS RaB BbB|b BbB,定理3.9 3型文法与自动机等价,

14、转换规则： 文法没有表示终止的符号，需要添加一个大写字母，表示结束状态。 大写字母对应自动机的状态集。 小写字母对应自动机的字母表。 文法的初始符为初始状态。 产生式Bb转换为,产生式ZbB转换为, 去掉多余状态,例子:设有3型文法如下 G1:ZaZ|bB|c BdB|b等价自动机A1=(S,s0,F)如下: S=Z,B,K =a,b,c,d S0=Z F=K (Z,a)=Z, (Z,b)=B, (Z,c)=K, (B,d)=B, (B,b)=K,注意：如果给定文法可以化简应进行化简再转换。,Y为非终止状态：XaYY为有输出边的终止状态XaY|aY为无输出边的终止状态Xa,例子:自动机A2如下

15、图,求等价3型文法,等价3型文法 G2=(VN,VT,P,S)如下: VN=Z,B,MR是终止状态没有输出边去掉 VT=a,b S=Z P=ZaM|bB|a|b BaB|bZ|a|b MbM|b|a说明: ZaM|a ZbB|b,例子: 设有文法如下： GS：SA|bB Ac BdD D 构造等价自动机。化简文法：Sc|bB BdD Bd,例子: 自动机如下所示,求与之等价的正则文法。,G=(A,B,C,a,b,P,A),其中P为： AaB BbC|b CaC|a|aB,4.6 词法分析程序的生成器,这里介绍一种以正则表达式作为输入的词法分析程序生成器，称为LEX。,1. 一个LEX源程序由下

16、面两段组成：,辅助定义段形式： D1=R1 D2=R2 Dn=Rn,例如：设VT=A,B,Z,0,1,9letter=A|B|Z digit=0|1|9identifer=letter(letter|digit)*第三个式子不能在一、二之前。,转换规则形式： P1 A1 P2 A2 Pn An,例子：要构造具有此变换功能的词法分析器，可编写LEX源程序如下：,辅助定义段 Letter=A|B|Z Digit=0|1|9,转换规则段 IF return 3 THEN return 4 ELSE return 5 return 34,:= return 38 ( return 20 ) retur

17、n 21 + return 24 * return 26letter(letter|digit)* return,0,标识符自身值digit(digit)* return,1,常量值 ,2. LEX compiler所完成的工作：,(a)对于每条转换规则Pi(正则式)构造NFA自动机。(b)引进新的开始状态，由此出发通过m条弧，将m个NFA连成一个NFA。(c)运用子集法将NFA化为FA。,例子：试利用LEX compiler 自动生成一个能识别无符号数dd.ddESdd的词法分析程序。,准备提交给生成的LEX源程序为 辅助定义段： digit=0|1|9 (d) Sign=+|-|E (S)

18、,转换规则段： dd* A1 d*.dd* A2 d*ESdd* A3 d*.dd*ESdd* A4,当LEX生成器接受上述LEX源程序后，它依次完成几个步骤： (a)构造四个Pi对应的NFA,(b)合并为一个NFA,(c)相应FA开始状态0,1,3,6,10用子集法。,重新命名如下：,得到状态图：,化简自动机：,所以，D和G等价、F和I等价。 同理，H和J等价。得到化简的状态图如下：,4.8 状态转换图,设计词法分析器时首先要构造状态转换图，它是一自动机即一张有向图，由一些结点和连接它们的箭弧以及弧上的字符组成。在这些结点中有一结点是初始结点，还有一个或多个终止结点。称有向图的结点为状态。,

19、下面以指数部分为例，介绍从词法图到状态转换图的方法。指数部分的词法图如下：,首先在词法图的入口和出口处各设一结点。分别称为状态转换图的初始和终止结点。,从上图到确定状态转换图的过程如下图所示。,图(d)的缺点是终止结点有输出边。它不能反映何时结束。为此我们要求终止结点没有输出边。当然，我们也可直接画出所需状态转换图。但最好的方法是机械的去构造它。,4.9 状态转换图的实现,考虑PASCAL语言的子情况。具体情况如下图所示：,其中单词的状态转换图如下图所示，l表示字母，d表示数字。,例子: X1:=X1+1; Begin YY:=0.5; ZZ:=YY*X1 End; While X1100 DO X1:=X1经词法分析后所得到的TOKEN序列如下(假定NAMEL表和CONSL表序号均从0000开始)：,同时被生成的NAMEL表和CONSL表分别如下图：,