KusonStack一站式可编程配置技术栈(Go): https://github.com/KusionStack/kusion
KCL 配置编程语言(Rust): https://github.com/KusionStack/KCLVM
凹语言™: https://github.com/wa-lang/wa

3.1 AST视角的µGo程序

最小的µGo程序虽然只有一个函数，函数中只有一个exit函数调用，但是已经是具有一个完整的程序的基本结构。本节我们将从AST角度分析最小µGo程序的结构，AST相关的代码在ast子包定义。

3.1.1 最小µGo程序

最小µGo程序代码如下：

package main

func main() {
	exit(40+2) // 退出码 42
}

3.1.2 Package信息

为了减少干扰，我们先排除全部的注释信息。有含义的语句首先是package main，表示这是一个main包。我们可以定义一个Package结构表示：

type Package struct {
	PkgPos  int
	NamePos int
	Name    string
}

其中PkgPos表示package关键字的位置，NamePos表示包名的开始位置，Name表示包的名字。我们通过在Package结构定义关键元素的值和位置信息，就可以精确表示文本格式的µGo程序（或则说可以轻松将ast.Package这个结构原样恢复出原始的µGo程序，而代码和AST的双向转换正是语法解析和代码格式化的基础）。

3.1.3 函数定义

然后是函数的表示：这个最小程序虽然只有一个main函数，但是正常的µGo程序可以定义很多个函数。。我们现在尝试定义一个可以表示函数AST的Func结构：

type Func struct {
	FuncPos int
	NamePos int
	Name    string
	Body    *BlockStmt
}

其中FuncPos和NamePos分别是func关键字和函数名字的开始位置，Name表示函数的名字（同样为了简单，我们忽略函数的参数和返回值信息，也忽略了小括弧的位置信息），然后BlockStmt类型的Body表示函数体内的语句。

3.1.4 块语句

目前函数虽然只有一个exit(40+2)语句，但是真实的µGo程序同样可以包含多个不同类型的语句。语句大约可以看作是分号分隔的、相同层级、顺序执行的代码。上面代码出现的BlockStmt就表示一个块语句，一个块语句是大括弧包含的语句序列。BlockStmt定义如下：

type BlockStmt struct {
	Lbrace int // '{'
	List   []Stmt
	Rbrace int // '}'
}

其中Lbrace和Rbrace是左右大括弧的位置，而List则是Stmt接口表示的语句列表。因为µGo程序中可能有变量定义、赋值、表达式、if、for、return等不同类型的语句，因此我们需要定义一个Stmt类型的接口来表示语句：

type Stmt interface {
	Pos() int
	End() int
	stmt_type()
}

语句也有一些共性的方法，其中Pos和End返回语句的开始和结束位置，对应一个语句代码的区间。同时为了区分Stmt和其他类型，我们定义了一个stmt_type私有方法。

3.1.5 表达式语句

光有Stmt接口我们依然无法表示目前的最小µGo程序。我们还需要为表达式语句定义一个ExprStmt结构：

type ExprStmt struct {
	X Expr
}

type Expr interface {
	Pos() int
	End() int
	expr_type()
}

ExprStmt结构中只有一个X成员，表示一个Expr类型的表达式（表达式可以产生值，也可能没有值，比如一个没有返回值的函数调用）。而Expr是与Stmt类似的接口，用于表示具体的表达式的构成。

3.1.6 四则运算表达式结构

在表达式一章我们已经通过一个简化的ExprNode节点表示全部的一元和二元表达式。但是目前的最小µGo程序出现了新的表达式结构：函数调用。因此，我们需要为表达式定义更为友好的结构：

type Number struct {
	ValuePos int
	ValueEnd int
	Value    int
}

type BinaryExpr struct {
	Op token.Token // 运算符
	X  Expr        // 左边的运算对象
	Y  Expr        // 右边的运算对象
}

type UnaryExpr struct {
	Op    token.Token // 运算符
	X     Expr        // 运算对象
}

type ParenExpr struct {
	Lparen int  // "(" 的位置
	X      Expr // 圆括弧内的表达式对象
	Rparen int  // ")" 的位置
}

其中Number表示一个普通的整数字面值、BinaryExpr表示二元表达式、UnaryExpr表示一元表达式、ParenExpr表示小括弧表达式。其中递归的表达式定义都是Expr类型，其他属性则是运算符类型和位置信息等。需要注意到是token.Token是一个词法记号值，其中不仅仅包含记号的类型和字面值，还包含记号的位置信息（在稍后的词法分析部分会继续讨论）。

3.1.7 函数调用表达式

函数调用表达式定义如下：

type CallExpr struct {
	FuncPos  int
	FuncName string
	Lparen   int
	Args     []Expr
	Rparen   int
}

FuncPos和FuncName是调用函数的名字和位置信息，Lparen和Rparen是小括弧位置，Args则是函数的参数表达式列表。

3.1.8 File结构

最小µGo程序的全部元素以已经定义，我们现在定义一个File结构表示一个文件：

type File struct {
	Pkg   *Package
	Funcs []Func
}

其中Pkg表示包信息，Funcs则表示文件中顺序出现的函数列表。

3.1.9 AST表示的µGo程序

现在我们尝试通过AST表示µGo程序（为了方便表示，我们暂时忽略位置信息）：

import "github.com/wa-lang/ugo/ast"
import "github.com/wa-lang/ugo/token"

var ugoProg = &ast.File {
	Pkg: &ast.Package{
		Name: "main",
	},
	Funcs: []ast.Func{
		{
			Name: "main",
			Body: &ast.BlockStmt {
				List: []ast.Stmt{
					&ast.ExprStmt{
						X: &ast.CallExpr{
							FuncName: "exit",
							Args: []ast.Expr{
								&ast.BinaryExpr{
									Op: token.Token{Type: token.ADD},
									X:  &ast.Number{Value: 40},
									Y:  &ast.Number{Value: 2},
								},
							},
						},
					},
				},
			},
		},
	},
}

这样我们就得到了一个全新形式表示的µGo程序。

3.1.10 小结

AST是编译器前后端链接的纽带：AST虽然看起来繁琐，但是结构非常清晰，非常适合程序处理。有了AST之后我们不仅仅可以进行语义检查、编译到汇编代码、也可以进行AST结构转换和代码格式化等很多工作。在本章稍后，我们将围绕AST明确token包的结构、讨论如何遍历AST、以及如何从AST输出LLVM汇编代码。

µGo语言实现