湖南大学编译原理课件3

《湖南大学编译原理课件3》由会员分享，可在线阅读，更多相关《湖南大学编译原理课件3（74页珍藏版）》请在金锄头文库上搜索。

1、第三章 词法分析,杨晓波 湖南大学信息科学与工程学院 2/16/2011,核心问题：如何构建一个词法分析器？,构建词法分析器的方法,DFA代码化 使用词法分析器自动生成工具，如：LEX,内容,词法分析器的作用 记号的说明 记号的识别 状态转换图的构造 状态转换图代码化 有穷自动机 从正则表达式到自动机 词法分析器生成工具的设计方法,3.1 词法分析器的作用,读入源程序字符流、组成词素，输出记号序列。 过滤空白、换行、制表符、注释等。 将词素添加到符号表中。 通常和语法分析器处于同一趟中（作为其子程序）,为什么有独立的词法分析器,简化编译器的设计 词法分析器可以首先完成一些简单的处理工作。 提高

2、编译器效率 相对于语法分析，词法分析过程简单，可高效实现。（下推自动机 vs 有穷自动机） 增强编译器的可移植性,记号、模式、词素,记号（token)记号名是表示某种词法单位的抽象符号。语法分析器通过记号名即可确定记号序列的结构。 模式(pattern) 描述了一个记号的词素可能具有的形式 关键词的模式就是组成该关键字的字符序列 如：if的模式就是if 词素(lexme) 源程序中跟某个记号模式相匹配的字符序列 被词法分析器识别为该记号的一个实例,记号、模式、词素（例子）,printf(“Total = % dn”, score)； Printf, score和id的模式匹配 “Total =

3、 % dn”和literal的模式匹配,记号的属性,一个模式匹配多个词素时，必须通过属性来传递附加的信息。属性值将被用于语义分析、代码生成等阶段。 不同的目的需要不同的属性。因此，属性值通常是一个结构化数据。 记号id的属性 词素、类型、第一次出现的位置、,内容,词法分析器的作用 记号的说明 正则表达式 记号的识别 有穷自动机 从正则表达式到自动机 词法分析器生成工具的设计方法,3.2 记号的说明,常用形式：正则表达式 可有效描述记号模式类型 与正则语言、正则文法等价 内容 串和语言 语言上的运算 正则表达式 正则定义 正则表达式的扩展,串和语言（1）,字母表（alphabet）：一个有限的符

4、号集合。 符号典型例子：字母、数位、标点符号。 字母表例子：0,1；ASCII；Unicode 在理论上，我们可以把任意的有限集合看作字母表。 字母表上的串（string）是该字母表中符号的有穷序列。 串s的长度，|s|，是指s中符号的出现次数； 空串：长度为0的串， 语言（language）是某个给定字母表上的一个可数的串集合。,串和语言（2）,和串有关的术语（banana） 前缀：从串尾删除0个或多个符号后得到的串。（ban、banana、 ） 后缀：从串首删除0个或多个符号后得到的串。（nana、banana、） 子串：删除串的任意前缀和任意后缀得到的串。（banana、nan、 ） 真

5、前缀、真后缀、真子串：既不等于原串，也不等于空串的前缀、后缀、子串。 子序列：从原串中删除0个或者多个符号后得到的串，这些被删除的符号可能不相邻。（baan）,串和语言（3）,串的运算 连接(concatenation)：x和y的连接时把y附加到x的后面形成的串，记作xy。 x=dog，y=house，xy=doghouse 指数运算（幂运算）：s0=，s1=s，si=si-1s； x=dog，x0=，x1=dog，x3=dogdogdog,串和语言（4）,语言的运算,3,注：L0规定为,串和语言（5）,例子 L=A,B,Z,a,b,z D=0,1,9 L U D=A,B,Z,a,b,z,0,

