解析器眼中的 Go 语言 · /golang-lexer-and-parser

[draveness]

https://draveness.me/golang-lexer-and-parser

[wujunze]

你好 博主 这个源码分析是基于 Go 的哪个版本 我用的1.11.2 发现源码内容对不上

[draveness]

@wujunze 你好 博主 这个源码分析是基于 Go 的哪个版本 我用的1.11.2 发现源码内容对不上

代码太多了， 进行了一些删减

[xzghua]

涨知识了

[xzghua]

2.2. 分析方法

语法分析的分析方法一般分为自顶向上和自底向下两种，这两种方式会使用不同的方式对输入的 Token 序列进行推导：

应该是

2.2. 分析方法

语法分析的分析方法一般分为自顶向下和自底向上两种，这两种方式会使用不同的方式对输入的 Token 序列进行推导：

[sjatsh]

博主，你是基于哪个版本分析的？

[draveness]

@sjatsh 博主，你是基于哪个版本分析的？

1.13 很多地方都加了方法的链接，可以直接点过去，有较大的更新，这里也会更新的

[draveness]

博主，你是基于哪个版本分析的？

现在是 1.14 了

[icetop]

牛币

[baixiaoshi]

你自己真的懂吗

[draveness]

你自己真的懂吗

@baixiaoshi ？

[draveness]

@baixiaoshi 你自己真的懂吗

我可能不懂，那你能给我讲讲么？

[yanjinbin]

解析向上和向下 写的感觉有点复杂了 我猜就是token构建的tree从root开始 还是 leave node开始吧
一个疑问： 2种策略的优劣在哪里呢？

[draveness]

解析向上和向下 写的感觉有点复杂了 我猜就是token构建的tree从root开始 还是 leave node开始吧

你觉得哪里不必要呢？

一个疑问： 2种策略的优劣在哪里呢？

这个问题 Google 一下吧，资料很多..

[yanjinbin]

@draveness

解析向上和向下 写的感觉有点复杂了 我猜就是token构建的tree从root开始 还是 leave node开始吧

你觉得哪里不必要呢？

一个疑问： 2种策略的优劣在哪里呢？

这个问题 Google 一下吧，资料很多..

sorry 我对编译知识缺失，这里出现的专业术词 还是很难理解，等我把 USTC的华保健看了 再说 😓

[Subfire]

没学编译原理看章这太难了😂

[Janetyu]

大佬写的文章很棒，涨姿势了，虽然没看太懂~

文中有一处小笔误：

”自顶向下 LL 文法17就是一种使用自顶向上分析方法的文法，下面给出了一个常见的 LL 文法：“

应该是 “自顶向下”

---

2020-05-29 UPDATES：已修复

[liuxg]

分析方法，自顶向下那一节是不是写错了，写成自顶向上了

---

2020-05-29 UPDATES：已修复

[Jax-Rene]

大佬写的太好了，大学过后就没回顾过编译原理了。看这篇文章居然还能勉强看懂，算是对Golang编译这块有点基础的了解了，感谢作者！

[draveness]

@jony-one 我还请教一下吧。golang 把所有编译的接口都开源的，我想知道怎么调用获取词法分析结果。然后获取语义分析结果。然后获取中间代码。

https://github.com/golang/go/tree/master/src/go 这里能找到编译相关的全部 package

目前我调的 syntax.Parse 获取的应该是词法分析结果过吧？不大确定，清指导下

你可以看看这个例子，如何获取抽象语法树 https://golang.org/pkg/go/ast/#example_Inspect

[tsunhua]

上述规则构成的文法就能够表示 ab、aabb 以及 aaa..bbb 等字符串

这里有问题哦，只能表示 {a^nb^n, n>=1} 吧。除非最后的规则改为 S = ε， 参考：https://en.wikipedia.org/wiki/Context-free_grammar

---

2021-01-12 UPDATES: 已修复

[godruoyi]

