编译原理词法分析完课件

第4章词法分析Page

1第4章词法分析2023/10/2主要内容：单词的描述工具：正规文法和正规式单词识别系统：有穷自动机词法分析程序的设计词法分析程序的自动构造原理第4章词法分析Page

2第4章词法分析2023/10/2学习目标:掌握：词法分析程序的构造，正规式和正规文法到有穷自动机的转换，NFA到DFA的2转换、DFA的化简理解：正规文法、正规式、DFA的概念、NFA的概念了解：词法分析程序的自动构造工具第4章词法分析词法分析程序的设计单词的描述工具有穷自动机正规式和有穷自动机的等价性正则文法和有穷自动机的等价性Page

3第4章词法分析2023/10/2§

4.1

词法分析程序的设计Page

4第4章词法分析2023/10/2主要任务：从左到右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。将词法分析程序设计成子程序，每当语法分析程序需要一个单词时，调用该子程序。§

4.1

词法分析程序的设计Page

5第4章词法分析2023/10/2词法分析程序的单词符号：关键字：如begin,if,while等等；标识符：如常量名，变量名，过程名等等；常数：25，3.14159，TRUE，”ABC”等；运算符：如+，*，<=等；界符：如逗号，分号，括号等。所输出的单词符号常常采用二元式表示：（单词种别，单词自身的值）§

4.1

词法分析程序的设计例:源程序

begin

var

sum,first,count:real;sum:=first+count*10end.,

f

i

rgb

es;n

t

:

rs

t

+

ci

n

△

v

a

r

△

s

u

mt

,

c

o

um

:

=

f

i

r↵e

n

d

.源程序在文件中的表示(逗号,,)(标识符,count)(基本字,var)(基本字,begin)(标识符,sum)(赋值号,:=) (标识符,first) (加号,+)词法分析后程序的图形表示空格e

a

l

;

↵

s

uo

u

n

t

*

1

0换行字符的内部表示即ASC码单词表示成二元式（单词的种别，单词自身值）(标识符,sum) (逗号,,) (标识符,first)(冒号,:) (基本字,real) (分号,;)……Page

6第4章词法分析2023/10/2§

4.2单词的描述工具Page

7第4章词法分析2023/10/2作用:描述单词的构成规则,基于这类描述工具建立词法分析技术,进而实现词法分析程序的自动构造.工具:

正规文法正规式(Regular

Expression)§

4.2单词的描述工具Page

8第4章词法分析2023/10/21、正规文法多数程序设计语言单词的语法都能用正规文法(3型文法)描述.正规文法回顾文法的任一产生式α→β的形式都为A→aB或A→a，其中A

，B∈VN

，a∈

VT

。*正规文法描述的是VT

上的正规集§

4.2单词的描述工具Page

9第4章词法分析2023/10/2例如

:用l表示a~z中的任一英文字母，d表示0~9中任一数字描述标识符的正规文法为<标识符>→l｜l

<字母数字><字母数字>→l｜d｜l

<字母数字>｜d

<字母数字>描述无符号整数的正规文法<无符号整数>→d｜d

<无符号整数>§

4.2单词的描述工具Page

10第4章词法分析2023/10/22、正规式(正则表达式)Regular

Expression对于字母表∑，我们感兴趣的是它的一些特殊字集——正规集。正规式是描述正规集的方便工具。§

4.2单词的描述工具Page

11第4章词法分析2023/10/2正规式与正规集的递归定义①ε和φ都是∑上的正规式，它所表示的正规集分别为｛ε｝和Ф；②对于任何ａ∈∑，ａ是∑上的正规式，它所表示的正规集为｛ａ｝；§

4.2单词的描述工具③假定ｅ1和ｅ2都是∑上的正规式，他们所表示的正规集分别为Ｌ(ｅ1)和Ｌ(ｅ2)，那么，以下也都是正规式和他们所表示的正规集；正规式 正规集(ｅ1)

Ｌ(ｅ1)ｅ1｜ｅ2

Ｌ(ｅ1)∪Ｌ(ｅ2)ｅ1.ｅ2

Ｌ(ｅ1)Ｌ(ｅ2)Page

12第4章词法分析2023/10/2ｅ1

＊(Ｌ(ｅ1))＊§

4.2单词的描述工具Page

13第4章词法分析2023/10/2④仅由有限次使用上述三步定义的表达式才是∑上的正规式，仅由这些正规式所表示的>

‘｜’字集才是∑上的正规集。

算符的优先顺序:‘＊’

