复习：程序语言的语法描述 几个概念: 考虑一个有穷 字母表∑ 字符集 其中每一个元素称为一个字符

Presentation on theme: "复习：程序语言的语法描述 几个概念: 考虑一个有穷 字母表∑ 字符集 其中每一个元素称为一个字符"— Presentation transcript:

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

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

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

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

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

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

7 复习：程序语言的语法描述 用一张图表示一个句型的推导,称为语法树。 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教研室

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

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

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

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

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

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

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

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

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

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

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

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

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

21 二、单词符号的识别:超前搜索 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教研室

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

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

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

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

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

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

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

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

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

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

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

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

34 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教研室

35 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教研室

36 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教研室

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

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

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

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

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

42 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教研室

43 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教研室

44 对正规式，下列等价成立： 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教研室

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

46 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教研室

47 例如：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教研室

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

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

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

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

52 识别所有含相继两个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教研室

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

54 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教研室

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

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

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

58 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教研室

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

60 其中，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教研室

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

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

63 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教研室

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

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

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

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

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

69 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教研室

70 (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教研室

71 对于右线性正规文法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教研室

72 令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教研室

73 例: 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教研室

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

75 证明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教研室

76 对任何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教研室

77 若有(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教研室

78 例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教研室

79 例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教研室

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

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

82 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教研室

83 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教研室

84 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教研室

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

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

87 (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教研室

88 令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教研室

89 令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教研室

90 令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教研室

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

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

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

94 (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教研室

95 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教研室

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

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

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

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

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

101 例如，假定状态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教研室

102 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教研室

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

104 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教研室

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

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

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

108 正规式 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, -) } { RETURN (9,-) } 10 * { RETURN (10,-) } 11 ** { RETURN (11,-) } 12 , { RETURN (12,-) } 13 ( { RETURN (13,-) } 14 ) { RETURN (14,-) } 正规式 国防科技大学计算机系602教研室

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

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

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

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

113 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教研室