作者你好，最近在学习 Go 词法分析的时候，有些分不清 src/cmd/compile/internal/syntax/parser.go 解析器和 src/go/parser/parser.go 解析器的区别。

如下面的例子：

func main() {
    println("hello")
}

这列子肯定不能通过编译，但若 Go 编译时用的是 cmd/compile/internal/syntax/parser.go 解析器，理应得到一个如下的错误：

if !p.got(_Package) {
    p.syntaxError("package statement must be first")
    return nil
}

但在实际编译中的错误提示却是：

cmd/hello.go:1:1: expected 'package', found 'func'

这实际上是 src/go/parser/parser.go 解析器包的错。

pos := p.expect(token.PACKAGE)

func (p *parser) expect(tok token.Token) token.Pos {
    if p.tok != tok {
        p.errorExpected(pos, "'"+tok.String()+"'")
    }
}

func (p *parser) errorExpected() {
    msg += ", found " + p.lit
    p.error(pos, msg)
}

所以我不是很清楚：

1. 这两个解析器有什么却别？
2. Go 词法分析的入口到底是什么？
3. 如果是学习目的，应该从哪个入手（虽然感觉学任意一个都能快速熟悉另外一个）

如果作者有时间的话，万分期待你的回复。

go

[draveness]

@godruoyi

1. 这两个解析器有什么却别？

前者是内部的实现，后者是 Go 语言暴露给『插件开发者』的接口

2. Go 词法分析的入口到底是什么？

前者

3. 如果是学习目的，应该从哪个入手（虽然感觉学任意一个都能快速熟悉另外一个）

学习编译器实现看前面的，想写 go generate 插件学后面的

[godruoyi]

或者这样说吧，如果我们执行 go build main.go 时对目标文件进行词法分析用的是 src/cmd/compile/internal/syntax/parser.go 解析器，那为什么上面的报错信息却提示的是 src/go/parser/parser.go 解析器的报错信息呢。

[draveness]

或者这样说吧，如果我们执行 go build main.go 时对目标文件进行词法分析用的是 src/cmd/compile/internal/syntax/parser.go 解析器，那为什么上面的报错信息却提示的是 src/go/parser/parser.go 解析器的报错信息呢。

我看了一下，其实没有找到答案，如果你找到了可以告诉我

你好 博主，想请教下src/go/token/token.go 和 src/cmd/compile/internal/syntax/tokens.go 有什么区别呢 ，我看这个作者https://github.com/chai2010/go-ast-book 是用 src/go/token/token.go 讲的，有点懵，难道前者也是暴露给插件开发者用的吗

可以这么理解，所有的 internal 的都是内部实现，其他包是引用不了的

[StrayCamel247]

看完后后面的gc和并发回头重新看一边，这份文档真不错！🙃

[bugangongwei]

@godruoyi 或者这样说吧，如果我们执行 go build main.go 时对目标文件进行词法分析用的是 src/cmd/compile/internal/syntax/parser.go 解析器，那为什么上面的报错信息却提示的是 src/go/parser/parser.go 解析器的报错信息呢。

就是用的 src/go/parser/parser.go 解析器;

我看的是 go1.13.8 的源码, 从 cmd/go/main.go 这个文件进去, 读 go build 的源代码, 最终定位到 go/build/build.go 文件 Import 方法对 parser.ParseFile 的调用 , 这块就是调用 go/parser/interface.go 中的 ParseFile 方法;

src/cmd/compile/internal/syntax/parser.go 这个解析看起来是 go compile 这个命令在使用;

[bugangongwei]

@bugangongwei

@godruoyi 或者这样说吧，如果我们执行 go build main.go 时对目标文件进行词法分析用的是 src/cmd/compile/internal/syntax/parser.go 解析器，那为什么上面的报错信息却提示的是 src/go/parser/parser.go 解析器的报错信息呢。

就是用的 src/go/parser/parser.go 解析器;

