第2章词法分析

1、Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春第二章第二章 词法分析词法分析本章主要讨论词法分析程序的设计原则，单词的描述技本章主要讨论词法分析程序的设计原则，单词的描述技术、识别机制及词法分析程序的自动构造原理。术、识别机制及词法分析程序的自动构造原理。1.词法分析的功能词法分析的功能 2.程序语言的单词符号种类及词法分析输出程序语言的单词符号种类及词法分析输出 3.词法分析程序的设计与实现词法分析程序的设计与实现4.正规表达式与有穷自动机正规表达式与有穷自动机5.词法分析程序的自动生成词法分析程序的自动生成P

2、rinciple of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春本章重点本章重点 单词的描述工具单词的描述工具 单词的识别系统单词的识别系统 设计和实现词法分析程序设计和实现词法分析程序 首先需要描述和刻画程序设计语言中的原子单位首先需要描述和刻画程序设计语言中的原子单位单词，其次需要识别单词和执行某些相关的动作。单词，其次需要识别单词和执行某些相关的动作。 描述程序设计语言的词法的机制是正规表达式，识别描述程序设计语言的词法的机制是正规表达式，识别机制是有穷自动机机制是有穷自动机。Principle of Compiling长春工

3、业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春词法分析程序词法分析程序功能：功能：逐个读入源程序字符并按照构词规则切分成一系列单词逐个读入源程序字符并按照构词规则切分成一系列单词主要任务：主要任务：读入源程序，输出单词符号读入源程序，输出单词符号其他任务：其他任务： 滤掉空格，跳过注释、换行符滤掉空格，跳过注释、换行符 追踪换行标志，指出源程序出错的行列位置追踪换行标志，指出源程序出错的行列位置 宏展开，宏展开，关键：关键：找出单词的分割符找出单词的分割符Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院

4、20112011春春l 词法分析是编译过程中的一个阶段，在语法分析前词法分析是编译过程中的一个阶段，在语法分析前进行。可以作为一个独立的子程序。进行。可以作为一个独立的子程序。优势表现为：优势表现为：简化设计简化设计改进编译效率改进编译效率增加编译系统的可移植性增加编译系统的可移植性 l 可以和语法分析结合在一起作为一遍，由语法分析可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使程序调用词法分析程序来获得当前单词供语法分析使用。用。Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院2011201

5、1春春单词符号单词符号是程序设计语言中具有独立意义的最小单位，程序设计是程序设计语言中具有独立意义的最小单位，程序设计语言基本组成成分。语言基本组成成分。五类：五类：关键字（保留字关键字（保留字/基本字）基本字）:if while 标识符：常量名标识符：常量名 变量名变量名常数：常数：34 56.78运算符：运算符：+ - / =，、,!,= /=*结束结束组合标识符组合标识符查保留字查保留字 保留字保留字 输出保留字输出保留字 输出标识符输出标识符组合整数组合整数 输出整数输出整数 输出单分符输出单分符 读字符读字符 读字符读字符读字符读字符输出双分符输出双分符 读字符读字符输出单分符输出单

6、分符/ 注释处理注释处理 输出单分符输出单分符 错误处理错误处理 YYYYYYYYYYNNNNNNNNNNPrinciple of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春正规表达式与有限自动机正规表达式与有限自动机要求要求正规式与正规集的定义正规式与正规集的定义有穷自动机的定义及表示有穷自动机的定义及表示NFANFA确定化为确定化为DFADFA掌握掌握DFADFA的化简的化简掌握用正规式构造掌握用正规式构造DFADFA掌握正规文法与有穷自动机间的转换掌握正规文法与有穷自动机间的转换 Principle of Compiling长春

