第三章：词法分析 戴新宇 南京大学 计算机科学与技术系.

Presentation on theme: "第三章：词法分析 戴新宇 南京大学 计算机科学与技术系."— Presentation transcript:

1 第三章：词法分析 戴新宇 南京大学 计算机科学与技术系

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

3 词法分析器作用 词法分析是读入源程序的输入字符、将它们组成词素，生成并输出一个词法单元序列，每个词法单元对应于一个词素。 常见的做法是：
由语法分析器调用，需要的时候不断读取、生成词法单元 可以避免额外的输入输出 在识别出词法单元之外，还会完成一些不需要生成词法单元的简单处理，比如删除注释、将多个连续的空白字符压缩成一个字符等。

4 词法分析和语法分析 通常，将编译过程的分析划分成两个阶段的原因： 简化编译器的设计，任务分解 提高编译器的效率 增强编译器的可移植性
注释、空白词法分析阶段就扔掉了 缓冲技术可以更高效 输入设备相关的特殊性被限制在句法分析过程中

5 词法分析相关概念 词法单元（Token）： 词素（Lexeme） 模式（Pattern）
包含单元名（Token-name）和可选的属性值(attribute-value) 单元名是表示某种词法单位抽象符号。语法分析器通过单元名即可确定词法单元序列的结构。 词素（Lexeme） 源程序中的字符序列，它和某类词法单元的模式匹配，被词法分析器识别为该词法单元的实例。 模式（Pattern） 词法单元的词素可能具有的形式。可以用正则表达式来表示。 关键字，单个 和很多符号串匹配

6 词法单元示例

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

8 词法单元示例（名和属性值）

9 词法分析器的构造实现 两种方法： 正则表达式
基于词法单元的词法结构图或其它描述，手工编写代码扫描输入中的每个词素，并返回识别到的词法单元信息。 使用词法分析器生成工具（如lex flex）。给出描述词素的模式，利用工具编译为具有词法分析器功能的代码。高效且简单。 正则表达式 一种描述词素模式的重要表示方法

10 Outline 词法分析的作用 词法单元的规约（正则表达式） 词法单元的识别（状态转换图） 有穷自动机 词法分析器生成工具及设计

11 相关概念 字母表：一个有限的符号集合 串：字母表中符号组成的一个有穷序列 语言：给定字母表上一个任意的可数的串的集合 二进制{0，1}
ASCII Unicode 典型的字母表包括字母、数位和标点符号 串：字母表中符号组成的一个有穷序列 串s的长度 |s| 空串ε，长度为0的串 语言：给定字母表上一个任意的可数的串的集合 语法正确的C程序的集合，英语，汉语

12 相关概念（2） 和串有关的术语（banana） 前缀：从串的尾部删除0个或多个符号后得到的串。（ban、banana、 ε）
后缀：从串的开始处删除0个或多个符号后得到的串。（nana、banana、ε） 子串：删除串的某个前缀和某个后缀得到的串。（banana、nan、 ε） 真前缀、真后缀、真子串：既不等于原串，也不等于空串的前缀、后缀、子串。 子序列：从原串中删除0个或者多个符号后得到的串。（baan）

13 相关概念（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

14 相关概念（4） 语言上的运算

15 语言及其运算示例3.3 L={A,B,……,Z,a,b,……,z} D={0,1,……,9}
L U D: {A,B,……,Z,a,b,……,z,0,1,……,9} LD：520个长度为2的串的集合 L4：所有由四个字母构成的串的集合 L*：所有字母构成的集合，包括ε。 L(L U D): D+:

16 正则表达式（Regular Expression, RE）
正则表达式可以高效、简洁地描述处理词法单元时用到的模式类型。 可以描述所有通过对某个字母表上的符号应用运算符而得到的语言。其定义的集合叫做正则集合(regular set)。 每个正则表达式r可以描述一个语言L(r)，也即其定义的正则集合。 C语言标识符的语言，可以用如下正则表达式来表示：letter_(letter_|digit)*

17 正则表达式 字母表Σ上的正则表达式的定义 基本部分 归纳步骤： 运算的优先级：* > 连接符 > |
ε 是一个正则表达式，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) 运算的优先级：* > 连接符 > | (a)|((b)*(c))可以改写为 a|b*c

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

19 正则表达式的性质 等价性 如果两个正则表达式r和s表示同样的语言，则r=s 代数定律

20 正则定义 对正则表达式命名，使表示简洁。 d1  r1 d2  r2 . . . dn  rn 各个di不在字母表Σ中，且名字都不同
每个ri都是Σ U {d1, d2, …, di-1 }上的正则表达式 为避免递归定义。。。。