我看的是 go1.13.8 的源码, 从 cmd/go/main.go 这个文件进去, 读 go build 的源代码, 最终定位到 go/build/build.go 文件 Import 方法对 parser.ParseFile 的调用 , 这块就是调用 go/parser/interface.go 中的 ParseFile 方法;

src/cmd/compile/internal/syntax/parser.go 这个解析看起来是 go compile 这个命令在使用;

src/cmd/compile/internal/syntax/parser.go 这个解析器看起来是 go tool compile 这个命令在使用;

~ go tool
addr2line
asm
buildid
cgo
compile
cover
dist
doc
fix
link
nm
objdump
pack
pprof
test2json
trace
vet

[godruoyi]

我看的是 go1.13.8 的源码, 从 cmd/go/main.go 这个文件进去, 读 go build 的源代码, 最终定位到 go/build/build.go 文件 Import 方法对 parser.ParseFile 的调用 , 这块就是调用 go/parser/interface.go 中的 ParseFile 方法; src/cmd/compile/internal/syntax/parser.go 这个解析看起来是 go compile 这个命令在使用;

@bugangongwei @draveness

确实是这样，go build 是使用的 go/parser/interface.go 来 ParseFile，而 go tool compile 才是使用的 src/cmd/compile/internal/syntax/parser.go。但要是这样的话，那研究 go 编译过程不应该去研究前者吗？并且既然前者已经提供了完整的分析过程 & 方法，那 go tool compile 这个工具的定位是什么呢？抱歉可能问得有点唐突。

[draveness]

我看的是 go1.13.8 的源码, 从 cmd/go/main.go 这个文件进去, 读 go build 的源代码, 最终定位到 go/build/build.go 文件 Import 方法对 parser.ParseFile 的调用 , 这块就是调用 go/parser/interface.go 中的 ParseFile 方法; src/cmd/compile/internal/syntax/parser.go 这个解析看起来是 go compile 这个命令在使用;

@bugangongwei @draveness

确实是这样，go build 是使用的 go/parser/interface.go 来 ParseFile，而 go tool compile 才是使用的 src/cmd/compile/internal/syntax/parser.go。但要是这样的话，那研究 go 编译过程不应该去研究前者吗？并且既然前者已经提供了完整的分析过程 & 方法，那 go tool compile 这个工具的定位是什么呢？抱歉可能问得有点唐突。

go tool compile 其实是一个层级更低的接口1

Compile, typically invoked as “go tool compile,” compiles a single Go package comprising the files named on the command line. It then writes a single object file named for the basename of the first source file with a .o suffix.

[bugangongwei]

@draveness

我看的是 go1.13.8 的源码, 从 cmd/go/main.go 这个文件进去, 读 go build 的源代码, 最终定位到 go/build/build.go 文件 Import 方法对 parser.ParseFile 的调用 , 这块就是调用 go/parser/interface.go 中的 ParseFile 方法; src/cmd/compile/internal/syntax/parser.go 这个解析看起来是 go compile 这个命令在使用;

@bugangongwei @draveness

确实是这样，go build 是使用的 go/parser/interface.go 来 ParseFile，而 go tool compile 才是使用的 src/cmd/compile/internal/syntax/parser.go。但要是这样的话，那研究 go 编译过程不应该去研究前者吗？并且既然前者已经提供了完整的分析过程 & 方法，那 go tool compile 这个工具的定位是什么呢？抱歉可能问得有点唐突。

go tool compile 其实是一个层级更低的接口1

Compile, typically invoked as “go tool compile,” compiles a single Go package comprising the files named on the command line. It then writes a single object file named for the basename of the first source file with a .o suffix.

感觉 go tool compile 的特征, go build 都支持了, 可能是 go tool compile 原本是想提供给开发者自己编译不同 go 源码, 后来发现 go build 也可以支持, 但是人家开发人员也不想删了, 就这样放着了?

