文章内容更新请以 WGrape GitHub博客 : 编译器前端之初探词法分析器为准

前言

本文原创，著作权归WGrape所有，未经授权，严禁转载

前言

本文原创，著作权归WGrape所有，未经授权，严禁转载

阅读指南

阅读此篇文章，你能从中学到什么？

什么是词法分析器
词法分析器的工作原理
词法分析器的应用场景

一、词法分析器的介绍

1、什么是词法分析器

(1) 官方文字定义

词法分析器如其名所称，是一种用于词法分析的工具。不过什么是词法分析呢？如果用比较官方的文字，那么它的定义大概如下

词法分析是计算机科学中将字符序列转换为记号（token）序列的过程

在编译原理理论中，词法分析又与语法分析、中间代码生成、代码优化、目标代码生成共同组成了编译程序构造的一般原理和基本方法。

(2) 简单轻松理解

看到这里，你对词法分析的理解可能还停留在抽象的文字上，真正的理解它的概念，我们可以先看一段简单的golang代码。

func (p *person) talk(content string){
}

如果你熟悉golang语言，就可以顺利成章的理解了上面代码的含义。但现在思考一个问题，我们为什么可以顺利成章的理解代码的含义？换句话说就是如何教会机器理解上面代码的含义呢？这就是编译原理所涵盖的内容。不过编译原理是非常深奥的一门理论，今天我们介绍的也只是它其中的一个部分，即词法分析。

重新回到上面代码，首先是func关键字标识了函数的开始，紧跟着的(和)双括号内定义了p这个person类型的*指针变量，函数名为talk，紧跟着的(和)双括号内又定义了一个string类型的content参数，最后用{和}两个花括号定义了函数体。

这样一段代码已经被我们分割成了func、(、p、*、person、)、talk、( 、content、string、)、{和}这样一个一个的单元。

到这里可能你已经明白了些什么，没错，代码被分割的过程就是词法分析的过程，而分割后得到的一个一个的单元，就称为token（记号）。

简而言之，词法分析器会做一个有规则的代码切割，然后会生成一个有序的token列表。

(3) token的作用

上面讲到，编译原理把编译程序构造的基本方法分为了词法分析、语法分析、中间代码生成、代码优化、目标代码生成这几个过程。你可以简单把它理解为一个有序的流水线，上游为下游提供数据。词法分析为语法分析提供的数据就是token列表。

(4) token的类型

特别需要注意的是，token是有类型区分的，不同类型的token也需要起着不同的作用。在不同的语言中，token类型也有差异，不过一般情况下，token的类型主要分为keyword关键字、Identifier标识符、operator、whitespace空白符等。

图片来自：https://wgrape.github.io/lexer/?lang=c

(5) token的生成

对于词法分析器而言，无论你输入的代码有多少，都会把它作为一整个字符串处理。在遍历字符串的过程中，实现token生成的算法一般有两种，暴力法和DFA算法。

暴力法

在遍历字符串过程中，使用if判断当前字符的类型的同时，需要对比上一个字符或下一个字符，再用蛮力的方式列举所有可能出现的情况，来决定当前的处理方式。

DFA算法

DFA算法即限状态自动机，其特点是可以实现状态的自动转移，可以用于解决字符匹配问题。关于它的详细介绍和应用，可以参考文章编译器前端之如何实现基于DFA的词法分析器

二、词法分析器的实现原理

在lexer项目中，使用非常简单易懂的代码设计实现了词法分析器，下面是其中一段核心的代码输入处理逻辑，如需深入了解请参考原lexer项目。

// 字符串输入处理
function read() {
    let ch = '';
    while ((ch = lexer.ISR.nextChar()) !== false) {
        let match = false;
        let end = false;

        // 根据状态判断是否匹配
        let state = lexer.DFA.state;
        let nextState = flowModel.getNextState(ch, state, lexer.DFA.result.matchs);
        if (nextState !== DFA_STATE_CONST.S_RESET) {
            match = true;
            if (lexer.ISR.isLastChar()) {
                end = true;
            }
        }

        // 匹配与未匹配时的不同处理逻辑
        if (match) {
            lexer.ISR.propsChange.incrSeq();
            lexer.DFA.events.flowtoNextState(ch, nextState);
            if (end) {
                lexer.DFA.resultChange.produceToken();
            }
        } else {
            lexer.DFA.resultChange.produceToken();
            lexer.DFA.events.flowtoResetState();
        }
    }
}

三、词法分析器的应用场景

1、编译器前端工具链

在实际应用中，词法分析器、语法分析器、语义分析器通常会组成一个完整的编译器前端工具链，用来处理并解决如下问题。

(1) 编译器前端的一部分

词法分析器是编译器前端必备的一个组成部分，如著名的的Clang项目

(2) 编程语言识别与代码高亮

编程语言的识别可以通过识别Token实现，如关键字Token等。

对于代码中不同关键字、符号、运算符等词语允许显示不同颜色的需求，就需要用到词法分析器处理。在它分析出代码中所有不同的token类型后，设置不同的颜色即可

(3) 代码提示与补全

在IDE中会有大量代码提示的场景，这些代码提示的功能也都可以通过匹配词法分析器输出的Token实现

2、语言标准化处理

当需要对编程语言或人类语言做标准化处理时，都需要用到词法解析。常见的场景如下

ES搜索分词
对一段英文句中所有出现的地名、人名、时间月份等做标准化（如大写）处理

编译器前端之初探词法分析器

前言

前言