词法分析 cnliying@sina.com.

Presentation on theme: "词法分析 cnliying@sina.com."— Presentation transcript:

1 词法分析

2 什么是词法分析 从左到右逐个字符对构成源程序的字符串进行扫描，依据词法规则，识别出一个一个的标记（token），把源程序变为等价的标记串序列。执行词法分析的程序称为词法分析器，也称为扫描器。

3 构造词法分析器方法 手工方式 通过自动生成工具 LEX

4 词法分析器的本质 基本任务是进行模式匹配，其关键在于分析过程中的模式说明和模式识别方法，在编译分析中即正规表达式和有限自动机

5 本章节内容 词法分析的操作以及相关概念 介绍正规表达式和有限自动机 从正规表达式转化为有限自动机的理论和方法 实现词法分析器的自动生成

6 2.1 扫描处理及缓冲 语法与词法分析器之间的关系  取下一个标记  标记  源程序 词法分析器 语法分析器 符号表

7 2.1 扫描处理及缓冲 标记的分类： 1）关键字，或称为保留字，是特定的字母序列，在相应的程序设计语言中表示特殊含义。
2）标识符，由用户定义的串，在程序中常用做常量名、变量名、过程名等。 3）常数，各种类型的常数，包括整型、实型、布尔型、文字型等，如100，10.12，TRUE，“ABC”等。 4）运算符，包括单算术运算符和逻辑运算符号，如+、*、<等。 5）界符，如逗号、分号等。

8 2.1 扫描处理及缓冲 词法分析器输出用二元式表示（标记种属，标记的属性值），其中，标记种属是语法分析所需要的信息，而标记的属性值则是编译的其他阶段需要的信息。 例： if a > 0 then b = b+1 （IF，—） （ID，指向a的符号表项的指针） （>，—） （NUM，0） （THEN，—） （ID，指向b的符号表项的指针） （=，—） （+，—） （NUM，1）

9 2.1 扫描处理及缓冲 词法分析器的结构 输入子系统 输入 缓冲区 扫描器 标记

10 2.2 正规表达式 串和语言中相关的一些基本概念 ： 术语字母表或字符类表示符号的有限集合，通常用Σ表示 。
字母表上的串是该字母表中符号的有限序列。 串s的长度是s中的符号个数，往往写作 | s | 。 空串是长度为0的特殊串，用ε表示。 在串和语言之上可以进行若干基本运算，包括：选择、连结和闭包。

11 2.2 正规表达式 基本运算 ： 如果x和y是串，则x和y的选择（写成x | y）结果是x或者y 。
如果x和y是串，则x和y的连结（写成x·y或xy）是把y加到x后形成的串。 对于串集合S上的闭包，则定义为：S* = {ε}∪S∪SS∪SSS∪ ………

12 2.2 正规表达式 正规表达式的定义 1）ε和Φ都是∑上的正规表达式，它们所表示的正规集分别是{ε}和Φ；
2）任何a∈∑，a是∑上的一个正规式，它所表示的正规集是{a}； 3）假定r1和r2都是∑上的正规式，，那么，(r1)，r1 | r2，r1·r2，r1*也都是正规式，他们所表示的正规集分别是：L(r1)，L(r1) | L(r2)，L(r1) ·L(r2)，(L(r1))* 4）仅由有限次使用上述三步骤而定义的表达式才是∑上的正规式，仅由这些正规式所表示的字集才是∑上的正规集。 算符的优先顺序为先“*”，再“·”，最后是“|”

13 2.2 正规表达式 命名 为较长的正规表达式可以进行命名，这样对正规表达式的书写非常有帮助。例如：一个或多个数字序列的正规表达式可以写作：
（0|1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）* 若引入名字digit，定义 digit = 0|1|2|3|4|5|6|7|8|9 则原来的正规表达式可以简化为： digit digit*