目前看下来, 两者比较明显的不同点是, go build 生成可执行文件, go tool compile 生成 .o 文件;

[bugangongwei]

@godruoyi

我看的是 go1.13.8 的源码, 从 cmd/go/main.go 这个文件进去, 读 go build 的源代码, 最终定位到 go/build/build.go 文件 Import 方法对 parser.ParseFile 的调用 , 这块就是调用 go/parser/interface.go 中的 ParseFile 方法; src/cmd/compile/internal/syntax/parser.go 这个解析看起来是 go compile 这个命令在使用;

@bugangongwei @draveness

确实是这样，go build 是使用的 go/parser/interface.go 来 ParseFile，而 go tool compile 才是使用的 src/cmd/compile/internal/syntax/parser.go。但要是这样的话，那研究 go 编译过程不应该去研究前者吗？并且既然前者已经提供了完整的分析过程 & 方法，那 go tool compile 这个工具的定位是什么呢？抱歉可能问得有点唐突。

我觉得这个问题可能也不是很重要, 你需要编译源码的时候, 最好用 go build, 如果你好奇心很重, 去 github 问问开发者, 然后来告诉我一下吧, 哈哈哈

[hick]

如果说前面几节我还看得饶有兴致(虽然也似懂非懂), 到 2.2.2 语法分析 的 文法部分彻底蒙圈了, 接着 "下面给出了一个常见的 LL 文法" 的后面看得我一愣一愣的, 或者可能是我需要去看下编译原理的书了? 哈哈哈哈

[draveness]

@hick 如果说前面几节我还看得饶有兴致(虽然也似懂非懂), 到 2.2.2 语法分析 的 文法部分彻底蒙圈了, 接着 "下面给出了一个常见的 LL 文法" 的后面看得我一愣一愣的, 或者可能是我需要去看下编译原理的书了? 哈哈哈哈

有道理，这个反馈很有价值，确实应该稍微展开一下 LL 文法是什么，不过也可以点链接看看

[TreeFalling]

没学过编译原理，这块读起来属实有些顶，所以这部分没看懂会妨碍之后的内容吗...

[draveness]

@TreeFalling 没学过编译原理，这块读起来属实有些顶，所以这部分没看懂会妨碍之后的内容吗...

个人觉得不妨碍，还是相对比较独立的

[HelloBug0]

词法分析就是单纯的字符串解析？每次解析出来一个单词，然后进行switch case判断，最终生成的token序列长什么样呢？

[HelloBug0]

语法分析讲解的太抽象了，没有编译原理基础，基本看不懂

[snail2sky]

有点晕，脑瓜子嗡嗡的~，不过觉得讲的是真的好，先有个大概的印象也是不错的 赞

[gengjiawen]

这里可以看go的ast： https://astexplorer.net/#/gist/825ad220483f53e3a7eec8bacd2bbac1/1245c33ba48428cdded60d7b65e6352d504371b4

[iam153]

for p.got(_Import) { f.DeclList = p.appendGroup(f.DeclList, p.importDecl) p.want(_Semi) } 博主你好，从这里来看，import语句最后一定要加一个分号吧？因为p.want(_Semi)里拿到的不是分号就会直接报错执行p.syntaxError(...)。但是实际写代码的时候好像不加也可以？

[WineChord]

@draveness

我看的是 go1.13.8 的源码, 从 cmd/go/main.go 这个文件进去, 读 go build 的源代码, 最终定位到 go/build/build.go 文件 Import 方法对 parser.ParseFile 的调用 , 这块就是调用 go/parser/interface.go 中的 ParseFile 方法; src/cmd/compile/internal/syntax/parser.go 这个解析看起来是 go compile 这个命令在使用;

@bugangongwei @draveness

