03 第三章 词法分析.pptx

第1页：复习：程序语言的语法描述

复习：程序语言的语法描述

• 几个概念:
• 考虑一个有穷字母表∑字符集
• 其中每一个元素称为一个字符
• ∑上的字(也叫字符串)是指由∑中的字符所构成的一个有穷序列
• 不包含任何字符的序列称为空字，记为ε
• 用∑*表示∑上的所有字的全体,包含空字ε

第2页：复习：程序语言的语法描述（续）

复习：程序语言的语法描述（续）

• ∑*的子集U和V的连接（积）定义为UV＝{
• |
• U &
• V }
• V自身的n次积记为Vn=VV…V
• 规定V0={
• }，令V*=V0∪V1∪V2∪V3∪…称V*是V的闭包;
• 记V＋＝VV*，称V+是V的正规闭包。

第3页：复习：程序语言的语法描述

复习：程序语言的语法描述

上下文无关文法的定义

一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中

VT

终结符集合(非空)

VN

非终结符集合(非空)，且VT

S

文法的开始符号，S

P

产生式集合(有限)，每个产生式形式为P

• VN=
• VN
• ，P
• VN，
• (VT
• VN)*
• 开始符S至少必须在某个产生式的左部出现一次。

第4页：复习：程序语言的语法描述（续）

复习：程序语言的语法描述（续）

• 定义：称
• A
• 直接推出
• ，即
• A
• 仅当A
• 是一个产生式，且
• ，
• (VT
• VN)*。
• 如果
• 1
• 2
• n，则我们称这个序列是从
• 1到
• n的一个推导。若存在一个从
• 1到
• n的推导，则称
• 1可以推导出
• n。

第5页：假定G是一个文法

假定G是一个文法

• 假定G是一个文法，S是它的开始符号。如果，则
• 1出发，经过一步或若干步，可以推出
• n。用表示：从
• 1出发，经过0步或若干步，可以推出
• n。所以：即或
• 称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。

第6页：复习：程序语言的语法描述

复习：程序语言的语法描述

最左推导

任何一步

• 都是对
• 中的最左非终结符进行替换。最右推导：任何一步
• 都是对
• 中的最右非终结符进行替换。

第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)

第8页：复习：程序语言的语法描述

复习：程序语言的语法描述

定义

如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。

语言的二义性

一个语言是二义性的，如果对它不存在无二义性的文法。

第9页：复习：程序语言的语法描述（续）

复习：程序语言的语法描述（续）

• 形式语言鸟瞰
• 0型(短语文法，图灵机)：产生式形如：
• 其中：
• (VT
• VN)*且至少含有一个非终结符；
• (VT
• VN)*
• 1型(上下文有关文法，线性界限自动机)：产生式形如：
• 其中：|
• |
• |
• |，仅S
• 例外。

第10页：复习：程序语言的语法描述

复习：程序语言的语法描述

• 形式语言鸟瞰
• 2型(上下文无关文法，非确定下推自动机)：产生式形如：A
• 其中：A
• VN；
• (VT
• VN)*。
• 3型(正规文法，有限自动机)：产生式形如：A
• B或A
• 其中：
• VT*；A，B
• VN产生式形如：A
• B
• 或A
• 其中：
• VT*；A，B
• VN

第11页：第三章词法分析

第三章词法分析

词法分析的任务

从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。

第12页：3.1对于词法分析器的要求

3.1对于词法分析器的要求

功能

输入源程序、输出单词符号

基本字

如begin，repeat，

标识符——表示各种名字

如变量名、数组名和过程名

常数

各种类型的常数

运算符

+，-，*，/，

界符

逗号、分号、括号和空白

• 对于词法分析器的要求一、词法分析器的功能和输出形式
• 单词符号的种类：

第13页：单词种别通常用整数编码表示

单词种别通常用整数编码表示

• 若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算符和界符都是一符一种。
• 若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值。
• 标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。
• 常数按类型分种；常数的值则表示成标准的二进制形式。

第14页：例C程序

例C程序

输出单词符号

< while,->< (,->< id,指向i的符号表项的指针>< >=,->< id,指向j的符号表项的指针>< ),->< id,指向i的符号表项的指针><--,->< ;,->

第15页：例FORTRAN程序

例FORTRAN程序

