复习：程序语言的语法描述 几个概念: 考虑一个有穷 字母表∑ 字符集 其中每一个元素称为一个字符 ∑上的字(也叫字符串) 是指由∑中的字符所构成的一个有穷序列 不包含任何字符的序列称为空字，记为ε 用∑*表示∑上的所有字的全体,包含空字ε 国防科技大学计算机系602教研室

复习：程序语言的语法描述 ∑*的子集U和V的连接（积）定义为 UV＝{  | U & V } V自身的 n次积记为 Vn=VV…V 规定V0={}，令 V*=V0∪V1∪V2∪V3∪… 称V*是V的闭包; 记 V＋＝VV* ，称V+是V的正规闭包。 国防科技大学计算机系602教研室

复习：程序语言的语法描述 上下文无关文法的定义： 一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中 VN：非终结符集合(非空)，且VT  VN= S：文法的开始符号，SVN P：产生式集合(有限)，每个产生式形式为 P， PVN，   (VT  VN)* 开始符S至少必须在某个产生式的左部出现一次。 国防科技大学计算机系602教研室

复习：程序语言的语法描述 定义：称A直接推出，即 且，  (VT  VN)* 。 如果1  2   n，则我们称这个序 列是从1到n的一个推导。若存在一个从 1到n的推导，则称1可以推导出n 。 国防科技大学计算机系602教研室

通常，用 表示：从1出发，经过 一步或若干步，可以推出n。 所以 ： 即 或 定义：假定G是一个文法，S 是它的开始符号。 如果 ，则称是一个句型。仅含终结符 号的句型是一个句子。文法G所产生的句子的全 体是一个语言，将它记为 L(G)。 国防科技大学计算机系602教研室

复习：程序语言的语法描述 最左推导：任何一步  都是对中的最 左非终结符进行替换。 最右推导：任何一步  都是对中的最 右非终结符进行替换。 国防科技大学计算机系602教研室

复习：程序语言的语法描述 用一张图表示一个句型的推导,称为语法树。 E (E) (E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i) E (E) (E+E) (E+i) (E*E+i) (E*i+i) (i*i+i) 国防科技大学计算机系602教研室

复习：程序语言的语法描述 定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。 语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。 国防科技大学计算机系602教研室

复习：程序语言的语法描述 形式语言鸟瞰 0型(短语文法，图灵机)： 1型(上下文有关文法，线性界限自动机)： 产生式形如：    产生式形如：    其中： (VT  VN)*且至少含有一个非终结符； (VT  VN)* 1型(上下文有关文法，线性界限自动机)： 其中：||  ||，仅 S 例外。 国防科技大学计算机系602教研室

复习：程序语言的语法描述 形式语言鸟瞰 2型(上下文无关文法，非确定下推自动机)： 产生式形如： A   其中：A VN； (VT  VN)*。 3型(正规文法，有限自动机)： 产生式形如： A  B 或 A   其中：  VT*；A，BVN 产生式形如： A  B 或 A   国防科技大学计算机系602教研室

第三章 词法分析 词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。 第三章 词法分析 词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。 词法分析器(Lexical Analyzer) 又称扫描器(Scanner)：执行词法分析的程序 国防科技大学计算机系602教研室

3.1 对于词法分析器的要求 一、词法分析器的功能和输出形式 功能:输入源程序、输出单词符号 单词符号的种类： 3.1 对于词法分析器的要求 一、词法分析器的功能和输出形式 功能:输入源程序、输出单词符号 单词符号的种类： 基本字：如 begin，repeat， 标识符——表示各种名字：如变量名、数组名和过程名 常数：各种类型的常数 运算符：+，-，*，/， 界符：逗号、分号、括号和空白 国防科技大学计算机系602教研室

输出的单词符号的表示形式: 单词种别通常用整数编码表示。 (单词种别，单词自身的值) 单词种别通常用整数编码表示。 若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算符和界符都是一符一种。 若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值。 标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。 常数按类型分种；常数的值则表示成标准的二进制形式。 国防科技大学计算机系602教研室

