模板引擎实现（一）词法分析

内容简介：模板引擎实现（一）词法分析

如果你想实现模版引擎、编译器前端、文本解析器（比如 Markdown ）或想要了解它们的实现原理，请一定不要错过本系列的文章

• 模板引擎实现（一）词法分析

本文介绍了**词法分析**的基本概念，主要参考 golang 的 text/template/parse 包源码进行解析。

词法分析

将面向源码的字符流转成 token 流的过程是词法分析。用“流”来描述主要说明了处理过程是**有序**和**连续**的。比如读取源码文件时是一个字符一个字符读取的，生成的 token 也是一个接一个的。

当我们在源码中看到 scanner、lex/lexeme、token/tokenize、item 等描述的时候我们就应该知道这是在干词法分析相关的事情了。

Token

一个 Token 是带了一个分类的字符串，这个字符串叫做词素（lexeme）。

比如对于源码语句 sum = 3 + 2 来说，

Lexeme	Token 分类
sum	Identifier
=	Assignment operator
3	Integer literal
+	Addition operator
2	Integer literal

详见 Lexical analysis 。

golang 的模版包中是使用 item 结构体来描述 token 的。

状态机

词法分析中用到状态机是为了解决“当前 token 识别后下一步怎么处理”的问题。

switch-case

传统状态机的实现是在状态处理函数中返回下一个待执行的状态：

for state != nil {
    switch state {
    case state1:
        state = action1()
    case state2:
        state = action2()
    case state3:
        state = action3()
    }
}

这是一个典型的**命令式编程**范式的过程化实现（也可以用面向对象实现，下面会提到）。

状态函数

而 lex.go 的实现方式是通过“置换”下一个待执行的行为，将状态迁移的实现从**状态**决定改进为**行为**决定：

type stateFn func() stateFn
func action1() stateFn { return actionN }
func action2() stateFn { return actionM }

for state = action1; state != nil; {
	state = state()
}

这是**声明式编程**范式中函数式的典型实现，该实现的巧妙之处在于 stateFn 是递归定义的，函数的返回值是符合该签名的自身定义，整个状态变迁过程就是这个函数的迭代展开。

其他状态机实现

另外还有两种常见的状态机实现：

1. 状态表/表驱动：可理解为将所有可能出现的状态及其变迁状态表格化，状态变迁就是查表找到下一个状态
2. 状态模式：使用面向对象 设计模式 中的状态模式来实现，本质上和上面的 switch-case 无差异

回退

回退指的是当前字符读取后需要“退格”一下，比如读到一个字符 'a' 时，我们将进入到标识符处理函数。进入之前需要将 a 退格出来，以便在标识符处理函数里面能够完整读取。

case isAlphaNumeric(r):
	l.backup() // 退格

	return lexIdentifier

并发分析

text/template/parse 使用 goroutine 并发执行词法分析和语法分析。parser 通过 channel 来接收 lexer 处理好的 tokens，每当一个新的 token 产生，parser 就会收到并处理，生成 node，构建 ast。

并发分析的好处是：

• 词法分析和语法分析较为独立，没有执行顺序的依赖
• lexer 只需要通过一个 chan 就能将 token 给到 parser，简化了数据结构
• 能够更早地发现语法错误，因为不必等词法分析都跑完
• 性能相对于词法分析完再进行语法分析可能会更好（我瞎猜的 ）

结语

golang 模版的词法分析实现是非常简洁的，亮点主要在于通过**函数式编程实现状态机**，并使用了 channel 进行**词法、语法并发分析**，简化了设计并提高了效率。

模版引擎的词法分析部分我们就此结束，下一次我们将介绍语法分析，谢谢大家阅读

参考

• Lexical Scanning in Go - Rob Pike 大神亲自介绍 go 模版词法分析实现
• Handwritten Parsers & Lexers in Go 类 SQL 解析器实现

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

• 手写一个词法分析器
• 深入ECMAScript系列（一）：词法环境
• 图解词法作用域与作用域链
• 【PHP源码学习】2019-03-20 PHP词法分析
• 百度深度学习中文词法分析工具LAC试用之旅
• Shading-jdbc源码分析-sql词法解析

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。