>

‘.’

‘.’和‘｜’都是左结合

‘＊’读为“闭包”

‘.’读为“连接”

‘｜’读为“或”§

4.2单词的描述工具Page

14第4章词法分析2023/10/2例子令Σ={a，b}，

Σ上的正规式和相应的正规集有：正规式 正规集a

{a}a⏐b

{a,b}ab

{ab}(a⏐b)(a⏐b)

{aa,ab,ba,bb}∗a

{ε

,a,aa,…任意个a串}(a⏐b)∗

{ε

,a,b,aa,ab

……所有由a和b组成的串}§

4.2单词的描述工具Page

15第4章词法分析2023/10/2正规式的代数性质：设r，s，t

是正规式，正规式的代数规律是：r｜s=s｜r

“｜”满足交换律r｜(s｜t)=(r｜s)｜t

“｜”的结合律(r

s)t=r(s

t)

“.(连接)”的结合律r(s｜t)

=

r

s｜r

t(r｜s)t=r

t｜s

t

分配律εr

=

rε=

r

ε是“.”的恒等元素r⏐r=r

“｜”的抽取律r∗=ε⏐r⏐rr⏐…§

4.2单词的描述工具Page

16第4章词法分析2023/10/2程序中的单词都能用正规式来定义令l为a~z的字母，d为0~9的数字e1=

l

(

l

|

d)

*

e1表示标识符集合e2=

dd

*

e2表示无符号整数注：<标识符>→l｜l

<字母数字><字母数字>→l｜d｜l

<字母数字>｜d

<字母数字>正规式比正规文法更容易让人理解单词是按怎样的规律构成的，且可以从某个正规式自动地构造识别程序。§

4.2单词的描述工具Page

17第4章词法分析2023/10/23、正规文法和正规式间的转换等价性：

对任意一个正规文法G，存在一个定义同一语言的正规式r

对任意一个正规式r，存在一个定义同一语言的正规文法G§

4.2单词的描述工具①

将∑上的一个正规式r转换成文法

G=(VN,VT,S,P)(正规式r

文法G)VT=

∑,首先形成产生式S→r,S为G的开始符不断利用下面的规则做变换,直到每个产生式最多含有一个终结符为止原产生式变换后产生式Page

18第4章词法分析2023/10/2规则1

A→xy规则2

A→x*yA→xB

B→yA→xA

A→y规则3

A→x|yA→x

A→y其中B为一新非终结符§

4.2单词的描述工具例:将r=a(a|d)*转换成相应的正则文法

令转换成文法G=(VN,VT,P,S)

其中VT={a,d}，文法开始符为S

首先形成S→a(a|d)*,然后变换:S→aAPage

19第4章词法分析2023/10/2S→a(a|d)*原产生式变换后产生式规则1

A→xy

A→xB

B→y规则2

A→x*y

A→xA

A→y规则3

A→x|y

A→x

A→y规则1规则2A→(a|d)A

A→ε规则3A→aA

A→dAA→(a|d)*ε最终有产生式：S→aA

，A→ε，A→aA，A→dA即，从正规式r=a(a|d)*转换成的正规文法有产生式：

S→aA

，A→ε，A→aA，A→dA§

4.2单词的描述工具将正规文法转换成正规式(正规文法G

正规式r)将每条产生式改写为正规式用代入法解正规式方程组最后只剩下一个开始符号定义的正规式,其中不含非终结符文法产生式 正规式规则1

A→xB

B→y

A=xy规则2

A→xA|y

A=x*y规则3

A→x

A→y

A=x|yPage

20第4章词法分析2023/10/2§

4.2单词的描述工具例：将文法G[S]转换成正规式G：S→a

A|aA→dA|dA→dA|d将A代入S中得:利用正规式变换得S=a(d*d|ε)=ad*说明:d*d|ε=(ε|d|dd|…)d|ε=d|dd|…|ε=

d*所求正规式为ad*文法产生式

正规式规则1

A→xB

B→y

A=xy规则2

A→xA|y

A=x*y规则3

A→x

A→y

A=x|yA=d*d

(规则2)S=ad*d|a解：

S→aA|a

S→aA

S→a

S=aA|a

(规则3)Page

21第4章词法分析2023/10/2§

4.3

有穷自动机Page

22第4章词法分析2023/10/2是一种识别装置作用:能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合意义:为词法分析程序的自动构造寻找特殊的方法和工具。分类:确定的有穷自动机(DFA)(Deterministic

Finite

Automata)不确定的有穷自动机(NFA)(Nondeterministic

FiniteAutomata)§

