正则表达式学习.pptx

《正则表达式学习.pptx》由会员分享，可在线阅读，更多相关《正则表达式学习.pptx（76页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/4/191第3章 词法分析3.1词法分析器的功能3.2单词的描述3.3单词的识别3.4词法分析程序的自动生成3.5本章小结第1页/共76页2023/4/1923.1 词法分析器的功能功能：输入源程序，输出单词符号(token)。即：把构成源程序的字符串转换成“等价的”单词(记号)序列根据词法规则识别及组合单词，进行词法检查对数字常数完成数字字符串到二进制数值的转换删去空格字符和注释第2页/共76页2023/4/193单词的分类与表示单词的分类与表示词法分析器的输出词法分析器的输出 一、单词的种类一、单词的种类 1.关键字关键字:也称基本字，也称基本字，begin、end、for、do

2、.2.标识符标识符:由用户定义，表示各种名字由用户定义，表示各种名字3.常数常数:整常数、实常数、布尔常数、字符串常数等整常数、实常数、布尔常数、字符串常数等4.运算符运算符:算术运算符算术运算符+、-、*、/等；逻辑运算符等；逻辑运算符not、or与与and等；关系运算符等；关系运算符=、和和 等等 5.分界符分界符:，、；、（、），、；、（、）.第3页/共76页2023/4/194二、单词的内部形式二、单词的内部形式几种常用的单词内部形式：几种常用的单词内部形式：1 1、按单词种类分类、按单词种类分类2 2、保留字和分界符采用一符一类、保留字和分界符采用一符一类3 3、标识符和常数的单词值

3、又为指示字、标识符和常数的单词值又为指示字（指针值）（指针值）种别种别 属性值属性值表示单词的种类，可用整表示单词的种类，可用整数编码或记忆符表示数编码或记忆符表示不同的单词不同的值不同的单词不同的值第4页/共76页2023/4/195单词名称单词名称标识符标识符无符号常数无符号常数(整整)无符号浮点数无符号浮点数布尔常数布尔常数字符串常数字符串常数保留字保留字分界符分界符类别编码类别编码1 12 23 34 45 56 67 7单词值单词值内部字符串内部字符串整数值整数值数值数值0 0 或或 1 1内部字符串内部字符串保留字或内部编码保留字或内部编码分界符或内部编码分界符或内部编码1、按单词

