【编译原理】词法分析（C/C++源代码+实验报告）

1 实验目的和内容 1.1实验目的

（1）根据 PL/0 语言的文法规范，编写PL/0语言的词法分析程序；或者调研词法分析程序的自动生成工具LEX或FLEX，设计并实现一个能够输出单词序列的词法分析器。

（2）通过设计调试词法分析程序，实现从源程序中分离出各种类型的单词；加深对课堂教学的理解；提高词法分析方法的实践能力。

（3）掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。

（4）掌握词法分析的实现方法。

（5）上机调试编出的词法分析程序。

1.2实验内容

根据PL/0语言的文法规范，编写PL/0语言的词法分析程序。要求：

（1）把词法分析器设计成一个独立一遍的过程。

（2）词法分析器的输出形式采用二元式序列，即：(单词种类, 单词的值)

2 设计思想 2.1单词种类及其正规式

（1）基本字

单词的值单词类型正规式rbeginbeginsymbegincallcallsymcallconstconstsymconstdodosymdoendendsymendififsymifoddoddsymoddprocedureproceduresymprocedurereadreadsymreadthenthensymthenvarvarsymvarwhilewhilesymwhilewritewritesymwrite

（2）标识符

单词的值单词类型正规式r标识符ident(字母)(字母|数字)*

（3）常数

单词的值单词类型正规式r常数number(数字)(数字)*

（4）运算符

单词的值单词类型正规式r+plus+-minus-*times*/slash/=eql=neq=:=becomes:=

（5）界符

单词的值单词类型正规式r(lparen()rparen)，comma，；semicolon；.period. 2.2 根据正规式构造NFA

下面我们根据上述的正规式来构造该文法的NFA，如下图所示，其中状态0为初态，凡带双圈的状态均为终态，状态24是识别不出单词符号的出错情形，其他状态的识别情况如下图中右边的注释所示。

图1 根据正规式构造的NFA

2.3根据NFA构造DFA 2.3.1根据替换规则构造未化简的DFA

替换规则如下图所示。

图2 替换规则

根据替换规则对NFA进行分裂，结果如下图所示。

图3 未化简DFA

2.3.2最小化DFA

一个确定有限自动机M的化简是指，寻找一个状态数比M少的DFA M’，使得L(M)=L(M’)。一个DFA M的状态最小化过程旨在将M的状态集分割成一些不相交的子集，使得任何不同的两子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价的。最后，在每个子集中选一个代表，同时消去其它的等价状态。

最小化后的DFA如下图所示。

图4 最小化DFA

3算法流程

词法分析程序的输入是源程序，输出是一个个单词符号的二元组，它的任务是从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。

首先逐行扫描源程序，然后遍历串的每一个字符，判断字符是不是空格、数学、字母、运算符或者界符，再进行下一步的判断，如果不符合这几种情况，将会归入出错处理。完整算法流程如下图所示。

图5 算法流程图

4源程序

#include 
#include 
using namespace std;

//用于识别是基本字或标识符
void Letter(string str)
{
    //识别基本字
    if(str=="begin")
        cout