4.3.1

确定的有穷自动机（DFA）Page

23第4章词法分析2023/10/2一个DFA

M✁一个五元组:M=（K,Σ,f,S,Z）K是一个有穷集，它的每个元素称为一个状态；Σ是一个有穷字母表，它的每个元素称为一个输入字符；f是一个从K

X∑→K的单值部分映射(映射函数)。f(ki,a)=kj意味着当前状态为ki、输入字符为a时，将转换到下一状态kj；S∈K,是唯一的初态；Z

⊂K,是一个终态集，终态也称为可接受状态或结束状态。§

4.3.1

确定的有穷自动机（DFA）例:–

DFAM=（{S,U,V,Q},{a,b},f,S,{Q}）–其中f定义为：f（S，a）=U

f（S，b）=Vf（V，a）=U

f（V，b）=Qf（U，a）=Q

f（U，b）=Vf（Q，a）=Q

f（Q，b）=QKPage

24第4章词法分析2023/10/2Σ

Z§

4.3.1

确定的有穷自动机（DFA）Page

25第4章词法分析2023/10/2DFA表示成状态转换图(TransitionDiagram)

每个状态对应图中的一个结点:

初态为唯一初态结点，用=〉标记；

终态对应终态结点，用双圈表示。

若有f(ki,a)=kj，则从结点ki到结点kj画标记为a的弧。§

4.3.1

确定的有穷自动机（DFA）

例

DFA

M=（{S，U，V，Q},{a，b},f,S,{Q}）f（S，a）=U

f（S，b）=Vf（V，a）=U

f（V，b）=Qf（U，a）=Q

f（U，b）=Vf（Q，a）=Q

f（Q，b）=Q状态转换图表示为:终态Page

26第4章词法分析2023/10/2SUVQ初态

abababa,b§

4.3.1

确定的有穷自动机（DFA）DFA表示成状态转换矩阵例

DFA

M=（{S，U，V，Q},{a，b},f,S,{Q}）f（S，a）=U

f（S，b）=Vf（V，a）=U

f（V，b）=Q字符状态0001f（U行，表a示）状=态Q，用

f（U，b）=Vf（Q双，箭a头）“==>Q”标明初态；否则第一行即是初态相应状态行和输Page

27第4章词法分析2023/10/2入字符列下的新状态，即k行a列为f(k,a)的值相应终态行在表f（Q，b）=Q的右端标以1，列非表终示态输标入以字0符§

4.3.1

确定的有穷自动机（DFA）DFA识别(接受)的字符串对于Σ*中的任何字符串t，若存在一条从初态结到某一终态结的通路，且该通路上所有弧的标记符连接成的字符串等于t，则称t可以为DFA

M所识别若DFA

M的初态结同时又是终态结，则ε可为M所识别。baab为DFA所接受SPage

28第4章词法分析2023/10/2UVQabababa,b§

4.3.1

确定的有穷自动机（DFA）Page

29第4章词法分析2023/10/2DFA

M所能接受的符号串的全体记为L(M).结论：

∑上一个符号串集V⊂∑∗是正规的，当且仅当存在一个∑上的确定有穷自动机M，使得V=L(M)确定性表现在:转换函数f:K×Σ→K是一个单值函数，也就是说，对任何状态k∈K，和输入符号

a∈Σ，f(k,a)唯一地确定了下一个状态。§

4.3.2

不确定的有穷自动机（NFA）一个NFA

M✁一个五元组：M=(K,Σ,f,S,Z)1.

K✁一个有穷集，它的每个元素称为一个状态；一个输入字字母表，它的每个元素称为符；f✁一个从K

X∑*至K的子集的映射，即KX∑*→2K

；S

⊂K，✁一个非空初态集；Z

⊂K，✁一个终态集。对比DFA：Page

30第4章词法分析2023/10/2f是一个从K

X∑→K的单值部分映射(映射2.

∑✁一个有穷函数)。f(ki,a)=kj意味着当前状态为ki、输入字符为a时，将转换到下一状态kj；Page

31§

4.3.2

不确定的有穷自动机（NFA）矩阵表示:0

1S

{P}

{S,Z}P

{}

{Z}第4章词法分析Z{P}

{2P02}3/10/2001SPZ00,1111状态图表示:K

∑

S例NFA

M=（{S,P,Z},{0,1},f,{S,P},{Z}）其中:f（S，0）={P}

f（S，1）={S，Z}f（Z，0）={P}

