编译程序构造与实践教程第三章

第三章词法分析3.1概况1.词法分析与词法分析程序

编译程序的功能是把高级程序设计语言源程序翻译成等价的低级语言目标程序，而源程序本身是一个基本符号序列或字符序列。为此，首先必须进行词法分析，编译程序中完成词法分析工作的部分称为词法分析程序，或称扫描程序。

其功能有三：

•扫描(读入)源程序字符序列，

•识别开符号(单词)并转换为等价的内部中间表示(属性字)，

•进行一些简单而有利于下一阶段之处理的工作(删除注解与空格等无效字符、某些预处理)。输入：源程序字符序列输出：属性字序列基础文法：正则文法2.符号的识别与重写规则的关系

C语言符号：标识符、常量、字符串、标号、界限符（关键字，专用符号）符号都可用正则文法规则来定义：

U::=VTU::=T（U、VVN，TVT）<标识符>::=<标识符>字母|<标识符>数字|字母

<整数>::=<整数>数字|数字

<逻辑与>::=<&符号>&<&符号>::=&其中字母是具体的英文字母，数字是具体的数字。即使关键字，如int等也可以用正则文法规则来定义：<int符号>::=<int-2>t<int-2>::=<int-1>n<int-1>::=i因此，关键字的定义都可采用正则文法规则形式。词法分析程序可以手工实现，也可自动生成。3.2词法分析程序的手工实现3.2.1实现要点

实现词法分析程序的大致步骤如下：

确定程序设计语言(或其子集)，明确相应的字符集、符号及其构造

总体设计

•设计各类数据结构，包括输入(源程序字符序列)与输出(属性字序列)，以及各类表格的数据结构

•

功能模块分解，明确各个模块(子程序)的功能与相互接口,画出总控流程图及各个子程序的控制流程图

编程，并设计调试实例，进行调试，完成研制。实现的要点是如下两方面，即，属性字的设计与标识符的处理。3.2.2属性字的设计属性字是符号的内部中间表示,对其设计要求，一是不同的符号都有唯一的表示，能彼此区分开，二是便于后继编译阶段的处理。

为此，所有属性字是等长、定长的。属性字指明是什么符号，且刻划了符号的属性。

1.属性字的一般结构

符号类识别开不同类的符号，符号值识别开同一类中不同的符号。例如标识符类。

当词法分析程序扫描到一个标识符时，把它的相关条目登录在标识符表中，以所登录的条目的序号或指针作为相应属性字的符号值，通过此序号或指针可以很方便地存取该标识符。关于无正负号整数，情况类似。

符号类符号值2.属性字的设计属性字的设计是词法分析程序之实现的重要方面。它的设计要有利于语法分析阶段的处理。

符号编码表如下。

符号类编码助记忆名符号类编码

助记忆名

无定义

标识符

整数

+

-

*/%<<=>>===!=&&&||!=0123456789101112131415161718$UND$ID$NUM$PLUS$MINUS$STAR$SLASH$MOD$LT$LE$GT$GE$EQ$NEQ&ADDR$AND$OR$NOT$ASSIGN()[]{},;void

intfloatchar

structifelsewhiledoforreturn19202122232425262728293031323334353637$LPAR$RPAR$LS$RS$LB$RB$COMMA$SEMICOLON$VOID$INT$FLOAT$CHAR$STRUCT$IF$ELSE$WHILE$DO$FOR$RETURN例属性字序列之例

voidmain(){inti,j,d;if(i>j)d=i-j;elsed=j-i;d=d/4;}

输入符号属性字序列

输入符号属性字序列voidmain(){inti,j,d;if(i>j)d27,"void"1,"main"19,"("20,")"23,"{"28,"int"1,"i"25,","1,"j"25,","1,"d"26,";"32,"if"19,"("1,"i"10,">"j,"j"20,")"1,"d"=i-j;elsed=j-i;d=d/4;}18,"="1,"i"4,"-"1,"j"26,";"33,"else"1,"d"18,"="1,"j"4,"-"1,"i"26,";"1,"d"18,"="1,"d"6,"/"2,"4"26,";“24,"}"相应的属性序列:属性字结构的改进·