确实是这样，go build 是使用的 go/parser/interface.go 来 ParseFile，而 go tool compile 才是使用的 src/cmd/compile/internal/syntax/parser.go。但要是这样的话，那研究 go 编译过程不应该去研究前者吗？并且既然前者已经提供了完整的分析过程 & 方法，那 go tool compile 这个工具的定位是什么呢？抱歉可能问得有点唐突。

go tool compile 其实是一个层级更低的接口1

Compile, typically invoked as “go tool compile,” compiles a single Go package comprising the files named on the command line. It then writes a single object file named for the basename of the first source file with a .o suffix.

为了方便描述，

把 go/src/parser 下的解析器称为 parser1

把 go/src/cmd/compile/internal 下的解析器称为 parser2

go tool compile 这个是用到了的（即 parser2），go/src/go/parser/interface.go 下面的 ParseFile 也是用到了的（即 parser1），简单来说，parser1 在 go build xxx.go 的过程中只是用来解析了 package 以及 imports 这两部分（用于初步提 package 相关的信息），而完整的整个编译过程还是通过调用 parser1 即 compile 这个二进制（linux_amd64 环境下该二进制位于 go/pkg/tool/linux_amd64）来完成的。

完整的源码追踪如下（基于 go 1.15.5）：

1. 当我们敲下 go build xxx.go 之后，运行的是 go 这一个二进制文件，该执行文件的 main 函数在 go/src/cmd/go/main.go 中的 func main.. 中，go build 则对应于该文件的 init 函数中设置的 work.CmdBuild 命令，CmdBuild 这个命令变量定义在 go/src/cmd/go/internal/work/build.go 文件中（可以直接从 main.go 中跳转定义找到这里），从这个命令可以看出其对应的就是 go build 这一命令，在这个 build.go 文件的 init 函数中定义了该命令实际运行的函数 CmdBuild.Run = runBuild，即实际运行的是 runBuild，跳转到该函数所在的位置（仍在当前文件 build.go 中），至此我们就已经找到了 go build 执行的真正入口。

2. 我们现在来找哪里使用了 parser1。在 runBuild 开始的第五行 pkgs := load.PackagesForBuild(args) 跳转进 PackagesForBuild，在该函数的第一行找到并跳转进 pkgs := PackagesAndErrors(args)，在 PackagesAndErrors 的第一个 return 处找到并跳转 return []*Package{GoFilesPackage(patterns)}，在 GoFilesPackage 函数中找到并跳转 bp, err := ctxt.ImportDir(dir, 0)，进入 ImportDir 跳转进 ctxt.Import，在这个很长的函数中可以找到对 parser1 的调用：pf, err := parser.ParseFile(fset, filename, data, parser.ImportsOnly|parser.ParseComments)，从传入的参数可以看到这个 parser1 只处理了 imports 之前以及注释的部分。这样就可以解释为什么开始没写 package 时编译报错显式的是 parser1 的错误。

3. 我们现在再来找哪里使用了 parser2 。回到 runBuild 函数，这个函数会先注册一些 build 或 install 的 Action，然后调用 b.Do 来执行这些 Action，所以只要找到 build 对应的 Action 的执行入口即可，我们跳到 AutoAction，然后找到里面调用的 CompileAction，跳到 CompileAction 中可以看到 build 对应的 Action.Func 字段填写的 (*Builder).build 即为执行入口，跳转进 (*Builder).build，经过一系列的判断（判断是不是要调用 cgo 啥的，但是这些都不是我们现在这个命令的执行目的地），最后找到 ofile, out, err := BuildToolchain.gc(b, a, objpkg, icfg.Bytes(), symabis, len(sfiles) > 0, gofiles)，即 BuildToolchain.gc 才是我们真正要执行的编译器（全小写 gc 表示 go compiler，全大写 GC 才表示 garbage collection，这个在 parser2 源码的 README 中有写），跳转进去，发现 gc 是 toolchain interface 的实现，跳转 BuildToolchain，发现这是一个全局变量，这个全局变量会根据环境变量用 (c buildCompiler) Set 来进行设置，最后其实代表的就是 gcToolchain 这个具体的结构体，跳转到 gcToolchain 这个结构体的定义，找到他的 gc 方法，这就是 parser2 的真正入口！该方法实现在 go/src/cmd/go/internal/work/gc.go 中，该方法会设置要调用的 compile 二进制所需要的参数：

   args := []interface{}{cfg.BuildToolexec, base.Tool("compile"), "-o", ofile, "-trimpath", a.trimpath(), gcflags, gcargs, "-D", p.Internal.LocalPrefix}

   （注意这一行里面的 base.Tool("compile") 最后展开就是形如 $GOROOT/pkg/tool/linux_amd64/compile 这样的完整路径） 然后在该方法的倒数第二行

   output, err = b.runOut(a, p.Dir, nil, args...)

   中的（跳转进 runOut）

   cmd := exec.Command(cmdline[0], cmdline[1:]...)

   来对 compile 这个二进制文件进行调用！