7、工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春字母表和符号串的基本概念字母表和符号串的基本概念字母表字母表：元素的：元素的非空有穷非空有穷集合。记为集合。记为。 字母表包含了语言中所允许出现的一切字母表包含了语言中所允许出现的一切符号符号。 例如：例如： = 0，1符号串符号串(字字)：字母表中的符号所组成的：字母表中的符号所组成的有穷有穷序列。序列。 一个语言的句子总是它的字母表的符号串。这个符号一个语言的句子总是它的字母表的符号串。这个符号串的组成必须是按照文法规则组合而成的。串的组成必须是按照文法规则组合而成的。 语法分析的一个重要任务就是：判断一个符号

8、串的组语法分析的一个重要任务就是：判断一个符号串的组成是否满足某个文法的规定。成是否满足某个文法的规定。Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春字母表和符号串的基本概念字母表和符号串的基本概念(续续)空串：不包含任何符号的串，记为。*：表示上所有符号串的全体。空集：，不包含任何元素。 在本课程中，语言被认为是句子的集合。所以，一个语言就是对应于它的字母表上的一个符号串集合。Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春符号串的

9、运算符号串的运算符号串的长度符号串的长度：指符号串：指符号串x中所含符号的个数，记为中所含符号的个数，记为|x|。符号串相等符号串相等：若：若x、y是字母表是字母表上的两个符号串，那么当且仅当组成上的两个符号串，那么当且仅当组成x的各符号与组成的各符号与组成y的各符号依次相等时，则符号串的各符号依次相等时，则符号串x与符号串与符号串y相相等，记作等，记作x=y。 连接连接(并置并置)：若：若x、y是两个符号串，则是两个符号串，则xy表示连接，是将符号串表示连接，是将符号串y连连接在符号串接在符号串x的后面。若的后面。若x、y是字母表是字母表上的两个符号串，则上的两个符号串，则xy也也是字母表是

10、字母表上的符号串。上的符号串。 注意：连接没有交换率律，即注意：连接没有交换率律，即 xy yx 而对于空串而对于空串有有 x=x=xPrinciple of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春方幂方幂：x的的n次方幂即将次方幂即将n个个x连接。连接。x0 = , x1 = x, x2 = xx, xn=xxx=xx n-1=x n-1 x 乘积乘积：令：令A、B为两个符号串集合，为两个符号串集合，A和和B的乘积的乘积AB定义定义为：为：AB = xy | x A且且y B A=A =A A= A =方幂方幂：A的的n次方幂就

11、是将次方幂就是将n个个A相乘。相乘。 A0= A1=A A2=AA An=AAA=AA n-1 =A n-1 A Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春符号串集合的运算符号串集合的运算集合的正则闭包和集合的闭包集合的正则闭包和集合的闭包： 设设A为一个集合，则集合为一个集合，则集合A的正则闭包用的正则闭包用A+表示，定义为：表示，定义为： A+ =A1 A2 . A n 表示表示A上的所有的非空符号串的集合。上的所有的非空符号串的集合。 集合集合A的闭包用的闭包用A*表示，定义为：表示，定义为： A* =

12、A 0 A+ 表示表示A上的所有符号串（包括空字符串）的集合。上的所有符号串（包括空字符串）的集合。 例如：例如：A =a，b， 则则A+ =a,b,aa,ab,ba,bb,aaa,aab, A* = ,a,b,aa,ab,ba,bb,aaa,aab,Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春定义（正规式和正规集）定义（正规式和正规集）设字母表为设字母表为 ，辅助字母表，辅助字母表 = ， ， ， ， ， ， 。1、 和和 都是都是 上的正规式，表示的正规集分别为上的正规式，表示的正规集分别为 和和 ；2、对

