《编译原理》课程实验 实验1
实验1 词法分析
1．实验说明
实验题目：词法分析器的设计与实现
实验目的：加深对词法分析基本理论的理解，锻炼实现词法分析器程序的实践能力。 实验过程：
（1）按照给定的表达式的词法要求，构造分DFA； （2）整合各分DFA，构造总DFA； （3）设计词法分析器算法； （4）根据DFA实现单词识别程序； （5）保存词法分析结果到文件。 输入：
（1） 输入为数学表达式，其中可能含有空格； （2） 运算符包括+，-，*，/，（，）。 （3） 运算数包括自然数和变量；
（4） 变量以下划线或字母开头，其后可以跟字母、下划线或数字。 输出：
输出到文本文件。每个单词输出为二元组（单词类别，单词值）。单词类别编码见下表： 编码 0 1 2
例1：表达式xy-(x-100)/2的输出
2,xy 0,- 0,( 2,x 0,- 1,100 0,) 0,/ 1,2
第-1-页
类别说明 算符
常量（自然数） 变量
《编译原理》课程实验 实验1
例2：表达式2x * (_x2 – y)的输出
1,2 2,x 0,* 0,( 2,_x2 0,- 2,y 0,)
注意： 2x识别为两个单词2和x，虽然2x在语法上不合法（中间需要一个运算符），但在词法分析时不
能发现这个错误。
例3：表达式x y * 012
注意： 该表达式x和y之间有一个空格，该词法分析程序的预处理程序简单的将空格全部去掉，因此与
表达式xy*012的输出相同。 2,xy 0,* 1,012
2．分DFA 2.1 自然数 2.2 标识符 2.3 算符
3．合DFA
说明：
（1） 状态0为初态。
（2） 状态4为程序正常出口，说明识别出一个单词，单词类别由前一个状态决定。 （3） 状态5为出错状态。
（4） 为进一步确定下一步要做什么，需要向前“假读”一个单词。状态2、3的假读是必须的，状态1是为
了程序上的统一进行假读。
4．数据结构说明 4.1 单词结点
单词序列采用链表存储，每个结点表示一个单词，用如下结构表示：
第-2-页
《编译原理》课程实验 实验1
struct WORDNODE {
unsigned short byType; // 单词类别 char Value[MAX_DATA_LEN]; // 值 WORDNODE *pNext; // 下一结点 };
单词链表结构在WordAnalysis（）函数中创建，并由此函数返回头结点指针；在main（）函数中销毁。 头结点只记录头指针，而不记录数据（单词类别和值），从第二个结点开始是第一个单词。
4.2 常量（宏定义）
#define MAX_DATA_LEN 256 // 数据缓冲区长度
数据缓冲区为一个字符数组，在main( )函数中声明并从键盘输入。 // 单词类别
#define WT_OPERATOR 0 // 操作符 #define WT_UINT 1 // 非负整数 #define WT_VARIABLE 2 // 变量
5．流程
5.1 主流程（main函数）
预处理过程只是简单的将所有空格删除。
5.2 词法分析（WordAnalysis函数）
该函数输入为存放表达式的字符数组c，输出为识别的单词序列。如果出错，则返回NULL。 该函数首先创建一个单词链表，用于存放单词。单词结点结构参考3.1。
识别过程如下面代码所示。该函数从字符数组c的第0个位置开始扫描字符串，单词开始位置为nCur。调用函数IdentifyOneWord后，nCur修改为下一个单词的开始位置（该变量为引用调用）。该函数的说明参考第5部分。
for (int nCur = 0; c[nCur] != '\\0'; ) { // 识别一个单词
pNode = IdentifyOneWord(c, nCur, pTail); if (pNode == NULL) // 出错 {
Clear(pHeader); return NULL; }
// 识别下一个单词 pTail = pNode; }
第-3-页
《编译原理》课程实验 实验1
如果IdentifyOneWord（）返回NULL，说明出错，则清空链表并返回NULL。如果返回值不是NULL，说明识别出一个单词，则使尾指针指向新创建的结点（即新识别出的单词）。
6．需要完成的内容 6.1 IdentifyOneWord函数
该函数用于识别一个单词，原型为：
WORDNODE* IdentifyOneWord(char c[ ], int &nCur, WORDNODE *pTail)
输入c为存放数学表达式的字符数组。nCur为扫描器起始指针，也就是当前要识别的单词的第一个符号。nCur不断递增（向右扫描），直道扫描完一个单词。pTail为单词链表的尾指针。
如果成功识别出一个单词，则新建这个单词结点，并将pTail的pNext指针指向这个结点，然后返回这个结点指针。如果不能识别出一个单词，则清空链表，并返回NULL。 填写这个函数的内容时要注意以下几点：
（1） 本函数开始时，当前符号为c[nCur]，当前状态为初态0。
（2） nCur为扫描器当前指针，它是引用类型，同时用作输入参数和返回值。在识别出一个单词后，由于
假读的原因，nCur实际指向了下一个单词的开始位置，而识别出的单词的结束位置为nCur-1。 （3） 识别出一个单词后，单词结束位置为nCur-1，而开始位置因为扫描器指针nCur的移动已经不可知。
因此要想知道识别出的单词开始位置，此函数开始时应该声明一个变量记录下nCur的初始值。 （4） 识别出单词后当前状态总为4（参考第2部分），从上一个状态才能判断单词的类别。因此应有一
个变量记录上一个状态。
（5） 一个单词的初始位置和结束位置已经确定，则其值已确定；识别终态的前一个状态已知，则单词类
别确定。这时就可以创建单词结点了。
（6） 在该函数填写过程中，可能会使用到一些已经写好的函数，参考第6部分。
6.2 根据上一状态确定单词类别
unsigned short GetWordType(int nStatus)
入口参数nStatus为终态的前一个状态，返回值为单词类别。
6.3 创建单词结点
WORDNODE* AddNode(char c[ ], int nBegin, int nEnd, unsigned short byType, WORDNODE *pTail) 入口参数：c 为存放数学表达式的字符数组。 nBegin 为识别出的单词在c中的开始位置。 nEnd为识别出的单词在c中的结束位置。 byType 为单词类别 pTail 单词链表尾指针。
函数功能：根据c、nBegin、nEnd、byType的信息创建单词结点，然后将pTail的pNext指针指向新建的结点，并返回新建结点指针。
第-4-页
《编译原理》课程实验 实验1
6.4 清空单词链表
void Clear(WORDNODE *pHeader) 入口参数pHeader为单词链表的头指针。
6.5 字符类别判定函数
这部分函数包含在Chars.h文件中。 bool IsEnglishCharOr_(char c)
判断字符c是否为英文字母或下划线，若是返回true，否则返回false。 bool IsNumChar(char c)
判断字符c是否为0~9的数字，若是返回true，否则返回false。 bool IsOperator(char c)
判断字符c是否为运算符（+|-|*|/|(|)），若是返回true，否则返回false。
第-5-页