第3章词法分析与有穷自动机20090326.ppt

1、2020年7月15日,编 译 原 理,第3章词法分析,本章介绍编译第一个阶段词法分析的设计原理和设计方法，要求明确此阶段的任务。 理解通常的单词分类和构词规则。 会使用单词的描述和识别机制。 要求掌握正规文法、状态图、DFA、NFA、正规式和正规集的基本概念和它们之间的关系。 掌握词法分析程序的手工实现方法。,教学目标,2020年7月15日,编 译 原 理,1 词法分析程序的功能 2 词法分析程序的输出形式 3 程序设计语言单词的定义 4 正规式与有穷自动机 5 正规文法与有穷自动机 6 词法分析程序的编写方法,教学内容,2020年7月15日,编 译 原 理,（1）分析和识别单词及属性， 包括

2、识别语言的关键字、标识符、常数、运算符等； （2）跳过各种分隔符，如空格，回车，制表符等； （3）删除注释； （4）进行词法检查，报告所发现的错误； （5）建立符号表。,3.1词法分析程序的功能,2020年7月15日,编 译 原 理,main( )/*ADD*/ int x=10,y=20,sum; sum=x+y; ,2020年7月15日,编 译 原 理,实现方案：基本上有两种,1.词法分析单独作为一遍,2.词法分析程序作为单独的子程序,S.P.(字符串),词法分析,S.P.(符号串),语法分析,第一遍,第二遍,单词串,优点: 结构清晰、各遍功能单一 缺点：效率低,2020年7月15日,编

3、译 原 理,单词的种类 （1）关键字：if、for、while （2）标识符： （3） 常数： （4） 运算符：+、-、* （5）分界符：, 、;、(、),3.2词法分析程序的输出形式,2020年7月15日,编 译 原 理,词法分析程序的输出形式-二元式,单词类别 单词的属性值,单词类别可以用整数编码表示:一类一种或一字一种,2020年7月15日,编 译 原 理,单词符号属性的值： 单词自身符号的机内编码。 关键字、运算符、界符：只输出其种别码即可。 标识符：自身字符串的值，长度受限制。 常数：本身的值。字符型输出字符串本身，数值型，输出其自身的二进制。 对于标识符和常数，若要建符号表，则输出

4、其在符号表的入口地址。,2020年7月15日,编 译 原 理,表3.1 int x=10,y=20,sum;词法分析的结果,表3.1 int x=10,y=20,sum;词法分析的结果,2020年7月15日,编 译 原 理,3.3语言单词符号的两种定义方式,文法定义: 标识符的定义：标识符是以字母开头的、字母数字的组合. I aB|a 右线性文法 B aB| dB| a |d I a| Ia| Id 左线性文法 正规式定义: 字母(字母数字)* a(a d)*,2020年7月15日,编 译 原 理,3.5,字母表, 定义在 上的正规式和正规集递归定义如下: 1. 和都是 上的正规式, 它们所表

