编译原理第2章 词法分析-2课件.ppt

2.3 正规表达式与有限自动机简介 2.3.1 正规表达式与正规集 状态转换图对构造词法分析程序是行之有效的，为了便于词法分析器的自动生成，还须将状态转换图的概念加以形式化。正规表达式就是一种形式化的表示法，它可以表示单词符号的结构，从而精确地定义单词符号集。正规表达式简称为正规式，它表示的集合即为正规集。 正则表达式 基本概念： 字母表：非空有限集，?，其元素称为符号或字母. 符号串：符号的有限序列，也称为‘字’。?表示空串 空串集{?}不同于空集? 。 符号串长度：符号串中字符的个数.|?| 符号串连接：?和?都是符号串，则??为符号串的连接 特别有： ? ? = ? ? = ? 符号串集的乘积：A和B是符号串的集合，则称 AB={??| ??A，? ?B} 特别有：?A=A?=A，其中?表示空集。 符号串集的方幂： 设A是符号串的集合，则称Ai为符号串集A的方幂，其中i是非负整数。 A0 ={?} A1 = A , A2 = A A AK = AA......A(k个) 符号串集合的正闭包： A+ =A1 ? A2 ?A3 ...... 符号串集合的闭包(星闭包)(克林闭包）： A* =A0 ? A1 ? A2 ?A3 ...... 正则表达式及其一些性质 ?为给定的字母表，则每个?上的正则表达式将定义?上的一个字符串集。 用R表示? 上的正则表达式，用L(R)表示R所表示的字符串集合 。即：函数L表示 正则表达式?字符串集的映射。 为了理解正规式与正规集的含义，我们以程序语言中的标识符为例予以说明。 程序语言中使用的标识符是一个以字母开头的字母数字串，如果字母用letter表示，数字用digit表示，则标识符可表示为 letter (letter∣digit)* 其中，letter与 (letter∣digit)*的并置表示两者的连接；括号中的“∣”表示letter或digit两者选一；“*”表示零次或多次引用由“*”标记的表达式；(letter∣digit)*是letter∣digit的零次或多次并置，即表示一长度为0、1、2、…的字母数字串；letter (letter∣digit)*表示以字母开头的字母数字串，也即标识符集。letter (letter∣digit)*就是表示标识符的正规式，而标识符集就是这个正规式所表示的正规集。 对于给定的字母表Σ，正规式和正规集的递归定义如下： (1) ε和Ф都是Σ上的正规式，它们所表示的正规集分别为{ε}和Ф。 (2) 对任一个a∈Σ，a是Σ上的一个正规式，它所表示的正规集为{a}。 (3) 如果R和S是Σ上的正规式，它们所表示的正规集分别为L(R)和L(S)，则： ① R∣S是Σ上的正规式，它所表示的正规集为L(R)∪L(S)； ② R.S是Σ上的正规式，它所表示的正规集为L(R) L(S)； ③ (R)*是Σ上的正规式，它所表示的正规集为(L(R))*； ④ R也是Σ上的正规式，它所表示的正规集为L(R)。 (4) 仅由有限次使用规则(1)～(3)得到的表示式是Σ上的正规式，它所表示的集合是Σ上的正规集。 在上述定义中，规则(1)、(2)为基础规则，规则(3)为归纳规则，规则(4)是界限规则或终止规则。此外，Σ上的一个字（符号串）是指由Σ中的字符所构成的一个有穷序列；不包含任何字符的序列称为空字，用ε表示。我们用Σ*表示Σ上所有字的全体，则空字ε也在其中。例如，若Σ={a，b}，则Σ*={ε，a，b，aa，ab，ba，bb，aaa，…}。我们还用Ф表示不含任何元素的空集{}。这里需要注意ε、{}和{ε}的区别：{ε}是由空字组成的集合，而{}则表示不含任何字的集合。 正规式间的运算符“∣”表示或，“· ”表示连接（通常可省略），“*”表示闭包，使用括号可以改变运算的次序。如果规定“*”优先于“· ”，“· ”优先于“∣”，则在不出现混淆的情况下括号也可以省去。注意，Σ*的正规式R和S的连接可以形式化地定义为 RS={α β∣α∈Rβ∈S} 即集合RS中