第三章词法分析
- 格式：ppt
- 大小：447.50 KB
- 文档页数：30
下载文档原格式
合集下载
第3章 词法分析
确定的有穷自动机DFA (Deterministic Finite Automata) 不确定的有穷自动机NFA (Nondeterministic Finite Automata)
7
关于有穷自动机将讨论以下问题
一、确定的有穷自动机DFA 二、不确定的有穷自动机NFA 三、具有ε动作的FA 四、NFA到DFA的变换
0
等价的DFA
0
1
0
1
1 0 1 2
练习
a X 1 2 b 4 b a 3 a 5 a 6 b Y
b
Ia
{X,1,2} 0 {1,2,3} 1 {1,2,4} 2 {1,2,3,5,6,Y}3* {1,2,4,5,6,Y}4* {1,2,4,6,Y} 5* {1,2,3,6,Y} 6* {1,2,3} {1,2,3,5,6,Y} {1,2,3} {1,2,3,5,6,Y}
41
仅由有限次使用上述3步骤而定义 设字母表为： 的表达式才是上的正规式，仅由这些 正规式所表示的集合才是上的正规集。
和都是上的正规式，它们所表示的 正规集分别为{}和{ }； 任何a ，a是上的一个正规式，它所 表示的正规集为{a}；
假定e1和e2都是上的正规式，它们所 表示的正规集分别为L(e1)和L(e2)，那么， (e1), e1 e2, e1e2, e1也都是正规式,它们所表 示的正规集分别为L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1))。
DFA M=（{S，U，V，Q}，{a，b}， δ，S，{Q}）其中δ定义为：
δ （S，a）=U
δ （S，b）=V
δ （V，a）=U
δ （V，b）=Q
δ （U，a）=Q
第三章 词法分析和有穷自动机
ε
ε
2
ε
6 b
ε
f
3.4.5 DFA的最小化（化简）
• 最少状态DFA 对于一个DFA M，存在一个最少状态DFA M’， 使得L(M’)=L(M)。 (a)没有多余状态 (b)没有两个状态是互相等价的 结论： 一个NFA 对应的DFA不惟一 但它对应的最小化DFA不计同构是惟一的
• 多余状态的例子 a
例
正规式 φ
ε
a a|b ab (a|b)(a|b) a* ba* (a|b)*
正规集 φ {ε } {a} L(a|b)=L(a) ∪ L(b)={a,b} L(ab)=L(a)L(b)={ab} {aa,ab,ba,bb} { ε ,a,aa,aaa,…} {b,ba,baa,baaa,…} {所有由a和b组成的字}
• 例 DFA M=({0,1,2,3},{a,b}, f ,0,{3}) 其中 f 为： f (0,a)=1 f (0,b)=2 f (1,a)=3 f (1,b)=2 f (2,a)=1 f (2,b)=3 f (3,b)=3 f (3,a)=3
3.4.1 确定有穷自动机(DFA) • DFA的表示方法 两种：矩阵和图形的方式 矩阵称为状态转换矩阵 图形称为状态转换图
• NFA M所接受字符串的集合称为NFA M所能 识别的语言，记为L(M)。 • NFA的确定化 DFA是NFA的特例
NFA M存在与之等价的DFA M’,L(M)=L(M’) 与某一NFA等价的DFA不惟一 正规式 NFA 正规文法 DFA
3.4.4 NFA 确定化
• 状态集合I的空闭包：ε -closure(I) 它是一个状态集合，包含 ： ♠ I中任何状态q ♠ I中任何状态q经任意条空弧到达的任何状态 • 状态集合I的a弧转换：Ia 定义一个状态集J，J是I中所有状态经一条a 弧到达的状态的全体 Ia＝ε -closure(J)
第三章词法分析
五、词法分析程序的输出形式
单词--是程序语言的基本语法符号。 如：基本字、标识符、常数、运算符、界符等。 词法分析器中单词的输出形式：
（单词类别、单词内部码值）
2019/10/14
中南大学软件学院 陈志刚
11
第三章 词法分析
3.1 词法分析概述
五、词法分析程序的输出形式
词法分析程序输出的单词符号通常用二元式表示： （单词种别，单词自身的值）
5.字的长度：
|α|
6.Σ上字的全体： Σ*
7.字的连接：
字α与字β的连接记为αβ
2019/10/14
中南大学软件学院 陈志刚
30
第三章 词法分析
3.3 正规式与有限自动机
一、基本概念
一个状态转换图只包含有限个状态，有一个初态，
终态用双圈表示。一个状态转换图可识别一定的字
符串。
状态都是非终结符号
例1：
字母或数字
S：开始状态 E：终止状态，用双圈表示 I：标识符状态
S
I
E
字母
数字
2019/10/14
中南大学软件学院 陈志刚
16
一、状态转换图
空白
0
字母
第三章 词法分析
字母或数字
中南大学软件学院 陈志刚
22
第三章 词法分析
四、应用状态转换图识别句子
如果x是相应文法的句子便必须能从开始状态出发， 顺着弧的方向行进到终止状态。其步骤如下: (1)从开始状态开始，以它作为当前状态，并从x 的最左字符开始重复步骤2，直到到达x的右端为止； (2)扫描x的下一字符，在当前状态射出的各个弧 中找出标记有该字符的弧，并沿此弧前进，以达到 的状态作为下一当前状态。
第3章 词法分析 (编译原理 陈火旺)
标识符的符号表入口地址作为其单词符号的属性值,常
每个基本字占一个单词种别，单词符号的属性值缺省。
对于界符，运算符通常一个符号一个种别，单词符号的
属性值缺省
例: 参见P42.表3.1 单词符号及种别编码
10
3.1.3 词法分析器作为独立子程序
词法分析可采用如下两种处理结构：
把词法分析程序作为主程序。将词法分析作为
19
3.2.1 正规文法、正规式与正规集
正规集：由正规文法产生的语言所构成的集合。
注：正规集是集合，可有穷也可无穷。 可通过正规式来形式化表示。
对于一个正规文法的语言提炼出一个简洁的公式，用这个
式子来对它进行形式化的表示，这个式子叫正规式。
正规式：也称正则表达式,是说明单词的模式的一种重要的 表示法（记号）；是定义正规集的数学工具；用来描述单词 符号。
在设计一个编译程序时，通常是把对源程序的结构分析分为词 法分析和语法分析两个相对独立的阶段来完成。
第一，描述单词的结构比描述源程序的其它语法结构要简单
得多，仅使用3型文法也就基本够用了。
第二，由于把词法分析和语法分析分开，可使编译程序各部
分的功能更为单一，整个编译程序的结构也更加清晰，从而 有利于编译程序的编写和调整。 上述词法分析和语法分析两个阶段的划分，仅仅是对整个编译 程序的逻辑功能而言，而不一定指的是编译程序的执行流程。
25
例3.2 判断下述正规式之间是否等价： (1)b(ab)*与(ba)*b (2)(ab)*与a*b* 解: (1) b(ab)*对应的正规集是b后面出现任意多个ab对
L(b(ab)*)={b,bab,babab, ……}
第3章--词法分析
第3章--词法分析第三章词法分析知识结构：功能词法分析器的要求单词符号分类词法分析单词内部形式器的设计设计⽅发词法分析器的设计状态图词法分析器组成正规表达式单词描述⼯具正规集词法分析器正规⽂法确定有限⾃动机（DFA ）单词识别⼯具⾮确定有限⾃动机（NFA ）DFA 的最⼩化正规式与FA 的等价转换等价转换正规⽂法与FA 的等价转换第⼀节对词法分析器的要求⼀、词法分析器的功能输⼊源程序，输出单词符号（⼆元式表⽰）。
关键字：是由程序语⾔定义的具有固定意义的标识符。
标识符：⽤来表⽰各种名字，如变量等。
常数：常数的类型有整型，实型等。
运算符：算术运算符，关系运算符，逻辑运算符。
界限符：逗号，分号等。
三、单词符号内部的表⽰形式内部的单词符号TOKEN字（⼆元式），TOKEN字占⽤机器字的长度，依据信息量的多少⽽定。
1、TOKEN字结构VALUE：表⽰单词符号的属性（符号表指针）。
2、TOKEN的作⽤CLASS：⽤于语法分析器对源程序结构的分析。
VALUE：⽤于语义分析器对源程序具体操作的分析。
3、单词种别码划分原则CLASS：关键字，运算符，界限符（编译程序定义的符号）使⽤⼀字⼀种编码。
VALUE值省略。
VALUE：标识符，常数（⽤户定义的符号），存放符号表常数表的指针。
标识符，常数每⼀类为⼀种编码。
例：BEGIN A：= B END；词法分析结果：符号表（BEGIN，---- ）Array（A ，K1 ） K1（：= ，--- ）（B ，K3 ） K3（END ，--- ）（；，--- ）四、词法分析器的结构1、⼀遍扫描（交互式结构）。
2、多遍扫描（独⽴式结构）。
第⼆节词法分析器的设计⼀、设计步骤1、确定词法分析器的接⼝关系；2、确定单词分类和TOKEN字的结构；3、对每⼀类单词构造状态转换图；4、根据状态转换图设计算法。
⼆、功能描述1、组织源程序输⼊；2、按词法规则拼读单词符号，并转换成⼆元式；3、删除注解⾏，空格和⽆⽤符号；4、检查词法错误。
编译原理 第三章 词法分析
5、界符：如逗号、分号、括号、/*，*/ 等。它是确定的。
单词符号的表示形式：词法分析器所输出的单词符号常常表示成
二元式（单词种别，单词自身的值）。 单词种别可以用以下形式表示： 1、一类单词统一用一个整数值代表其属性。例如：1代表关键字， 2代表标识符等。 2、每一个单词一个类别。例如：1代表BEGIN，2代表END等。 单词自身的值可以表示成：常量的二进制表示；常量、变量等在符号表 种的地址码，等等。
例3-3：简单的状态转换图示例：
1
X
2
初态
终态
Y
(a)转换图示例 数字
3
从0状态到1状态 可能出现字母
字母或数字 字母 其他
0
1
2
*
0
数字
1
其他
2 *
（b）识别标识符的转换图
（c）识别整数的转换图
例3-4：识别FORTRAN实型常数的转换图：
例如下列实型常数可 以被以下转换图识别： 1.23E+4
•scanner当作一遍。 •把scanner当作子程序。
scanner
源程序
scanner作为一遍
设计前提：
输入
列表 把scanner作为一个独立的子程序； 输入缓冲区 预处理 • 词法分析器的任务为输出单词符号。 子程序
•
扫描缓冲区
预 处 理 部 分
•必要性：编辑性字符如空白符、回车符等，除了出现在文字和 扫描器 常数中以外，在别处出现都没有意义。 扫 单词符号 描 •功 能： 剔除无用字符。 器 语法分析器 •实 现： 预处理子程序。 图2.1 词法分析器
例3-2 ：下述C++代码段：while ( i >= j ) i - -； 经词法分析器处理以后，它将被转换为如下的单词符号串
单词符号的表示形式：词法分析器所输出的单词符号常常表示成
二元式（单词种别，单词自身的值）。 单词种别可以用以下形式表示： 1、一类单词统一用一个整数值代表其属性。例如：1代表关键字， 2代表标识符等。 2、每一个单词一个类别。例如：1代表BEGIN，2代表END等。 单词自身的值可以表示成：常量的二进制表示；常量、变量等在符号表 种的地址码，等等。
例3-3：简单的状态转换图示例：
1
X
2
初态
终态
Y
(a)转换图示例 数字
3
从0状态到1状态 可能出现字母
字母或数字 字母 其他
0
1
2
*
0
数字
1
其他
2 *
（b）识别标识符的转换图
（c）识别整数的转换图
例3-4：识别FORTRAN实型常数的转换图：
例如下列实型常数可 以被以下转换图识别： 1.23E+4
•scanner当作一遍。 •把scanner当作子程序。
scanner
源程序
scanner作为一遍
设计前提：
输入
列表 把scanner作为一个独立的子程序； 输入缓冲区 预处理 • 词法分析器的任务为输出单词符号。 子程序
•
扫描缓冲区
预 处 理 部 分
•必要性：编辑性字符如空白符、回车符等，除了出现在文字和 扫描器 常数中以外，在别处出现都没有意义。 扫 单词符号 描 •功 能： 剔除无用字符。 器 语法分析器 •实 现： 预处理子程序。 图2.1 词法分析器
例3-2 ：下述C++代码段：while ( i >= j ) i - -； 经词法分析器处理以后，它将被转换为如下的单词符号串
第三章词法分析
根据定义比较容易证明上述性质，利用这些性质可以化简正规式，证明 正规式的等价关系
说明：*上的某些集合若不能用正规表达式表示，则该集合不是正规集。 如： ={a,b},L(G)={anbn| n0}就不是正规集，因为它不能用正规式表示。 （可以用上下文无关文法Z∷=aZb|ab|ε产生）可以证明，凡是由正规文 法所产生的语言一定是正规集，即可由正规式表示 。
18
第三章 词 法 分 析
§3.6正规表达式和有穷自动机
一、正规表达式和正规集的定义
1.非形式定义 2.递归定义
二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机的关系 四、由正规表达式构造确定有穷自动机
1.由正规表达式e构造转换系统 2.由转换系统构造确定有穷自动机ＤＦＡ(子集法) 3.由正规文法构造正规表达式
1.由正规表达式e构造转换系统 2.由转换系统构造确定有穷自动机ＤＦＡ(子集法) 3.由正规文法构造正规表达式
五、确定有穷自动机的化简
1.等价和可区分的概念 2.确定有穷自动机的化简方法
2
§3.6正规表达式和有穷自动机
为什么引入正规表达式？
由正规文法构造状态转换图，再根据状态转换 图可以构造有穷自动机，往往很麻烦，但是， 对于一些复杂的正规文法，如果将其先转换成 正规表达式，再由正规表达式来产生有穷自动 机就方便得多。而且正规表达式的引入有助于 词法分析程序的自动生成，它还广泛应用于模 式识别和文献目录检索等。
五、确定有穷自动机的化简
1.等价和可区分的概念 2.确定有穷自动机的化简方法
16
第三章 词 法 分 析
§3.6正规表达式和有穷自动机
一、正规表达式和正规集的定义
1.非形式定义 2.递归定义
说明：*上的某些集合若不能用正规表达式表示，则该集合不是正规集。 如： ={a,b},L(G)={anbn| n0}就不是正规集，因为它不能用正规式表示。 （可以用上下文无关文法Z∷=aZb|ab|ε产生）可以证明，凡是由正规文 法所产生的语言一定是正规集，即可由正规式表示 。
18
第三章 词 法 分 析
§3.6正规表达式和有穷自动机
一、正规表达式和正规集的定义
1.非形式定义 2.递归定义
二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机的关系 四、由正规表达式构造确定有穷自动机
1.由正规表达式e构造转换系统 2.由转换系统构造确定有穷自动机ＤＦＡ(子集法) 3.由正规文法构造正规表达式
1.由正规表达式e构造转换系统 2.由转换系统构造确定有穷自动机ＤＦＡ(子集法) 3.由正规文法构造正规表达式
五、确定有穷自动机的化简
1.等价和可区分的概念 2.确定有穷自动机的化简方法
2
§3.6正规表达式和有穷自动机
为什么引入正规表达式？
由正规文法构造状态转换图，再根据状态转换 图可以构造有穷自动机，往往很麻烦，但是， 对于一些复杂的正规文法，如果将其先转换成 正规表达式，再由正规表达式来产生有穷自动 机就方便得多。而且正规表达式的引入有助于 词法分析程序的自动生成，它还广泛应用于模 式识别和文献目录检索等。
五、确定有穷自动机的化简
1.等价和可区分的概念 2.确定有穷自动机的化简方法
16
第三章 词 法 分 析
§3.6正规表达式和有穷自动机
一、正规表达式和正规集的定义
1.非形式定义 2.递归定义
第三章词法分析
第三章词法分析前两章为研究编译技术作了一些概念和技术上的先期铺垫，在本章的词法分析内容里将开始介绍编译技术的第一个重要技术点：词法分析。
本章的重点与难点是：词法分析器的任务与设计、状态转换图的实现、由正规表达式（正规式）构造非确定有限自动机、非确定有限自动机的确定化、确定有限自动机的最小化，正规式，正规集；词法分析器自动生成。
本章主要内容是：词法分析器任务，词法分析器设计，正规表达式与有限自动机，词法分析器自动生成。
对于本章，读者应该掌握：词法分析器的作用与设计，状态转换图的实现；正规式，正规集，正规定义；确定有限自动机，非确定有限自动机，NFA到DFA的转化；从正规式构造自动机；词法分析器自动生成。
3.1学习指导3.1.1词法分析器的功能词法分析的任务是识别源程序中具有独立含义的最小语法单位——符号或单词，如标识符，无正负号常数和界符等等。
并把源程序转换为等价的内部表示形式。
功能：读入源程序字符串；识别单词（符号）；转换成属性字；并实现一些其他的简单工作：删除注解，预加工处理等等。
执行词法分析的程序称为词法分析程序，或词法分析器，或扫描器。
词法分析的实现有两种方式：相对独立：词法分析作为子程序。
当语法分析程序需要读下一个符号的时候，调用这个子程序。
完全独立：词法分析程序作为单独的一遍来实现。
常用的做法：将词法分析程序安排成一个子程序（过程），每当语法分析需要一个单词时就调用这个子程序；每调用一次，就向语法分析程序提供一个单词的二元组。
词法分析器的功能是输入源程序，输出单词符号。
单词符号是一个程序语言的基本语法符号。
程序语言的单词符号一般可以分为5类：（1）基本字（关键字、保留字）：具有特殊含义的标识符，不作它用，有分隔语法的作用；（2）标识符：表示各种名字；（3）常量：整型、实型、布尔型、字符型；（4）运算符：算术、逻辑、关系运算符；（5）界符：包括，；，（，），：，等等。
扫描器的输出格式：输出格式为二元组序列，每个单词对应一个二元组，形式为（类号，内码）。
第3章词法分析
例：语言L[G]={abn|n>=1},其正规文 语言L[G]={ab |n>=1},其正规文 法为G[A]： 法为G[A]： A→aB A→aB B→bB| B→bB| b 画出状态转换图
例：部分单词的状态图
Letter,digit
s
letter digit
其它 （IDN，入口） ，入口） digit 其它 （NUM，值） ， （ASG，_） ， ） =
3.2 状态转换图
•识别标识符的流程图 识别标识符的流程图 开始
出口 N N 数字 Y
字母 N 出口
Y
取字符
字母 Y
结点：状态用○表示；终态用◎表示 结点：状态用○表示；终态用◎ 有向弧 弧标记 初态 开始 1 letter 2 ── 箭头 ── 输入字符 Letter,d号的表示
• 常用单词种别 常用单词种别——分类 分类
–各关键字（保留字、基本字） 各关键字（保留字、基本字） 各关键字 –各种运算符 各种运算符 –各种分界符 各种分界符——各用一个种别码标识（特定符号类） 各用一个种别码标识（ 各种分界符 各用一个种别码标识 特定符号类） –其它标识符 其它标识符——用一个种别码标示（非特定符号类） 用一个种别码标示（ 其它标识符 用一个种别码标示 非特定符号类） –常数 常数——用一个种别码标示（非特定符号类） 用一个种别码标示（ 常数 用一个种别码标示 非特定符号类）
• 例：文法 文法G[Z]： ： • Z→ Z→Za| Aa| Bb • A→ A→Ba | a • B→ B→Ab| b • 画出状态转换图
2、从右线性正规文法出发，构造状态图 从右线性正规文法出发， 以每个非终结符为状态结点， 1. 以每个非终结符为状态结点 ， 开始符号 对应初态S 对应初态S ； 2.增设一个终态 Z； 3. 对于规则 A→aB ， 画从状态 A 到 B 的 A→aB， 弧，标为 a； A→a， 4. 对于规则 A→a ， 画从状态 A 到终态 Z 的弧， 的弧，标为 a。
第三章词法分析
7
源程序的输入
在内存开辟缓冲区，将程序文本放进该缓冲区 预处理：删除无用字符等 词法分析程序对缓冲区扫描时，设置两个指示器，
一个指向当前正在识别的单词的开始位置，称为 起始指针；另一个用于向前搜索，以寻找单词的 终点，称为扫描指针。
起始指针 搜索指针
8
扫描缓冲区的大小
应当保证单词符号不被缓冲区的边界打断 使用循环链表实现 规定单词符号的大小不超过整个链表的容量
注意：一种语言的单词如何分类、怎样编码，主要取决于 技术上的方便。
13
举例
例如：程序段 if(a>1) b=10;
假定基本字、运 算符、界符都是 一符一种。
它所输出的单词符号是：
(2,)
基本字if
(29,)
左括号(
(10,’a’)
标识符a
(23,)
大于号>
(11,’1’的二进制) 常数1
(30,)
词法分析程序输出的单词符号通常用二元式表示：（单词 类别，单词自身的值）
单词类别：表示单词种类，常用整数编码，它是语法分析 需要的
单词自身的值：是编译中其他阶段所需要的信息
如果一个种别只含一个单词符号，那么该单词符号的类别编码就完 全代表它自身的值。 把单词符号存储在符号表中。不同种类的单词符号可能具有不同类 型的属性。可以用不同种类的符号表实现。
对于字母表∑，我们感兴趣的是它的一些特 殊字集－正规集。
正规集是字母表Σ上的符合一定规则的符号串构成
的集合 正则表达式是一种适合描述符号的表示法，可由它 定义正规集。
20
正规式(regular expression)
定义（正规式和它所表示的正规集）：
设字母标为 ❖ 1 和都是上的正规式，它们所表示的正规集分别为{}
编译原理第三章词法分析
L→ a | b | … | z | A | B | … | Z D → 0 | 1 | … | 9 <标识符> → L(L|D|_)* <无符号正整数> → DD*
z19
step1 : 对语言的各类单词分别构造状态图；
step1
L
1
2
other
*
3 其中： other表示非L| D | _字符
z8
3.2.1 单词与属性字
注意：
(1) 同一个字符开头+后续字符->跨多个单词类；
(2) 非单词成分和预处理成分；
•例:源程序注释；/* …….*/
预处理指令：
•# define… # include…
z9
3.2.1 单词与属性字
2. 属性字 对所识别的单词的数据结构表示。
控制线
数据线
X : 固定长度的存储空间 ; z16
预处理程序（作用）
(1) 减少内存空间占用；
(2) 减轻扫描器实质性处理的负担；
预处理程序主要任务：
(1) 滤掉源程序中的非单词成分(如无用空格；换行
符等)；
•滤掉注释；
(2) 实际的预处理工作
•宏替换； •文件包含的嵌入；
L1= （ T，C）
属性字 Token
Code
刻画单词类别（单词性质）
如:标识符；运算符；…
单词的内码值（可空）
z10
说明
单词类别通常用整数编码 单词类别提供给语法分析程序使用 单词符号属性信息记录单词符号的特征或特性 单词的属性值提供给语义分析程序使用
编码形式：
一类一种：关键字、标识符、常数、运算符、界符 一字一种：关键字、运算符、分界符各一码
z19
step1 : 对语言的各类单词分别构造状态图；
step1
L
1
2
other
*
3 其中： other表示非L| D | _字符
z8
3.2.1 单词与属性字
注意：
(1) 同一个字符开头+后续字符->跨多个单词类；
(2) 非单词成分和预处理成分；
•例:源程序注释；/* …….*/
预处理指令：
•# define… # include…
z9
3.2.1 单词与属性字
2. 属性字 对所识别的单词的数据结构表示。
控制线
数据线
X : 固定长度的存储空间 ; z16
预处理程序（作用）
(1) 减少内存空间占用；
(2) 减轻扫描器实质性处理的负担；
预处理程序主要任务：
(1) 滤掉源程序中的非单词成分(如无用空格；换行
符等)；
•滤掉注释；
(2) 实际的预处理工作
•宏替换； •文件包含的嵌入；
L1= （ T，C）
属性字 Token
Code
刻画单词类别（单词性质）
如:标识符；运算符；…
单词的内码值（可空）
z10
说明
单词类别通常用整数编码 单词类别提供给语法分析程序使用 单词符号属性信息记录单词符号的特征或特性 单词的属性值提供给语义分析程序使用
编码形式：
一类一种：关键字、标识符、常数、运算符、界符 一字一种：关键字、运算符、分界符各一码
第三章_词法分析
∑*的子集U和V的连接（积）定义为
UV { | U, V}
V自身的 n次积记为 V n VV V
n
规定V0={}，令
V * V 0 V1 V 2 称V*是V的闭包;
记 V VV * V 1 V 2
称V+是V的正规闭包。
3.3.1 正规式与正规集
有限自动机
有限自动机所讨论的问题
确定的有限自动机DFA 不确定的有限自动机NFA NFA的确定化 DFA的最小化
标识符单列一种；标识符自身的值表示成按机器字节划分 的内部码。
常数按类型分种；常数的值则表示成标准的二进制形式。
3.1.1 词法分析器的功能和输出形式
例 FORTRAN程序
IF (5.EQ.M) GOTO 100 输出单词符号： 逻辑IF (34，-) 左括号 (2，-) 整常数 (20， ‘5’的二进制) 等号 (6，-) 标识符 (26， ‘M’) 右括号 (16，-) GOTO (30，-) 标号 (19， ‘100’的二进制)
END;
状态转换图实现示例
'0'..'9':
BEGIN WHILE DIGIT DO BEGIN CONCAT;GETCHAR END; RETRACT; RETURN ($INT，DBT)
END;
'=': RETURN ($ASSIGN，-); '+': RETURN ($PLUS，-);
状态转换图实现示例
4 算符和界符的识别
把多个字符符合而成的算符和界符拼合成一个 单一单词符号。：=， **， .EQ.
3.2.3 状态转换图
第三章词法分析终.ppt
在一个上的确定有穷自动机M，使得V=L(M) ❖DFA的确定性表现在转换函数f:K×∑→K是一个单值
函数，也就是说,对任何状态k∈K和输入符号a ∈∑， f(k,a)唯一地确定了下一个状态
29
二.不确定的有穷自动机NFA ❖一个NFA：M=（K，，f，S，Z） ➢K是一个有穷集，它的每个元素称为一个状态 ➢是一个有穷字母表，它的每个元素称为一个输入符号 ➢f是一个从K * 到K的子集的映像，即：K* * →2 K ➢SK是一个非空初态集 ➢ZK是一个终态集
15
❖设r,s,t为正规式，正规式服从的代数规律有：
➢rs=sr
“或”服从交换律
➢r(st)=(rs)t “或”的可结合律
➢(rs)t=r(st)
“连接”的可结合律
➢r(st)=rsrt
(st)r=srtr
分配律
➢r=r
r=r
是“连接”的恒等元素（零一律）
➢rr=r
r=rrr… “或”的抽取律
16
A (a|d)*
R2 S aA
A (a|d)B A
B (a|d)B B
R3 S aA
A
A aB
A dB
B aB
B dB
B
18
2.将正规文法转换成正规式： 基本上是上述过程的逆过程，最后只剩下一个开始符
号定义的正规式，其转换规则如表4.1所示：
19
例3.5 G[s]: S aA A dA
Sa Aa
5
二.词法分析程序的输出 1.单词符号一般可分为下列五种： ❖基本字（关键字）：begin、end、if、while、var ❖标识符：常量名、变量名、过程名 ❖常数（量）：25、3.1415、true、“ABC” ❖运算符：＋、－、*、＜= ❖界符：逗点、分号、括号 2.输出表示： ❖（单词种别，单词自身的值） ➢单词种别：语法分析需要的信息 ➢单词自身的值：编译其他阶段需要的信息
函数，也就是说,对任何状态k∈K和输入符号a ∈∑， f(k,a)唯一地确定了下一个状态
29
二.不确定的有穷自动机NFA ❖一个NFA：M=（K，，f，S，Z） ➢K是一个有穷集，它的每个元素称为一个状态 ➢是一个有穷字母表，它的每个元素称为一个输入符号 ➢f是一个从K * 到K的子集的映像，即：K* * →2 K ➢SK是一个非空初态集 ➢ZK是一个终态集
15
❖设r,s,t为正规式，正规式服从的代数规律有：
➢rs=sr
“或”服从交换律
➢r(st)=(rs)t “或”的可结合律
➢(rs)t=r(st)
“连接”的可结合律
➢r(st)=rsrt
(st)r=srtr
分配律
➢r=r
r=r
是“连接”的恒等元素（零一律）
➢rr=r
r=rrr… “或”的抽取律
16
A (a|d)*
R2 S aA
A (a|d)B A
B (a|d)B B
R3 S aA
A
A aB
A dB
B aB
B dB
B
18
2.将正规文法转换成正规式： 基本上是上述过程的逆过程，最后只剩下一个开始符
号定义的正规式，其转换规则如表4.1所示：
19
例3.5 G[s]: S aA A dA
Sa Aa
5
二.词法分析程序的输出 1.单词符号一般可分为下列五种： ❖基本字（关键字）：begin、end、if、while、var ❖标识符：常量名、变量名、过程名 ❖常数（量）：25、3.1415、true、“ABC” ❖运算符：＋、－、*、＜= ❖界符：逗点、分号、括号 2.输出表示： ❖（单词种别，单词自身的值） ➢单词种别：语法分析需要的信息 ➢单词自身的值：编译其他阶段需要的信息
【编译原理】第三章词法分析
【编译原理】第三章词法分析⼀，词法分析器的作⽤词法分析是编译的第⼀阶段。
词法分析器主要任务是读⼊源程序的输⼊字符、将他们组成词素，⽣成并输出⼀个词法单元序列，每个词法单元对应于⼀个词素。
分析部分：词法分析、语法分析（简化编译器设计、提⾼编译器效率、增强编译器可移植性）1）词法单元：词法单元名和可选的属性值组成。
关键字、操作符……2）模式：词法单元词素可能具有的形式，当词法单元是关键字时，模式就是这个关键字的字符序列3）词素：源程序中的⼀个字符序列，它和某个词法单元模式匹配。
4）词法错误：识别出某个错误词素，继续判断下⼀个词素⼆，输⼊缓冲1）我们⾄少向前看⼀个字符，才能判断当前词素是否到头。
2）对付⼤型源程序，需要处理⼤量字符。
处理往往需要很多时间，我们采⽤两个交替读⼊的缓冲区。
（详见73）三，词法单元的规约1）我们会不会⽤完缓冲区？通常对于⽐较长的字符串我们采⽤ ”+“的形式链接起来。
2）正则表达式：letter_（letter_ | digit) * 表⽰字母开头 0个或多个字母或数字3）正则表达式例⼦a |b {a, b}(a | b) (a | b ) {aa, ab, ba, bb}aa | ab | ba | bb {aa, ab, ba, bb}a* 由字母a构成的所有串集(a | b)* 由a和b构成的所有串集复杂的例⼦( 00 | 11 | ( (01 | 10) (00 | 11) * (01 | 10) ) ) * 010011010000100000101110013）正则表达式扩展1>⼀个或多个实例⼀元后缀算符“+”的意思是“⼀个或多个实例”,即正规式a+表⽰⼀个或多个a的所有串的集合。
算符+和算符*有同样的优先级和结合性。
代数恒等式 r* = r+ | 和r+ = rr*表达了这两个算符之间的关系。
2>零个或⼀个实例⼀元后缀算符？的意思是“零个或⼀个实例”，r？是r | 的缩写。
第三章 词法分析
从正则表达式到DFA 从正则表达式到DFA
正则式 替换 规则 NFA 子集法 DFA 最少化
最简的DFA 最简的
从NFA到DFA (确定化) NFA到 确定化) DFA的化简 最少化） DFA的化简（最少化） 的化简（
从NFA到DFA NFA到
P49~50 : 对任意的NFA M’，可构造等价的DFA M， 对任意的NFA M’，可构造等价的DFA M，即 接受相同串的字。 接受相同串的字。 通过求状态集合的ε 通过求状态集合的ε-闭包和子集法构造实现由 NFA到DFA的转换 NFA到DFA的转换。 的转换。 一个集合I M’的状态集的子集 的状态集的子集） 一个集合I（I是M’的状态集的子集）的εCLOSURE(I)： CLOSURE(I)： (1)若q∈I,则q ∈ε-CLOSURE(I) (1)若 I,则 (2)若q∈I,则从q出发经任意ε弧 而到达的任何状态 I,则从 出发经任意ε 则从q q ‘∈ε-CLOSURE(I) ‘∈
第三章
词法分析
一、词法分析器的要求 二、词法分析器的设计 三、正规表达式与有限自动机
词法分析
词法分析或扫描阶段可将源程序作为字符文件读 并将其分为若干记号。 入，并将其分为若干记号。 记号类似于单词， 记号类似于单词，表示源程序中信息单元的字符 序列。典型的有关键字、标识符、运算符、 序列。典型的有关键字、标识符、运算符、标点 符号和常量等等。 符号和常量等等。 扫描程序从输入字符的开头识别或匹配某种格 式的字符。 式的字符。 记号的格式说明：正则表达式。 记号的格式说明：正则表达式。 记号的识别方法：有限自动机。 记号的识别方法：有限自动机。 执行词法分析的程序成为词法分析器。
例1：P47 例3.1 例2：令Σ={a，b，c}， Σ上串集合对应 ={a， c}， 的正则表达式： 的正则表达式： 1）仅包含一个b的所有串的集合的正则 仅包含一个b 表达式： 表达式： (a|c)*b(a|c)* 例如， abc、abaca、baaaac、 例如，串b、abc、abaca、baaaac、 ccbaca可与上述正则表达式匹配 ccbaca可与上述正则表达式匹配。 可与上述正则表达式匹配。
3章词法分析
一个状态转换图可用于接受（或识别） 一定的符号串。 一个状态转换图可用于接受 （ 或识别 ） 一定的符号串 。 在状态转换图中从初始状态到某一终止状态的序列为路 在状态转换图中从初始状态到某一终止状态的序列为 路 。 对于某一符号串β，在状态转换图中，若存在一条路产生β， 对于某一符号串 ， 在状态转换图中 ， 若存在一条路产生 ， 则称状态转换图接受（或识别）该符号串β，否则符号串β 则称状态转换图接受 （ 或识别 ） 该符号串 ， 否则符号串 不能被接受。能被状态转换图TG接受的符号串的集合记为 不能被接受。 能被状态转换图 接受的符号串的集合记为 L(TG)，称为状态转换图所能识别的语言。 状态转换图所能识别的语言。 ，称为状态转换图所能识别的语言 由以上状态转换图可见， 字母表Σ上的符号串： 01 10 0100 0111 1011 010011 011100 …… 都能被上述转换图所接受。
(4)输入缓冲区的处理：显然，无论缓冲区设定为多大，都 输入缓冲区的处理：显然，无论缓冲区设定为多大， 输入缓冲区的处理 不能保证单词不会被它的边界打断，若有单词TEST123， 不能保证单词不会被它的边界打断，若有单词 ， 可能在缓冲区中成为： 可能在缓冲区中成为： ……………… ………….TES 在这种情况下，即使通过假读读到缓冲区的最后一个字符， 在这种情况下，即使通过假读读到缓冲区的最后一个字符， 但仍不能找到该单词的右边界，这时， 但仍不能找到该单词的右边界，这时，若从外存上再读一 部分源程序进入缓冲区，则会将没有处理过的字符(TES) 部分源程序进入缓冲区，则会将没有处理过的字符(TES) 冲掉。为此，我们可将缓冲区分成相等的两个区域： 冲掉。为此，我们可将缓冲区分成相等的两个区域： 单词长度有无限 制？ •两个半区互补使用
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
sort
字母 数字 / 界符
’
RECOGID RECOGDIG HANDLCOM RECOGDEC RECOGSTR
LOOKUP
第三章词法分析
17
一、 手工构造识别单词的DFA m
根椐DFA识别单词的定义，在研究给定程 序语言单词结构的基础上，能直接构造出识 别它的DFA m。例如：对于C语言
整数：非空数字串。
第三章 词法分析
第三章词法分析
编译器的各个阶段：
编译器是分
符
阶段执行的。 号
管
每个阶段将
理
源程序从一
表
种表示转换
成另一种表
示
编译的各
个阶段
源程序
词法分析器
语法分析器
错 误
处
语义分析器
理
器
中间代码生成器
代码优化器
代码生成器
第三章词法分析
2
3. 1 词法分析程序的设计：
词法分析器的功能，输出，把它组 织成单独程序
if <12 ,
>
I
<25 , 符号表入口 >
＞ <39 ,
>
J
<25 ,符号表入口 >
Then <20 ,
>
词I 法＝
<25 ,符号表入口 >
<36 ,
>
分0
<26 ,常数表入口 >
析 else <8 ,
>
j <25 ,符号表入口 >
= <36 ,
>
1
<26 ,常数表入口 >
第三章词法分析
6
三、词类和属性 程序语言单词的分类： 1．关键字(保留字或基本字)：begin,end 2．标识符：用来表示各种名字 3．字面常数：256，3 .14，true,‘abc’ 4． 运算符：如，＋、－、*、/ 等等 5．分界符：如逗号，分号，冒号等
E
12e-4
d
d
-
d
0d 1.
2
d3
E
4
+
5
d
6
7
d
1000
3.1415
第三章词法分析
0.1e+1
4
20
二、 编写词法分析程序
根据画出的状态转换图（识别单词的）构 造词法分析程序，每个状态对应一段程序， 完成到达此状态的工作；词法分析程序的控 制程序模拟状态转换图的状态转换。
在识别标识符的过程中，要拼写出来，并和 保留字区别开来；识别出的标识符要填入符 号表中
第三章词法分析
10
对于常数， 其单词自身的属性常用其在 常数表中的入口指针来表示
第三章词法分析
11
以a 语= 句b 子+ ac=*b+d c*d 为例，假设按表 3.1为单词编码，词法分析后的结果为：
Token字
符号表
<25,
>
<36, -------- >
a 25 B 25
<25,
>
C 25
<32, -------- >
为了构造词法分析器，要研究构词法， 每种词类的结构模式以及识别它的数 学模型——有穷自动机。它的模拟程 序可以作为词法分析器的控制程序。
32 1确定的有限自动机（DFA） 32 2构造识别单词的DFA 32 3 编写词法分析程序
第三章词法分析
16
分析程序的设计框图
SCANNER
OUTPUT
D 25
<25,
>
<31, -------- >
<25,
>
第三章词法分析
12
四、 词法分析的设计形式
（1）设计成一个独立程序，完成词 法分析的任务，结果以文件的形式组织， 做为语法分析的输入
源程序
词法 分析
第三章词法分析
符号表 TOKEN字 错误信息
13
（2）作为语法分析和语义分析的子程序
错误的诊查处理
有穷控制器
单词的词类和属性 6 （词类符号，
第三章词法分析
单词的属性） 4
3.1 词法分析程序的设计
一、词法分析程序的功能
源程序 词法分析器 单词序列
二、 扫描器的任务
1、组织源程序的输入
2、转换成机内表示形式
3、删除注释行、空格及无用符号
4、查填符号表
5、检查词法错误
第三章词法分析
5
if i＞j then i:＝0 else j:=1
语法分析
源 程 序
词法 分析
语义分析和 中间代码生成
中 间 代 码
符号表管理
第三章词法分析
14
五、词法分析程序的设计框图
SCANNER
OUTPUT
sort
字母 数字 / 界符
’
RECOGID RECOGDIG HANDLCOM RECOGDEC RECOGSTR
LOOKUP
第三章词法分析
15
32 词法分析器的手工构造
无符号实数（用d表示数字）:
(a) dd.d dE(+- ) dd 0.1e+14
(b)ddE(+- ) dd
12e-4
Hale Waihona Puke (c) dd.d d3.141592
(d) dd…dd
1000
第三章词法分析
18
标识符：字母开始的字母数字串。
例：C语言的标识符
a
a,d
I
B
TT
其它
-
第三章词法分析
19
例：C语言实常数的文法描述
在识别常数的过程中，要把它转换成机器表
示以作为属性值，记录到常数表中。
第三章词法分析
21
program SCANNER;
Begin initiate符号表,字符串表,行,列计数器;
Open 源文件,TOKEN文件,打印机文件;
Repeat FIRSTCH(CH);
模块0：
if CH!=EOL then call SORT(CH)
扫描器主控
else RDLINE;
until CH=EOF;
把符号表,字符串表做成文件;
close源文件,TOKEN文件;
call OUTPUTR;
第三章词法分析
22
单词分类模块(SORT)输入：
CH内含单词首符；
procedure SORT(CH);
{ case CH of ‘字母’:
8
表3.1 单词词类编码
第三章词法分析
9
对于关键字、界符、运算符来说，它们 的词类编码就可以表示其完整的信息， 故对于这类单词，其单词自身的属性值 通常为空
而对于标识符，词类编码所反映的信息 不够充分，标识符的具体特性还要通过 单词自身的属性进行互相区分。标识符 的单词自身的属性常用其在符号表中的 入口指针来表示
3 . 2 词法分析器的手工构造： 用DFA 能识别
3 . 3词法分析程序自动构造工具LEX简介
第三章词法分析
3
L i n e = 8 0 ; 输入
字母
字字母母
0
1
2
数
字
数字
3数 4
字
=
5
输出
id(25) , ‘Line’ =( 36), num(27), ‘80’ ;(45),
；
第三章词法分析
7
词法分析器的输出：
（词类编码，单词自身的属性值）
词类编码原则: 界符和运算符: 一字一码。
关键字可分成一类，也可以一个关键字分 成一类。 一字一码。
常数可统归一类，也可按类型（整型、实 型、布尔型等），每个类型的常数划分成 一类。 一类型一码。
所有的标识符分为一类。 一类一码。
第三章词法分析