例 C程序 while (i>=j) i--; < while, - > < (, - > 输出单词符号： < while, - > < (, - > < id, 指向i的符号表项的指针 > < >=, - > < id, 指向j的符号表项的指针 > < ), - > < --, - > < ;, - > 国防科技大学计算机系602教研室

例 FORTRAN程序 IF (5.EQ.M) GOTO 100 输出单词符号： 逻辑IF (34，-) 左括号 (2，-) 左括号 (2，-) 整常数 (20， ‘5’的二进制) 等号 (6，-) 标识符 (26， ‘M’) 右括号 (16，-) GOTO (30，-) 标号 (19， ‘100’的二进制) 国防科技大学计算机系602教研室

二、词法分析器作为一个独立子程序 词法分析是作为一个独立的阶段，是否应当将其处理为一遍呢？ 作为独立阶段的优点：结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问题。 不作为一遍：将其处理为一个子程序。 国防科技大学计算机系602教研室

词法分析器 单词符号 源程序 词法分 析器 语法分 符号表 ... 取下一单词 国防科技大学计算机系602教研室

3.2 词法分析器的设计 输入 预处理子程序 列表 输入缓冲区 扫描器 扫描缓冲区 单词符号 词法分析器的结构 国防科技大学计算机系602教研室

一、输入、预处理 输入串放在输入缓冲区中。 预处理子程序：剔除无用的空白、跳格、回车和换行等编辑性字符;区分标号区、捻接续行和给出句末符等 扫描缓冲区 ↑ ↑ 起点 搜索 指示器 指示器 国防科技大学计算机系602教研室

WhatALong…Word … WhatALong…Wo rd … WhatALong…Wo rd rd … WhatALong…Wo 国防科技大学计算机系602教研室

二、单词符号的识别:超前搜索 1 基本字识别: 例如: DO99K=1，10 DO 99 K = 1，10 IF(5.EQ.M)GOTO55 IF (5.EQ.M) GOTO 55 DO99K=1.10 IF(5)=55 需要超前搜索才能确定哪些是基本字 国防科技大学计算机系602教研室

:=， **， .EQ. ， ++，--，>= 2 标识符识别: 字母开头的字母数字串，后跟界符或算符 3 常数识别: 识别出算术常数并将其转变为二进制内码表示。有些也要超前搜索。 5.EQ.M 5.E08 4 算符和界符的识别 把多个字符符合而成的算符和界符拼合成一个单一单词符号。 :=， **， .EQ. ， ++，--，>= 国防科技大学计算机系602教研室

三、状态转换图 1 概念 状态转换图是一张有限方向图。 结点代表状态，用圆圈表示。 X Y 2 1 3 状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类。 一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态。 国防科技大学计算机系602教研室

一个状态转换图可用于识别(或接受)一定的字符串。 1 2 3 数字 其他 * 识别整常数的状态转换图 字母或数字 字母 其他 * 1 2 3 识别标识符的状态转换图 国防科技大学计算机系602教研室

助忆符：直接用编码表示不便于记忆，因此用助忆符来表示编码。 2 例子 助忆符：直接用编码表示不便于记忆，因此用助忆符来表示编码。 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室

1 2 3 4 5 6 7 8 9 10 11 12 13 空白 字母 字母或数字 非字母与数字 数字 非数字 = + * 非* , ( ) 其它 国防科技大学计算机系602教研室

几点重要限制——不必使用超前搜索 所有基本字都是保留字;用户不能用它们作自己的标识符 基本字作为特殊的标识符来处理;不用特殊的状态图来识别，只要查保留字表。 如果基本字、标识符和常数(或标号)之间没有确定的运算符或界符作间隔，则必须使用一个空白符作间隔。 DO99K=1，10 要写成 DO 99 K=1，10 国防科技大学计算机系602教研室

3 状态转换图的实现 思想：每个状态结对应一小段程序。 做法: 1)对不含回路的分叉结，可用一个CASE语句或一组IF-THEN-ELSE语句实现 i j k l 字母 数字 \ GetChar( ); if (IsLetter( )) {…状态j的对应程序段…;} else if (IsDigit( )) {…状态k的对应程序段…;} else if (ch=‘/’) {…状态l的对应程序段…;} else {…错误处理…;} 国防科技大学计算机系602教研室

3 状态转换图的实现 2)对含回路的状态结，可对应一段由WHILE结构和IF语句构成的程序. i j 字母或数字 GetChar( ); 其它 j GetChar( ); while (IsLetter( ) or IsDigit( )) …状态j的对应程序段… 国防科技大学计算机系602教研室

3 状态转换图的实现 3)终态结表示识别出某种单词符号，因此，对应语句为 RETURN (C，VAL) 国防科技大学计算机系602教研室

1)ch 字符变量、存放最新读入的源程序字符 2)strToken 字符数组，存放构成单词符号的字符串 全局变量与过程 1)ch 字符变量、存放最新读入的源程序字符 2)strToken 字符数组，存放构成单词符号的字符串 3)GetChar 子程序过程，把下一个字符读入到 ch 中 4)GetBC 子程序过程，跳过空白符，直至 ch 中读入一非空白符 5)Concat 子程序，把ch中的字符连接到 strToken 国防科技大学计算机系602教研室