f（Z，1）={P}f（P，1）={Z}初态终态§

4.3.2

不确定的有穷自动机（NFA）说明：因为NFA的转换函数f为K×∑*到K的子集的一种映射，即存在从K的一个状态到其本身的转换，这个转换是通过ε转移来实现的。所以NFA中可以有ε转移。例：12ε3εPage

32第4章词法分析2023/10/2abc§

4.3.2

不确定的有穷自动机（NFA）NFA识别（接受）的字符串对于Σ*中的任何字符串t，若存在一条从某一初态结到某一终态结的通路，且该通路上所有弧的标记字依次连接成的串（不理睬那些标记为ε的弧）等于t，则称t可以被NFA

M所识别。若M的某个初态结又是终态结，或者存在一条从某个初态结到某个终态结的ε通路，那么ε为M所识别。a1

ε

b2

ε

3Page

33第4章词法分析2023/10/2c

NFA

M

所能识别的符号串的全体记为L(M)§

4.3.2

不确定的有穷自动机（NFA）Page

34第4章词法分析2023/10/2NFA与DFA的等价性DFA是NFA的特例对于任何两个有穷自动机M和M’，如果

L(M)=L(M’)，则称M与M’是等价的对于每个NFA

M，存在一个与其等价的DFA

M’§

4.3.4

确定有穷自动机的化简Page

35第4章词法分析2023/10/2化简的任务：去掉多余状态，合并等价状态多余状态：从开始状态出发无法到达的状态。等价状态：两个状态s和t等价的条件是:1.一致性条件—状态s和t必须同为可接受状态或不可接受状态.2.蔓延性条件—对于所有输入符号,状态s和状态t必须转换到等价的状态里.可区别状态：不等价状态。如终态与非终态是可区别的。aCDBAEFSbaaaaabbbbaPage

36第4章词法分析2023/10/2a例bC和F同是终态,

C和F读入a都到达C,读入b

都到达E,所以

C和F等价S和C不等价，因为C是终态，而S不是终态“分割法”Page

37第4章词法分析2023/10/2DFA的最小化算法:把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的.例DBASaabbba,bCAEB

D

FSbaaaaaabbbbbba1.将M的状态分成非终态和终态集{S,A,B}=>{S}{A,B}=>{S}{A}{B}{C,D,E,F}3令D代表{C,D,E,F}a

bS

A

BA

C

BB

A

DC

C

ED

F

DE

F

DF

C

EP={{S},{A},{B},{D}}在等价状态子集中选一状态{S,A,B}

{C,D,E,F}

做代表，消去其他状态，把从消去状态射出和射入的弧2

寻找子集中不等价都状引态到代表状态，子集a中有初态，则代表状态也是初态Page

38第4章词法分析2023/10/2例：将下图中的DFA

M最小化（P61）1234567aaaaabbbbabab

b13456aabbbba

baaP0=({1,2,3,4},

{5,6,7})P1=({1,2},{3,4},{5,6,7})P2=({1,2},{3},{4},{5,6,7})P3=({1,2},{3},{4},{5},{6,7})1

3

4

5

6Page

39第4章词法分析2023/10/2§

4.3.3 NFA到DFA的转换从NFA构造DFA的算法—子集法字符状态00010

1Page

40第4章词法分析2023/10/2S

{P}

{S,Z}DFA的状态转换矩阵P

{}

{Z}ZNFA的{状P态}转{换P矩}阵1.

基本思想:让DFA

的每个状态对应NFA

的一个状态集合。即DFA用它的一个状态记录在NFA读入一个输入符号后可能达到的所有状态。001ε合并，则把S2状态合并到S1状态。如果有S1S2εikj

mεaban（a）i,jmkaabnPage

41第4章词法分析2023/10/2（b）2.转换需解决的问题：状态合并0123aabc（a）bPage

42第4章词法分析2023/10/20

a

1,2

c

3（b）3.

对状态集合I的有关运算：ε①状态集合I

的ε闭包ε-closure(I)是状态集I中的所有状态S以及经任意条ε弧而能到达的状态的集合。εεIIS2S2S1S1S3S3ε-

closure(I)Page

43第4章词法分析2023/10/2以下将ε-closure(I)简写为closure(I)closure(I)

=I

∪

{Sk|存在

Sj

ε

Sk, Sj

∈

closure(I),

Sk∉closure(I)

}注意：这是一个递归定义，通过多条ε边才能到达的状态也将被合并到closure中Page