分成两大类：特定符号、非特定符号·

指明说明符还是运算符·

运算符时给出优先级特定符号类符号的属性字可有如下的构造。

01234567…1516…31特定符号说明符运算符运算符优先级

符号类编码符号值

运算符优先级定义如下：8：&!+-

（单目）7：*

/%6：+

-

（双目）5：<<=>>=4:==!=3:&&2:||1:=

符号类符号值

符号类符号值100027"void"101118"="00001"main"00001"i"100019"("10164"-"100020")"00001"j"100023"{"100026";"110028"int"100033"else"00001"i"00001"d"100025","101118"="00001"j"00001"j"100025","10164"-"00001"d"00001"i"100026";"100026";"100032"if"00001"d"100019"("101118"="00001"i"00001"d"101510">"10176"/"00001"j"00002"4"100020"("100026";"00001"d"100024"}"例改进的属性字序列3.2.3标识符的处理标识符是源程序中出现最频繁的符号，编译程序处理的重点是标识符。对标识符的处理涉及下列三方面：1.区分标识符的定义性出现与使用性出现2.确定标识符的作用域3.确定标识符属性字的符号值1.区分标识符的定义性出现与使用性出现1）定义性出现时填标识符表（符号表）应用性出现时查标识符表（符号表）2）定义性出现一般在程序的说明部分应用性出现一般在程序的控制部分例见下页。例设有C程序如下：intmax3(inta,intb,intc){intmax;

if(a>b)max=a;elsemax=b;

if(c>max)max=c;returnmax;}main(){int

x,y,z,max;

printf(″Inputvaluesofx,y,andz:″);

scanf(″%d%d%d″,&x,&y,&z);max=max3(x,y,z);

printf(″max(%d,%d,%d)=%d\n″,x,y,z,max);}定义性出现？使用性出现？符号类符号值符号类符号值110028″int″101118″=″00001″max3″00001″a″100019″(″100026″;″110028″int″100033″else″00001″a″00001″max″100025″,″101118″=″110028″int″00001″b″00001″b″100026″;″100025″,″100032″if″110028″int″100019″(″00001″c″00001″c″100020″)″101510″>″100023″{″00001″max″110028″int″100020″)″00001″max″00001″max″100026″;″101118″=″100032″if″00001″c″100019″(″100026″;″00001″a″100037″return″101510″>″00001″max″00001″b″100026″;″100020″)″100024″}″00001″max″max3之函数定义的属性字序列

标识符表

max300001max3a00001ab00001bc00001cmax00001maxx00001xy00001yz

00001z问题是：在函数max3与main函数中都有标识符max，它们在控制部分中出现时代表不同的数据对象，如何区分?2.确定标识符的作用域作用域：标识符与某类型属性相关联的有效范围。同一个标识符出现在不同的作用域中将代表不同的数据对象。

/*Scopeforidentifier*/intm=3;int

fun(inta,intb){intm=4,x=5;return(a+m)*(x-b)-m;}main(){intx=1,y=1;

printf(″fun(%d,%d)/%d=%d\n″,x,y,m,fun(x,y)/m);}

请指明各个标识符的作用域，并说明运行结果。确定标识符的作用域，作用在于：当词法分析程序扫描到某个标识符的使用性出现时，通过确定其作用域，能确定该标识符所代表的数据对象，从而能确定其具有的类型等属性。为了确切地确定一个使用性出现的标识符的作用域，采用静态作用域法则，并按“最接近的嵌套”约定来确定作用域。

为了实现正确地确定标识符的作用域，简单而可行的办法是利用后进先出栈。确定标识符属性字的符号值

不同的符号应有不同的属性字。

对于特定符号类，一个符号类也就是一个符号，即，有唯一的属性字。

对于非特定符号类，同一个符号类可以有多个不同的符号，确切地说，对于标识符，同为标识符类，却可以有多个不同的标识符。常量情况类似。

符号值区分同一类中不同的符号。

可如下地处理。