14 2.2 正规表达式 例 令∑ = {a，b}，则∑上的正规表达式和相应的正规集的例子有： 正规表达式 正规集 a {a} a|b {a，b}
正规表达式 正规集 a {a} a|b {a，b} ab {ab} (a|b)(a|b) {aa，ab，ba，bb} a* {ε，a，aa，aaa，…} （任意个a组成的串） (a|b)* {ε，a，b，ab，…}（所有a、b组成的字符串） b*ab* （刚好包含一个a的由a、b组成的字符串） (a|b)*(aa|bb)(a|b)* 包含相继两个a或相继两个b的由a、b组成的字符串

15 2.2 正规表达式 若r，s，t是正规式，则他们之间满足如下代数规律： r|s = s|r “或”满足交换律。
r|(s|t) = (r|s)|t “或”满足结合律。 (rs)t = r(st) “连接”满足结合律。 r(s|t) = rs|rt “或”满足分配律 (s|t)r = sr|tr εr = r ε连接的恒等特性 rε = r

16 2.2 正规表达式 正规表达式的表示局限性 对于字母表∑={a,b}上的串集合S，由一个a及其前后数目相同的b组成，可表示为：
S = {a, bab, bbabb, ...} = {bnabn | n≠0}

17 2.2 正规表达式 正规表达式的扩展 1）一次或多次重复，用+表示 r+ = rr* r* = ε| r+
3）字母表中的任意字符，用·表示 4）字符范围，常用方括号和连字符表示连续的字符序列 5）不在给定集合中的字母表中的任意字符，用~表示

18 2.2 正规表达式 关键字和标识符 reserved = if | while | then | ... letter = [a-zA-Z]
digit = [0-9] identifier = letter (le-tter|digit)*

19 2.2 正规表达式 数 注释 Nat = [0-9]+ signedNat = (+|-)? Nat
Number = signedNat (“.”nat)? (E signedNat)? 注释 注释格式 正规表达式 //C的注释信息 //(~newline)* ；Scheme的注释信息 ；(~newline)* -- Ada的注释信息 //(~newline)* /*C的注释信息*/ a*(b*~(a|b)a*)*b*

20 2.2 正规表达式 空白格 whitespace = (newline | blank | tab | comment)+

21 2.3 有限自动机 有限自动机（也称为有穷自动机），是描述特定类型算法的数学方法，作为一种语言识别装置，能准确地识别正规集。有限自动机分为两类： 确定的有限自动机（DFA） 非确定有限自动机 （NFA）

22 2.3.1 确定有限自动机 有限自动机的运行 有限控制器 q0 q1 q2 q3 q4 q5 a b 输入带 读头

23 2.3.1 确定有限自动机 定义 确定有限自动机（DFA）是一个五元组M = (K，Σ，δ，s，F)，其中，
2）Σ是字母表，它的每个元素称为一个输入字符； 3）F是接受状态集合，也称为终结状态或结束状态； 4）δ是K×Σ到K的子集的函数，叫做转移函数，如δ(ki， a)=kj，意味着当前状态为ki，输入字符为a时，将转移 到下一状态kj，我们把kj称作 ki的一个后继状态。 5）s∈K 是唯一的一个初始状态。

24 2.3.1 确定有限自动机 确定有限自动机M接受的语言是M所接受的所有字符串的集合，写作L(M) 。
对于Σ*中的任何字符串w，若存在一条从初态到某一接受状态的道路，且这条路上的所有弧的标记符连接成的字符串等于w，则可称w为确定有限自动机M所接受。

25 2.3.1 确定有限自动机 例：设DFA M = (K，Σ，δ，s，F)，其中 K = {q0,q1}，Σ= {a, b}，s = q0，F = {q0}，δ定义为：δ(q0，a) = q0，δ(q0，b) = q1，δ(q1，a) = q1，δ(q1，b) = q0 状态图表示 q1 q0 b a 对于输入串aababa，识别过程为： q0 q1 a b

26 2.3.1 确定有限自动机 digit + _ E

