词法分析(6学时)调整版.ppt

第四章 词法分析,有穷自动机 FA： 是一个识别装置，用于识别“所有句子”。 引入FA的目的： 为词法分析程序的自动构造寻找特殊的方法和工具 类型： 确定的有穷自动机 DFA 不确定的有穷自动机 NFA,返回,4.1 有穷自动机（FA ，Finite Automata）,FA ( Finite AutoMata ) ： 是一个识别装置，用于识别“所有句子”。 引入FA的目的： 为词法分析程序的自动构造寻找特殊的方法和工具 类型： 确定的有穷自动机 DFA 不确定的有穷自动机 NFA NFA DFA（子集法） DFA的化简（最小化 DFA）,下一节,确定的有穷自动机(DFA),1. 定义：一个DFA是一个五元组 M=(K , ,f ,S ,Z ) K：有穷的状态集 ：有穷的字母表（即输入字符的集合） f：转换函数 KK 上的映像 S：初态（初态唯一） Z：终态集（终态不唯一）,例：DFA M =(S,U,V,Q , a,b , f , S , Q) f： f(S,a)=U f(S,b)=V f(U,a)=Q f(U,b)=V f(V,a)=U f(V,b)=Q f(Q,a)=Q f(Q,b)=Q,确定的有穷自动机(DFA),2. DFA的“直观”表示： 状态图（状态转换图） 每个状态用结点表示 若f( Ki , a ) = Kj，则 初态用“=” 或 “-”标出 终态用双圈 或 “+”标出 矩阵 列标题：输出符号（VT） 行标题：状态 若f( Ki , a ) = Kj，则Ki和a的交汇处是 Kj 初态用“=” 标出 或 默认第一行（表格左端） 终态用“1”标出（表格右端） 非终态用“0”标出（表格右端）,例：参见上例的DFA，分别用状态图和矩阵表示。,确定的有穷自动机(DFA),3. DFA可以接受的句子（符号串）： 若t*，且存在f(S,t)= = P，P终态集， 则t为该DFA可以接受的句子。 即：从初态S到某终态结点P的道路上，所有弧上的标记符连接而成字符串t，t为该DFA可以接受的句子。,例：参见上例的DFA状态图，判断下列句子能否被接受： abba baab abb aa a,DFA M 能够接受的句子的全体记为 L(M) !,确定的有穷自动机(DFA),4. DFA的确定性： f: KK 是一个单值函数 即 对任何状态K，当输入字符a时，下一状态唯一。 上例的有穷状态机就是DFA,DFA M=（K，f，S，Z）的行为模拟程序： K:=S； c:=getchar; while (ceof) K:=f(K,c); c:=getchar; if (K in Z) return (yes); else return (no); ,DFA的行为模拟程序,返回,示例：,一个识别标识符的确定的有穷状态机,数字或其它,最小化DFA 没有多余状态(死状态) 没有两个状态是互相等价,DFA的化简（最小化DFA）,（1）多余状态： 从开始状态出发，任何输入串也不能到达的状态 处理：消除多余状态 （2）两个状态s和t等价：满足 一致性同是终态 或 同是非终态 蔓延性从s出发读入某个aa和从 t 出发读入某个a到达的状态等价。 处理：合并等价状态（使用“分割法”）,DFA的化简（最小化DFA）,举例：消除多余状态,解： 步骤一：消除多余状态 步骤二：使用分割法，合并等价状态。,举例：求最小化DFA,DFA的化简（最小化DFA）,举例：求最小化DFA,返回,P70 例2 课后题：4(b) 9,不确定的有穷自动机(NFA),1. 定义：一个NFA是一个五元组 M=(K , ,f ,S ,Z ) K：有穷的状态集 ：有穷的字母表（即输入字符的集合） f：转换函数 K*K+ 上的映像 （K+ 表示K的子集） S：初态集（初态不唯一） Z：终态集,例：NFA M=(0,1,2,3,4 , a,b , f ,0 ,2,4) f： f(0,a)=0,3 f(0,b)=0,1 f(1,b)=2 f(2,a)=2 f(2,b)=2 f(3,a)=4 f(4,a)=4 f(4,b)=4,2. NFA的“直观”表示： 状态图（状态转换图） 每个状态用结点表示 若f( Ki , a ) = Kj，则 初态用“=” 或 “-”标出 终态用双圈 或 “+”标出 矩阵 列标题：输出符号（VT） 行标题：状态 若f( Ki , a ) = Kj，则Ki和a的交汇处是 Kj 初态用“=” 标出 或 默认第一行（表格左端） 终态用“1”标出（表格右端） 非终态用“0”标出（表格右端）,举例：参见上例的NFA，分别用状态图和矩阵表示。,不确定的有穷自动机(NFA),3. NFA可以接受的句子（符号串）：(同DFA) 若t*，且存在f(S,t)= = P，P终态集， 则t为该NFA可以接受的句子。,例：参见上例的NFA状态图，判断下列句子能否被接受： aaa baab abb a aba bab,NFA M 能够接受的句子的全体记为 L(M) 对于每个NFA M 存在一个DFA M，使得L(M)= L(M) !,不确定的有穷自动机(NFA), 可以被 NFA M 能够接受的两种情况： M的某结点既是初态，又是终态 存在一条从初态到终态的道路,4. NFA的不确定性： 对于状态K，当输入字符a时，下一状态不一定唯一。 5. NFA的确定化： 对每个NFA M 一定存在一个DFA M，使得L(M)=L(M) 即：对每个NFA M存在着与之等价的DFA M 。 注：与某一NFA等价的DFA不唯一。,不确定的有穷自动机(NFA),返回,NFADFA（子集法）,（一）基本运算： 状态集合I的闭包：表示为-closure(I) 状态集I中的任何状态S经任意条弧而能到达的状态的集合。 注：状态集I的任何状态S都属于-closure(I) 状态集合I的a弧转换：表示为move(I,a) 定义为状态集合J，其中J是所有那些可从I的某一状态经过一条a弧而到达的状态的全体。 定义 Ia = -closure(J) 举例：参见P58 图4.4，求： -closure(0) move(0,a) move(0,b) -closure(1) move(2,a) move(2,b) move(0,1,2,4,7,a) -closure(1,3) move(0,1,2,4,7,b),NFADFA（子集法）,（二）转换的主要思想： DFA的一个状态可能对应NFA的一个或一组状态 DFA同样记录在NFA上读入某个VT后可能到达的所有状态,（三）子集法 NFA N=(K, ,f,K0,Kt)构造 DFA M=(S, ,d,S0,St)，使得 L(M)=L(N) ： M的状态集S由K的一些子集组成 M和N的输入字母表相同 转换函数d是这样定义的： d(S1 ,.,Sj,a) = -closure(move(S1 ,.,Sj,a) S0=-closure(K0)为M的开始状态 St=Si ,Sk ,.,Se，其中Si ,Sk ,.,SeS 且Si ,Sk,. SeKt,NFADFA（子集法）,构造 NFA N 的状态 K 的子集的算法： 假定所构造的子集族为 C = (T1, T2,. Ti)， 其中T1, T2,. Ti为状态 K 的子集。 1）开始，令-closure(K0)为C中唯一成员，并且它是未被标记的。 2）While(C中存在尚未被标记的子集T) do 标记T； for(每个输入字母a) do U:= -closure(move(T,a)； if（U不在C中） then 将U作为未标记的子集加在C中； 举例：参见P58 图4.4 构造NFA对应的子集,NFADFA（子集法）,初态,终态,DFA M：,课后习题：2，3，4(a),返回,4.2 词法分析程序的设计,词法分析（lexical analysis）功能： 逐个读入源程序字符，输出“单词符号” ，供语法分析使用。 主要任务： 读源程序，产生单词符号 其他任务： 滤掉空格，跳过注释、换行符 追踪换行标志，复制出错源程序 宏展开，,单词符号,一般可分为下列五种： 基本字（关键字）：begin, end, if, while 标识符：各种名称，如常量名、变量名、过程名 常数（量）：25, 3.1415, TRUE, “ABC”等 运算符：如 + - * / =等 界符：逗号，分号，括号等,词法分析程序与语法分析程序的接口方式,方式一（常用）：,：二元式（单词种类，值）,优点： （1）整个编译结构简洁、清晰、条理化 （2）可移植性好,词法分析程序与语法分析程序的接口方式,方式二（PL/0采用）：,4.3 单词的描述工具,单词的描述工具和识别工具： 正规文法（正则文法、3型文法） 正规式（正则式） 有穷自动机（NFA、DFA） 三者之间可以相互转换,下一节,正规文法,文法的每个产生式的形式都为： AaB 或 Aa 右线性 ABa 或 Aa 左线性 其中 A，BVN ，aVT*,例如： 标识符的正规文法：（若i表示任一字母，d表示任一数字） 标识符i|i字母数字 字母数字i|d|i字母数字|d字母数字 无符号整数的正规文法： 无符号整数 d | d无符号整数 运算符的正规文法： 运算符 +|-|*|/|=|等号 等号 = 界符的正规文法： 界符 , | ; | ( | ) |,返回,正规式(regular expression),正规式：是描述单词符号串规则的工具 设字母表=a,z, A,Z, 0,9 辅助字母表=， ， “”表示“闭包”，即任意有限次的自重复连接 “”表示“连接”，有时可以省略 “”表示“或” 优先顺序为“( )”、“”、“”、“” “”、“”和“” 都是左结合的 正规式为 ， ， ，(e) ，e1|e2 ，e1 e2 ， e* 中的符号。 （其中e表示任一正规式）,例1：令=0，1， 上正规式和相应正规集的例子有： 正规式 正规集 0 0 01 0,1 01 01 (01)(01)(中间省略连接号) 00,01,10,11 0 ,0,0, 任意个0的串 (01) ,0,1,00,01 所有由0 和1组成的串 (01)(0011)(01) 上所有含有两个相继 的0或两个相继的1组成 的串,正规式举例,两个正规式等价,若两个正规式 e1 和 e2 所表示的正规集相同, 则说 e1 和 e2 等价。 记作 e1 = e2 例如： 01 = 10 1(01) = (10)1 (01) = (01),正规式的代数运算,设r,s,t为正规式，则有： rs=sr “或”的交换律 r(st)=(rs)t “或”的结合律 (rs)t=r(st) “连接”的可结合律 r(st)=rsrt (st)r=srtr 分配律 r=r r=r 是“连接”的恒等元素,程序中的单词符号都能用正规式表示： e = (|)*,返回,转换,正规文法正规式, 等价转换的规则 不断用上述规则进行变换，直到最后只剩一个开始符号为止。,正规文法正规式 举例,例：正规文法GS: SaA ，将正规式正规文法。 Sa AaA AdA Aa Ad,SaA Sa AaA AdA Aa Ad,SaA|a AaA|dA Aa|d,Sa(A|) A(a|d)A Aa|d,Sa(A|) A(a|d)*(a|d),Sa(a|d)*(a|d)|),Sa(a|d)*,课后习题：8,正规式正规文法, 任何正规式 r：定义S为开始符号 Sr 转换规则 不断用上述规则进行变换，直到每个产生式的右部只含一个VT为止。,正规式正规文法 举例,例：正规式 r = 0(0|1)* ，将正规式正规文法。,S0 (0|1)*,S0A S(0|1)*,S0A A(0|1)A A,S0A A0A|1A A,S0A A0A A1A A,练习：R=(01|10)*(0|1) ，将正规式正规文法,返回,4.4 正规式和有穷自动机的等价性,转换,对于上的 NFA M，可以构造一个上的正规式 R，使得 L(R)=L(M)。 对于上的正规式R，可以构造一个上的 NFA M，使得 L(M)=L(R)。,在FA M的状态图上加两个状态结点x和y。 从x结点出发，用弧连接 x结点 到 所有初态结点 从M的 所有终态结点 用弧连接到 y结点 此时， x为初态和y为终态。 利用消结规则，逐步消去M中的所有结点，直至只剩下x和y。 最后x和y结点间的弧上的标记则为所求的正规式R。,FA 正规式,举例：求FA所对应的正规式R,解：,FA 正规式,则：R=(a|b)* (aa |bb)(a|b)*,课后习题：9,将正规式分解成一系列 子表达式。 对于每个子表达式，用如下规则构造 FA：,正规式FA,注意：由于分解的方法和顺序不同， 构造的NFA可能不同，但最小化的DFA一定相同 ！,举例：为 R=(a|b)*abb 构造NFA N，使得L(N)=L(R)。,P68 例1 课后习题：1(3)(4) 11,正规式FA,4.5 正规文法和有穷自动机的等价性,转换,输入字符集与正规文法的 VT 相同 状态集与正规文法中的 VN 相同 左线性正规文法的转换规则： 增加一个初态结点，开始符号对应的结点作为终态 对形如 At 的规则，引一条从初始状态到A的弧，标记为t 对形如 ABt 的规则，引一条从B到A的弧，标记为t 右线性正规文法的转换规则： 增加一