21 正则定义（2） 各个di在Σ上的正则表达式如下： 注意：替换的时候不能破坏替换进去的di的完整性。 d1的正则表达式即r1。
将r2中的d1替换为r1，得到d2的正则表达式。 … … … … 将ri中的d1,d2,…,di-1替换为各自的正则表达式，得到di的正则表达式。 注意：替换的时候不能破坏替换进去的di的完整性。

22 正则定义的例子 C语言的标识符集合 letter_  A | B | … | Z | a | b | … | z | _
digit  0 | 1 | … | 9 id  letter_(letter_|digit)*

23 正则定义的例子2 Pascal无符号数集合，例1946,11.28,63.6E8,1.99E-6 digit  0 | 1 | … | 9
digits  digit digit* optional_fraction  .digits|ε optional_exponent  (E ( + | - | ε ) digits ) | ε num  digits optional_fraction optional_exponent 10.

24 正则表达式的扩展 基本运算符：并 连接 闭包 扩展运算符 前面两个例子的简化表示 一个或多个：r+ , 等价于rr*
基本运算符：并 连接 闭包 扩展运算符 一个或多个：r+ , 等价于rr* 零个或一个： r?，等价于ε |r 字符类 [abc]等价于a|b|c, [a-z]等价于a|b|…|z 前面两个例子的简化表示

25

26 附注 正则表达式是一种描述手段，通常用来描述程序语言的词法符号。为了识别一个串是否属于某个正则集，则一般采用自动机来做。
很多编辑器支持正则表达式 工具GREP Optional homework

27 Outline 词法分析的作用 词法单元的规约（正则表达式） 词法单元的识别（状态转换图） 有穷自动机 词法分析器生成工具及设计

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

29 29

30 状态转换图 状态转换图是词法分析器的重要组件之一 可以将正则表达式转换成状态转换图 状态转换图(transition diagram)
状态(state)：表示了在识别词素的过程中可能出现的情况 状态看作是已处理部分的总结。 某些状态为接受状态或最终状态，表明已经找到词素。 加上*的接受状态表示最后读入的符号不在词素中。 开始状态（初始状态）：用start边表示。 边(edge)：从一个状态指向另一个状态；边的标号是一个或者多个符号。 如果当前状态为s，下一个输入符号为a，就沿着从s离开，标号为a的边到达下一个状态。 需要将模式转换成流图，状态转换图。手工构造，自动构造。

31 状态转换图的例子

32 保留字和标识符的识别 在很多程序设计语言中，保留字也符合标识符的模式，识别标识符的状态转换图也会识别保留字。 解决方法
在符号表中预先填写保留字，并指明它们不是普通标识符。 为关键字/保留字建立单独的状态转换图。并设定保留字的优先级高于标识符。

33 其它的状态转换图

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

35 Relop对应的代码概要

36 多个模式集成到词法分析器 方法1：词法分析器需要匹配多个模式（有多个状态转换图） 方法2：并行的运行各个状态转换图
顺序的尝试各个词法单元的状态转换图，如果引发fail，回退并启动下一个状态转换图 次序问题 优先级 方法2：并行的运行各个状态转换图 一个图已经匹配到词素，另一个仍在继续读入 取最长的和某个模式匹配的输入前缀（词法单元） 方法3：所有的状态转换图合并为一个图 选择策略同方法2 书中例子简单，因为没有两类词法单元以相同的字符开头

37 有穷自动机 Lex的核心 本质上等价与状态转换图 区别在于： 分为两类 自动机是识别器，对每个输入串回答yes or no
不确定的有穷自动机（Nondeterministic Finite Automate，NFA） 确定的有穷状态自动机（Deterministic Finite Automate，DFA）

38 不确定 vs. 确定 相同：都可以识别正则语言，两者之间存在等价性 不同：
一个符号标记离开同一状态的多条边 vs. 对于每个状态和字母表中的每个字符，有且仅有 一条离开该状态、以该符合为标号的边 可以有边的标号是ε vs. 没有标记为ε的边 相同：都可以识别正则语言，两者之间存在等价性

39 不确定的有穷自动机 NFA由以下几部分组成 一个有穷的状态集合S 一个输入符号集合Σ（input alphabet）
转换函数（transition function）对于每个状态和Σ ∪ {ε}中的符号，给出相应的后继状态集合 一个状态S0被指定为开始状态/初始状态 S的一个子集F被指定为接受状态

40 NFA的例子 状态集合S={0,1,2,3} 开始状态0 接受状态集合{3} 转换函数：
(0,a){0,1} (0,b){0} (1,b)2 (2,b)3 相应的转换图表示

41 转换表 NFA可以表示为一个转换表 表的各行对应于状态 各列对应于输入符号和ε 表中的元素表示给定状态在给定输入下的后继状态

