Lex.cpp 和 Lex.hpp 为lex类，程序的主体部分，main.cpp为对lex类的使用 a.out为上述文件生成的可执行文件(mac-os, 其他平台需重新编译，需支持c++11) temp.l为写好的lex文件 执行a.out 会根据temp.l生成out.c

temp.c为一段测试的c源代码 out.c编译后生成可执行文件out, 执行 ./out temp.c 会生成temp.c对应的词法分析结果

前言

前一阵子，编译原理课实验内容是要去做一个词法分析器，实现后，觉得没有把正规表达式和NFA、DFA这些知识用上，所以就产生了想自己去实现一个lex的想法，于是就有了这篇博文。 如果还不知道词法分析器该怎么实现，可以去看c语言词法分析初试(C++实现)。

简介

上图是维基百科对lex的定义。 从中可以明确lex的功能：读进一个代表词法分析器规则的输入字符串流，然后输出以C语言实做的词法分析器源代码。 本质上，本人是在对原lex进行模仿，但使用规则细节什么的与其并不一致，比如原lex用正则表达式来表示词法分析器规则，而本人的自制lex使用的是正规表达式，所以接下来关于原lex的内容不再赘述。

执行流程

1.解析lex文本

1.1文本规则

%{
	c代码区块
%}
%!
	定义区块
%!
%%
	规则1 方法体
%$
	规则2 方法体
%$
	...	
%%

由上可以看到，整个lex文本分为三个区块。

c代码区

用%{ %}包围，里面内容是c代码，这些代码会原样复制进程序生成的词法分析器源代码中，也就是说，我们可以在这个区块里预定义一些c函数、变量等等。

定义区

用%! %!包围，里面内容是一些定义，格式为 a = b。

a表示我们定义一种输入字符，比如所有的字母、数字，或是a-v，3-7等等区间，或是除了字母以外的任何字符。我们可以给这些值的集合起一个名字为a。 b表示一个函数名，该函数接受一个char字符，返回1或者0，表示输入是否匹配。该函数必须自己在c代码区进行实现。 例如：我们定义 digit = isDigit digit表示所有的数字，则我们需要实现这样一个函数：

int isDigit(char ch){
	if(ch >= '0' && ch <= '9')
		return 1;
	return 0;
}

完成上述之后，我们就可以在规则区里以{a}的形式在正规表达式中使用该自定义输入。

规则区

这里可以说是整个lex文件最核心的部分了。 我们需要在这里对所有的词法规则用正规表达式进行描述。 还是举个例子，我们要将c语言的标识符的规则进行描述：

正规表达式  方法体

({letter}|_)({letter}|_|digit)* {printf("<$ID, %s>", LEX_TEXT);}

letter表示所有字母，digit表示所有数字，这两者都属于是我们在定义区所自定义的输入类型。 那么上面正规表达式代表的含义就是所有以字母或者下划线开头并后续字母是字母数字或者下划线的字符串，即是我们认为合法的标识符。 后面{}包含的内容是我们的方法体，即定义我们生成的词法分析器当识别出符合正规式定义的字符串后需要进行的操作，该操作用c语言来进行描述。 LEX_TEXT为我们预设定的保存识别出的串的char数组。 那么上面的规则所定义的就是对标识符进行匹配，并在匹配成功之后将其进行输出。

1.2文本识别细节

这部分做的比较粗略。 1.上述三个区域的界符即%{，%!等必须出现在每行的行首，否则会被忽略。 2.所有出现在三个区域外的文本内容全部忽略 3.当出现文本忽略时会报出警告(文本内容及行号) 4.当出现文本识别错误时会进行报错(文本内容及行号)并程序终止。 5.因为正规式里面原本就有(,),|,*等符号，再加上{}用于标识自定义输入的符号以及空格，这些字符均需要进行转义，我定义的转义标志是%，与c语言的\没有什么区别。用%$表示正规表达式里的空。

根据lex文本内容生成NFA等

这部分我用了一个栈来实现，具体细节可参看之前写的一篇博客正规表达式转NFA(C++)，细节有所差异，但是实现思想是一致的，这里就不再重复描述了。 除了要生成NFA，还要完成两件事。

1. 保存定义区里 自定义输入与对应判断函数名的映射。
2. 保存NFA的终点状态的序号集合，并保存其各自对应的方法体的映射。

根据NFA生成DFA

这里使用的方法是子集法： 每个状态表示为一个数字，这一点在上面已经提过，那么我们用一个vector表示一个状态集合。 再使用一个set和一个queue，set用于对vector进行查重，queue用于遍历，从起始状态的集合开始，将其经每个输入到达的状态加入queue，当然，前提是该状态集合没有在set中出现过。 这里有个重点是关于空的处理，见代码。

//i为当前状态，input为输入，state为存放可到达的状态的集合
void Lex::findBeGo(int i, string input, vector<int>* state)
{
    for(auto x : nfaVet[i])
    {
        int sId = x.toId;
        bool flag = true;
        for(auto iter=state->begin(); iter!=state->end(); iter++)
            if((*iter) == sId)
            {
                flag = false;
                break;
            }

        if(flag && input.compare(x.input) == 0)
        {
            state->push_back(sId);
            findBeGo(sId, "", state);
        }
    }
}

当然，这里也需要保存DFA的终点状态的序号，并保存其各自对应的方法体的映射。

将DFA转换为C代码

如果用自动机的模式写过一次词法分析器，就很明了，DFA只跟自动机的状态里面内容相关。 即：switch(状态){//} ；里面的内容是需要根据DFA动态生成的，其他的都不需要改变。 所以我们一开始就将switch部分上下的代码都确定，然后根据DFA来生成。 对每一个case来说，我们需要输出的内容只有以下几点：

1. 状态id
2. 状态接受的输入，以及该输入转向的状态id
3. 枚举完所有可接受的输入后，如果当前字符与以上输入都不符合，那么根据该状态是否是终止状态来确定是结束并执行方法体还是报错。 例子如下：

目前的问题

1. 没有对正规式的正确性进行判断，想在后面用语法分析来解决
2. 上面的第一步等同于对lex文件进行词法分析，因为其实际上是一种自定义语法，所以需要对其完善报错，好方便使用者
3. 优化

---

temp.l内容注释
%{
这里会让用户去写一些预设在词法分析程序里的代码
和 自定义函数
%}

%!
这里写一些自定义输入的映射
例如
letter = isLetter
isLetter会在上面%{%}区域进行实现，是一个形参为char ch，成功返回值为1否则为0的函数
%!

%%
这里需要去将分析的词法里所有合法的单词用正规式进行表示
如  c语言的标识符
({letter}|_)({letter}|_|{digit})*   {
这里要写的是当解析出该单词之后，要执行的动作
比如 printf("<$IDm, ->\n");
}
%%