[理学]编译原理 第三章.ppt

第三章 有限自动机和词法分析器 词法分析中的主要问题 正则表达式 有限自动机 词法分析器的构造,3.1 词法分析 一、词法分析器的功能 将以字符为单位的源程序转换成词法单元序列。 例如：有小型语言TOYL的程序: begin x:=10; read(y); x:=x+y end 经过词法分析之后得到结果(词法单元序列)如下： 1(BEGIN,”begin”) 2(ID,”x”) 3(ASS_OP,”:=” ) 4(NUMBER,”10”) 5(SEMI,”;”) 6(READ,”read”) 7(OPEN,”(”) 8(ID ,”y”) 9(CLOSE,”)”) 10(SEMI,”;”) 11(ID,”x”) 12(ASS_OP,”:=”) 13(ID,”x”) 14(PLUS_OP,”+”) 15(ID,”y”) 16(END,”end”) 词法单元由两部分组成：（词法单元名，属性值) 词素是一个词法单元的一个实例。,附属词法分析器,调用,token,语法分析器,源程序,源程序,独立词法分析器,token,序列,语法分析器,二、词法分析器的分类 作为语法分析器的子程序, 作为编译器的独立一遍任务,不同语言，词法单元的分类互不相同，一般而言，词法单元类别包含： 1、每个关键字有个词法单元。 2、表示运算符的词法单元，可以代表单个运算，也可以表示一类运算。 3、一个表示所有标识符的词法单元，标识符词法单元属性值比较复 杂，通常，要为标识符建立符号表，该标识符的所有属性将登记在 其对应的符号表条目中，则该标识符词法单元的属性值即为其在符 号表对应条目的指针。 4、一个或多个表示常量的词法单元。 5、每个界限符号有一个词法单元，如左右括号、逗号、分号等。,三、关键字（保留字）的处理 区分一般标识符和保留字的方法： 先构造好保留字表，每当拼出一个ID型的单词时，先查 保留字表，若找到，则为保留字，否则为一般标识符； 该方法需要注意保留字表结构的构造。 在拼出单词的同时完成保留字的判断，该方法速度较 快，但程序较冗长。,四、空格符、制表符和换行符的处理 空格符、制表符只有词法意义而没有语法和语义上的意 义，因此词法分析后需删除，但字符串中的空格符不能 删除； 换行符对错误处理具有重要的意义，在发现错误时指出 错误的行号，因此词法分析时不能删除。,五、括号类配对预检 程序中括号配对的正确性，对于提高语法分析器的报 错准确率具有非常重要的意义，在词法分析阶段进行括 号配对的检查是必要的； 括号配对检查的方法： 为每一类括号设置一个计数器，每当遇到开括号 时，计数器加1，遇到闭括号时，计数器减1，计数器 初始值为0，程序结束时，计数器的值不为0，则括号 不配对。,六、向前看多个字符的处理 例如： x:10100; 七、词法错误修正 1、当发现程序的词法错误时，并非立即停止分析，而是采用一定的补救措施，使词法分析过程继续进行下去，并尽可能地使后继的词法分析工作不受到影响。 2、修正的方法 从剩余的输入中删除一个字符； 向剩余的输入中插入一个遗漏的字符； 用一个字符替换另一个字符； 交换两个相邻字符； 将出错部分作为一个特殊的token保留，以便进行后期的语法矫正,3.2正则表达式 一、基本概念 字母表:任何语言均有固定的字母表。 符号串：也可称为字或句子，用表示空符号串。 符号串长度： | |=0 语言：给定字母表上一个任意的可数的串的集合。 符号串连接 符号串集合的并集 符号串集合的连接 符号串集合的方幂 符号串集合的正闭包 符号串集合的星闭包 例如：P73 例：任意a串，任意0、1串的集合,二、正则表达式 设是一个给定的字符集， 则上的每一个正则表达式R 均定义了一个符号串的集合L(R ), 因此正则表达式是语言中表示单词的工具。, 是正则表达式, L( )= , 是正则表达式, L( ) = ,a 是正则表达式, L( a )= a ,例、以00结尾的二进制数字串对应的正则表达式为：,设A,B , 则:,R ,(A) R , L(A) )=L(A); A|B R , L(A|B)=L(A) L(B); AB R , L(AB)= L(A) L(B); A* R , L(A* )=L(A)* A+ R , L(A+ )=L(A)+,(0|1)*00,例、串中至少包含两个连续的0或两个连续的1构成的二进制串：,(0|1)*(00|11)(0|1)*,例：P74,三、正则定义 使用联立方程定义相关的一组正则表达式。由于正则定义可以引入变量，因此正则定义比正则表达式的表达能力强。,练习：写出以下符号串集合所对应的正则表达式： 1、以0开始以1结尾的所有二进制数字串； 2、L(G)=a2n+1b2ma2p+1|n=0, p=0, m=1,解答： 1、0(0|1)*1 2、a(aa)*bb(bb)*a(aa)*,例、相同0、1串中夹一个a的符号串的集合：,A-yay y-(0|1)*,例：P75,3.3 有穷自动机 一、自动机与正则文法、正则表达式具有相 同的表达能力。 二、有穷自动机分为： 不确定自动机NFA 确定自动机DFA,三、不确定有穷自动机NFA 1、不确定有穷自动机的组成 符号集； 状态集合S=S0,S1,.Sn; 开始状态S0； 转换函数：S （） S； 终止状态集：Si1,Si2,Sik.,2、不确定有穷自动机的表示方法 (1)根据定义的描述法 (2)状态转换图法 (3)状态转换表法 3、不确定有穷自动机的特点 从同一个状态出发的不同边上可以标注相同的符号； 允许有边。,4、称字符串a1,a2,an被有穷自动机所接受，如果存在 状态序列S0，S1，Sn,使得 S0 S1, S1 S2, , Sn-1 Sn 其中S0为初始状态，Sn为一个终止状态，中间状态可以为初始状态，也可为一个终止状态。 5、称一个自动机所能接受的所有符号串构成的集合为该 自动机所接受的语言。 例：P92,a1,a2,an,6、确定有穷自动机 确定有穷自动机是不确定有穷自动机的一个特例，它要求满足： 1）没有边； 2）对于每个状态s和每个输入符号a，有且仅有一条标有a的边 离开，即从一个状态出发的边上不允许标有相同的字符,例如：接受整数、实数和标识符的自动机,7、确定有穷自动机的实现 (1)采用状态转换表的实现方式 int scanner(char input) in=0;S=S0; ch=inputin+; while(TTS,ch)!=undef ,(2)直接转换法,int scanner() state=1; getch(ch); while(state!=0 ,初始状态为：1 终止状态为：3 无效状态为：0,case 3: switch(ch) case a:state=3;break; case b:state=0;break; default: state=0;break; break; getch( ); if (state=3 ,1、 合并: -closure(SS),计算-closure(SS)算法(见P95)： 【1】首先令-closure(SS) 包含SS； 【2】若S -closure(SS) ，且S S1,S1 -closure(SS), 则将 S1加入到-closure(SS)中； 【3】直到-closure(SS)中没有一个状态S有边指向-closure(SS) 以外的状态为止。,四、NFA到DFA的转换过程,1,2,3,4,5,6,7,x,z,y,-closure(1)=1,2,3,4 -closure(2)=1,2,3,4 -closure(3)=1,2,3,4 -closure(4)=1,2,3,4 -closure(5)=5,6,7 -closure(6)=6,7,2、NFA转换成DFA,（1）不含边的NFA转换DFA：图3-21转换成图3-25,（2）包含边的NFA转换DFA：图3-31转换成图3-33,（3）NFA转换成DFA的算法：P95图3-29,五、确定有限自动机的最小化 * 1、合并法 首先将自动机的状态分成两类：所有接受状态为一类，所有非接受状态为一类。然后在自动机的状态转换表中寻找相同的两行，如这两行对应的状态S i和Sj属于同一类，则可以合并。用（Si,Sj）表示Si吸收Sj，则 .若Sj是开始状态，则Si成为开始状态； .删除状态转换表中的Sj行； .将状态转换表中的Sj统统改为Si。,2、分离法 对自动机M进行最小化，即寻找一个状态数比M更少的DFA M，使得M和M所识别的符号串相同。 自动机最小化的关键在于把它的状态集分成一些两两互不相交的子集，使得任何两个不同子集中的状态都是不等价的，而同一子集中的所有状态都是等价的，这样以一个状态为代表而删除其它等价的状态，也就获得了状态个数最少的DFA。,分离法算法 1、开始时将自动机的状态分成两类：所有接受状态为一类，所有非接受状态为一类。 2、考虑已有的状态集（类）是否需进一步分离。如果两个状态P和Q属于同一类，当且仅当对于任何输入字符a，状态P和Q转换成的状态均属于已有的同一类。如发现某一状态集中有不等价的状态，则应将它们分离，重复以上过程，直到不再产生新的类为止。,3、按步骤2得到最终的类划分后，取每一类中的一个状态作代表，而删除其他一切等价的状态，则所有这些状态代表构成了最小化自动机M的状态集合。 4、删除所有死状态（对于任何字符，均不能从它到终止状态或不可能从开始状态到它的那些状态）。,例、将以下自动机最小化：,A,B,F,C,D,E,G,a,b,a,b,b,b,b,a,b,a,例：P98（例3.24）,六、正则表达式到DFA的转换,1、正则定理：对于任意的正则表达式RE，均可构造一个有 穷自动机FA，使得FA所接受的符号串的集合 与RE所接受的符号串集合等价。,2、结构化自动机（SFA）的特点： （1）SFA只有一个入口状态和一个出口状态； （2）SFA的入口状态和出口状态不重叠； （3）SFA的入口状态没有输入边，出口状态没有输出边； （4）SFA的其他状态无指向SFA外部的边，也无从SFA外部指 向SFA内部的边。,3、转换规则,RE=,RE=a,a,RE=AB,SFA(A),SFA(B),RE=A|B,SFA(A),SFA(B),RE=A*,SFA(A),练习： 1、(a|b)*(aa|bb)(a|b)* 2、（a*|b*）b(ba)*,3、为正则表达式(a|b)*a(a|b)构造一个DFA。,例1、（a|b）a,例2、 a*,例4、 a*b*,例5、 a*|b*,例6、 (a|b)*,例3、 ab,七、词法分析器的构造 1、确定语言的单词集合 通常分为：标识符、保留字、常量、运算符、界限符 2、为每类单词定义词法单元结构 标识符：(ID,标识符首地址） 常量（NUMBER,常量值地址） 保留字、界