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

大家好，欢迎来到IT知识分享网。

前言

本文原创，著作权归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搜索分词
• 对一段英文句中所有出现的地名、人名、时间月份等做标准化（如大写）处理