5、示的正规集分别为:和; 2. 任何a , a是 上的正规式,它所表示的正规集为:a; 3. 假定e1和e2是 上的正规式, 它们所表示的正规集分别记为L(e1) 和L(e2), 那么e1|e2, e1 e2和e1*也都是 上的正规式, 它们所表 示的正规集分别为L(e1)L(e2)、 L(e1) L(e2)和(L(e1)* 4. 任何 上的正规式和正规集均由1、2和3产生。,3.3.1正规式与正规集,2020年7月15日,编 译 原 理,正规式中的运算符： | -或（选择） -连接 * 或 -重复 （） -括号,运算符的优先级： 先*, 后 , 最后 | 在正规式中可以省略.,正规式相等 这两

6、个正规式表示的语言相等,2020年7月15日,编 译 原 理,正规式举例,例：设有字母表 =a,b，根据正规式与正规集的定义，有以下的正规式和正规集 正规式 正规集 a a ab a,b ab ab ( ab)( ab) aa,ab,ba,bb a* ,a,aa,aaa,任意个a的串 （ab）* ，a,b,aa,ab,ba,bb,所有a,b组成的串 (ab) *(aabb) (ab) * *上所有含两个连续的a 或两个连续的b组成的串,2020年7月15日,编 译 原 理,【例】=d,e,+，- 则上的正规式 d*(dd*)(e(+- )dd*)表示的是实数。其中d为09中的数字。比如：2，1

7、2.59,3.6e2和471.88e-1等等都是该正规集所表示集合中的元素。 【例】设=a,b,c,则aa*bb*cc*是上的一个正规式,它所表示的正规集 L=abc,aabc,abbc,abcc,aaabc,.=ambnclm,n,l1,2020年7月15日,编 译 原 理,【例】设=a,b,2020年7月15日,编 译 原 理,【例】使用正规式来表示程序设计语言中的相应单词符号。,字母 | 字母 | 数字） 数字 | 数字 + | * |=,2020年7月15日,编 译 原 理,设r，s，t均是正规式，则有以下性质： （1）交换律： r|s= s|r （2）结合律： r|(s|t)=(r|

8、s)|t (rs)t=r(st) （3）分配律： (r|s)t=rt|st （4）同一律： r= r= r,2020年7月15日,编 译 原 理,3.3.2正规文法与正规式,正规文法正规式的转换 方法： （1）将正规文法中的每一个非终结符表示成关于它的一个正规式方程，获得一个联立方程组； （2）依照求解规则: 若x=ax(或x=ax+)，则解为x=a*。 若x=xa(或x=xa+),则解为x=a*。 求关于开始符号S的解. 文法规则正规式方程的变换 (1)若Aa,则有A=a； (2)若AaB,则有A=aB+；,2020年7月15日,编 译 原 理,举例:【例34】设有正规文法G： Z0A A0

9、A0B B1A 试给出该文法生成语言的正规式。 【例35】设有正规文法G： AaBbB BaCab CaB 试给出该文法生成语言的正规式。,2020年7月15日,编 译 原 理,【例3.6】设有正规文法G： ZU0V1 UZ11 VZ00 试给出该文法生成语言的正规式。,2020年7月15日,编 译 原 理,正规表达式RE 正规文法G,对任何一个正规表达式e，都存在一个等价的正规文法G ，使得 L(e) =L(G) 。,2020年7月15日,编 译 原 理,字母表上的正规式到正规文法G=（VN，VT，P，S）的转换方法如下： （1）令VT=； （2）对任意正规式R选择一个非终结符Z生成规则ZR

10、，并令S=Z； （3）若a和b都是正规式，对形如Aab的规则转换成AaB和Bb两个规则，其中B是新增的非终结符； （4）在已转换的文法中，将形如Aa*b的规则进一步转换成AaAb； （5）不断利用规则（3）和（4）进行变换，直到每条规则最多含有一个终结符为止。,2020年7月15日,编 译 原 理,【例38】将R=（ab）(aa)*(ab)转换成相应的正规文法。,设A是文法 的开始符号，根据规则（2）变换为 A (ab)(aa)*(ab) 根据规则（3）变换为： A（ab）B B (aa)*(ab) 根据规则（4）变换为： AaBbB BaaBab 根据规则（3）变换为： AaBbB BaCa

11、b CaB,2020年7月15日,编 译 原 理,【例39】将描述标识符的正规式R=l(ld)*转换成相应的正规文法。,令S为文法的开始符号，根据规则（2） 有 Sl(ld)* 根据规则（3）变换为： SlA A(ld)* 根据规则（4）变换为： SlA A(ld)A,进一步变换为： SlA AlAdA 去掉规则： SllA AldlAdA 既为标识符的文法。,2020年7月15日,编 译 原 理,有穷自动机是一种数学模型，具有离散的输入与输出，系统可处于有穷状态中的任何一个状态 它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合 引入有穷自动机这个理论，正是为词法分析程序的

12、自动构造寻找特殊的方法和工具,有穷自动机分为两类： 确定的有穷自动机（DFA） (Deterministic Finite Automata) 不确定的有穷自动机（NFA） (Nondeterministic Finite Automata),3.4正规式与有穷自动机,2020年7月15日,编 译 原 理,2020年7月15日,编 译 原 理,1-9 1,3,5,7,9,有穷自动机的模型,1 0 4 3 9 7,T,A,S,1,3,5,7,9,输入带,有穷控制器,读头,0-9,2020年7月15日,编 译 原 理,有穷自动机的作用,实质上是提供了一种逻辑的探测方式,去探测一些输入串是否属于某种

13、语言,即: 它可以作为一种语法检查器。,2020年7月15日,编 译 原 理,3.4.1确定的有穷自动机（DFA） M=(, Q, f,S, Z),：有穷字母表，它的每个元素称为一个输入符号 Q：有穷状态集，它的每个元素称为一个状态 SK，是唯一的初态 Z K是一个终态集，终态也称可接受状态或结束状态 f是转换函数，是QQ上的单值映射： f（q1，a）=q,2020年7月15日,编 译 原 理,例如: M:（0,1,2,3,a,b,f，0，3） f（0，a）=1 f（0，b）=2 f（1，a）=3 f（1，b）=2 f（2，a）=1 f（2，b）=3 f（3，a）=3 f（3，b）=3,所谓确

14、定的状 态机，其确定 性表现在状态 转移函数是单 值函数！,M=(, Q, f,S, Z),2020年7月15日,编 译 原 理,一个DFA也可以用一状态转换图表示：,字母表含有n个 输入字符，那末 任何一个状态结 点最多有n条弧 射出，而且每条 弧以一个不同的 输入字符标记。,2020年7月15日,编 译 原 理,换言之：若存在一条初始状态到某一终止状态的路径，且这条路径上所有弧的标记符号连接成符号串，则称为DFA M（接受）识别。,DFA M所接受的语言为：L(M)=|f(S, )=Sn, Sn Z DFA M所能接受的符号串的全体记为L(M),若M的初态结点同时为终态，或者存在一条从初态

15、到某个终态结点的通路，则为M所识别。,2020年7月15日,编 译 原 理,f（0，abaab） = f（1，baab） = f（2，aab） = f（1，ab） = f（3，b） = 3 (接受),f（0，abab） = f（1，bab） = f（2，ab） = f（1，b） = 2 (拒绝),对于符号串abaab的识别过程,对于符号串abab的识别过程,2020年7月15日,编 译 原 理,f是一个多值函数，是从Q*到Q的子集的映射： f：Q2Q 其中2Q是Q的幂集，即Q中所有子集组成的集合。,3.4.2不确定的有穷自动机（NFA） M=(, Q, f,S, Z),有穷自动机的不确定性表现

16、在在某个状态下，对于某个输入字符存在多个后继状态，即状态的转向是不确定的,2020年7月15日,编 译 原 理,2020年7月15日,编 译 原 理,对于*上的任何符号串，若存在一条从某一初态到某一终态的通路，且该通路上所有弧的标记字符依次连接成的串等于，则称可以被NFA N所识别或接受。 若N的初态结点同时为终态，或者存在一条从初态到某个终态结点的通路，则为N所识别。,NFA N所能识别的符号串的全体记为L(N)，称为NFA N所识别的语言,2020年7月15日,编 译 原 理,上例题相应的状态图为：,N所接受的语言（正规式） R=aa*b|ac*c|,2020年7月15日,编 译 原 理,

17、能接受 000 111 1010001 110000001,(0|1)*(000|111)(0|1) *,不能接受 00 01100,2020年7月15日,编 译 原 理,画出能够识别C语言注释/* */的DFA,2020年7月15日,编 译 原 理,状态1：注释开始状态。 状态2：进入注释体前的中间状态。 状态3：表明目前正在注释体中的状态。 状态4：离开注释前的中间状态。 状态5：注释结束状态，即接受状态。,2020年7月15日,编 译 原 理,用于某些重要软件的设计和构造 设计和检查数字电路行为的软件; 扫描如网页族等大规模文本以发现字、词或其它结构的出现频率的软件; 验证所有只有有限多

18、个不同状态的系统的软件，这类系统包括通信协议和信息安全交换协议。,有穷自动机的其它应用,2020年7月15日,编 译 原 理,几个概念,1）自动机所接收字符 如果对某一自动机M=（Q,f,S,Z） xVT 有f（S,x）=P,且PZ，则称字符x被自动机所接收。 2）自动机所接收输入串 自动机从开始状态读完全部输入串后，自动机恰好到达终止状态，则称输入串被自动机所接收。 定义为 f(q,) = q f (q,a) = f(f(q,a),) 其中qQ，a, *,2020年7月15日,编 译 原 理,3）自动机接收语言 自动机M所能接收的串组成一个集合，则称该集合为自动机M所能接收（识别）的语言。

19、用L（M）表示： L（M）ff(S,t)Z ,t VT* ）自动机的等价性 如果两个有穷自动机A1和A2满足 L(A1)=L(A2) 则称自动机自动机A1和A2是等价的。,2020年7月15日,编 译 原 理,DFA与NFA的区别,（1）DFA的转换函数 f 是一个单值函数； NFA的转换函数 f 是一个多值函数。 （2）DFA拥有唯一的初始状态； NFA拥有一个初态集。 （3）DFA状态图中不允许有边；NFA允许，并且允许多条。 （表示：在没有任何输入符号的情况下也可以进行移动） 这样，在NFA中从一个非终止状态经由一个或多个空移也可以到达某个终止状态。,2020年7月15日,编 译 原 理

20、,3.4.3 正规式RNFA M 对于字母表上的每个正规式R，可以构造一个上的NFA M， 使得L(M)=L(R)。,（1）对NFA M构造一个广义的状态图，其中只有一个初态X和终态Y，连接X和Y的有向弧标记为正规式。 （2）对正规式依次进行分解，分解的过程是一个不断加入结点和弧的过程，直到转换图上的所有弧标记上都是字母表上的元素或为止。,2020年7月15日,编 译 原 理,若s,t为上的正规式,2020年7月15日,编 译 原 理,2020年7月15日,编 译 原 理,已证明：非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的，也就是说，我们能够从：,NFA M,DFA M,构造成一

21、个,使得 L(M)=L(M),DFA是NFA的特例。有一种算法，将NFA转换成接受同样语言的DFA.这种算法称为子集法. 与某一NFA等价的DFA不唯一,3.4.4 NFA的确定化,2020年7月15日,编 译 原 理,从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态。 NFA到相应的DFA的构造的基本思路是： DFA的每一个状态对应NFA的一组状态.,2020年7月15日,编 译 原 理,(1) 合并 如果有 ，则把S2合并到S1,转换需解决的问题：,2020年7月15日,编 译 原 理,(2)状态合并,2020年7月15日,编 译 原 理,定义1

22、 状态集合I的-闭包，表示为-closure(I), 若qI，则q-closure(I)； 若qI，则从q出发经过任意条弧而能到达的任何状态q都属于-closure(I)。,为了使得NFA确定化，我们首先给出两个定义：,2020年7月15日,编 译 原 理,例： 如图所示的状态图： 令I=1， 求-closure（I）=？,根据定义： -closure（I）=1，3,课堂练习： 令I=1,2， 求-closure（I）=？,2020年7月15日,编 译 原 理,I是状态集，由I中的状态出发，经过一条a弧可能到达的状态的集合称为go（I，a），则 Ia= _closure ( go( I , a

23、 ) ),定义2 Ia 子集,2020年7月15日,编 译 原 理,例：令 I=1 Ia=-closure(go（I，a）) =-closure(f（1，a） =-closure(2，4）=2，4，6,根据定义1，2，可以将上述的M确定化（即可构造出状态 转换矩阵）,课堂练习： 令I=1,2,3 求Ia =？,2020年7月15日,编 译 原 理,课堂练习： 令I=1，设S= -closure（I），求 S？ Sa =？,将从状态S出发经过任意条弧所能到达的状态作为DFA的初态S 从S出发，把遇到输入符号a所转移到的后继状态集作为DFA的新状态 如此重复，直到不再有新的状态出现为止,NFA转换

24、为DFA的思想,2020年7月15日,编 译 原 理,I Ia Ib Ic,1,4 2,3 ,2,3 2 4 3,4,2 2 4 ,4 ,3,4 3,4,（1）构造一张表，它共有+1列 （2）第一行第一列为-closure(S) （3）求Ia （4）重复步骤（3） （5）将状态子集重新命名,2020年7月15日,编 译 原 理,将求得的状态转换矩阵重新编号 DFA M状态转换矩阵：,2020年7月15日,编 译 原 理,DFA M的状态图：,2020年7月15日,编 译 原 理,课堂练习,2020年7月15日,编 译 原 理,等价的DFA,a,a,b,start,2020年7月15日,编 译

25、原 理,3.4.5 DFA的最小化,如果不同的DFA能识别相同的语言，则称它们是等价的DFA。 在等价的DFA中，如果某一个DFA的状态数是最少的，则这个DFA是最简的。 对于任一个DFA，存在一个唯一的状态最少的等价的DFA,最简的DFA 它没有多余状态和等价状态,2020年7月15日,编 译 原 理,定义1 多余状态：从开始状态出发,任何输入串也不能到达的状态,2020年7月15日,编 译 原 理, 状态S和T必须同时为终态或非终态 对于所有输入符号，S和T必须转换到等价的状态里,2020年7月15日,编 译 原 理,把DFA的状态划分成一些不相交的子集 任何不同的两个子集的状态都是可区分

26、的 同一子集中的任何两个状态都是等价的,DFA最小化算法的基本思想(没有多余状态)：,2020年7月15日,编 译 原 理,解:,(一)区分终态与非终态,1,2,3,4,5,6,6,3,7,3,1,5,4,6,7,3,7,4,1,4,2,a,b,区号,（1）将所有状态分成两个子集：终态集和非终态集 （2）把等价的状态构成一个子集，若不等价继续划分 （3）结束后，重新标号或从每个子集中选一个状态做代表,2020年7月15日,编 译 原 理,区号,区号,2020年7月15日,编 译 原 理,将区号代替状态号得:,化简后的有穷自动机具有较少的状态，实现起来更加简洁。,2020年7月15日,编 译 原

27、 理,3.4.6. NFA M正规式R,(1)在M上加两个结点X,Y，从X结点用弧到M的所有初态，从M的所有终态用到Y结成与M等价的M ，M只有一个初态X和一个终态Y.,2020年7月15日,编 译 原 理,2020年7月15日,编 译 原 理,(2)消除M中的所有结点,2020年7月15日,编 译 原 理,3.5 正规文法与有穷自动机,（1）对于NFA M，存在一个右线性文法（左线性文法）G，使得L(G)=L(M)； （2）对于右线性文法（左线性文法）G，可以构造一个NFA M，使得L(M)=L(G)。,2020年7月15日,编 译 原 理,（1）文法的终结符号集为NFA的字母表； （2）文

28、法的非终结符号集为NFA的状态集； （3）文法的开始符号作为NFA的初态；增加一个终态Z （4）对文法中形如AtB的产生式，其中t为终结符或，A和B为非终结符，构造NFA的一个转换函数f(A,t)=B； （5）对文法中形如At的产生式，构造NFA的一个转换函数f(A,t)=Z。,3.5.1正规文法(右线性)NFA,2020年7月15日,编 译 原 理,例:求与文法GS等价的NFA GS: SaA|bB| AaB|bA BaS|bA|,2020年7月15日,编 译 原 理,【例】构造下述文法GZ的有穷自动机。 Z0A A0A0B B1A,与文法GZ等价的自动机M（Z，A，B，D，0，1，Z，D）

29、，其中 (Z,0)=A (Z,1 )= (A,0)=A,B (A,1)= (B,)=D (B,1)=A,2020年7月15日,编 译 原 理,3.5.2左线性文法有穷自动机,（1）文法的终结符号集为NFA的字母表； （2）文法的非终结符号集为NFA的状态集； （3）文法的开始符号作为NFA的终态；增加一个开始状态S. （4）对G中每一形如ABa的产生式,构造NFA的一个转换函数(B,a)=A。 （5）对G中每一形如Aa的产生式,构造NFA的一个转换函数(S,a)=A。,2020年7月15日,编 译 原 理,【例】构造下述文法GA的自动机。AA1B1 BB00,与文法GA对应的自动机M（S，A，

30、B，0，1，S，A），其中 （S，0）B （B，0）B （B，1）A （A，1）A,2020年7月15日,编 译 原 理,3.5.3 NFA正规文法,（1）NFA的字母表为文法的终结符号集； （2）NFA的状态集为文法的非终结符号集； （3）NFA的初态对应于文法的开始符号； （4）NFA的转换函数f(A,t)=B，写成一个产生式AtB； （5）对NFA的终态Z，增加一个产生式Z。,2020年7月15日,编 译 原 理,例:给出如图NFA等价的正规文法G,2020年7月15日,编 译 原 理,正规文法,NFA,正规式,6,5,4,3,1,2,DFA,最小化,转换方法,8,7,2020年7月15

31、日,编 译 原 理,3.6 词法分析程序的设计,词法分析程序的主要功能包括以下几个方面： （1）组织源程序的输入； （2）按规则拼单词，并转换成二元式形式进行输出； （3）删除注释行、空格及无用符号（如回车符、字符常数的引号等）； （4）行、列计数，发现并定位语法错误，列表打印源程序和错误清单； （5）建立符号表、常数表等表格。,2020年7月15日,编 译 原 理,源程序的输入及预处理 预处理的主要工作主要包括: (1)删除注释; (2)删除续行符号以及后续换行符号 (3)将换行符号和TAB键统一替换为空格. (4)大写换小写或相反,以便后续处理,2020年7月15日,编 译 原 理,（1）

32、根据词法规则写出正规文法； （2）将正规文法转换成状态图； （3）将状态图转换成流程图。,2020年7月15日,编 译 原 理,标识符 关键字(标识符的子集） 常数 运算符 +、*、= 分界符 ,、;,【例】假设某种语言的单词符号的子集有：,试构造此语言子集的词法分析程序。,2020年7月15日,编 译 原 理,（1）根据词法规则写出正规文法,字母 | 字母 | 数字） 数字 | 数字 + | * |=,2020年7月15日,编 译 原 理,字母 | 字母 | 数字） 数字 | 数字 + | * |=,（2）将正规文法转换成状态图,2020年7月15日,编 译 原 理,合并 将初始状态合并为一

33、个唯一的初态； 化简调整状态冲突并对冲突状态重新编号； 如有必要，增加出错状态。,2020年7月15日,编 译 原 理,标识符,无符号整数,单界符,双界符,合并后的状态图,2020年7月15日,编 译 原 理,（3）将状态图转换成流程图,写出词法分析程序,2020年7月15日,编 译 原 理,扫描程序的设计,下面用一个比较简单的语言作为例子来讨论扫描程序的设计。 假定该语言中有分界符或运算符（如，*，/，（，），关键字（如begin，abs，end），标识符（非保留字）以及整数。 至少要有一个空白符将相邻的标识符、整数和（或）关键字隔开，但不能用空白符将符号中的相邻字符分开。 此外，注解是以符

34、号/*开始，并以符号/*的第一次出现作为结束的。,2020年7月15日,编 译 原 理,2020年7月15日,编 译 原 理,有关变量和函数的说明,（1）ch字符变量，存放当前读进的源程序字符。 （2）token字符数组，存放构成单词符号的字符串。 （3）getch（）读字符函数，每调用一次从输入缓冲区中读进源程序的下一个字符放在ch中，并把读字符指针指向下一个字符。 （4）getbc（）函数，每次调用时，检查ch中的字符是否为空白字符，若是空白字符，则反复调用getch（），直至 ch中读入一个非空字符为止。 （5）concat（）函数，每次调用把当前ch中读进的字符与token中的字符串连

35、接。例如，假设token字符数组中原有值为“ab”,ch中存放着“c”, 调用concat（）函数后，token字符数组中的值变为“abc”。 （6）letter (ch) 和digit（ch）为布尔函数，它们分别判定ch中的字符是否为字母和数字，从而给出true或false布尔值。 （7）reserve（）函数，对token中的字符串查关键字表，若为关键字，则返回它的种别码，否则返回输出标识符的种别码和它的值。 （8）reback （）函数，读字符指针回退一个字符。 （9）return（）函数，收集并携带必要的信息返回调用程序，即返回到语法分析程序。 （10）dtb（）十进制转换为二进制函数

36、。,2020年7月15日,编 译 原 理,对应的C语言程序,Scanner( ) Token=null; Getch( ); Getbc( ); If (letter(ch) while(letter(ch)digit(ch) Concat( ); Getch( ); reback( ); C=reserve( ); If(c!=1) return(c,token); Else return(1,token); Else if(digit(ch) while(digit(ch) Concat( ); Getch( ); reback( ); return(2,dbt( ); ,Else Swich(ch) case:return(7, _); break; case:return(8,_); break; case:return(9, _); break;