13、任何、对任何a ，a是正规式，它所表示的正规集为是正规式，它所表示的正规集为a；3、假定、假定e1和和e2都是都是 上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为L(e1)和和L(e2)，那么，那么，(e1), e1 e2, e1 e2, e1 也都是正规式也都是正规式,它们所表示的正规集它们所表示的正规集分别为分别为L(e1), L(e1) L(e2), L(e1)L(e2)和和(L(e1) 。4、仅由有限次使用上述三步骤而定义的表达式才是、仅由有限次使用上述三步骤而定义的表达式才是 上的正规式，仅由上的正规式，仅由这些正规式所表示的集合才是这些正规式所表示的集合才

14、是 上的正规集。上的正规集。 或或； 连接；连接； 闭包闭包 规定优先顺序为规定优先顺序为“ ”、“ ”、“ ” ， 左结合左结合Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春例：令例：令 =a，b， 上的正规式和相应的正规集有：上的正规式和相应的正规集有：正规式正规式正规集正规集aaba*所有以所有以b开头后跟任意多个开头后跟任意多个a的字的字a ba,babab(a b)(a b)aa,ab,ba,bba ,a,aa, 任意个任意个a的串的串(a|b)*(aa|bb)(a|b)*所有含有两个相继的所有含有两个

15、相继的a或两个相继的或两个相继的b的字的字(a b) ,a,b,aa,ab 所有由所有由a 和和b组成的串组成的串Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春程序设计语言的单词都能用正规式来定义。程序设计语言的单词都能用正规式来定义。例例：令：令 =l，d，则，则 上的正规式上的正规式: r=l(l d) 定义的正规集为定义的正规集为: l,ll,ld,lll,ldd,就是标识符的词法规就是标识符的词法规则。其中则。其中l代表字母代表字母,d代表数字代表数字, 正规式正规式 ：字母：字母(字母字母|数字数字)

16、,它表示每个元素的模式是它表示每个元素的模式是“字字母打头的字母数字串母打头的字母数字串”,例例：令令 d， ，e，则，则 上的正规式上的正规式:d*(.dd*| )(e(+|-| )dd*| )表示的是无符号数。表示的是无符号数。 其中其中d为为09中的数字。中的数字。 比如：比如：2,12.59,3.6e2,471.88e-1等都是正规式表示集合中的等都是正规式表示集合中的元素。元素。Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春正规式的等价正规式的等价若两个正规式若两个正规式e1和和e2所表示的正规集相同所

17、表示的正规集相同,则说则说e1和和e2等价等价,写作写作e1=e2。设设r,s,t为正规式，正规式服从的代数规律有：为正规式，正规式服从的代数规律有：lr s=s r “或或”的交换律的交换律lr (s t)=(r s) t“或或”的可结合律的可结合律l(rs)t=r(st)“连接连接”的可结合律的可结合律lr(s t)=rs rt (s t)r=sr tr 分配律分配律 l r=r =r 是是“连接连接”的恒等元素的恒等元素le*e+le+=e*e=ee*l(e*)*=e*Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院201120

18、11春春有限自动机有限自动机研究词法分析器的重要理论基础研究词法分析器的重要理论基础lDFA，NFA的基本概念和理论的基本概念和理论 DFA:确定的有限自动机确定的有限自动机 (Deterministic Finite Automata) NFA:非确定的有限自动机非确定的有限自动机 (Nondeterministic Finite Automata)l正规文法、正规表达式与有限自动机之间的关系。正规文法、正规表达式与有限自动机之间的关系。Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春DFA的定义的定义一个确定的

19、有限自动机一个确定的有限自动机(DFA) M是一个五元组：是一个五元组： M=(S，s0，F),),其中其中: : 1. 1.S S是一个有穷集，它的每个元素称为一个状态；是一个有穷集，它的每个元素称为一个状态； 2.2.是一个有穷字母表，它的每个元素称为一个输入符号，所以也是一个有穷字母表，它的每个元素称为一个输入符号，所以也称称为输入符号表；为输入符号表； 3.3.是在是在SS上的单值映射，即，如上的单值映射，即，如 (s，a)=s，(sS，sS)就意味着，当前状态为就意味着，当前状态为s，输入符为，输入符为a时，将转换为下一个状态时，将转换为下一个状态s，我，我们把们把s称作称作s s的