6)IsLetter和 IsDisgital 布尔函数，判断ch中字符是否为字母和数字 7) Reserve 整型函数，对于 strToken 中的字符串查找保留字表，若它实保留字则给出它的编码，否则回送0 8) Retract 子程序，把搜索指针回调一个字符位置 9)InsertId 整型函数，将strToken中的标识符插入符号表，返回符号表指针 10)InsertConst 整型函数过程，将strToken中的常数插入常数表，返回常数表指针。 国防科技大学计算机系602教研室

strToken := “ ”; /*置strToken为空串*/ GetChar(); GetBC(); if (IsLetter()) int code, value; strToken := “ ”; /*置strToken为空串*/ GetChar(); GetBC(); if (IsLetter()) begin while (IsLetter() or IsDigit()) Concat(); GetChar(); end Retract(); code := Reserve(); if (code = 0) value := InsertId(strToken); return ($ID, value); else return (code, -); 国防科技大学计算机系602教研室

value := InsertConst(strToken); return($INT, value); else if (IsDigit()) begin while (IsDigit()) Concat( ); GetChar( ); end Retract(); value := InsertConst(strToken); return($INT, value); else if (ch =‘=’) return ($ASSIGN, -); else if (ch =‘+’) return ($PLUS, -); 国防科技大学计算机系602教研室

if (ch =‘*’) return ($POWER, -); Retract(); return ($STAR, -); end else if (ch =‘*’) begin GetChar(); if (ch =‘*’) return ($POWER, -); Retract(); return ($STAR, -); end else if (ch =‘;’) return ($SEMICOLON, -); else if (ch =‘(’) return ($LPAR, -); else if (ch =‘)’) return ($RPAR, -); else ProcError( ); /* 错误处理*/ 国防科技大学计算机系602教研室

3.3 正规表达式与有限自动机 几个概念: 考虑一个有穷 字母表∑ 字符集 其中每一个元素称为一个字符 3.3 正规表达式与有限自动机 几个概念: 考虑一个有穷 字母表∑ 字符集 其中每一个元素称为一个字符 ∑上的字(也叫字符串) 是指由∑中的字符所构成的一个有穷序列 不包含任何字符的序列称为空字，记为ε 用∑*表示∑上的所有字的全体,包含空字ε 例如: 设 ∑={a， b}，则 ∑*={ε,a,b,aa,ab,ba,bb,aaa,...} 国防科技大学计算机系602教研室

UV＝{  | U & V } Vn=VV…V V*=V0∪V1∪V2∪V3∪… 称V*是V的闭包; 记 V＋＝VV* ，称V+是V的正规闭包。 国防科技大学计算机系602教研室

3.3.1 正规式和正规集 正规集可以用正规表达式（简称正规式）表示。 正规表达式是表示正规集一种方法。一个字集合是正规集当且仅当它能用正规式表示。 国防科技大学计算机系602教研室

冯-诺伊曼构造自然数的方案  0 {} 1 {, {}} 2 {, {}, {, {}}} 3  0 {} 1 {, {}} 2 {, {}, {, {}}} 3 国防科技大学计算机系602教研室

正规式和正规集的递归定义： 对给定的字母表 1) 和都是上的正规式，它们所表示的正规 集为{}和; 2) 任何a ，a是上的正规式，它所表示的 正规集为{a} ; 国防科技大学计算机系602教研室

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))*， 仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式表示的字集才是上的正规集。 国防科技大学计算机系602教研室

b(ab)*=(ba)*b (a*b*)*=(a|b)* 所有词法结构一般都可以用正规式描述。 若两个正规式所表示的正规集相同，则称这两个正规式等价。如 b(ab)*=(ba)*b (a*b*)*=(a|b)* L(b(ab)*) = L(b)L((ab)*) = L(b) (L(ab))* = L(b) (L(a)L(b))* ={b} {ab}* = {b} {, ab, abab, ababab, …} = {b, bab, babab, bababab, …} L( (ba)*b) = L((ba)*) L(b) = (L(ba))*L(b) = (L(b)L(a))* L(b) = {ba}* {b} = {, ba, baba, bababa, …} {b} = {b, bab, babab, bababab, …} ∵ L(b(ab)*)= L( (ba)*b) ∴b(ab)*=(ba)*b 国防科技大学计算机系602教研室

对正规式，下列等价成立： e1|e2 = e2|e1 交换律 e1 |(e2|e3) = (e1|e2)|e3 结合律 L(e1|e2) = L(e1 )  L(e2) = L(e2 )  L(e1) = L(e2|e1) 国防科技大学计算机系602教研室