•简单变量为标识符表序号；

•常量为常量表序号；

•其它各类标识符为相应信息表之序号。

3.2.4词法分析程序的设计和编写

1.总控流程图

总控程序流程示意图入口置初值

源程序结束是出口

否取符号，并

生成属性字

输出属性字取符号置初值返回返回

重查sym=“”

放过空字符生成属性字生成属性字

是是

字母是ch拼入sym取字符字母数字否关键字否查造标识符表

否

数字是ch拼入sym取字符数字否查造常量表生成属性字

否是

S[1]:=ch

返回

取字符

S[2]:=ch

重查

查符号机查到否S[2]:=′′查符号机查到否出错

内表示表是内表示表是

取字符生成属性字返回

取符号子程序的程序控制流程示意图词法分析程序的基本子程序（函数）取符号子程序、

取字符子程序、

查造标识符表子程序、查造常量表子程序、

查关键字表子程序、查符号机内表示表子程序重点：取符号子程序的编写。注意：取字符子程序的编写。

取符号子程序的约定:

约定1进入时已取到当前符号的第一个字符；约定2在离开时已取到当前符号的后继字符。2.数据结构的设计手工实现词法分析程序的基本思路

·确定所要实现的语言（或其子集）

·设计属性字，并设计各类表格标识符表、常量表、关键字表、符号机内表示表等

·画出总控流程图及各子程序的流程图

·最终完成词法分析程序的编程及其调试要点是数据结构（包括表格）的设计。

词法分析时使用的数据结构（表）：属性字序列

字符表符号机内表示表关键字表标识符表（符号表）无正负号整数表（常量表）重点是属性字的数据结构设计。属性字的数据结构设计：

typedef

struct

属性字{符号类类型

属性字符号类；符号值类型符号值；/*可以是字符数组类型*/}属性字类型；其中符号类类型可定义如下：

typedef

struct

{int

符号大类；/*1：特定符号类0：非特定符号类*/

int

说明符标志；

/*1：说明符，

0：非说明符*/

int

运算符标志；

/*1：运算符，

0：非运算符*/

int

运算符优先级；

int

符号类编码；

}符号类类型；

属性字序列可以用数组类型定义如下：

属性字类型属性字序列[MaxAttriWordLength];

其中,MaxAttriWordLength是可允许的属性字序列最大长度。

标识符表条目的数据结构可设计如下。

typedef

struct

{char标识符[MaxIdLength];

/*当符号值为符号本身时此成员变量可删*/

属性字类型标识符属性字；

int

条目序号；/*当符号值为序号时此成员变量可删*/

}标识符表条目类型；

标识符表的数据结构可设计如下：

标识符表条目类型标识符表[MaxIDTLength];

