极简编译原理1——概述和词法分析（上）

起因

最近在leetcode上看到一道题（65.Valid Numuber），然后有人说这道题毫无价值，全都是edge case的判断。。。拜托，“不要在网上哔哔赖赖”，这道题引申出的知识点明明很有价值，因此自己打算写点关于编译原理的相关内容

题目如下：

概述

顾名思义，编译原理是一门把源程序文本转化成可执行程序的科学。

之所以是极简，是因为不会像大学课堂一样剖析的非常细致严谨，面向的对象是非计算机专业的工程师或者已经忘记编译原理知识的工程师，所以点到为止即可。

一般来说，整个编译原理的过程可以大致分为如下几个过程：（以下内容摘抄自陈火旺《程序设计语言编译原理》）

出错处理顾名思义，即用来处理编译过程中的错误。而表格管理，可以大致理解成“缓存”，比如在扫描到一个单词的时候，并不知道这个单词是常量名还是变量名还是过程名等等，需要到之后的阶段才能确认，这个时候就需要用到表格管理

编译过程中的每个阶段，我们以后都会详细阐述，今天我们来介绍“词法分析”相关的内容。

词法分析

我们知道，源程序本身可以看成是一串长长的文本，而把这些文本分成一个个词的过程就是词法分析。

例如，我们有一句源程序if(a > 1) int b12 = 1;，经过词法分析后，能得到if ( a > 1 ) int b12 = 1 ;这几个字

词法分析器设计

那么我们如何实现一个词法分析器呢？通常，我们在写程序前都需要经过一些设计，词法分析器一样不例外。下面我们引入一个概念——状态转换图

下图展示了状态转换图的样子

• 圆圈表示状态，如图a，共有三个状态
• 箭弧表示状态转化
• 箭弧上的字母表示这个转换接收的字符
• 双圈表示终态，那么相应的就会有初态，在状态图上的表现就为没有射入箭弧的状态
• *表示回退一个字符，即不包括刚刚读入的字符

看个例子，上图b：

一开始的时候，程序状态在0态，这个时候，如果输入了一个字母，那么程序就转换到了1态，紧接着，如果输入了一个字母或者数字，程序就还保持1态，直到输入的不是字母或者数字，那么这个状态转换图终止。

回看上述过程，我们可以清楚地看到，这个状态转换图接收了“一个字母+任意多个字母或数字”，也就是说，这个状态转换图可以识别“以字母为首，后面接上任意多个字母或数字”这样的字符串。

那么，图c的功能就很清楚了，它可以识别一个数字。

状态转换图实现

接下来，我们来看状态图如何转换成代码。在此之前，我们对图b稍作修改，从初态加上一个分支。

代码如下：

#include <iostream>
#include <vector>

using namespace std;

bool isCharacter(char c) {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}

bool isCharOrNum(char c) {
    return isCharacter(c) || (c >= '0' && c <= '9');
}

int main() {
    string src = "6666666 int b12c = 3";
    string result;
    char *ptr = &src[0];
    while (*ptr != '\0') { // 循环读取输入的字符
        if (isCharacter(*ptr)) { // 如果输入的字符是字母，转到状态1
            result += *ptr;
            ptr++;
            while (isCharOrNum(*ptr)) {
                // 如果输入的是字母或数组，回到状态2
                result += *ptr;
                ptr++;
            }
            if (!isCharacter(*ptr) && !isCharOrNum(*ptr)) {
                // 如果输入的是其他，转到状态3，输出扫描出的字符
                cout << result << endl;
                result = "";
                ptr++;
            }
        } else { // 如果输入的字符是其他，转到状态3
            ptr++;
        }
    }
    return 0;
}

从上述代码中，不难看出：

1. 对于不含回路的分支箭弧，用if或者switch-case语句
2. 对于回路箭弧，用循环语句

以上就是把一个状态转换图变成代码的最基本方法

假设我们自己设计了一套语言，有这些单词符号

我们可以轻松得到一个状态转换图，用来识别这个语言所有的单词符号：

现在回到开篇我们提到的leetcode问题

有了状态转换图的帮助，我们就可以轻松解决此题。现在给出状态转换图：