正规集 3.3.1 正规式 国防科技大学计算机系602教研室

3.3.2 确定有限自动机(DFA) 对状态图进行形式化，则可以下定义： 自动机M是一个五元式M=(S, , f, S0, F),其中： 2. ：输入字母表(有穷)， 3. f: 状态转换函数，为SS的单值部分映射，f(s，a)=s’表示：当现行状态为s，输入字符为a时，将状态转换到下一状态s’。我们把s’称为s的一个后继状态。 4. S0S是唯一的一个初态； 5 FS ：终态集(可空)。 国防科技大学计算机系602教研室

例如：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 3 1 2 a 状态转换图 b 状态转换矩阵 国防科技大学计算机系602教研室

DFA可以表示为状态转换图。假定DFA M含有m个状态和n个输入字符，那么，这个图含有m个状态结点，每个结点顶多含有n条箭弧射出，且每条箭弧用Σ上的不同的输入字符来作标记。 国防科技大学计算机系602教研室

对于*中的任何字，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于，则称为DFA M所识别(接收) DFA M所识别的字的全体记为L(M)。 可以证明：上的字集V*是正规集，当且仅当存在上的DFA M，使得V＝L(M)。 国防科技大学计算机系602教研室

3.3.3 非确定有限自动机(NFA) 定义：一个非确定有限自动机(NFA) M是一个五元式M=(S, , f, S0, F)，其中： 2  ：输入字母表(有穷)； 3 f: 状态转换函数，为S*2S的部分映射(非单值)； 4 S0S是非空的初态集； 5 F S ：终态集(可空)。 国防科技大学计算机系602教研室

1 弧上的标记可以是*中的一个字，而不一定是单个字符； 2 同一个字可能出现在同状态射出的多条弧上。 DFA是NFA的特例。 从状态图中看NFA 和DFA的区别： 1 弧上的标记可以是*中的一个字，而不一定是单个字符； 2 同一个字可能出现在同状态射出的多条弧上。 DFA是NFA的特例。 国防科技大学计算机系602教研室

识别所有含相继两个a 或相继两个b的字 {ambn | m，n1} a，b aa bb a b 2 1 1 2 2 1 a，b aa bb 识别所有含相继两个a 或相继两个b的字 {ambn | m，n1} 1 2 a b 国防科技大学计算机系602教研室

定义：对于任何两个有限自动机M和M’，如果L(M)=L(M’)，则称M与M’等价。 自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的。 对于每个NFA M存在一个DFA M’，使得 L(M)=L(M’)。亦即DFA与NFA描述能力相同。 国防科技大学计算机系602教研室

1. 假定NFA M=<S, , , S0, F>，我们对M的状态转换图进行以下改造： 证明: 1. 假定NFA M=<S, , , S0, F>，我们对M的状态转换图进行以下改造： 1) 引进新的初态结点X和终态结点Y，X,YS， 从X到S0中任意状态结点连一条箭弧， 从F中任意状态结点连一条箭弧到Y。 2) 对M的状态转换图进一步施行替换，其中k是新引入的状态。 国防科技大学计算机系602教研室

按下面的三条规则对V进行分裂: i AB i k A B j 代之为 i j B A i j A|B 代之为 i j A* i k  j 国防科技大学计算机系602教研室

逐步把这个图转变为每条弧只标记为上的一个字符或，最后得到一个NFA M’，显然L(M’)=L(M) 国防科技大学计算机系602教研室

识别所有含相继两个a或相继两个b的字 5 1 2 6 a b  aa bb X Y  5 1 4 2 3 6 a b 国防科技大学计算机系602教研室

2. 把上述NFA确定化——采用子集法. 设I是的状态集的一个子集，定义I的-闭包-closure(I)为: i) 若sI，则s-closure(I)； ii) 若sI，则从s出发经过任意条弧而能到达的任何状态s’都属于-closure(I) 即 -closure(I)=I{s’|从某个sI出发经过任意条弧能到达s’} 国防科技大学计算机系602教研室

其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。 Ia= -closure(J) 其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。 国防科技大学计算机系602教研室

其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。 6 Ia= -closure(J) 其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。 6 1 a  2 3 4 5 7 8 -closure({1})={1，2}=I J={5，4，3} Ia= -closure(J)= -closure({5，4，3}) ={5，4，3，6，2，7，8} 国防科技大学计算机系602教研室

不失一般性，设字母表只包含两个a和b，我们构造一张表: 把确定化的过程: 不失一般性，设字母表只包含两个a和b，我们构造一张表: 国防科技大学计算机系602教研室

