发布时间 : 星期三 文章TINY-C编译器的设计与实现-词法分析器的设计与实现更新完毕开始阅读3fa538efe2bd960591c6770e
源程序 扫描字符串 调用 缓冲区中是否 取单词 还有字符 返回 N 扫描一个字符 结束 .
输出 图2-3第二层数据流程图
8
三 概要设计
3.1概要设计分析
3.1.1 目的
概要设计可以站在全局高度上，花较少成本，从较抽象的层次上分析对比多种可能的系统实现方案和软件结构，从中选出最佳方案和最合理的软件结构，从而用较低成本开发出较高质量的软件系统。
词法分析是编译系统中最基本的功能。要对一种语言进行编译,就必须能够识别这种语言的基本符号。
设计实现的词法分析器作为一个独立的子过程，当语法分析器需要一个单词符号时，就调用这个子程序。每一次调用，词法分析器就从输入的TINY源程序中识别一个单词符号，把它交给语法分析器。词法分析是编译的基础。
为了便于演示词法分析的结果，我们在此基础上用delphi来写图形用户界面，用于显示对TINY源程序进行词法分析的结果
3.1.2 定义
词法分析：扫描程序执行词法分析（Lexical analysis）：它将字符序列收集到
称作记号（t o k e n）的有意义单元中，记号同自然语言。采用DFA进行分析。
DFA：：下一个状态由当前状态和当前输入字符唯一给出的有穷自动机。（有穷自动机是描述特定类型算法的数学方法。有穷自动机可用作描述在输入串中识别模式的过程，因此也能用作构造扫描程序。）
3.1.3 参考资料
[1]Kenneth C.Louden . Compiler Construction Principles and Practice(编
译原理及实践)[M] . 机械工业出版社 . 2000-01-11
[2] 陈火旺，刘春林 .程序设计语言-编译原理（第3版）[M] . 国防工业出版社 .2000-01-12
[3]严蔚敏，吴伟民 .数据结构C语言版[M] . 清华大学出版社 .1997-10-25
[4]潘锦平,施小姚,姚天昉 . 软件系统开发技术[M] .西安电子科技大学出版社.2004-1
3.2 任务概述
3.2.1 目标
设计一个独立的词法分析器，能单独进行词法分析，同时能把词法分析的结果提供给语法分析程序。词法分析程序除了识别出单词及其属性外，还要完成在语
9
法分析前要做的工作。
3.2.2 需求概述
编译器的扫描或词法分析（ lexical analysis）阶段可将源程序读作字符文件并将其分为若干个记号
3.3 总体设计
3.3.1 词法分析的目标和作用 词法分析的目标：
编译器的扫描或词法分析（ lexical analysis）阶段可将源程序读作字
符文件并将其分为若干个记号。因此，词法器又称为扫描器。记号与自然语言中的单词类似：每一个记号都是表示源程序中信息单元的字符序列。典型的有：关键字（ k e y w o r d），例如i f和w h i l e，它们是字母的固定串；标识符（ i d e n t i f i e r）是由用户定义的串，它们通常由字母和数字组成并由一个字母开头；特殊符号（special symbol）如算术符号+和*、一些多字符符号，如> = 和< >。在各种情况中，记号都表示由扫描程序从剩余的输入字符的开头识别或匹配的某种字符格式。
将源程序中的空格、回车、换行等编辑符号排除，从而要构造一个预处
理程序。进一步进行单词符号的识别，常用超前搜索的方法来完成。词法分析器的另一种方法是使用状态转换图。状态转换图是一种有限方向图。该图中只包含有限个状态，结点代表状态，用圆圈表示，状态之间用箭弧连结，箭弧上的标记代表在射出结点状态下可能出现的输入字符或字符类。通常，一个状态图可有多个开始状态，也可有不止一个终止状态。 3.3.2词法分析的数学基础和算法： 正规表达式与有限自动机（DFA） （1）正规表达式与正规集
设有字母表Σ，Σ上的正规表达式及其值 --下规集的递归定义为：
10
ε和Φ都是Σ上的正规表达式，它们所表示的正规集分别为{ε} 和Φ； 任何a∈Σ，a是Σ上的一个正规工，它所表示的正规集为{a}；
假定U和V都是Σ上的正规式，它们所表示的正规集分别记为L（U）和L（V），那么，（U|V）、（U·V）和（U）*也都是正规式，它们所表示的正规集分别为L（U）∪L（V）、L（U）·L（V）（连接积）和（L（U）*（闭包）。 （2）确定有限自动机（DFA） 一个确定有限自动机M是一个五元式 M=（S,Σ,δ,s0,F） 其中：
S是一个有限集，它的每个元素称为一个状态
Σ是一个有穷字母表，它的每个元素称为一个输入字符
δ是一个从S×∑至S的单值部分映射。δ(s,a)=s'意味着：当现行状态为s、输入字符为a时，将转换到下一状态s'。称s'为s的一个后继状态。 F≌S是一个终态集（可为空）。 （3）非确定有限自动机（NFA） 一个非确定有限自动机M是一个五元式 M=（S,Σ,δ,s0,F） 其中：
S是一个有限集，它的每个元素称为一个状态
Σ是一个有穷字母表，它的每个元素称为一个输入字符 δ是一个从S×∑*到S的子集映照，即 δ：S×∑*→2S
F≌S是一个终态集（可为空）。 TINY语言记号的正则表达式 数的正则表达式：
nat = [0-9]+
11