这是从网上找来的图，因为我自己懒得在电脑上画了。大家也可以自己一步步画出状态转换图，大体思路是：

首先，我们通过观察题目可以看出，本题状态转换图应该可以接受以下五种字：

1. 空格(space)
2. +/-
3. 数字(digit)
4. 点(.)
5. e

接下来，从初态开始，当接收到一个空格时，还是回到初态；接收到数字时，到1态；接收到点时，到2态；接收到正负号时，到3态；除了空格、数字、点、正负号之外，不接受其他字符。

然后，再仿照初态时的做法，再对1、2、3态可以接收的字符做筛选过滤，以此重复，便可以得到一个状态转换图，但是这样得到的状态转换图和上述给出的图一定不是一样的，这就涉及到状态转换图简化的方法，但是这个方法不在本文中给出，大家有兴趣可以自己去看。同时，这也体现了“同一个问题，可以有不同状态转换图”的特性。

有了状态转换图之后，我们便可以利用上文给出的方法，该换成if/switch-case的地方换成if/switch-case，该换成循环的地方换成循环，虽然可以预见代码可能复杂一些，但是总归是可以觉得问题的

那么有没有什么简单的方法，能让代码编写简单一些呢？

通用方法

我们直接给出方法，该方法需要利用一个二维数组

	空格	+/-	数字	.	e
0	0	3	1	2	-1
1	8	-1	1	4	5
2	-1	-1	4	-1	-1
3	-1	-1	1	2	-1
4	8	-1	4	-1	5
5	-1	6	7	-1	-1
6	-1	-1	7	-1	-1
7	8	-1	7	-1	-1
8	8	-1	-1	-1	-1

首先来解释一下这张二维表格，这张二维表格是由状态图转化而来。第一列是状态编号，第一行是可以接收的字符，表格内容是某个状态接收到了字符之后可以到达的状态。例如，0态接收一个空格还是0态，0态接收一个符号变为1态，0态不能接收e；2态接收一个数字到达4态，2态不接受空格等。我们只需要看着状态图就能很轻松的写出这张表。

知道了这张表的意思，我们来想一下如何使用这张表。这张表用一句话总结就是：一个状态接收一个字符到了另一个状态。那么可想而知，我们就可以循环重复这个动作，从新得到的状态接收新的字符到更新的状态，直到结果为-1或者字符串循环完毕。结果为-1表示当前状态不接受当前字符，也就意味着字符串不符合要求；如果是字符串循环完毕，那我们看结果是否正好落在终态，如果正好落在终态，说明符合要求，不在终态则不符合要求。

有个大体的思想，我们就可以很轻松的转化为代码：

class Solution {
public:
    int checkchar(char c) {
        if (c == ' ') {
            return 0;
        } else if (c == '+' | c == '-') {
            return 1;
        } else if (c >= 48 && c <= 57) {
            return 2;
        } else if (c == '.') {
            return 3;
        } else if (c == 'e') {
            return 4;
        } else {
            return 5;
        }
    }
    
    bool isNumber(string s) {
        if (s.length() == 0) return false;
        
        int8_t machine[9][5] = {{ 0,  3,  1,  2, -1},
                                { 8, -1,  1,  4,  5},
                                {-1, -1,  4, -1, -1},
                                {-1, -1,  1,  2, -1},
                                { 8, -1,  4, -1,  5},
                                {-1,  6,  7, -1, -1},
                                {-1, -1,  7, -1, -1},
                                { 8, -1,  7, -1, -1},
                                { 8, -1, -1, -1, -1}};

        int currentState = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s[i];
            int cidentifier = checkchar(c);
            if (cidentifier == 5) {
                return false;
            }

            int nextState = machine[currentState][cidentifier];
            if (nextState == -1) return false;
            currentState = nextState;
        }

        if (currentState == 1 || currentState == 4 || currentState == 7 || currentState == 8) {
            return true;
        }

        return false;
    }
};

以上代码是我在leetcode的答案，所以没有main入口。

这就是一个通用的简单方法，几乎所有的确定有限状态转换图都可以通过一个二维转换表来生成代码。

这一次的文章就到这里，下一篇我们会说一说词法分析中其他的概念和方法，以及看一看正则表达式和词法分析的关系。