0%

语法分析

完善 switch 语句:

1
2
3
4
5
6
stm: ......
| 'switch' '(' expr ')' '{' case* default? '}'
......

case : 'case' expr ':' (stm ';'?)*;
default: 'default' ':' (stm ';'?)*;

核心代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
if str_1 == "switch" {
var key bool = false
vaule, _ := h.handExpr(stm.GetChild(2).(*Jsp.ExprContext))
for i := 0; i < stm.GetChildCount()-7; i++ {
num, _ := h.handExpr(stm.GetChild(i + 5).GetChild(1).(*Jsp.ExprContext))
if num.getString() == vaule.getString() || key {
key = true
if h.isBreak {
h.isBreak = false
break
}
for y := 0; y < stm.GetChild(i+5).GetChildCount()-2; y++ {
if stm.GetChild(i+5).GetChild(y+2).GetChild(0) != nil {
h.handStm(stm.GetChild(i + 5).GetChild(y + 2).(*Jsp.StmContext))
}
}
}
}
if !key {
for y := 0; y < stm.GetChild(stm.GetChildCount()-2).GetChildCount(); y++ {
if stm.GetChild(stm.GetChildCount()-2).GetChild(y).GetChild(0) != nil {
h.handStm(stm.GetChild(stm.GetChildCount() - 2).GetChild(y).(*Jsp.StmContext))
}
}
}
}

为了使 switch 语句成立,这里添加了 break continue 语句的实现:

1
2
3
4
5
6
7
8
if str_1 == "break" {
h.isBreak = true
return nil, 0
}
if str_1 == "continue" {
h.isContinue = true
return nil, 0
}
  • 另外在 for 语句和 while 语句中也添加了对 break continue 的处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
if str_1 == "while" {
for {
if h.isBreak {
h.isBreak = false
break
}
if h.isContinue {
h.isContinue = false
continue
}
vaule, typ := h.handExpr(stm.GetChild(2).(*Jsp.ExprContext))
if ok := h.checkExpr(vaule, typ); !ok {
break
}
h.handBlock(stm.GetChild(4).(*Jsp.BlockContext))
}
}
if str_1 == "for" {
var smts [3]*Jsp.StmContext
var index int = 0
for _, c := range stm.GetChildren() {
_, ok := c.(*Jsp.StmContext)
if tmp := fmt.Sprintf("%v", c); tmp == ";" {
index++
}
if c.GetChild(0) != nil && ok {
smts[index] = c.(*Jsp.StmContext)
}
}
if smts[0] != nil {
h.handStm(smts[0])
}
for {
if h.isBreak {
h.isBreak = false
break
}
if h.isContinue {
h.isContinue = false
continue
}
if smts[1] != nil {
vaule, typ := h.handStm(smts[1])
if ok := h.checkExpr(vaule, typ); !ok {
break
}
}
h.handBlock(stm.GetChild(stm.GetChildCount() - 1).(*Jsp.BlockContext))
if smts[2] != nil {
h.handStm(smts[2])
}
}
}

Class 的实现

对于一个类而言,需要记录的数据有:名称,变量,方法

1
2
3
4
5
type Class struct {
name string
vars []string
funcs map[string]*Fuction
}

将 Class 添加到 SymTable 中:

1
2
3
4
5
6
type SymTable struct {
Fuctions []Fuction
Classes []*Class
InFuctions inFunction
scope *Scope
}
  • 附加的内置函数如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
func NewClass(name string) *Class {
return &Class{name: name,
vars: []string{},
funcs: map[string]*Fuction{},
}
}

func (vl *SymTable) getClass(name string) (*Class, bool) {
for _, c := range vl.Classes {
if name == c.name {
return c, true
}
}
return nil, false
}

func (vl *SymTable) addClass(class *Class) {
vl.Classes = append(vl.Classes, class)
}

func (c *Class) addVar(name string) {
c.vars = append(c.vars, name)
}

func (c *Class) initFunc(m *Jsp.ConsContext) { /* 处理构造函数 */
currentT := current
defer func() {
current = currentT
}()

name := fmt.Sprintf("%v", m.GetChild(0))
current = name

params := m.GetChild(2)
var args []string
for _, param := range params.GetChildren() {
if param.GetChild(0) != nil {
arg := fmt.Sprintf("%v", param.GetChild(0))
args = append(args, arg)
}
}
method := NewFunction(name, args, m.GetChild(4).(*Jsp.BlockContext))
c.funcs[name] = method
}

func (c *Class) addFunc(m *Jsp.MethodContext) { /* 处理内置函数 */
currentT := current
defer func() {
current = currentT
}()

name := fmt.Sprintf("%v", m.GetChild(0))
current = name

params := m.GetChild(2)
var args []string
for _, param := range params.GetChildren() {
if param.GetChild(0) != nil {
arg := fmt.Sprintf("%v", param.GetChild(0))
args = append(args, arg)
}
}
method := NewFunction(name, args, m.GetChild(4).(*Jsp.BlockContext))
c.funcs[name] = method
}

func (c *Class) getFunc(name string) (*Fuction, bool) {
if _, ok := c.funcs[name]; ok {
return c.funcs[name], true
}
return nil, false
}

在基础类型对象的处理中添加 class object:

1
2
3
4
5
type CobjObject struct {
BaseObject
ClassName string
Value map[string]BaseObject
}
  • 附加的内置函数如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func (o *CobjObject) getString() string {
str := "{"
for k, v := range o.Value {
str += fmt.Sprintf(" %s:%s,", k, v.getString())
}
str = str[:len(str)-1] + " }"

return str
}

func (o *CobjObject) addValue(name string, obj BaseObject) {
o.Value[name] = obj
}

func (o *CobjObject) setValue(name string, obj BaseObject) {
for i, _ := range o.Value {
if i == name {
o.Value[i] = obj
}
}
}

添加 class 的语法:

1
2
3
class: 'class' IDENTIFIER '{' cons? method* '}';
cons: 'constructor' '(' paramlist? ')' block;
method: IDENTIFIER '(' paramlist? ')' block;

在 listener 中添加对 class 的处理:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func (l *MyListener) EnterClass(ctx *Jsp.ClassContext) {
name := fmt.Sprintf("%v", ctx.GetChild(1))
class := NewClass(name)

for _, c := range ctx.GetChildren() {
if con, ok := c.(*Jsp.ConsContext); ok {
class.initFunc(con)
}
if met, ok := c.(*Jsp.MethodContext); ok {
class.addFunc(met)
}
}
vl.addClass(class)
}

在 handExpr 中添加对于 this 和 class object 的处理:

1
2
3
4
5
6
7
if _, ok := exp.GetChild(0).(*Jsp.ThisContext); ok { // this
return &ThisObjetc{}, Jsp.JavaScriptParserRULE_this
}

if cobj, ok := exp.GetChild(0).(*Jsp.CobjContext); ok { // class object
return h.handExpr_cobj(cobj) /* 核心函数 */
}