输出单词符号

逻辑IF(34，-)左括号(2，-)整常数(20，‘5’的二进制)等号(6，-)标识符(26，‘M’)右括号(16，-)GOTO(30，-)标号(19，‘100’的二进制)

第16页：例FORTRAN程序（续）

例FORTRAN程序（续）

作为独立阶段的优点

结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问题。

不作为一遍

将其处理为一个子程序。

• 为一个独立子程序
• 词法分析是作为一个独立的阶段，是否应当将其处理为一遍呢？

第17页：例FORTRAN程序

例FORTRAN程序

• 下一单词...

第18页：例FORTRAN程序（续）

例FORTRAN程序（续）

• 区单词符号输入列表3.2词法分析器的设计

第19页：预处理子程序

预处理子程序

• 剔除无用的空白、跳格、回车和换行等编辑性字符;区分标号区、捻接续行和给出句末符等
• 扫描缓冲区↑ ↑起点搜索指示器指示器一、输入、预处理

第20页：预处理子程序（续）

预处理子程序（续）

• ordrd… WhatALong…Word… WhatALong…Wo

第21页：预处理子程序

预处理子程序

• :超前搜索1基本字识别:例如:DO99K=1，10DO99K=1，10IF(5.EQ.M)GOTO55IF(5.EQ.M)GOTO55DO99K=1.10IF(5)=55
• 需要超前搜索才能确定哪些是基本字

第22页：2标识符识别

2标识符识别

• 字母开头的字母数字串，后跟界符或算符3常数识别:
• 识别出算术常数并将其转变为二进制内码表示。有些也要超前搜索。5.EQ.M5.E084算符和界符的识别
• 把多个字符符合而成的算符和界符拼合成一个单一单词符号。:=，**，.EQ.，++，--，>=

第23页：2标识符识别（续）

2标识符识别（续）

• 状态转换图是一张有限方向图。213XY
• 结点代表状态，用圆圈表示。
• 状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类。
• 一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态。

第24页：2标识符识别

2标识符识别

• 整常数的状态转换图123数字其他数字*
• 一个状态转换图可用于识别(或接受)一定的字符串。

第25页：2标识符识别（续）

2标识符识别（续）

助忆符

直接用编码表示不便于记忆，因此用助忆符来表示编码。

第26页：

第27页：2标识符识别

2标识符识别

• 字非字母与数字数字非数字数字=+*非*,()其它****

第28页：所有基本字都是保留字

所有基本字都是保留字

• 所有基本字都是保留字;用户不能用它们作自己的标识符
• 基本字作为特殊的标识符来处理;不用特殊的状态图来识别，只要查保留字表。
• 如果基本字、标识符和常数(或标号)之间没有确定的运算符或界符作间隔，则必须使用一个空白符作间隔。DO99K=1，10要写成DO99K=1，10

第29页：3状态转换图的实现

3状态转换图的实现

思想

每个状态结对应一小段程序。

做法

1)对不含回路的分叉结，可用一个CASE语句或一组IF-THEN-ELSE语句实现GetChar( );if (IsLetter( )) {…状态j的对应程序段…;}else if (IsDigit( )) {…状态k的对应程序段…;}else if (ch=‘/’) {…状态l的对应程序段…;}else {…错误处理…;}ijkl字母数字\

第30页：3状态转换图的实现（续）

3状态转换图的实现（续）

• 可对应一段由WHILE结构和IF语句构成的程序.i字母或数字其它jGetChar( );while (IsLetter( ) or IsDigit( ))GetChar( );…状态j的对应程序段…

第31页：3状态转换图的实现

3状态转换图的实现

• 因此，对应语句为RETURN (C，VAL)其中，C为单词种别，VAL为单词自身值.

第32页：3状态转换图的实现（续）

3状态转换图的实现（续）

全局变量与过程1)ch字符变量、存放最新读入的源程序字符2)strToken字符数组，存放构成单词符号的字符串3)GetChar子程序过程，把下一个字符读入到ch中4)GetBC子程序过程，跳过空白符，直至ch中读入一非空白符5)Concat子程序，把ch中的字符连接到strToken

第33页：3状态转换图的实现

3状态转换图的实现

