|
知识路径: > 计算机系统基础知识 > 计算机软件基础知识 > 程序设计语言和语言处理程序知识 > 汇编、编译、解释系统的基本知识和基本工作原理 > 程序语言翻译基础 > 编译程序基本原理 > 词法分析 >
|
相关知识点:4个
|
|
|
|
有限自动机是一种识别装置的抽象概念,它能准确地识别正规集。有限自动机分为确定的有限自动机和不确定的有限自动机两类。
|
|
|
(1)确定的有限自动机(Deterministic Finite Automata,DFA)。一个确定的有限自动机是一个五元组(S,Σ,f,s0,Z),其中:
|
|
|
|
.Σ是一个有穷字母表,其每个元素称为一个输入字符。
|
|
|
.f是S×Σ→S上的单值部分映像。f(A,a)=Q表示当前状态为A、输入为a时,将转换到下一状态Q。称Q为A的一个后继状态。
|
|
|
|
.Z是非空的终止状态集合,。
|
|
|
一个DFA可以用两种直观的方式表示:状态转换图和状态转换矩阵。状态转换图简称为转换图,是一个有向图。DFA中的每个状态对应转换图中的一个节点,DFA中的每个转换函数对应图中的一条有向弧,若转换函数为f(A,a)=Q,则该有向弧从节点A出发,进入节点Q,字符a是弧上的标记。
|
|
|
(2)不确定的有限自动机(Nondeterministic Finite Automata,NFA)。一个不确定的有限自动机也是一个五元组,它与确定有限自动机的区别如下:
|
|
|
①f是S×Σ→2S上的映像。对于S中的一个给定状态及输入符号,返回一个状态的集合。即当前状态的后继状态不一定是唯一的。
|
|
|
|
|
任何一个NFA都可以转换为DFA,下面先定义转换过程中需要的计算。
|
|
|
|
若I是NFAN的状态集合的一个子集,定义ε_CLOSURE(I)如下:
|
|
|
.状态集I的ε_CLOSURE(I)是一个状态集。
|
|
|
.状态集I的所有状态属于ε_CLOSURE(I)。
|
|
|
.若s∈I,那么从s出发经过任意条ε弧到达的状态s'都属于ε_CLOSURE(I)。
|
|
|
|
由以上的定义可知,I的ε_闭包就是从状态集I的状态出发,经ε所能到达的状态的全体。
|
|
|
|
假定I是NFAN的状态集的一个子集,a是Σ中的一个字符,定义:
|
|
|
|
其中,J是所有那些可从I中的某一状态节点出发经过一条a弧而到达的状态节点的全体。
|
|
|
|
设NFAN=(S,Σ,f,s0,Z),与之等价的DFAM=(S',Σ,f',q0,Z'),用子集法将非确定的有限自动机确定化的算法步骤如下:
|
|
|
①求出DFAM的初态q0,即令q0=ε_CLOSURE({s0}),此时S'仅含初态q0,并且没有标记。
|
|
|
②对于S'中尚未标记的状态qi={si1,si2,…,sim},sij∈S(j=1,…,m)进行以下处理:
|
|
|
|
.对于每个a∈∑,令T=f({si1,si2,…,sim},a),qj=ε_CLOSURE(T)。
|
|
|
.若qj尚不在S'中,则将qj作为一个未加标记的新状态添加到S',并把状态转换函数f'(qi,a)=qj添加到DFAM中。
|
|
|
③重复进行步骤②,直到S'中不再出现未标记的状态时为止。
|
|
|
|
|
|
对上图所示的自动机进行化简所得的DFA如下图所示。
|
|
|
|
|