首先，置第1行第1列为-closure({X})求出这一列的Ia，Ib； 重复上述过程，知道所有第2，3列子集全部出现在第一列为止。 国防科技大学计算机系602教研室

I Ia Ib {X,5,1} {5,3,1} {5,4,1} {5,3,1} {5,2,3,1,6,Y} {5,4,1} {5,4,1}  5 1 4 2 3 6 a b I Ia Ib {X,5,1} {5,3,1} {5,4,1} {5,3,1} {5,2,3,1,6,Y} {5,4,1} {5,4,1} {5,3,1} {5,2,4,1,6,Y} {5,2,3,1,6,Y} {5,2,3,1,6,Y} {5,4,6,1,Y} {5,4,6,1,Y} {5,3,6,1,Y} {5,2,4,1,6,Y} {5,2,4,1,6,Y} {5,3,6,1,Y} {5,2,4,1,6,Y} {5,3,6,1,Y} {5,2,3,1,6,Y} {5,4,6,1,Y} 国防科技大学计算机系602教研室

现在把这张表看成一个状态转换矩阵，把其中的每个子集看成一个状态。 这张表唯一刻划了一个确定的有限自动机M，它的初态是-closure({X}) ，它的终态是含有原终态Y的子集。 不难看出，这个DFA M与M’等价。 国防科技大学计算机系602教研室

I a b 1 2 3 4 6 5 1 2 3 5 4 6 a b 国防科技大学计算机系602教研室

FA 正规集 DFA 3.3.2 3.3.3 3.3.1 3.3.4 正规式 NFA 正规文法 国防科技大学计算机系602教研室

3.3.4 正规文法与有限自动机的等价性 对于正规文法G和有限自动机M，如果L(G)＝L(M)，则称G和M是等价的。关于正规文法和有限自动机的等价性，有以下结论： 国防科技大学计算机系602教研室

3.3.4 正规文法与有限自动机的等价性 定理： 1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机(FA) M，使得L(M)＝L(G)。 2.对每一个FA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)＝L(GR)＝L(GL)。 国防科技大学计算机系602教研室

1. 对每一个右线性正规文法G或左线性正规文法G，都构造一个有限自动机（FA） M，使得L(M)＝L(G)。 证明： 1. 对每一个右线性正规文法G或左线性正规文法G，都构造一个有限自动机（FA） M，使得L(M)＝L(G)。 (1) 设右线性正规文法G=<VT, VN, S, P >。将VN中的每一非终结符号视为状态符号，并增加一个新的终结状态符号f，fVN。 令M=<VN∪{f}, VT, , S, {f}>，其中状态转换函数由以下规则定义： 国防科技大学计算机系602教研室

(a) 若对某个AVN及aVT∪{}，P中有产生式A→a，则令(A,a)=f (b) 对任意的AVN及aVT∪{}，设P中左端为A，右端第一符号为a的所有产生式为： A→aA1|…|aAk （不包括A→a）， 则令(A,a)={A1,…,Ak}。 显然，上述M是一个NFA。 国防科技大学计算机系602教研室

对于右线性正规文法G，在S w的最左推导过程中: 利用AaB一次就相当于在M中从状态A经过标记为a的箭弧到达状态B（包括a=的情形）; 在推导的最后，利用Aa一次则相当于在M中从状态A经过标记为a的箭弧到达终结状态f（包括a=的情形）。 综上，在正规文法G中，S w的充要条件是：在M中，从状态S到状态f有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于w，这就是说，wL(G)当且仅当wL(M)，故L(G)＝L(M)。 国防科技大学计算机系602教研室

令M=<VN∪{q0}, VT, , q0, {S}>，其中状态转换函数由以下规则定义： (2) 设左线性正规文法G=<VT, VN, S, P>。将VN中的每一符号视为状态符号，并增加一个初始状态符号q0，q0VN。 令M=<VN∪{q0}, VT, , q0, {S}>，其中状态转换函数由以下规则定义： (a) 若对某个AVN及aVT∪{}，若P中有产生式Aa，则令(q0,a)=A (b) 对任意的AVN及aVT∪{}，若P中所有右端第一符号为A，第二个符号为a的产生式为： A1→Aa, …, Ak→Aa， 则令(A,a)={A1,…,Ak}。 与(1)类似，可以证明L(G)＝L(M)。 国防科技大学计算机系602教研室

例: GR(A) ： A→0 | 0B | 1D B→0D | 1C C→0 | 0B | 1D D→0D | 1D 从GR出发构造NFA M = <{A, B, C, D, f}, {0, 1}, , A, {f}>，M的状态转换图如右图所示。 显然 L(M) = L(GR)。 B 1 f C A 1 1 D 0,1 国防科技大学计算机系602教研室

