第03章有限自动机和词法分析精.ppt

《第03章有限自动机和词法分析精.ppt》由会员分享，可在线阅读，更多相关《第03章有限自动机和词法分析精.ppt（93页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第03章有限自动机和词法分析第1页，本讲稿共93页3.1词法分析词法分析有关词法分析器的几个问题和处理方法：有关词法分析器的几个问题和处理方法：1)1)词法分析器的功能、分类词法分析器的功能、分类 2)2)单词的分类、单词的分类、TokenToken表示表示 3)3)字符串、保留字的处理字符串、保留字的处理 4)4)空格符、制表符和换行符空格符、制表符和换行符 5)5)复合型符号复合型符号 6)6)括号类匹配预检括号类匹配预检7)7)词法错误校正词法错误校正8)8)词法分析独立化的意义词法分析独立化的意义第2页，本讲稿共93页3.1.1 3.1.1 词法分析器的功能词法分析器的功能词法分析器功

2、能：词法分析器功能：读源程序的字符序列，逐个读源程序的字符序列，逐个拼出单词拼出单词,并构并构造相应的造相应的内部表示内部表示TOKENTOKEN。同时。同时检查检查源程序中源程序中的的词法错误词法错误。引入引入TokenToken的原因：的原因：编译程序总是用某种程序语言书写的程序，编译程序总是用某种程序语言书写的程序，语言的操作对象只能是该语言规定的各种数据。语言的操作对象只能是该语言规定的各种数据。而编译程序的而编译程序的操作对象操作对象是程序中的各种是程序中的各种语法单语法单位位，因此，必须把它们表示成某种数据结构形，因此，必须把它们表示成某种数据结构形式。式。第3页，本讲稿共93页词

3、法分析器的两种形式词法分析器的两种形式:CharList 独 立词法分析器语法分析TokenList 附 属词法分析器语法分析callTokenCharList第4页，本讲稿共93页3.1.2 3.1.2 单词的内部表示单词的内部表示 TokenToken定义：定义：TokenToken表示最小的语义单位表示最小的语义单位-单词的信息单词的信息。即：即：单词单词内部表示的数据结构形式内部表示的数据结构形式。单词不是程序设计语言中的语法概念，是编译程序中单词不是程序设计语言中的语法概念，是编译程序中引进的一个概念。是最小的语义单位，不能分割。引进的一个概念。是最小的语义单位，不能分割。Token

4、Token中需要记录有关单词的信息：中需要记录有关单词的信息：单词的单词的类别码类别码(Token.class)Token.class)：标识单词的种类：标识单词的种类-词法词法信息信息 单词的单词的特征属性特征属性（Token.semanToken.seman，标识符名，符号表地，标识符名，符号表地址等）：址等）：-语义信息语义信息第5页，本讲稿共93页Token设计示例设计示例程序表示ASCToken.classToken.semanIf9666019666Then478656E602478656E6Begin26567696E60326567696E6End56E6460456E646+