另外在 handExpr 中处理 expr '.' expr 时添加对应的处理:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
} else if obj, ok := exp1.(*CobjObject); ok { // class object
if obj.Value[name2] != nil {
obj.setValue(name1, obj.Value[name2])
str := fmt.Sprintf("%v", obj.Value[name2].getString())
if str[0] == '"' {
return obj.Value[name2], Jsp.JavaScriptLexerSTRING
}
if renum.MatchString(str) {
return obj.Value[name2], Jsp.JavaScriptLexerNUMBER
}
return obj.Value[name2], -1
} else {
var args []Variant
cname := obj.ClassName

if call, ok := exp.GetChild(2).GetChild(0).(*Jsp.FuncallContext); ok {
for _, c := range call.GetChild(2).GetChildren() {
if c.GetChild(0) != nil {
value, typ := h.handExpr(c.(*Jsp.ExprContext))
args = append(args, *NewVariant("unknown", value, typ))
}
}
}
if class, ok := vl.getClass(cname); ok {
value, typ := h.handMethod(obj, class, name2, args)
return value, typ
}
return nil, -1
}
} else if this, ok := exp1.(*ThisObjetc); ok { // this
this.setValue(name2)
this.setObject(exp2)
return this, Jsp.JavaScriptParserRULE_this

核心函数 handExpr_cobj 的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func (h *Handler) handExpr_cobj(new *Jsp.CobjContext) (BaseObject, int) {
var args []Variant
cname := fmt.Sprintf("%s", new.GetChild(1))
cobjt := &CobjObject{Value: make(map[string]BaseObject), ClassName: cname}

if class, ok := vl.getClass(cname); ok {
for _, o := range new.GetChild(3).GetChildren() {
if o.GetChild(0) != nil {
value, typ := h.handExpr(o.(*Jsp.ExprContext))
args = append(args, Variant{"unknown", value, typ})
}
}
h.handMethod(cobjt, class, "constructor", args)
}

return cobjt, Jsp.JavaScriptParserRULE_cobj
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func (h *Handler) handMethod(cobjt *CobjObject, c *Class, name string, args []Variant) (BaseObject, int) {
currentT := current
defer func() {
vl.delVarAll()
current = currentT
}()
current = name
fun, _ := c.getFunc(name)

if len(fun.args) != len(args) {
panic("The parameters do not match")
} else {
for i, param := range fun.args {
value, typ := args[i].value, args[i].typ
vl.addVar(param, value, typ)
}
}

block := fun.fctx
for _, c := range block.GetChildren() {
if h.isBreak {
break
}
if h.isContinue {
continue
}
if c.GetChild(0) != nil {
value, typ := h.handStm(c.(*Jsp.StmContext))
if this, ok := value.(*ThisObjetc); ok {
cobjt.addValue(this.Value, this.Object)
}
if h.isReturn {
return value, typ
}
}
}

return nil, -1
}

重构基础类型

之前所有的类型都是用 string 记录:

1
2
3
4
5
type Variant struct {
name string
value string
typ int
}

JavaScript 一切皆对象,这里选择为各个基础对象添加对应的结构体:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
type BaseObject interface {
getString() string
}

type UndefObject struct {
BaseObject
Value string
}

type StringObject struct {
BaseObject
Value string
}

type NumberObject struct {
BaseObject
Value int
}

type BooleanObject struct {
BaseObject
Value bool
}

type ArrayObject struct {
BaseObject
Value []BaseObject
}

type ObjObject struct {
BaseObject
Value map[string]BaseObject
}

type VariantObject struct {
BaseObject
Value string
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
func (n *UndefObject) getString() string {
return "undefined"
}

func (s *StringObject) getString() string {
return s.Value
}

func (n *NumberObject) getString() string {
return fmt.Sprintf("%d", n.Value)
}

func (b *BooleanObject) getString() string {
if b.Value {
return "true"
}
return "false"
}

func (a *ArrayObject) getString() string {
str := "["
for _, n := range a.Value {
str += fmt.Sprintf(" %v,", n.getString())
}
str = str[:len(str)-1] + " ]"

return str
}

func (a *ArrayObject) setValue(num BaseObject) {
a.Value = append(a.Value, num)
}

func (a *ArrayObject) getValue(index int) BaseObject {
return a.Value[index]
}

func (o *ObjObject) getString() string {
str := "{"
for k, v := range o.Value {
str += fmt.Sprintf(" %s:%s,", k, v.getString())
}
str = str[:len(str)-1] + " }"

return str
}

func (o *ObjObject) addValue(name string, obj BaseObject) {
o.Value[name] = obj
}

func (o *ObjObject) setValue(name string, obj BaseObject) {
for i, _ := range o.Value {
if i == name {
o.Value[i] = obj
}
}
}

func (v *VariantObject) getString() string {
return v.Value
}

记录基础类型的结构体改变以后,许多地方的代码都要重构

首先是 handExpr 中对二元运算符的处理:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
op := fmt.Sprintf("%v", exp.GetChild(1))
exp1, typ1 := handExpr(exp.GetChild(0).(*Jsp.ExprContext))
exp2, typ2 := handExpr(exp.GetChild(2).(*Jsp.ExprContext))

......

if op == "+" {
if typ1 == Jsp.JavaScriptLexerNUMBER && typ2 == Jsp.JavaScriptLexerNUMBER {
num1, _ := strconv.Atoi(exp1.getString())
num2, _ := strconv.Atoi(exp2.getString())
return &NumberObject{Value: num1 + num2}, Jsp.JavaScriptLexerNUMBER
} else if typ1 == Jsp.JavaScriptLexerSTRING || typ2 == Jsp.JavaScriptLexerSTRING {
return &StringObject{Value: exp1.getString() + exp2.getString()}, Jsp.JavaScriptLexerSTRING
} else {
return nil, -1
}
}

......

if op == ">" {
if typ1 == Jsp.JavaScriptLexerNUMBER && typ2 == Jsp.JavaScriptLexerNUMBER {
num1, _ := strconv.Atoi(exp1.getString())
num2, _ := strconv.Atoi(exp2.getString())
return &BooleanObject{Value: num1 > num2}, Jsp.JavaScriptLexerNUMBER
} else {
return nil, -1
}
}

......

handExpr 中对一元运算符的处理:

1
2
3
4
5
6
7
8
9
10
11
if op == "++" {
if typ1 == Jsp.JavaScriptLexerNUMBER {
num1, _ := strconv.Atoi(exp1.getString())
num := &NumberObject{Value: num1 + 1}
name := fmt.Sprintf("%v", exp.GetChild(0).GetChild(0).GetChild(0))
vl.setVar(name, num, Jsp.JavaScriptLexerNUMBER)
return num, Jsp.JavaScriptLexerNUMBER
} else {
return nil, -1
}
}

handExpr 中对原始数据类型的处理:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
if exp.GetChildCount() == 1 { // funcall | num | id | str | arr | obj
if call, ok := exp.GetChild(0).(*Jsp.FuncallContext); ok {
return handExpr_funcall(call)
} else if arr, ok := exp.GetChild(0).(*Jsp.ArrContext); ok {
arrt := &ArrayObject{Value: make([]BaseObject, 0)}
for _, a := range arr.GetChildren() {
if a.GetChild(0) != nil {
num, _ := strconv.Atoi(fmt.Sprintf("%v", a.GetChild(0).GetChild(0)))
arrt.setValue(&NumberObject{Value: num})
}
}
return arrt, Jsp.JavaScriptParserRULE_arr
} else if obj, ok := exp.GetChild(0).(*Jsp.ObjContext); ok { // object
objt := &ObjObject{Value: make(map[string]BaseObject)}
for _, o := range obj.GetChildren() {
if o.GetChild(0) != nil {
name := fmt.Sprintf("%v", o.GetChild(0).GetChild(0))
value, _ := handExpr(o.GetChild(2).(*Jsp.ExprContext))
objt.addValue(name, value)
}
}
return objt, Jsp.JavaScriptParserRULE_obj
} else {
renum := regexp.MustCompile(`^\d+$`)
resym := regexp.MustCompile(`^[a-zA-Z_][a-zA-Z0-9_]*$`)
str := fmt.Sprintf("%v", exp.GetChild(0).GetChild(0))
if str[0] == '"' { // string
return &StringObject{Value: str}, Jsp.JavaScriptLexerSTRING
}
if renum.MatchString(str) { // number
num, _ := strconv.Atoi(str)
return &NumberObject{Value: num}, Jsp.JavaScriptLexerNUMBER
}
if resym.MatchString(str) { // var
value, typ := vl.getVarByName(str)
return value, typ
}
}
}

最后则是对数组与对象的处理:

1
2
3
4
5
6
7
8
9
10
if op == "." { // expr '.' expr
name1 := fmt.Sprintf("%v", exp.GetChild(0).GetChild(0).GetChild(0))
name2 := fmt.Sprintf("%v", exp.GetChild(2).GetChild(0).GetChild(0))
if obj, ok := exp1.(*ObjObject); ok {
obj.setValue(name1, obj.Value[name2])
return obj.Value[name2], typ
} else {
panic("Object syntax error")
}
}
1
2
3
4
5
6
7
8
9
10
11
if exp.GetChildCount() == 4 { // expr '[' expr ']'
index, _ := handExpr(exp.GetChild(2).(*Jsp.ExprContext))
exp, typ := handExpr(exp.GetChild(0).(*Jsp.ExprContext))

if arr, ok := exp.(*ArrayObject); ok {
i, _ := strconv.Atoi(index.getString())
return arr.getValue(i), typ
} else {
panic("Array syntax error")
}
}

重构作用域

之前对作用域的处理主要是针对函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func handFuncdef(name string, args []Variant) (BaseObject, int) {
var currentT = current
current = name
params, ctx := vl.getFunc(name)

defer func() {
vl.delVarAll() /* 清空SymTable中的函数参数 */
current = currentT
}()

if ctx == nil {
value, typ := vl.callInFunc(name, args)
return value, typ
}

if len(params) != len(args) {
panic("The parameters do not match")
} else {
for i, param := range params {
value, typ := args[i].value, args[i].typ
vl.addVar(param, value, typ) /* 将函数参数添加到SymTable中 */
}
}
block := ctx.GetChild(ctx.GetChildCount() - 1).(*Jsp.BlockContext)
revalue, retyp := handBlock(block)

return revalue, retyp
}
1
2
3
4
func (vl *SymTable) addVar(name string, value BaseObject, typ int) {
vl.Variants = append(vl.Variants, *NewVariant(current+"."+name, value, typ))
vl.setFuncByName(current, name)
}
1
2
3
4
5
6
7
8
func (vl *SymTable) delVarAll() {
for _, v := range vl.Variants {
substrs := strings.Split(v.name, ".")
if substrs[0] == current {
vl.Variants = vl.Variants[:len(vl.Variants)-1]
}
}
}
  • 这种写法有一个问题,那就是递归的函数也会被清除所有的参数,导致程序内部出错

重构后的作用域主要基于 Scope 结构体:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
type Scope struct {
Outer *Scope
Objects map[string]*Variant
}

func NewScope(outer *Scope) *Scope {
return &Scope{
Outer: outer,
Objects: make(map[string]*Variant),
}
}

func (s *Scope) HasName(name string) bool {
_, ok := s.Objects[name]
return ok
}

func (s *Scope) Lookup(name string) (*Scope, *Variant) {
for ; s != nil; s = s.Outer {
if obj := s.Objects[name]; obj != nil {
return s, obj
}
}
return nil, nil
}

func (s *Scope) Insert(v *Variant) (alt *Variant) {
if alt = s.Objects[v.name]; alt == nil {
s.Objects[v.name] = v
}
return
}

每一层作用域都可以用一个 Scope 结构体表示,可以用下面两个函数进行控制:

1
2
3
4
5
6
7
func (p *SymTable) enterScope() { /* 新建并进入下一层 */
p.scope = NewScope(p.scope)
}

func (p *SymTable) leaveScope(scope *Scope) { /* 返回上一层 */
p.scope = scope
}

基于 Scope 可以对 SymTable 中的其他函数进行重构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func (vl *SymTable) addVar(name string, value BaseObject, typ int) {
vl.scope.Insert(NewVariant(current+"."+name, value, typ))
vl.setFuncByName(current, name)
}

func (vl *SymTable) setVar(name string, value BaseObject, typ int) {
substrs := strings.Split(name, "@")
if _, obj := vl.scope.Lookup(current + "." + substrs[0]); obj != nil {
if typ == Jsp.JavaScriptParserRULE_obj {
if o, ok := obj.value.(*ObjObject); ok {
o.setValue(substrs[1], value)
}
} else {
obj.value = value
obj.typ = typ
}
} else {
panic(fmt.Sprintf("var %s undefined", name))
}
}

func (vl *SymTable) getVarByName(name string) (BaseObject, int) {
if _, obj := vl.scope.Lookup(current + "." + name); obj != nil {
return obj.value, obj.typ
}
return nil, -1
}

最后在 handBlock 中添加对 Scope 的处理即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func (h *Handler) handBlock(blo *Jsp.BlockContext) (BaseObject, int) {
defer vl.leaveScope(vl.scope)
vl.enterScope()

for _, c := range blo.GetChildren() {
if h.isBreak {
break
}
if h.isContinue {
continue
}
if c.GetChild(0) != nil {
value, typ := h.handStm(c.(*Jsp.StmContext))
if h.isReturn {
return value, typ
}
}
}

return nil, -1
}

语法分析

完善 if while for 语句:

1
2
3
| 'if' '(' expr ')' block ('else' block)?
| 'while' '(' expr ')' block
| 'for' '(' stm? ';' stm? ';' stm? ')' block

对应的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
if str_1 == "return" {
value, typ = handExpr(stm.GetChild(1).(*Jsp.ExprContext))
return value, typ, true
}
if str_1 == "var" {
name := fmt.Sprintf("%v", stm.GetChild(1))
str_2 = fmt.Sprintf("%v", stm.GetChild(2))
if str_2 == "=" {
vaule, typ := handExpr(stm.GetChild(3).(*Jsp.ExprContext))
vl.addVar(name, vaule, typ)
if typ == Jsp.JavaScriptParserRULE_obj {
vl.setVarAll(name)
vl.showVarAll()
}
}
vl.showVarAll()
}
if str_1 == "if" {
vaule, typ := handExpr(stm.GetChild(2).(*Jsp.ExprContext))
if ok := checkExpr(vaule, typ); ok {
handBlock(stm.GetChild(4).(*Jsp.BlockContext))
} else if stm.GetChildCount() == 6 {
handBlock(stm.GetChild(6).(*Jsp.BlockContext))
}
}
if str_1 == "while" {
for {
vaule, typ := handExpr(stm.GetChild(2).(*Jsp.ExprContext))
if ok := checkExpr(vaule, typ); !ok {
break
}
handBlock(stm.GetChild(4).(*Jsp.BlockContext))
}
}
if str_1 == "for" {
var smts [3]*Jsp.StmContext
var index int = 0

for _, c := range stm.GetChildren() {
_, ok := c.(*Jsp.StmContext)
if tmp := fmt.Sprintf("%v", c); tmp == ";" {
index++
}
if c.GetChild(0) != nil && ok {
smts[index] = c.(*Jsp.StmContext)
}
}
if smts[0] != nil {
handStm(smts[0])
}

for {
if smts[1] != nil {
vaule, typ, _ := handStm(smts[1])
if ok := checkExpr(vaule, typ); !ok {
break
}
}
handBlock(stm.GetChild(stm.GetChildCount() - 1).(*Jsp.BlockContext))
if smts[2] != nil {
handStm(smts[2])
}
}
}

为了匹配 if 语句,需要给表达式语句添加对于条件语句的处理:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
if op == ">" {
if typ1 == Jsp.JavaScriptLexerNUMBER && typ2 == Jsp.JavaScriptLexerNUMBER {
num1, _ := strconv.Atoi(exp1)
num2, _ := strconv.Atoi(exp2)
return strconv.FormatBool(num1 > num2), Jsp.JavaScriptParserRULE_bool
} else {
return "", -1
}
}
if op == ">=" {
if typ1 == Jsp.JavaScriptLexerNUMBER && typ2 == Jsp.JavaScriptLexerNUMBER {
num1, _ := strconv.Atoi(exp1)
num2, _ := strconv.Atoi(exp2)
return strconv.FormatBool(num1 >= num2), Jsp.JavaScriptParserRULE_bool
} else {
return "", -1
}
}
if op == "<" {
if typ1 == Jsp.JavaScriptLexerNUMBER && typ2 == Jsp.JavaScriptLexerNUMBER {
num1, _ := strconv.Atoi(exp1)
num2, _ := strconv.Atoi(exp2)
return strconv.FormatBool(num1 < num2), Jsp.JavaScriptParserRULE_bool
} else {
return "", -1
}
}
if op == "<=" {
if typ1 == Jsp.JavaScriptLexerNUMBER && typ2 == Jsp.JavaScriptLexerNUMBER {
num1, _ := strconv.Atoi(exp1)
num2, _ := strconv.Atoi(exp2)
return strconv.FormatBool(num1 <= num2), Jsp.JavaScriptParserRULE_bool
} else {
return "", -1
}
}
if op == "==" {
if typ1 == Jsp.JavaScriptLexerNUMBER && typ2 == Jsp.JavaScriptLexerNUMBER {
num1, _ := strconv.Atoi(exp1)
num2, _ := strconv.Atoi(exp2)
return strconv.FormatBool(num1 == num2), Jsp.JavaScriptParserRULE_bool
} else {
return "", -1
}
}
if op == "!=" {
if typ1 == Jsp.JavaScriptLexerNUMBER && typ2 == Jsp.JavaScriptLexerNUMBER {
num1, _ := strconv.Atoi(exp1)
num2, _ := strconv.Atoi(exp2)
return strconv.FormatBool(num1 != num2), Jsp.JavaScriptParserRULE_bool
} else {
return "", -1
}
}

另外还添加了对于语句块的处理:

1
2
3
4
5
6
7
8
9
10
11
func handBlock(blo *Jsp.BlockContext) (string, int) {
for _, c := range blo.GetChildren() {
if c.GetChild(0) != nil {
value, typ, ok := handStm(c.(*Jsp.StmContext))
if ok {
return value, typ
}
}
}
return "", -1
}

为了实现对象处理,我这里对许多地方进行了修改:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
if exp.GetChildCount() == 1 {
if call, ok := exp.GetChild(0).(*Jsp.FuncallContext); ok {
return handExpr_funcall(call)
} else if obj, ok := exp.GetChild(0).(*Jsp.ObjContext); ok {
for _, o := range obj.GetChildren() {
if o.GetChild(0) != nil {
name := fmt.Sprintf("%v", o.GetChild(0).GetChild(0))
value, typ := handExpr(o.GetChild(2).(*Jsp.ExprContext))
vl.addVar("*."+name, value, typ)
}
}
return "", Jsp.JavaScriptParserRULE_obj
} else {
renum := regexp.MustCompile(`^\d+$`)
resym := regexp.MustCompile(`^[a-zA-Z_][a-zA-Z0-9_]*$`)
str := fmt.Sprintf("%v", exp.GetChild(0).GetChild(0))
if str[0] == '"' {
return str, Jsp.JavaScriptLexerSTRING
}
if renum.MatchString(str) {
return str, Jsp.JavaScriptLexerNUMBER
}
if resym.MatchString(str) {
value, typ := vl.getVarByName(str)
return value, typ
}
}
}
  • 当匹配到 Jsp.ObjContext 时,程序会将该对象的各个条目装入动态符号表 SymTable,形成如下结构:
1
2
3
4
5
6
7
|----------SymTable--------------------------------------|
|name type value |
|--------------------------------------------------------|
|globol.*.type 20 "porsche" |
|globol.*.model 20 "911" |
|globol.*.color 20 "white" |
|--------------------------------------------------------|
  • 此时的对象条目并不能被直接使用,只有第一次使用该对象时才会再次进行初始化,然后形成如下结构:
1
2
3
4
5
6
7
8
|----------SymTable--------------------------------------|
|name type value |
|--------------------------------------------------------|
|globol.car.type 20 "porsche" |
|globol.car.model 20 "911" |
|globol.car.color 20 "white" |
|globol.car 5 {car} |
|--------------------------------------------------------|

对应的代码如下:

1
2
3
4
5
6
7
8
if str_2 == "=" {
vaule, typ := handExpr(stm.GetChild(3).(*Jsp.ExprContext))
vl.addVar(name, vaule, typ)
if typ == Jsp.JavaScriptParserRULE_obj {
vl.setVarAll(name)
vl.showVarAll()
}
}
  • 这样的处理保证了没有被引用的对象不会被 SymTable 使用,但同时它们也被永远遗留在了 SymTable 中
  • 其实有考虑过将 SymTable 中不使用的对象数据给清除掉,但考虑到后续可能会想到更好的处理方式,便没有写清除 SymTable 的代码

最后在表达式处理中添加了关于对象引用的代码:

1
2
3
4
5
6
if op == "." {
name1 := exp1[1 : len(exp1)-1]
name2 := fmt.Sprintf("%v", exp.GetChild(2).GetChild(0).GetChild(0))
value, typ := vl.getVarByName(name1 + op + name2)
return value, typ
}
  • 我这里直接将对象引用 . 当成了一种运算符号,然后强行合并到二元运算符的处理中
  • 这部分代码返回的上层代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
if exp1, ok := stm.GetChild(0).(*Jsp.ExprContext); ok {
value, typ = handExpr(exp1)
if str_2 == "=" {
if exp2, ok := stm.GetChild(2).(*Jsp.ExprContext); ok {
var name string
value2, typ2 := handExpr(exp2)

if exp1.GetChild(0).GetChild(0).GetChild(0) == nil {
name = fmt.Sprintf("%v", exp1.GetChild(0).GetChild(0))
} else {
name = fmt.Sprintf("%v", exp1.GetChild(0).GetChild(0).GetChild(0))
name += "."
name += fmt.Sprintf("%v", exp1.GetChild(2).GetChild(0).GetChild(0))
}
vl.setVar(name, value2, typ2)
}
}
}
  • 目前看上去有点勉强,之后会考虑优化

这是一个基于 Go 的简单 JavaScript 解释器,词法分析和语法分析都使用了 antlr4

词法分析

词法分析使用了 antlr4,脚本如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
lexer grammar JavaScriptLexer;

FUNCTION : 'function';
RETURN : 'return';
VAR : 'var';

IF : 'if';
ELSE : 'else';
WHILE : 'while';
FOR : 'for';
BREAK : 'break';
CONTINUE : 'continue';

TRUE: 'true';
FALSE: 'false';

LPAREN: '(';
RPAREN: ')';
LBRACE: '{';
RBRACE: '}';
LBRACKET: '[';
RBRACKET: ']';

NUMBER: [0-9]+('.'[0-9]+)?;
IDENTIFIER: [a-zA-Z] [a-zA-Z0-9]*;
STRING: '"' (~["\r\n] | '\\"')* '"';

COL : ':';
DOT : '.';
COMMA : ',';
SEMICOLON : ';';

ASSIGN : '=';
ADD: '+';
SUB: '-';
MUL: '*';
DIV: '/';
MOD: '%';

ADD_ASSIGN: '+=';
SUB_ASSIGN: '-=';
MUL_ASSIGN: '*=';
DIV_ASSIGN: '/=';
MOD_ASSIGN: '%=';

NOT: '!';
EQ: '==';
NEQ: '!=';
LT: '<';
GT: '>';
LTE: '<=';
GTE: '>=';

AND: '&&';
OR: '||';

WS: [ \t\r\n]+ -> skip;
COMMENT: '/*' .*? '*/' -> skip;
LINE_COMMENT: '//' ~[\r\n]* -> skip;

语法分析

语法分析使用了 antlr4,脚本如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
parser grammar JavaScriptParser;

options { tokenVocab=JavaScriptLexer; }

num : NUMBER;
id : IDENTIFIER;
str: STRING;
arr: '[' str (',' str)* ']';
key : id ':' expr;
obj: '{' key (',' key)* '}';

funcdef: 'function' IDENTIFIER '(' paramlist? ')' block;
paramlist: param (',' param)*;
param: IDENTIFIER ('=' expr)?;

funcall: IDENTIFIER '(' exprlist? ')';
exprlist: expr (',' expr)*;

program : (global)* ;

global: funcdef
| stmg
;

expr: expr ('*' | '/' | '+' | '-') expr
| expr ('<' | '>' | '==' | '<=' | '>=' | '!=') expr
| expr ('&&' | '||') expr
| '!' expr
| '-' expr
| '(' expr ')'
| id '.' funcall
| id '.' id
| funcall '.' funcall
| funcall '.' id
| funcall
| num
| id
| str
| arr
| obj
;

stmg: stm ';'?;
stm: expr ('=' | '+=' | '-=' | '*=' | '/=') expr
| 'var' IDENTIFIER ('=' expr)?
| 'return' expr
| 'break'
| 'continue'
| if
| while
| block
| expr
;

if: 'if' '(' expr ')' block ('else' block)?;
while: 'while' '(' expr ')' block;
block: '{' (stm ';'?)* '}';

语法分析

语法分析主要使用了 antlr4 中的 listener 模块,主要分析全局的函数和语句:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package listener

import (
"fmt"

Jsp "github.com/klang/js-go/JavaScript"
)

type MyListener struct {
*Jsp.BaseJavaScriptParserListener
}

func (l *MyListener) EnterProgram(ctx *Jsp.ProgramContext) {
vl = NewSymTable()
}

func (l *MyListener) EnterFuncdef(ctx *Jsp.FuncdefContext) {
var args []string
name := fmt.Sprintf("%v", ctx.GetChild(1))
for _, v := range ctx.GetChild(3).GetChildren() {
if v.GetChild(0) != nil {
args = append(args, fmt.Sprintf("%v", v.GetChild(0)))
}
}
vl.addFunc(name, args, ctx)
vl.showFuncAll()
}

func (l *MyListener) EnterStmg(ctx *Jsp.StmgContext) {
handStm(ctx.GetChild(0).(*Jsp.StmContext))
}
  • 对于函数只是简单的将其记录在 SymTable 中
  • 对于语句则需要进行详细的处理

由于 JavaScript 是解释性语言,我这里使用了一个动态变化的 SymTable 来实时记录各个变量的数据,其结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
type SymTable struct {
Variants []Variant
Fuctions []Fuction
InFuctions inFunction
}

type Variant struct {
name string
value string
typ int
}

type Fuction struct {
name string
args []string
fctx *Jsp.FuncdefContext
}

type inFunction struct {
log func(string) int
}

对应的辅助函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
func NewSymTable() *SymTable {
sym := &SymTable{
Variants: []Variant{},
Fuctions: []Fuction{},
InFuctions: inFunction{},
}
sym.initBuildInFunc()
return sym
}

func NewVariant(name string, value string, typ int) *Variant {
return &Variant{name, value, typ}
}

func (vl *SymTable) showVarAll() {
fmt.Println("|-----------------SymTable-----------------------|")
fmt.Println("|name \t\t type \t\t value \t\t |")
fmt.Println("|------------------------------------------------|")
for _, v := range vl.Variants {
fmt.Printf("|%-15v %-15v %-15v |\n", v.name, v.typ, v.value)
}
fmt.Printf("|------------------------------------------------|\n\n")
}

func (vl *SymTable) addVar(name string, value string, typ int) {
vl.Variants = append(vl.Variants, *NewVariant(name, value, typ))
}

func (vl *SymTable) getVarByName(name string) (string, int) {
for _, v := range vl.Variants {
if v.name == name {
return v.value, v.typ
}
}
return "", -1
}

func (vl *SymTable) getvarByIndex(index int) (string, int) {
return vl.Variants[index].value, vl.Variants[index].typ
}

func (vl *SymTable) getVarlen() int {
return len(vl.Variants)
}

func (vl *SymTable) delVar() {
vl.Variants = vl.Variants[:len(vl.Variants)-1]
}

func NewFunction(name string, args []string, ctx *Jsp.FuncdefContext) *Fuction {
return &Fuction{name, args, ctx}
}

func (vl *SymTable) addFunc(name string, args []string, ctx *Jsp.FuncdefContext) {
vl.Fuctions = append(vl.Fuctions, *NewFunction(name, args, ctx))
}

func (vl *SymTable) getFunc(name string) ([]string, *Jsp.FuncdefContext) {
for _, f := range vl.Fuctions {
if f.name == name {
return f.args, f.fctx
}
}
return nil, nil
}

func (vl *SymTable) showFuncAll() {
fmt.Println("|----------Function--------------|")
fmt.Println("|name \t\t args \t\t |")
for _, v := range vl.Fuctions {
fmt.Printf("|%-15v[ ", v.name)
for _, a := range v.args {
fmt.Printf("%v ", a)
}
fmt.Println("]")
}
fmt.Printf("|--------------------------------|\n\n")
}

func (vl *SymTable) initBuildInFunc() {
vl.InFuctions.log = func(msg string) int {
fmt.Printf("[+]log: %v\n", msg)
return 0
}
}

func (vl *SymTable) callInFunc(name string, args []Variant) string {
if name == "log" {
vl.InFuctions.log(args[0].value)
}
return ""
}

负责处理语句的函数为 handStm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func handStm(stm *Jsp.StmContext) (string, int, bool) {
str_1 := fmt.Sprintf("%v", stm.GetChild(0))
if str_1 == "return" {
value, typ := handExpr(stm.GetChild(1).(*Jsp.ExprContext))
return value, typ, true
}
if str_1 == "var" {
name := fmt.Sprintf("%v", stm.GetChild(1))
vaule, typ := handExpr(stm.GetChild(3).(*Jsp.ExprContext))
vl.addVar(name, vaule, typ)
vl.showVarAll()
}

if exp, ok := stm.GetChild(0).(*Jsp.ExprContext); ok {
handExpr(exp)
}

return "", -1, false
}
  • 目前只支持 return 语句,var 语句和表达式语句

其中最核心的部分就是处理表达式的函数 handExpr:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
func handExpr(exp *Jsp.ExprContext) (value string, typ int) {
if exp.GetChildCount() == 3 {
op := fmt.Sprintf("%v", exp.GetChild(1))
exp1, typ1 := handExpr(exp.GetChild(0).(*Jsp.ExprContext))
exp2, typ2 := handExpr(exp.GetChild(2).(*Jsp.ExprContext))

if op == "+" {
if typ1 == Jsp.JavaScriptParserNUMBER && typ2 == Jsp.JavaScriptParserNUMBER {
num1, _ := strconv.Atoi(exp1)
num2, _ := strconv.Atoi(exp2)
return strconv.Itoa(num1 + num2), Jsp.JavaScriptParserNUMBER
} else {
if exp1[0] == '"' {
exp1 = exp1[1 : len(exp1)-1]
}
if exp2[0] == '"' {
exp2 = exp2[1 : len(exp2)-1]
}
return "\"" + exp1 + exp2 + "\"", Jsp.JavaScriptLexerSTRING
}
}
if op == "-" {
if typ1 == Jsp.JavaScriptParserNUMBER && typ2 == Jsp.JavaScriptParserNUMBER {
num1, _ := strconv.Atoi(exp1)
num2, _ := strconv.Atoi(exp2)
return strconv.Itoa(num1 - num2), Jsp.JavaScriptParserNUMBER
} else {
return "", -1
}
}
if op == "*" {
if typ1 == Jsp.JavaScriptParserNUMBER && typ2 == Jsp.JavaScriptParserNUMBER {
num1, _ := strconv.Atoi(exp1)
num2, _ := strconv.Atoi(exp2)
return strconv.Itoa(num1 * num2), Jsp.JavaScriptParserNUMBER
} else {
return "", -1
}
}
if op == "/" {
if typ1 == Jsp.JavaScriptParserNUMBER && typ2 == Jsp.JavaScriptParserNUMBER {
num1, _ := strconv.Atoi(exp1)
num2, _ := strconv.Atoi(exp2)
return strconv.Itoa(num1 / num2), Jsp.JavaScriptParserNUMBER
} else {
return "", -1
}
}
}

if exp.GetChildCount() == 2 {
op := fmt.Sprintf("%v", exp.GetChild(0))
exp1, typ1 := handExpr(exp.GetChild(1).(*Jsp.ExprContext))

if op == "-" {
if typ1 == Jsp.JavaScriptParserNUMBER {
num1, _ := strconv.Atoi(exp1)
return strconv.Itoa(-num1), Jsp.JavaScriptParserNUMBER
} else {
return "", -1
}
}
}

if exp.GetChildCount() == 1 {
if exp.GetChild(0).GetChildCount() > 1 {
return handExpr_funcall(exp.GetChild(0).(*Jsp.FuncallContext))
} else {
renum := regexp.MustCompile(`^\d+$`)
resym := regexp.MustCompile(`^[a-zA-Z_][a-zA-Z0-9_]*$`)
str := fmt.Sprintf("%v", exp.GetChild(0).GetChild(0))
if str[0] == '"' {
return str, Jsp.JavaScriptLexerSTRING
}
if renum.MatchString(str) {
return str, Jsp.JavaScriptLexerNUMBER
}
if resym.MatchString(str) {
value, typ := vl.getVarByName(str)
return value, typ
}
}
}

return "", -1
}
  • 其中包括对二元表达式和一元表达式的处理

在表达式语句中有一个特殊的部分需要单独处理,那就是函数调用:

1
2
3
4
5
6
7
8
9
10
11
12
13
func handExpr_funcall(call *Jsp.FuncallContext) (string, int) {
var args []Variant = []Variant{}

name := fmt.Sprintf("%v", call.GetChild(0))

for _, c := range call.GetChild(2).GetChildren() {
if c.GetChild(0) != nil {
value, typ := handExpr(c.(*Jsp.ExprContext))
args = append(args, Variant{"unknown", value, typ})
}
}
return handFuncdef(name, args)
}
  • 该函数会先记录函数调用的参数,然后再进入函数定义中进行进一步的处理

处理函数定义的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func handFuncdef(name string, args []Variant) (string, int) {
var revalue string
var retyp int
params, ctx := vl.getFunc(name)
if ctx == nil {
return vl.callInFunc(name, args), -1
}

if len(params) != len(args) {
fmt.Println("errorrrr")
} else {
for i, param := range params {
value, typ := args[i].value, args[i].typ
vl.addVar(param, value, typ)
}
}

for _, c := range ctx.GetChild(ctx.GetChildCount() - 1).GetChildren() {
if c.GetChild(0) != nil {
value, typ, ok := handStm(c.(*Jsp.StmContext))
revalue, retyp = value, typ
if ok {
break
}
}
}

for i := 0; i < len(params); i++ {
vl.delVar()
}

return revalue, retyp
}
  • 先查找记录在 SymTable 中的函数,如果没有则查找内置函数

作用域处理

AST 语法树翻译到 LLVM-IR 需要处理嵌套的词法域问题,在 LLVM-IR 中,通常使用 scope 语句来处理作用域问题

作用域属于语义解析,只有 compiler 包产生 LLVM 汇编代码时需要,因此在 compiler 包定义 Scope 管理词法域:

1
2
3
4
5
6
7
8
9
10
type Scope struct {
Outer *Scope
Objects map[string]*Object
}

type Object struct {
Name string
MangledName string
ast.Node
}
  • Scope 内的 Outer 指向外层的 Scope,比如 main 函数的外层 Scope 是文件
  • Object 表示一个命名对象,其中 Name 是实体在 uGo 代码中词法域的名字,LLName 是映射到 LLVM 汇编语言的名字,其中还有指向的 AST 节点,可以用于识别更多的信息

对应的辅助函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
func NewScope(outer *Scope) *Scope {
return &Scope{
Outer: outer,
Objects: make(map[string]*Object),
}
}

func (s *Scope) HasName(name string) bool {
_, ok := s.Objects[name]
return ok
}

func (s *Scope) Lookup(name string) (*Scope, *Object) {
for ; s != nil; s = s.Outer {
if obj := s.Objects[name]; obj != nil {
return s, obj
}
}
return nil, nil
}

func (s *Scope) Insert(obj *Object) (alt *Object) {
if alt = s.Objects[obj.Name]; alt != nil {
s.Objects[obj.Name] = obj
}
return
}

func (s *Scope) String() string {
var buf bytes.Buffer
fmt.Fprintf(&buf, "scope %p", s)
if s != nil && len(s.Objects) > 0 {
fmt.Fprintln(&buf)
for _, obj := range s.Objects {
fmt.Fprintf(&buf, "\t%T %s\n", obj.Node, obj.Name)
}
}
fmt.Fprintf(&buf, "}\n")
return buf.String()
}

基于 Scope,我们可以构造出 Compiler 类用于描述编译器:

1
2
3
4
5
type Compiler struct {
file *ast.File
scope *Scope
nextId int
}

通过如下两个函数来进入和退出内层的 Scope:

1
2
3
4
5
6
7
8
9
10
11
func (p *Compiler) enterScope() {
p.scope = NewScope(p.scope)
}

func (p *Compiler) leaveScope() {
p.scope = p.scope.Outer
}

func (p *Compiler) restoreScope(scope *Scope) {
p.scope = scope
}
  • 我们需要在编译文件、块语句时进入新的 Scope,以便于存储新词法域定义的新变量

至于全局变量则在编译文件时处理,具体而言就是 compileFile 函数

翻译为 LLVM IR

接下来的工作就是把 AST 翻译为 LLVM IR(这里我把类型检查的操作提前到了语法分析中,因此不需要考虑报错检查的问题)

核心函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func (p *Compiler) genHeader(w io.Writer, file *ast.File) {
fmt.Fprintf(w, "; package %s\n", file.Pkg.Name)
fmt.Fprint(w, Header)
}

func (p *Compiler) genMain(w io.Writer, file *ast.File) {
if file.Pkg.Name != "main" {
return
}
for _, fn := range file.Funcs {
if fn.Name.Name == "main" {
fmt.Fprint(w, MainMain)
return
}
}
}

func (p *Compiler) Run(file *ast.File) string {
var buf bytes.Buffer

p.file = file

p.genHeader(&buf, file)
p.compileFile(&buf, file)
p.genMain(&buf, file)

return buf.String()
}

函数 compileFile 就是 LLVM IR 翻译的起点,其详细代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func (p *Compiler) compileFile(w io.Writer, file *ast.File) {
defer p.restoreScope(p.scope)
p.enterScope()
for _, g := range file.Globals {
var mangledName = fmt.Sprintf("@ugo_%s_%s", file.Pkg.Name, g.Name.Name)
p.scope.Insert(&Object{
Name: g.Name.Name,
MangledName: mangledName,
Node: g,
})
fmt.Fprintf(w, "%s = global i32 0\n", mangledName)
}

for _, g := range file.Funcs {
var mangledName = fmt.Sprintf("declare i32 @ugo_%s_%s", file.Pkg.Name, g.Name.Name)
p.scope.Insert(&Object{
Name: g.Name.Name,
MangledName: mangledName,
Node: g,
})
fmt.Fprintf(w, "%s(%s)\n", mangledName, p.changeType(g.Type.Name))
}

if len(file.Globals) != 0 {
fmt.Fprintln(w)
}
for _, fn := range file.Funcs {
p.compileFunc(w, file, fn)
}

p.genInit(w, file)
}
  • 在函数开始之前执行 enterScope 代表进入新的命名空间
  • 在函数结束时执行 restoreScope 退出到上一级的命名空间
  • 对于一个 ugo 代码而言,File 层就是最外层的命名空间,函数和全局变量都在此记录

下面是对函数的处理:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func (p *Compiler) compileFunc(w io.Writer, file *ast.File, fn *ast.FuncDecl) {
defer p.restoreScope(p.scope)
p.enterScope()

var mangledName = fmt.Sprintf("@ugo_%s_%s", file.Pkg.Name, fn.Name.Name)

p.scope.Insert(&Object{
Name: fn.Name.Name,
MangledName: mangledName,
Node: fn,
})

if fn.Body == nil {
fmt.Fprintf(w, "declare i32 @ugo_%s_%s()\n", file.Pkg.Name, fn.Name.Name)
return
}
fmt.Fprintln(w)

fmt.Fprintf(w, "define i32 @ugo_%s_%s() {\n", file.Pkg.Name, fn.Name.Name)
p.compileStmt(w, fn.Body)
fmt.Fprintln(w, "\tret i32 0")
fmt.Fprintln(w, "}")
}
  • 每一个函数都要使用 scope.Insert 在当前命名空间中注册函数符号
  • 基础的处理过后就交给 compileStmt 处理语句块

函数 compileStmt 的核心步骤就是处理如下几种语句:

  • VarSpec:变量定义
  • AssignStmt:赋值语句
  • BlockStmt:语句块
  • ExprStmt:表达式语句
  • RetStmt:返回语句
  • IfStmt:if 语句
  • ForStmt:for 语句

除了 if 语句,for 语句和表达式语句的实现代码都比较简单,这里直接给出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
case *ast.VarSpec:
var localName = "0"
if stmt.Value != nil {
localName = p.compileExpr(w, stmt.Value)
}

var mangledName = fmt.Sprintf("%%local_%s.pos.%d", stmt.Name.Name, stmt.VarPos)
p.scope.Insert(&Object{
Name: stmt.Name.Name,
MangledName: mangledName,
Node: stmt,
})

fmt.Fprintf(w, "\t%s = alloca i32, align 4\n", mangledName)
fmt.Fprintf(
w, "\tstore i32 %s, i32* %s\n",
localName, mangledName,
)

case *ast.AssignStmt:
p.compileStmt_assign(w, stmt)

case *ast.BlockStmt:
defer p.restoreScope(p.scope)
p.enterScope()

for _, x := range stmt.List {
p.compileStmt(w, x)
}

case *ast.ExprStmt:
p.compileExpr(w, stmt.X)

case *ast.RetStmt:
var retValue = p.compileExpr(w, stmt.Expr)
fmt.Fprintf(w, "\tret i32 %s\n", retValue)

处理 if 语句时需要考虑各个部分的作用域范围,因此使用匿名函数立即执行的写法,在匿名函数中添加 enterScope 和 restoreScope 来控制作用域范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
case *ast.IfStmt:
defer p.restoreScope(p.scope)
p.enterScope()

ifPos := fmt.Sprintf("%d", p.posLine())
ifInit := p.genLabelId("if.init.line" + ifPos)
ifCond := p.genLabelId("if.cond.line" + ifPos)
ifBody := p.genLabelId("if.body.line" + ifPos)
ifElse := p.genLabelId("if.else.line" + ifPos)
ifEnd := p.genLabelId("if.end.line" + ifPos)

// br if.init
fmt.Fprintf(w, "\tbr label %%%s\n", ifInit)

// if.init
fmt.Fprintf(w, "\n%s:\n", ifInit)
func() {
defer p.restoreScope(p.scope)
p.enterScope()

if stmt.Init != nil {
p.compileStmt(w, stmt.Init)
fmt.Fprintf(w, "\tbr label %%%s\n", ifCond)
} else {
fmt.Fprintf(w, "\tbr label %%%s\n", ifCond)
}

// if.cond
{
fmt.Fprintf(w, "\n%s:\n", ifCond)
condValue := p.compileExpr(w, stmt.Cond)
if stmt.Else != nil {
fmt.Fprintf(w, "\tbr i1 %s , label %%%s, label %%%s\n", condValue, ifBody, ifElse)
} else {
fmt.Fprintf(w, "\tbr i1 %s , label %%%s, label %%%s\n", condValue, ifBody, ifEnd)
}
}

// if.body
func() {
defer p.restoreScope(p.scope)
p.enterScope()

fmt.Fprintf(w, "\n%s:\n", ifBody)
if stmt.Else != nil {
p.compileStmt(w, stmt.Body)
fmt.Fprintf(w, "\tbr label %%%s\n", ifElse)
} else {
p.compileStmt(w, stmt.Body)
fmt.Fprintf(w, "\tbr label %%%s\n", ifEnd)
}
}()

// if.else
func() {
defer p.restoreScope(p.scope)
p.enterScope()

fmt.Fprintf(w, "\n%s:\n", ifElse)
if stmt.Else != nil {
p.compileStmt(w, stmt.Else)
fmt.Fprintf(w, "\tbr label %%%s\n", ifEnd)
} else {
fmt.Fprintf(w, "\tbr label %%%s\n", ifEnd)
}
}()
}()

// end
fmt.Fprintf(w, "\n%s:\n", ifEnd)

处理 for 语句时也是同样的思路:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
case *ast.ForStmt:
defer p.restoreScope(p.scope)
p.enterScope()

forPos := fmt.Sprintf("%d", p.posLine())
forInit := p.genLabelId("for.init.line" + forPos)
forCond := p.genLabelId("for.cond.line" + forPos)
forPost := p.genLabelId("for.post.line" + forPos)
forBody := p.genLabelId("for.body.line" + forPos)
forEnd := p.genLabelId("for.end.line" + forPos)

// br for.init
fmt.Fprintf(w, "\tbr label %%%s\n", forInit)

// for.init
func() {
defer p.restoreScope(p.scope)
p.enterScope()

fmt.Fprintf(w, "\n%s:\n", forInit)
if stmt.Init != nil {
p.compileStmt(w, stmt.Init)
fmt.Fprintf(w, "\tbr label %%%s\n", forCond)
} else {
fmt.Fprintf(w, "\tbr label %%%s\n", forCond)
}

// for.cond
fmt.Fprintf(w, "\n%s:\n", forCond)
if stmt.Cond != nil {
condValue := p.compileExpr(w, stmt.Cond)
fmt.Fprintf(w, "\tbr i1 %s , label %%%s, label %%%s\n", condValue, forBody, forEnd)
} else {
fmt.Fprintf(w, "\tbr label %%%s\n", forBody)
}

// for.body
func() {
defer p.restoreScope(p.scope)
p.enterScope()

fmt.Fprintf(w, "\n%s:\n", forBody)
p.compileStmt(w, stmt.Body)
fmt.Fprintf(w, "\tbr label %%%s\n", forPost)
}()

// for.post
{
fmt.Fprintf(w, "\n%s:\n", forPost)
if stmt.Post != nil {
p.compileStmt(w, stmt.Post)
fmt.Fprintf(w, "\tbr label %%%s\n", forCond)
} else {
fmt.Fprintf(w, "\tbr label %%%s\n", forCond)
}
}
}()

// end
fmt.Fprintf(w, "\n%s:\n", forEnd)

最后是表达式语句的处理,具体而言就是 compileExpr 函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
func (p *Compiler) compileExpr(w io.Writer, expr ast.Expr) (localName string) {
switch expr := expr.(type) {
case *ast.CallExpr:
if _, obj := p.scope.Lookup(expr.FuncName.Name); obj != nil {
localName = p.genId()
varStr := fmt.Sprintf("\t%s = call i32(i32) @ugo_main_%s(",
localName, expr.FuncName.Name,
)
for i, arg := range expr.Args {
if i == 0 {
varStr += p.changeType(obj.Node.(*ast.FuncDecl).Type.Name) + " " + p.compileExpr(w, arg)
} else {
varStr += ", " + p.changeType(obj.Node.(*ast.FuncDecl).Type.Name) + " " + p.compileExpr(w, arg)
}

}
varStr += ")\n"

fmt.Fprint(w, varStr)

} else {
panic(fmt.Sprintf("func %s undefined", expr.FuncName.Name))
}
return localName
case *ast.Ident:
var varName string
if _, obj := p.scope.Lookup(expr.Name); obj != nil {
varName = obj.MangledName
} else {
panic(fmt.Sprintf("var %s undefined", expr.Name))
}

localName = p.genId()
fmt.Fprintf(w, "\t%s = load i32, i32* %s, align 4\n",
localName, varName,
)
return localName
case *ast.IdentAS:
var varName string
if _, obj := p.scope.Lookup(expr.Name); obj != nil {
varName = obj.MangledName

call, ok := expr.Offset.(*ast.CallExpr)
if ok {
varName = p.compileExpr(w, call)
}
} else {
panic(fmt.Sprintf("var %s undefined", expr.Name))
}

localName = p.genId()
fmt.Fprintf(w, "\t%s = load i32, i32* %s, align 4\n",
localName, varName,
)
return localName
case *ast.Number:
localName = p.genId()
fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
localName, "add", `0`, expr.Value,
)
return localName
case *ast.BinaryExpr:
localName = p.genId()
switch expr.Op {
case token.ADD:
fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
localName, "add", p.compileExpr(w, expr.X), p.compileExpr(w, expr.Y),
)
return localName
case token.SUB:
fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
localName, "sub", p.compileExpr(w, expr.X), p.compileExpr(w, expr.Y),
)
return localName
case token.MUL:
fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
localName, "mul", p.compileExpr(w, expr.X), p.compileExpr(w, expr.Y),
)
return localName
case token.DIV:
fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
localName, "div", p.compileExpr(w, expr.X), p.compileExpr(w, expr.Y),
)
return localName
case token.MOD:
fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
localName, "srem", p.compileExpr(w, expr.X), p.compileExpr(w, expr.Y),
)
return localName
case token.EQL: // ==
fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
localName, "icmp eq", p.compileExpr(w, expr.X), p.compileExpr(w, expr.Y),
)
return localName
case token.NEQ: // !=
fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
localName, "icmp ne", p.compileExpr(w, expr.X), p.compileExpr(w, expr.Y),
)
return localName
case token.LSS: // <
fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
localName, "icmp slt", p.compileExpr(w, expr.X), p.compileExpr(w, expr.Y),
)
return localName
case token.LEQ: // <=
fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
localName, "icmp sle", p.compileExpr(w, expr.X), p.compileExpr(w, expr.Y),
)
return localName
case token.GTR: // >
fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
localName, "icmp sgt", p.compileExpr(w, expr.X), p.compileExpr(w, expr.Y),
)
return localName
case token.GEQ: // >=
fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
localName, "icmp sge", p.compileExpr(w, expr.X), p.compileExpr(w, expr.Y),
)
return localName
default:
panic(fmt.Sprintf("unknown: %[1]T, %[1]v", expr))
}
case *ast.UnaryExpr:
if expr.Op == token.SUB {
localName = p.genId()
fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
localName, "sub", `0`, p.compileExpr(w, expr.X),
)
return localName
}
return p.compileExpr(w, expr.X)
case *ast.ParenExpr:
return p.compileExpr(w, expr.X)