27 2.3.1 确定有限自动机 状态转换图变换成程序 将DFA直接实现于程序的逻辑控制之中，基本上一个语句对应一个DFA状态；程序的大小与状态图中的状态数和边数成正比 用表驱动的方法实现

28 2.3.2 非确定有限自动机 定义 非确定有限自动机（NFA）是一个五元组M = (K，Σ，δ，s，F)，其中，
2）Σ是字母表，它的每个元素称为一个输入字符； 3）F是终结状态集合，也称为可接受状态或结束状态； 4）δ是K×（Σ∪{ε}）到K的子集的函数，叫做转移函数； 5）s∈K 是唯一的一个初始状态。

29 2.3.2 非确定有限自动机 非确定有限自动机与确定有限自动机不同，它相当于对原有的字母表进行了扩展，把ε也包括了进来。此外，非确定有限自动机还需扩展δ转换函数的定义，对于一个确定状态的一个字符转换可以导致多个状态，δ的值是有限机状态的一个集合，即状态集合K的子集。显然，确定有限自动机DFA是非确定有限自动机NFA的特例。

30 2.3.2 非确定有限自动机 识别的语言是所有含有相继两个a或相继两个b的由a、b组成的字符串
例 一个NFA M = (K,Σ,δ,s,F),其中,Σ = {a，b}， K={0,1,2,3,4,5},s = 0,F = {2，5},δ的定义为：δ(0,ε)= {3},δ(0，a)= {0},δ(0,b)= {0,1},δ(1,b)= {2},δ(2,a)= {2},δ(2，b)= {2},δ(3,a)= {4},δ(4,a)= {5},δ(5,a)= {5},δ(5,b)= {5} a，b a ε 5 3 4 1 2 b 识别的语言是所有含有相继两个a或相继两个b的由a、b组成的字符串

31 2.3.2 非确定有限自动机 自动机的等价 对于任何一个非确定有限自动机N，存在一个确定有限自动机M，使得L(M) = L(N)，对于任何两个有限自动机M和M'，若L(M) = L(M')，则称M和M'是等价的。

32 2.4 从正则表达式到有限自动机 词法分析器自动生成的主要工作是将正规表达式的定义转换为等价的确定有限自动机，这工作通常分三步进行。
1）从正规表达式到等价的NFA; 2）从NFA到等价的DFA； 3）优化DFA，产生等价的具有最小状态数的DFA

33 2.4.1从正规式到NFA 正规表达式和有限自动机是等价的。
1）对于Σ上的每个NFA M，可以构造一个Σ上的正规表达式R，使得L（R） = L（M）。 2）对于Σ上的每个正规表达式R，可以构造一个Σ上的NFA M，使得L（R）= L（M） 。

34 2.4.1从正规式到NFA 基本正规表达式对应的NFA ε a

35 2.4.1从正规式到NFA 正规表达式r、s以及rs对应的NFA r … s (a) (b) (c) ε

36 2.4.1从正规式到NFA 正规表达式r | s的NFA r … s ε

37 2.4.1从正规式到NFA 正规表达式r *对应的NFA r … ε

38 2.4.1从正规式到NFA 例 为程序设计语言中标识符的定义letter(letter|digit)*构造相应的有限自动机
ε

39 2.4.1从正规式到NFA 建立(letter | digit)*的有限自动机 digit letter ε

40 2.4.1从正规式到NFA 建立letter(letter | digit)*的有限自动机 digit letter ε

41 2.4.2 从NFA到DFA 子集构造法 DFA M的每个状态，对应于NFA N中的一个状态集，M在读入一个给定的输入串之后处于状态{x，y，z}，当且仅当N可能处在x，y，z中的任何一个状态，让M记住N可能走的全部可能路线，并让M和N平行的工作，M的接受状态将是任何含有N的接受状态的任何集合。M的初始状态是N所处的初始状态及未读任何输入字符时所在的状态的集合，也就是N经过ε弧所可能到达的状态的集合，称此集合为初始状态的闭包。任何状态都有一条隐含的到自身的ε弧转换，初态自身在初态的闭包之中。