4、种类分类、按单词种类分类第5页/共76页2023/4/1962 2、保留字和分界符采用一符一类、保留字和分界符采用一符一类单词名称单词名称标识符标识符无符号常数无符号常数(整整)无符号浮点数无符号浮点数布尔常数布尔常数字符串常数字符串常数BEGINBEGINENDENDFORFORDODO:+*,(类别编码类别编码1 12 23 34 45 56 67 78 89 92020212122222323单词值单词值内部字符串内部字符串整数值整数值数值数值0 0 或或 1 1内部字符串内部字符串-第6页/共76页2023/4/197例3.1 语句if count7 then result:=3.14

5、的单词符号序列(IF，0)(ID，指向count 的符号表入口)(GT，0)(INT，7)(THEN，0)(ID，指向result的符号表入口)(ASSIGN，0)(REAL，3.14)(SEMIC，0)跟实现有关第7页/共76页2023/4/198源程序的输入缓冲与预处理 超前搜索和回退双字符运算符（*,/*,:=,）DO 90 k=1,10DO 90 k=1.10 缓冲区假定源程序存储在磁盘上，这样每读一个字符就需要访问一次磁盘，效率显然是很低的。空白字符的剔除剔除源程序中的无用符号、空格、换行、注释等第8页/共76页2023/4/199源程序的输入缓冲与预处理(续)工作区工作区(toke

6、n)(token)(token)(token)单词开始指针单词开始指针扫描指针扫描指针正拼单词正拼单词输入缓冲区第9页/共76页2023/4/1910每次移动向前指针都需要每次移动向前指针都需要做两次测试做两次测试源程序的输入缓冲与预处理(续)双缓冲区问题_超前扫描导致的效率问题n n问题：如何设计和实现扫描器？问题：如何设计和实现扫描器？n n大小问题大小问题128Byte*2|1024Byte*2|4096Byte*2128Byte*2|1024Byte*2|4096Byte*2if forward在缓冲区第一部分末尾在缓冲区第一部分末尾 then begin重装缓冲区第二部分重装缓冲区第

7、二部分;forward:=forward+1endelse if forward在缓冲区第二部分末尾在缓冲区第二部分末尾 then begin 重装缓冲区第一部分重装缓冲区第一部分;将将forward移到缓冲区第一部分开始移到缓冲区第一部分开始endelse forward:=forward+1;forward:=forward+1;if forward=eof then beginif forward在第一部分末尾在第一部分末尾 then begin 重装第二部分重装第二部分;forward:=forward+1endelse if forward在第二部分末尾在第二部分末尾 then be

8、gin 重装第一部分重装第一部分;将将forward 移到第一部分开始移到第一部分开始endelse /*eof 在表示输入结束在表示输入结束*/终止词法分析终止词法分析end 第10页/共76页2023/4/1911词法分析阶段的错误处理 1非法字符检查2关键字拼写错误检查3不封闭错误检查4重复说明检查5错误恢复与续编译紧急方式恢复(panic-mode recovery)反复删掉剩余输入最前面的字符，直到词法分析器能发现一个正确的单词为止。第11页/共76页2023/4/1912词法分析器的位置 目标程序词法分析器语法分析器语义分析与代码生成目标代码整理图3.4以语法分析器为中心源程序符号

9、表以语法分析器为中心的优点：简化编译器的设计。提高编译器的效率。增强编译器的可移植性。第12页/共76页2023/4/19133.2 单词的描述正则文法正则文法G=(V，T，P，S)中，对P，均具有形式Aw或AwB(Aw或ABw)，其中A，BV，wT+。例3.2标识符的文法约定：用digit表示数字：0,1,2,9;用letter表示字母：A,B,Z,a,b,z|A|B|Z|a|b|z0|1|2|9第13页/共76页2023/4/1914正则表达式例3.2：标识符的另一种表示letter(letter|digit)*|表示或*表示Kleene闭包+表示正闭包？表示“0或1个”Letter和(l

10、etter|digit)*的并列表示两者的连接正则式r表示正则集,相应的正则集记为L(r)第14页/共76页2023/4/1915正则表达式(续)RE定义3.1设是一个字母表，则上的正则表达式及其所表示的正则语言可递归地定义如下：是上的一个正则表达式，它表示空集；是上的一个正则表达式，它表示语言；对于a(a)，a是上的一个正则表达式，它表示的正则语言是a；假设r和s都是上的正则表达式，它们表示的语言分别为L(r)和L(s)，则：(r)也是上的正则表达式，它表示的语言为L(r)；(r|s)也是上的正则表达式，它表示的语言为L(r)L(s)；(rs)也是上的正则表达式，它表示的语言为L(r)L(s

11、)；(r*)也是上的正则表达式，它表示的语言为(L(r)*；只有经有限次使用上述规则构造的表达式才是上的正则表达式。第15页/共76页2023/4/1916正则表达式中的运算优先级运算优先级和结合性:*高于“连接”和|，“连接”高于|具有交换律、结合律“连接”具有结合律、和对|的分配律()指定优先关系意义清楚时，括号可以省略例：1.L(a|b)*)=L(a*|b*)*)=x|x是a和b构成的符号串，包括2.L(a|a*b)=a,b,ab,aab,aaab,aaaab,.第16页/共76页2023/4/1917正则表达式与正则文法的等价性正则表达式与正则文法等价对任意一个正则表达式，存在一个定义

12、同一语言的正则文法对任意一个正则文法，存在一个定义同一语言的正则表达式第17页/共76页2023/4/1918根据正则文法构造等价的正则表达式 问题：给定正则文法G，构造一个正则表达式r，使得L(r)=L(G)基本思路为正则文法的每个产生式构造一个正则表达式方程式，这些方程式中的变量是文法G中的语法变量，各变量的系数是正则表达式，简称为方程式。从而得到一个联立方程组。用代入消元法消去联立方程组中除开始符号外的其他变量，最后得到关于开始符号S的解：S=r，r即为所求的正则表达式。第18页/共76页2023/4/1919根据正则文法构造等价的正则表达式 具体步骤(1)根据正则文法G构造正则表达式联