后记：可以通过不是 package 错误的文件来简单验证，比如以下文件

package main

func main() {
        println("hello")
        var 
}

该文件的 package 部分没有错，用 go build test.go 可以得到如下错误：

# command-line-arguments
./test.go:6:1: syntax error: unexpected }, expecting name

可以在源码中找到是在 go/src/cmd/compile/internal/syntax/parser.go 的 syntaxErrorAt 方法中构造出来的。

[WineChord]

@iam153 for p.got(_Import) { f.DeclList = p.appendGroup(f.DeclList, p.importDecl) p.want(_Semi) } 博主你好，从这里来看，import语句最后一定要加一个分号吧？因为p.want(_Semi)里拿到的不是分号就会直接报错执行p.syntaxError(...)。但是实际写代码的时候好像不加也可以？

你可以看一下 src/cmd/compile/internal/syntax/scanner.go 里面 next() 的实现，当遇到 \n 时，会设置 s.tok 为 _Semi，其实相当于会把每个换行符看成分号

[imcuttle]

作者你好，有个小问题： 如果说 GO 的编译过程，如词法分析 & 语法分析 是基于 go 编码实现的，那么这块 go 语言代码是基于什么来进行执行的呢？ 或者说前期是存在一个其他语言实现的 go 的编译过程，有了这个之后，才有的 go 语言实现的 go 的编译过程吗？

[WineChord]

@imcuttle 作者你好，有个小问题： 如果说 GO 的编译过程，如词法分析 & 语法分析 是基于 go 编码实现的，那么这块 go 语言代码是基于什么来进行执行的呢？ 或者说前期是存在一个其他语言实现的 go 的编译过程，有了这个之后，才有的 go 语言实现的 go 的编译过程吗？

Go 的编译器前期是用 C 写的，后来改成 Go，你可以去搜一下 编译器自举（bootstrap）

[Rain-Life]

老师您好。Go的语法解析过程，用的是自顶向下的分析方式进行语法分析的吧？我看文中说：Go 语言的解析器使用了 LALR(1) 的文法来解析词法分析过程中输出的 Token 序列。LALR(1) 是自底向上的分析方法，是因为版本的原因吗？请问您这是哪个版本的？盼回复

[ClearLovePlus]

谁来解析词法分析器自己本身呢？通过c去解析本身吗？

[draveness]

@ClearLovePlus 谁来解析词法分析器自己本身呢？通过c去解析本身吗？

你的这个问题跟自举有关系，可以看看

[liuqin19980818]

(σﾟ∀ﾟ)σ哇!有一点不太懂,这个simplego.l是怎么来的?是helloworld.go先用什么工具转换成simplego.l之后再用lex分析的吗?

[jiang4869]

SourceFile = PackageClause ";" { ImportDecl ";" } { TopLevelDecl ";" } . 想问一下在这个文法中，{}这个大括号表示是什么意思？是不是说大括号内的文法是可选的？