42 2.4.2 从NFA到DFA 定义对状态集合S的几个有关运算 ：
1）状态集合S的ε闭包，表示为ε-closure（S）。单个状态s的ε闭包定义为可由一系列（零个或多个）ε转换能达到的状态集合，表示为ε-closure(s)，一个状态的ε闭包总包含它自身。状态集合S的ε闭包则是该集合中每个状态s的ε闭包的联合。 2）状态集合S的a弧转换，表示为move（S，a），定义为状态集合S'，其中S'是所有那些可以从S中的某一状态经过一条a弧而到达的状态的全体。

43 2.4.2 从NFA到DFA 计算其ε闭包的算法 : CALCULATE e_closure(input) {
S = input; //初始化，任何一个状态的ε闭包包含自身 push() //把输入状态全部入状态栈 while (栈非空) POP() //栈顶元素出栈并赋予变量a if (有一条ε弧从状态a到状态b) if(状态b不在S中) {把j加到S中； 把j压入栈中}}} return (S)

44 2.4.3 状态数最小化 自动机理论中的定理： 对于任何给定的DFA，存在一个含有最小量状态的等价的DFA，且这个最小状态的DFA是唯一的。

45 2.4.3 状态数最小化 最小化方法： 去除无效状态； 合并等价状态。 关键在于消除DFA中的等价状态 !

46 2.4.3 状态数最小化 找出DFA的等价类的方法其基本思想是：
将状态放在不同的状态集合中，若在一个状态集合中，含有不等价的状态，就把不等价的状态分开，保持一个集合中的状态等价。分开后，如果一个集合中的状态还有不等价的，就继续分开，直到每个分开的小集合中的状态都等价为止。

47 2.4.3 状态数最小化 DFA状态最小化过程 1）把有限自动机M的状态分为两类，接受状态和非接受状态，形成分划Ⅱ；
2）假设Ⅱ={I(1), I(2), I(3),…，I(n)}，不同子集的状态是可区别的，存在某个I(i)，若存在一个字符a，使得I(i)a不全包括在Ⅱ的某个子集I(j)中，就将I(j)一分为二； 3）重复2）直至子集数目不再增长为止。

48 2.4.3 状态数最小化 最小化DFA digit letter 3' 4' 1' 2'

49 2.6 利用lex建立词法分析器 工作示意图 LEX编译器 LEX源程序 lex.l lex.yy.c C编译器 a.out 输入流 标记流

50 2.6 利用lex建立词法分析器 LEX编译器的工作原理是：
LEX编译器将LEX源程序中的正规式经过若干步骤的转换（正规式NFADFA最小状态数的DFA），最终转换成相应的等价确定有限自动机，并将其动作插入到lex.yy.c中适当的地方。

51 2.6 利用lex建立词法分析器 LEX源程序组织结构 说明部分 %% 转换规则 辅助过程

52 2.6 利用lex建立词法分析器 %{ /* a Lex program that adds line numbers
to lines of text, printing the new text to the standard output */ #include <stdio.h> int lineno = l; %} line .*\n %% {line} { printf ("%5d %s",lineno++,yytext) ; } main( ) { yylex( ); return 0; }

53 2.6 利用lex建立词法分析器 %{ /* a Lex program that changes all numbers from decimal to hexadecimal notation, printing a summary statiatic to stderr */ #include <stdlib.h> #include <stdio.h> int count=0; %} digit [0-9J number {digit}+ %% {number} {int n= atoi(yytext); printf(“%x”,n); if (n > 9) count++;} main( ) { yylex(); fprintf(stderr, “number of replacements = %d”, count); return 0; }

54 2.6 利用lex建立词法分析器 %{ /* Selects only lines that end or begin with the letter 'a'. Deletes everything else. */ #include <stdio.h> %} ends_with_a .*a\n begins_with_a a.*\n %% {ends_with_a} ECHO; {begins_with_a} ECHO; .*\n ; main( ) { yylex( ); return 0; }