03 编译原理---词法分析

1 .第三章 词法分析 许畅 南京大学计算机系 2018年春季 

2 .内容  词法分析器的作用  词法单元的规约 (正则表达式)  词法单元的识别 (状态转换图)  词法分析器生成工具及设计  有穷自动机 2 

3 .词法分析器的作用 • 读入字符流，组成词素，输出词法单元序列 • 过滤空白、换行、制表符、注释等 • 将词素添加到符号表中 • 在逻辑上独立于语法分析，但是通常和语法分析 器处于同一趟中 3 

4 .为什么要设立独立的词法分析器？  简化编译器的设计  词法分析器可以首先完成一些简单的处理工作  提高编译器效率  相对于语法分析，词法分析过程简单，可高效实现 (下 推自动机 vs. 有穷自动机)  增强编译器的可移植性 4 

5 .词法单元、模式、词素 • 词法单元 (Token) – <词法单元名、属性值 (可选) > – 单元名是表示词法单位种类的抽象符号，语法分析器 通过单元名即可确定词法单元序列的结构 – 属性值通常用于语义分析之后的阶段 • 模式 (Pattern) – 描述了一类词法单元的词素可能具有的形式 • 词素 (Lexeme) – 源程序中的字符序列 – 它和某个词法单元的模式匹配，被词法分析器识别为 该词法单元的实例 5 

6 .词法单元、模式、词素 (例子) • printf("Total = %d\n", score)； – printf, score和标识符 (id) 的模式匹配 – "Total = % d\n"和literal的模式匹配 6 

7 .词法单元的属性  一个模式匹配多个词素时，必须通过属性来传递 附加的信息  属性值将被用于语义分析、代码生成等阶段  不同的目的需要不同的属性  属性值通常是一个结构化数据  如词法单元id的属性  词素、类型、第一次出现的位置、… 7 

8 .内容  词法分析器的作用  词法单元的规约 (正则表达式)  词法单元的识别 (状态转换图)  词法分析器生成工具及设计  有穷自动机 8 

9 .词法单元的规约  正则表达式可以高效、简洁地描述处理词法单元 时用到的模式类型  内容  串和语言  语言上的运算  正则表达式和正则定义  正则表达式的扩展 9 

10 .串和语言 (1) • 字母表 (Alphabet) ：一个有穷的符号集合 – 符号典型例子：字母、数字、标点符号 – 例子：{0,1}, ASCII, Unicode – 在理论上，我们可以把任意的有限集合看作字母表 • 字母表上的串 (String) 是该表中符号的有穷序列 – 串s的长度，即 |s|，是指s中符号出现的次数 – 空串：长度为0的串，ε • 语言 (Language) 是某个给定字母表上的串的可数 集合 10 

11 .串和语言 (2) • 和串有关的术语 (以banana为例) – 前缀：从串的尾部删除0个或多个符号后得到的串 (ban、banana、ε) – 后缀：从串的开始处删除0个或多个符号后得到的串 (nana、banana、ε) – 子串：删除串的某个前缀和某个后缀得到的串 (banana、nan、ε) – 真前缀、真后缀、真子串：既不等于原串，也不等于 空串的前缀、后缀、子串 (前面例子的红色部分) – 子序列：从原串中删除0个或者多个符号后得到的串 (baan) 11 