6、1,9 LD：以1个字母开头，后跟1个数位的串的集合 L4：所有由四个字母构成的串的集合 L*：所有字母构成的集合，包括。 Q: L(L U D)*和D+识别什么语言？,正则表达式,字母表上的正则表达式的定义（科学归纳法） 基本正则式 （归纳基础） 是一个正则表达式，L()= 如果a是上的一个符号，那么a是正则表达式，L(a)=a 归纳步骤：（四运算，将小的正则式复合成大的正则式） 选择：(r) | (s)，L(r) | (s)=L(r) U L(s)； 连接：(r)(s)，L(r)(s)=L(r)L(s) ； 闭包：(r)*，L(r)*)=(L(r)*； 括号：(r)，L(r)=L(r) 运

7、算的优先级：* 连接 | 结合性：全都左结合 正则集合：可以用一个正则表达式定义的语言,正则表达式的例子,=a,b L(a|b) = a,b L(a|b)(a|b) = aa,ab,ba,bb L(a*) = ,a,aa,aaa,aaaa, L(a|b)*) = ,a,b,aa,ab,ba,bb, aaa,aab, L(a|a*b) = a,b,ab,aab,aaab,正则集合的等价及其定律,如果L(r)=L(s)，正则表达式r和s等价。,问题：连结运算是否有交换率？,正则定义（1）,为书写方便，可给正则表达式命名 之后的正则表达式可使用这些名字 正则定义是如下形式的定义序列d1 r1d2 r

8、2 dnrn 其中： di不在中，且各不相同 每个ri是字母表 U d1,d2,di-1上的正则表达式。 这保证了不会出现递归定义。,正则定义（2）,可通过代入法构建各个di的上的独立正则表达式如下： d1的正则表达式即r1。 将r2中的d1替换为r1，得到d1的正则表达式。 将ri中的d1,d2,di-1替换为各自的正则表达式，得到di的正则表达式。,正则定义的例子,C语言标识符的正则定义 letter_ A | B | | Z | a | b | | z | _ digit 0 | 1 | | 9 id letter_ ( letter_ | digit )* id对应的正则表达式为 (A

9、 | B | | Z | a | b | | z | _) (A | B | | Z | a | b | | z | _) |(0 | 1 | | 9)*,正则表达式的扩展,基本运算符：并、连接、Kleene闭包 扩展的运算符： 一个或多个实例：单目后缀+ r+等价于rr* 零个或一个实例：？ r?等价于 |r 字符类 a1a2an等价于a1|a2|an a-e等价于a|b|c|d|e 使正则表达式更简洁，但不会使正则表达式能够描述更多的语言。,内容,词法分析器的作用 记号的说明 记号的识别 状态转换图构造 状态转换图代码化 有穷自动机 从正则表达式到自动机 词法分析器生成工具的设计方法,3.

10、3 记号的识别,词法分析器要求能够检查输入字符串，在前缀中找出和某个模式匹配的词素。 首先通过正则定义来描述各种记号的模式。 定义ws(blank | tab | newline)+来消除空白 词法分析器识别到这个模式时，不返回记号，继续识别其它模式。,状态转换图(transition diagram),是词法分析器的重要组件之一 状态转换图 状态(state)：表示了在识别词素的过程中可能出现的情况 状态可看作是已处理部分的总结。 某些状态为接受状态或最终状态，表明已经找到词素。 加上*的接受状态表示最后读入的符号不属于词素（先行符号）。 开始状态（初始状态）：用start边表示。 边(ed

11、ge)：从一个状态指向另一个状态；边上标记一个或者多个符号，即状态变迁的条件 若如果当前状态为s，当前输入符号为a，则沿着从S发出、标记为a的边进入下一个状态。 问题：试设计一个状态图描述日光灯的状态转换过程,识别标识符的状态转换图,1,2,3,字母,其他,字母或数位,*,识别整常数的状态转换图,一个状态转换图可用于识别(或接受)一定的字符串。,状态转换图举例：关系算符relop,注：双圈表示 接收状态,保留字和标识符的识别,在很多程序设计语言中，保留字也符合标识符的模式，识别标识符的状态转换图也会识别保留字。 解决方法 在符号表中预先填写保留字，并指明它们不是普通标识符。 为关键字/保留字建

