词法分析
知识点
1.词法分析器
1)、关键字:是由程序语言定义的具有固定意义的标识符。
(2)、标识符:用来表示各种名字,如变量名、数组名、过程名等。
(3)、常数:常数的类型一般有整型、实型、布尔型、文字型等。
(4)、运算符:如+、-、*、/等。
(5)、界符:如逗号、分号、括号、/*、*/等。
2、状态转换图
3、正规式与正规集(定义与正规式性质与等价性)
正规式等价性:若两个正规式U,V所表示的正规集相同,则两者等价
4、有限自动机(DFA与NFA)
DFA定义:一个确定有限自动机(DFA)M是一个五元式:M = (S, ∑, f, s0, F)
NFA定义 :一个非确定有限自动机(NFA)M是一个五元式M = (S, ∑, f, S0, F)
区别:
DFA:f是从 S×∑ →S的单值部分映射
NFA:f是从S×∑*→2S 的部分映射,其中,2S表示S的幂集合(所有S的子集组成的集合)(f是非单值的->M是非确定)
状态集合
5、非确定的有限自动机(NFA)
定义:一个非确定有限自动机(NFA)M是一个五元式M = (S, ∑, f, S0, F),其中
(1)、S是一个有限的状态集合,它的每个元素我们称为一个状态。(2)、∑是一个有限的输入符号的字母表,它的每个元素我们称为一个输入字符。
(3)、f是从S×∑*→2S 的部分映射,其中,2S表示S的幂集合(所有S的子集组成的集合)(f是非单值的M是非确定)。
(4)、状态集合S0是初始状态集合,它是S的子集。
(5)、状态集合F是终止状态的集合,它是S的子集。
6、正规式与有限自动机的等价性
(1)、对于任何∑上NFA M都可构造一个∑上的正规式V,使得 L(V) = L(M) 。其中,L(M)是∑上NFA M所能识别的字的全体L(V)是∑上的正规集。
(2)、对于∑上的每一个正规式V,存在一个∑上的DFA M,使得L(M) = L(V) 。
①、假定I是M’的状态集的子集,定义I的ε闭包ε_CLOSURE(I)为:
(a)若q∈I,则q∈ε_CLOSURE(I)
(b)若q∈I,那么从q出发经任意条ε弧而能到达的任何状态q’都属于ε_CLOSURE(I) ;
②、 假定I是M’的状态集的子集,a ∈ ∑,定义 Ia =ε_CLOSURE(J) 其中,J是所有那些可从I中的某一状态结点出发经过一条a弧而到达的状态结点的全体。
课后题