default:
panic(fmt.Sprintf("unknown: %[1]T, %[1]v", expr))
}
}

完善函数语句

对于一个函数而已,关键信息有:函数名,参数列表,返回类型,语句块

对应的 AST 结点结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
// 全局函数/方法
type FuncDecl struct {
FuncPos int // func 关键字位置
Params *FieldList // 传参类型
Name *Ident // 函数名
Type *Ident // 返回类型
Body *BlockStmt // 函数内的语句块
}

// 参数/属性 列表
type FieldList struct {
List []*Field
}
  • 暂时不涉及多值返回

处理函数定义

函数 parseFunc 用于解析函数定义,其初步实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
func (p *Parser) parseFunc() *ast.FuncDecl {
tokFunc := p.MustAcceptToken(token.FUNC)
tokFuncIdent := p.MustAcceptToken(token.IDENT)

p.MustAcceptToken(token.LPAREN)
funcFieldList := &ast.FieldList{}

if _, ok := p.AcceptToken(token.RPAREN); !ok {
for {
tokVal := p.MustAcceptToken(token.IDENT)
tokTyp := p.MustAcceptToken(token.IDENT)
funcField := &ast.Field{
Name: &ast.Ident{
NamePos: tokVal.Pos,
Name: tokVal.Literal,
},
Type: &ast.Ident{
NamePos: tokTyp.Pos,
Name: tokTyp.Literal,
}}
funcFieldList.List = append(funcFieldList.List, funcField)
if ok = p.SymTab.Push(funcField.Name, funcField.Type); !ok {
p.errorf(tokVal.Pos, "duplicate variable declaration: %s", tokVal.Literal)
}
if _, ok := p.AcceptToken(token.COMMA); !ok {
break
}
}
p.MustAcceptToken(token.RPAREN)
}

funcName := &ast.Ident{
NamePos: tokFuncIdent.Pos,
Name: tokFuncIdent.Literal,
}

funcType := &ast.Ident{}
if tokTypeIdent, ok := p.AcceptToken(token.IDENT); ok {
funcType = &ast.Ident{
NamePos: tokTypeIdent.Pos,
Name: tokTypeIdent.Literal,
}
}

return &ast.FuncDecl{
FuncPos: tokFunc.Pos,
Params: funcFieldList,
Name: funcName,
Type: funcType,
Body: p.parseStmt_block(),
}
}
  • 暂时不支持Go语言中多个参数共用一个类型的写法
  • 函数参数将会被暂时添加入符号表中