表格的输入，可以以赋初值方式给出。属性字类型符号机内表示表[22]={{{1,0,1,6,3},"+"},{{1,0,1,6,4},"-"},{{1,0,1,7,5},"*"},{{1,0,1,7,6},"/"},{{1,0,1,7,7},"%"},{{1,0,1,5,8},"<"},{{1,0,1,5,9},"<="},{{1,0,1,5,10},">"},{{1,0,1,5,11},">="},{{1,0,1,4,12},"=="},{{1,0,1,4,13},"!="},{{1,0,1,3,14},"&"},

{{1,0,1,4,15},"&&"},{{1,0,1,3,16},"||"},{{1,0,1,2,17},"!"},{{1,0,1,1,18},"="},{{1,0,0,0,19},"("},{{1,0,0,0,20},")"},{{1,0,0,0,21},"["},{{1,0,0,0,22},"]"},{{1,0,0,0,23},"{"},{{1,0,0,0,24},"}

"},{{1,0,0,0,25},","},{{1,0,0,0,26},";"}};属性字类型关键字表[10]={{0},{{1,0,0,0,27},"void"},{{1,1,0,0,28},"int"},{{1,1,0,0,29},"float"},{{1,1,0,0,29},"char"},

{{1,1,0,0,31},"struct"},{{1,0,0,0,32},"if"},{{1,0,0,0,33},"else"},{{1,0,0,0,34},"while"},{{1,0,0,0,35},"do"},{{1,0,0,0,36},"for"}，{{1,0,0,0,37},"return"}};3.各子程序的实现

子程序包括：

取符号子程序、

取字符子程序、

查造常量表子程序、

查造标识符表子程序、

查符号机内表示表子程序

这些子程序的实现都是容易的，只是指出：

•取字符子程序，当取到标志输入结束的字符时，需给出相应信息。

•查符号机内表示表分成2个子程序，分别查关键字表与查单双字符表。

•查造标识符表，查是使用性出现时进行，而造是定义性出现时进行。一般要涉及标识符的作用域问题。

•宜加入出错处理功能。3.3词法分析程序的自动生成

3.3.1词法分析程序自动生成的基本思想

•引进通用扫描算法，进行词法分析

基于与程序设计语言相关的一些表

不同的语言有不同的表

•引进构造程序，生成表

根据语言的特定符号说明书

其中指明符号的组成与机内表示等词法分析程序自动生成的构造程序与通用扫描算法及程序设计语言的符号说明书之间的联系如下所示。

关于某程序设计语言的符号说明书

构造程序

通用扫描算法

各类表扫描程序语言符号说明书描述的内容：

1.语言中允许哪些字符？

2.有哪几类符号，各类符号如何组成？

3.各类符号的机内表示是什么？

符号的结构与字符类1)标识符或保留字构形:<开始字符>{<其他字符>}2)整数构形:<数字>{<数字>}3)单字符界限符构形:<字符>4)双字符界限符构形:<字符><字符>5)关键字构形:<括号><开始字符>{<其他字符>}<括号>五类构形：DELIMDELIMDELIMDIGIT｛DIGIT｝IDBEG｛IDCHAR｝DELIMIDBEG｛IDCHAR｝DELIM通用扫描算法功能：处理五类构形2.*

扫描程序定义与构造程序扫描程序定义〈扫描程序〉∷=BEGIN<标识符1>[<标识符2>]{<类定义>}{<符号定义>}END〈类定义〉∷=〈类名字〉〈字符表〉〈类名字〉∷=IDBEG｜IDCHAR｜DIGIT｜IGNORE

｜INVISICHAR｜DELIM〈字符表〉∷=［ALLBUT］〈字符〉｛〈字符〉｝〈符号定义〉∷=RES〈整数〉〈符号〉｛〈符号〉｝〈符号〉∷=〈字符〉｛“｜”〈字符〉｝｜“不包含空白字符的EBCDIC字符序列”〈字符〉∷=“除空白字符外的EBCDIC字符”｜〈十六进制数字〉〈十六进制数字〉〈十六进制数字〉∷=0｜1｜2｜3｜4｜5｜6｜7｜8｜9

｜A｜B｜C｜D｜E｜F说明：标识符1是扫描程序的名称，标识符2是词法分析时查看源程序的程序名。某程序设计语言的符号说明书之例。

BEGINSCANNER

DIGIT0123

IDBEGABCDEFG

IDCHARabcdefg0123456789

INVISICHARX20

DELIM+-*/%<<=>>===!=&&&||!=

DELIM()[]{},;

RES3+-*/%

RES8<<=>>===!=

RES14&&&||!=

RES19()[]{},;

KEY27voidintfloatcharstruct

KEY32ifelsewhiledoforreturn

END

为了描述更一般的符号，

•引进正则表达式描述符号的表示法。

例如，L{L|D}D{D}

构造程序构造程序的功能：读入扫描程序定义，并由此建立通用扫描算法所用的内部表。输入：扫描程序定义输出：通用扫描算法所使用的内部表构造程序的功能决定于所处理的正则表达式，上述扫描程序定义描述的是5类正则表达式：

IDBEG{IDCHAR}DIGIT{DIGIT}DELIMDELIMDELIMDELIMIDBEG{IDCHAR}DELIM

只要构造程序能处理某正则表达式，就能处理相应的一类符号。为了实现词法分析，

•引进状态转换图