20、一个后继状态；的一个后继状态； 4.4. s0 SS是唯一的一个初态；是唯一的一个初态； 5.5.F S是一个终态集，也称可接受状态或识别状态集。是一个终态集，也称可接受状态或识别状态集。Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春DFA映射的表示映射的表示直接给出：直接给出： (s，a)=s状态转换矩阵：状态转换矩阵： 行表示状态，列表示输入符号行表示状态，列表示输入符号状态转换图：状态转换图：结点：状态，用结点：状态，用表示；终态，用表示；终态，用表示表示有向弧有向弧 箭头箭头弧标记弧标记 输入字符输入字符

21、Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春例：有例：有DFA M =(0,1,2,3,a,b, ,0,3) 为：为：(0,a) = 1 (0,b) = 2(1,a) = 3 (1,b) = 2(2,a) = 1 (2,b) = 3(3,a) = 3 (3,b) = 3状态状态 输入输入ab0121322133*33Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春(0,a) = 1 (0,b) = 2(1,a) = 3 (1,b)

22、= 2(2,a) = 1 (2,b) = 3(3,a) = 3 (3,b) = 3aaab0123ba，bbPrinciple of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春DFA的确定性表现在：的确定性表现在： 对任何状态对任何状态s S，在读入了输入符号，在读入了输入符号a 之后，之后，能够唯一地确定下一个状态。能够唯一地确定下一个状态。 从状态转换图来看，若字母表从状态转换图来看，若字母表含有含有n个输入字符，个输入字符，那末任何一个状态结点最多有那末任何一个状态结点最多有n条弧射出，而且每条弧射出，而且每条弧以一个不同的输入

23、字符标记。条弧以一个不同的输入字符标记。Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春DFA识别的字识别的字一个字一个字可为可为DFA M所接受：对于所接受：对于* 中的任何字中的任何字，若存在一，若存在一条从初态结点到终态结点的条从初态结点到终态结点的通路通路，且这条通路上所有弧的，且这条通路上所有弧的标记符号连接成的字等于标记符号连接成的字等于。若若M的初态结点又是终态结点，则空字的初态结点又是终态结点，则空字可为可为M所识别。所识别。DFA M所能识别的符所能识别的符号号串的全体记为串的全体记为L(M)。

24、对于任何两个有穷自动机对于任何两个有穷自动机M和和M，如果，如果L(M)=L(M)，则称，则称M与与M是等价的。是等价的。 Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春每读入一个符号，读每读入一个符号，读头向后移动一个位置，头向后移动一个位置，有穷控制器控制状态有穷控制器控制状态转移到下一个状态转移到下一个状态在初始时，读头处于输在初始时，读头处于输入带的开始位置，表示入带的开始位置，表示准备读入，状态处于初准备读入，状态处于初始状态始状态整个模型由三部分组成：整个模型由三部分组成： 输入带：存放输入符号输入带

25、：存放输入符号 读头：可以在输入带上向后移动读头：可以在输入带上向后移动 有穷控制器：控制状态发生变化有穷控制器：控制状态发生变化如果读头移动到最后一个符号后面，如果读头移动到最后一个符号后面，状态正好是终结状态，则输入带上状态正好是终结状态，则输入带上的符号组成的字能被该有限自动机的符号组成的字能被该有限自动机所识别所识别Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春能接受偶数个能接受偶数个0和偶数个和偶数个1组成的串的有穷自动机。组成的串的有穷自动机。SABC11010010Principle of Comp

26、iling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春NFA的定义的定义一个非确定的有限自动机一个非确定的有限自动机(NFA) M是一个五元组：是一个五元组： NFA M=(S， ，s0，F ) 其中其中: :1.1.S为状态的有穷非空集为状态的有穷非空集；2.2.是有穷输入字母表；是有穷输入字母表；3.3.为一个为一个S * 到到S的子集的映射的子集的映射；4.4. s0 S是初始状态集是初始状态集；5.5.F S为终止状态集为终止状态集。Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院201

