目录

简介     

词法分析

正则表达式

有穷状态自动机

从正则表达式到有穷自动机的转换

单词识别

---

简介     

        主要介绍编译系统设计过程中涉及的原理与技术，主要分为前端设计和后端设计两 个模块。前端部分包括词法分析器、语法分析器的构建和语义分析过程的设计，后端部分包 括汇编生成目标文件以及链接生成可执行文件。

词法分析

         词法分析是编译器的首个阶段，它从左至右逐个读取输入源程序中的字符，并识别出单 个词素。词素的识别过程是字符串匹配的一种特殊情况，其中用到的基本原理最主要是正则 表达式（RegularExpression，RE）和有穷自动机（FiniteAutomata，FA）

正则表达式

正则表达式[26-28]是对字符串（包括普通字符和特殊字符）操作的一种符号表示法，其构 造方法和创建数学表达式相似，可作为模板用来匹配、过滤特定的字符串。从编程语言角度 上看，正则表达式的基本语法结构与过程式高级编程语言非常相似，主要有选择、连接和重 复（又称闭包）这三种基本操作。在一般的形式语言中，主要使用以下元字符来进行正则表 达式的构造：

（1）选择匹配。用‘|’来表示选择匹配，如x|y表示匹配x或y中的一个。

（2）重复限定。用来限定某个字符或子表达式出现的次数，最常用的有*、+、？、｛n｝等， 其中，‘*’号表示任意次匹配前面的字符或子表达式，‘+’号表示匹配前面的字符或子表 达式一次或多次，‘？’号表示匹配前面的字符或子表达式一次或零次，｛n｝表示匹配确定 的n次。如正则表达式a.*b可以匹配以a开头且以b为结尾的任意长字符串，即字符串acb、 azcdb 等均可匹配。

（3）范围限定。用‘[’和‘]’来限定匹配的字符范围，如[a-z]表示匹配字符‘a’到字符‘z’ 之间任意的小写字母。

（4）通配符。用‘.’来匹配除‘\n’与‘\r’之外的任意单个字符。

有穷状态自动机

有穷自动机描述的是一种数学模型，表示有限个状态在转移函数和有限输入条件下的状 态转移情况，被广泛的应用在各种各样的领域中，如设计数字电路的软件、词法分析的编译 器及通信协议中验证有穷状态等。有穷状态自动机又分为确定性有穷自动机（Deterministic FiniteAutomata，DFA）和非确定性有穷自动机（NondeterministicFiniteAutomata，NFA）。

DFA的下一状态由当前状态和当前输入字符唯一确定，自动机在读取输入字符后可转入到一 个确定状态，因此，称为确定性有穷状态机。而NFA在一个输入下存在多个下一状态，读取 输入字符后，自动机可从当前状态转移到其中任一状态，因此，称为非确定性有穷状态机。 DFA是一个带权有向图，图的节点表示状态，图的边表示自动机的状态变化情况，每条 边的权值表示从一个状态转换到另一个状态所需要的条件。DFA的形式化定义是一个五元 组

从正则表达式到有穷自动机的转换

虽然正则表达式能够进行字符串匹配，但若直接用正则表达式来解析字符串，不仅工作 量大，而且速度缓慢。因此，在进行词法分析器扫描程序的设计时，需要设计一种方法， 将正则表达式转化为计算机程序的模型，其中最常用的是Thompson构造法，它先将正 则表达式转换成NFA，再通过子集构造法从NFA构造出DFA，最终使用DFA进行单词识别。 如图2.1所示，构造一个词法分析器的扫描程序主要包含四步：首先根据C语言的特性 定义词法规则，然后采用正则表达式描述，再将正则表达式翻译成DFA，分别建立一个状态 转换图，构造词法分析器，完成最终的扫描程序。

单词识别

词法分析器的任务是将源程序字符流进行分割，将其分解为多个单词，每个单词都是一 个字符序列，表示源程序的相关信息。典型的单词主要有以下五种：

（1）关键字：如for和if等，它们是定长字符串，是程序语言中具有特殊含义的标识符。

（2）标识符：不定长字符串，由用户自行定义，根据C语言语法规则，C语言程序中的标识 符都是由字母、数字和下划线组成，且只能由字母和下划线开头。

（3）常量：数字型常量、字符型常量等。

（4）运算符：如+、−、×、÷等。

（5）界符：如{}、[]、()等。 在实际词法分析器的设计中，通常要求扫描程序向前搜索一个字符，这样能够保证在符 合词法定义的情况下，词法分析器识别的单词长度尽可能最大。也就是说，在满足C语言词 法定义的情况下，扫描器会一直向前读取字符，直到当前读入字符无法满足词法定义，即停 止扫描，保存识别的单词。