13、立方程组。假设正则文法G是右线性的，其每个产生式的右部只含有一个终结符，则有如下方程式构造规则：对形如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。第19页/共76页2023/4/1920根据正则文法构造等价的正则表达式(2)解联立方程组，求等价的正则表达式r用代入消元法逐个消去方程组中除开始符号S外的其他变量，最后即可得到关于开始符号S的解。代入消元规则如下：如果有A=r1B|r2B|

14、rnB，则用A=(r1|r2|rn)B替换之，其中BA；如果有A=t1A|t2A|tmA，则用A=(t1|t2|tm)*A替换之；第20页/共76页2023/4/1921根据正则文法构造等价的正则表达式 如果有A=(r1|r2|rn)B，B=(t1|t2|tm)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=(t

15、1|t2|tm)*A且A=r1|r2|rn则用A=(t1|t2|tm)*(r1|r2|rn)替换之；第21页/共76页2023/4/1922根据正则文法构造等价的正则表达式 如果有A=1、A=2、A=h，则用A=1|2|h代替之。如果最后得到的关于S的方程式为如下形式，S=1|2|h则将方程式右边所有其中仍然含有语法变量的i(1in)删除，得到的结果就是与G等价的正则表达式；如果任意的i(1in)均含有语法变量，则就是与G等价的正则表达式。第22页/共76页2023/4/1923根据正则文法构造等价的正则表达式 例3.6将如下文法G转换成相应的正则表达式SaS|aBBbB|bC|aB|bSCc

16、C|c1.列方程组S=a*S S=aB B=(a|b)*B B=bCB=bS C=c*C C=c2.代入法解方程组C=c*c B=bc*c|bc B=(a|b)*(bc*c|bc)B=(a|b)*bS S=a*aBS=a*a(a|b)*bS|a*a(a|b)*(bc*c|bc)S=(a*a(a|b)*b)*a*a(a|b)*(bc*c|bc)如果用正闭包表示，则为(a+(a|b)*b)*a+(a|b)*(bc+|bc)第23页/共76页2023/4/1924将正则表达式转换成等价的正则文法 问题：给定上的一个正则表达式r，根据r构造正则文法G，使得L(G)=L(r)定义3.3设字母表为，A、B

17、、C为语法变量集合，对于上的任意正则表达式r，形如Ar的式子称为正则定义式；如果r是中的字母和用正则定义式定义的变量组成的正则表达式，则形如Ar的式子称为正则定义式。第24页/共76页2023/4/1925将正则表达式转换成等价的正则文法 按如下方法构造正则定义式，并逐步将其转换成正则文法引入开始符号S，从如下正则定义式开始Sr按如下规则将Sr分解为新的正则定义式，在分解过程中根据需要引入新的语法变量第25页/共76页2023/4/1926将正则表达式转换成等价的正则文法Ar是正则定义式，则对Ar的分解规则如下：如果r=r1r2，则将Ar分解为Ar1B，Br2，BV；如果r=r1*r2，则将A

