ugo-lab2-表达式优先级

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

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

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

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

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+2*(3+4)

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

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

获取优先级的函数如下：

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
}

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

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 方法如下：

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程序：

package main

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

修改 main 函数，使其方便我们进行测试：

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())
}

最后的效果如下：

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
            }
        }
    ]
}