与有穷状态自动机

3.*

自动生成系统LEX简介

LEX是当前广泛应用的词法分析程序自动生成系统，本质是从正则表达式来生成等价的确定有穷状态自动机。特点是能灵活地和足够强有力地表达各种正则表达式，因此能适应各种程序设计语言。

LEX系统由三部分组成：•

说明部分：

letter[A-Z,a-z]digit[0-9]idletter{letter|digit}integerdigit{digit}*•

翻译部分：

while{return($WHILE);}if{return($IF);}id{csidt();return($ID,sym);}•

辅助过程部分：

csidt(){查造标识符表函数实现细节}3.3.2正则表达式

1.正则表达式的概念

这是一种适合于描述符号的表示法：

•易理解正被定义的是什么符号集合；

•更容易构造高效识别程序；

•有利于自动地构造识别程序；

•可用于其他各种信息流的处理。

例如，L{L|D}表示标识符的组成，D{D}表示整数的组成。而可以用

D{D}.D{D}[E[+|-]D{D}]|D{D}E[+|-]D{D}

表示实数的组成。

正则表达式是描述程序设计语言符号之组成的好工具。

1.正则表达式的概念及其性质(1)概念设有字母表Σa.a∈Σ，则a是字母表Σ上的正则表达式；(原子正则表达式)

b.若e、e1与e2都是字母表Σ上的正则表达式，则(e)、e1e2、e1｜e2

与｛e｝都是字母表Σ上的正则表达式；

按照严格的定义，空串ε与空集Ø也是字母表Σ上的正则表达式；上述概念表明：一般的正则表达式可以从原子正则表达式或较小的正则表达式通过加括号或一些运算来构造。例

设Σ1={0,1},则(0|1){0|1}是Σ1上的正则表达式。例

设Σ2={A,B,0,1}，则(A|B){A|B|0|1}是Σ2上的正则表达式。

(2)

正则表达式e的值是字母表上的正则集，记作｜e｜。||=||={}|a|={a}|(e)|=|e||e1e2|=|e1||e2|={xy|x|e1|,且y|e2|}|e1|e2|=|e1||e2|={x|x|e1|或x|e2|}|{e}|=|e|*即，|e|的闭包例如，|a|={a}|D{D}|=|D||{D}|=|D||D|*={D}{D}*={D}+

所以，|D{D}|={x|x是整数}，（D是数字）请自行计算|(0|1){0|1}|与|(A|B){A|B|0|1}|

(3)等价:若|e1|=|e2|,则称e1与e2是等价的,记为e1=e2(4)正则表达式与语法规则的联系重写规则（扩充表示法）：

〈标识符〉∷=字母｛字母｜数字｝

〈整数〉∷=数字｛数字｝

正则表达式：

字母｛字母｜数字｝数字｛数字｝显然，|字母｛字母｜数字｝|={x|<标识符>=>*x,x是标识符}|数字｛数字｝|={x|<整数>=>*x,x是整数}因此正则表达式与扩充表示法的正则文法重写规则之右部相当。但正则表达式更明确直观地描述了一类符号的结构。

正则表达式与词法分析程序的实现

自动构造的词法分析程序应能识别程序设计语言中的任何符号，包括即将可能扩充的符号。这意指，程序设计语言的符号说明书中应能描述任何希望包含的符号。正则表达式是描述符号之结构的好工具，因此，可以把正则表达式应用于程序设计语言的符号说明书。

如何应用正则表达式实现词法分析程序的自动生成？

应用正则表达式实现词法分析程序自动生成的思路大致如下。

·让正则表达式对应于一个状态转换图或有穷状态自动机

·从状态转换图或有穷状态自动机对应到词法分析程序

从正则表达式生成状态转换图，思路如下：首先建立一个有向图，它只有开始状态结点与终止状态结点，两结点用一弧相连，弧上标记就是所给的正则表达式。然后应用下列三个转换规则（见图3-5）对所给出的正则表达式进行转换，还可应用转换规则时，继续应用转换规则进行转换，直到一切弧上的标记都是原子正则表达式，而不能再应用转换规则时结束。

