4.3纯手工打造词法分析器

title

date

comments

categories

tags

permalink

description

纯手工打造词法分析器

2020/4/14

true

编译原理

编译原理

词法分析

4.3

词法分析

上一讲，讲到词法分析的工作是将一个长长的字符串识别出一个个的单词，这一个个单词就是 Token。而且词法分析的工作是一边读取一边识别字符串的，不是把字符串都读到内存再识别。你在听一位朋友讲话的时候，其实也是同样的过程，一边听，一边提取信息。

那么问题来了，字符串是一连串的字符形成的，怎么把它断开成一个个的 Token 呢？分割的依据是什么呢？本节课将会通过讲解正则表达式（Regular Expression）和有限自动机的知识带你解决这个问题。

其实，我们手工打造词法分析器的过程，就是写出正则表达式，画出有限自动机的图形，然后根据图形直观地写出解析代码的过程。而我今天带你写的词法分析器，能够分析以下 3 个程序语句：

• age >= 45
• int age = 40
• 2+3*5

它们分别是关系表达式、变量声明和初始化语句，以及算术表达式。接下来，我们先来解析一下“age >= 45”这个关系表达式，这样你就能理解有限自动机的概念，知道它是做词法解析的核心机制了。

解析 age >= 45

我们来描述一下标识符、比较操作符和数字字面量这三种 Token 的词法规则。

• 标识符：第一个字符必须是字母，后面的字符可以是字母或数字。
• 比较操作符：> 和 >=（其他比较操作符暂时忽略）。
• 数字字面量：全部由数字构成（像带小数点的浮点数，暂时不管它）。

我们就是依据这样的规则，来构造有限自动机的。这样，词法分析程序在遇到 age、>= 和 45 时，会分别识别成标识符、比较操作符和数字字面量。之前的图只是一个简化的示意图，一个严格意义上的有限自动机是下面这种画法：

解释一下上图的 5 种状态。

1. 初始状态：刚开始启动词法分析的时候，程序所处的状态。
2. 标识符状态：在初始状态时，当第一个字符是字母的时候，迁移到状态 2。当后续字符是字母和数字时，保留在状态 2。如果不是，就离开状态 2，写下该 Token，回到初始状态。
3. 大于操作符（GT）：在初始状态时，当第一个字符是 > 时，进入这个状态。它是比较操作符的一种情况。4. 大于等于操作符（GE）：如果状态 3 的下一个字符是 =，就进入状态
4. 变成 >=。它也是比较操作符的一种情况。
5. 数字字面量：在初始状态时，下一个字符是数字，进入这个状态。如果后续仍是数字，就保持在状态 5。

这里我想补充一下，你能看到上图中的圆圈有单线的也有双线的。双线的意思是这个状态已经是一个合法的 Token 了，单线的意思是这个状态还是临时状态。

按照这 5 种状态迁移过程，你很容易编成程序（我用 Java 写了代码示例，你可以用自己熟悉的语言编写）。我们先从状态 1 开始，在遇到不同的字符时，分别进入 2、3、5 三个状态：

DfaState newState = DfaState.Initial;
if (isAlpha(ch)) {              //第一个字符是字母
    newState = DfaState.Id; //进入Id状态
    token.type = TokenType.Identifier;
    tokenText.append(ch);
} else if (isDigit(ch)) {       //第一个字符是数字
    newState = DfaState.IntLiteral;
    token.type = TokenType.IntLiteral;
    tokenText.append(ch);
} else if (ch == '>') {         //第一个字符是>
    newState = DfaState.GT;
    token.type = TokenType.GT;
    tokenText.append(ch);
}

上面的代码中，我用 Java 中的枚举（enum）类型定义了一些枚举值来代表不同的状态，让代码更容易读。

其中 Token 是自定义的一个数据结构，它有两个主要的属性：一个是“type”，就是 Token 的类型，它用的也是一个枚举类型的值；一个是“text”，也就是这个 Token 的文本值。

我们接着处理进入 2、3、5 三个状态之后的状态迁移过程：

case Initial:
    state = initToken(ch);          //重新确定后续状态
    break;
case Id:
    if (isAlpha(ch) || isDigit(ch)) {
        tokenText.append(ch);       //保持标识符状态
    } else {
        state = initToken(ch); //退出标识符状态，并保存Token
    }
    break;
case GT:
    if (ch == '=') {
        token.type = TokenType.GE;  //转换成GE
        state = DfaState.GE;
        tokenText.append(ch);
    } else {
        state = initToken(ch);      //退出GT状态，并保存Token
    }
    break;
case GE:
    state = initToken(ch);        //退出当前状态，并保存Token
    break;
case IntLiteral:
    if (isDigit(ch)) {
        tokenText.append(ch);    //继续保持在数字字面量状态
    } else {
        state = initToken(ch);    //退出当前状态，并保存Token
    }
    break;

运行这个示例程序，你就会成功地解析类似“age >= 45”这样的程序语句。不过，你可以先根据我的讲解自己实现一下，然后再去参考这个示例程序。示例程序的输出如下，其中第一列是 Token 的类型，第二列是 Token 的文本值：

Identifier   age
GE           >=  
IntLiteral   45  

上面的例子虽然简单，但其实已经讲清楚了词法原理，就是依据构造好的有限自动机，在不同的状态中迁移，从而解析出 Token 来。你只要再扩展这个有限自动机，增加里面的状态和迁移路线，就可以逐步实现一个完整的词法分析器了。

正则表达式

之前已经写过正则表达式的：正则表达式的使用方法不再赘述