基于C语言编译器的词法分析浅析

摘要：编译器是高级语言执行前必须使用的一个环节，它的作用是将自然语言转换成机器语言，而词法分析又是编译器整个工作的第一步——词素解析，笔者从词法分析的任务、基本词素、词法分析工具和DFA几个方面对词法分析进行浅析。

关键词：词法分析；编译器；有穷自动机（DFA）；词素

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）24-5450-05

计算机问世以后，就彰显了它神奇的力量就是为我们解决各种复杂的问题，事实上它的神奇都是我们人类赋予计算机。当我们面临的一个问题，便想办法告诉计算机什么问题，怎么解决，结果是什么。告诉计算机的过程就是我们选择程序语言的编程的操作。最早人们使用机器语言，由于专业性太强，被少数人员所掌握，慢慢过渡到高级语言，但高级语言又不能直接被计算机识别和执行，必须经过等价的转换，变成计算机能识别并执行的机器代码。完成这种等价转换操作的工具，就是编译程序。

1 编译程序的结构

编译程序完成高级语言到机器语言的转换，最终得到计算机可执行的01代码，但这个复杂的过程可被分成五个相对独立的阶段——词法分析阶段、语法分析阶段、语义分析及中间代码生成阶段、优化代码阶段和OBJ代码生成阶段，每个阶段承担专门的工作，前一个阶段的产物正好是下一个阶段处理的数据。

1.1 词法分析阶段

词法分析阶段就是对源代码中字符串进行扫描和分解，依据高级语言的编程规则将字符串（ String）转化成词素 （Token）。例如对于C-语句：

词法分析的结果用二元式表示是：

构词的规则就是词法，例如标识符（ID）可定义为以字母开头，后面跟零个或任意个字母或数字的序列。词法分析程序就根据词法构造有限自动机来识别每一个词素，词素的编码[1]，将产生的单词交给语法分析程序。

1.2 语法分析阶段

语法分析阶段的是根据词素进行语法分析，识别出各类语法单位，最终判断输入串在语法上是否为合法的程序，例如对上一个的输入串进行语法分析可得到如图2的语法树。

1.3 语义分析与中间代码生成阶段

语义分析阶段是根据前一阶段产生的分析树，按语义规则对语法分析器规约的语法单位进行语义判断并把它们翻译成为一定形式的中间代码，其形式有四元式或三元式等中间语言。有了中间代码就能很容易地转换成OBJ代码。前面的语法树翻译的中间代码用四元式序列表示为：

1.4 代码优化阶段

代码优化阶段的工作是把中间代码进行优化处理，以便获取更为高效的OBJ产物。

1.5 目标代码生成阶段

目标代码生成是编译过程最后一个阶段，它把中间代码翻译成为OBJ代码。如对于前面生成的中间代码，助记符代码表示为：

助记符代码经过汇编器（Assembler）和连接器（Linker）执行，就可以得到计算机上运行的01代码。

2 词法分析阶段

2.1 词法分析的任务

词法分析是编译过程的第一个阶段，是编译的基础。它就是将源代码中的字符串、组成符号按照从左到右的顺序一个一个字符读入进行识别，即对构成源程序的字符串进行扫描然后根据构词规则识别单词，过滤空白、换行、制表符、注解等，将词素添加到符号表中，输出词法单元序列。词法分析是语法分析的基础，通常它与语法分析处于同一趟中完成（图3）。

2.2 词法分析的词素

C语言的程序主要有五种词素：关键词、标识符、常数、运算符和界符。对于关键词、运算符和界符的形式和个数是确定的在词法分析时可以进行独立枚举并确定词素自身的的编码。而对于标识符和常数的使用个数是不确定的。完成词法分析就是将源代码中的五种词素分析出来。用下图表示五种词素之一的关系运算符（图4）。

2.3 词法分析的工具

2.3.1 状态转换图

状态转换图是词法分析器设计的好工具。状态转换图是一张有限方向图。在状态转换图中，有一个初态，至少一个终态。

其中0为初态，2为终态（图5）。这个转换图识别（接受）标识符的过程是：从初态0开始，若在状态0之下输入字符是一个字母，则读进它，并转入状态1。在状态1之下，若下一个输入字符为字母或数字，则读进它，并重新进入状态1。一直重复这个过程直到状态1发现输入字符不再是字母或数字时（这个字符也已被读进）就进入状态2。状态2是终态，它意味着到此已识别出一个标识符，识别过程宣告终止。终态结上打个星号意味着多读进了一个不属于标识符部分的字符，应把它退还给输入口中（超前扫描技术）。

2.3.2 正规表达式与正规集

正规表达式是说明单词的一种重要的表示法，是定义正规集的工具。词法分析中，正规表达式用来描述单词可能具有的形式。

如标识符正规式：l（l|d）*

3 词法分析与有穷自动机

有穷自动机（Finite Automata）是具有离散输入与输出系统的一种抽象数学模型，它能准确地识别正规集，引入有穷自动机这个技术，为词法分析程序的自动构造寻找有效的方法和工具。