对于一个函数而言,需要在函数返回之后在符号表中清除其传参和临时变量,这里的处理方式为:记录语句块中传参和临时变量的个数,然后在语句块结束之后执行对应数量的 Pop

这样做有一个好处,那就是当遇到嵌套语句块时也可以区分各个变量的作用域

为此需要在 SymTab 中新添加一个条目:

1
2
3
4
5
6
type SymTab struct {
elements []*TypeSpec
block []int
top int
level int
}
  • 每一层都有一个数字来记录当前语句块中有多少个变量

修改一下 Push 和 Pop 语句,并添加一个 Pops 用于弹出全部的传参和临时变量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func (s *SymTab) Push(name, typ *Ident) bool {
for i := s.top - 1; i >= 0; i-- {
if s.elements[i].Name.Name == name.Name {
return false
}
}
s.elements = append(s.elements, &TypeSpec{
Name: name,
Type: typ,
})
s.top++
s.block[s.level]++
return true
}

func (s *SymTab) Pop() bool {
if s.top == 0 {
return false
}
s.top--
s.elements = s.elements[:len(s.elements)-1]
return true
}

func (s *SymTab) Pops() bool {
for s.block[s.level] > 0 {
if ok := s.Pop(); !ok {
return false
}
s.block[s.level]--
}
return true
}

