"如果你想实现模版引擎、编译器前端、文本解析器(比如 Markdown )或想要了解它们的实现原理,请一定不要错过本系列的文章 [链接] 另外, 本系列的文章面向的是撸起袖子就开干的朋友,所以不会介绍基础理论,比如 DFA/NFA,算法复杂度等(确切的说是没法介绍理论,因为作者能力有限 ) 在使用到的术语 / 定义方面作 .."

模板引擎实现(一)词法分析

本贴最后更新于 659 天前,其中的信息可能已经天翻地覆

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

另外,

  • 本系列的文章面向的是撸起袖子就开干的朋友,所以不会介绍基础理论,比如 DFA/NFA,算法复杂度等(确切的说是没法介绍理论,因为作者能力有限 😂)
  • 在使用到的术语 / 定义方面作者是认真查过资料并再三斟酌的,不会出现胡编乱造,请放心理解和使用 ✅
  • 本系列文章的对应项目是 freemarker.go(FreeMarker 的 golang 实现),欢迎大家关注点赞 🌟

本文介绍了词法分析的基本概念,主要参考 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。

并发分析的好处是:

结语

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

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

参考

  • 模版引擎
    1 引用 • 20 回帖
  • 词法分析
    1 引用 • 20 回帖
  • golang

    Go 语言是 Google 推出的一种全新的编程语言,可以在不损失应用程序性能的情况下降低代码的复杂性。谷歌首席软件工程师罗布派克(Rob Pike)说:我们之所以开发 Go,是因为过去 10 多年间软件开发的难度令人沮丧。Go 是谷歌 2009 发布的第二款编程语言。

    241 引用 • 1005 回帖 • 784 关注
  • 编译原理
    2 引用 • 20 回帖
感谢    关注    收藏    赞同    反对    举报    分享
优质回帖
  • 88250  

    嗯,欢迎来帮忙!

19 回帖    
请输入回帖内容...
  • DASHU      

    厉害了 D,真要开搞啊

    1 回复 
    感谢    赞同    反对    举报    分享       回复
  • 88250            

    嗯,欢迎来帮忙!

    2 回复 
    感谢    赞同 1    反对    举报    分享       回复
  • DASHU            

    目前深陷泥潭。。。脱不得身

    感谢    赞同    反对    举报    分享       回复
  • iTanken      

    Solo 以后也要改成 Go 吗?Javaer 好忧伤 🤣

    感谢    赞同    反对    举报    分享       回复
  • yangyujiao      

    昨天看了 drools 是个规则引擎。 现在看到引擎两个字,感觉好厉害噢。一副没见过世面的样子😂

    感谢    赞同    反对    举报    分享       回复
  • junze      

    厉害了 👍

    感谢    赞同    反对    举报    分享       回复
  • Vanessa      

    赶紧写。写出来才是真腻害

    1 回复 
    感谢    赞同    反对    举报    分享       回复
  • 61260551 1 感谢              

    需要鞭笞

    感谢    赞同    反对    举报    分享       回复
  • someone API      

    厉害了。😂

    感谢    赞同    反对    举报    分享       回复
  • zonghua      

    别啊,不要酱紫

    感谢    赞同    反对    举报    分享       回复
  • rzx            

    😬solo 真的很棒,最近上手改了改 91php7e35f9cad7ad437b89f6186d39852f8c-QQ20170626225718.png , 还不是太熟悉,有点问题想请教,我看文档说有相关阅读这各部分,但是这个 theme 好像没有。

    1 回复 
    感谢    赞同    反对    举报    分享       回复
  • 88250            

    看了下,好像确实漏了,还漏了个随机阅读… 这是 @Vanessa 的锅 👿 你看下 page.js 里面的 loadRelevantArticlesloadRandomArticles

    2 回复 
    感谢    赞同    反对    举报    分享       回复
  • Vanessa            

    @rzx 已修复

    1 回复 
    感谢    赞同    反对    举报    分享       回复
  • rzx            

    OK,3Q,我猜应该是,写了方法,没有整展示模块, 😆 哈哈。我去看看

    感谢    赞同    反对    举报    分享       回复
  • rzx            

    。。宝宝拉了最新的,,没看到有更新相关阅读啊 😢

    1 回复 
    感谢    赞同    反对    举报    分享       回复
  • Vanessa            

    在分支上。。。

    1 回复 
    感谢    赞同    反对    举报    分享       回复
  • rzx            

    😭 😭 好吧,我去找找 😢3Q

    感谢    赞同    反对    举报    分享       回复
  • mainlove      

    然后恩

    感谢    赞同    反对    举报    分享       回复
  • JRoger API      

    😂 没有然后了吗?

    感谢    赞同    反对    举报    分享       回复
请输入回帖内容...