Se2e1e1|e2ZSZ转换为转换为SZe1e2Se2e1Ze1e3SZe2SZe1{e2}e3转换为最终所得的是相应的状态转换图。从正则表达式到状态转换图的例子。L转换为转换为(d)(e)LDDNSDIDLSZLIDDN（a）(b)(c)SZL{L|D}D{D}SZL{L|D}|D{D}转换为转换为L|DSDLZDNI(e)中为所求的状态转换图。下面讨论如何从正则文法出发生成状态转换图。(1)从正则表达式到状态转换图a.状态转换图的引进

<id>::=L|<id>L|<id>D

Y

Y

Y

入口L取符号LNDN

出口

N

出口

L,D

抽象成：SLI其他

E称状态转换图引进目的：识别正则文法的句子。状态转换图：为识别正则文法的句子而专门设计的有向图。如何理解状态转换图？例正则文法G[Z]：

Z∷=Za｜Ab｜Ba

A∷=Bb｜aB∷=Aa｜b状态转换图：

AabSabZabaB

b.状态转换图的构造状态转换图构造步骤如下：步骤1以符号S为开始状态作结点(假定文法的字汇表中不包含符号S)；步骤2以每一个非终结符号为状态作结点；步骤3对于形如Q∷=T的每个规则，引一条从开始状态S到状态Q的弧，其标记为T；而对于形如Q∷=RT的规则引一条从状态R到Q的弧，其标记为T。其中R为非终结符号，T为终结符号；步骤4识别符号相应的状态作为终止状态。c.应用状态转换图来识别句子一般地识别步骤如下。步骤1从开始状态开始，以它作为当前状态，并从输入字符串x的最左字符开始，重复步骤2直到达到x的右端为止。步骤2扫描x的下一字符(当前字符)，在当前状态射出的各个弧中找出标记有该字符的弧，并沿此弧前进，以所达到的状态作为下一当前状态。假定有输入字符串aababb，要识别它是否是相应正则文法的句子。

例正则文法G[Z]：

K∷=If｜SeI::=i

S∷=LsL::=ElE::=e

状态转换图：

I

if

AELSK

else

当识别一个字符串x时，如果能从状态转换图的开始状态出发，行进达到x的右端,x为句子的充分必要条件是最后的当前状态为终止状态。输入字符串x=else,是否是该正则文法的句子？

elseAELSK或写为：

(A)e→(E)l→(L)s→(S)e→(K)K是终止状态，所以，输入字符串else是上述正则文法的句子。

为什么可以通过运行状态转换图来识别正则文法的句子？步骤

当前状态

输入的其余部分

1AelseK2ElseS3LseL4SeE5Kelse运行状态转换图：利用状态转换图识别正则文法句子的过程。例正则文法G[Z]：

Z∷=Za｜Aa｜BbA∷=Ba｜aB∷=Ab｜b

AaaSbaZabbB

输入字符串：ababaaa

(2)确定有穷状态自动机DFA概念状态转换图是一种有向图，由5个要素组成，把它们抽象，便到得有穷状态自动机FA。一个确定的有穷状态自动机DFA是五元组

DFAD=(K，Σ，M，S，F),其中,K：状态集，Σ：字母表，

M：K×Σ→K映象，

S∈K开始状态，FK终止状态集例DFAD=({A,I,E,L,S,K},{i,f,e,l,s,e},M,A,{K})其中,M：M(A,i)=I

M(I,f)=KM(A,e)=EM(E,l)=LM(L,s)=SM(S,e)=K例

设有正则文法G[Z]:

Z::=Aa|BbA::=a|BaB::=Ab|b

可为其构造状态转换图如图所示。

相应的DFAD=(K,{a,b},M,S,{Z})，

其中，

K={S，A，B，Z}

M：M(S,a)=AM(S,b)=B

M(A,a)=ZM(A,b)=B

M(B,a)=AM(B,b)=ZAZSBabbabab.运行DFA扩充了的映象M：

M(R,ε)=R，其中R为任意状态；