3.3.4 正规文法与有限自动机的等价性 定理： 1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机(FA) M，使得L(M)＝L(G)。 2.对每一个FA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)＝L(GR)＝L(GL)。 国防科技大学计算机系602教研室

证明2：对每一个DFA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)＝L(GR)＝L(GL)。 设DFA M=<S, , , s0, F> (1) 若s0F，我们令GR=<, S, s0, P>，其中P是由以下规则定义的产生式集合： 对任何a及A,BS，若有(A,a)=B，则： (a) 当BF时，令A→aB， (b) 当BF时，令A→a|aB。 国防科技大学计算机系602教研室

对任何w*，不妨设w=a1…ak，其中ai (i=1,…k)。若s0 w，则存在一个最左推导： s0a1A1a1a2A2…a1…aiAi a1…ai+1Ai+1…a1…ak 因而，在M中有一条从s0出发依次经过A1，…，Ak-1到达终态的通路，该通路上所有箭弧的标记依次为a1,…,ak。反之亦然。所以，wL(GR)当且仅当wL(M)。 国防科技大学计算机系602教研室

若有(A,a)=B： 现在考虑s0F的情形： 因为(s0, )=s0，所以L(M)。但不属于上面构造的GR所产生的语言L(GR)。不难发现，L(GR)=L(M)-{}。 所以，我们在上述GR中添加新的非终结符号s0，(s0S)和产生式s0s0|，并用s0代替s0作开始符号。这样修正GR后得到的文法GR仍是右线性正规文法，并且L(GR)=L(M)。 (2) 类似于(1)，从DFA M出发可构造左线性正规文法GL，使得L(GL)=L(M)。 最后，由DFA和NFA之间的等价性，结论2得证。 若有(A,a)=B： (a) 当A= q0时，令B→a， (b) 当A ≠q0时，令B→Aa 国防科技大学计算机系602教研室

例3.4 设DFA M = <{A, B, C, D}, {0, 1}, , A, {B}>。M的状态转换图如下图所示。 L(M) = 0(10)* GR = <{0, 1}, {A, B, C, D}, A, P>，其中P由下列产生式组成： A→0 | 0B | 1D B→0D | 1C C→0 | 0B | 1D D→0D | 1D L(GR) = L(M) = 0(10)* A B C D 1 0,1 国防科技大学计算机系602教研室

例3. 4 设DFA M = <{A, B, C, D}, {0, 1}, , A, {B}>。M的状态转换图如图3 例3.4 设DFA M = <{A, B, C, D}, {0, 1}, , A, {B}>。M的状态转换图如图3.9(a)所示。 从NFA M出发构造左线性正规文法GL = <{0, 1}, {B, C, D, f}, f, P>，其中P由下列产生式组成： f→0 | C0 C→B1 B→0 | C0 D→1 | C1 | D0 | D1 | B0 易证 L(GL) = L(M)。 A B C D 1 0,1 f 国防科技大学计算机系602教研室

FA 正规集 DFA 3.3.2 3.3.3 3.3.1 3.3.5 3.3.4 正规式 NFA 正规文法 国防科技大学计算机系602教研室

3.3.5 正规式与有限自动机的等价性 定理： 1. 对任何FA M，都存在一个正规式r，使得L(r)=L(M)。 2. 对任何正规式r，都存在一个FA M，使得L(M)=L(r)。 对转换图概念拓广，令每条弧可用一个 正规式作标记。(对一类输入符号) 国防科技大学计算机系602教研室

1 对上任一NFA M，构造一个上的正规式r，使得L(r)=L(M)。 证明： 1 对上任一NFA M，构造一个上的正规式r，使得L(r)=L(M)。 首先，在M的转换图上加进两个状态X和Y，从X用弧连接到M的所有初态结点，从M的所有终态结点用弧连接到Y，从而形成一个新的NFA，记为M’，它只有一个初态X和一个终态Y，显然L(M)=L(M’)。 然后，反复使用下面的一条规则，逐步消去的所有结点，直到只剩下X和Y为止； 国防科技大学计算机系602教研室

i k r1r2 i j r1 r2 k 代之为 i j r2 r1 i j r1|r2 代之为 i k r1r2*r2 i j r1 r3 国防科技大学计算机系602教研室

1 2 3 5 4 U1 V1 U2 V2 W2 W1 V1(U1|U2)*W1 1 4 V1(U1|U2)*W2 V2(U1|U2)*W1 国防科技大学计算机系602教研室

最后，X到Y的弧上标记的正规式即为所构造的正规式r 显然L(r)=L(M)=L(M’) 国防科技大学计算机系602教研室