• 判断ch中字符是否为字母和数字7)Reserve整型函数，对于strToken中的字符串查找保留字表，若它实保留字则给出它的编码，否则回送08)Retract子程序，把搜索指针回调一个字符位置9)InsertId整型函数，将strToken中的标识符插入符号表，返回符号表指针10)InsertConst整型函数过程，将strToken中的常数插入常数表，返回常数表指针。

第34页：3状态转换图的实现（续）

3状态转换图的实现（续）

strToken

=“”;GetChar();GetBC();if(IsLetter())beginwhile(IsLetter()orIsDigit())beginConcat();GetChar();endRetract();code:=Reserve();if(code=0)beginvalue:=InsertId(strToken);return($ID,value);endelsereturn(code,-);end

第35页：3状态转换图的实现

3状态转换图的实现

• e(IsDigit())beginConcat()GetChar();endRetract();value:=InsertConst(strToken);return($INT,value);endelseif(ch=‘=’)return($ASSIGN,-);elseif(ch=‘+’)return($PLUS,-);

第36页：3状态转换图的实现（续）

3状态转换图的实现（续）

• ()if(ch=‘*’)return($POWER,-);Retract();return($STAR,-);endelseif(ch=‘;’)return($SEMICOLON,-);elseif(ch=‘(’)return($LPAR,-);elseif(ch=‘)’)return($RPAR,-);elseProcError();

第37页：3.3正规表达式与有限自动机

3.3正规表达式与有限自动机

• 有限自动机
• 几个概念:
• 考虑一个有穷字母表∑字符集
• 其中每一个元素称为一个字符
• ∑上的字(也叫字符串)是指由∑中的字符所构成的一个有穷序列
• 不包含任何字符的序列称为空字，记为ε
• 用∑*表示∑上的所有字的全体,包含空字ε例如:设∑={a，b}，则∑*={ε,a,b,aa,ab,ba,bb,aaa,...}

第38页：3.3正规表达式与有限自动机（续）

3.3正规表达式与有限自动机（续）

• |
• U &
• V }V自身的n次积记为Vn=VV…V
• }，令V*=V0∪V1∪V2∪V3∪…称V*是V的闭包;
• 记V＋＝VV*，称V+是V的正规闭包。

第39页：3.3.1正规式和正规集

3.3.1正规式和正规集

• 正规集可以用正规表达式（简称正规式）表示。
• 正规表达式是表示正规集一种方法。一个字集合是正规集当且仅当它能用正规式表示。

第40页：冯-诺伊曼构造自然数的方案

冯-诺伊曼构造自然数的方案

• 0
• {
• }1
• {
• , {
• }}2
• {
• , {
• }, {
• , {
• }}}3

第41页：上的正规式

上的正规式

• 1)
• 和
• 都是
• 上的正规式，它们所表示的正规集为{
• }和
• ;2)任何a
• ，a是
• 上的正规式，它所表示的正规集为{a};

第42页：上的正规式（续）

上的正规式（续）

• 上的正规式，它们所表示的正规集为L(e1)和L(e2)，则i)(e1|e2)为正规式，它所表示的正规集为L(e1)
• L(e2)，ii)(e1.e2)为正规式，它所表示的正规集为L(e1)L(e2)，iii)(e1)*为正规式，它所表示的正规集为(L(e1))*，仅由有限次使用上述三步骤而定义的表达式才是
• 上的正规式，仅由这些正规式表示的字集才是
• 上的正规集。

第43页：上的正规式

上的正规式

• 则称这两个正规式等价。如b(ab)*=(ba)*b(a*b*)*=(a|b)*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(b)L((ab)*)= L(b) (L(ab))*= L(b) (L(a)L(b))*={b} {ab}*= {b} {
• , ab, abab, ababab, …}= {b, bab, babab, bababab, …}∵L(b(ab)*)= L( (ba)*b)∴b(ab)*=(ba)*b

第44页：上的正规式（续）

上的正规式（续）

• e1|e2= e2|e1交换律
• e1|(e2|e3) = (e1|e2)|e3结合律
• e1(e2e3) = (e1e2)e3结合律
• e1(e2|e3) = e1e2|e1e3分配律
• (e2|e3)e1= e2e1|e3e1分配律
• e
• =
• e= ee1e2<> e2e1L(e1|e2)= L(e1)
• L(e2)= L(e2)
• L(e1)= L(e2|e1)