42 自动机对输入字符串的接受 一个NFA接受输入字符串x，当且仅当对应的转换图中存在一条从开始状态到某个接受状态的路径，使得该路径中各条边上的标号组成符号串x 。 （路径中可能包含ε 边） 图2-24对应的NFA能够接受aabb 注意：只要存在从开始状态到接受状态的路径，符号串就认为被NFA接受。

43 自动机与语言 由一个NFA A定义（接受）的语言是从开始状态到某个接受状态的所有路径上的符号串集合，称为L(A)。
相应的语言：L(aa*|bb*)

44 确定有穷自动机 一个NFA被称为DFA，如果 可以高效判断一个串能否被一个DFA接受。
没有ε之上的转换动作 对于每个状态s和每个输入符号a，有且只有一条标号为a的边。 可以高效判断一个串能否被一个DFA接受。 每个NFA都有一个等价的DFA。即它们接受同样的语言。 转换表每个表项只有一个状态，因此不再需要花括号。

45 DFA的模拟 假设输入符号就是字符串中的符号； Nextchar读入下一个字符（符号） move给出了离开s，标号为c的边的目标状态

46 DFA的例子 假设输入为ababb，那么进入的状态序列为 0,1,2,1,2,3，返回yes

47 正则表达式到自动机 正则表达式可以简洁、精确地描述词法单元的模式但是在进行模式匹配时需要模拟DFA的执行。
步骤： 正则表达式到NFA NFA到DFA

48 NFA转换成DFA - 子集构造法 对NFA的模拟往往不如对DFA的模拟直接，除非转换花费更多的时间 基本思想：
DFA读入a1,a2,…,an后到达的状态对应于从NFA开始状态出发沿着a1,a2,…,an可能到达的状态集合。 理论上，最坏情况下DFA的状态个数会是NFA状态个数的指数多个。但是对于大部分应用，NFA和相应的DFA的状态数量大致相同。

49 NFA转换成DFA - 子集构造法 输入：一个NFA N 输出：一个接受相同语言的DFA D s表示N中的单个状态，T代表N的一个状态集

50 NFA转换成DFA - 子集构造法 D的开始状态是ε-closure(s0)，D的接受状态是所有至少包含了N的一个接受状态的状态集合。

51 NFA转换成DFA - 子集构造法 对NFA的任何状态集合ε-closure(T)的计算 一个图搜索过程

52 NFA到DFA转换的示例 A：=ε-closure(0)={0,1,2,4,7}
B：Dtran[A,a]= ε -closure(move(A,a))= ε -closure({3,8})={1,2,3,4,6,7,8} C：Dtran[A,b]= ε -closure(move(A,b))= ε -closure({5})={1,2,4,5,6,7} D：Dtran[B,b]=ε -closure(move(B,b))= {1,2,4,5,6,7,9} …

53 NFA到DFA转换的示例 开始状态：A 接受状态：E

54 利用子集构造法对NFA的运行进行模拟 输入：一个以文件结束符eof结尾的输入串x，一个NFA N，其开始状态是S0，接受状态集为F，转换函数为move。 输出：如果N接受x，返回yes，否则返回no。

55 DFA状态数最小化 DFA化简：状态数最小化 等价的DFA可能具有不同的状态个数 任何正则语言都有一个唯一的（不计同构）状态数目最少的DFA

56 DFA状态最小化 原理：将一个DFA的状态集合分划成多个组，每个组中的各状态之间相互不可区分。然后将每个组中的状态合并为一个状态。
可区分的定义： 如果分别从状态s和状态t出发，沿着标号为x的路径到达的两个状态只有一个是接受状态，称为x区分状态s和t。 如果存在能够区分s和t的串，那么它们就是可区分的。 空串区分了E和其它状态 bb区分了A和B

57 最小化算法（分划部分） 设置初始分划П={S-F,F} 迭代，不断分划：
for (П中的每个元素G){ 细分G，使得G中的s、t仍然在同一组中 iff 对任意a，s,t都到达П中的同一组； Пnew=将П中的G替换为细分得到的小组； } 如果Пnew==П，令Пfinal==П，转步骤4；否则П==Пnew，转步骤2；

58 最小化算法（构造部分） 4. 在Пfinal的每个组中选择一个状态作代表，最为最小DFA的状态 开始状态就是中包含原开始状态的组的代表
接受状态就是包含了原接受状态的组的代表 转化关系构造如下： 如果s是中G的代表，而s在a上的转换到达t，而t所在组的代表为r，那么最小DFA中有从s到r的、在a上的转换。

59 DFA最小化的正确性证明 位于Пfinal的同一组中的状态不可能被任意串区分 Пfinal的不同组的状态之间是可区分的
i次迭代后，s和t还在一个小组，肯定不存在长度小于i的串可以将它们分开。 Пfinal的不同组的状态之间是可区分的 s和t一开始就在不同组 某一次迭代，s和t被划分到不通的组，肯定是因为存在一个输入字符a和状态p、q，而p和q在不同的组里。即存在x可以划分p和q，ax可以区分s和t。 初始划分，第i次被划分。

