词法分析课件

第三章词法分析词法分析的基本概念正规式自动机和状态图词法分析程序的设计1第三章词法分析词法分析的基本概念1学习目标:掌握：词法分析程序的构造，正规式和正规文法到有穷自动机的转换，NFA到DFA的转换、DFA的化简理解：正规文法、正规式、DFA的概念、NFA的概念了解：词法分析程序的自动构造工具2学习目标:2词法分析程序词法分析是编译过程中的一个阶段，在语法分析前进行，也可以和语法分析结合在一起作为一遍。输入：源程序字符串输出：单词符号（最基本的语法单位）3词法分析程序词法分析是编译过程中的一个阶段，在语法分析前进行词法分析程序的功能词法分析程序主要执行以下功能：读入源程序字符串，识别开具有独立含义的最小语法单位——单词（符号）；把单词变换成长度统一的且为定长的属性字；其他功能：滤掉空格，跳过注释、换行符某些预加工处理4词法分析程序的功能词法分析程序主要执行以下功能：4词法分析程序的实现方式相对独立方式：把词法分析程序作为语法分析程序的一个独立子程序。语法分析程序需要新符号时调用这个子程序。完全独立方式：词法分析程序作为单独一趟来实现。词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。5词法分析程序的实现方式相对独立方式：把词法分析程序作为语法分相对独立方式当采用递归下降分析等技术实现一趟编译程序时常采用这种方式。源程序词法分析程序语法分析程序Tokengettoken….6相对独立方式当采用递归下降分析等技术实现一趟编译程序时常采用完全独立方式采用词法分析工作完全独立的原因：简化设计，降低语法分析的复杂性提高编译效率增加编译系统的可移植性源程序词法分析程序语法分析程序属性字序列….7完全独立方式采用词法分析工作完全独立的原因：源程序词法分析程源程序的输入在内存开辟缓冲区，将程序文本放进该缓冲区预处理：删除无用字符等词法分析程序对缓冲区扫描时，设置两个指示器，一个指向当前正在识别的单词的开始位置，称为起始指针；另一个用于向前搜索，以寻找单词的终点，称为扫描指针。起始指针搜索指针8源程序的输入在内存开辟缓冲区，将程序文本放进该缓冲区起始指针扫描缓冲区的大小应当保证单词符号不被缓冲区的边界打断使用循环链表实现规定单词符号的大小不超过整个链表的容量9扫描缓冲区的大小9超前搜索词法分析程序在读取单词时，为了判断是否已读入整个单词的全部字符，常采取向前多读取字符并通过读取的字符来判别，即所谓超前搜索技术。10超前搜索词法分析程序在读取单词时，为了判断是否已读入整个单词单词符号的构成规则

——标识符012字母(a-z)字母或数字(a-z0-9)其它*此时，超前搜索了一个字符11单词符号的构成规则

——标识符012字母(a-z)字母或数字词法分析程序输出单词的形式词法分析程序输出的单词符号通常用二元式表示：（单词类别，单词自身的值）单词类别：表示单词种类，常用整数编码，它是语法分析需要的单词自身的值：是编译中其他阶段所需要的信息如果一个种别只含一个单词符号，那么该单词符号的类别编码就完全代表它自身的值。把单词符号存储在符号表中。不同种类的单词符号可能具有不同类型的属性。可以用不同种类的符号表实现。如果一个种别含有多个单词符号，那么还应给出该单词符号的自身值：标识符自身值是标识符自身的字符串；常数自身值是常数的二进制数值。12词法分析程序输出单词的形式词法分析程序输出的单词符号通常用二语言的单词符号单词符号是程序语言的基本语法单位，一般分为下面5种：关键字（基本字）：（个数确定，可全体编为一类，也可一字一类)标识符：（个数不确定，作为一类）常数：各种类型的常数。(个数不确定，按类型分类)运算符：如+、-、*、/、<等。(个数确定，一符一类)界符：如，、；、（、）、:等。(个数确定,一符一类)注意：一种语言的单词如何分类、怎样编码，主要取决于技术上的方便。13语言的单词符号单词符号是程序语言的基本语法单位，一般分为下面举例例如：程序段if(a>1)b=10;假定基本字、运算符、界符都是一符一种。

它所输出的单词符号是：(2,)基本字if(29,)左括号((10,’a’)标识符a(23,)大于号>(11,’1’的二进制)常数1

(30,)

右括号)(10,’b’)标识符b(17,)赋值号=(11,’10’的二进制)常数10(26,)分号；14举例例如：程序段它所输出的单词符号是：14正规式和有限自动机1515正规表达式和有限自动机

