第六讲词法分析4讲义.ppt

第2章 词法分析 2.4 正规表达式到有限自动机的构造 2.5 词法分析器的自动生成 2.4.4 正规表达式到有限自动机构造示例 例2.10 试用DFA的等价性证明正规表达式(a∣b)*与(a*b*)*等价。 [解答] (1) 正规表达式(a∣b)*对应的NFA如图2–18所示。 用子集法将图2–18的NFA确定化得到如表2.7所列的转换表，重新命名后得到如表2.8所列的状态转换矩阵。 由于状态0和状态1均为终态，故无论输入什么字符，其下一状态仍是终态，故最简DFA如图2–19所示。 (2) 正规表达式(a*b*)*对应的NFA如图2–20所示。 用子集法将图2–20的NFA确定化得到如表2.9所列的转换表，重新命名得到如表2.10所列的状态转换矩阵。 例2.11 C语言可接受的合法的文件名为device:name.extension，其中第一部分（device:）和第三部分(.extension)可缺省。若device、name和extension都是字母串，长度不限，但至少为1，试画出识别这种文件名的DFA M。 [解答] 以字母“c”代表字母，则所求正规式为 (cc*: ∣ε)cc*(.cc*∣ε) 由此得到的NFA M如图2–21所示。 用子集法将NFA M确定化，得到如表2.11所列的转换表；重新命名后得到如表2.12所列的状态转换矩阵和如图2-22所示的DFA M。 例2.12 某高级程序语言无符号数的正规表达式为 digit+(.digit+)?(e (+∣?)?digit+)? 其中，digit表示数字，(?)? 表(?)中的内容可有可无，试给出其DFA M。 [解答] 我们用d代表digit，则用状态转换图表示接受无符号数的NFA如图2–23所示。 用子集法将NFA M确定化，得到如表2.13所列的转换表；重新命名后得到如表2.14所列的状态转换矩阵和如图2–24所示的DFA M。 由状态转换矩阵可以看出：状态5和状态6面对输入符号的下一状态都是相同的，但状态5为非终态，而状态6为终态，故图2–24的DFA已为最简。 例2.13 构造一个DFA，它接收Σ=｛a,b｝上所有满足下述条件的字符串：该字符串中的每个a都有至少一个b直接跟在其右边。 [解答] 已知Σ=｛a,b｝，根据题意得到正规表达式为b*(abb*)*。根据此正规表达式画出相应的NFA M如图2–25所示。 用子集法将NFA M确定化，得到如表2.15所列的转换表；重新命名后得到如表2.16所列的状态转换矩阵和如图2–26所示的DFA M。 2.5 词法分析器的自动生成 由于各种不同的高级程序语言中单词的总体结构大致相同，基本上都可用一组正规表达式描述，因而人们希望构造这样的自动生成系统：只要给出某高级语言各类单词词法结构的一组正规表达式以及识别各类单词时词法分析程序应采取的语义动作，该系统便可自动产生此高级程序语言的词法分析程序。所生成的词法分析程序的作用如同一台有限自动机，可以用来识别和分析单词符号。正规表达式与有限自动机的理论研究产生了自动生成词法分析程序的技术和工具。 LEX是由美国Bell实验室的M.Lesk和Schmidt于1975年用C语言研制的一个词法分析程序的自动生成工具。对任何高级程序语言，用户必须用正规表达式描述该语言的各个词法类（这一描述称为LEX的源程序），LEX就可以自动生成该语言的词法分析程序。LEX及其编译系统的作用如图2–29所示。 一个LEX源程序由用“%%”分隔的三部分组成：第一部分为正规式的辅助定义式，第二部分为识别规则，最后一部分为用户子程序。其书写格式为： 辅助定义式 %% 识别规则 %% 用户子程序 其中，辅助定义式和用户子程序是任选的，而识别规则是必需的。如果用户子程序缺省，则第二个分隔符号“%%”可以省去；但如果无辅助定义式部分，第一个分隔符号“%%”不能省去，因为第一个分隔符号用于指示识别规则部分的开始。 下面给出一个简单语言的单词符号的LEX源程序例子，其输出单词的类别编码用整数编码表示。 Auxiliary Definitions