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

第四章 词法分析 正规式 NFA 正规文法 DFA 最小化DFA 子集法 语言 消除多余状态 合并等价状态 n有穷自动机 FA： 是一个识别装置，用于识别“所有句子”。 n引入FA的目的： 为词法分析程序的自动构造寻找特殊的方法和工 具 n类型： 确定的有穷自动机 DFA 不确定的有穷自动机 NFA 返回 4.1 有穷自动机（FA ，Finite Automata） nFA ( Finite AutoMata ) ： 是一个识别装置，用于识别“所有句子”。 n引入FA的目的： 为词法分析程序的自动构造寻找特殊的方法和工 具 n类型： 确定的有穷自动机 DFA 不确定的有穷自动机 NFA nNFA DFA（子集法） nDFA的化简（最小化 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)=Uf(S,b)=V f(U,a)=Qf(U,b)=V f(V,a)=Uf(V,b)=Q f(Q,a)=Qf(Q,b)=Q 确定的有穷自动机确定的有穷自动机( (DFA)DFA) 2. DFA的“直观”表示： 状态图（状态转换图） 每个状态用结点表示 若f( Ki , a ) = Kj，则 初态用“=” 或 “-”标出 终态用双圈 或 “+”标出 矩阵 列标题：输出符号（VT） 行标题：状态 若f( Ki , a ) = Kj，则Ki和a的交汇处是 Kj 初态用“=” 标出 或 默认第一行（表格左端 ） 终态用“1”标出（表格右端） 非终态用“0”标出（表格右端） KiKj a 例：参见上例的DFA，分别用状态图和矩阵表示。 确定的有穷自动机确定的有穷自动机( (DFA)DFA) 3. DFA可以接受的句子句子（符号串符号串）： 若t*，且存在f(S,t)= = P，P终态集， 则t为该DFA可以接受的句子。 即：从初态S到某终态结点P的道路上，所有弧上的 标记符连接而成字符串t，t为该DFA可以接受的 句子。 例：参见上例的DFA状态图，判断下列句子能否被接受： abbabaababbaaa DFA M 能够接受的句子的全体记为 L(M) ! 确定的有穷自动机确定的有穷自动机( (DFA)DFA) 4. DFA的确定性： f: KK 是一个单值函数 即 对任何状态K，当输入字符a时，下一状态唯一 。 上例的有穷状态机就是DFA DFA M=（K，f，S，Z）的行为模拟程序： K:=S； c:=getchar; while (c” 或 “-”标出 终态用双圈 或 “+”标出 矩阵 列标题：输出符号（VT） 行标题：状态 若f( Ki , a ) = Kj，则Ki和a的交汇处是 Kj 初态用“=” 标出 或 默认第一行（表格左端 ） 终态用“1”标出（表格右端） 非终态用“0”标出（表格右端） KiKj a 举例：参见上例的NFA，分别用状态图和矩阵表示。 不确定的有穷自动机不确定的有穷自动机( (NFA)NFA) 3. NFA可以接受的句子句子（符号串符号串）：(同DFA) 若t*，且存在f(S,t)= = P，P终态集， 则t为该NFA可以接受的句子。 例：参见上例的NFA状态图，判断下列句子能否被接受： aaabaababb aababab NFA M 能够接受的句子的全体记为 L(M) 对于每个NFA M 存在一个DFA M，使得L(M)= L(M) ! 不确定的有穷自动机不确定的有穷自动机( (NFA)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)NFA) 返回 NFADFA（子集法） （一）基本运算： n n 状态集合状态集合I I的的 闭包闭包：表示为 - -closure(I)closure(I) 状态集I中的任何状态S经任意条弧而能到达的状态状态 的集合的集合。 注：状态集I的任何状态S都属于-closure(I) n n 状态集合状态集合I I的的a a弧转换弧转换：表示为move(I,a)move(I,a) 定义为状态集合J，其中J是所有那些可从I的某一状 态经过一条a弧而到达的状态的全体。 定义 Ia = -closure(J) 举例：参见P58 图4.4，求： - -closure(0)closure(0)move(0,a)move(0,a)move(0,b)move(0,b) - -closure(1)closure(1)move(2,a)move(2,a)move(2,b)move(2,b) move(0,1,2,4,7,a)move(0,1,2,4,7,a) - -closure(1,3)closure(1,3)move(0,1,2,4,7,b)move(0,1,2,4,7,b) NFADFA（子集法） （二）转换的主要思想： DFADFA的的一个一个状态可能对应状态可能对应NFANFA的的一个或一组一个或一组状态状态 DFADFA同样同样记录记录在在NFANFA上上读入某个读入某个VTVT后可能到达的所后可能到达的所 有状态有状态 （三）子集法 NFA NFA N N=(K, =(K, ,f,K,f,K 0 0 ,K,K t t ) )构造构造 DFA DFA M M=(S, =(S, ,d,S,d,S 0 0 ,S,S t t ) )， 使得使得 L(M)=L(N)L(M)=L(N) ： M M的状态集的状态集S S由由K K的一些子集组成的一些子集组成 M M和和N N的的输入字母表相同输入字母表相同 转换函数转换函数d d是这样定义的：是这样定义的： d(d( S S1 1 ,., ,.,S S j j ,a) = a) = - -closure(moveclosure(move( ( S S1 1 ,., ,.,S S j j ,a)a) S S 0 0 = = - -closure(Kclosure(K 0 0 ) )为为M M的开始状态的开始状态 S S t t =S Si i , ,S Sk k ,.,S,.,S e e ，其中，其中 S Si i , ,S Sk k ,.,S,.,S e e S S 且且 S Si i , ,S Sk k, , ,.,. S Se e K K t t NFADFA（子集法） 构造构造 NFA N NFA N 的状态的状态 K 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 P58 图图4.4 4.4 构造构造NFANFA对应的子集对应的子集 NFADFA（子集法） -closure(move(Ti,a)-closure(move(Ti,b) T0= -closure(0) =0,1,2,4,7 T1 = 1,2,3,4,6,7,8 T2 = 1,2,4,5,6,7 T1= 1,2,3,4,6,7,8 T1 = 1,2,3,4,6,7,8 T3 = 1,2,4,5,6,7,9 T2= 1,2,4,5,6,7 T1 = 1,2,3,4,6,7,8 T2 = 1,2,4,5,6,7 T3= 1,2,4,5,6,7,9 T1 = 1,2,3,4,6,7,8 T4 = 1,2,4,5,7,10 T4= 1,2,4,5,7,10 T1 = 1,2,3,4,6,7,8 T2 = 1,2,4,5,6,7 b 0 2 134 a b a a a a b b b 初态 终态 DFA M：课后习题：2，3，4(a) 返回 4.4.2 2 词法分析程序的设计词法分析程序的设计 词法分析（词法分析（lexical analysislexical analysis）功能：功能： 逐个读入逐个读入源程序源程序字符字符，输出，输出“单词符号单词符号” ” ，供，供 语法分析使用。语法分析使用。 主要任务：主要任务： 读源程序，产生单词符号读源程序，产生单词符号 其他任务：其他任务： 滤掉空格，跳过注释、换行符滤掉空格，跳过注释、换行符 追踪换行标志，复制出错源程序追踪换行标志，复制出错源程序 宏展开，宏展开， 单词符号单词符号 n n 一般可分为下列五种：一般可分为下列五种： 基本字基本字（关键字关键字）：）：begin, end, if, whilebegin, end, if, while 标识符标识符：各种名称，如常量名、变量名、过程：各种名称，如常量名、变量名、过程 名名 常数常数（量）：（量）：25, 3.1415, 25, 3.1415, TRUE, “ABC”TRUE, “ABC”等等 运算符运算符：如：如 + - * / 等号 等号 = n n 界符界符的正规文法的正规文法： 界符 , | ; | ( | ) | 返回 正规式正规式( (regular expression)regular expression) n正规式：是描述单词符号串规则的工具 设字母表=a,z, A,Z, 0,9 辅助字母表=， ， “”表示“闭包”，即任意有限次的自 重复连接 “”表示“连接”，有时可以省略 “”表示“或” 优先顺序为“( )”、“”、“”、 “” “”、“”和“” 都是左结合的 正规式为 ， ， ，(e) ，e1|e2 ，e1 e2 ， e* 中的符号。 （其中e表示任一正规式） 例例1 1：令：令 =0 0，11， 上正规式和相应正规集的例子有上正规式和相应正规集的例子有 ： 正规式正规式正规集正规集 00 010,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组成 的串 正规式举例正规式举例 两个正规式两个正规式等价等价 n若两个正规式 e1 和 e2 所表示的正规集相同正规集相同, 则说 e1 和 e2 等价。 记作 e1 = e2 例如： 01 = 10 1(01) = (10)1 (01) = (01) 正规式的代数运算 n n 设设r,s,tr,s,t为正规式，则有：为正规式，则有： r r s=ss=s r r“或或”的交换律的交换律 r r ( (s s t)=(t)=(r r s s) ) t t “或或”的结合律的结合律 ( (rs)trs)t= =r(str(st) )“连接连接”的可结的可结 合律合律 r(s r(s t)=t)=rsrs rtrt (s(s t)r=t)r=srsr trtr分配律分配律 r=r r=r r r =r=r 是是“连接连接”的恒等元素的恒等元素 n n 程序中的程序中的单词符号单词符号都能用正规式表示：都能用正规式表示： e = (|) * * 返回 正规式 NFA 正规文法 DFA 最小化DFA 子集法 语言 消除多余状态 合并等价状态 转换 正规文法正规式 等价转换的规则 不断用上述规则进行变换，直到最后只剩一个开始符 号为止。 正规规文法正规规式 AxB By Axy AxA Ay Ax*y Ax Ay Ax | y 正规文法正规式 举例 例：正规文法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为止。 正规规式正规规文法 Axy AxB By Ax*y AxB 或 AxA Ay Ay BxB By Ax|y Ax Ay 正规式正规文法 举例 例：正规式 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 正规文法 DFA 最小化DFA 子集法 语言 消除多余状态 合并等价状态 转换 n对于上的 NFA M，可以构造一个上的正规式 R ，使得 L(R)=L(M)。 n对于上的正规式R，可以构造一个上的 NFA M， 使得 L(M)=L(R)。 n 在FA M的状态图上加两个状态结点加两个状态结点x x和和y y。 从x结点出发，用弧连接 x结点 到 所有初态结点所有初态结点 从M的 所有终态结点所有终态结点 用弧连接到 y结点 此时， x x为初态为初态和y y为终态为终态。 n 利用消结规则，逐步消去M中的所有结点，直至只剩下x和y 。 n 最后x和y结点间的弧上的标记则为所求的正规式R。 FA 正规式 123 R1R2 13 R1R2 13 R1 R2 13 R1| R2 123 R1R3 R2 13 R1 R2* R3 举例：求FA所对应的正规式R 0 3 12 4a,b a a a,b a,b b b 解： 0 3 12 4 a,ba a a,b a,b b b xy FA 正规式 0 2 4 a|b aa a|b a|b bb xy 0 a|b aa(a|b)* bb(a|b)* xy 则：R=(a|b)* (aa |bb)(a|b)* 0 a|b aa(a|b)* bb(a|b)* xy 0 a|b xy (aa |bb)(a|b)* xy (a|b)* (aa |bb)(a|b)* 课后习题：9 n 将正规式分解成一系列 子表达式。 n 对于每个子表达式，用如下规则构造 FA： 正规式FA 正规规式FA R R1R2 12 12 12 R 正规规式FA R1 | R2 R* 13 R1 R2 123 R 注意：由于分解的方法和顺序不同， 构造的NFA可能不同，但最小化的DFA一定相同 ！ 13 R1 R2 2 举例：为 R=R=(a|b)(a|b) * * abbabb 构造NFA N，使得L(N)=L(R)。 136 b 2 a b 45 ab 解：对应的NFA为 NFADFA最小化DFA P68 例1 课后习题：1(3)(4) 11 正规式FA 4.5 正规文法和有穷自动机的等价性 正规式 NFA 正规文法 DFA 最小化DFA 子集法 语言 消除多余状态 合并等价状态 转换 n输入字符集与正规文法的 VT 相同 n状态集与正规文法中的 VN 相同 n左线性正规文法的转换规则： 增加一个初态结点，开始符号对应的结点作为终态 对形如 At 的规则，引一条从初始状态到A的弧， 标记为t 对形如 ABt 的规则，引一条从B到A的弧，标记为 t n右线性正规文法的转换规则： 增加一个终态结点，开始符号对应的结点作为初态 对形如 At 的规则，引一条从A到终态结点的弧， 标记为t