关于编译原理：词法分析

词法分析简介和碎碎念

最近正在和 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 的耐心等待和帮助。要感谢的还有 天童アリス 、 棗イロハ 和 小鳥遊ホシノ ，感谢这三位给予我精神上的支持。