5、B205B2(820682第6页，本讲稿共93页单词的分类单词的分类:标识符：标识符：字母打头的字母字母打头的字母/数字串数字串整常数：整常数：数字打头的数字串数字打头的数字串实常数：实常数：整数整数.整数整数保留字：保留字：beginbegin，endend，varvar，readread，writewrite，integerinteger，realreal符号符号 ：+，*，(，)，:，:=:=，;控制控制 ：(换行符）换行符）第7页，本讲稿共93页v字符串字符串：标识符的语义信息的表示方法有两种标识符的语义信息的表示方法有两种：a a 字符数组法：字符串空间字符数组法：字符串空间中的地址

6、被表示为对偶地址（中的地址被表示为对偶地址（head,lenghead,leng），如下图所示：），如下图所示：b 指针数组法：字符串空间中的地址用指针表示，如下图所示：(4,3)(2,2)x 1 z 1 2名表“x1”“z12”h e i g h t eofa g e eofx 1 eofy eof0123第8页，本讲稿共93页v保留字的处理保留字的处理：两种识别保留字的方法：两种识别保留字的方法：1.1.建立保留字表：顺序、散列、散列顺序建立保留字表：顺序、散列、散列顺序 2.2.拼写的同时进行判断：自动机拼写的同时进行判断：自动机 例：例：假设保留字只有假设保留字只有beginbegin

7、和和endend的情况见下图：的情况见下图：beginndeNot(e)Not(g)Not(i)Not(n)Not(b,e)Not(n)Not(d)该方法的优点：速度快；缺点：自动机太大。第9页，本讲稿共93页v 运算符的处理运算符的处理：1.1.不区分，统一成一类不区分，统一成一类 2.2.区分，每个运算符为一类区分，每个运算符为一类v 空格符和制表符以及换行符的处理空格符和制表符以及换行符的处理 1.1.无用的空格符和制表符要删掉；无用的空格符和制表符要删掉；2.2.字符串内的空格不能删；字符串内的空格不能删；实现方法：实现方法：进入字符串时令标志变量进入字符串时令标志变量StringFl

8、agStringFlag为为true,true,退退出时为出时为falsefalse。3.3.换行符不能删，用于错误定位。换行符不能删，用于错误定位。第10页，本讲稿共93页v括号类配对预检括号类配对预检括号类：括号类：如：如：begin begin end,if end,if then,()then,()，record record endend处理方法：处理方法：对每类括号设置一个计数器（初值对每类括号设置一个计数器（初值=0=0）每当遇到开括号，则计数器加每当遇到开括号，则计数器加1 1 每当遇到闭括号时，计数器减每当遇到闭括号时，计数器减1 1 词法分析结束时，如果计数器词法分析结束时

9、，如果计数器 0 0，则表明括号不匹配，报，则表明括号不匹配，报错。错。第11页，本讲稿共93页v向前看多个字符的处理向前看多个字符的处理对于对于复合型特殊符，如复合型特殊符，如“:=:=”的处理的处理方法：方法：读到读到“:”时不能判断是否为冒号，必须读下一字符。时不能判断是否为冒号，必须读下一字符。下图是对枚举类型如下图是对枚举类型如10.10010.100和实数如和实数如3.143.14的处理：的处理：D.D.DD注：对于pascal和Ada等语言至多向前看两个字符即名。第12页，本讲稿共93页例：错误单词例：错误单词12.3e+q的处理的处理方法：方法：每当一个字每当一个字符被扫描时，

10、缓存符被扫描时，缓存并判断已扫部分的并判断已扫部分的类型或无效类型或无效（Invalid），当，当不能进一步扫描时，不能进一步扫描时，进行倒退工作，返进行倒退工作，返回最后回最后Invalid前面前面的类型，的类型，如右表中如右表中返回返回RealConstant。Buffered TokenToken Flag1Integer Constant12Integer Constant12.Invalid12.3Real Constant12.3eInvalid12.3e+Invalid第13页，本讲稿共93页v词法错误校正词法错误校正词法错误种类：词法错误种类：语言不允许的符号：语言不允许的符号

11、：#括号类配对错误：括号类配对错误：单词的后继符错（偶尔）：单词的后继符错（偶尔）：词法错误校正：词法错误校正：a a 删除已被读过的字符，并重新扫描未被删除已被读过的字符，并重新扫描未被 读过的字符读过的字符 b b 删除已读过的第一个字符，重新扫描它删除已读过的第一个字符，重新扫描它 的后继部分的字符。的后继部分的字符。校正后的标示校正后的标示第14页，本讲稿共93页v词法分析独立化的意义词法分析独立化的意义 1 1）使语法分析器和语义分析器的算法更加清）使语法分析器和语义分析器的算法更加清晰和简练；晰和简练；2 2）便于利用自动机、正则表达式的算法更加清晰和）便于利用自动机、正则表达式的

12、算法更加清晰和简练；简练；3 3）更加有利于构造出高效的词法分析器；）更加有利于构造出高效的词法分析器；4 4）有利于编译器的移植。）有利于编译器的移植。第15页，本讲稿共93页3.2 3.2 有限自动机有限自动机描述程序设计语言中的单词的识别过程。描述程序设计语言中的单词的识别过程。主要内容：主要内容：确定有限自动机确定有限自动机DFADFA的定义的定义确定有限自动机确定有限自动机DFADFA的实现的实现非确定有限自动机非确定有限自动机NFANFANFANFA到到DFADFA的转换的转换DFADFA的化简的化简第16页，本讲稿共93页一个确定的有穷自动机（一个确定的有穷自动机（DFA）M是一

13、个五元组：是一个五元组：M=（SS，S0，Z）其中其中 1.1.SSSSSSSS是一个有穷集，它是一个有穷集，它的每个元素的每个元素的每个元素的每个元素称称为为为为一个一个状态状态状态状态；2.2.是是是是一个有穷字母表，它的每个元素称为一个输入符号，所以也一个有穷字母表，它的每个元素称为一个输入符号，所以也称称为为输入符号字母表输入符号字母表输入符号字母表输入符号字母表；3.3.是转换函数是转换函数是转换函数是转换函数，是在，是在SSSS上的映射，即上的映射，即:如如（ki，a）=kj，（，（kiSS，kjSS）就意味着，当前状态为就意味着，当前状态为ki，输入符为输入符为a时，时，将转换为

14、下一个状态将转换为下一个状态kj，我们把我们把kj称作称作k ki i的一个后继状态；的一个后继状态；4.S S S S0 0 0 0SS,SS,是唯一是唯一是唯一是唯一的一个的一个初态初态初态初态；5.5.Z Z Z Z SS,是是是是一个一个终态集终态集终态集终态集，终态也称，终态也称可接受状态可接受状态或或结束状态结束状态。3.2.1确定的有穷自动机（确定的有穷自动机（DFA）定义定义定义定义:第17页，本讲稿共93页DFADFA的两种表示方式的两种表示方式 状态转换图：状态转换图：结点表示状态，转换边表示转换函数，边结点表示状态，转换边表示转换函数，边 的箭头方向指向转换函数中定义的转

15、换方的箭头方向指向转换函数中定义的转换方 向。标识出初始状态和终止状态。向。标识出初始状态和终止状态。状态转换表：状态转换表：可用二维数组描述。标识出初始状态和终可用二维数组描述。标识出初始状态和终 止状态。止状态。Trans Trans（S SI I ，a a）S SJ J第18页，本讲稿共93页DFA例例1：DFAM=（S,U,V,Q,a,b,f,S,Q）其中其中f定义为：定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q第19页，本讲稿共93页DFA的状态图表示的状态图表示:f（S，a）=Uf（V，a）

16、=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUVQaaaba，bb第20页，本讲稿共93页DFA的矩阵表示的矩阵表示:f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QabSUVUQVVUQQQQ字符状态0100第21页，本讲稿共93页DFA例例2：整常数集：整常数集：如如16,135,258实常数集：实常数集：如如16.135,258.5S0dS1d0d.2d3dd1第22页，本讲稿共93页DFA例例3：第二位为第二位为2的整数集的整数集(包括一位包括一位

17、)：如如x2ad标识符集：标识符集：如如x,ab3_7d2dL-L,DL,D第23页，本讲稿共93页*上的符号串 t 被 M 接受定义定义1 1：对于对于*中的任何字符串中的任何字符串t t，若若存在一存在一条从初态结到某一终态结的道路条从初态结到某一终态结的道路，且这条路上，且这条路上所有弧的标记符连接成的字符串等于所有弧的标记符连接成的字符串等于t t，则称则称t t可为可为DFA MDFA M所接受所接受，若，若M M的初态结同时又是终态的初态结同时又是终态结，则空字可为结，则空字可为M M所所接受接受接受接受（识别识别识别识别）。）。定义定义2 2：若若 t t*，f(Sf(S，t)=

18、Pt)=P，其中其中S S为为DFADFA M M的开始状态的开始状态，P P Z Z，Z Z为终态集为终态集。则称则称t t为为DFA MDFA M所所接受接受接受接受（识别识别识别识别）。）。第24页，本讲稿共93页*上的符号串上的符号串上的符号串上的符号串t t t t（我们将输入符号串我们将输入符号串t t表示成表示成t t1 1t tx x的形的形式，其中式，其中t t1 1，t tx x *）在在在在M M M M上上上上在在DFA MDFA M上上运行运行运行运行的的定定义为：义为：f f f f（Q,Q,Q,Q,t t1 1t tx x ）=f=f=f=f（f f f f（Q,

19、Q,Q,Q,t t1 1）,t tx x）其中其中QKQK扩充转换函数扩充转换函数f f，是是K K*K K上的映射，且：上的映射，且：f f（Q Q，）=Q=Q第25页，本讲稿共93页例：例：证明证明t=baab被如下的被如下的DFA所接受。所接受。DFA M=（S,U,V,Q,a,b,f,S,Q）其中 f 定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUVQaaaba,bb证明：f（S，baab）=f（f（S，b），aab）=f（V，aab）=f（f（V，a），ab）=f（U，ab）=f（f（U，

20、a），b）=f（Q，b）=QQ属于终态。得证。第26页，本讲稿共93页DFA M DFA M 所所能接受的符号串能接受的符号串的全体记为的全体记为 L(M)L(M)结论：结论：上一个字符串集上一个字符串集 V V 是是正规正规的的，当且仅当存在一个，当且仅当存在一个 上的确定有穷自上的确定有穷自动机动机M M，使得使得 V=L(M)V=L(M)。第27页，本讲稿共93页3.2.2 3.2.2 确定有穷自动机的实现确定有穷自动机的实现DFADFA的确定性的特点：的确定性的特点：初始状态唯一初始状态唯一。转换函数转换函数f:SSf:SSSSSS是一个是一个单值函数单值函数，也，也就是说，对任何状态

21、就是说，对任何状态S S SS,SS,和输入符号和输入符号a a ,f(S,a),f(S,a)唯一地确定了下一个状态。即转唯一地确定了下一个状态。即转换函数至多确定一个状态。换函数至多确定一个状态。没有空边没有空边。即没有输入为。即没有输入为（）第28页，本讲稿共93页用用DFADFA构造词法分析器的方法构造词法分析器的方法1 1状态转换表的形式：状态转换表的形式：（数组（数组T T存放转换函数）存放转换函数）1.1.当前状态当前状态StateState置为初始状态置为初始状态 2.2.读一个字符读一个字符 CurrentCharCurrentChar 3.3.如果如果CurrentCharC

22、urrentChar EofEof并且并且 T(State,CurrentChar)T(State,CurrentChar)errorerror 则当前状态则当前状态State=State=新的状态新的状态T(State,Current)T(State,Current)，转到第转到第2 2步工作。步工作。4.4.如果当前字符为如果当前字符为EofEof并且当前状态属于终止状态，则接受并且当前状态属于终止状态，则接受当前字符串，程序结束。否则报错当前字符串，程序结束。否则报错 特点：特点：程序短小，但占用存储空间多程序短小，但占用存储空间多第29页，本讲稿共93页代码如下：代码如下：Int Sc

23、anner(char input)Int Scanner(char input)S:=S0;in=0;S:=S0;in=0;ch=inputin+;ch=inputin+;While(TT(S,ch)While(TT(S,ch)undef&undef&chch Eof)Eof)S=T(S,ch);S=T(S,ch);ch=inputin+;ch=inputin+;If(S If(S FinalStates)then return(1)FinalStates)then return(1)else return(0)else return(0)第30页，本讲稿共93页用用DFADFA构造词法分析器

24、的方法构造词法分析器的方法2 2状态转换图的形式：状态转换图的形式：每个状态对应一个带标号的每个状态对应一个带标号的casecase语句；语句；转向边对应转向边对应gotogoto语句。语句。特点：特点：程序长，但占用存储空间少。程序长，但占用存储空间少。Switch(satate)case Si:Switch(ch)Case a：goto Sj;break;Case b：goto Sk;break;other :Error;ajbki第31页，本讲稿共93页3.2.3 3.2.3 非确定有限自动机非确定有限自动机NFANFA定义：定义：一个非确定有限自动机一个非确定有限自动机(NFANFA)

25、A)A是一是一个五元组个五元组A=(A=(,SS,S,SS,S0 0,f,TS).,f,TS).其中其中 :是字母表是字母表;SS:SS:是状态集是状态集;S S0:0:是是初始状态集初始状态集;f:f:是转换函数，但是转换函数，但不要求是单值的不要求是单值的;f:SS f:SS ()SSSS TS:TS:是终止状态集是终止状态集.第32页，本讲稿共93页NFANFA的特点：的特点：一个状态的一个状态的不同输出边不同输出边可标有可标有相同的符号相同的符号。允许有允许有多个开始状态多个开始状态。允许输出边上标有允许输出边上标有空串符号空串符号。0|n02 2）正则表达式不能用于描述重复串。正则表

26、达式不能用于描述重复串。例：例：w c w|ww c w|w是是a a和和b b的串的串 无法用正则表无法用正则表达式表示（保证两边达式表示（保证两边w w是相同的）。是相同的）。原因是：原因是：正则表达式中没有变量正则表达式中没有变量。第57页，本讲稿共93页 正则定义正则定义正则定义：正则定义：M Mr r /本质是为本质是为正则表达式命名正则表达式命名功能：功能：为较长的正则表达式提供一个简化了的名字为较长的正则表达式提供一个简化了的名字 如：如：E=(a+bE=(a+b c)+c)+(a+b(a+b c)c)(a+b(a+b c)c)(a(a b+b+c)+c)+(a(a b+b+c)

27、c)其中其中 a+ba+b c c 出现了三次，出现了三次，a a b+b+c c 出现了二次，如用出现了二次，如用正则定义正则定义可可表示如下：表示如下：E E1 1 a+ba+b c c E E2 2 a a b+b+c c E E (E E1 1+E+E1 1 E E1 1)E E2 2+E+E2 2第58页，本讲稿共93页例例3：标识符：标识符：letterlettera-za-z，A-ZA-Z digit digit 0-90-9 identifieridentifierletter(letter|digit)letter(letter|digit)*数字：数字：整数整数 Int I

28、nt 1-9Digit1-9Digit*|0|0 实数实数 realrealIntInt.Int Int 特殊符号：特殊符号：运算符运算符 chch+|-|+|-|第59页，本讲稿共93页 正则表达式与有限自动机等价正则表达式与有限自动机等价定理：定理：对任一确定有限自动机对任一确定有限自动机A A，存在一正存在一正 则表达式则表达式e,e,使得使得L(A)=L(e),L(A)=L(e),反之亦然。反之亦然。关系图：关系图：DFA 正则表达式NFA第60页，本讲稿共93页正则表达式到FA的转换规则：13a b12a|b13 b*123ab12ab123b第61页，本讲稿共93页R=R=(a|b

29、)*(a|b)*abbabbxiy(a|b)*abbxjyabbia|bxjyabbiab例：例：为为R=(a|b)*abbR=(a|b)*abb构造构造NFA，使得使得L(N)=L(R)。xjybiabklab第62页，本讲稿共93页123ab12ab12313a b12a|b13a b*cabcDFADFA到正则表达式的转换规则到正则表达式的转换规则：第63页，本讲稿共93页例：03124a,baaa,ba,bbb求正规式R第64页，本讲稿共93页03124a,baaa,ba,bbbxy024a|baaa|ba|bbbxy第65页，本讲稿共93页024a|baaa|ba|bbbxy0a|b

30、aa(a|b)*bb(a|b)*xy第66页，本讲稿共93页0a|baa(a|b)*bb(a|b)*xy0a|bxyaa(a|b)*|bb(a|b)*xy(a|b)*(aa|bb)(a|b)*R=(a|b)*(aa|bb)(a|b)*第67页，本讲稿共93页习习题题作作业业z S=a,b,cS=a,b,c，试给出，试给出S-S-上一个不包含连续两个上一个不包含连续两个b b的所有符号串集合的正则定义。的所有符号串集合的正则定义。z S=a,b,cS=a,b,c，叙叙述述正正则则式式(b|c)b|c)*a(b|c)a(b|c)*a)a)*(b|c)(b|c)*描述的符号串。描述的符号串。zS S

