《正则表达式.ppt》由会员分享，可在线阅读，更多相关《正则表达式.ppt（76页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章第三章 词法分析词法分析School of Computer Science&Technology Harbin Institute of Technology重点：重点：词法分析器的输入、输出，词法分析器的输入、输出，用于识别符号的状态转移图的构造，用于识别符号的状态转移图的构造，根据状态转移图实现词法分析器。根据状态转移图实现词法分析器。难点：难点：词法的正规文法表示、正规表达式表示、词法的正规文法表示、正规表达式表示、状态转移图表示，它们之间的转换。状态转移图表示，它们之间的转换。2023/3/92第第3章章词法分析词法分析3.1词法分析器的功能词法分析器的功能3.2单词的描述单词
2、的描述3.3单词的识别单词的识别3.4词法分析程序的自动生成词法分析程序的自动生成3.5本章小结本章小结2023/3/933.1词法分析器的功能词法分析器的功能n功能：输入源程序，输出单词符号功能：输入源程序，输出单词符号(token)。即：把构成源程序的字符串转换成即：把构成源程序的字符串转换成“等价的等价的”单词单词(记号记号)序列序列n根据词法规则识别及组合单词，进行词法根据词法规则识别及组合单词，进行词法检查检查n对数字常数完成数字字符串到二进制数值对数字常数完成数字字符串到二进制数值的转换的转换n删去空格字符和注释删去空格字符和注释2023/3/943.1.1单词的分类与表示单词的分
3、类与表示&3.1.2词法分析器的输出词法分析器的输出一、单词的种类一、单词的种类1.关键字关键字:也称基本字，也称基本字，begin、end、for、do.2.标识符标识符:由用户定义，表示各种名字由用户定义，表示各种名字3.常数常数:整常数、实常数、布尔常数、字符串常数等整常数、实常数、布尔常数、字符串常数等4.运算符运算符:算术运算符算术运算符+、-、*、/等；逻辑运算符等；逻辑运算符not、or与与and等；关系运算符等；关系运算符=、和和 等等5.分界符分界符:，、；、（、），、；、（、）.2023/3/95二、单词的内部形式二、单词的内部形式几种常用的单词内部形式：几种常用的单词内部
4、形式：1 1、按单词种类分类、按单词种类分类2 2、保留字和分界符采用一符一类、保留字和分界符采用一符一类3 3、标识符和常数的单词值又为指示字、标识符和常数的单词值又为指示字（指针值）（指针值）种别种别 属性值属性值表示单词的种类，可用整表示单词的种类，可用整数编码或记忆符表示数编码或记忆符表示不同的单词不同的值不同的单词不同的值2023/3/96单词名称单词名称标识符标识符无符号常数无符号常数(整整)无符号浮点数无符号浮点数布尔常数布尔常数字符串常数字符串常数保留字保留字分界符分界符类别编码类别编码1 12 23 34 45 56 67 7单词值单词值内部字符串内部字符串整数值整数值数值数
5、值0 0 或或 1 1内部字符串内部字符串保留字或内部编码保留字或内部编码分界符或内部编码分界符或内部编码1、按单词种类分类、按单词种类分类2023/3/972 2、保留字和分界符采用一符一类、保留字和分界符采用一符一类单词名称单词名称标识符标识符无符号常数无符号常数(整整)无符号浮点数无符号浮点数布尔常数布尔常数字符串常数字符串常数BEGINBEGINENDENDFORFORDODO:+*,(类别编码类别编码1 12 23 34 45 56 67 78 89 92020212122222323单词值单词值内部字符串内部字符串整数值整数值数值数值0 0 或或 1 1内部字符串内部字符串-202
6、3/3/98例例3.1语句语句ifcount7thenresult:=3.14的的单词符号序列单词符号序列(IF(IF，0)0)(ID(ID，指向指向count count 的符号表入口的符号表入口)(GT(GT，0)0)(INT(INT，7)7)(THEN(THEN，0)0)(ID(ID，指向指向resultresult的符号表入口的符号表入口)(ASSIGN(ASSIGN，0)0)(REAL(REAL，3.14)3.14)(SEMIC(SEMIC，0)0)跟实现有关跟实现有关2023/3/993.1.3源程序的输入缓冲与预处理源程序的输入缓冲与预处理 n超前搜索和回退超前搜索和回退n双字符
7、运算符（双字符运算符（*,/*,:=,/*,:=,）nDO 90 k=1,10DO 90 k=1,10nDO 90 k=1.10 DO 90 k=1.10 n缓冲区缓冲区n假定源程序存储在磁盘上，这样每读一个字符就假定源程序存储在磁盘上，这样每读一个字符就需要访问一次磁盘，效率显然是很低的。需要访问一次磁盘，效率显然是很低的。n空白字符的剔除空白字符的剔除n剔除源程序中的无用符号、空格、换行、注释等剔除源程序中的无用符号、空格、换行、注释等2023/3/9103.1.3源程序的输入缓冲与预处理源程序的输入缓冲与预处理(续续)工作区工作区工作区工作区(token)(token)(token)(t
8、oken)单词开始指针单词开始指针扫描指针扫描指针正拼单词正拼单词正拼单词正拼单词n输入缓冲区输入缓冲区2023/3/911每次移动向前指针都需要每次移动向前指针都需要做两次测试做两次测试3.1.3源程序的输入缓冲与预处理源程序的输入缓冲与预处理(续续)n双缓冲区问题双缓冲区问题_超前扫描导致的效率问题超前扫描导致的效率问题n n问题：如何设计和实现扫描器？问题：如何设计和实现扫描器？问题：如何设计和实现扫描器？问题：如何设计和实现扫描器？n n大小问题大小问题大小问题大小问题128Byte*2|1024Byte*2|4096Byte*2128Byte*2|1024Byte*2|4096Byt
9、e*2ifforward在缓冲区第一部分末尾在缓冲区第一部分末尾thenbegin重装缓冲区第二部分重装缓冲区第二部分;forward:=forward+1endelseifforward在缓冲区第二部分末尾在缓冲区第二部分末尾thenbegin重装缓冲区第一部分重装缓冲区第一部分;将将forward移到缓冲区第一部分开始移到缓冲区第一部分开始endelseforward:=forward+1;forward:=forward+1;ifforward=eofthenbeginif forward在第一部分末尾在第一部分末尾thenbegin重装第二部分重装第二部分;forward:=forwa
10、rd+1endelseifforward在第二部分末尾在第二部分末尾thenbegin重装第一部分重装第一部分;将将forward移到第一部分开始移到第一部分开始endelse/*eof在表示输入结束在表示输入结束*/终止词法分析终止词法分析end 2023/3/9123.1.4词法分析阶段的错误处理词法分析阶段的错误处理 1 1非法字符检查非法字符检查2 2关键字拼写错误检查关键字拼写错误检查3 3不封闭错误检查不封闭错误检查4 4重复说明检查重复说明检查5 5错误恢复与续编译错误恢复与续编译紧急方式恢复紧急方式恢复(panic-mode recovery)(panic-mode recov
11、ery)反复删掉剩余输入最前面的字符，直到词法反复删掉剩余输入最前面的字符，直到词法分析器能发现一个正确的单词为止。分析器能发现一个正确的单词为止。2023/3/9133.1.5词法分析器的位置词法分析器的位置 目标程序词法分析器语法分析器语义分析与代码生成目标代码整理图3.4以语法分析器为中心源程序符号表n以语法分析器为中心的优点：以语法分析器为中心的优点：n简化编译器的设计。简化编译器的设计。n提高编译器的效率。提高编译器的效率。n增强编译器的可移植性。增强编译器的可移植性。2023/3/9143.2单词的描述单词的描述3.2.1正则文法正则文法n正则文法正则文法G=(V，T，P，S)中，
12、对中，对 P，均具有形式均具有形式Aw或或AwB(Aw或或ABw)，其中，其中A，BV，wT+。n例例3.2标识符的文法标识符的文法n约定：用约定：用digit表示数字：表示数字：0,1,2,9;用用letter表示字母：表示字母：A,B,Z,a,b,zn|nA|B|Z|a|b|zn0|1|2|92023/3/9153.2.2正则表达式正则表达式n例例3.2：标识符的另一种表示：标识符的另一种表示nletter(letter|digit)*n|表示表示或或n*表示表示Kleene闭包闭包n+表示正闭包表示正闭包n？表示？表示“0或或1个个”nLetter和和(letter|digit)*的并列
13、表示两者的连接的并列表示两者的连接n正则式正则式r表示正则集表示正则集,相应的正则集记为相应的正则集记为L(r)2023/3/9163.2.2正则表达式正则表达式(续续)RE定义定义3.1设设是一个字母表，则是一个字母表，则上的正则表达式及其所表示的上的正则表达式及其所表示的正则语言可递归地定义如下：正则语言可递归地定义如下：是是上的一个正则表达式，它表示空集；上的一个正则表达式，它表示空集；是是上的一个正则表达式，它表示语言上的一个正则表达式，它表示语言；对于对于 a(a)，a是是上的一个正则表达式，它表示的正则上的一个正则表达式，它表示的正则语言是语言是a；假设假设r和和s都是都是上的正则
14、表达式，它们表示的语言分别为上的正则表达式，它们表示的语言分别为L(r)和和L(s)，则：，则：(r)也是也是上的正则表达式，它表示的语言为上的正则表达式，它表示的语言为L(r)；(r|s)也是也是上的正则表达式，它表示的语言为上的正则表达式，它表示的语言为L(r)L(s)；(rs)也是也是上的正则表达式，它表示的语言为上的正则表达式，它表示的语言为L(r)L(s)；(r*)也是也是上的正则表达式，它表示的语言为上的正则表达式，它表示的语言为(L(r)*；只有经有限次使用上述规则构造的表达式才是只有经有限次使用上述规则构造的表达式才是上的正则表上的正则表达式。达式。2023/3/917正则表达
15、式中的运算优先级正则表达式中的运算优先级运算优先级和结合性运算优先级和结合性:n*高于高于“连接连接”和和|，“连接连接”高于高于|n|具有交换律、结合律具有交换律、结合律n“连接连接”具有结合律、和对具有结合律、和对|的分配律的分配律n()指定优先关系指定优先关系意义清楚时，括号可以省略意义清楚时，括号可以省略例：例：1.L(a|b)*)=L(a*|b*)*)=x|x是是a和和b构成的符号串，构成的符号串，包括包括2.L(a|a*b)=a,b,ab,aab,aaab,aaaab,.2023/3/9183.2.3正则表达式与正则文法的等价性正则表达式与正则文法的等价性n正则表达式与正则文法等价
16、正则表达式与正则文法等价n对对任任意意一一个个正正则则表表达达式式，存存在在一一个个定定义义同同一语言的正则文法一语言的正则文法n对对任任意意一一个个正正则则文文法法，存存在在一一个个定定义义同同一一语言的正则表达式语言的正则表达式2023/3/919根据正则文法构造等价的正则表达式根据正则文法构造等价的正则表达式 n问题：给定正则文法问题：给定正则文法G，构造一个正则表达，构造一个正则表达式式r，使得，使得L(r)=L(G)n基本思路基本思路n为正则文法的每个产生式构造一个正则表达式方为正则文法的每个产生式构造一个正则表达式方程式，这些方程式中的变量是文法程式，这些方程式中的变量是文法G中的
17、语法变中的语法变量，各变量的系数是正则表达式，简称为方程式。量，各变量的系数是正则表达式，简称为方程式。从而得到一个联立方程组。从而得到一个联立方程组。n用代入消元法消去联立方程组中除开始符号外的用代入消元法消去联立方程组中除开始符号外的其他变量，最后得到关于开始符号其他变量，最后得到关于开始符号S的解：的解：S=r，r即为所求的正则表达式。即为所求的正则表达式。2023/3/920根据正则文法构造等价的正则表达式根据正则文法构造等价的正则表达式 n具体步骤具体步骤(1)根据正则文法根据正则文法G构造正则表达式联立方程组。构造正则表达式联立方程组。假设正则文法假设正则文法G是右线性的，其每个产
18、生式的右部是右线性的，其每个产生式的右部只含有一个终结符，则有如下方程式构造规则：只含有一个终结符，则有如下方程式构造规则：对形如对形如A a1|a2|am的产生式，构造方程式的产生式，构造方程式A=a1|a2|am。其中可以有形如其中可以有形如A的产生式；的产生式；对形如对形如Aa1A|a2A|amA的产生式，构造方程式的产生式，构造方程式A=(a1|a2|am)*A；对形如对形如Aa1B|a2B|amB的产生式，构造方程式的产生式，构造方程式A=(a1|a2|am)B，其中，其中BA。2023/3/921根据正则文法构造等价的正则表达式根据正则文法构造等价的正则表达式(2)解联立方程组，求
19、等价的正则表达式解联立方程组，求等价的正则表达式r用代入消元法逐个消去方程组中除开始符号用代入消元法逐个消去方程组中除开始符号S外的其他变量，最后即可得到关于开始符号外的其他变量，最后即可得到关于开始符号S的解。代入消元规则如下：的解。代入消元规则如下：如果有如果有A=r1B|r2B|rnB，则用，则用A=(r1|r2|rn)B替换之，其中替换之，其中BA；如果有如果有A=t1A|t2A|tmA，则用，则用A=(t1|t2|tm)*A替换之；替换之；2023/3/922根据正则文法构造等价的正则表达式根据正则文法构造等价的正则表达式 如果有如果有A=(r1|r2|rn)B，B=(t1|t2|t
20、m)C，则用，则用A=(r1|r2|rn)(t1|t2|tm)C替换之，其中替换之，其中BA；如果有如果有A=(r1|r2|rn)B，B=(t1|t2|tm)，则用，则用A=(r1|r2|rn)(t1|t2|tm)替换之，其中替换之，其中BA；对对A=(t1|t2|tm)*A且且A=(r1|r2|rn)B，其中，其中BA，则用则用A=(t1|t2|tm)*(r1|r2|rn)B替换之；替换之；对对A=(t1|t2|tm)*A且且A=r1|r2|rn则用则用A=(t1|t2|tm)*(r1|r2|rn)替换之；替换之；2023/3/923根据正则文法构造等价的正则表达式根据正则文法构造等价的正则
21、表达式 如果有如果有A=1、A=2、A=h，则用，则用A=1|2|h代替之。代替之。如果最后得到的关于如果最后得到的关于S的方程式为如下形式，的方程式为如下形式，S=1|2|h则将方程式右边所有其中仍然含有语法变量则将方程式右边所有其中仍然含有语法变量的的i(1in)删除，得到的结果就是与删除，得到的结果就是与G等价等价的正则表达式；如果任意的的正则表达式；如果任意的i(1in)均含有均含有语法变量，则语法变量，则就是与就是与G等价的正则表达式。等价的正则表达式。2023/3/924根据正则文法构造等价的正则表达式根据正则文法构造等价的正则表达式 n例例3.6将如下文法将如下文法G转换成相应的
22、正则表达式转换成相应的正则表达式SaS|aBBbB|bC|aB|bSCcC|c1.列方程组列方程组nS=a*S S=aB B=(a|b)*B B=bCnB=bS C=c*C C=c2.代入法解方程组代入法解方程组nC=c*c B=bc*c|bc B=(a|b)*(bc*c|bc)nB=(a|b)*bS S=a*aBnS=a*a(a|b)*bS|a*a(a|b)*(bc*c|bc)nS=(a*a(a|b)*b)*a*a(a|b)*(bc*c|bc)n如果用正闭包表示，则为如果用正闭包表示，则为(a+(a|b)*b)*a+(a|b)*(bc+|bc)2023/3/925将正则表达式转换成等价的正则
23、文法将正则表达式转换成等价的正则文法 n问题：给定问题：给定上的一个正则表达式上的一个正则表达式r，根据，根据r构构造正则文法造正则文法G，使得，使得L(G)=L(r)n定义定义3.3设字母表为设字母表为，A、B、C为语为语法变量集合，对于法变量集合，对于上的任意正则表达式上的任意正则表达式r，形如形如Ar的式子称为正则定义式；如果的式子称为正则定义式；如果r是是中的字母和用正则定义式定义的变量组成的中的字母和用正则定义式定义的变量组成的正则表达式，则形如正则表达式，则形如Ar的式子称为正则定的式子称为正则定义式。义式。2023/3/926将正则表达式转换成等价的正则文法将正则表达式转换成等价
24、的正则文法 n按如下方法构造正则定义式，并逐步将其转按如下方法构造正则定义式，并逐步将其转换成正则文法换成正则文法n引入开始符号引入开始符号S，从如下正则定义式开始，从如下正则定义式开始nSrn按如下规则将按如下规则将Sr分解为新的正则定义式，在分解为新的正则定义式，在分解过程中根据需要引入新的语法变量分解过程中根据需要引入新的语法变量2023/3/927将正则表达式转换成等价的正则文法将正则表达式转换成等价的正则文法nAr是正则定义式，则对是正则定义式，则对Ar的分解规则如下：的分解规则如下：如果如果r=r1r2，则将，则将Ar分解为分解为Ar1B，Br2，BV；如果如果r=r1*r2，则将
25、，则将Ar分解为分解为Ar1A，Ar2；如果如果r=r1 r2，则将，则将Ar分解为分解为Ar1，Ar2。不断应用分解规则不断应用分解规则到到对各个正则定义式进行分解，对各个正则定义式进行分解，直到每个正则定义式右端只含一个语法变量直到每个正则定义式右端只含一个语法变量(即符合即符合正则文法产生式的形式正则文法产生式的形式)为止。为止。例例3.9正则表达式到正则文法的转换正则表达式到正则文法的转换na(a|b)*(|(.|_)(a|b)(a|b)*)=a(a|b)*|a(a|b)*.(a(a|b)*|b(a|b)*)|a(a|b)*_(a(a|b)*|b(a|b)*)=aA|aBA=aA|bA
26、|B=aB|bB|.C|_CC=aA|bAS SaAaA|aBaB A AaAaA|bAbA|B BaBaB|bBbB|.|.C C|_|_C CC CaAaA|bAbA28例例3.10标识符定义的转换标识符定义的转换n引入引入SSletter(letter|digit)*n分解为分解为SletterAA(letter|digit)A|n执行连接对执行连接对|的分配律的分配律SletterAAletterA|digitA|29高级语言词法的简单描述高级语言词法的简单描述n词法词法n单词符号的文法，用来描述高级语言中的：单词符号的文法，用来描述高级语言中的：标识符、常数、运算符、分界符、关键字标
27、识符、常数、运算符、分界符、关键字n参参考考教教材材P73-77，了了解解如如何何定定义义高高级级语语言言中的整数、实数中的整数、实数等的相应正则文法。等的相应正则文法。302023/3/931例例3.7某简易语言的词法某简易语言的词法正则定义式正则定义式 词法规则词法规则 单词种别单词种别 属性属性(|)*IDN 符号表入口符号表入口 ()*NUM 数值数值 :=:=ASG无无 其它单词其它单词字符本身字符本身 单词名称单词名称 无无 2023/3/932变换为正规文法变换为正规文法letter|letter|digitdigit|digit:=+=(其它：实数、算术运算符、关系运算符、分号
28、、括号等）其它：实数、算术运算符、关系运算符、分号、括号等）问题：如问题：如何识别记何识别记号？号？2023/3/9333.2.4有穷状态自动机有穷状态自动机n具有离散输入输出的系统的数学模型具有离散输入输出的系统的数学模型n具有有穷个内部状态具有有穷个内部状态n系统只需根据当前所处的状态和面临的输入就系统只需根据当前所处的状态和面临的输入就能确定后继的行为，处理完当前输入后系统的能确定后继的行为，处理完当前输入后系统的状态将发生变化状态将发生变化n具有初始状态和终止状态具有初始状态和终止状态n例：电梯、文本编辑程序、词法分析程序例：电梯、文本编辑程序、词法分析程序有穷自动机的物理模型有穷自动
29、机的物理模型 有穷状态有穷状态控制器控制器输入带输入带读头读头设想有个按钮，自设想有个按钮，自动机启动后一个动动机启动后一个动作一个动作地做下作一个动作地做下去，去，直到没有，直到没有输入。如果停在终输入。如果停在终态，接收；如果停态，接收；如果停在非终态，不接收在非终态，不接收一个动作：一个动作：pp，aqaq，读头前进一格，读头前进一格FAFA接收的符号接收的符号行的集合即为行的集合即为其其接收的语言接收的语言342023/3/935有穷自动机的用处有穷自动机的用处n有穷自动机是许多重要类型的硬件和软件有穷自动机是许多重要类型的硬件和软件的有用模型的有用模型n数字电路的设计和检查软件数字电
30、路的设计和检查软件n典型编译器的词法分析器典型编译器的词法分析器n扫描大量文本来发现单词、短语或其他模式扫描大量文本来发现单词、短语或其他模式的出现的软件的出现的软件n所有只有有穷个不同状态的系统（如通信协所有只有有穷个不同状态的系统（如通信协议或安全交换信息的协议）的验证软件议或安全交换信息的协议）的验证软件2023/3/936例：例：一个奇偶校验器一个奇偶校验器q q0 00 00 01 11 1q q1 1测试输入中测试输入中1 1的个数的奇偶性，并且只接的个数的奇偶性，并且只接收含有奇数个收含有奇数个1 1的那些输入串。的那些输入串。问题：有穷自动机的形式描述？问题：有穷自动机的形式描
31、述？关键是如何描述动作？关键是如何描述动作？注意：状态有注意：状态有记忆功能，记记忆功能，记住输入串的部住输入串的部分特征。分特征。2023/3/937确定的有穷自动机的形式定义确定的有穷自动机的形式定义定义定义3.4一个一个确定的有穷自动机确定的有穷自动机M（记作（记作DFAM）是一）是一个五元组个五元组（，0，），其中），其中是一个有穷状态集合。是一个有穷状态集合。是一个字母表，它的每个元素称输入符号。是一个字母表，它的每个元素称输入符号。0，0称为初始状态。称为初始状态。，称为终止状态集合。称为终止状态集合。是一个从是一个从到到的单值映射的单值映射(p，a)（p,q，a）表示当前状态为表
32、示当前状态为p,输入符号为输入符号为a时，自动机将转换到下时，自动机将转换到下一个状态一个状态q，q称为称为p的一个后继。的一个后继。2023/3/938DFA的表示的表示例例设设（，（，a，b，），）其中：其中：（，（，a），），（，（，a）3（，（，a），），（，（，a）（，（，b），），（，（，b）（，（，b），），（，（，b）一个有三种表示：一个有三种表示：（1）转换函数；）转换函数；（2）转移矩阵；）转移矩阵；（3）状态转换图。）状态转换图。2023/3/939转移矩阵转移矩阵0132aaaabbbb3状态转换图状态转换图易存储易存储2023/3/940从状态转换图看，从初态从状态转
33、换图看，从初态出发，沿任一条路径到达出发，沿任一条路径到达接受状态，这条路径上的接受状态，这条路径上的弧上的标记符号连接起来弧上的标记符号连接起来构成的符号串被接受。构成的符号串被接受。如：如：abab0123aaaabbbbDFAM接受的语言接受的语言问题：如何形式描述问题：如何形式描述DFA接收的语言？接收的语言？2023/3/941DFAM接受的语言接受的语言如果对所有如果对所有*，a，q以下述方式递以下述方式递归地扩展归地扩展的定义的定义（q，）q，(q，wa）(q，w），），a），），则则M所接收的语言为：所接收的语言为：()ww*，且，且(q，w)对于上页例中的对于上页例中的DFA
34、M和和w=baa，(0，baa）=(2,aa）=(1,a）=32023/3/942非确定的有穷自动机非确定的有穷自动机NFAM定义定义3.6非确定的有穷自动机是一个五元组非确定的有穷自动机是一个五元组M（，q，）其中其中，q，的意义和的意义和DFA的定义一样，的定义一样，而而是一个从是一个从 到到的子集的映射，即的子集的映射，即：，其中，其中S=。类似于类似于DFA，NFAM亦可用状态转换图表示，亦可用状态转换图表示，同样也可以定义同样也可以定义NFAM接受的语言。接受的语言。2023/3/943DFAM的模拟算法的模拟算法输入：以输入：以eof结尾的串结尾的串x，DFAM=(Q，q0，F)；
35、输出：如果输出：如果M接受接受x则输出则输出“yes”，如果，如果M不接受不接受x则输出则输出“no”步骤：步骤：1s=q0;2c=getchar(x);3while(c!=eof)4s=move(s,c);5c=getchar(x);67ifsFreturn“yes”8elsereturn“no”;2023/3/9443.2.5状态转换图状态转换图n定义定义3.7设设M=(Q，q0，F)为一个有穷为一个有穷状态自动机，满足如下条件的有向图被称为状态自动机，满足如下条件的有向图被称为M的状态转换图的状态转换图(transitiondiagram)：qQq是该有向图中的一个顶点；是该有向图中的一
36、个顶点；(q，a)=p图中有一条从顶点图中有一条从顶点q到顶点到顶点p的的标记为标记为a的弧；的弧；qF标记为标记为q的顶点被用双层圈标出；的顶点被用双层圈标出；用标有用标有start的箭头指出的箭头指出M的开始状态。的开始状态。2023/3/9453.2.6正则表达式转换为状态转换图正则表达式转换为状态转换图s sr ra(a)对应的状态转换图对应的状态转换图(b)对应的状态转换图对应的状态转换图rr rsrr rr r(c)a对应的状态转换图对应的状态转换图(d)r|s对应的状态转换图对应的状态转换图(e)rs对应的状态转换图对应的状态转换图(h)rs*对应的状态转换图对应的状态转换图(g
37、)r+对应的状态转换图对应的状态转换图(f)r*对应的状态转换图对应的状态转换图图图3.8典型正则表达式对应的状态转换图典型正则表达式对应的状态转换图s2023/3/9463.2.6正则表达式转换为状态转换图正则表达式转换为状态转换图n转换过程如下：转换过程如下：n设置一个开始状态和一个终止状态，从开始状态设置一个开始状态和一个终止状态，从开始状态到终止状态引一条标记为待转换表达式的边；到终止状态引一条标记为待转换表达式的边；n检查图中边的标记，如果相应的标记不是字符、检查图中边的标记，如果相应的标记不是字符、或用或用“|”连接的字符和连接的字符和，则根据规则，则根据规则(1)-(8)(1)-
38、(8)进行替换，直到图中不再存在不满足要进行替换，直到图中不再存在不满足要求的边。按照习惯，如果一条边上标记的是求的边。按照习惯，如果一条边上标记的是，这个边就不用画出来。这个边就不用画出来。3.3单词的识别单词的识别3.3.1有穷状态自动机与单词识别的关系有穷状态自动机与单词识别的关系 n有穷状态自动机和正则文法等价，考虑到状态有穷状态自动机和正则文法等价，考虑到状态转换图的直观性，我们从状态转换图出发来考转换图的直观性，我们从状态转换图出发来考虑词法分析器的设计。虑词法分析器的设计。n允许在状态转换图的边上标记像允许在状态转换图的边上标记像digitdigit、letterletter这样
39、意义明确的符号，这样意义明确的符号，otherother表示例外表示例外情况情况473.3.1有穷状态自动机与单词识别的关系有穷状态自动机与单词识别的关系 n考虑到在识别单词的过程中需要执行一些动作，考虑到在识别单词的过程中需要执行一些动作，所以将这些动作标记标在基本的状态转换图上。所以将这些动作标记标在基本的状态转换图上。n如果到达终止状态，则意味着读入了一个与当如果到达终止状态，则意味着读入了一个与当前单词无关的字符，由于这个无关字符是下一前单词无关的字符，由于这个无关字符是下一个单词的开始符号，所以必须回退一个字符。个单词的开始符号，所以必须回退一个字符。状态上的状态上的*表示向前指针必
40、须回退一个字符。表示向前指针必须回退一个字符。482023/3/949例例3.14不同进制无符号整数的识别不同进制无符号整数的识别八进制数八进制数:(OCT，值，值)noct0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*十进制数十进制数:(DEC，值，值)ndec(1|.|9)(0|.|9)*|0十六进制数十六进制数:(HEX，值，值)nhex0 x(0|1|.|9|a|.|f|A|F)(0|.|9|a|.|f|A|F)*识别不同进制数的状态图识别不同进制数的状态图图图3.11 3.11 识别八进制无符号整数的状态转换图识别八进制无符号整数的状态转换图50识别不同进制
41、数的状态图识别不同进制数的状态图图图3.12 3.12 识别十进制无符号整数的状态转换图识别十进制无符号整数的状态转换图51识别不同进制数的状态图识别不同进制数的状态图图图3.13 3.13 识别十六进制无符号整数的状态转换图识别十六进制无符号整数的状态转换图52识别不同进制数的状态图识别不同进制数的状态图图图3.14 3.14 识别识别C C语言不同进制无符号整数的状态转换图语言不同进制无符号整数的状态转换图532023/3/9543.3.2单词识别的状态转换图表示单词识别的状态转换图表示 nlettern|letter|digitndigitn|digitn:=n|=|=|=n+|-|*|
42、/|*n:|,|;2023/3/9552023/3/956利用状态转换图识别单词利用状态转换图识别单词 从初始状态出发；从初始状态出发；读入一个字符；读入一个字符；按当前字符转入下一状态；按当前字符转入下一状态；重复重复-直到无法继续转移为止。直到无法继续转移为止。在遇到读入的字符是单词的分界符时，若当前在遇到读入的字符是单词的分界符时，若当前状态是终止状态，说明读入的字符组成了一个状态是终止状态，说明读入的字符组成了一个单词；否则，说明输入字符串单词；否则，说明输入字符串w不符合词法规不符合词法规则。则。2023/3/957利用状态转换图识别单词利用状态转换图识别单词 从初始状态出发；从初始
43、状态出发；读入一个字符；读入一个字符；按当前字符转入下一状态；按当前字符转入下一状态；重复重复-直到无法继续转移为止。直到无法继续转移为止。n在遇到读入的字符是单词的分界符时，若当前状态是终止状在遇到读入的字符是单词的分界符时，若当前状态是终止状态，说明读入的字符组成了一个单词；否则，说明输入字符态，说明读入的字符组成了一个单词；否则，说明输入字符串串w不符合词法规则。不符合词法规则。n如果从状态转换图的初始状态出发，分别沿着所有可能的路如果从状态转换图的初始状态出发，分别沿着所有可能的路径到达终止状态，并将每条路径上的标记依次连接成字符串，径到达终止状态，并将每条路径上的标记依次连接成字符串
44、，则可以得到状态转换图能够识别的所有单词，这些单词组成则可以得到状态转换图能够识别的所有单词，这些单词组成的集合也就是状态转换图识别的语言。的集合也就是状态转换图识别的语言。n读入字符读入字符a时从状态时从状态A转换到状态转换到状态B正好对应着一步推导过程，正好对应着一步推导过程，即即AaB，边正好与产生式，边正好与产生式(AaB)相对应相对应2023/3/958由正则文法构造状态转换图由正则文法构造状态转换图 以每个语法变量以每个语法变量(或其编号或其编号)为状态结点，开始符号对为状态结点，开始符号对应初始状态应初始状态S；增设一个终止状态增设一个终止状态T；对对G中每个形如中每个形如AaB
45、的产生式，从状态的产生式，从状态A到状态到状态B画一条有向弧，并标记为画一条有向弧，并标记为a；对对G中每个形如中每个形如Aa的产生式，从状态的产生式，从状态A到终止状态到终止状态T画一条标记为画一条标记为a的有向弧；的有向弧；对对G中每个形如中每个形如A的产生式，从状态的产生式，从状态A到终止状态到终止状态T画一条标记为画一条标记为any的有向弧，的有向弧，any表示表示T中的任何符中的任何符号。号。2023/3/9593.3.3几种典型的单词识别问题几种典型的单词识别问题 n标识符的识别标识符的识别n关键字的识别关键字的识别n常数的识别常数的识别n算符和分界符的识别算符和分界符的识别n回退
46、回退2023/3/9603.3.4状态转换图的实现状态转换图的实现 n如果将状态转换图看成是单词的识别规则库的话，如果将状态转换图看成是单词的识别规则库的话，则单词识别程序从当前状态则单词识别程序从当前状态(最初为初始状态最初为初始状态)出发，出发，读入一个输入字符后，将首先查询该规则库。读入一个输入字符后，将首先查询该规则库。n重复以下过程，直至到达某个终止状态。重复以下过程，直至到达某个终止状态。n如果从当前状态出发有一条边上标记了刚刚读入的输入字如果从当前状态出发有一条边上标记了刚刚读入的输入字符，则单词识别程序将转入这条边所指向的那个状态，并符，则单词识别程序将转入这条边所指向的那个状
47、态，并再读入一个输入字符；再读入一个输入字符；n否则调用出错处理程序；否则调用出错处理程序；n将从初始状态到该终止状态所经历的路径上的字符所组成将从初始状态到该终止状态所经历的路径上的字符所组成的字符串作为一个单词输出；的字符串作为一个单词输出；n并将当前状态重新置为开始状态，以便进行下一个单词的并将当前状态重新置为开始状态，以便进行下一个单词的识别；识别；n如果读完输入字符流后仍未进入某个终止状态则调用出错如果读完输入字符流后仍未进入某个终止状态则调用出错处理程序。处理程序。2023/3/9613.3.5词法分析程序的编写词法分析程序的编写n状态转移图状态转移图教材教材P93P93图图3.1
48、53.15n状态转移图的实现状态转移图的实现教材教材P105P105图图3.223.22n词法分析程序词法分析程序tokentoken_ _scanscan()()n输入：字符流输入：字符流n输出：输出：nsymbolsymbol:单词种别单词种别nattrattr:属性（全局变量）属性（全局变量）2023/3/962数据结构与子例程数据结构与子例程n数据结构数据结构nch字符变量，存放当前读入的输入字符字符变量，存放当前读入的输入字符ntoken字符串变量，存放构成单词的字符串字符串变量，存放构成单词的字符串nsymbol单词种别（词法分析子程序的返回值）单词种别（词法分析子程序的返回值）n
49、attr属性（全局变量）属性（全局变量）n子例程子例程ninstall_id(token):将将token存入符号表，返回入口指针存入符号表，返回入口指针ngetchar():从输入缓冲区中读入一个字符放入从输入缓冲区中读入一个字符放入chnretract():将向前指针回退一个字符，将将向前指针回退一个字符，将ch置为空白符置为空白符ncopytoken():返回输入缓冲区中从开始指针返回输入缓冲区中从开始指针lexeme_beginning到向前指针到向前指针forward之间的字符串之间的字符串nisLetter()isalpha()isalnum()2023/3/963图图3.15的状
50、态转换图的实现算法的状态转换图的实现算法ntokentoken_scan()ncharch;nchar*token;nch=getchar();nwhile(ch=blank|ch=tab|ch=newline)nch=getchar();nlexeme_beginning+;nnif(isalpha(ch)ch=getchar();nwhile(isalnum(ch)nch=getchar();nretract(1);ntoken=copytoken();nreturn(gettoken(token),install_id(token);2023/3/964nelsenif(isdigit(