44第4章词法分析2023/10/2设I={0}，则ε-closure(I

)={ε例NFA:100124536789abab

bεεεεεεε7

}0,

1,

2,

4,Page

45第4章词法分析2023/10/2②Move(I,a):I是状态集，由I中的状态出发，经过一条a弧可能到达的状态的集合称为Move(I,a)。➂Ia子集。Ia=

ε-

closure

(

Move(

I

,

a

)

)Page

46第4章词法分析2023/10/2例NFA:εPage

47第4章词法分析2023/10/210124536789abab

b0

εεεεεεε设I={0,1,2,4,7}则)=

{

3,

8,

6,

7,

1,

2,

4

}=

ε-

closure(

{

5

}

)

=

{

5,6,

7,

1,

2,

4

}Ia=ε-

closure

(Move(I,a))=

ε-

closure(

{

3, 8

}Ib=ε-

closure

(Move(I,b))4.

NFA确定化算法Page

48第4章词法分析2023/10/2假设NFA

N=(K,∑,f,K0,Kt)按如下办法构造一个DFA

M=(S,∑,d,S0,St)，使得L(M)=L(N)：①

M的状态集S由K的一些子集组成。用[S1

S2...Sj]表示S的元素，其中S1,S2,...Sj是K的状态。②

M和N的输入字母表是相同的，即是∑；➂

转换函数d([S1

S2,...Sj],a)=[R1R2...Rt]其中{R1,R2,...,Rt}=ε-closure(move({S1,

S2,,...

Sj},a))④

S0=ε-closure(K0)为M的开始状态；⑤

St={[Si

Sk...

Se]，其中[Si

Sk...

Se]∈S且{Si

,

Sk,,...

Se}∩Kt≠Φ}5.

构造DFA的状态集的算法Page

49第4章词法分析2023/10/2假设NFA

N=(K,Σ,F,K0,Kt)构造的DFA为:M=(C,Σ,D,C0,Ct)，状态集C=(T1,T2,…Ti),其中T1,T2,…Ti都是状态集K的子集。①

开始，令ε-closure(K0)为C中唯一成员，并且它是未被标记的。②

while（C中存在尚未被标记的子集T

）do{标记T；for

（每个输入字符a∈Σ）

do{U:=Ta;（即ε-closure(Move(T,a))）if

（U不在C中）

then将U做为未被标记的子集加入C中}}Page

50第4章词法分析{5,6,7,1,2,4}

T22023/10/2}{5,6,7,1,2,4}

T2{8,3,6,7,1,2,4}