有穷自动机有确定的有穷自动机（Deterministic Finite Automata）和不确定的有穷自动机（Nondeterministic Finite Automata），确定的有穷自动机是不确定的有穷自动机的特例。它们都能准确的识别正规集。

3.1 确定的有穷自动机（DFA）

一个确定的有穷自动机（DFA）M是一个五元组：M=（Q，Σ，f，S，Z）其中：

1）Q是一个有穷状态集，它的每个元素称为一个状态；

2）Σ是一个有穷输入字母表， 它的每个元素称为一个输入字符，所以也称Σ为输入符号字母表。

3）f是一个从Q×ΣQ上的单指映射， f（qi，a）=qj （qi， qj∈Q，a∈Σ）表示当前状态为qi，输入字符为a时，自动机将转换到下一个状态qj，我们把k qj称作qi的一个后继状态；

4）S∈Q是惟一的一个初态；

5）Z ? Q，是一个终态集。

一个DFA也可以用一个状态图表示。 假定DFA M有k个状态，n个输入字符，那么这个状态图含有k个状态节点，每个状态节点最多有n条箭弧射出和别的状态节点相连接，每个箭弧用Σ中的一个不同的输入符号作标记。整个状态图含有惟一一个初态节点和若干个终态节点。

对于Σ*中的任何符号串β，若存在一条从初态结到某一终态结的通路， 且这条路上所有弧的标记连接成的符号串等于β，则称β为DFA M所识别，若M的初态结同时又是终态结，则ε可为M所识别。DFA M所能接受的符号串的全体记为L（M）[2]。

3.2 不确定的有穷自动机（NFA）

不确定的有穷自动机与确定的有穷自动机的区别在于NFA M对于∑*中的任何一个字符串α，若存在一条从某一初态结到某一终态结的通路，且这条通路上所有弧的标记依序连接成的字符串等于α， 则称α可为NFA M所识别。若M的某些结既是初态结又是终态结， 或者存在一条从某个初态结到某个终态结的ε通路，那么空字可为M所接受。

3.3 NFA转换DFA的过程

NFA都会有一个DFA相对应，使得它们能接受相同的语言。主要采用子集法完成相应的转换。其中涉及ε-闭包的概念，即（1）若s∈I，则s∈ε-CLOSURE（I）；（2） 若s∈I，那么从s出发经过任意条ε弧而能到达的任何状态s’，都属于ε-CLOSURE（I）。

输入：一个NFA

输出：一个识别相同语言的DFA

方法：利用构造ε-闭包的方法将NFA转换为DFA，NFA N={Q，∑，f，S，Z}转换等价的DFA M={Q’，∑，f’，S’，Z’}首先将从状态S出发经过任意条ε弧所能到达的状态所组成的集合作为M的新状态，重复直到不再出现新的状态出现为止。

构造标识符的NFA并转换成DFA，描述标识符的正规式R=l（l|d）*

1）按照正规式到NFA的拓广转换规则可得到（图6）

2）NFA N转换DFA M的等价状态表（表1）

3.4 确定有穷自动机的化简

一个DFA产生后，并不一定是最简的，所谓简化就是寻找一个状态数比 M少的DFA M’，使得L（M）=了（M’）。主要方法是通过合并等价状态从而消除多余状态最终转换成一个最少状态的与之等价的DFA。

所谓有穷自动机的等价状态是如果从状态s出发能读到某个字符串w而停止与终态，同样，从状态t也能读出同样的字符串w而终于终态。则称状态s和状态t是等价的。对于给定的有穷自动机，如果它含有多余状态，可以非常简单地将多余状态消除，而得到与它等价的有穷自动机。

在有穷自动机中，两个状态s和t等价的条件是：

1）一致性条件——状态s和t必须同时为可接受状态或不可接受状态。

2）传播性条件——从状态s出发读入某个字符a和从状态t出发读入某个字符a，到达的状态等价[3]。按照简化条件得到（图8）

图8 标识符的最简DFA

比起原来的有穷自动机，化简了的有穷自动机具有较少的状态，因而在计算机上实现起来将简洁些。由简化的DFA进行C语言编码[3]：

4 小结

上文从词法分析的任务、工具和采用超前搜索技术的方法识别出一个单词后， 根据单词的结构，将其归类，如关键词、标识符、算符等，相关特征信息存放信息的二元式中。利用词法分析工具，采用进超前搜索的方法，借助某种程序设计语言，就可以构造出词法分析的算法，即词法分析器。

参考文献：

[1] 陈火旺， 刘春林， 谭庆平. 程序设计语言编译原理[M].北京：国防工业出版社， 2000：5-6.

[2] 胡伦骏，徐兰芳，刘建农.编译原理[M].北京：电子工业出版社， 2003：34-52.

[3] 胡元义，邓亚玲，谈妹辰. 编译原理教程[M].西安：西安电子科技大学出版社，2003：101-103.