- KusonStack一站式可编程配置技术栈(Go): https://github.com/KusionStack/kusion
- KCL 配置编程语言(Rust): https://github.com/KusionStack/KCLVM
- 凹语言™: https://github.com/wa-lang/wa
3.5 打印AST语法树
我们已经实现了µGo程序的语法树解析，为了方便调试我们经常需要打印语法树。本节将为语法树实现格式化打印支持。
3.5.1 打印JSON
最简单的打印AST方式是输出JSON格式，为ast.File增加JSONString方法如下：
package ast
func (p *File) JSONString() string {
file := *p
if len(file.Source) > 8 {
file.Source = file.Source[:8] + "..."
}
d, _ := json.MarshalIndent(&file, "", " ")
return string(d)
}
为了减少ast.File.Source的干扰，当µGo源代码较长时用省略号表示。然后通过json.MarshalIndent打印缩进格式的JSON。
构造测试函数：
func main() {
code := loadCode("../hello.ugo")
f, err := parser.ParseFile("../hello.ugo", code)
if err != nil {
panic(err)
}
fmt.Println(f.JSONString())
}
func loadCode(filename string) string {
data, err := os.ReadFile(filename)
if err != nil {
panic(err)
}
return string(data)
}
输入JSON如下：
{
"Filename": "../hello.ugo",
"Source": "package ...",
"Pkg": {
"PkgPos": 1,
"NamePos": 9,
"Name": "main"
},
"Funcs": [
{
"FuncPos": 15,
"NamePos": 20,
"Name": "main",
"Body": {
"Lbrace": 27,
"List": [
{
"X": {
"FuncName": "exit",
"Lparen": 34,
"Args": [
{
"OpPos": 38,
"Op": 7,
"X": {
"ValuePos": 35,
"ValueEnd": 37,
"Value": 40
},
"Y": {
"ValuePos": 40,
"ValueEnd": 41,
"Value": 2
}
}
],
"Rparen": 41
}
}
],
"Rbrace": 59
}
}
]
}
JSON数据忠实地反映了AST中的数据。但是JSON丢失了AST成员的类型信息，同时Pos显示为数字不够直观。因此JSON更适合程序之间交换数据，对于调试AST需求JSON依然不够直观。
3.5.2 打印 Pos
为了更好地展示 Pos 信息，我们新定义 token.Pos 类型：
package token
// Pos 类似一个指针, 表示文件中的位置.
type Pos int
// NoPos 类似指针的 nil 值, 表示一个无效的位置.
const NoPos Pos = 0
func (p Pos) IsValid() bool { return p != NoPos }
Pos 是基于 int 类型定义的新类型，类似一种抽象的指针，用于表示文件中的位置偏移量。其中 NoPos 对应 0 表示一个无效的地址（类似一个nil指针），因此有效的 Pos 是从1开始的。
同时增加一个 Position 表示基于行列号的位置信息：
type Position struct {
Filename string // 文件名
Offset int // 偏移量, 从 0 开始
Line int // 行号, 从 1 开始
Column int // 列号, 从 1 开始
}
结合源代码可以将Pos转换行列号的Position结构：
func (pos Pos) Position(filename, src string) Position {
var p = Position{
Filename: filename,
Offset: int(pos) - 1,
Line: 1,
Column: 1,
}
for _, c := range []byte(src[:p.Offset]) {
p.Column++
if c == '\n' {
p.Column = 1
p.Line++
}
}
return p
}
Position结果有自己的String方法：
func (pos Position) String() string {
s := pos.Filename
if pos.IsValid() {
if s != "" {
s += ":"
}
s += fmt.Sprintf("%d", pos.Line)
if pos.Column != 0 {
s += fmt.Sprintf(":%d", pos.Column)
}
}
if s == "" {
s = "-"
}
return s
}
对应以下几种输出格式：
// file:line:column valid position with file name
// file:line valid position with file name but no column (column == 0)
// line:column valid position without file name
// line valid position without file name and no column (column == 0)
// file invalid position with file name
// - invalid position without file name
在VSCode等环境中，可以根据file:line:column格式的位置直接跳转到对应的位置，这样可以极大提高调试的效率。
3.5.3 改造AST
首先改造AST结构，将其中的token.Token类型改造为token.TokenType和token.Pos表示。目前只有一元和二元表达式需要改造：
type BinaryExpr struct {
Op token.Token // 运算符
X Expr // 左边的运算对象
Y Expr // 右边的运算对象
}
type UnaryExpr struct {
Op token.Token // 运算符
X Expr // 运算对象
}
改造后如下：
type BinaryExpr struct {
OpPos token.Pos // 运算符位置
Op token.TokenType // 运算符类型
X Expr // 左边的运算对象
Y Expr // 右边的运算对象
}
// UnaryExpr 表示一个一元表达式.
type UnaryExpr struct {
OpPos token.Pos // 运算符位置
Op token.TokenType // 运算符类型
X Expr // 运算对象
}
其次将之前用int类型表示的Pos成员改造为token.Pos类型。这类需要改造的地方比较多，但是改造的工作是类似的。比如表示数字面值的Number改造后如下：
type Number struct {
ValuePos token.Pos
ValueEnd token.Pos
Value int
}
此外为了方便跟踪函数名和变量名等标识符，我们新增加了ast.Ident结构：
type Ident struct {
NamePos token.Pos
Name string
}
函数调用ast.CallExpr中的FuncName成员就可以用ast.Ident指针表示了：
type CallExpr struct {
FuncName *Ident // 函数名字
Lparen token.Pos // '(' 位置
Args []Expr // 调用参数列表
Rparen token.Pos // ')' 位置
}
AST结构发生变化后，parser包也需要做相应的更新，这类不再详细展开。
3.5.4 AST打印
AST语法树中结点类型是固定的，我们可以根据不同的类型分别定制打印。不过打印函数一般只用作调试场景，我们也可以基于反射简化打印的工作。先定义一个内部的printer打印对象：
type printer struct {
output io.Writer
filename string
source string
ptrmap map[interface{}]int
indent int
}
其中output是打印的目标流，filename和source将节点的Pos信息翻译为行列号（如果缺失则忽略位置信息），ptrmap用于处理内部相互引用的对象（目前还没有这种），indent用于控制缩进。
然后基于反射提供一个打印的方法：
func (p *printer) print(x reflect.Value) {
switch x.Kind() {
case reflect.Interface:
p.print(x.Elem())
case reflect.Map:
// TODO
case reflect.Ptr:
// TODO
case reflect.Array:
// TODO
case reflect.Slice:
// TODO
case reflect.Struct:
// TODO
default:
// TODO
}
}
如果是接口则直接递归调用print方法打印对应的元素，其他map、指针、数组、切片、结构等也分开处理即可。
map的打印如下：
case reflect.Map:
p.printf("%s (len = %d) {", x.Type(), x.Len())
if x.Len() > 0 {
p.indent++
p.printf("\n")
for _, key := range x.MapKeys() {
p.print(key)
p.printf(": ")
p.print(x.MapIndex(key))
p.printf("\n")
}
p.indent--
}
p.printf("}")
p.printf是打印对象包装的格式化打印函数，然后控制缩进并打印map的key-value对。
指针类型打印方式如下：
case reflect.Ptr:
p.printf("*")
ptr := x.Interface()
if line, exists := p.ptrmap[ptr]; exists {
p.printf("(obj @ %d)", line)
} else {
p.ptrmap[ptr] = p.line
p.print(x.Elem())
}
其中关键点是需要记录制作到p.ptrmap中，如果第一次出现则打印，否则打印引用第一次打印该对象的行号。
数组和切片的打印方式类似：
case reflect.Array:
p.printf("%s {", x.Type())
if x.Len() > 0 {
p.indent++
p.printf("\n")
for i, n := 0, x.Len(); i < n; i++ {
p.printf("%d: ", i)
p.print(x.Index(i))
p.printf("\n")
}
p.indent--
}
p.printf("}")
case reflect.Slice:
if s, ok := x.Interface().([]byte); ok {
p.printf("%#q", s)
return
}
p.printf("%s (len = %d) {", x.Type(), x.Len())
if x.Len() > 0 {
p.indent++
p.printf("\n")
for i, n := 0, x.Len(); i < n; i++ {
p.printf("%d: ", i)
p.print(x.Index(i))
p.printf("\n")
}
p.indent--
}
p.printf("}")
切片打印的类型包含了长度信息，同时对字节切片做了一定特花处理。然后控制缩进打印数组或切片的元素。
最重要的是结构体的打印：
case reflect.Struct:
t := x.Type()
p.printf("%s {", t)
p.indent++
first := true
for i, n := 0, t.NumField(); i < n; i++ {
name := t.Field(i).Name
value := x.Field(i)
if p.notNilFilter(name, value) {
if first {
p.printf("\n")
first = false
}
p.printf("%s: ", name)
p.print(value)
p.printf("\n")
}
}
p.indent--
p.printf("}")
遍历结构体的成员，然后和map类似的方式打印其中内容。为了减少语法树中空指针的影响，通过p.notNilFilter做了简单的过滤，其实现如下：
func (p *printer) notNilFilter(_name string, v reflect.Value) bool {
switch v.Kind() {
case reflect.Chan, reflect.Func, reflect.Interface, reflect.Map, reflect.Ptr, reflect.Slice:
return !v.IsNil()
}
return true
}
最后是defaul分支的打印：
default:
v := x.Interface()
switch v := v.(type) {
case string:
// print strings in quotes
p.printf("%q", v)
return
case token.Pos:
if p.filename != "" && p.source != "" {
p.printf("%s", v.Position(p.filename, p.source))
return
}
}
// default
p.printf("%v", v)
}
对应字符串和Pos做了特殊的格式化处理。
3.5.5 包装打印函数
包装一个Print打印函数，打印任意的语法树结点
func Fprint(w io.Writer, filename, source string, node Node) {
fprint(w, filename, source, node)
}
func fprint(w io.Writer, filename, source string, x interface{}) (err error) {
p := printer{
output: w,
filename: filename,
source: source,
ptrmap: make(map[interface{}]int),
last: '\n', // force printing of line number on first line
}
// print x
if x == nil {
p.printf("nil\n")
return
}
p.print(reflect.ValueOf(x))
p.printf("\n")
return
}
并为File包装一个String方法：
func (p *File) String() string {
var buf bytes.Buffer
Fprint(&buf, p.Filename, p.Source, p)
return buf.String()
}
3.5.6 测试打印效果
现在可以用fmt.Println(f.String())打印文件，输出结果如下：
0 ast.File {
1 . Filename: "../hello.ugo"
2 . Source: "package ..."
3 . Pkg: *ast.Package {
4 . . PkgPos: ../hello.ugo:1:1
5 . . NamePos: ../hello.ugo:1:9
6 . . Name: "main"
7 . }
8 . Funcs: []*ast.Func (len = 1) {
9 . . 0: *ast.Func {
10 . . . FuncPos: ../hello.ugo:3:1
11 . . . NamePos: ../hello.ugo:3:6
12 . . . Name: "main"
13 . . . Body: *ast.BlockStmt {
14 . . . . Lbrace: ../hello.ugo:3:13
15 . . . . List: []ast.Stmt (len = 1) {
16 . . . . . 0: *ast.ExprStmt {
17 . . . . . . X: *ast.CallExpr {
18 . . . . . . . FuncName: *ast.Ident {
19 . . . . . . . . NamePos: ../hello.ugo:4:2
20 . . . . . . . . Name: "exit"
21 . . . . . . . }
22 . . . . . . . Lparen: ../hello.ugo:4:6
23 . . . . . . . Args: []ast.Expr (len = 1) {
24 . . . . . . . . 0: *ast.BinaryExpr {
25 . . . . . . . . . OpPos: ../hello.ugo:4:10
26 . . . . . . . . . Op: +
27 . . . . . . . . . X: *ast.Number {
28 . . . . . . . . . . ValuePos: ../hello.ugo:4:7
29 . . . . . . . . . . ValueEnd: ../hello.ugo:4:9
30 . . . . . . . . . . Value: 40
31 . . . . . . . . . }
32 . . . . . . . . . Y: *ast.Number {
33 . . . . . . . . . . ValuePos: ../hello.ugo:4:12
34 . . . . . . . . . . ValueEnd: ../hello.ugo:4:13
35 . . . . . . . . . . Value: 2
36 . . . . . . . . . }
37 . . . . . . . . }
38 . . . . . . . }
39 . . . . . . . Rparen: ../hello.ugo:4:13
40 . . . . . . }
41 . . . . . }
42 . . . . }
43 . . . . Rbrace: ../hello.ugo:5:1
44 . . . }
45 . . }
46 . }
47 }