18、r分解为Ar1A，Ar2；如果r=r1r2，则将Ar分解为Ar1，Ar2。不断应用分解规则到对各个正则定义式进行分解，直到每个正则定义式右端只含一个语法变量(即符合正则文法产生式的形式)为止。第26页/共76页例3.9 正则表达式到正则文法的转换a(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|B=aB|bB|.C|_CC=aA|bAS SaAaA|aBaB A AaAaA|bAbA|B BaBaB|bBbB|.|.C C|_|_C CC CaA

19、aA|bAbA27第27页/共76页例 3.10 标识符定义的转换引入SSletter(letter|digit)*分解为SletterAA(letter|digit)A|执行连接对|的分配律SletterAAletterA|digitA|28第28页/共76页高级语言词法的简单描述词法单词符号的文法，用来描述高级语言中的：标识符、常数、运算符、分界符、关键字参考教材P73-77，了解如何定义高级语言中的整数、实数等的相应正则文法。29第29页/共76页2023/4/1930例 3.7 某简易语言的词法正则定义式 词法规则 单词种别 属性(|)*IDN 符号表入口 ()*NUM 数值 :=AS

20、G无 其它单词字符本身 单词名称 无 第30页/共76页2023/4/1931变换为正规文法letter|letter|digitdigit|digit:=+=(其它：实数、算术运算符、关系运算符、分号、括号等）问题：如问题：如何识别记何识别记号？号？第31页/共76页2023/4/1932有穷状态自动机具有离散输入输出的系统的数学模型具有有穷个内部状态系统只需根据当前所处的状态和面临的输入就能确定后继的行为，处理完当前输入后系统的状态将发生变化具有初始状态和终止状态例：电梯、文本编辑程序、词法分析程序第32页/共76页有穷自动机的物理模型有穷状态有穷状态控制器控制器输入带输入带读头读头设想有

21、个按钮，自设想有个按钮，自动机启动后一个动动机启动后一个动作一个动作地做下作一个动作地做下去，去，直到没有，直到没有输入。如果停在终输入。如果停在终态，接收；如果停态，接收；如果停在非终态，不接收在非终态，不接收一个动作：一个动作：pp，aqaq，读头前进一格，读头前进一格FAFA接收的符号接收的符号行的集合即为行的集合即为其其接收的语言接收的语言33第33页/共76页2023/4/1934有穷自动机的用处有穷自动机是许多重要类型的硬件和软件的有用模型数字电路的设计和检查软件典型编译器的词法分析器扫描大量文本来发现单词、短语或其他模式的出现的软件所有只有有穷个不同状态的系统（如通信协议或安全交

22、换信息的协议）的验证软件第34页/共76页2023/4/1935例：一个奇偶校验器q q0 00 00 01 11 1q q1 1测试输入中测试输入中1 1的个数的奇偶性，并且只接的个数的奇偶性，并且只接收含有奇数个收含有奇数个1 1的那些输入串。的那些输入串。问题：有穷自动机的形式描述？问题：有穷自动机的形式描述？关键是如何描述动作？关键是如何描述动作？注意：状态有注意：状态有记忆功能，记记忆功能，记住输入串的部住输入串的部分特征。分特征。第35页/共76页2023/4/1936确定的有穷自动机的形式定义定义3.4一个确定的有穷自动机M（记作DFAM）是一个五元组（，0，），其中是一个有穷状

23、态集合。是一个字母表，它的每个元素称输入符号。0，0称为初始状态。，称为终止状态集合。是一个从到的单值映射(p，a)（p,q，a）表示当前状态为p,输入符号为a时，自动机将转换到下一个状态q，q称为p的一个后继。第36页/共76页2023/4/1937DFA的表示例设（，a，b，）其中：（，a），（，a）3（，a），（，a）（，b），（，b）（，b），（，b）一个有三种表示：（1）转换函数；（2）转移矩阵；（3）状态转换图。第37页/共76页2023/4/1938转移矩阵转移矩阵0132aaaabbbb3状态转换图状态转换图易存储易存储第38页/共76页2023/4/1939从状态转换图看，从

24、初态从状态转换图看，从初态出发，沿任一条路径到达出发，沿任一条路径到达接受状态，这条路径上的接受状态，这条路径上的弧上的标记符号连接起来弧上的标记符号连接起来构成的符号串被接受。构成的符号串被接受。如：如：abab0123aaaabbbbDFA M接受的语言接受的语言问题：如何形式描述问题：如何形式描述DFA接收的语言？接收的语言？第39页/共76页2023/4/1940DFA M接受的语言如果对所有*，a，q以下述方式递归地扩展的定义（q，）q，(q，wa）(q，w），a），则M所接收的语言为：()ww*，且(q，w)对于上页例中的DFA M和w=baa，(0，baa）=(2,aa）=(1,

25、a）=3第40页/共76页2023/4/1941非确定的有穷自动机NFA M定义3.6非确定的有穷自动机是一个五元组M（，q，）其中，q，的意义和DFA的定义一样，而是一个从到的子集的映射，即：，其中S=。类似于DFA，NFAM亦可用状态转换图表示，同样也可以定义NFAM接受的语言。第41页/共76页2023/4/1942DFA M 的模拟算法输入：以eof结尾的串x，DFAM=(Q，q0，F)；输出：如果M接受x则输出“yes”，如果M不接受x则输出“no”步骤：1s=q0;2c=getchar(x);3while(c!=eof)4s=move(s,c);5c=getchar(x);67if

26、sFreturn“yes”8elsereturn“no”;第42页/共76页2023/4/1943状态转换图定义3.7设M=(Q，q0，F)为一个有穷状态自动机，满足如下条件的有向图被称为M的状态转换图(transitiondiagram)：qQq是该有向图中的一个顶点；(q，a)=p图中有一条从顶点q到顶点p的标记为a的弧；qF标记为q的顶点被用双层圈标出；用标有start的箭头指出M的开始状态。第43页/共76页2023/4/1944正则表达式转换为状态转换图s sr ra(a)对应的状态转换图对应的状态转换图(b)对应的状态转换图对应的状态转换图rr rsrr rr r(c)a对应的状态

27、转换图对应的状态转换图(d)r|s对应的状态转换图对应的状态转换图(e)rs对应的状态转换图对应的状态转换图(h)rs*对应的状态转换图对应的状态转换图(g)r+对应的状态转换图对应的状态转换图(f)r*对应的状态转换图对应的状态转换图 图图3.8 典型正则表达式对应的状态转换图典型正则表达式对应的状态转换图s第44页/共76页2023/4/1945正则表达式转换为状态转换图转换过程如下：设置一个开始状态和一个终止状态，从开始状态到终止状态引一条标记为待转换表达式的边；检查图中边的标记，如果相应的标记不是字符、或用“|”连接的字符和，则根据规则(1)-(8)进行替换，直到图中不再存在不满足要求

28、的边。按照习惯，如果一条边上标记的是，这个边就不用画出来。第45页/共76页3.3 单词的识别有穷状态自动机与单词识别的关系 有穷状态自动机和正则文法等价，考虑到状态转换图的直观性，我们从状态转换图出发来考虑词法分析器的设计。允许在状态转换图的边上标记像digit、letter这样意义明确的符号，other表示例外情况46第46页/共76页有穷状态自动机与单词识别的关系 考虑到在识别单词的过程中需要执行一些动作，所以将这些动作标记标在基本的状态转换图上。如果到达终止状态，则意味着读入了一个与当前单词无关的字符，由于这个无关字符是下一个单词的开始符号，所以必须回退一个字符。状态上的*表示向前指针

29、必须回退一个字符。47第47页/共76页2023/4/1948例 3.14 不同进制无符号整数的识别八进制数:(OCT，值)oct0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*十进制数:(DEC，值)dec(1|.|9)(0|.|9)*|0十六进制数:(HEX，值)hex0 x(0|1|.|9|a|.|f|A|F)(0|.|9|a|.|f|A|F)*第48页/共76页识别不同进制数的状态图图图3.11 3.11 识别八进制无符号整数的状态转换图识别八进制无符号整数的状态转换图49第49页/共76页识别不同进制数的状态图图图3.12 3.12 识别十进制无符号整数的状态

30、转换图识别十进制无符号整数的状态转换图50第50页/共76页识别不同进制数的状态图图图3.13 3.13 识别十六进制无符号整数的状态转换图识别十六进制无符号整数的状态转换图51第51页/共76页识别不同进制数的状态图图图3.14 3.14 识别识别C C语言不同进制无符号整数的状态转换图语言不同进制无符号整数的状态转换图52第52页/共76页2023/4/1953单词识别的状态转换图表示 letter|letter|digitdigit|digit:=|=|=|=+|-|*|/|*:|,|;第53页/共76页2023/4/1954第54页/共76页2023/4/1955利用状态转换图识别单词

31、 从初始状态出发；读入一个字符；按当前字符转入下一状态；重复-直到无法继续转移为止。在遇到读入的字符是单词的分界符时，若当前状态是终止状态，说明读入的字符组成了一个单词；否则，说明输入字符串w不符合词法规则。第55页/共76页2023/4/1956利用状态转换图识别单词 从初始状态出发；读入一个字符；按当前字符转入下一状态；重复-直到无法继续转移为止。在遇到读入的字符是单词的分界符时，若当前状态是终止状态，说明读入的字符组成了一个单词；否则，说明输入字符串w不符合词法规则。如果从状态转换图的初始状态出发，分别沿着所有可能的路径到达终止状态，并将每条路径上的标记依次连接成字符串，则可以得到状态转

32、换图能够识别的所有单词，这些单词组成的集合也就是状态转换图识别的语言。读入字符a时从状态A转换到状态B正好对应着一步推导过程，即AaB，边正好与产生式(AaB)相对应第56页/共76页2023/4/1957由正则文法构造状态转换图 以每个语法变量(或其编号)为状态结点，开始符号对应初始状态S；增设一个终止状态T；对G中每个形如AaB的产生式，从状态A到状态B画一条有向弧，并标记为a；对G中每个形如Aa的产生式，从状态A到终止状态T画一条标记为a的有向弧；对G中每个形如A的产生式，从状态A到终止状态T画一条标记为any的有向弧，any表示T中的任何符号。第57页/共76页2023/4/1958几

33、种典型的单词识别问题 标识符的识别关键字的识别常数的识别算符和分界符的识别回退第58页/共76页2023/4/1959状态转换图的实现 如果将状态转换图看成是单词的识别规则库的话，则单词识别程序从当前状态(最初为初始状态)出发，读入一个输入字符后，将首先查询该规则库。重复以下过程，直至到达某个终止状态。如果从当前状态出发有一条边上标记了刚刚读入的输入字符，则单词识别程序将转入这条边所指向的那个状态，并再读入一个输入字符；否则调用出错处理程序；将从初始状态到该终止状态所经历的路径上的字符所组成的字符串作为一个单词输出；并将当前状态重新置为开始状态，以便进行下一个单词的识别；如果读完输入字符流后仍

34、未进入某个终止状态则调用出错处理程序。第59页/共76页2023/4/1960词法分析程序的编写状态转移图教材P93图3.15状态转移图的实现教材P105图3.22词法分析程序token_scan()输入：字符流输出：symbol:单词种别attr:属性（全局变量）第60页/共76页2023/4/1961数据结构与子例程数据结构ch字符变量，存放当前读入的输入字符token字符串变量，存放构成单词的字符串symbol单词种别（词法分析子程序的返回值）attr属性（全局变量）子例程install_id(token):将token存入符号表，返回入口指针getchar():从输入缓冲区中读入一个字

35、符放入chretract():将向前指针回退一个字符，将ch置为空白符copytoken():返回输入缓冲区中从开始指针lexeme_beginning到向前指针forward之间的字符串isLetter()isalpha()isalnum()第61页/共76页2023/4/1962图3.15的状态转换图的实现算法tokentoken_scan()charch;char*token;ch=getchar();while(ch=blank|ch=tab|ch=newline)ch=getchar();lexeme_beginning+;if(isalpha(ch)ch=getchar();whi

36、le(isalnum(ch)ch=getchar();retract(1);token=copytoken();return(gettoken(token),install_id(token);第62页/共76页2023/4/1963elseif(isdigit(ch)ch=getchar();while(isdigit(ch)ch=getchar();retract(1);token=copytoken();return(INT,install_num(token);elseswitch(ch)case*:ch=getchar();if(ch=*)return(EXP,0);elseretr

37、act(1);return(MULTI,0);break;第63页/共76页2023/4/1964case:ch=getchar();if(ch=)return(ASSIGN,0);elseretract(1);return(COLON,0);break;case)return(NE,0);elseretract(1);return(LT,0);break;case=:return(EQ,0);break;case:ch=getchar();if(ch=)return(GE,0);elseretract(1);return(GT,0);break;case+:return(PLUS,0);br

38、eak;case-:return(MINUS,0);break;case/:return(RDIV,0);break;case,:return(COMMA,0);break;case;:return(SEMIC,0);break;default:error_handle();break;return;第64页/共76页2023/4/1965需要说明的问题缓冲区预处理，超前搜索关键字的处理，符号表的实现Install_id()：查找效率，算法的优化实现词法错误处理由于高级语言的词组成的集合为3型语言，所以，这里讨论的词法分析技术可以用于处理所有的3型语言，也就是所有的可以用3型文法描述的语言。如

39、：信息检索系统的查询语言、命令语言等第65页/共76页2023/4/19663.4 词法分析程序的自动生成图图3.233.23利用利用LexLex建立词法分析程序的过程建立词法分析程序的过程第66页/共76页2023/4/1967源程序声明部分(正规定义式)%识别规则部分(识别规则)%辅助过程部分%常量定义常量定义%正规定义正规定义第67页/共76页2023/4/1968源程序1、正规定义式letterA|B|C|Z|a|b|c|zdigit0|1|2|9identifierletter(letter|digit)*integerdigit(digit)*2、识别规则 正规式动作描述token

40、1action1token2action2tokennactionn第68页/共76页2023/4/1969%#include#define ID1#define INT2#define EXP3#define MULTI4#define COLON5#define EQ6#define NE7#define LE8#define GE9#define LT10#define GT11#define PLUS12#define MINUS13#define RDIV14#define COMMA15#define SEMIC16#define RELOP17#define ASSGIN18in

41、t line_no=1;%delimtnwsdelim+lettera-zA-Zdigit0-9idletter(letter|digit)*numberdigit+%ws;beginreturn(BEGIN);endreturn(END);ifreturn(IF);thenreturn(THEN);elsereturn(ELSE);doreturn(DO);programreturn(PROGRAM);id yyval=install_id();return(ID);number yyval=install_num();return(INT);第69页/共76页2023/4/1970yyva

42、l=LT;return(RELOP);yyval=GT;return(RELOP);=“yyval=GE;return(RELOP);“yyval=NE;return(RELOP);+return(PLUS);-return(MINUS);*return(MULTI);/return(RDIV);*return(EXP);:return(COLON);:=return(ASSGIN);,return(COMMA);return(SEMIC);nline_no+;.fprintf(stderr,%c(0%o):illegalcharcteratline%dn,yytext0,yytext0,li

43、ne_no);%install_id()install_num()第70页/共76页2023/4/1971LEX二义性问题的两条原则二义性问题的两条原则1.最长匹配原则最长匹配原则 在识别单词过程中，有一字符串在识别单词过程中，有一字符串 x x x x x 根据最长匹配原则，应识别为这是根据最长匹配原则，应识别为这是 一个符合一个符合Pk规则的单词，规则的单词，而不是而不是Pj和和Pi规则的单词。规则的单词。PjPiPk2.优先匹配原则优先匹配原则 如果有一字符串有两条规则可以同时匹配时，那么用规则如果有一字符串有两条规则可以同时匹配时，那么用规则序列中位于前面的规则相匹配，所以排列在最前面

44、的规则优先序列中位于前面的规则相匹配，所以排列在最前面的规则优先权最高。权最高。如:begin:=第71页/共76页2023/4/1972Lex的功能是根据的功能是根据Lex源程序构造一个词法分析程序，源程序构造一个词法分析程序，该词法分析器实质上是一个有穷自动机。该词法分析器实质上是一个有穷自动机。Lex的功能是根据的功能是根据Lex源程序生成状态转换矩阵和控制程序源程序生成状态转换矩阵和控制程序的实现原理的实现原理图图 3.243.24LexLex生成的词法分析器结构生成的词法分析器结构第72页/共76页2023/4/1973三点说明三点说明1)以上是以上是Lex的构造原理，虽然是原理性的

45、，的构造原理，虽然是原理性的，但据此就不难将但据此就不难将Lex构造出来。构造出来。2)所构造出来的所构造出来的Lex是一个通用的工具，是一个通用的工具，用它可以生成各种语言的词法分析程序，用它可以生成各种语言的词法分析程序，只需要根据不同的语言书写不同的只需要根据不同的语言书写不同的LEX源文件源文件 就可以了。就可以了。3)Lex不但能自动生成词法分析器，不但能自动生成词法分析器，而且也可以产生多种模式识别器及文本编辑程序等而且也可以产生多种模式识别器及文本编辑程序等第73页/共76页2023/4/1974本章小结词法分析器接收表示源程序的“平滑字符流”，输出与之等价的单词序列；单词被分成多个种类，并被表示成(种别，属性值)的二元组形式；为了提高效率，词法分析器使用缓冲技术，而且在将字符流读入缓冲区时，是经过剔除注解、无用空白符等预处理后的结果；第74页/共76页2023/4/1975本章小结单词的识别相当于正则语言的识别；词法的等价描述形式有正则文法、有穷状态自动机、正则表达式，其中有穷状态自动机可以用状态转换图表示；实现词法分析器时状态转换图是一个很好的设计工具，根据该图，容易构造出相应的分析程序；使用恰当的形式化描述，可以实现词法分析器的自动生成，Lex就是一种自动生成工具。第75页/共76页感谢您的观看！第76页/共76页