27、12011春春NFA映射的表示映射的表示直接给出直接给出状态转换矩阵状态转换矩阵状态转换图状态转换图Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春矩阵表示矩阵表示(S，0)=P (S，1)=S，Z(Z，0)=P(Z，1)=P(P，1)=Z状态状态 输入输入01SPS,ZPZZ*PPPrinciple of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春状态转换图状态转换图(S，0)=P (S，1)=S，Z(Z，0)=P(Z，1)=P(P，1)=ZSPZ00,

28、1111Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春NFA识别的字识别的字l对于对于*中的任何一个串中的任何一个串t，若存在一条从某一初态结点到，若存在一条从某一初态结点到某一终态结点的道路，且这条道路上所有弧的标记字依序某一终态结点的道路，且这条道路上所有弧的标记字依序连接成的串等于连接成的串等于t，则称，则称t可为可为NFA M所识别所识别(读出或接受读出或接受)。l若若M的某些结点既是初态结点又是终态结点；或者存在的某些结点既是初态结点又是终态结点；或者存在一条从某个初态结点到某个终态结点的道路一条从某个

29、初态结点到某个终态结点的道路,其上所有弧的其上所有弧的标记均为标记均为，那么空字，那么空字可为可为M所接受。所接受。lNFA M所能接受的符号串的全体记为所能接受的符号串的全体记为L(M)。Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春021ba,bab Sab0211(1,2)2*22Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春DFA 与与NFA的区别的区别: DFA是是NFA的特例。的特例。 对每个对每个NFA N存在着与之等

30、价的存在着与之等价的DFA M。DFA与与NFA的关系的关系DFA： S为状态的有穷非空集为状态的有穷非空集； 是有穷输入字母表；是有穷输入字母表； 为一个为一个S 到到S的单值的单值映射映射； s0 S是初始状态是初始状态； F S为终止状态集为终止状态集NFA： S为状态的有穷非空集为状态的有穷非空集； 是有穷输入字母表；是有穷输入字母表； 为一个为一个S * 到到S的子集的的子集的映射映射； s0 S是初始状态集是初始状态集； F S为终止状态集为终止状态集Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春解决

31、的问题解决的问题： 1. 初态集初态集 2. 输入字输入字 3. 弧弧 4. 转换的目标状态集转换的目标状态集Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春NFA的确定化的确定化1.增加状态增加状态X,使之成为新的唯一的初态。从使之成为新的唯一的初态。从X引引弧到原初态结点。弧到原初态结点。2.对状态图进一步进行如下形式的改变对状态图进一步进行如下形式的改变ijABikAjBijA|BiAjBijA*ikjAPrinciple of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学

32、院20112011春春例：例：(a|b)*(aa|bb)(a|b)*S S12Z(a|b)*(aa|bb)(a|b)*例：例：(a|b)*(aa|bb)(a|b)*SZ(a|b)*(aa|bb)(a|b)*(a|b)*(aa|bb)(a|b)*S312Z4ababaabbS312Z4aabba45abbPrinciple of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春 3.定义定义I I的的-闭包闭包-closure(I I)，v任何状态任何状态q I，则，则q -closure(I)；v任何状态任何状态q I，则，则q经任意条经任

33、意条 弧而能到达的状态的弧而能到达的状态的q -closure(I) 。例：例：I=1, -closure(I)=1,2； I=5, -closure(I)=5,6,2；12534687aaaNFA的确定化的确定化Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春12534687aaa定义状态集合定义状态集合I I的的a弧转换弧转换，I Ia = -closure(J J) ,其中其中J J是所有那是所有那些可从些可从I I中的某一状态经过一条中的某一状态经过一条a a弧而到达的状态的全体。弧而到达的状态的全体。Pr