第45页：正规集正规式3.3.1

正规集正规式3.3.1

• 正规集正规式

第46页：3.3.2确定有限自动机

3.3.2确定有限自动机

,f,S0,F),其中

1.S:有穷状态集，2.

S

终态集(可空)。

• 有限自动机(DFA)
• 对状态图进行形式化，则可以下定义：自动机M是一个五元式M=(S,
• ：输入字母表(有穷)，3.f:状态转换函数，为S
• S的单值部分映射，f(s，a)=s’表示：当现行状态为s，输入字符为a时，将状态转换到下一状态s’。我们把s’称为s的一个后继状态。4.S0
• S是唯一的一个初态；5F

第47页：3.3.2确定有限自动机（续）

3.3.2确定有限自动机（续）

例如：DFA M=({0，1，2，3}，{a，b}，f，0，{3})，其中：f定义如下：f(0，a)=1f(0，b)=2f(1，a)=3f(1，b)=2f(2，a)=1f(2，b)=3f(3，a)=3f(3，b)=3状态转换矩阵0312aaaa状态转换图bbbb

第48页：3.3.2确定有限自动机

3.3.2确定有限自动机

DFA可以表示为状态转换图。假定DFAM含有m个状态和n个输入字符，那么，这个图含有m个状态结点，每个结点顶多含有n条箭弧射出，且每条箭弧用Σ上的不同的输入字符来作标记。

第49页：3.3.2确定有限自动机（续）

3.3.2确定有限自动机（续）

• *中的任何字
• ，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于
• ，则称
• 为DFAM所识别(接收)
• 可以证明：
• 上的字集V
• *是正规集，当且仅当存在上的DFAM，使得V＝L(M)。

第50页：3.3.3非确定有限自动机

3.3.3非确定有限自动机

定义

一个非确定有限自动机(NFA)M是一个五元式M=(S,

S

终态集(可空)。

• 有限自动机(NFA)
• ,f,S0,F)，其中：1S:有穷状态集；2
• ：输入字母表(有穷)；3f:状态转换函数，为S
• *
• 2S的部分映射(非单值)；4S0
• S是非空的初态集；5F

第51页：DFA是NFA的特例

DFA是NFA的特例

• *中的一个字，而不一定是单个字符；2同一个字可能出现在同状态射出的多条弧上。

第52页：DFA是NFA的特例（续）

DFA是NFA的特例（续）

• baaa，bbba，b012abab识别所有含相继两个a或相继两个b的字{ambn| m，n
• 1}

第53页：自动机理论中一个重要的结论

自动机理论中一个重要的结论

• 判定两个自动机等价性的算法是存在的。
• 对于每个NFA M存在一个DFA M’，使得L(M)=L(M’)。亦即DFA与NFA描述能力相同。

第54页：自动机理论中一个重要的结论（续）

自动机理论中一个重要的结论（续）

• S,
• ,
• , S0, F>，我们对M的状态转换图进行以下改造：1)引进新的初态结点X和终态结点Y，X,Y
• S，从X到S0中任意状态结点连一条
• 箭弧，从F中任意状态结点连一条
• 箭弧到Y。2)对M的状态转换图进一步施行替换，其中k是新引入的状态。证明:

第55页：自动机理论中一个重要的结论

自动机理论中一个重要的结论

• 为ijA*ik
• jA按下面的三条规则对V进行分裂:

第56页：上的一个字符或

上的一个字符或

• ，最后得到一个NFA M’，显然L(M’)=L(M)

第57页：上的一个字符或（续）

上的一个字符或（续）

• 514236ab
• ababab5126ab
• abaabb

第58页：上的一个字符或

上的一个字符或

-closure(I)为

i)若s

• 的一个子集定义I的
• -闭包
• I，则s
• -closure(I)；ii)若s
• I，则从s出发经过任意条
• 弧而能到达的任何状态s’都属于
• -closure(I)即
• -closure(I)=I
• {s’|从某个s
• I出发经过任意条
• 弧能到达s’}

第59页：中的一个字符

中的一个字符

• 中的一个字符，定义Ia=
• -closure(J)其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。

第60页：中的一个字符（续）

中的一个字符（续）

• -closure(J)=
• -closure({5，4，3})={5，4，3，6，2，7，8}61a
• 234578aa
• 中的一个字符，定义Ia=
• -closure(J)其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。