M(R,Tt)=M(M(R,T)，t)，其中t∈Σ*，T∈Σ。接受：对于某个DFAD=(K,Σ,M,S,F)，如果M(S,t)=P,P∈F,则称字符串t可被该DFAD所接受。例识别字符串ababaa

是否可为上述DFA所接受。

M(S,ababaa)=M(M(S,a),babaa)=M(M(A,b),abaa)=M(M(B,a),baa)=M(M(A,b),aa)=M(M(B,a),a)=M(A,a)=ZZ是终止状态，所以,字符串ababaa可为该DFA所接受。运行DFA：识别输入字符串是否可被DFA所接受的过程。(3)不确定有穷状态自动机NFAa.NFA的引进例设有正则文法G3.3[Z]：

Z::=a|Ia|I0|0|N0I::=a|Ia|I0N::=0|N0相应的FA如下：存在U∷=WT和V∷=WTTUW

TV映像不唯一：状态W，字符T下映像到U或V。a,0aa,000a,0ZSNI0不确定的有穷状态自动机通常定义如下。

NFA是一个五元组(K,Σ,M,S,F)，其中,K:状态集Σ：字母表

M:K×Σ→K的子集所组成集合

SK开始状态集

FK终止状态集文法G[Z]:

Z::=a|Ia|I0|0|N0I::=a|Ia|I0N::=0|N0

NFAN=（{S，I，N，Z}，{a,0},M,{S},{Z}）其中，M:M(S,a)={I,Z}M(S,0)={N,Z}M(I,a)={I,Z}M(I,0)={I,Z}M(N,a)={}M(N,0)={N,Z}M(Z,a)={}M(Z,0)={}NFA与DFA的区别主要在于两方面:

开始状态与映像文法G[Z]:

Z∷=Z0｜T1｜0｜1T∷=Z0｜0

NFAN=

({S,T,Z},{0,1},M,{S},{Z})

其中M=？b.运行NFA扩充了的映象M：

M(R,ε)={R},其中R是任意的状态；

M(R,Tt)=M(Q1,t)∪M(Q2,t)∪…∪M(Qn,t)，其中，M(R,T)={Q1，Q2，…，Qn

}接受：若对于某NFA存在状态P,P∈F,有P∈M(S′,t)，S′∈S，则说字符串t可被该NFA所接受。当一个输入字符串为NFA所接受时，它就是相应文法的句子。关于输入字符串a0a00，运行NFA的过程如下：步骤当前状态输入的其余部分可能的后继选择1Sa0a00I,ZI2I0a00I,ZI3Ia00I,ZI4I00I,ZI5I0I,ZZ文法G[Z]:

Z::=a|Ia|I0|0|N0I::=a|Ia|I0N::=0|N0G[Z]：

Z::=Z0|T1|0|1T::=Z0|0关于输入字符串1010010,运行相应NFA的过程如下：步骤当前状态输入的其余部分可能的选择选择1S1010010ZZ2Z

010010T，ZT3T

10010ZZ4Z

0010T，ZZ5Z

010T，ZT6T

10ZZ7Z

0T，ZZc.从NFA生成DFA思路：假定对于一个NFA，存在状态R，对于它有：

M(R,T)=｛Q1,Q2,…,Qn｝即，转换到的状态可能是Q1或Q2，…，也可能是Qn。为使NFA成为等价的DFA,把状态集合{Q1,Q2,…,Qn｝看成单个状态，用[Q1,Q2,…,Qn]表示这单个状态，如:

M(S,0)={T,Z}M'([S],0)=[T，Z]

注意：DFA的状态名中所包含的原有状态名按字典顺序排列。NFAN=(K,∑,M,S,F)确定化为：DFAN'=(K',∑,M',S',F')其中，K'=K的一切子集组成的集合

S'=[S1,S2,…,Sn],这里S={S1，S2，…，Sn}M'：M([R1，R2，…，Rm],T)=[Q1,Q2,…,Qj]j这里M({R1,R2,…,Rm},T)=

M(Ri,T)={Q1,Q2,…,Qj}i=1F={