34、inciple of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春确定化的算法确定化的算法v首先置该表的首行首列为首先置该表的首行首列为 : closure(X),X为开始结点。为开始结点。v对对 = a1ak, 构造一个构造一个k+1列的表。列的表。若某行的第一列的若某行的第一列的状态已确定为状态已确定为I I，则第，则第i+1(i = 1,2,k)列的值为列的值为I Iai，然后，然后检查该行上的所有状态子集，看它是否已在第一列出现。检查该行上的所有状态子集，看它是否已在第一列出现。若未出现，将其填加到后面的空行上。重复此过程，直若

35、未出现，将其填加到后面的空行上。重复此过程，直到所有状态子集均在第一列中出现。到所有状态子集均在第一列中出现。v得到一个确定的有限自动机：将每个状态子集视为新的得到一个确定的有限自动机：将每个状态子集视为新的状态，初态就是首行首列的状态，终态是含有原终态的状态，初态就是首行首列的状态，终态是含有原终态的集合。集合。Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春例子例子4f35621iaaaabbbbSABACBBADCCEDFDEFDFCEPrinciple of Compiling长春工业大学计算机科学与工程学

36、院长春工业大学计算机科学与工程学院20112011春春等价的等价的DFAaCDBAEFSbaaaaabbbbbabFPrinciple of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春小结小结DFA与与NFA的相关概念的相关概念DFA与与NFA的关系的关系重点：重点：DFA与与NFA定义及关系定义及关系难点：难点：NFA的确定化的确定化Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春正规表达式与正规表达式与FA的等价性的等价性正规表达式和有限自动机的表达能

37、力是相同的。具体表正规表达式和有限自动机的表达能力是相同的。具体表现在：现在： 给定一个正规表达式给定一个正规表达式R，可以构造出相应的有限自，可以构造出相应的有限自动机动机A。该自动机接受的符号串的集合恰巧是正规。该自动机接受的符号串的集合恰巧是正规表达式的值，即表达式的值，即L（R）=L（A） 给定一个有穷状态自动机给定一个有穷状态自动机A，可以构造出相应的正，可以构造出相应的正规表达式规表达式R。该正规表达式的值恰巧是该自动机接。该正规表达式的值恰巧是该自动机接受的符号串的集合，即受的符号串的集合，即L （ A ） =L（ R ）Principle of Compiling长春工业大学计

38、算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春从正规表达式到从正规表达式到FA具体步骤：对于任意的一个正则表达式具体步骤：对于任意的一个正则表达式e，从，从 e开始，按照变换规则，逐步扩弧、扩结，直到转换图上开始，按照变换规则，逐步扩弧、扩结，直到转换图上所有的弧上都是所有的弧上都是中的单个符号为止。中的单个符号为止。对于引入的每一个新状态，应该赋予一个独有的名字。对于引入的每一个新状态，应该赋予一个独有的名字。 Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春从正规表达式到从正规表达式到F

39、A的替换规则的替换规则替换规则：替换规则：sze1e2Ase1ze2sze1|e2Zse1e2sz e*szeAPrinciple of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春例子例子e = (A|B)（A|B|0|1)*sze1sAA|B2z(A|B|0|1)*BAsA3zA|B|0|1BPrinciple of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春例子例子a*|(a|b)a)*SZa*|(a|b)a)*SZa*(a|b)a)*SZa(a|b)aSZaa|baPr

40、inciple of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春NFA 到正规表达式到正规表达式1、转换图拓广，新设置一个唯一的开始状态、转换图拓广，新设置一个唯一的开始状态S和唯和唯一的终态一的终态Z，通过，通过弧连接到原弧连接到原FA。2、运用、运用替替换规则消弧消结点，直到只剩下开始状态换规则消弧消结点，直到只剩下开始状态和接受状态。此时，唯一的边上的标记就是所要和接受状态。此时，唯一的边上的标记就是所要的表达式。的表达式。SZ M Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科