第61页：中的一个字符

中的一个字符

把确定化的过程:不失一般性，设字母表只包含两个a和b，我们构造一张表:

第62页：中的一个字符（续）

中的一个字符（续）

• 置第1行第1列为
• -closure({X})求出这一列的Ia，Ib；然后，检查这两个Ia，Ib，看它们是否已在表中的第一列中出现，把未曾出现的填入后面的空行的第1列上，求出每行第2，3列上的集合...重复上述过程，知道所有第2，3列子集全部出现在第一列为止。

第63页：中的一个字符

中的一个字符

• {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}XY
• 514236ab
• ababab

第64页：中的一个字符（续）

中的一个字符（续）

• 它的初态是
• -closure({X})，它的终态是含有原终态Y的子集。
• 不难看出，这个DFA M与M’等价。

第65页：中的一个字符

中的一个字符

• 23546aabbbabaababab

第66页：中的一个字符（续）

中的一个字符（续）

• 3.3.13.3.23.3.33.3.4

第67页：3.3.4正规文法与有限自动机的等价性

3.3.4正规文法与有限自动机的等价性

• 有限自动机的等价性
• 对于正规文法G和有限自动机M，如果L(G)＝L(M)，则称G和M是等价的。关于正规文法和有限自动机的等价性，有以下结论：

第68页：3.3.4正规文法与有限自动机的等（续）

3.3.4正规文法与有限自动机的等（续）

定理

1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机(FA)M，使得L(M)＝L(G)。2.对每一个FA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)＝L(GR)＝L(GL)。

第69页：3.3.4正规文法与有限自动机的等价性

3.3.4正规文法与有限自动机的等价性

• VN。令M=<VN∪{f}, VT,
• , S, {f}>，其中状态转换函数
• 由以下规则定义：

第70页：3.3.4正规文法与有限自动机的等（续）

3.3.4正规文法与有限自动机的等（续）

• 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。

第71页：对于右线性正规文法G

对于右线性正规文法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)。

第72页：对于右线性正规文法G（续）

对于右线性正规文法G（续）

由以下规则定义

(a)若对某个A

• VT, VN, S, P>。将VN中的每一符号视为状态符号，并增加一个初始状态符号q0，q0
• VN。令M=<VN∪{q0}, VT,
• , q0, {S}>，其中状态转换函数
• 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)。

第73页：对于右线性正规文法G

对于右线性正规文法G

• {A, B, C, D, f}, {0, 1},
• ,A, {f}>，M的状态转换图如右图所示。
• 显然L(M) = L(GR)。例:ABCD100,1110f000

第74页：3.3.4正规文法与有限自动机的等价性

3.3.4正规文法与有限自动机的等价性

定理

1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机(FA)M，使得L(M)＝L(G)。2.对每一个FA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)＝L(GR)＝L(GL)。

第75页：3.3.4正规文法与有限自动机的等（续）

3.3.4正规文法与有限自动机的等（续）

• 对每一个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。

第76页：对任何w

对任何w

• *，不妨设w=a1…ak，其中ai
• (i=1,…k)。若s0w，则存在一个最左推导：s0
• a1A1
• a1a2A2
• …
• a1…aiAi
• a1…ai+1Ai+1
• …
• a1…ak因而，在M中有一条从s0出发依次经过A1，…，Ak-1到达终态的通路，该通路上所有箭弧的标记依次为a1,…,ak。反之亦然。所以，w
• L(GR)当且仅当w
• L(M)。

第77页：对任何w（续）

对任何w（续）

(A,a)=B

(a)当A=q0时，令B→a，(b)当A≠q0时，令B→Aa

• F的情形：因为
• (s0,
• )=s0，所以
• L(M)。但
• 不属于上面构造的GR所产生的语言L(GR)。不难发现，L(GR)=L(M)-{
• }。所以，我们在上述GR中添加新的非终结符号s0
• S)和产生式s0
• s0|
• ，并用s0
• 代替s0作开始符号。这样修正GR后得到的文法GR
• 仍是右线性正规文法，并且L(GR
• )=L(M)。(2)类似于(1)，从DFA M出发可构造左线性正规文法GL，使得L(GL)=L(M)。最后，由DFA和NFA之间的等价性，结论2得证。若有