60 DFA最小化的例子 初始分划：{A,B,C,D} {E} 处理{A,B,C,D}，b把它细分为{A,B,C} {D}。
处理{A,B,C}，b把它细分为{A,C} {B} 分划完毕。选取A,B,D和E最为代表，构造得到最小DFA。

61 正则表达式到NFA 输入：字母表Σ上的一个正则表达式r 输出：一个接受L(r)的NFA N 基本思想
算法分成两个部分： 基本规则处理ε和单符号的情况 基于正则表达式子表达式的NFA，组合构造表达式的NFA。

62 转换算法(1) 基本规则： 表达式ε， 表达式a，

63 转换算法(2) 归纳规则 正则表达式s和t的NFA分别是 N(s)和N(t) r=s|t， r的NFA N(r)

64 转换算法(2) 归纳规则 正则表达式r=st， N(r)

65 转换算法(3) 归纳规则 正则表达式 r=s*, N(r) r=(s), N(r)=N(s)

66 正则表达式到NFA的例子（1） 正则表达式(a|b)*abb 第一个a对应的NFA 第一个b对应的NFA

67 正则表达式到NFA的例子（2） (a|b)的NFA 第二个a的NFA

68 正则表达式到NFA的例子（3） (a|b)*的NFA

69 正则表达式到NFA的例子（4） (a|b)*a

70 词法分析器生成工具的设计 词法分析器生成工具的体系结构

71 词法分析器工具Lex Lex/Flex:基于给定的用来描述词法单元模式的正则表达式，生成词法分析器 通常和Yacc一起使用，生成编译器的前端

72 Lex程序结构 声明部分 转换规则 辅助函数 明示常量：表示常数的标识符 正则定义 模式 {动作} 模式是一个正则表达式或者正则定义
%% 转换规则 辅助函数 Lex程序的形式 声明部分 明示常量：表示常数的标识符 正则定义 转换规则 模式 {动作} 模式是一个正则表达式或者正则定义 动作通常是C语言代码，表示匹配该表达式后，应该执行的代码。 辅助函数 动作中需要使用的函数

73 词法分析器的工作方式 （与语法分析器协同工作）
词法分析器的工作方式 （与语法分析器协同工作） 被调用时，不断读入余下的输入 直到发现最长的、与某个模式匹配的前缀，调用相应的动作； 该动作进行相关处理，并把控制返回； 如果不返回，则词法分析器继续寻找其它词素

74 Lex程序的例子（1） %{和}%之间的内容一般被直接拷贝到lex.yy.c中； 这里的内容就是一段注释；
LT，LE等的值在yacc源程序中定义 正则定义 分隔声明部分和转换规则部分。

75 Lex程序的例子（2） 没有返回，表示继续识别其它词法单元

76 Lex程序的例子（3） 辅助函数被直接拷贝到lex.yy.c中 可在转换规则中直接调用

77 Lex变量 当id被匹配时，会用到三个变量 Yylval：存放指向符号表的指针 yytext：token的lexeme
yyleng：lexeme的长度

78 示例

79 示例（续） 上述三种模式对应的NFA

80 示例（续） 由于自动机需要识别所有与Lex程序中的模式相匹配的词素，因此我们需要将这些NFA合并为一个NFA。
引入一个新的开始状态，从这个新状态到各个对应于模式pi的NFA Ni的开始状态各有一个ε转换。

81 Lex中的冲突解决方法 当输入的多个前缀与一个或者多个模式匹配时，会有冲突 Lex按照如下规则解决冲突 abb aaabbbb
总是选择最长的前缀 保证词法分析器把<=当作一个词法单元识别 长度相等时，选择在Lex程序中首先被列出的模式 如果保留字对应的规则在标识符的规则之前，词法分析器将识别出保留字

82 基于NFA的模式匹配 词法分析器模拟NFA的运行，直到到达一个没有后续状态的输入点。
沿着状态集顺序回找，直到找到一个包含一个或多个接受状态的集合为止。如果集合中有多个接受状态，我们就选择和在Lex程序中位置最靠前的模式相关联的接受状态pi，执行相应模式对应的Ai。

83 词法分析器使用DFA 将NFA转换成DFA之后，由词法分析器模拟DFA的运行。
输入abba，找到模式p2=abb

84 词法分析器的状态最小化 词法分析器中的不同接受状态对应于不同的模式，因此需要有不同于DFA化简的初始划分
初始分划为：所有非接受状态集合+对应于各个模式的接受状态集合

85 例子 初始划分增加死状态Φ，用作词法分析的DFA可以丢掉Φ 初始分划：{0137, 7} {247} {8,58}{68}{Φ}

86 Lexical Analysis What? Why? How?