对于 go 语言源代码可以看做是一个很长的字符串,GO 编译器是如何识别出这个长字符串里边哪些是变量?哪些是赋值语句?哪些是函数?基本解决思路就是使用正则表达式对字符串进行分割,找到对应的标识,可以将这种标识转化为 token,将 go 源代码扫描找出所有 token 的过程称为词法分析。
1.正则表达式举例
对于一个正则表达式 (a|b)*abb,应该如何判断一个字符串对于该正则表达式满足呢?例如:
abb aabb babb aababb //肉眼可以看出上面字符串是符合上述正则表达式的 a ab bb acabb //肉眼可以看出上面字符串是不符合上述正则表达式的 abbaabbbaaabbbababaaababb //对于很长的字符串是否满足上述正则表达式,需要使用程序代码来实现,如何实现一个正则匹配的算法呢?
2.不确定有穷自动机(NFA)
对于一个正则表达式 (a|b)*abb,其对应的 NFA 对应如下:
这个自动机包含 4 个状态,其中 0、1、2 这 3 种状态用一个圈表示中间状态,3 是双圈表示状态机的结束,箭头和字母表示每个状态遇到不同输入迁移到另一个状态,可以用上述例子走一下该自动机,比如字符串 abb,初始状态 0,遇到 a,迁移到 1,状态 1 遇到 b,迁移到 2,状态 2 遇到 b,迁移到 3,状态 3 是结束状态,所以 abb 是满足正则表达式。对于 字符串 ab 最终状态是 2,不是结束状态,不满足正则表达式。但该有穷自动机有一个缺陷,就是状态 0 遇到 a,有可能迁移到状态 1,也有可能迁移到到本身状态 0,所以这里是不确定的有穷自动机,这就导致可能满足表达式的字符串,最终状态并没有到结束状态。
3.确定有穷自动机(DFA)
DFA 和 NFA 不同的是,对于每一个状态遇到的输入都有确定下一个状态,可以使用 re2c 这种工具帮助我们生成正则表达式对应的有穷自动机程序代码。
4.用 re2c 做词法解析
re2c 官网中介绍 go 词法解析的地址是 re2c官网,使用 git 命令可下载 re2c 源码包:
git clone https://github.com/skvadrik/re2c.git git clone https://git.code.sf.net/p/re2c/code-git
如果是 mac 电脑需要先使用 brew install automake 命令安装 automake, 下载后进入到 re2c 的源码目录下包下执行如下命令就可生成 configure 文件:
进入到 re2c 目录下执行 ./configure && make && make install 命令即可开始编译 re2c :
编译安装完之后,执行 re2c 命令出现如下图所示内容表示安装成功:
提示需要指定源文件,这里编辑一个 t.go 文件,用于判断某个字符是不是二进制数,编辑内容如下:
//go:generate re2go $INPUT -o $OUTPUT -i package main func lex(str string) { var cursor int /*!re2c re2c:define:YYCTYPE = char; re2c:yyfill:enable = 0; end = "\x00"; bin = '0b'[01]+; * { return ERR; } bin end { return BIN; } */ } func main() { lex("0b1") }
上面 /*!re2c 和 */ 之间的内容可以理解为词法解析的正则表达式,这里可以根据自己的需要自己编写正则表达式,re2c 代码库会帮我们生成有限自动机程序代码,然后使用 re2c t.go 命令,可生成与之对应的有限自动机:
生成的与之对应的有限自动机(DFA)程序代码如下:
/* Generated by re2c 2.2 on Thu Oct 21 00:13:40 2021 */ #line 1 "t.go" //go:generate re2go $INPUT -o $OUTPUT -i package main func lex(str string) { var cursor int #line 12 "<stdout>" { char yych; yych = *YYCURSOR; switch (yych) { case '0': goto yy4; default: goto yy2; } yy2: ++YYCURSOR; yy3: #line 13 "t.go" { return ERR; } #line 25 "<stdout>" yy4: yych = *(YYMARKER = ++YYCURSOR); switch (yych) { case 'B': case 'b': goto yy5; default: goto yy3; } yy5: yych = *++YYCURSOR; if (yych >= 0x01) goto yy8; yy6: YYCURSOR = YYMARKER; goto yy3; yy7: yych = *++YYCURSOR; yy8: switch (yych) { case 0x00: goto yy9; case '0': case '1': goto yy7; default: goto yy6; } yy9: ++YYCURSOR; #line 14 "t.go" { return BIN; } #line 52 "<stdout>" } #line 15 "t.go" } func main() { lex("0b1") }
对应的有限自动机图如下图:
5.go 词法解析demo
package main import ( "fmt" "go/scanner" "go/token" ) func main() { src := []byte("cos(x) + 2i*sin(x) //Euler") //初始化 scanner var s scanner.Scanner fset := token.NewFileSet() file := fset.AddFile("",fset.Base(),len(src)) s.Init(file,src,nil,scanner.ScanComments) //扫描 for { pos,tok,lit := s.Scan() if tok == token.EOF{ break } fmt.Println("%s\t%s\t%q\n",fset.Position(pos),tok,lit) } }
其中字符串 “cos(x) + 2i*sin(x) //Euler” 可以理解为源代码,输出结果就是将其词法解析,然后 token 化,至此词法解析已经简单实现:
源代码 token 化后,就可进行语法解析,后面将继续介绍语法解析和抽象语法树构建。
