编译原理词法1(正规表达式与有限自动机简介).ppt

第 2 讲,编译原理,西北农林科技大学本科教程,主讲教师：赵建邦,第二章词法分析前三节2.1 词法分析器的设计方法2.2 一个简单的词法分析器2.3 正规表达式与有限自动机简介重点掌握 状态转换图的概念正规表达式的概念和运算,本讲目标,第二章 词法分析,2.1 词法分析器的设计方法2.2 一个简单的词法分析器2.3 正规表达式与有限自动机简介2.4 正规表达式到有限自动机的构造2.5 词法分析器的自动生成,回顾词法分析器：定位词法分析是编译的第一个阶段任务从左至右逐个字符地对源程序进行扫描，产生一个个单词（Token）符号功能输入源程序，输出单词符号（流）不断访问、更新符号表,2.1 词法分析器的设计方法,词法分析器的处理结构（2种）：第一种：词法分析器和语法分析器完全分开词法分析器的输出（单词符号流）作为语法分析器的输入 将词法分析工作作为独立的一遍来完成，在这个过程中不断查询和完善符号表,2.1 词法分析器的设计方法,图2-1(a)词法分析程序作为主程序,词法分析器的处理结构（2种）：第二种：词法分析器作为语法分析器调用的子程序每当语法分析器需要一个单词时便调用词法分析器词法分析和语法分析交替进行,2.1 词法分析器的设计方法,图2-1(b)词法分析程序作为子程序,：单词符号的分类与输出形式分类：单词符号是程序语言的基本语法单位，具有确定的语法意义。程序语言的单词符号通常可分为下面五种：保留字：如C语言中的if、else、while和do等几乎所有的程序语言都禁止用户使用保留字作为标识符标识符：用户自己定义的常量名、变量名、方法名等常数：布尔常数（true/false）和其它常数运算符：“+”、“-”、“*”、“/”、“”、“”等界符：在语言中是作为语法上的分界符号使用的，如“,”、“;”、“(”、“)”、“=”等,2.1 词法分析器的设计方法,：单词符号的分类与输出形式输出形式：单词符号通常表示成如下的二元式：（单词种别，单词自身的值/内码值）1、单词种别：即单词的种类。为了处理方便，通常让每种单词对应一个整数码，可以最大限度地将每个单词区别开来保留字：可以统一视为一种，也可一字一种（后一种较常用）标识符：统一归为一种常数：可统一归为一种或按照整型、实型、布尔型等分为几种运算符和界符可统一归为一种或采用一符一种,2.1 词法分析器的设计方法,：单词符号的分类与输出形式2、单词自身的值如果一个种别只含一个单词符号，对于这个单词符号，种别编码就完全代表它自身的值如果一个种别含有多个单词符号，除了给出种别编码之外，还应给出单词符号自身的值，以便区分同一种类的单词,2.1 词法分析器的设计方法,注意，标识符自身的值就是标识符自身的字符串，而常数自身的值是常数本身的二进制数值（第一种）。也可用指向某类表格中一个特定项目的指针来区分同类中的不同单词。例如，对于标识符，可以用它在符号表的入口指针作为它自身的值；而常数也可用它在常数表的入口指针作为它自身的值（第二种）。,例如：if(a1)b=100;如果采用每种单词对应一个整数码，对应的二元式序列？假如五类单词的种别规定如下：保留字if种别：2标识符种别：10常量种别：11“=”种别：17“”种别：23“;”种别：26“(”种别：29“)”种别：30,10,2.1 单词符号分类举例,上面的子程序输出的二元式序列：(2,）if(29,)(10,a)a(23,)(11,1的二进制）1(30,)(10,b)b(17,)=(11,100的二进制)100（26，);,采用第一种表示,：状态转换图（概念）上一小节解决了单词符号的表示，但是如何识别单词呢？答：借助“状态转换图”在词法分析中，可以用状态转换图来识别单词。状态转换图是状态有限的有向图，结点代表状态，用圆圈表示；结点之间可由有向边连接，代表状态转换关系，有向边上可标记字符，表示前一状态接受某一个字符之后的状态转移,2.1 词法分析器的设计方法,例如，右图表示在状态i下的状态转换：若输入字符为x，则读入x并转换到状态j；若输入字符为y，则读入y并转换到状态k。,：状态转换图（表示）状态转换图的要求状态（即结点）个数有限至少一个初始状态，若干终止状态每条边上标有字符（也可以是空字符）状态转换图的表示习惯初始状态用“”表示非终止状态用“”表示状态之间的跳转用“”（有向边）表示终止状态用“*”表示,2.1 词法分析器的设计方法,：状态转换图（表示）特别说明：终止状态用“*”表示某些终止状态是在读入了一个其它不属于该单词的符号后才得到相应的单词编码的，这表明在识别单词的过程中多读入了一个符号，所以识别出单词后应将最后多读入的这个符号予以回退；我们对此类情况的处理是在终态上以“*”作为标识。,2.1 词法分析器的设计方法,：状态转换图（举例）,2.1 词法分析器的设计方法,标识符,无符号整数,无符号数字,图2-4(a)含分支的状态i,2.1 词法分析器的设计方法,图2-4(b)含回路的状态i,：状态转换图（编程）含分支的状态对应一个switch()语句或对应一组if-else语句含回路的状态对应一个while语句终态对应一个return()语句意味着从词法分析器返回到调用段，一般指返回到语法分析器,第二章 词法分析,2.1 词法分析的设计方法2.2 一个简单的词法分析器2.3 正规表达式与有限自动机简介2.4 正规表达式到有限自动机的构造2.5 词法分析器的自动生成,2.2 一个简单的词法分析器示例,大多数程序语言的单词符号都可以用状态转换图予以识别构造一个C语言子集的词法分析器：定义C语言子集的单词符号及内码值C语言子集对应的状态转换图状态转换图的代码实现,：C语言子集的单词符号表示使用种别编码不利于记忆，故使用助记符和种别编码对应,2.2 一个简单的词法分析器示例,：C语言子集的单词符号表示,2.2 一个简单的词法分析器示例,：C语言子集对应的状态转换图对输出程序串预处理在设计的状态转换图中，首先对输入串做预处理，即剔除多余的空白符(在实际的词法分析中，预处理还包括剔除注释和制表换行符等编辑性字符的工作)，使词法分析工作既简单又清晰。将保留字作为一类特殊的标识符来处理即对保留字不专设对应的状态转换图，当转换图识别出一个标识符时就去查对表2.1的前五项，确定它是否为一个保留字。当然，也可以专设一个保留字表来进行处理。,2.2 一个简单的词法分析器示例,图2-5 简单词法分析的状态转换图,返回（id，id在符号表中的位置）或返回（保留字，）,返回（num，num在常数表中的位置）,返回（+，）,返回（=，）,返回（relop，EQ）,返回（;）,返回（）,非法字符错,21,：C语言子集对应的状态转换图特别注意：状态2在识别标识符和保留字时：1、先看识别出的单词是否是保留字，否则是标识符2、如果是标识符，查符号表中是否已有，如果表中没有此标识符，将此标识符登录到符号表中，并返回（id,id在符号表中的位置/入口指针）；若表中已有此标识符，给出重名错误信息。,2.2 一个简单的词法分析器示例,：状态转换图的实现实现方法：让每个状态对应一小段程序含分支多的状态对应switch()语句，分支少的对应if-else含回路的状态对应一个while语句注意：结合图2-5，读懂课本P14-P16的代码character:单个字符，token:单词符号的字符串getbe()和getchar()的使用区别reserve():如果token保存的是保留字，则返回编码（1-5），否则返回0retract()：扫描指针回退一个字符，同时将character置空,2.2 一个简单的词法分析器示例,第二章 词法分析,2.1 词法分析的设计方法2.2 一个简单的词法分析器2.3 正规表达式与有限自动机简介2.4 正规表达式到有限自动机的构造2.5 词法分析器的自动生成,：正规表达式与正规集（定义和运算）状态转换图可以构造词法分析程序，但属于非形式化描述正规表达式（简称正规式）是词法分析的形式化表示方法所谓形式化的方法，是指用一整套带有严格规定的符号体系来描述问题的方法，优点：更加清晰和准确例如：形式化表示标识符，即标识符的正规式：这里，字母字符用letter表示,数字字符用digit表示letter与(letter|digit)*的并置表示连接括号中的“|”表示letter或digit两者选一“*”表示零次或多次引用，长度为0,1,2,2.3 正规表达式与优先自动机简介,letter(letter|digit)*,能够表示的单词集合称为正规集,：正规表达式与正规集（相关基础概念）1.字母表：语言元素的非空有穷集合，通常用表示例如：=a,b,c是字母表，它由a,b,c三个元素组成注意：字母表中至少包含一个元素，任何语言的字母表规定了该语言中允许出现的一切符号。如英文的字母表是26个字母、数字和标点符号的集合；C语言的字母表是由字母、数字和若干专用符号组成。2.符号：字母表中的每一个元素，也叫字符,2.3 正规表达式与优先自动机简介,：正规表达式与正规集（相关基础概念）3.符号串：由符号组成的有穷序列（可以是0个），也叫字如=a,b，则,a,b,aa,ab,aaa,bbb,都是字4.空字：长度为0的字，用表示5.字的全体：所有字组成的集合，用“*”表示例如：如果=a,b则*=，a，b，aa，ab，ba，bb，aaa，6.空语言：不含任何字的语言，用表示,2.3 正规表达式与优先自动机简介,注意区分、和：是空字，是语言字的集合中的一个元素,不包含任何字，属于集合的概念 由空字组成的集合，这个集合比 多一个元素,不是的元素,：正规表达式与正规集（递归定义）对于给定的字母表，正规式和正规集定义为：(1)和都是上的正规式，它们所表示的正规集分别为和。(2)对于任一个符号a，a是上的一个正规式，它所表示的正规集为a。,2.3 正规表达式与优先自动机简介,这两条规则称为基础规则第二条：从普通的符号产生对应的正规式和正规集,(3)如果R和S是上的正规式，它们所表示的正规集分别为L(R)和L(S)，则：R|S是上的正规式，它所表示的正规集为L(R)L(S)；RS是上的正规式，它所表示的正规集为L(R)L(S)；(R)*是上的正规式，它所表示的正规集为(L(R)*；,2.3 正规表达式与优先自动机简介,第三条规则称为归纳规则根据已有的正规式和正规集生成其它正规式和正规集,可以看出，归纳规则中有三种运算：“|”为或运算“”为连接运算，通常可省略“*”为闭包运算,(4)仅由有限次使用规则(1)(3)得到的表达式是上的正规式，它所表示的集合是上的正规集,2.3 正规表达式与优先自动机简介,第四条规则称为界限规则或者终止规则根据已有的正规式和正规集生成其它正规式和正规集,注意：在后面的正规式中，约定：不做特殊说明情况下，大写字母（如R、S等）对应字的集合,：正规表达式与正规集（正规式的运算）连接运算：字的连接：设“ab”和“aab”是两个字，则 abaab=abaab正规式的连接：RS=|R&S 例：A=ab，bc,B=ac,cb,则：AB=abac,abcb,bcac,bccb正规式的幂运算：正规式自身的n次连接并约定：R0=。,2.3 正规表达式与优先自动机简介,Rn=RRR,n个,ABBA,：正规表达式与正规集（正规式的运算）闭包运算：集合R的闭包表示为R*,具体定义为：R*=R0R1R2R3集合R的正闭包表示为R+,具体定义为：R+=R1R2R3=RR*显然：R*=R0R+,2.3 正规表达式与优先自动机简介,：正规表达式与正规集（正规式的运算性质）对于上的正规式R和S,如果它们的正规集满足L(R)=L(S),则称R和S等价，记为R=S。正规式的性质有：(1)交换律：R|S=S|R(2)结合律：R|(S|T)=(R|S)|T；R(ST)=(RS)T(3)分配律：R(S|T)=RS|RT；(R|S)T=RT|ST(4)同一律：R=R=R,2.3 正规表达式与优先自动机简介,2.3 课堂例题,例2.1 令=a,b，设R=a(a|b)*是上的正规式，试求其表示的正规集。,解答 L(R)=L(a(a|b)*)=L(a)L(a|b)*)=L(a)(L(a|b)*=L(a)(L(a)L(b)*=a(ab)*=aa,b*=a,a,b,aa,ab,ba,bb,aaa,=a,aa,ab,aaa,aab,aba,abb,aaaa,2.3 课堂例题,例2.2 令=a,b，根据给出的正规式，试描述其表示的正规集。,正规式 正规集 ba*上所有的以b为首，并且后跟任意多个a 的字，b,ba,baa,baaa,a(a|b)*上所有的以a为首的字(a|b)*(aa|bb)(a|b)*上所有含有两个连续的a或者b的字,2.3 课堂例题,例2.3 判断下述正规式之间是否等价：(1)(a|b)*与a*|b*(2)(ab)*与a*b*,解答(1)(a|b)*对应的正规集其a、b可任意交替出现，如abbaaaba；而 a*|b*对应的正规集只可出现任意个a或者任意个b；因此两者不等价。,解答(2)(ab)*对应的正规集是以任意个ab对出现的，即ababab；而a*b*对应的正规集则是先出现任意个a后接任意个b，即aabb；因此两者不等价。,2.3 课堂例题,例2.4 证明：设L(a+)=a*-,则有a+=aa*,证明 L(a+)=a*-=,a,a2,a3,-=a,a2,a3,=a*,a,a2,=a*a*=L(a)L(a*)=L(aa*)故 a+=aa*,2.4 正规表达式到有限自动机的构造,课后 2.4 正规式(ab)*a 与正规式a(ba)*,解答 格式参考上页PPT,