《编译3词法分析zss2.ppt

编译原理(第三版) 陈火旺等编著 （2012年9月-12月） 主讲：朱世松 计算机学院 3.3 正规表达式与有限自动机 几个概念: 考虑一个有穷 字母表∑ (字符集) 其中每一个元素称为一个字符 ∑上的字(也叫字符串) 是指由∑中的字符所构成的一个有穷序列 不包含任何字符的序列称为空字，记为ε 用∑*表示∑上的所有字的全体,包含空字ε 例如: 设 ∑={a， b}，则 ∑*={ε,a,b,aa,ab,ba,bb,aaa,...} ∑*的子集U和V的连接（积）定义为 UV＝{ ?? | ??U ??V } V自身的 n次积记为 Vn=VV…V 规定V0={?}，令 V*=V0∪V1∪V2∪V3∪… 称V*是V的闭包; 记 V＋＝VV* ，称V+是V的正规闭包。 3.3.1 正规式和正规集 正规集可以用正规表达式（简称正规式）表示。 正规表达式是表示正规集一种方法。一个字集合是正规集当且仅当它能用正规式表示。 正规式和正规集的递归定义： 对给定的字母表? 1)? 和?都是?上的正规式，它们所表示的正规集为{?}和?; 2) 任何a?? ，a是?上的正规式，它所表示的正规集为{a} ; 3) 假定e1和e2都是?上的正规式，它们所表示的正规集为L(e1)和L(e2)，则 i) (e1|e2)为正规式，它所表示的正规集为 L(e1) ? L(e2)， ii) (e1· e2)为正规式，它所表示的正规集为 L(e1) L(e2)， iii) (e1)*为正规式，它所表示的正规集为 (L(e1))*， 仅由有限次使用上述三步骤而定义的表达式才是?上的正规式，仅由这些正规式表示的字集才是?上的正规集。 所有词法结构一般都可以用正规式描述。 若两个正规式所表示的正规集相同，则称这两个正规式等价。如 b(ab)*=(ba)*b (a*b*)*=(a|b)* 对正规式，下列等价成立： e1|e2 = e2|e1 交换律 e1 |(e2|e3) = (e1|e2)|e3 结合律 e1(e2e3) = (e1e2)e3 结合律 e1(e2|e3) = e1e2|e1e3 分配律 (e2|e3)e1 = e2e1|e3 e1 分配律 e? = ? e = e （e1e2 e2 e1 ） 3.3.2 确定有限自动机(DFA) 对状态图进行形式化，则可以下定义： 自动机M是一个五元式M=(S, ?, f, S0, F),其中： 1. S: 有穷状态集， 2. ?：输入字母表(有穷)， 3. f: 状态转换函数，为S???S的单值部分映射，f(s，a)=s’。表示：当现行状态为s，输入字符为a时，将状态转换到下一状态s’。我们把s’称为s的一个后继状态。 4. S0?S是唯一的一个初态； 5. F?S ：终态集(可空，识别不出的字符串)。 例如：DFA M=({0，1，2，3}，{a，b}，f，0，{3})， 其中：f定义如下： 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 DFA可以表示为状态转换图。假定DFA M含有m个状态和n个输入字符，那么，这个图含有m个状态结点，每个结点顶多含有n条箭弧射出，且每条箭弧用Σ上的不同的输入字符来作标记。 对于?*中的任何字?，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于?，则称?为DFA M所识别(接收) DFA M所识别的字的全体记为L(M)。 可以证明：?上的字集 V??* 是正规集，当且仅当存在?上的DFA M，使得V＝L(M)。 3.3.3 非确定有限自动机(NFA) 定义：一个非确定有限自动机(NFA) M是一个五元式M=(S, ?, f, S0, F)，其中： 1 S: 有穷状态集； 2 ? ：输入字母表(有穷)； 3 f: 状态转换函数，为S??*?2S的部分映 射(非单值，S的子集映射)； 4 S0?S是非空的初态集； 5 F ?S ：终态集(可空)。 从状态图中看NFA 和DFA的区别： 1 弧上的标记可以是?*中的一个字，而不一定是单个字符； 2 同一个字可能出现在同状态射出的多条弧上。 DFA是NFA的特例。 定义：对于任何两个有限自动机M和M’，如果L(M)=L(M’)，则称M与M’等价。 自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的。 对于每个NFA M存在一个DFA M’，使得 L(M)=L(M’)。亦即DFA与NFA描述能力相同。 1. 假定NFA