T1}{9,5,6,7,1,2,4{

0{78,2,3,4,6},7,1,2,4}{5,6,7,1,2,4{5,6,7,1,2,4}

T2{9,5,6,7,1,2,4}T3{8,3,6,7,1,2,4}

T1IbIaIεε10124536789abab

b0

εεεεεε,T1,0T1

{8,3,6,7,1,2,4}

T1T2T3}{10,5,6,7,1,2,4

T4

{8,3,6,7,1,2,4}

T1000{8,3,6,7,1,2,4}

T1

{10,5,6,7,1,2,4}

T401①计算ε-closure(0)={0,1,2,4,7}——标为T0，即T0={0,1,2,4,7}②计算ε-closure(move(T0,a))=ε-closure({3,8})={1,2,3,4,6,7,8}——标为T1，即T1={1,2,3,4,6,7,8}计算ε-closure(move(T0,b))=ε-closure({5})={1,2,4,5,6,7}——标为T2，即T2={1,2,4,5,6,7}计算ε-closure(move(T1,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=T1计算ε-closure(move(T1,b))=ε-closure({5,9})={1,2,4,5,6,7,9}——标为T3，即T3={1,2,4,5,6,7,9}T0Page

51第4章词法分析2023/10/2T1T2T4{0,1,2,4,7}T3

{1,2,4,5,6,7,9}{1{,12,,23,,44,,56,,67,7,8}}④计算ε-closure(move(T2,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=T1计算ε-closure(move(T2,b))=ε-closure({5})={1,2,4,5,6,7}=

T2⑤计算ε-closure(move(T3,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=T1计算ε-closure(move(T3,b))=ε-closure({5,10})={1,2,4,5,6,7,10}——标为T4，即T4={1,2,4,5,6,7,10}⑥计算ε-closure(move(T4,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=T1计算ε-closure(move(T4,b))=ε-closure({5})={1,2,4,5,6,7}=

T2T0Page

52第4章词法分析2023/10/2{0,1,2,4,7}T1{1,2,3,4,6,7,8}T2{1,2,4,5,6,7}T3T4{{11,2,2,4,4,5,5,6,6,7,7,1,90}}没有新的集合诞生了，所以算法结束6.重新命名DFA的状态S

a

b0

1

21

1

33

1

44

1

24Page

53第4章词法分析2023/10/20b213bbaaab得到DFA的状态转换矩阵和转换图如下:aba002

1

2

001例：将下图NFA转换成等价的DFA。iPage

54第4章词法分析2023/10/2341

2

567ε

ε

εεa

ab

ba,ba,b计算ε-closure(i)={i,1,2}——标为T0，即T0={i,1,2}计算ε-closure(move(T0,a))=ε-closure({1,3})={1,2,3}——标为T1，即T1={1,2,3}计算ε-closure(move(T0,b))=ε-closure({1,4})={1,2,4}——标为T2，即T2={1,2,4}计算ε-closure(move(T1,a))=ε-closure({1,3,5})={1,2,3,5,6,7}——标为T3，即T3={1,2,3,5,6,7}计算ε-closure(move(T1,b))=ε-closure({1,4})={1,2,4}=T2计算ε-closure(move(T2,a))=ε-closure({1,3})={1,2,3}=T1计算ε-closure(move(T2,b))=ε-closure({1,4,5})={1,2,4,5,6,7}——标为T4，即T4={1,2,4,5,6,7}计算ε-closure(move(T3,a))=ε-closure({1,3,5,6})={1,2,3,5,6,7}=T3计算ε-closure(move(T3,b))=ε-closure({1,4,6})={1,2,4,6,7}——标为T5，即T5={1,2,4,6,7}计算ε-closure(move(T4,a))=ε-closure({1,3,6})={1,2,3,6,7}——标为T6，即T6={1,2,3,6,7}计算ε-closure(move(T4,b))=ε-closure({1,4,5,6})={1,2,4,5,6,7}=T4iPage

55第4章词法分析2023/10/21234567εεεεaab

ba,ba,b计算ε-closure(move(T5,a))=ε-closure({1,3,6})={1,2,3,6,7}=T6计算ε-closure(move(T5,b))=ε-closure({1,4,5,6})={1,2,4,5,6,7}=T4计算ε-closure(move(T6,a))=ε-closure({1,3,5,6})={1,2,3,5,6,7}=T3计算ε-closure(move(T6,b))=ε-closure({1,4,6})={1,2,4,6,7}=T5iPage

56第4章词法分析2023/10/21234567εεεεaab

ba,ba,b令：S=T0,A=T1,B=T2,C=T3,D=T4,E=T5,F=T6，则abS

A

BA

CBB

A

DC

CED

FDDE

FF

CESPage

57第4章词法分析2023/10/2ABCDEFaaaaaaaabbbbbbbb§

4.4正规式和有穷自动机的等价性Page

58第4章词法分析2023/10/2等价性对于∑上的一个NFA

M，可以构造一个∑上的正规式R，使得L(R)=L(M)。对于∑上的一个正规式R，可以构造一个∑上的NFA

M，使的L(M)=L(R)。从正规式构造NFA“语法制导”法：按正规式的语法结构指引构造过程正规式的基本语法结构的构造规则对于正规式ε

,构造的NFA为:YXε对于正规式x,x

∈∑构造的NFA为:YXxYX对于正规式∅,构造的NFA为:Page

59第4章词法分析2023/10/2复合正规式e的构造规则1.先构造如下的NFAyxe2.然后按下述三种情况进行分解，直至每条弧上标记一个字符e1Xye=e1|e2e2X

1e1ye2e=e1e2X

1εyεe1e=e1*Page

60第4章词法分析2023/10/2X例：为R=(a|b)*abb构造NFA

M，使得L(M)=L(R)(a|b)*abbYX1(a|b)*

a2bb3YXε4ε1b3a2ba|bYXε4ε1b3a2babYPage

61第4章词法分析2023/10/2§

4.5正规文法和有穷自动机的等价性Page

62第4章词法分析2023/10/2从正规文法G到NFA的转换方法设文法G=(VN,VT,P,S)相应NFA为M=(K,∑,f,K0,Z),则：➀

∑=VT➁

K0=S③

增加一个新的状态Z作为终态④

K=VN∪{Z}⑤

f由以下方法求得：若P中有A→aB，则有f(A,a)=B；若P中有A→a，则有f(A,a)=Z；若P中有A→ε，则有f(A,ε)=Z；例：设文法G=({S,A,B},

{a,b},

P,

S)，则有自动机M=({S,A,B,Z},

{a,b},f,S,{Z})产生式 转换函数Page

63第4章词法分析2023/10/2S→aAf(S,a)=AS→bBf(S,b)=BS→εf(S,ε)=ZA→aBf(A,a)=BA→bAf(A,b)=AB→aSf(B,a)=SB→bAf(B,b)=AB→εf(B,ε)=ZSAZBabaεεabb状态转换图为：Page

64第4章词法分析2023/10/2正规文法，正规表达式，有穷自动机三者可等价相互转换描述工具 识别工具Page

65第4章词法分析2023/10/2小结Page

66第4章词法分析2023/10/21、正规文法和正规式的转换2、确定有穷自动机DFA3、不确定有穷自动机NFA4、NFA转换成DFA（确定化）5、有穷自动机的化简6、正规式和有穷自动机的相互转换7、正规文法和有穷自动机的相互转换小结1——正规文法和正规式的转换(正规式r

文法G)原产生式 变换后产生式规则1

A→xy

A→xB

B→y规则2

A→x*y

A→xA

A→y规则3

A→x|y

A→x

A→yPage

67第4章词法分析2023/10/2例:将r=a(a|d)*转换成相应的正则文法令转换成文法G=(VN,VT,P,S)其中VT={a,d}，文法开始符为S首先形成S→a(a|d)*,然后A→(a|d)A

A→εA→aA

A→dA变换:最终有产生式：S→aA

，A→ε，A→aA，A→dAPage

68第4章词法分析2023/10/2S→aAS→a(a|d)*原产生式

变换后产生式规则1

A→xy

A→xB

B→y规则2

A→x*y

A→xA

A→y规则3

A→x|y

A→x

A→y规则1规则2规则3A→(a|d)*ε小结1——正规文法和正规式的转换(正规文法G

正规式r)正规式Page

69第4章词法分析2023/10/2A=xyA=x*y文法产生式规则1

A→xB

B→y规则2

A→xA|y规则3

A→x

A→yA=x|y例：将文法G[S]转换成正规式G：S→a

A|aA→dA|d解：S→aA|aA→dA|d将A代入S中得:

S=ad*d|a利用正规式变换得S=a(d*d|ε)=ad*说明:d*d|ε=(ε|d|dd|…)d|ε=d|dd|…|ε=

d*所求正规式为ad*文法产生式

正规式规则1

A→xB

B→y

A=xy规则2

A→xA|y

A=x*y规则3

A→x

A→y

A=x|yS→aA

S→aA=d*d

(规则2)S=aA|a

(规则3)Page

70第4章词法分析2023/10/2小结2——确定有穷自动机DFAPage

71第4章词法分析2023/10/2一个DFA

M是一个五元组:M=（K,Σ,f,S,Z）K是一个有穷集，它的每个元素称为一个状态；Σ是一个有穷字母表，它的每个元素称为一个输入字符；f是一个从K

X∑→K的单值部分映射(映射函数)。f(ki,a)=kj意味着当前状态为ki、输入字符为a时，将转换到下一状态kj；S∈K,是唯一的初态；Z

⊂K,是一个终态集，终态也称为可接受状态或结束状态。小结2——确定有穷自动机DFA例

DFA

M=（{S，U，V，Q},{a，b},f,S,{Q}）f（S，a）=U

f（S，b）=Vf（V，a）=U

f（V，b）=Qf（U，a）=Q

f（U，b）=Vf（Q，a）=Q

f（Q，b）=Q状态转换图表示为:初态终SUVQababab态

a,b状态字符Page

72第4章词法分析2023/10/20001小结3——不确定有穷自动机NFAPage

73第4章词法分析2023/10/2一个NFA

M✁一个五元组：M=(K,Σ,f,S,Z)K✁一个有穷集，它的每个元素称为一个状态；∑✁一个有穷字母表，它的每个元素称为一个输入字符；f✁一个从K

X∑*至K的子集的映射，即KX∑*→2K

；S

⊂K，✁一个非空初态集；Z

⊂K，✁一个终态集。小结3——不确定有穷自动机NFAf（P，1）={Z}矩阵表示:0

1S

{P}

{S,Z}P

{}

{Z}Z{P}

{P}001SPZ00,1111状态图表示:K

∑

S例NFA

M=（{S,P,Z},{0,1},f,{S,P},{Z}）其中:f（S，0）={P}

f（S，1）={S，Z}f（Z，0）={P}

f（Z，1）={P}初态终态Page

74第4章词法分析2023/10/2小结4——NFA转换成DFA(确定化)Page

75第4章词法分析2023/10/2子集法基本思想:–

让DFA

的每个状态对应NFA

的一个状态集合。即DFA用它的一个状态记录在NFA读入一个输入符号后可能达到的所有状态。S0=ε-closure(K0)为M的开始状态；（即，所求的DFA的开始状态S0✁已知的NFA的开始状态K0的ε-闭包）Page

76第4章词法分析{5,6,7,1,2,4}

T22023/10/2}{5,6,7,1,2,4}

T2{8,3,6,7,1,2,4}

T1}{9,5,6,7,1,2,4{

0{78,2,3,4,6},7,1,2,4}{5,6,7,1,2,4{5,6,7,1,2,4}

T2{9,5,6,7,1,2,4}T3{8,3,6,7,1,2,4}

T1IbIaIεε10124536789abab

b0

εεεεεε,T1,0T1

{8,3,6,7,1,2,4}

T1T2T3}{10,5,6,7,1,2,4

T4

{8,3,6,7,1,2,4}

T1000{8,3,6,7,1,2,4}

T1

{10,5,6,7,1,2,4}

T401计算ε-closure(0)={0,1,2,4,7}——标为T0，即T0={0,1,2,4,7}计算ε-closure(move(T0,a))=ε-closure({3,8})={1,2,3,4,6,7,8}——标为T1，即T1={1,2,3,4,6,7,8}计算ε-closure(move(T0,b))=ε-closure({5})={1,2,4,5,6,7}——标为T2，即T2={1,2,4,5,6,7}计算ε-closure(move(T1,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=T1计算ε-closure(move(T1,b))=ε-closure({5,9})={1,2,4,5,6,7,9}——标为T3，即T3={1,2,4,5,6,7,9}T0Page

77第4章词法分析2023/10/2T1T2T4{0,1,2,4,7}T3

{1,2,4,5,6,7,9}{1{,12,,23,,44,,56,,67,7,8}}计算ε-closure(move(T2,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=T1计算ε-closure(move(T2,b))=ε-closure({5})={1,2,4,5,6,7}=

T2计算ε-closure(move(T3,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=T1计算ε-closure(move(T3,b))=ε-closure({5,10})={1,2,4,5,6,7,10}——标为T4，即T4={1,2,4,5,6,7,10}计算ε-closure(move(T4,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=T1计算ε-closure(move(T4,b))=ε-closure({5})={1,2,4,5,6,7}=

T2T0Page

78第4章词法分析2023/10/2{0,1,2,4,7}T1{1,2,3,4,6,7,8}T2{1,2,4,5,6,7}T3T4{{11,2,2,4,4,5,5,6,6,7,7,1,90}}小结5——有穷自动机的化简DBASaaabbba,bCB

DAEFSbaaaaaabbbbbba1.将M的状态分成非终态和终态集{S,A,B}

{C,D,E,F}2

寻找子集中不等价状态{S,A,B}=>{S}{A,B}=>{S}{A}{B}{C,D,E,F}3令D代表{C,D,E,F}a

bS

A

BA

C

BB

A

DC

C

ED

F

DE

F

DF

C

EP={{S},{A},{B},{D}}分割法：Page

79第4章词法分析2023/10/2小结6——正规式和有穷自动机的等价性复合正规式e的构造规则1.

先构造如下的NFAyxe2.然后按下述三种情况进行分解，直至每条弧上标记一个字符e1Xye=e1|e2e2X

1e1ye2e=e1e2X

1εyεe1e=e1*Page

80第4章词法分析2023/10/2从正规文法G到NFA的转换方法设文法G=(VN,VT,P,S)相应NFA

M=(K,∑,f,K0,Z),则：➀

∑=VT➁

K0=S③

增加一个新的状态Z作为终态④

K=VN∪{Z}⑤

f由以下方法求得：若P中有A→aB，则有f(A,a)=B；若P中有A→a，则有f(A,a)=Z；若P中有A→ε，则有f(A,ε)=Z；Page

81第4章词法分析2023/10/2小结7——正规文法和有穷自动机的等价性练习Page

82第4章词法分析2023/10/21、构造正规式1(0|1)*101相应的DFA思路：先由正规式r求出NFA再由NFA确定化为DFA①先由正规式r求出NFA将正规式r=1(0|1)*101分解成

r=r1r2r3，其中：r1=1，