证明2: 对于上的正规式r，构造一个NFA M，使L(M)=L(r)，并且M只有一个终态，而且没有从该终态出发的箭弧。 (1) 若r具有零个运算符，则r=或r=或r=a，其中a。此时下图所示的三个有限自动机显然符合上述要求。 a q0 qf q0 q0 qf 国防科技大学计算机系602教研室

(2) 假设结论对于少于k(k1)个运算符的正规式成立。 当r中含有k个运算符时，r有三种情形： 情形1：r=r1|r2，r1,r2中运算符个数少于k。从而，由归纳假设，对ri存在Mi=<Si, i, i, qi, {fi}>，使得L(Mi)=L(ri)，并且Mi没有从终态出发的箭弧（i=1,2）。不妨设S1∩S2=，在S1 ∪S2中加入两个新状态q0，f0。 国防科技大学计算机系602教研室

令M=<S1∪S2∪{q0,f0}, 1∪2, , q0, {f0}>，其中定义如下： (a) (q0, )={q1,q2} (b) (q,a)= 1(q,a), 当qS1-{f1}, a1∪{} (c) (q,a)= 2(q,a), 当qS2-{f2}, a2∪{} (d) (f1,)=(f2,)={f0}。 M的状态转换如右图所示。 L(M)=L(M1)∪L(M2) =L(r1)∪L(r2)=L(r) M1 q1 f1   q0 f0   M2 q2 f2 国防科技大学计算机系602教研室

令M=<S1∪S2, 1∪2, , q1, {f2}>，其中定义如下： 情形2：r=r1r2, 设Mi同情形1(i=1,2)。 令M=<S1∪S2, 1∪2, , q1, {f2}>，其中定义如下： (a) (q,a)= 1(q,a), 当qS1-{f1}, a1∪{} (b) (q,a)= 2(q,a), 当qS2, a2∪{} (c) (f1,)={q2} M的状态转换如右图所示。 L(M)=L(M1)L(M2) =L(r1)L(r2)=L(r)。 M1 q1 f1  M2 q2 f2 国防科技大学计算机系602教研室

令M=<S1∪{q0, f0}, 1, , q0, {f0}>，其中q0, f0S1，定义如下： 情形3：r=r1*。设M1同情形1。 令M=<S1∪{q0, f0}, 1, , q0, {f0}>，其中q0, f0S1，定义如下： (a) (q0,)=(f1,)={q1, f0} (b) (q,a)= 1(q, a), 当qS1-{f1}, a1∪{}。 M的状态转换如右图所示。 L(M) = L(M1)* = L(r1)* = L(r) 至此，结论2获证。  M1 q1 f1    q0 f0 国防科技大学计算机系602教研室

上述证明过程实质上是一个将正规表达式转换为有限自动机的算法。 1) 构造上的NFA M’ 使得 L(V)=L(M’) 首先，把V表示成 X Y V 国防科技大学计算机系602教研室

然后，按下面的三条规则对V进行分裂 i k V1V2 i j V1 V2 k 代之为 i j V2 V1 i j V1|V2 代之为 i k  k V1 代之为 国防科技大学计算机系602教研室

逐步把这个图转变为每条弧只标记为上的一个字符或，最后得到一个NFA M’，显然L(M’)=L(V) 国防科技大学计算机系602教研室

(a|b)*(aa|bb)(a|b)* X Y (a|b)*(aa|bb)(a|b)* X Y  5 1 4 2 3 6 a b 国防科技大学计算机系602教研室

X Y  5 1 4 2 3 6 a b I Ia Ib {X,5,1} {5,3,1} {5,4,1} {5,2,3,1,6,Y} {5,2,4,1,6,Y} {5,4,6,1,Y} {5,3,6,1,Y} 国防科技大学计算机系602教研室

I a b 1 2 3 4 6 5 1 2 3 5 4 6 a b 国防科技大学计算机系602教研室

3.3.6 正规集 DFA 3.3.2 3.3.3 3.3.1 3.3.5 3.3.4 正规式 NFA 正规文法 DFA FA 国防科技大学计算机系602教研室

3.3.6 确定有限自动机的化简 对DFA M的化简:寻找一个状态数比M少的DFA M’，使得L(M)=L(M’) 假设s和t为M的两个状态，称s和t等价:如果从状态s出发能读出某个字而停止于终态，那么同样，从t出发也能读出而停止于终态；反之亦然。 两个状态不等价，则称它们是可区别的。 国防科技大学计算机系602教研室

对一个DFA M最少化的基本思想: 把M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。 国防科技大学计算机系602教研室