第78页：对任何w

对任何w

• ;{0, 1}, {A, B, C, D},A, P>，其中P由下列产生式组成：A→0 | 0B | 1DB→0D | 1CC→0 | 0B | 1DD→0D | 1DL(GR) = L(M) = 0(10)*例3.4设DFA M = <{A, B, C, D}, {0, 1},
• , A,{B}>。M的状态转换图如下图所示。ABCD100,11100

第79页：对任何w（续）

对任何w（续）

由下列产生式组成

f→0 | C0C→B1B→0 | C0D→1 | C1 | D0 | D1 | B0易证L(GL) = L(M)。例3.4设DFA M = <{A, B, C, D}, {0, 1},

• ，其中P
• , A,{B}>。M的状态转换图如图3.9(a)所示。ABCD100,1110f000

第80页：对任何w

对任何w

• 3.3.13.3.23.3.33.3.43.3.5

第81页：3.3.5正规式与有限自动机的等价性

3.3.5正规式与有限自动机的等价性

定理

1.对任何FA M，都存在一个正规式r，使得L(r)=L(M)。2.对任何正规式r，都存在一个FA M，使得L(M)=L(r)。

• 有限自动机的等价性
• 对转换图概念拓广，令每条弧可用一个正规式作标记。(对一类输入符号)

第82页：上任一NFA M

上任一NFA M

• 上任一NFA M，构造一个
• 上的正规式r，使得L(r)=L(M)。
• 首先，在M的转换图上加进两个状态X和Y，从X用
• 弧连接到M的所有初态结点，从M的所有终态结点用
• 弧连接到Y，从而形成一个新的NFA，记为M’，它只有一个初态X和一个终态Y，显然L(M)=L(M’)。
• 然后，反复使用下面的一条规则，逐步消去的所有结点，直到只剩下X和Y为止；

第83页：上任一NFA M（续）

上任一NFA M（续）

• ijr2r1代之为ikr1r2*r2ijr1r3kr2

第84页：上任一NFA M

上任一NFA M

• |U2)*W1V1(U1|U2)*W2V2(U1|U2)*W2V2(U1|U2)*W1

第85页：上任一NFA M（续）

上任一NFA M（续）

最后，X到Y的弧上标记的正规式即为所构造的正规式r 显然L(r)=L(M)=L(M’)

第86页：上的正规式r

上的正规式r

• 上的正规式r，构造一个NFAM，使L(M)=L(r)，并且M只有一个终态，而且没有从该终态出发的箭弧。下面使用关于r中运算符数目的归纳法证明上述结论。(1)若r具有零个运算符，则r=
• 或r=
• 或r=a，其中a
• 。此时下图所示的三个有限自动机显然符合上述要求。q0q0qfaq0qf

第87页：上的正规式r（续）

上的正规式r（续）

情形1

r=r1|r2，r1,r2中运算符个数少于k。从而，由归纳假设，对ri存在Mi=<Si,

• 1)个运算符的正规式成立。当r中含有k个运算符时，r有三种情形：
• i,
• i,qi, {fi}>，使得L(Mi)=L(ri)，并且Mi没有从终态出发的箭弧（i=1,2）。不妨设S1∩S2=
• ，在S1∪S2中加入两个新状态q0，f0。

第88页：上的正规式r

上的正规式r

• 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)
• q0f0M1q1f1M2q2f2

第89页：上的正规式r（续）

上的正规式r（续）

• 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)。
• M1q1f1M2q2f2

第90页：上的正规式r

上的正规式r

• 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获证。
• M1q1f1q0f0

第91页：上的正规式r（续）

上的正规式r（续）

• 上的NFA M’使得L(V)=L(M’)首先，把V表示成XYV上述证明过程实质上是一个将正规表达式转换为有限自动机的算法。

第92页：上的正规式r

上的正规式r

• ijV2V1代之为ikV1*ij
• kV1然后，按下面的三条规则对V进行分裂

第93页：上的一个字符或

上的一个字符或

• ，最后得到一个NFA M’，显然L(M’)=L(V)

第94页：上的一个字符或（续）

上的一个字符或（续）

• 514236ab
• ababab

第95页：上的一个字符或

上的一个字符或

• {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}XY
• 514236ab
• ababab