41、学与工程学院20112011春春NFA 到正规表达式替换规则到正规表达式替换规则c.321R1R2R331R1R2*R3a.123R1R213R1R2b.12R1R221R1|R2Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春例：例： L(M)如右图：如右图：求正规式求正规式R，使，使L(R)=L(M).因此：因此：L(R)= (a|b)(a|b)*y(a|b)(a|b)*xya|ba|bx-+aba,b-+aba,bxyPrinciple of Compiling长春工业大学计算机科学与工程学院长春工业大学计算

42、机科学与工程学院20112011春春确定有穷自动机的化简确定有穷自动机的化简一个有穷自动机是化简了的，即是说：一个有穷自动机是化简了的，即是说： 它没有多余状态；它没有多余状态； 它的状态中没有两个是互相等价的。它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。态而转换成一个最小的与之等价的有穷自动机。所谓有穷自动机的所谓有穷自动机的多余状态多余状态，是指这样的状态：从自，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那动机的开始状态出发，任何输入串也不能到达的那

43、个状态；或者从这个状态没有通路到达终态。个状态；或者从这个状态没有通路到达终态。Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春确定有穷自动机的化简确定有穷自动机的化简一个有穷自动机是化简了的，即是说：一个有穷自动机是化简了的，即是说： 它没有多余状态；它没有多余状态； 它的状态中没有两个是互相等价的。它的状态中没有两个是互相等价的。状态状态S和和T等价的条件等价的条件 一致性条件一致性条件 状态状态S和和T必须同时为可接受状态或必须同时为可接受状态或不可接受状态。不可接受状态。 蔓延性条件蔓延性条件 对于所有输入

44、符号，状态对于所有输入符号，状态S和状态和状态T必须转换到等价的状态里。必须转换到等价的状态里。DFA的最小化的方法（分割法）的最小化的方法（分割法）方法：将方法：将DFA的状态分割成一些互不相交的子集。的状态分割成一些互不相交的子集。Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春分割法分割法DFA的最小化算法的核心 把一个把一个DFA的状态分成一些不相交的子集，使得任何不同的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个的两子集的状态都是可区别的，而同一子集中的任何两个

45、状态都是等价的状态都是等价的.算法：将所有状态分成两个子集将所有状态分成两个子集终态集终态集和和非终态集非终态集运用判定状态等价原则分别对两个子集的状态进行分析和运用判定状态等价原则分别对两个子集的状态进行分析和划分，把互相等价的状态构成一个子集，若发现不等价，划分，把互相等价的状态构成一个子集，若发现不等价，继续划分，这样继续划分，这样FA的状态被分成互不相交的若干子集。的状态被分成互不相交的若干子集。从每个子集中选出一个状态做代表，即可构成简化的从每个子集中选出一个状态做代表，即可构成简化的FAPrinciple of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科

46、学与工程学院20112011春春注意：注意：a a、由于一个子集中，各状态射出的弧均相同，故只需要将原、由于一个子集中，各状态射出的弧均相同，故只需要将原进入各子集中各状态的弧都改为进入所选的状态。进入各子集中各状态的弧都改为进入所选的状态。b b、含有原来初态的子集仍为初态，各终态的子集仍为终态、含有原来初态的子集仍为初态，各终态的子集仍为终态Principle of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春例：化简下图，使其最小化例：化简下图，使其最小化。CDBAEFSbaaaaabbbbbabFaPrinciple of Co

47、mpiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春DBASaaabbbbaCDBAEFSbaaaaaabbbbbba00: S,A,B C,D,E,F1:1: 2:2:aA，S,BbS,BS,A,BPrinciple of Compiling长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院20112011春春词法分析器生成工具词法分析器生成工具LexLex：Unix(Linux)系统的一个标准实用程序。系统的一个标准实用程序。词法分析器自动构造示意图词法分析器自动构造示意图Lex源文件源文件 （.l）Lex词法分析程序词法分析程序（lex.yy.c）输入的输入的Lex源文件（源文件（.l），主要定义了一些词法规则。），主要定义了一些词法规则。输出的词法分析程序输出的词法分析程序(lex.yy.c)，包含，包