添加两个辅助函数用于换层:

1
2
3
4
5
6
7
8
9
func (s *SymTab) AddLevel() {
s.level++
s.block = append(s.block, 0)
}

func (s *SymTab) SubLevel() {
s.level--
s.block = s.block[:len(s.block)-1]
}

最后修改 parseStmt_block 和 parseFunc,往其中添加换层与清空临时变量的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func (p *Parser) parseStmt_block() *ast.BlockStmt {
block := &ast.BlockStmt{}
tokBegin := p.MustAcceptToken(token.LBRACE) // 获取'{'的位置

p.SymTab.AddLevel()

......

tokEnd := p.MustAcceptToken(token.RBRACE) // 获取'}'的位置
block.Lbrace = tokBegin.Pos
block.Rbrace = tokEnd.Pos

p.SymTab.Pops()
p.SymTab.SubLevel()

return block
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func (p *Parser) parseFunc() *ast.FuncDecl {
tokFunc := p.MustAcceptToken(token.FUNC)
tokFuncIdent := p.MustAcceptToken(token.IDENT)

p.MustAcceptToken(token.LPAREN)
funcFieldList := &ast.FieldList{}

p.SymTab.AddLevel()

......

p.SymTab.Pops()
p.SymTab.SubLevel()

return &ast.FuncDecl{
FuncPos: tokFunc.Pos,
Params: funcFieldList,
Name: funcName,
Type: funcType,
Body: funcBody,
}
}

处理返回语句

return 语句对应的 AST 结点结构如下:

1
2
3
4
5
// 表示一个 return 语句节点
type RetStmt struct {
Ret int // return 关键字的位置
Expr Expr // 返回值表达式
}

核心函数 parseStmt_return 如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func (p *Parser) parseStmt_return() *ast.RetStmt {
tokRet := p.MustAcceptToken(token.RETURN)
tokExp := p.parseExpr()

myTypeX := reflect.TypeOf(tokExp)
if myTypeX.String() == "*ast.Strings" || myTypeX.String() == "*ast.Bool" {
p.errorf(tokExp.Pos(), "Non-numbers cannot participate in the calculation")
}

return &ast.RetStmt{
Ret: tokRet.Pos,
Expr: tokExp,
}
}

处理函数调用

函数调用对应的 AST 结点结构如下:

1
2
3
4
5
6
7
// 表示一个函数调用
type CallExpr struct {
FuncName *Ident // 函数名字
Lparen int // '(' 位置
Args []Expr // 调用参数列表
Rparen int // ')' 位置
}

函数调用发生在表达式中,需要处理的函数为 parseExpr_primary:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
if lp, ok := p.AcceptToken(token.LPAREN); ok {
var rp token.Token
astc := &ast.CallExpr{
FuncName: &ast.Ident{
NamePos: tok.Pos,
Name: tok.Literal,
},
}
for {
if rp, ok = p.AcceptToken(token.RPAREN); ok {
break
}
arg := p.parseExpr()
astc.Args = append(astc.Args, arg)
p.AcceptToken(token.COMMA)
}
astc.Lparen = lp.Pos
astc.Rparen = rp.Pos
asti.Offset = astc

return asti
}

函数表

函数表被记录于全局函数中,这里主要是通过函数表完成与函数有关的各种错误检查

错误类型:函数重复定义

1
2
3
4
5
6
7
8
func (p *Parser) checkFuncName(name string) bool {
for _, fu := range p.file.Funcs {
if fu.Name.Name == name {
return true
}
}
return false
}
1
2
3
4
5
tokFunc := p.MustAcceptToken(token.FUNC)
tokFuncIdent := p.MustAcceptToken(token.IDENT)
if ok := p.checkFuncName(tokFuncIdent.Literal); ok {
p.errorf(tokFuncIdent.Pos, "duplicate function declaration: %s", tokFuncIdent.Literal)
}

错误类型:函数未定义

1
2
3
4
5
6
7
8
9
10
11
if lp, ok := p.AcceptToken(token.LPAREN); ok {
if ok = p.checkFuncName(tok.Literal); !ok {
p.errorf(lp.Pos, "Function name:%s not find", tok.Literal)
}
var rp token.Token
astc := &ast.CallExpr{
FuncName: &ast.Ident{
NamePos: tok.Pos,
Name: tok.Literal,
},
}

错误类型:传参不匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func (p *Parser) checkFuncArgs(name string, args []ast.Expr) bool {
for _, fu := range p.file.Funcs {
if fu.Name.Name != name {
continue
}

if len(args) != len(fu.Params.List) {
return false
}

for i, arg := range fu.Params.List {
myType := reflect.TypeOf(args[i])
if arg.Type.Name == "string" && myType.String() != "*ast.Strings" {
return false
}
if arg.Type.Name == "bool" && myType.String() != "*ast.Bool" {
return false
}
}
break
}
return true
}
1
2
3
4
5
6
7
8
9
10
11
for {
if rp, ok = p.AcceptToken(token.RPAREN); ok {
break
}
arg := p.parseExpr()
astc.Args = append(astc.Args, arg)
p.AcceptToken(token.COMMA)
}
if ok = p.checkFuncArgs(tok.Literal, astc.Args); !ok {
p.errorf(lp.Pos, "The function parameters do not match")
}

符号表

本实验使用如下结构来组织符号表:

1
2
3
4
type SymTab struct {
elements []*TypeSpec
top int
}
  • PS:目前该符号表仅用于变量,在后续实验完善函数模块后会添加函数符号

与之配套的函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
func NewSymTab() *SymTab {
return &SymTab{
elements: nil,
top: 0,
}
}

func (s *SymTab) Push(name, typ *Ident) bool {
for i := s.top - 1; i >= 0; i-- {
if s.elements[i].Name.Name == name.Name {
return false
}
}
s.elements = append(s.elements, &TypeSpec{
Name: name,
Type: typ,
})
s.top++
return true
}

func (s *SymTab) Pop() bool {
if s.top == 0 {
return false
}
s.top--
s.elements = s.elements[:len(s.elements)-1]
return true
}

func (s *SymTab) GetType(value *Ident) (*Ident, bool) {
for i := s.top - 1; i >= 0; i-- {
if s.elements[i].Name.Name == value.Name {
return s.elements[i].Type, true
}
}
return nil, false
}

func (s *SymTab) CheckType(value, typ *Ident) bool {
if tmp, ok := s.GetType(value); ok {
return tmp.Name == typ.Name
}
return false
}

func (s *SymTab) ShowAll() {
fmt.Println("----------SymTab-------------------------")
for i, e := range s.elements {
fmt.Printf("|@%d: {Name: %s, Type: %s}\t\t|\n", i+1, e.Name.Name, e.Type.Name)
}
fmt.Println("-----------------------------------------")
fmt.Println("")
}

错误检测

该错误检测不包括函数未定义和函数参数不匹配,后续实验会进行补充

错误类型:重复定义

该错误发生在变量定义的过程中,具体的函数为 parseStmt_var,需要在该函数中添加与符号表相关的代码:

1
2
3
4
5
6
if ok := p.SymTab.Push(&ast.Ident{
NamePos: tokIdent.Pos,
Name: tokIdent.Literal,
}, varSpec.Type); !ok {
p.errorf(tokIdent.Pos, "duplicate variable declaration: %s", tokIdent.Literal)
}

错误类型:使用时未定义

变量通常在表达式中使用,因此需要在 parseExpr_primary 中进行修改:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
case token.IDENT: // 变量 && 数组 && 结构体
p.MustAcceptToken(token.IDENT)
asti := &ast.IdentAS{
NamePos: tok.Pos,
Name: tok.Literal,
}
if _, ok := p.AcceptToken(token.LSB); ok {
asti.Offset = p.parseExpr()
p.AcceptToken(token.RSB)
}
if _, ok := p.AcceptToken(token.DOT); ok {
asti.Offset = p.parseExpr()
}

if _, ok := p.SymTab.GetType(tok.Literal); !ok {
p.errorf(tok.Pos, "unknown variable: %s", tok.Literal)
}
return asti

错误类型:未知类型

在进行类型检查之前需要先创建一个类型列表用以记录已有的类型:

1
2
3
4
type TypeTab struct {
elements []string
top int
}

相关函数可以模仿 SymTab:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
func NewTypeTab() *TypeTab {
var re = &TypeTab{
elements: make([]string, 4),
top: 4,
}

re.elements[0] = "bool"
re.elements[1] = "char"
re.elements[2] = "int"
re.elements[3] = "string"

return re
}

func (s *TypeTab) Push(typ string) bool {
for i := s.top - 1; i >= 0; i-- {
if s.elements[i] == typ {
return false
}
}
s.elements = append(s.elements, typ)
s.top++
return true
}

func (s *TypeTab) Pop() bool {
if s.top == 0 {
return false
}
s.top--
return true
}

func (s *TypeTab) CheckType(typ string) bool {
for i := s.top - 1; i >= 0; i-- {
if s.elements[i] == typ {
return true
}
}
return false
}

func (s *TypeTab) ShowAll() {
fmt.Println("----------TypeTab------------------------")
for i, e := range s.elements {
fmt.Printf("|@%d: {Type: %s}\t\t\t|\n", i+1, e)
}
fmt.Println("-----------------------------------------")
fmt.Println("")
}

类型检查发生在变量定义的过程中,也就是 parseStmt_var 函数,往其中添加有关类型检查的代码:

1
2
3
4
5
6
7
8
9
if typ, ok := p.AcceptToken(token.IDENT); ok {
varSpec.Type = &ast.Ident{
NamePos: typ.Pos,
Name: typ.Literal,
}
if ok = p.TypeTab.CheckType(typ.Literal); !ok {
p.errorf(typ.Pos, "unknown type: %s", typ.Literal)
}
}

错误类型:重复类型定义

该错误发生在 type 语句,需要在 parseStmt_type 函数中添加对应的检查代码:

1
2
3
if ok := p.TypeTab.Push(tokIdent.Literal); !ok {
p.errorf(tokIdent.Pos, "duplicate type name: %s", tokIdent.Literal)
}

错误类型:类型不匹配

目前该编译器支持4种类型(bool,char,int,string),而需要修改的地方一共有3处

用于匹配类型的函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func (s *TypeTab) MatchType(left string, right interface{}) bool {
myType := reflect.TypeOf(right)
switch {
case myType.String() == "*ast.Strings":
if left != "string" {
return false
}
case myType.String() == "*ast.Number":
if left != "int" {
return false
}
case myType.String() == "*ast.Bool":
if left != "bool" {
return false
}
case myType.String() == "*ast.Char":
if left != "char" {
return false
}
}
return true
}

修改 parseStmt_var,检查变量初始化的类型是否匹配:

1
2
3
4
5
6
7
if _, ok := p.AcceptToken(token.ASSIGN); ok {
varSpec.Value = p.parseExpr()

if ok = p.TypeTab.MatchType(varSpec.Type.Name, varSpec.Value); !ok {
p.errorf(tokIdent.Pos, "The variable:%s type:%s not match", varSpec.Name.Name, varSpec.Type.Name)
}
}

修改 parseStmt_block,检查赋值语句的类型是否匹配:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
case token.DEFINE, token.ASSIGN:
p.ReadToken()
exprValueList := p.parseExprList()
if len(exprList) != len(exprValueList) {
p.errorf(tok.Pos, "unknown token: %v", tok)
}
var assignStmt = &ast.AssignStmt{
Target: make([]*ast.IdentAS, len(exprList)),
OpPos: tok.Pos,
Op: tok.Type,
Value: make([]ast.Expr, len(exprList)),
}
for i, target := range exprList {
assignStmt.Target[i] = target.(*ast.IdentAS)
assignStmt.Value[i] = exprValueList[i]

if ok := p.TypeTab.MatchType(assignStmt.Target[i].Name, assignStmt.Value[i]); !ok {
p.errorf(tok.Pos, "The variable:%s type not match", assignStmt.Target[i].Name)
}
}
block.List = append(block.List, assignStmt)

修改 parseExpr_binary,字符串和布尔不能参与运算:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
op := p.PeekToken()
if op.Type.Precedence() < prec {
return x
}

myTypeX := reflect.TypeOf(x)
if myTypeX.String() == "*ast.Strings" || myTypeX.String() == "*ast.Bool" {
p.errorf(op.Pos, "Non-numbers cannot participate in the calculation")
}

p.MustAcceptToken(op.Type)
y := p.parseExpr_binary(op.Type.Precedence() + 1)
x = &ast.BinaryExpr{OpPos: op.Pos, Op: op.Type, X: x, Y: y}

myTypeY := reflect.TypeOf(y)
if myTypeY.String() == "*ast.Strings" || myTypeY.String() == "*ast.Bool" {
p.errorf(op.Pos, "Non-numbers cannot participate in the calculation")
}

首先需要在 token.go 中添加对应的定义:

1
2
3
4
5
6
7
8
const (
......
STRINGS
ARRAY
TYPE
STRUCT
......
)
1
2
3
4
5
6
7
8
var tokens = [...]string{
......
STRINGS: "STRINGS",
ARRAY: "ARRAY",
TYPE: "type",
STRUCT: "struct",
......
}

字符串处理

在词法分析阶段,只需要添加对 “双引号” 的处理即可:

1
2
3
4
5
6
7
case r == '"':
for {
if r := p.src.Read(); r == '"' {
p.emit(token.STRINGS)
break
}
}

在语法分析阶段,字符串 AST 结点的结构可以仿造 Number:

1
2
3
4
5
6
7
// 一个字符串
type Strings struct {
ValuePos int // 字符串的开始位置
ValueEnd int // 字符串的结束位置
Value string // 字符串
ValueLen int // 字符串长度
}

字符串通常会作为表达式出现,因此需要在 parseExpr_primary 中添加与字符串有关的处理:

1
2
3
4
5
6
7
case token.STRINGS: // 字符串
tokStrings := p.MustAcceptToken(token.STRINGS)
return &ast.Strings{
ValuePos: tokStrings.Pos + 1,
ValueEnd: tokStrings.Pos + int(len(tokStrings.Literal)) - 1,
Value: tokStrings.Literal[1 : len(tokStrings.Literal)-1],
}

数组处理

数组的处理分为数组定义和数组使用这两个过程,首先需要定义 “[]” 的符号:

1
2
3
4
5
6
const (
......
LSB // [
RSB // ]
......
)
1
2
3
4
5
6
var tokens = [...]string{
......
LSB: "[",
RSB: "]",
......
}

然后在语法分析中添加对 “[]” 的识别:

1
2
3
4
case r == '[':
p.emit(token.LSB)
case r == ']':
p.emit(token.RSB)

另外还需要修改变量的 AST 结点结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 变量定义信息
type VarSpec struct {
VarPos int // var 关键字位置
Name *IdentArr // 变量名字
Type *Ident // 变量类型, 可省略
Value Expr // 变量表达式
}

// 一个变量 && 数组
type IdentArr struct {
NamePos int // 字符位置
Name string // 字符
Offset Expr // 数组位置
}
  • 其实就是在变量的基础上添加了一个 Expr 用于记录数组偏移

数组定义的格式如下:

1
var arrName [arrLen]arrType

对比于普通变量的定义多了 [arrLen]arrType,因此直接对 parseStmt_var 函数进行修改:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func (p *Parser) parseStmt_var() *ast.VarSpec {
tokVar := p.MustAcceptToken(token.VAR)
tokIdent := p.MustAcceptToken(token.IDENT)

var varSpec = &ast.VarSpec{
VarPos: tokVar.Pos,
}

varSpec.Name = &ast.IdentArr{
NamePos: tokIdent.Pos,
Name: tokIdent.Literal,
Offset: nil,
}

if typ, ok := p.AcceptToken(token.IDENT); ok {
varSpec.Type = &ast.Ident{
NamePos: typ.Pos,
Name: typ.Literal,
}
}

if _, ok := p.AcceptToken(token.LSB); ok { /* 若检测到'['则为Offset添加数据 */
varSpec.Name.Offset = p.parseExpr()
p.AcceptToken(token.RSB)

typ, _ := p.AcceptToken(token.IDENT)
varSpec.Type = &ast.Ident{
NamePos: typ.Pos,
Name: typ.Literal,
}
}

if _, ok := p.AcceptToken(token.ASSIGN); ok {
varSpec.Value = p.parseExpr()
}

p.AcceptToken(token.SEMICOLON)
return varSpec
}

数组多用于表达式中,需要在 parseExpr_primary 添加对于数组的处理:

1
2
3
4
5
6
7
8
9
10
11
case token.IDENT: // 变量 && 数组
p.MustAcceptToken(token.IDENT)
asti := &ast.IdentArr{
NamePos: tok.Pos,
Name: tok.Literal,
}
if _, ok := p.AcceptToken(token.LSB); ok { /* 检测'['判断是否为数组 */
asti.Offset = p.parseExpr()
p.AcceptToken(token.RSB)
}
return asti

为了与赋值语句匹配,最后需要修改 parseStmt 和 parseStmt_block 的部分代码:

1
2
3
4
5
6
7
8
9
10
var assignStmt = &ast.AssignStmt{
Target: make([]*ast.IdentArr, len(exprList)),
OpPos: tok.Pos,
Op: tok.Type,
Value: make([]ast.Expr, len(exprList)),
}
for i, target := range exprList {
assignStmt.Target[i] = target.(*ast.IdentArr)
assignStmt.Value[i] = exprValueList[i]
}

结构体处理

在词法分析阶段,需要添加对 “type” 和 “struct” 这两个关键词的匹配:

1
2
3
4
5
6
var tokens = [...]string{
.....
TYPE: "type",
STRUCT: "struct",
.....
}

另外需要将它们添加入关键词列表中:

1
2
3
4
5
6
var keywords = map[string]TokenType{
......
"type": TYPE,
"struct": STRUCT,
......
}

结构体的 AST 结点结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
// 类型定义
type TypeSpec struct {
Name *Ident // 类型名
Type *Ident // 类型
}

// 结构体定义
type StructType struct {
TypePos int // type 关键字位置
Name *Ident // 结构体名字
Types []*TypeSpec // 类型列表
}

结构体定义发生在全局,需要先修改 parseFile 函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func (p *Parser) parseFile() {
p.file = &ast.File{
Filename: p.Filename(),
Source: p.Source(),
}

p.file.Pkg = p.parsePackage()

for {
switch tok := p.PeekToken(); tok.Type {
case token.EOF:
return
case token.ERROR:
panic(tok)
case token.SEMICOLON:
p.AcceptTokenList(token.SEMICOLON)
case token.FUNC:
p.file.Funcs = append(p.file.Funcs, p.parseFunc())
case token.VAR: /* 全局变量处理 */
p.file.Globals = append(p.file.Globals, p.parseStmt_var())
case token.TYPE: /* 结构体处理 */
p.file.Types = append(p.file.Types, p.parseStmt_type())
default:
p.errorf(tok.Pos, "unknown token: %v", tok)
}
}
}

核心函数 parseStmt_type 如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
func (p *Parser) parseStmt_type() *ast.StructType {
tokpos := p.MustAcceptToken(token.TYPE)
tokIdent := p.MustAcceptToken(token.IDENT)

var StructType = &ast.StructType{
TypePos: tokpos.Pos,
}

StructType.Name = &ast.Ident{
NamePos: tokIdent.Pos,
Name: tokIdent.Literal,
}

switch tok := p.PeekToken(); tok.Type {
case token.IDENT:
tokty := p.MustAcceptToken(token.IDENT)
StructType.Types = append(StructType.Types, &ast.TypeSpec{
Name: nil,
Type: &ast.Ident{
NamePos: tokty.Pos,
Name: tokty.Literal,
},
})
case token.STRUCT:
if _, ok := p.AcceptToken(token.STRUCT); ok {
p.AcceptToken(token.LBRACE)

for {
if _, ok := p.AcceptToken(token.RBRACE); ok {
break
}
if toks, ok := p.AcceptTokenList(token.IDENT); ok {
StructType.Types = append(StructType.Types, &ast.TypeSpec{
Name: &ast.Ident{
NamePos: toks[0].Pos,
Name: toks[0].Literal,
},
Type: &ast.Ident{
NamePos: toks[1].Pos,
Name: toks[1].Literal,
},
})
}
p.ReadToken()
}
} else {
panic("Grammatical parsing errors")
}
default:
p.errorf(tok.Pos, "unknown tok: type=%v, lit=%q", tok.Type, tok.Literal)
}

p.AcceptToken(token.SEMICOLON)
return StructType
}
  • 这里分别实现了 type 的两种用法

结构体多用于表达式中,需要在 parseExpr_primary 添加对于结构体的处理:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
case token.IDENT: // 变量 && 数组 && 结构体
p.MustAcceptToken(token.IDENT)
asti := &ast.IdentArr{
NamePos: tok.Pos,
Name: tok.Literal,
}
if _, ok := p.AcceptToken(token.LSB); ok {
asti.Offset = p.parseExpr()
p.AcceptToken(token.RSB)
}
if _, ok := p.AcceptToken(token.DOT); ok {
asti.Offset = p.parseExpr()
}
return asti

变量和作用域

最小µGo的编译器中没有等号,需要在 (p *Lexer) run() (tokens []token.Token) 中添加有关等号的处理:

1
2
3
4
5
6
7
8
case r == '=': // =, ==
switch p.src.Read() {
case '=':
p.emit(token.EQL)
default:
p.src.Unread()
p.emit(token.ASSIGN)
}

本次实验需要完成语法分析中的:“变量声明”,“嵌套语句块”,“赋值语句”

在语法分析中对于语句的处理如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
func (p *Parser) parseStmt() ast.Stmt {
switch tok := p.PeekToken(); tok.Type {
case token.EOF:
return nil
case token.ERROR:
p.errorf(tok.Pos, "invalid token: %s", tok.Literal)
case token.SEMICOLON:
p.AcceptTokenList(token.SEMICOLON)
return nil
case token.LBRACE: // 语句块
return p.parseStmt_block()
default:
exprList := p.parseExprList() // 表达式列表 exprList
switch tok := p.PeekToken(); tok.Type {
case token.SEMICOLON, token.LBRACE: // exprList;
if len(exprList) != 1 {
p.errorf(tok.Pos, "unknown token: %v", tok.Type)
}
return &ast.ExprStmt{
X: exprList[0],
}
case token.DEFINE, token.ASSIGN:
// exprList := exprList; && exprList = exprList;
p.ReadToken()
exprValueList := p.parseExprList()
if len(exprList) != len(exprValueList) {
p.errorf(tok.Pos, "unknown token: %v", tok)
}
var assignStmt = &ast.AssignStmt{
Target: make([]*ast.Ident, len(exprList)),
OpPos: tok.Pos,
Op: tok.Type,
Value: make([]ast.Expr, len(exprList)),
}
for i, target := range exprList {
assignStmt.Target[i] = target.(*ast.Ident)
assignStmt.Value[i] = exprValueList[i]
}
return assignStmt
default:
p.errorf(tok.Pos, "unknown token: %v", tok)
}
}

panic("unreachable")
}
  • 对于 default 分支来说有如下3种情况:
1
2
3
exprList ;
exprList := exprList;
exprList = exprList;
  • 然后根据这3种情况分别生成赋值语句结点,该结点的 AST 结构如下:
1
2
3
4
5
6
7
// 一个赋值语句结点
type AssignStmt struct {
Target []*Ident // 要赋值的目标
OpPos int // ':=' 的位置
Op token.TokenType // '=' or ':='
Value []Expr // 值
}

语句块的 AST 结构体定义如下:

1
2
3
4
5
6
// 块语句
type BlockStmt struct {
Lbrace int // '{'的位置
List []Stmt
Rbrace int // '}'的位置
}

核心函数为 parseStmt_block,实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func (p *Parser) parseStmt_block() *ast.BlockStmt {
block := &ast.BlockStmt{}
tokBegin := p.MustAcceptToken(token.LBRACE) // 获取'{'的位置

Loop:
for {
switch tok := p.PeekToken(); tok.Type {
case token.EOF:
break Loop
case token.ERROR:
p.errorf(tok.Pos, "invalid token: %s", tok.Literal)
case token.SEMICOLON:
p.AcceptTokenList(token.SEMICOLON)
case token.RBRACE: // }
break Loop
default:
block.List = append(block.List, p.parseStmt_expr()) // 表达式中可能有子语句块
}
}

tokEnd := p.MustAcceptToken(token.RBRACE) // 获取'}'的位置
block.Lbrace = tokBegin.Pos
block.Rbrace = tokEnd.Pos
return block
}
  • break label 这种语法可以一次性跳出 for 和 switch

用于管理变量的 AST 结构体如下:

1
2
3
4
5
6
7
// 变量信息
type VarSpec struct {
VarPos int // var 关键字位置
Name *Ident // 变量名字
Type *Ident // 变量类型, 可省略
Value Expr // 变量表达式
}

变量可以为全局也可以存在于语句块中,因此需要将函数 parseStmt_var 添加入 parseStmt 和 parseStmt_block 中

核心函数 parseStmt_var 实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func (p *Parser) parseStmt_var() *ast.VarSpec {
tokVar := p.MustAcceptToken(token.VAR)
tokIdent := p.MustAcceptToken(token.IDENT)

var varSpec = &ast.VarSpec{
VarPos: tokVar.Pos,
}

varSpec.Name = &ast.Ident{
NamePos: tokIdent.Pos,
Name: tokIdent.Literal,
}

if typ, ok := p.AcceptToken(token.IDENT); ok {
varSpec.Type = &ast.Ident{
NamePos: typ.Pos,
Name: typ.Literal,
}
}

if _, ok := p.AcceptToken(token.ASSIGN); ok {
varSpec.Value = p.parseExpr()
}
p.AcceptToken(token.SEMICOLON)
return varSpec
}
  • 利用之前实现的 API 获取 AST 结点的关键信息,最后生成并返回该 AST 结点

if分支和for循环

在 token 类型和注册的关键字中添加 if for,以保证词法分析可以顺利匹配

if 语句结点和 for 语句结点的定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 表示一个 if 语句节点
type IfStmt struct {
If int // if 关键字的位置
Init Stmt // 初始化语句
Cond Expr // if 条件, *BinaryExpr
Body *BlockStmt // if 为真时对应的语句列表
Else Stmt // else 对应的语句
}

// 表示一个 for 语句节点
type ForStmt struct {
For int // for 关键字的位置
Init Stmt // 初始化语句
Cond Expr // 条件表达式
Post Stmt // 迭代语句
Body *BlockStmt // 循环对应的语句列表
}

在语法分析中与 if for 语句只能在语句块中,因此需要添加入 parseStmt_block:

1
2
3
4
case token.IF:
block.List = append(block.List, p.parseStmt_if())
case token.FOR:
block.List = append(block.List, p.parseStmt_for())

对于 if 语句而言,有如下几种情况:

1
2
3
4
if x > 0 {}
if x := 1; x > 0 {}
if x > 0 {} else {}
if x := 1; x > 0 {} else {}

对应的处理函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func (p *Parser) parseStmt_if() *ast.IfStmt {
tokIf := p.MustAcceptToken(token.IF)
ifStmt := &ast.IfStmt{
If: tokIf.Pos,
}
stmt := p.parseStmt()
if _, ok := p.AcceptToken(token.SEMICOLON); ok {
ifStmt.Init = stmt
ifStmt.Cond = p.parseExpr()
ifStmt.Body = p.parseStmt_block()
} else {
ifStmt.Init = nil
if cond, ok := stmt.(*ast.ExprStmt); ok {
ifStmt.Cond = cond.X
} else {
p.errorf(tokIf.Pos, "if cond expect expr: %#v", stmt)
}
ifStmt.Body = p.parseStmt_block()
}

if _, ok := p.AcceptToken(token.ELSE); ok {
switch p.PeekToken().Type {
case token.IF: // else if
ifStmt.Else = p.parseStmt_if()
default:
ifStmt.Else = p.parseStmt_block()
}
}

return ifStmt
}

对于 for 语句而言,有如下几种情况:

1
2
3
for {}
for x > 10 {}
for x := 0; x < 10; x = x+1 {}

对应的处理函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
func (p *Parser) parseStmt_for() *ast.ForStmt {
tokFor := p.MustAcceptToken(token.FOR)

forStmt := &ast.ForStmt{
For: tokFor.Pos,
}

// for {}
if _, ok := p.AcceptToken(token.LBRACE); ok {
p.UnreadToken()
forStmt.Body = p.parseStmt_block()
return forStmt
}

// for Cond {}
// for Init?; Cond?; Post? {}

// for ; ...
if _, ok := p.AcceptToken(token.SEMICOLON); ok {
forStmt.Init = nil

// for ;; ...
if _, ok := p.AcceptToken(token.SEMICOLON); ok {
if _, ok := p.AcceptToken(token.LBRACE); ok {
// for ;; {}
p.UnreadToken()
forStmt.Body = p.parseStmt_block()
return forStmt
} else {
// for ; ; postStmt {}
forStmt.Post = p.parseStmt()
forStmt.Body = p.parseStmt_block()
return forStmt
}
} else {
// for ; cond ; ... {}
forStmt.Cond = p.parseExpr()
p.MustAcceptToken(token.SEMICOLON)
if _, ok := p.AcceptToken(token.LBRACE); ok {
// for ; cond ; {}
p.UnreadToken()
forStmt.Body = p.parseStmt_block()
return forStmt
} else {
// for ; cond ; postStmt {}
forStmt.Post = p.parseStmt()
forStmt.Body = p.parseStmt_block()
return forStmt
}
}
} else {
stmt := p.parseStmt()

if _, ok := p.AcceptToken(token.LBRACE); ok {
// for cond {}
p.UnreadToken()
if expr, ok := stmt.(ast.Expr); ok {
forStmt.Cond = expr
}
forStmt.Body = p.parseStmt_block()
return forStmt
} else {
// for init;
p.MustAcceptToken(token.SEMICOLON)
forStmt.Init = stmt

// for ;; ...
if _, ok := p.AcceptToken(token.SEMICOLON); ok {
if _, ok := p.AcceptToken(token.LBRACE); ok {
// for ;; {}
p.UnreadToken()
forStmt.Body = p.parseStmt_block()
return forStmt
} else {
// for ; ; postStmt {}
forStmt.Post = p.parseStmt()
forStmt.Body = p.parseStmt_block()
return forStmt
}
} else {
// for ; cond ; ... {}
forStmt.Cond = p.parseExpr()
p.MustAcceptToken(token.SEMICOLON)
if _, ok := p.AcceptToken(token.LBRACE); ok {
// for ; cond ; {}
p.UnreadToken()
forStmt.Body = p.parseStmt_block()
return forStmt
} else {
// for ; cond ; postStmt {}
forStmt.Post = p.parseStmt()
forStmt.Body = p.parseStmt_block()
return forStmt
}
}
}
}
}

赋值语句

赋值语句出现在语句块中,直接修改 parseStmt_block 函数即可

核心思路和 parseStmt 中关于变量初始化的处理一样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
default:
// exprList ;
// exprList := exprList;
// exprList = exprList;
exprList := p.parseExprList()
switch tok := p.PeekToken(); tok.Type {
case token.SEMICOLON:
if len(exprList) != 1 {
p.errorf(tok.Pos, "unknown token: %v", tok.Type)
}
block.List = append(block.List, &ast.ExprStmt{
X: exprList[0],
})
case token.DEFINE, token.ASSIGN:
p.ReadToken()
exprValueList := p.parseExprList()
if len(exprList) != len(exprValueList) {
p.errorf(tok.Pos, "unknown token: %v", tok)
}
var assignStmt = &ast.AssignStmt{
Target: make([]*ast.Ident, len(exprList)),
OpPos: tok.Pos,
Op: tok.Type,
Value: make([]ast.Expr, len(exprList)),
}
for i, target := range exprList {
assignStmt.Target[i] = target.(*ast.Ident)
assignStmt.Value[i] = exprValueList[i]
}
block.List = append(block.List, assignStmt)
default:
p.errorf(tok.Pos, "unknown token: %v", tok)
}
}

在上一节的最小uGo程序中,对于语句只需要处理表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func (p *Parser) parseStmt_block() *ast.BlockStmt {
block := &ast.BlockStmt{}
tokBegin := p.MustAcceptToken(token.LBRACE)

Loop:
for {
switch tok := p.PeekToken(); tok.Type {
case token.EOF:
break Loop
case token.ERROR:
p.errorf(tok.Pos, "invalid token: %s", tok.Literal)
case token.SEMICOLON:
p.AcceptTokenList(token.SEMICOLON)
case token.RBRACE: // }
break Loop
default:
block.List = append(block.List, p.parseStmt_expr())
}
}

tokEnd := p.MustAcceptToken(token.RBRACE)
block.Lbrace = tokBegin.Pos
block.Rbrace = tokEnd.Pos
return block
}

优先级处理

表达式节点生成的实现也是依赖于递归下降的思想

各个子表达式节点会根据优先级进行融合,最后得到一个用于描述该表达式的子树:

1
2
3
4
5
6
7
  +
/ \
1 *
/ \
2 +
/ \
3 4
  • 该子树所代表的表达式为:(1+(2*(3+4))) => 1+2*(3+4)
  • 数字节点“3”与数字节点“4”进行融合,然后融合后的表达式与数字节点“2”进行融合,以此类推

这里先给出一个简单的解决方式,假设需要处理的符号只有:+-*/()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
func (p *parser) build_expr() *ExprNode {
node := p.build_mul() // 优先乘除
for {
switch p.peekToken() {
case "+":
p.nextToken()
node = NewExprNode("+", node, p.build_mul())
case "-":
p.nextToken()
node = NewExprNode("-", node, p.build_mul())
default:
return node
}
}
}

func (p *parser) build_mul() *ExprNode {
node := p.build_primary() // 优先括号
for {
switch p.peekToken() {
case "*":
p.nextToken()
node = NewExprNode("*", node, p.build_primary())
case "/":
p.nextToken()
node = NewExprNode("/", node, p.build_primary())
default:
return node
}
}
}

func (p *parser) build_primary() *ExprNode {
if tok := p.peekToken(); tok == "(" {
p.nextToken()
node := p.build_expr()
p.nextToken() // skip ')'
return node
} else {
p.nextToken()
return NewExprNode(tok, nil, nil)
}
}
  • 这样写可以保证高优先级的表达式一定先融合,一定程度上遵守了表达式合成的规则

上述解决方案有一个很明显的问题,那就是不够通用,一个语言可能有很多的运算符号,对每个符号都进行优先级处理就会显得代码的臃肿

这里有一个更通用的表达式处理方案,其思路来自于 ACM 中的表达式求值:

1
1+2*(3+4)
  • 需要的数据结构为两个栈:一个存储符号,一个存储数字
  • 遇到数字直接 push 到数字栈中,遇到符号则先判断该符号和符号栈顶符号的优先级关系:
    • 该符号的优先级大于栈顶:从数字栈中 pop 两个数字,从符号栈中 pop 栈顶符号,计算该算式后将结果 push 到数字栈中
    • 该符号的优先级小于或等于栈顶:将该符号 push 到符号栈中
  • 循环执行上一步,最终符号栈为空,数字栈中只有一个数字(输出结果)

在编译原理中不需要栈进行辅助,但判断子节点是否进行融合的思路是一致的

获取优先级的函数如下:

1
2
3
4
5
6
7
8
9
10
11
func (op TokenType) Precedence() int {
switch op {
case EQL, NEQ, LSS, LEQ, GTR, GEQ:
return 1
case ADD, SUB:
return 2
case MUL, DIV, MOD:
return 3
}
return 0
}

基于优先级的处理方案如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
func (p *Parser) parseExpr() ast.Expr {
return p.parseExpr_binary(1)
}

func (p *Parser) parseExpr_binary(prec int) ast.Expr { // 处理二元表达式
x := p.parseExpr_unary()
for {
switch tok := p.PeekToken(); tok.Type {
case token.EOF:
return x
case token.SEMICOLON: // ;
return x
}

op := p.PeekToken()
if op.Type.Precedence() < prec {
return x
}

p.MustAcceptToken(op.Type)
y := p.parseExpr_binary(op.Type.Precedence() + 1)
x = &ast.BinaryExpr{OpPos: op.Pos, Op: op.Type, X: x, Y: y}
}
}

func (p *Parser) parseExpr_unary() ast.Expr { // 处理一元表达式
if _, ok := p.AcceptToken(token.ADD); ok {
return p.parseExpr_primary()
}
if tok, ok := p.AcceptToken(token.SUB); ok {
return &ast.UnaryExpr{
OpPos: tok.Pos,
Op: tok.Type,
X: p.parseExpr_primary(),
}
}
return p.parseExpr_primary()
}

func (p *Parser) parseExpr_primary() ast.Expr { // 处理元素
if _, ok := p.AcceptToken(token.LPAREN); ok {
expr := p.parseExpr()
p.MustAcceptToken(token.RPAREN)
return expr
}

switch tok := p.PeekToken(); tok.Type {
case token.IDENT: // 变量
p.MustAcceptToken(token.IDENT)
return &ast.Ident{
NamePos: tok.Pos,
Name: tok.Literal,
}
case token.NUMBER: // 数字
tokNumber := p.MustAcceptToken(token.NUMBER)
value, _ := strconv.Atoi(tokNumber.Literal)
return &ast.Number{
ValuePos: tokNumber.Pos,
ValueEnd: tokNumber.Pos + int(len(tokNumber.Literal)),
Value: value,
}
default:
p.errorf(tok.Pos, "unknown tok: type=%v, lit=%q", tok.Type, tok.Literal)
panic("unreachable")
}
}
  • 如果后一个符号 token 的优先级比当前符号 token 的优先小,则直接返回,并在回溯中融合子节点生成子树
  • 相反则是再次递归调用 parseExpr_binary,等待 parseExpr_binary 融合完成后,与融合后的子树进行融合

打印JSON

最简单的打印 AST 方式是输出 JSON 格式,为 ast.File 增加 JSONString 方法如下:

1
2
3
4
5
6
7
8
func (p *File) JSONString() string {
file := *p
if len(file.Source) > 8 {
file.Source = file.Source[:8] + "..."
}
d, _ := json.MarshalIndent(&file, "", " ")
return string(d)
}

使用案例还是之前的最小uGo程序:

1
2
3
4
5
package main

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

修改 main 函数,使其方便我们进行测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func main() {
code, err := readSource("./hello.ugo")
if err != nil {
return
}

l := lexer.NewLexer("../hello.ugo", code)

for i, tok := range l.Tokens() {
fmt.Printf(
"%02d: %-12v: %-20q // %s\n",
i, tok.Type, tok.Literal,
token.PosString("../hello.ugo", code, tok.Pos),
)
}
fmt.Println("-------------")

for i, tok := range l.Comments() {
fmt.Printf(
"%02d: %-12v: %-20q // %s\n",
i, tok.Type, tok.Literal,
token.PosString("../hello.ugo", code, tok.Pos),
)
}

p, err := parser.NewParser(l)
if err != nil {
panic(err)
}
fmt.Println(p.JSONString())
}

最后的效果如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
00: 5           : "package"            // ../hello.ugo:1:1
01: 3 : "main" // ../hello.ugo:1:9
02: 35 : "" // ../hello.ugo:2:1
03: 8 : "func" // ../hello.ugo:3:1
04: 3 : "main" // ../hello.ugo:3:6
05: 30 : "(" // ../hello.ugo:3:10
06: 31 : ")" // ../hello.ugo:3:11
07: 32 : "{" // ../hello.ugo:3:13
08: 3 : "exit" // ../hello.ugo:4:5
09: 30 : "(" // ../hello.ugo:4:9
10: 4 : "40" // ../hello.ugo:4:10
11: 17 : "+" // ../hello.ugo:4:12
12: 4 : "2" // ../hello.ugo:4:13
13: 31 : ")" // ../hello.ugo:4:14
14: 35 : "" // ../hello.ugo:5:1
15: 33 : "}" // ../hello.ugo:5:1
16: 0 : "" // ../hello.ugo:5:2
-------------
00: 2 : "// 退出码 42" // ../hello.ugo:4:16
{
"Filename": "../hello.ugo",
"Source": "package ...",
"Pkg": {
"PkgPos": 0,
"NamePos": 8,
"Name": "main"
},
"Globals": null,
"Funcs": [
{
"Recv": null,
"Name": {
"NamePos": 19,
"Name": "main"
},
"Type": {
"Func": 14,
"Params": null,
"Results": null
},
"Body": {
"Lbrace": 26,
"List": [
{
"X": {
"NamePos": 32,
"Name": "exit"
}
},
{
"X": {
"OpPos": 39,
"Op": 17,
"X": {
"ValuePos": 37,
"ValueEnd": 39,
"Value": 40
},
"Y": {
"ValuePos": 40,
"ValueEnd": 41,
"Value": 2
}
}
}
],
"Rbrace": 59
}
}
]
}