31、 0,10,1，叙叙述述正正则则式式(00(00|11)11)(01(01|10)10)(00(00|11)11)(01(01|10 10)(00(00|11)11)描述的符号串。描述的符号串。z 给给出出能能被被5 5整整除除的的二二进进制制数数表表示示形形式式的的正正则则定定义。义。第68页，本讲稿共93页*3.4词法分析器的构造词法分析器的构造词法分析器（Scanner）输入流词法描述（正则表达式）NFADFATokenListerror第69页，本讲稿共93页词法分析器的词法分析器的构造方法构造方法用用DFADFA人工构造：人工构造：1.1.确定词法分析器的接口，即确定词法分析确定词法

32、分析器的接口，即确定词法分析 器是作为语法分析的一个子程序还是作为器是作为语法分析的一个子程序还是作为 独立一遍。独立一遍。2.2.确定单词分类和确定单词分类和TokenToken结构。结构。3.3.根据根据2 2步，构造每一类单词的描述：步，构造每一类单词的描述：正则表达式正则表达式NFANFADFADFA。4.4.根据根据3 3步设计算法实现步设计算法实现DFADFA。利用工具自动生成：利用工具自动生成：ScanGenScanGen、LexLex第70页，本讲稿共93页3.4.1 3.4.1 用用DFADFA人工构造词法分析器人工构造词法分析器单词的单词的TOKEN输出表如下：输出表如下：

33、identifier($id,Name)number($int,Numb)+($plus,);($semi,):=($assi,):($colon,)=($le,)($lt,)第71页，本讲稿共93页单词的一个单词的一个DFA15L023L|DD4869710D+;:=otherother第72页，本讲稿共93页状态状态(0)的代码：的代码：Ls0:string:=;ReadChar(CurrentChar);caseCurrentCharofA.Z|a.z:gotoLs1;0.9:gotoLs2;+:gotoLs3;:gotoLs4;:gotoLs5;:gotoLs8;end;第73页，本讲

34、稿共93页状态状态(1)的代码：的代码：Ls1:beginstring:=Append(string,CurrentChar);ReadChar(CurrentChar);caseCurrentCharofA.Z|a.z|0.9:gotoLs1;other:beginBACK;return($id,string)endendend;第74页，本讲稿共93页状态状态(2)的代码：的代码：Ls2:beginstring:=Append(string,CurrentChar);ReadChar(CurrentChar);caseCurrentCharof0.9:gotoLs2;other:begin

35、BACK;return($int,string)endendend;第75页，本讲稿共93页状态状态(3)(4)(5)(6)的代码：的代码：Ls3:return($plus,);Ls4:return($semi,);Ls5:beginReadChar(CurrentChar);caseCurrentCharof=:gotoLs6;other:gotoLs7;endend;Ls6:return($assi,);第76页，本讲稿共93页状态状态(7)(8)(9)(10)的代码：的代码：Ls7:beginBACK;return($plus,)endLs8:beginReadChar(CurrentC

36、har);caseCurrentCharof=:gotoLs9;other:gotoLs10;endend;Ls9:return($le,);Ls10:beginBACK;return($lt,)end第77页，本讲稿共93页3.4.2 3.4.2 词法分析器的生成器词法分析器的生成器LexLex功能：功能：依据语言的正则表达式，自动生成该语言依据语言的正则表达式，自动生成该语言的词法分析程序。的词法分析程序。执行过程：执行过程：正则表达式文件Lex.lLex词法分析器lexyy.cC编译器a.out输入流Token序列第78页，本讲稿共93页Lex的常规表达式（的常规表达式（1）字符 含义

37、A-Z,0-9,a-z 构成了部分模式的字符和数字。.匹配任意字符，除了 n。-用来指定范围。例如：A-Z 指从 A 到 Z 之间的所有字符。一个字符集合。匹配括号内的 任意 字符。如果第一个字符是 那么它表示否定模式。例如：abC 匹配 a,b 和 C中的任何一个。*匹配 0个或者多个上述的模式。+匹配 1个或者多个上述模式。?匹配 0个或1个上述模式。$作为模式的最后一个字符匹配一行的结尾。第79页，本讲稿共93页Lex的常规表达式（的常规表达式（2）字符 含义 指出一个模式可能出现的次数。例如：A1,3 表示 A 可能出现1次或3次。用来转义元字符。同样用来覆盖字符在此表中定义的特殊意义

38、，只取字符的本意。否定。|表达式间的逻辑或。字符的字面含义。元字符具有。/向前匹配。如果在匹配的模版中的“/”后跟有后续表达式，只匹配模版中“/”前面的部分。如：如果输入 A01，那么在模版 A0/1 中的 A0 是匹配的。()将一系列常规表达式分组。第80页，本讲稿共93页常规表达式举例常规表达式举例常规表达式 含义 jokers 匹配 jokes 或 joker。A1,2shis+匹配 AAshis,Ashis,Ashiss,Ashisss。(Ab-e)+匹配在 A 出现位置后跟随的从 b 到 e 的所有字符中的 1 个或 多个。第81页，本讲稿共93页标记声明举例标记声明举例标记 相关表

39、达式 含义 数字(number)(0-9)+1个或多个数字字符(chars)A-Za-z任意字符空格(blank)一个空格字(word)(chars)+1个或多个 chars 变量(variable)(字符)+(数字)*(字符)*(数字)*第82页，本讲稿共93页LexLex输入文件的格式输入文件的格式输入文件格式：输入文件格式：declarations declarations%rules rules%auxiliary procedures auxiliary procedures%声明变量,常量%正则定义p action第83页，本讲稿共93页Lex编程编程Lex编程可以分为三步：编程可

40、以分为三步：以以Lex可以理解的格式指定模式相关的动作。可以理解的格式指定模式相关的动作。在这一文件上运行在这一文件上运行Lex，生成扫描器的，生成扫描器的C代码。代码。编译和链接编译和链接C代码，生成可执行的扫描器。代码，生成可执行的扫描器。Lex的输入格式的输入格式一个一个Lex程序分为三个段：程序分为三个段：第一段：是第一段：是C和和Lex的全局声明的全局声明第二段：包括模式（第二段：包括模式（C代码）代码）第三段：是补充的第三段：是补充的C函数。函数。这些段以这些段以%来分界。来分界。第84页，本讲稿共93页（1）C和和Lex的全局声明的全局声明这一段中我们可以增加这一段中我们可以增加

41、C变量声明。变量声明。%intwordCount=0;/*保存统计出来的字数保存统计出来的字数*/%charsA-Za-znumbers(0-9)+delimntwhitespacedelim+wordschars+%两个百分号标记指出了两个百分号标记指出了Lex程序中这一段的结束和三程序中这一段的结束和三段中第二段的开始。段中第二段的开始。第85页，本讲稿共93页（2）Lex的模式匹配规则的模式匹配规则wordswordCount+;/*increasethewordcountbyone*/whitespace/*donothing*/numbers/*onemaywanttoaddsome

42、processinghere*/%第86页，本讲稿共93页（3）C代码代码 Lex编程的第三段，也就是最后一段覆盖了编程的第三段，也就是最后一段覆盖了C的的函数声明（有时是主函数）。函数声明（有时是主函数）。Lex有一套可供使用的有一套可供使用的函数和变量。函数和变量。其中之一就是其中之一就是yywrap。一般来说，。一般来说，yywrap()的定义如下例的定义如下例。voidmain()yylex();/*starttheanalysis*/printf(Noofwords:%dn,wordCount);intyywrap()return1;第87页，本讲稿共93页例：例：识别识别PL/0单

43、词的单词的LEX程序程序%#include#include“code.h”#include“symbol.h”#include“y.tab.h”externintlevel;intcc=0;%IDENTa-zA-Za-zA-Z0-9*NUMBER0-90-9*%第88页，本讲稿共93页“cc+;“t“tablize();/*adjustcctotab-position*/“n“cc=0;line_copy();/*copyalineofinputfile*/“cc+;returnGT;“=“cc+;returnET;“#“cc+;returnNT;“,“cc+;returncolon;“.“c

44、c+;returnPeriod;“(“cc+;returnLparen;“)“cc+;returnRparen;“=“cc+;cc+;returnGE;“:=“cc+;cc+;returnASGN;“;“cc+;returnSemicolon;第89页，本讲稿共93页NUMBERintn;cc+=yyleng;sscanf(yytext,”%d”,&n);yylval.numder=n;returnNUMBER;IDENTSymbol*s;cc+=yyleng;if(s=lookup(yytext)=0)s=install(yytext,VARIABLE,level,0);if(s-type=

45、C)yylval.numder=s-adr;elseyylval.sym=s;returns-type;%第90页，本讲稿共93页int yywrap()return 1;第91页，本讲稿共93页单元总结单元总结两个工具：两个工具：有限自动机、正则表达式有限自动机、正则表达式三个算法：三个算法：正则表达式到正则表达式到FAFA的转换的转换 NFA NFA到到DFADFA的转换的转换 DFADFA的化简的化简一个实现：一个实现：DFADFA的实现的实现 第92页，本讲稿共93页作业：作业：构造正则表达式构造正则表达式 (a|b)*abb(a|b)*(a|b)*abb(a|b)*的最简的最简 DFA DFA。要求先构造。要求先构造NFANFA，其次转换为，其次转换为DFADFA，最，最 后加以极小化。后加以极小化。书上书上 Pp58 Pp58 第第8 8题题附加题：附加题：分别构造分别构造 和和 的自动机的自动机第93页，本讲稿共93页