12、立单独的状态转换图。并设定保留字的优先级高于标识符。,其它常用状态转换图,问题：状态19,20,21分别识别什么记号,词法分析器的体系结构,从转换图构造词法分析器的方法（DFA代码化） 变量state记录当前状态 整体可通过一个switch来根据state的值转到相应的代码 每个状态对应于一段代码。 这段代码根据读入的符号，确定下一个状态 如果找不到相应的边，则调用fail()进行错误恢复 进入某个接受状态时，返回相应的记号。 注意状态有*标记时，需要回退forward指针。,失效函数,DFA代码化举例Relop对应的代码概要,处理多个模式的方法,词法分析器需要匹配多个模式 解决方法（3种）

13、顺序地尝试各个记号对应的状态转换图。如果引发fail()，回退并启动下一个状态图。可以根据优先级确定尝试顺序。 “并行地”运行各个状态转换图。通过greedy策略，识别最长的和某个模式匹配的输入前缀 最长前缀匹配原则 预先把各个状态转换图合成一个状态转换图，然后运行这个状态转换图。,3.5 有穷自动机,本质上和状态转换图类似 区别 有穷自动机只回答Yes/No 区分为两类： 非确定有穷自动机（Nondeterministic Finite Automata,NFA）边上的标号没有限制，一个符号可出现在离开同一个状态的多条边上， 可以做标号 确定性有穷自动机（ Deterministic Fin

14、ite Automata, DFA）对于每个状态以及每个符号，有且只有一条边。 两种自动机都识别正则语言,非确定有穷自动机,NFA由以下几部分组成（五要素） 一个有穷状态集合S 一个输入字母表（input alphabet） 转换函数（transition function） 对于每个状态和 U中的符号，给出相应的后继状态集合 初始状态s0 有些定义中可以有多个开始状态 接受状态集合F FS,NFA的例子,状态集合S=0,1,2,3 开始状态0 接受状态集合3 转换函数： (0,a)0,1 (0,b)0 (1,b)2 (2,b)3,相应的图形表示,转换表（transition table）表示

15、法,用二维表表示NFA的转换函数 每行对应于一个状态， 每列对应于一个输入符号或者。 每个条目表示对应的后继状态集合,转换表表示法,输入字符串的接受,一个NFA接受输入字符串x，当且仅当对应的转换图中存在一条从开始状态到某个接受状态的路径，该路径中各条边上的标号组成x（ 标号不考虑）。 前面的NFA接受aabb，因为：NFA接受的语言：从开始状态到达接受状态的所有路径上的标号串的集合。 就是它接受的所有符号串的集合,NFA和相应语言的例子,相应的语言：L(aa*|bb*),确定有穷自动机,一个NFA被称为DFA，如果 没有之上的转换动作 对于每个状态s和每个输入符号a，有且仅有一条标号为a的离

16、开s的边 可以高效判断一个串能否被一个DFA接受。 每个NFA都有一个等价的DFA。即它们接受同样的语言。,DFA的模拟,假设输入符号就是字符； Nextchar读入下一个字符（符号） move给出了离开s，标号为c的边的目标状态,DFA的例子,假设输入为ababb，那么进入的状态序列为 0,1,2,1,2,3,从正则表达式到自动机的转换,正则表达式可以简洁、精确地描述记号的模式但是在进行模式匹配时需要模拟DFA的执行。 因此，需要将正则表达式转换为DFA 步骤： 正则表达式到NFA NFA到DFA,NFA到DFA（子集构造法）(1),基本思想： 构造得到的DFA的每个状态和NFA的状态子集对应 DFA读入a1,a2,an后到达的状态对应于从NFA开始状态出发沿着a1,a2,an可能到达的状态集合。 在算法中“并行地模拟” NFA在遇到一个给定输入串时可能执行的所有动作。 理论上，最坏情况下DFA的状态个数会是NFA状态个数的指数多个。但是对于大部分应用，NFA和相应的DFA的状态数量大致相同。,