关于编译原理：词法分析

词法分析简介和碎碎念

最近正在和Tastror做编译器，然而她超级厉害两个晚上就把语法分析写完了，我写的是词法分析。

编译器的前端分析过程大致包括这几件事：词法分析，语法分析，语义分析。

词法分析，是将代码中的每一个token提取出来的过程。给我个人的感觉类似于分类。即，判断语句中的每个标记属于什么成分。例如，对于代码：

int a=300;

"int"是关键字(Keyword)，类型说明符；"a"是一个变量名，属于标识符(ID，Identifier)，而"="是一个运算符(Operator)，";"是终止标志，可以算作一个标点(Punctuation)。词法分析器扫描一遍源代码，按照类似这样的分类生成一个列表提供给语法分析器。同时还可以记录行列的值从而在分析出不合法token的时候停下并报出详细错误位置。而其中token间以某些符号（具体指标点或运算符）或者空格、回车、换行为界。

词法分析的简单实现

词法分析的核心是状态机。一种较为简单的方法是，列出不同首字符下的状态，然后对各个状态进行细分，每一种细分再用状态机实现。

以C语言为例。

1、如果读入token的第一个字符是一个字母或者下划线，则当前的token可能是一个关键字（当然关键字不含下划线），也可能是一个ID。读取整个token，符合正则表达式

[a-zA-Z|_][a-zA-Z0-9|_]*

的token是一个合理的ID或关键字，然后去关键字列表查找是否是关键字确定具体情况。

当然也可以在一开始就把下划线开头和字母开头分开，这样效率会高一些。但是直接在1中所述的状态机里区分开关键字和ID会使得状态机变得更复杂，比如识别"while"或者"return"这样的关键字的时候，会有比较长的识别过程，可能还不如直接在关键词列表里查一遍（其实是我懒o(TヘTo)）。

2、如果读入的token第一个字符是一个数字，那么这个token只可能是数字。C语言中的整数包括十进制、八进制、十六进制，小数包括普通表示和科学计数法。这些数字满足的正则表达式如下：

十进制(Dec)：

[0-9]+

八进制(Oct)：

0[0-7]+

十六进制(Hex)：

0[x|X][0-9a-fA-F]+

普通小数：

[0-9]+\.[0-9]+

科学计数法：

[0-9]+\.[0-9]+[e|E][+|-]?[0-9]+

使用与这些正则表达式对应的状态机去检测是哪一种数字。这些规则是有优先级的，先检查带字母和符号的格式，比如Hex和科学计数法、普通小数。在此之后再检查普通数字。

主要的情况就这些了，其他的开头是一些符号，可能会遇到一些困难，比如两个字符的运算符"&&"、"||"等等，这类符号的处理建议直接使用状态机处理效率更高。

有关token的划分的注意事项

匹配token的时候需要遵循最长匹配的原则。前面提到了，token之间以运算符或者空格等分割，但是一些代码的写法比如

float c=3+e;

和

float c=3.0e+3;

这两者都是合法的，但第二个语句不能直接按照"+"简单的将两边分割为两个token。这种情况下应该先按照数字规则匹配，匹配剩下的再继续分割为新的token。

一些吐槽和致谢

flex真难用TAT，玩了好久还是不会玩，最后全部自己写了。词法分析写了好久我好菜呜呜呜~

另外，谢谢 Tastror 的耐心等待和帮助。要感谢的还有 天童アリス 、 棗イロハ 和 小鳥遊ホシノ ，感谢这三位给予我精神上的支持。

参考资料：现代编译原理——第1章：词法分析 - jacksplwxy - 博客园 (cnblogs.com)