——学习目的和内容用正则表达式描述词法规则构造正则表达式等价的NFA构造NFA等价的DFA化简DFA根据DFA编写程序，实现词法分析器提示：本部分内容占学习内容的25%，考核内容的1/2与本部分相关16正规表达式和有限自动机

——学习目的和内容用正则表达式描述词单词的描述工具作用:描述单词的构成规则,基于这类描述工具建立词法分析技术,进而实现词法分析程序的自动构造.工具有:正规文法 正规式(RegularExpression)17单词的描述工具作用:描述单词的构成规则,基于这类描述工具建正规文法

多数程序设计语言单词的语法都能用正规文法(3型文法)描述正规文法回顾 文法的任一产生式α→β的形式都为A→aB或A→a，其中A，B∈VN，a∈VT。 正规文法描述的是VT*上的正规集18正规文法 多数程序设计语言单词的语法都能用正规文法(3型文法例如: 用l表示a~z中的任一英文字母，d表示0~9中任一数字描述标识符的正规文法为 <标识符>→l｜l<字母数字> <字母数字>→l｜d｜l<字母数字>｜d<字母数字>描述无符号整数的正规文法 <无符号整数>→d｜d<无符号整数>19例如:19为什么要引进正则表达式？对于字母表∑，我们感兴趣的是它的一些特殊字集－正规集。正规集是字母表Σ上的符合一定规则的符号串构成的集合正则表达式是一种适合描述符号的表示法，可由它定义正规集。20为什么要引进正则表达式？对于字母表∑，我们感兴趣的是它的一些正规式(regularexpression)定义（正规式和它所表示的正规集）：设字母标为

1和都是上的正规式，它们所表示的正规集分别为{}和；2任何a，a是上的一个正规式，它所表示的正规集为{a}；3假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1

也都是正规式,它们所表示的正规集分别为L(e1),L(e1)∪L(e2),L(e1)L(e2)和(L(e1))

。（递归）4仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。21正规式(regularexpression)定义（正规式和(e1),e1e2,e1e2,e1

L(e1),L(e1)∪L(e2),L(e1)L(e2)和(L(e1))

。

其中的“”读为“或”（也有使用“+”代替“”的）；“

”读为“连接”；“

”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“

”、“

”、“”。连接符“

”一般可省略不写。“

”、“

”和“”都是左结合的。22(e1),e1e2,e1e2,e1正则集正则集定义:正则表达式e的值是字母表上的正则集，记作|e|||=||={}|a|={a}|(e)|=|e||e1e2|=|e1||e2|={xy|x|e1|且y|e2|}

|e1|e2|=|e1||e2|={x|x|e1|或x|e2|}

|{e}|=|e|*(e的闭包)例：(0|1){0|1}的值为：一切只包含0与1的任意序列组成的正则集（二进制数集合）23正则集正则集定义:正则表达式e的值是字母表上的正则集，记作举例例:

2={A,B,0,1},则(A|B){A|B|0|1}5是2上的正则表达式(A|B){A|B|0|1}5的值，即|(A|B){A|B|0|1}5|，是这样一个正则集，每个字符串都是以字母A或B打头，后跟以至多5个字母（A或B）或数字（0或1）(0|1)(0|1)*∑上的“数”的全体24举例例:2={A,B,0,1},则24例令={a，b}，上的正规式和相应的正规集的例子有：正规式 正规集a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a

{,a,a,……任意个a的串}(ab)

{,a,b,aa,ab……所有由a 和b组成的串}(ab)

(aabb)(ab)

{

上所有含有两个相继 的a或两个相继的b组成 的串}25例令={a，b}，上的正规式和相应的正规集的例子有例={l，d}，r=l(ld)

定义的正规集:{l,ll,ld,ldd,……}（标识符）例={d，.，e，+，-},则上的正规式d

(.dd

)(e(+-)dd

)表示的是无符号数的集合。其中d为0~9的数字。26例={l，d}，r=l(ld)定义的正规集:两个正规式等价若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。例如：e1=(ab)，e2=ba又如：b(ab)

=(ba)

b

(ab)

=(a

b

)

27两个正规式等价若两个正规式e1和e2所表示的正规集相同,则说正规式的运算律设r,s,t为正规式，正规式服从的代数规律有：1。rs=sr “或”服从交换律2。r(st)=(rs)t “或”的可结合律3。(rs)t=r(st) “连接”的可结合律4。r(st)=rsrt (st)r=srtr 分配律5。r=r,r=r 是“连接”的恒等元素6。rr=r r

=rrr… “或”的抽取律

28正规式的运算律设r,s,t为正规式，正规式服从的代数规律有：程序中的单词都能用正规式来定义令l为a~z的字母，d为0~9的数字e1=l(l|d)* e1表示标识符集合e2=dd* e2表示无符号整数注(比较)： <标识符>→l｜l<字母数字><字母数字>→l｜d｜l<字母数字>｜d<字母数字> 正规式比正规文法更容易让人理解单词是按怎样的规律构成的，且可以从某个正规式自动地构造识别程序。29程序中的单词都能用正规式来定义29正规文法和正规式间的转换等价性：对任意一个正规文法，存在一个定义同一语言的正规式对任意一个正规式，存在一个定义同一语言的正规文法30正规文法和正规式间的转换等价性：30将∑上的一个正规式r转换成文法G=(VN,VT,S,P)VT=∑,首先形成产生式S→r,S为G的开始符不断利用下面的规则做变换,直到每个产生式最多含有一个终结符为止原产生式变换后产生式规则1A→xyA→xBB→y规则2A→x*yA→xAA→y规则3A→x|yA→xA→y其中B为一新非终结符31将∑上的一个正规式r转换成文法G=(VN,VT,S,P)原产例:将R=a(a|d)*转换成相应的正则文法令转换成文法G=(VN,VT,P,S)其中VT={a,d}，文法开始符为S首先形成S→a(a|d)*,然后变换S→aA A→(a|d)*A→(a|d)AA→εA→aAA→dA 最终有产生式：S→aA，A→ε，A→aA， A→dA32例:将R=a(a|d)*转换成相应的正则文法A→(a|d)将正规文法转换成正规式将每条产生式改写为正规式用代入法解正规式方程组最后只剩下一个开始符号定义的正规式,其中不含非终结符正规文法到正规式的转换规则:文法产生式正规式规则1A→xBB→yA=xy规则2A→xA|yA=x*y规则3A→xA→yA=x|y33将正规文法转换成正规式文法产生式正规式规则1A→xBB→例：将文法G[S]转换成正规式G：S→aA|aA→dA|d先由产生式得: S=aA|a A=d*d将A代入S中得: S=ad*d|a利用正规式变换得 S=a(d*d|ε)=ad*说明:d*d|ε =(ε|d|dd|…)d|ε =d|dd|…|ε=d* 所求正规式为ad*34例：将文法G[S]转换成正规式34有穷自动机（FiniteAutomata）状态转换图确定有穷状态自动机（DFA）非确定有穷状态自动机（NFA）把NFA变为DFADFA的化简35状态转换图35状态转换图（TransitionDiagram）为了识别正则文法的句子而专门设计的有向图。如：C语言中关于标识符定义的规则（词法规则）如下：<标识符>::=字母|<标识符>字母|<标识符>数字则识别标识符的状态（转换）图：SIE字母数字字母或数字状态都是非终结符号S：开始状态E：终止状态，用双圈表示I：标识符状态36状态转换图（TransitionDiagram）为了识别正状态转换图——概念1有限方向图结点表示状态有一个起始状态，初态至少有一个终止状态，终态。用双圆圈表示状态的数量有限状态之间用有方向的边——箭头相连箭头上有标记37状态转换图——概念1有限方向图37状态转换图——概念2当前状态箭头的起始结点目的状态箭头的终点箭头上的标记当前状态允许输入字符或一类字符从当前状态通过输入箭头上的标记到达目的状态38状态转换图——概念2当前状态38voidstate0(buffer&aBuf,token&aToken){charaChar=aBuf.getChar();if(aChar<=‘z’)&&(aChar>=‘a’){aToken.val.append(aChar);state1(aBuf,aToken);}elseaToken.type=token.error;}39voidstate0(buffer&aBuf,tvoidstate1(buffer&aBuf,token&aToken){charaChar=aBuf.getChar();while((aChar<=‘z’)&&(aChar>=‘a’)||(aChar<=‘9’)&&(aChar>=‘0’)){aChar=aBuf.getChar();aToken.val.append(aChar);}state2(aBuf,aToken);}40voidstate1(buffer&aBuf,tvoidstate2(buffer&aBuf,token&aToken){aBuf.goBack(1);aToken.val.removeTail(1);aToken.type=token.identifier;}

41voidstate2(buffer&aBuf,to如何为正则文法构造状态转换图？什么是正则文法？（U::=a或U::=aB）步骤如下：以S为开始状态作结点；把文法中的每一个非终结符号作为状态结点；对于形如Q::=a的每个规则，引一条开始状态S到状态Q的弧，弧上标记为a；对于形如Q::=aB的规则引一条从状态a到Q的弧，弧上标记为B，其中a为非终结符号，B为终结符号。以识别符号为终止状态。42如何为正则文法构造状态转换图？什么是正则文法？（U::=a构造状态转换图举例例如：对于正则文法G[Z]：Z::=Za|Aa|BbA::=Ba|aB::=Ab|bSABabSABaZZaSABabZbaabaaaba(1)(2)(3)43构造状态转换图举例例如：对于正则文法G[Z]：SABabSA如何应用状态转换图识别句子？如果x是相应文法的句子便必须能从开始状态出发，顺着弧的方向行进到终止状态。其步骤如下:(1)从开始状态开始，以它作为当前状态，并从x的最左字符开始重复步骤2，直到到达x的右端为止；(2)扫描x的下一字符，在当前状态射出的各个弧中找出标记有该字符的弧，并沿此弧前进，以达到的状态作为下一当前状态。步骤2存在的两种可能：可能找不到一条弧的标记与当前字符相同；总能找到一个弧，其标记与当前字符相同。44如何应用状态转换图识别句子？如果x是相应文法的句子便必须能从应用状态转换图识别句子举例例如：对于正则文法G[Z]：Z::=Za|Aa|BbA::=Ba|aB::=Ab|babSABabZbaaabSABabZbaa(1)识别字符串ababaaaFba,b(2)识别字符串bababbb45应用状态转换图识别句子举例例如：对于正则文法G[Z]：abS状态转换图识别句子的实质是一个规约过程，运用自底向上的识别算法：如：SA与AZ表示：a直接规约为A，Aa直接规约为Z。从开始状态S出发逐步到达终止状态Z的过程，也是从终结符号串出发，规约到非终结符号的过程。46状态转换图识别句子的实质是一个规约过程，运用自底向上的识别算对句子ababaaa的分析步骤当前状态输入的其余部分SababaaaAbabaaaBabaaaAbaaaBaaaAaaZaZababaaaABABAZZ(a)分析过程(b)语法树47对句子ababaaa的分析步骤当前状态输入的其余状态转换图的实现1每个状态对应一个子程序当前结点的输出边的目的结点不是当前结点——不含有直接回路用嵌套的条件语句实现当前结点的输出边的目的结点是当前结点——含有直接回路用循环语句实现48状态转换图的实现1每个状态对应一个子程序48状态转换图的实现2终态结点用返回语句实现返回单词符号的种类和属性值带有*的结点为进行了超前搜索的结点。需要把扫描位置退回超前搜索字符的个数49状态转换图的实现2终态结点用返回语句实现49什么是转换系统？转换系统对于从正则表达式转换到状态转换图起到了中间表示的作用。定义：转换系统是具有下列三个特征的状态转换图，即1)开始状态S和终止状态Z唯一;2)无弧进入S，也无弧自Z射出；3)可能存在标记为空串（ε）的弧。转换系统与状态转换图的区别：ε弧SS1S2ZεεAZ2Z1εε50什么是转换系统？转换系统对于从正则表达式转换到状态转换图起到词法规则的描述状态转换图难于书写，非线性结构更好的方式的要求线性方式表达与状态转换图等价正规表达式[a-z][a-z0-9]*51词法规则的描述状态转换图51有穷自动机(也称有限自动机)是一种识别装置作用:能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合意义:为词法分析程序的自动构造寻找特殊的方法和工具。分类:

确定的有穷自动机

(DeterministicFiniteAutomata)

不确定的有穷自动机

(NondeterministicFiniteAutomata)52有穷自动机(也称有限自动机)是一种识别装置52确定型有穷状态自动机一个确定的有穷自动机（DFA）D是一个五元组：D=（K，Σ，f，S，Z）其中K：有穷非空的状态集合；Σ：有穷非空的输入符号字母表；f：转换函数，是在K×Σ→K上的映像，即，如f（ki，a）=kj，（ki∈K，kj∈K）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；S∈K是唯一的一个初态；Z_K是非空的终态集合。“确定”即状态转换函数是单值函数！53确定型有穷状态自动机一个确定的有穷自动机（DFA）D是一个五从状态转换图构造有穷状态自动机例如：从下面状态图构造DFADFAD=（{S，Z，A，B}，{a，b}，M，S，{Z}）其中M定义为：M（S，a）=AM（S，b）=BM（A，a）=ZM（A，b）=BM（B，a）=AM（B，b）=Z M（Z，a）=Z abSABabZbaa54从状态转换图构造有穷状态自动机例如：从下面状态图构造DFAa运行DFA与识别一个字符串定义：对于某DFAD=（K,Σ,M,S,F），如果M(S，t)=P,P∈F，则称符号串t可被DFAD所接受。运行一个DFA的过程：识别一个符号串是否被接受55运行DFA与识别一个字符串定义：对于某DFAD=（K,Σ举例如前例：DFAD=（{S，Z，A，B}，{a，b}，M，S，{Z}）M（S，a）=AM（S，b）=BM（A，a）=ZM（A，b）=BM（B，a）=AM（B，b）=Z M（Z，a）=Z 则：M(S,ababaa)=M(M(S,a),babaa)=M(A,babaa)=M(M(A,b),abaa)=M(B,abaa)=M(A,baa)=M(B,aa)=M(A,a)=Z56举例如前例：DFAD=（{S，Z，A，B}，{a，b}正则集正则集：L(D)，是一个DFA接受的字符串集合正则语言与正则集：L(G)=L(D)最小状态自动机：状态个数最少，唯一57正则集正则集：L(D)，是一个DFA接受的字符串集合57如何在计算机内表示映像？映像M：含义？映像在计算机内的表示法：矩阵表示法表结构表示法DFA的确定性体现在δ是一个从SXΣ到S的单值部分映射也即使状态的转换是确定的，是单值映射58如何在计算机内表示映像？映像M：含义？58DFA的矩阵表示法字符状态abSABabZbaa矩阵行代表状态，列代表输入字符，矩阵元素是映像得到的新状态。59DFA的矩阵表示法字符状态abSABabZbaa矩阵行代表表结构表示法状态名射出的弧数标记1指向的下一状态1…标记K指向的下一状态k对每一个状态结点而言若某结点有K个射出的弧，则相应表长为2k+260表结构表示法状态名射出的弧数标记1指向的下一状态1…标记K指非确定有穷状态自动机的引入M(R,T)是K×Σ到K的单值函数，即唯一确定下一状态如果在当前状态下，同一个输入字符确定的下一状态不止一个呢？如V::=UTW::=UTUWVTTabSABabZbaaaa例如：文法G3.2:Z::=Za|Aa|BbA::=Ba|Za|aB::=Ab|Ba|b61非确定有穷状态自动机的引入M(R,T)是K×Σ到K的单值函数非确定有穷状态自动机一个非确定的有穷自动机（NFA）D是一个五元组：N=（K，Σ，M，S，F）其中K：有穷非空的状态集合；Σ：有穷非空的输入字母表；M：转换函数，是在K×Σ到K的子集所组成集合的映像，M(R,T)={Q1,Q2,….Qn}S=K是非空的初态集合；F=K是非空的终态集合.62非确定有穷状态自动机一个非确定的有穷自动机（NFA）D是一个DFA与NFA的区别DFANFA开始状态唯一一个或多个映像单个状态状态集合63DFA与NFA的区别DFANFA开始状态唯一一个或多个映像单举例前述文法G3.2对应的自动机NFAN=({S,A,B,Z},{a,b},M,{S},{Z})其中M：M(S,a)={A}M(S,b)={B}M(A,a)={Z}M(A,b)={B}M(B,a)={A,B}M(B,b)={Z}M(Z,a)={A,Z}abSABabZbaaaa64举例前述文法G3.2对应的自动机NFAN=({S,A,B,举例(字符串被NFA所接受)对于输入字符串babbabb，运行G3.2的NFA步骤当前状态输入的其余部分可能的后继选择1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZ65举例(字符串被NFA所接受)对于输入字符串babbabb，运运行NFA运行NFA：识别一个字符串是否被NFA所接受，是否能达到终态集合中的某个状态实质：用自底向上方法识别句子状态转换的下一状态不唯一，如何解决？66运行NFA运行NFA：识别一个字符串是否被NFA所接受，是否DFA和NFA的关系对于Σ*上的字符串β，如果存在一条从初态到终态的通路，且这条通路上的输入字符恰好连接成β，称为β可以此DFA、NFA识别DFA、NFA都可以识别一个字符集Σ上的字符串可以用DFA、NFA定义Σ上的字符串的集合DFA都是NFA、NFA可化为等价的DFA67DFA和NFA的关系对于Σ*上的字符串β，如果存在一条从初态构造与正规式等价的NFA方法XYααα|β12αβ1268构造与正规式等价的NFA方法XYααα|β12αβ12683αεε1αβ32αβ1221α*12693αεε1αβ32αβ1221α*1269构造与正规式等价的NFA示例a(a|b)*XYa(a|b)*XYa1(a|b)*70构造与正规式等价的NFA示例a(a|b)*XYa(a|b)XYa1(a|b)2XYa1a2bεεεε71XYa1(a|b)2XYa1a2bεεεε71NFA的确定化方法初态的唯一化终态的唯一化从初态开始，求对于每个输入符号的后继状态集合Si——新的状态对每个Si，求对于每个输入符号的后继状态集合Si+1直到不产生新的后继状态集合含有终态的状态集合为终态72NFA的确定化方法初态的唯一化72NFA的确定化示例状态转换矩阵 a bX{1,2,Y} {}1{2,Y} {2,Y}2{2,Y} {2,Y}Y{} {}XYa1a2bεε73NFA的确定化示例状态转换矩阵 a bXYa1a2bεε73 a bX{1,2,Y} {}1{2,Y} {2,Y}2{2,Y} {2,Y}Y{} {} a b{X} {1,2,Y}{} {1,2,Y}{2,Y}{2,Y}{2,Y} {2,Y}{2,Y}NFA状态转换矩阵1)(2)(3) a b1) (2) (2) (3) (3)(3) (3) (3)等价的DFA状态转换矩阵74 a b a bNFA状态转换矩阵1) a b等价的 a b1) (2) (2) (3) (3)(3) (3) (3)13aabab275 a b13aabab275ε闭包状态集I的ε_CLOSURE(I)如果q属于Iq属于ε_CLOSURE(I)从q出发经任意条ε弧到达的任何状态q’都属于ε_CLOSURE(I)76ε闭包状态集I的ε_CLOSURE(I)76DFA的化简状态的等价性能够识别相同的字符串划分为终态和非终态两个子集如果某个子集中的状态是可区分的，则进一步划分这个子集直到在每个子集内，各个状态都是不可区分的。同一子集内的状态合并。77DFA的化简状态的等价性77DFA的化简示例 a b1) 2) 2) (3) (3)(3) (3) (3)划分1：{1},{2，3}{2,3}a={3}属于{2,3}{2,3}b={3}属于{2,3}状态2、3不可区分，应简化为{1,2}78DFA的化简示例 a b划分1：{1},{2，3}7813aabab21a2ab化简前的DFA化简后的DFA7913aabab21a2ab化简前的DFA化简后的DFA79练习字母表{a,b}上所有含有aa或bb的字符串组成的集合用正规式表达为(a|b)*(aa|bb)(a|b)*80练习字母表{a,b}上所有含有aa或bb的字符串组成的集合8(a|b)*(aa|bb)(a|b)*0Y(a|b)*(aa|bb)(a|b)*1Y(aa|bb)(a|b)*0(a|b)*1Y(a|b)*0(a|b)*2(aa|bb)81(a|b)*(aa|bb)(a|b)*0Y(a|b)*(aa1Y(a|b)*0a2(aa|bb)3bεε1Y(a|b)*0a2aa3bεεbb821Y(a|b)*0a2(aa|bb)3bεε1Y(a|b)*1Y(a|b)*0a2a3bεεb45ab831Y(a|b)*0a2a3bεεb45ab831Y0a2a3bεεb45ab6baεε841Y0a2a3bεεb45ab6baεε84状态转换矩阵

a b{X,3,1} {3,1,4} {3,1,5}{3,1,4} {3,1,4,2,6,Y} {3,1,5}{3,1,5} {3,1,4} {3,1,5,2,6,Y}{3,1,4,2,6,Y} {3,1,4,2,6,Y} {3,1,5,6,Y}{3,1,5,2,6,Y} {3,1,4,6,Y} {3,1,5,2,6,Y}{3,1,5,6,Y} {3,1,4,6,Y} {3,1,5,2,6,Y}{3,1,4,6,Y} {3,1,4,2,6,Y} {3,1,5,6,Y}85状态转换矩阵 a b85状态转换矩阵

a b0 1 21 3 22 1 43） 3 54） 6 45） 6 46） 3 586状态转换矩阵 a b86DFA的最小化一定可以区分的两个集合用e表示出错状态非终止状态集{0,1,2}——不认识ε终止状态集{3,4,5,6}——认识ε{0,1,2}中δ(0,a)=1,δ(1,a)=3,δ(2,a)=1{0,2}与{1}不同，可区分{0,2}中δ(0,b)=2,δ(2,b)=4{0}与{2}不同，可区分{3,4,5,6}a={3,6},{3,4,5,6}b={4,5}{3,4,5,6}内不可区分87DFA的最小化一定可以区分的两个集合87最小化的DFA a b0 1 21 3 22 1 33 3 3 88最小化的DFA a b88词法分析程序的实现词法分析程序的构造方法词法分析程序的编写89词法分析程序的实现89构造词法分析程序的方法用手工方式，即根据识别语言单词的状态转换图，使用某种高级语言，例如，C语言直接编写词法分析程序。利用自动生成工具LEX自动生成词法分析程序。90构造词法分析程序的方法用手工方式，即根据识别语言单词的状态转词法分析程序实现中

要考虑的问题确定实现词法分析程序的执行方式确定属性字的结构缓冲区预处理，超前搜索,关键字的处理，符号表的实现查找效率，算法的优化实现词法错误处理91词法分析程序实现中

要考虑的问题确定实现词法分析程序的执行方属性字词法分析程序对说明部分不做语义处理。词法分析程序输出属性字一般采用下面的形式：（符号类，符号值）属性字是符号的机内表示，有统一固定的长度92属性字词法分析程序对说明部分不做语义处理。92关键字的识别与查表算法对于关键字，先把它们当成标识符，然后去查关键字表。若在表中查到，则为关键字，获取相应的类别码；否则，认为是标识符。查找算法：线性查找折半查找Hash函数93关键字的识别与查表算法对于关键字，先把它们当成标识符，然后去出错处理对定义外的（如，对首字符不是字母的，不是数字的，不是运算符和分界符的）单词进行出错处理。94出错处理对定义外的（如，对首字符不是字母的，不是数字的，不是词法分析中使用的数据字符表：（字母表）列出源程序中所有可能的字符。特定符号与机内表示表：一切特定符号与相应编码。标识符表：登录一切源程序中出现的一切标识符。此表的序号作为属性字的值。常数表：登录一切源程序中出现的常数。此表的序号作为属性字的值。95词法分析中使用的数据字符表：（字母表）列出源程序中所有可能的使用状态图设计词法分析程序多数语言的词法规则可用正则文法和正则表达式来描述。正则文法或正则表达式定义的语言都可以被状态图识别。使用状态图设计词法分析程序的步骤如下：对程序设计语言的单词按类构造相应的状态图。（这里把关键字与标识符作为一类）合并各类单词的状态图，增加一个出错处理终态，构成一个识别该语言所有单词的状态转换图对状态图的每一个终点编一段相应的子程序。96使用状态图设计词法分析程序多数语言的词法规则可用正则文法和正201字母字母|数字其它3456数字数字其它+-78*/9101113<=>:;1617其它13=举例97201字母字母|数字其它3456数字数字其它+-78*/91词法分析程序的结构取字符子程序取符号子程序，一般有如下约定：进入子程序时，已经取到当前符号的一个字符。离开子程序时，已经取到其后继字符。查造标识符表子程序查造常量表子程序查符号机内表示对照表子程序98词法分析程序的结构取字符子程序98词法分析程序的自动生成（Lex)LEX是由美国Bell实验室的M.Lesk和Schmidt于1975年用C语言研制的一个词法分析程序的自动生成工具。对任何高级程序语言，用户必须用正规表达式描述该语言的各个词法类（这一描述称为LEX的源程序），LEX就可以自动生成该语言的词法分析程序。LEX及其编译系统的作用如图。99词法分析程序的自动生成（Lex)LEX是由美国Bell实验图LEX及其编译系统的作用100图LEX及其编译系统的作用100一个LEX源程序由用“%%”分隔的三部分组成：第一部分为正规式的辅助定义式，第二部分为识别规则，最后一部分为用户子程序。其书写格式为：辅助定义式%%识别规则%%用户子程序101一个LEX源程序由用“%%”分隔的三部分组其中，辅助定义式和用户子程序是任选的，而识别规则是必需的。如果用户子程序缺省，则第二个分隔符号“%%”可以省去；但如果无辅助定义式部分，第一个分隔符号“%%”不能省去，因为第一个分隔符号用于指示识别规则部分的开始。102其中，辅助定义式和用户子程序是任选的下面给出一个简单语言的单词符号的LEX源程序例子，其输出单词的类别编码用整数编码表示。AuxiliaryDefinitions /*辅助定义*/letter→A∣B∣C∣…∣Z∣a∣b∣c∣…∣zdigit→0∣1∣2∣3∣…∣9%%RecognitionRules /*识别规则*/103下面给出一个简单语言的单词符号的LEX源程1while {return(1,null)}2do {return(2,null)}3if {return(3,null)}4else {return(4,null)}5switch {return(5,null)}6{ {return(6,null)}7} {return(7,null)}8( {return(8,null)}9) {return(9,null)}10+ {return(10,null)}11− {return(11,null)}1041while {ret12* {return(12,null)}13/ {return(13,null)}14= {return(14,null)}15； {return(15,null)}16letter(letter∣digit)*{if(keyword(id)==0){return(16,null)；return(id)};elsereturn(keyword(id))}17digit(digit)* {val=int(id)； return(17,null)； return(val)}10512* {retu18（letter∣digit∣{∣}∣(∣)∣+∣−∣*∣/∣=∣；）* {return(18，null)；inslit(id)； return(pointer，lenth)}该LEX源程序中用户子程序为空；其中识别规则{A18}语句中调用过程“inslit(id)”是将字符串常量id存放到字符表中，“pointer”中存放该串的起始位置，“lenth”存放该串的长度。10618（letter∣digit∣{∣}∣(∣LEX可以用两种方式来使用：一种是将LEX作为一个单独的工具，用以生成所需的识别程序；另一种是将LEX和语法分析器自动生成工具（如YACC）结合起来使用，以生成一个编译程序的扫描器和语法分析器。107LEX可以用两种方式来使用：一种是主线：两个工具：正规文法和正规式一个识别系统：有穷自动机词法分析程序的设计

本章小结108主线：本章小结108自动机、正则文法、正则表达式

的相互转化正则文法NFA正则表达式123456DFA最小化109自动机、正则文法、正则表达式

的相互转化正则文法NFA正则表主要内容词法分析的功能单词的种类及词法分析程序的输出形式正则文法和状态图★★★正则表达式与有穷自动机★★★

词法分析程序110主要内容词法分析的功能110基本要求了解词法分析程序的功能和实质。明确DFA与NFA的区别，掌握把NFA变为DFA的方法；熟练掌握把正则文法变为状态转换图以及写出有穷状态自动机的方法。掌握词法分析程序的基本实现方法。111基本要求了解词法分析程序的功能和实质。111作业第1题:构造正规式相应的最小化的DFA：1(0|1)*101

第2题:给出下述文法所对应的正则式：S→0A|1B,A→1S|1,B→0S|0第3题:构造正规式相应的最小化DFA：b*abb*(abb*)*112作业第1题:构造正规式相应的最小化的DFA：1(0|1一个简单的词法分析器示例1C语言子集的单词符号表示一个非常重要的事实是：大多数程序语言的单词符号都可以用状态转换图予以识别。作为一个综合例子，我们来构造一个C语言子集的简单词法分析器。表1列出了这个C语言子集的所有单词符号以及它们的种别编码和内码值。由于直接使用整数编码不利于记忆，故该例中用一些特殊符号来表示种别编码。113一个简单的词法分析器示例1C语言子集的单词符号表示11表1C语言子集的单词符号及内码值单词符号种别编码助记符内码值while1while—if2if—else3else—switch4switch—case5case—标识符6idid在符号表中的位置常数7numnum在常数表中的位置+8+—−9−—*10*—<=11relopLE<11relopLT==11relopEQ=12=—；13；—114表1C语言子集的单词符号及内码值while1while2C语言子集对应的状态转换图在设计的状态转换图中，首先对输入串做预处理，即剔除多余的空白符（在实际的词法分析中，预处理还包括剔除注释和制表换行符等编辑性字符的工作），使词法分析工作既简单又清晰。其次，将保留字作为一类特殊的标识符来处理，也即对保留字不专设对应的状态转换图，当转换图识别出一个标识符时就去查对表1的前五项，确定它是否为一个保留字。当然，也可以专设一个保留字表来进行处理。图5就是对应表1这个简单词法分析的状态转换图。

1152C语言子集对应的状态转换图115图5简单词法分析的状态