12 .串和语言 (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 12 

13 .串和语言 (4)  语言的运算  语言是某个给定字母表上的串的可数集合 + 13 

14 .串和语言 (5)  例子  L = {A, B , ……, Z, a, b, ……, z}  D = {0, 1, ……, 9}  L  D = {A, B, ……, Z, a, b, ……, z, 0, 1, ……, 9}  LD：520个长度为2的串的集合 (字母 + 数字)  L4：所有由四个字母构成的串的集合  L*：所有字母构成的集合，包括ε  L (L  D)*：？  D+：？ 14 

15 .正则表达式 字母表Σ上的正则表达式的定义 • 基本部分 – ε是一个正则表达式，L(ε) = {ε} – 如果a是Σ上的一个符号，那么a是正则表达式，L(a) = {a} • 归纳步骤 – 选择：(r)|(s)，L((r)|(s)) = L(r)  L(s) – 连接：(r)(s)，L((r)(s)) = L(r)L(s) – 闭包：(r)*，L((r)*) = (L(r))* – 括号：(r)，L((r)) = L(r) • 运算的优先级：* > 连接 > |，如(a) | ((b)*(c)) = a | b*c • 正则集合：可以用一个正则表达式定义的语言 15 

16 .正则表达式的例子  Σ = {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, …} 16 

17 .正则定义 (1) • 为了书写方便，可以给正则表达式命名，且可以 通过名字使用正则表达式 • 正则定义是如下形式的定义序列 d1  r1 d2  r2 … dn  rn • 其中 – di不在Σ中，且各不相同 – 每个ri是字母表Σ  {d1, d2, …, di-1}上的正则表达式；这 保证了不会出现递归定义 18 

18 .正则定义的例子  C语言标识符的正则定义  letter_  A | B | … | Z | a | b | … | z | _  digit  0 | 1 | … | 9  id  letter_ ( letter_ | digit )*  id对应的正则表达式为  (A | B | … | Z | a | b | … | z | _) ( (A | B | … | Z | a | b | … | z | _) | (0 | 1 | … | 9) )* 20 

19 .正则表达式的扩展 • 基本运算符：选择、连接、Kleene闭包 • 扩展的运算符 – 一个或多个实例：单目后缀+ • r+等价于r r* – 零个或一个实例：？ • r?等价于ε | r – 字符类 • [a1a2…an]等价于a1 | a2 | … | an • [ae]等价于a | b | c | d | e • 使正则表达式更简洁，但不会使其描述能力增强 21 

20 .内容  词法分析器的作用  词法单元的规约 (正则表达式)  词法单元的识别 (状态转换图)  词法分析器生成工具及设计  有穷自动机 22 

21 .词法单元的识别  词法分析器要求能够检查输入字符串，在其前缀 中找出和某个模式匹配的词素  首先通过正则定义来描述各种词法单元的模式  定义ws  (blank | tab | newline)+来消除空白  当词法分析器识别出这个模式时，不返回词法单元， 继续识别其它模式 23 

22 .24 

23 .状态转换图  词法分析器的重要组件之一  状态转换图 (Transition diagram)  状态 (State)：表示在识别词素时可能出现的情况  状态看作是已处理部分的总结  某些状态为接受状态或最终状态，表明已找到词素  加上*的接受状态表示最后读入的符号不在词素中  开始状态 (初始状态)：用Start边表示  边 (Edge)：从一个状态指向另一个状态  边的标号是一个或多个符号  当前状态为s，下一个输入符号为a，就沿着从s离开，标号为a 的边到达下一个状态 25 

24 .状态转换图的例子 26 

25 .保留字和标识符的识别  在很多时候，保留字也符合标识符的模式  识别标识符的状态转换图也会识别保留字  解决方法  在符号表中先填保留字，并指明它们不是普通标识符  为保留字建立独立的、高优先级的状态转换图 27 

26 .其它的状态转换图 28 

27 .词法分析器的体系结构 • 从转换图构造词法分析器的方法 – 变量State记录当前状态 – 一个switch根据State的值转到相应的代码 – 每个状态对应于一段代码 • 这段代码根据读入的符号，确定下一个状态 • 如果找不到相应的边，则调用fail()进行错误恢复 – 进入某个接受状态时，返回相应的词法单元 • 注意状态有*标记时，需要回退forward指针 • 实际是模拟转换图的运行 29 

28 .Relop对应的代码概要 30 

29 .内容  词法分析器的作用  词法单元的规约 (正则表达式)  词法单元的识别 (状态转换图)  词法分析器生成工具及设计  有穷自动机 32