编译原理-西安交通大学(冯博琴)2_词法分析_3.0解读.ppt

一个DFA也可用一张（确定的）状态转换图来表示。假定DFA M含有m个状态和n个输入字符，那么，这个状态转换图含有m个状态结点，每个结点顶多有n条箭弧射出和别的结点相连接，整张图含有一个初态结点和若干个（可以为0）终态结点。 3 0 1 图2.5 状态转换图 2 a a a a b b b 状态 a b 0 1 2 1 3 2 2 1 3 3 3 - 如下表所示的状态转换矩阵对应的状态转换图如右图： 3 0 1 2 a a a b b b 上图所示的状态转换图的S、∑及∑*如下： S = {0,1,2,3} ∑= {a,b} ∑*= {α| α为ε，或者α为a、b的任意组合} 从初态0到终态3有如图所示的通路，箭弧上到标记符连接起来的字aa属于∑*，所以右图所示的DFA可以识别字aa。 同理：从初态0到终态3还有如图所示的通路，箭弧上到标记符连接起来的字bba属于∑*，所以右图所示的DFA可以识别字bba。 a 例2-13：科学表示法中数字常量的正则表达式对应的DFA： digit digit nat对应的DFA如下图 digit = [0-9] nat = digit + signedNat = ( +|- )? nat number = signedNat(“·”nat)？ signedNat对应的DFA如下图 加上可选的小数部分，数字常量的正则表达式number = signedNat(“·”nat)？ 对应的DFA如下图： + digit digit digit - + digit digit digit - digit digit ? a b b b 接受与正则式ab+|ab*|b* 相同的语言的DFA如下所示： 例2-14：串中只有一个b被如下所示的DFA接受： b not b not b 例2-15：包含最多一个b的串被如下所示的DFA接受： b not b not b 注意二者之 间的区别 定理：如果一个DFA M 的输入字母表为∑，则我们也称M是∑上的一个 DFA。可以证明:∑上的一个字集V ∑*是正规的，当且仅当存在∑上的DFA M，使得V =L(M)。 DFA的确定性表现在映射δ： S×∑→S是一个单值函数。即：对于任何状态s∈S和输入符号a∈∑， δ(s,a)唯一确定了一个状态。 从转换图角度，我们也可以得到答案。 如果允许是一个多值函数，我们就得到下一节要讲到的非确定自动机的概念。 一个非确定有限自动机（NFA） M是一个五元式： M ＝ (S,∑,δ,S0 ,F) ，其中 1、S是一个有限集，它的每个元素称为一个状态 2、∑是一个有穷字母表，它的每个元素称为一个输入字符 3、δ是一个从S×∑*至S的子集的映射，即δ： S×∑* → 2s 4、 S0∈S是唯一的初态 5、 F S是一个终态集（可空）。 一个含有m个状态和n个输入字符的NFA可用一张如下的状态转换图来表示：该图含有m个状态结点，每个结点可以射出若干条弧与别的结点相连接，每条弧用∑*中的一个字（可以是不同的字，也可以是空字）做标记，整张图至少含有一个初态结点和若干个（可以为0）终态结点。某些结点既可以是初态结点也可以是终态结点。 1 aa a,b 2 bb ab 0 a,b 0 1 ab,ba aa,bb ab,ba aa,bb 词法分析的任务： 从左至右逐个字符地扫描源程序，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。 词法分析器/扫描器：执行词法分析的程序。 源程序 扫描器 scanner 1、关键字 词法分析器的功能如下图所示： 2、标识符 5、界符 4、运算符 3、常数 由程序语言定义的具有固定意义的标识符。也可称为保留字或基本字。例如：Pascal中的begin，end，if等。 界符：如逗号、分号、括号、/*，*/ 等。它是确定的。 运算符：如+、-、*、/ 等。它是确定的。 常数的类型一般有整型、实型、布尔型、文字型等。它是不限的。 用来表示各种名字，如变量名、数组名、过程名等。它是不限的。 词法分析器的功能：输入源程序，输出单词符号。 单词符号：一个程序语言的基本语法符号。分为以下5种。 1、关键字：由程序语言定义的具有固定意义的标识符。也可称为保留字或基本字。例如：Pascal中的begin，end，if等。它是确定的。 2、标识符：用来表示各种名字，如变量名、数组名、过程名等。它是不限的。 3、常数：常数的类型一般有整型、实型、布尔型、文字型等。它是不限的。