第96页：上的一个字符或（续）

上的一个字符或（续）

• 23546aabbbabaababab

第97页：上的一个字符或

上的一个字符或

• 3.3.13.3.23.3.33.3.43.3.5DFA3.3.6

第98页：3.3.6确定有限自动机的化简

3.3.6确定有限自动机的化简

对DFA M的化简

寻找一个状态数比M少的DFA M’，使得L(M)=L(M’)

• 有限自动机的化简
• 假设s和t为M的两个状态，称s和t等价:如果从状态s出发能读出某个字
• 而停止于终态，那么同样，从t出发也能读出
• 而停止于终态；反之亦然。
• 两个状态不等价，则称它们是可区别的。

第99页：3.3.6确定有限自动机的化简（续）

3.3.6确定有限自动机的化简（续）

对一个DFA M最少化的基本思想:把M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。

第100页：3.3.6确定有限自动机的化简

3.3.6确定有限自动机的化简

• 令I(i)={s1,s2,
• 首先，把S划分为终态和非终态两个子集，形成基本划分
• 。
• 假定到某个时候，
• 已含m个子集，记为
• ={I(1)，I(2)，
• ，I(m)}，检查
• 中的每个子集看是否能进一步划分:
• ,sk}，若存在一个输入字符a使得Ia(i)不会包含在现行
• 的某个子集I(j)中，则至少应把I(i)分为两个部分。

第101页：中的两个不同子集

中的两个不同子集

• 中的两个不同子集，说明有一个字
• ，t1读出
• 后到达终态，而t2读出
• 后不能到达终态，或者反之，那么对于字a
• ，s1读出a
• 后到达终态，而s2读出a
• 不能到达终态，或者反之，所以s1和s2不等价。s1t1as2t2a
• i
• j

第102页：中的两个不同子集（续）

中的两个不同子集（续）

中的同一子集}另一半含有s2

I(i2)=I(i)-I(i1)s1t1as2t2a

• I(i)且s经a弧到达t,且t与t1属于现行
• i
• j

第103页：重复上述过程

重复上述过程

• 中N个不同子集，则应把I(i)划分成N个不相交的组，使得每个组J的Ja都落入的
• 同一子集。这样构成新的划分。
• 所含子集数不再增长。
• 对于上述最后划分
• 中的每个子集，我们选取每个子集I中的一个状态代表其他状态，则可得到化简后的DFA M’。
• 若I含有原来的初态，则其代表为新的初态，若I含有原来的终态，则其代表为新的终态。

第104页：重复上述过程（续）

重复上述过程（续）

{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}

第105页：重复上述过程

重复上述过程

• abbbaab

第106页：重复上述过程（续）

重复上述过程（续）

• 3.3.13.3.23.3.33.3.43.3.5DFA3.3.6

第107页：3.4词法分析器的自动产生

3.4词法分析器的自动产生

• 产生器词法分析程序LLEX源程序词法分析程序L单词符号输入串状态转换矩阵控制执行程序

第108页：3.4词法分析器的自动产生（续）

3.4词法分析器的自动产生（续）

• A|B|...|Zdigit
• 0|1|...|9RECOGNITION RULES1DIM{ RETURN (1,-) }2IF{ RETURN (2,-) }3DO{ RETURN (3,-) }4STOP{ RETURN (4,-) }5END{ RETURN (5,-) }6letter(letter|digit) *{ RETURN (6, TOKEN) }7digit(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,-) }正规式

第109页：LEX的工作过程

LEX的工作过程

• 首先，对每条识别规则Pi构造一个相应的非确定有限自动机Mi；
• 然后，引进一个新初态X，通过
• 弧，将这些自动机连接成一个新的NFA；
• 最后，把M确定化、最小化，生成该DFA的状态转换表和控制执行程序

第110页：LEX的工作过程（续）

LEX的工作过程（续）

• P2
• M1MmM2P1Pm

第111页：LEX的工作过程

LEX的工作过程

• P64-7，8，12，14

第112页：LEX的工作过程（续）

LEX的工作过程（续）

• 对下图NFA M构造其DFA.aabbbXY解:用子集法构造转换矩阵不可识别ba !

第113页：LEX的工作过程

LEX的工作过程

• ,bab01化简后的DFA M’ba！！