具体做法: 对M的状态集进行划分 首先，把S划分为终态和非终态两个子集，形成基本划分。 假定到某个时候，已含m个子集，记为={I(1)，I(2)，，I(m)}，检查中的每个子集看是否能进一步划分: 对某个I(i)，令I(i)={s1,s2, ,sk}，若存在一个输入字符a使得Ia(i) 不会包含在现行的某个子集I(j)中，则至少应把I(i)分为两个部分。 国防科技大学计算机系602教研室

例如，假定状态s1和s2经a弧分别到达t1和t2，而t1和t2属于现行中的两个不同子集，说明有一个字， t1读出后到达终态，而t2读出后不能到达终态，或者反之，那么对于字a ， s1读出a后到达终态，而s2读出a不能到达终态，或者反之，所以s1和s2不等价。 a  s1 t1 i a  s2 t2 j 国防科技大学计算机系602教研室

I(i1)={s|sI(i)且s经a弧到达t, 且t与t1属于现行中的同一子集} 另一半含有s2 : I(i2)=I(i)-I(i1)  i j 则将I(i)分成两半，使得一半含有s1 : I(i1)={s|sI(i)且s经a弧到达t, 且t与t1属于现行中的同一子集} 另一半含有s2 : I(i2)=I(i)-I(i1) 国防科技大学计算机系602教研室

重复上述过程，直到所含子集数不再增长。 一般地，对某个a和I(i)，若Ia(i) 落入现行中 N个不同子集，则应把I(i)划分成N个不相交的组，使得每个组J的Ja都落入的同一子集。这样构成新的划分。 重复上述过程，直到所含子集数不再增长。 对于上述最后划分中的每个子集，我们选取每个子集I中的一个状态代表其他状态，则可得到化简后的DFA M’。 若I含有原来的初态，则其代表为新的初态，若I含有原来的终态，则其代表为新的终态。 国防科技大学计算机系602教研室

1 2 3 5 4 6 a b I(1)={0, 1, 2} I(2)={3, 4, 5, 6} Ia(1) ={1, 3} I(11) ={0, 2} I(12) ={1} I(2)={3, 4, 5, 6} I(11) ={0, 2} Ia(11) ={1} Ib(11) ={2, 5} I(111) ={0} I(112) ={2} I(12) ={1} I(2)={3, 4, 5, 6} Ia(2) ={3, 6} Ia(2) ={4, 5} 国防科技大学计算机系602教研室

1 2 3 5 4 6 a b 1 2 3 a b 国防科技大学计算机系602教研室

3.3.6 正规集 DFA 3.3.2 3.3.3 3.3.1 3.3.5 3.3.4 正规式 NFA 正规文法 DFA FA 国防科技大学计算机系602教研室

3.4 词法分析器的自动产生--LEX LEX源程序 词法分析程序自动产生器 词法分析程序L 词法分析程序L 输入串 单词符号 控制执行程序 状态转换矩阵 国防科技大学计算机系602教研室

正规式 AUXILIARY DEFINITION letterA|B|...|Z digit 0|1|...|9 RECOGNITION RULES 1 DIM { RETURN (1,-) } 2 IF { RETURN (2,-) } 3 DO { RETURN (3,-) } 4 STOP { RETURN (4,-) } 5 END { RETURN (5,-) } 6 letter(letter|digit) * { RETURN (6, TOKEN) } 7 digit(digit)* { RETURN (7, DTB) } 8 = { RETURN (8, -) } 9 + { RETURN (9,-) } 10 * { RETURN (10,-) } 11 ** { RETURN (11,-) } 12 , { RETURN (12,-) } 13 ( { RETURN (13,-) } 14 ) { RETURN (14,-) } 正规式 国防科技大学计算机系602教研室

LEX的工作过程： 首先，对每条识别规则Pi构造一个相应的非确定有限自动机Mi； 然后，引进一个新初态X，通过弧，将这些自动机连接成一个新的NFA； 最后，把M确定化、最小化，生成该DFA的状态转换表和控制执行程序 国防科技大学计算机系602教研室

M1 P1   M2 X P2     Mm Pm 国防科技大学计算机系602教研室

作业 P64-7，8，12，14 国防科技大学计算机系602教研室

例: 对下图NFA M构造其DFA. a b X Y 解: 不可识别ba ! 用子集法构造转换矩阵 国防科技大学计算机系602教研室

ba ！！！ b a,b a 2 1 DFA M’ {1, 2} {0} a,b a b 1 化简后的DFA M’ 2 1 DFA M’ {1, 2} {0} ba ！！！ a,b a b 1 化简后的DFA M’ 国防科技大学计算机系602教研室