Pratt Parsing - 自顶向下的算符优先级

1 + 2 * 3

3 * (1 + 2)

5 * (add(2,3) + 1)

add(3 * (1 + 2), add(1,2)) * 100

expr:
    expr ('+'|'-'|'*'|'/') expr
    | ('-') expr
    | '(' expr ')'
    | literal;

literal:
    IDENTIFIER // 标识别符
    | integer // 整数字面量
    | '(' ( expr (',' expr)* )? ')'; //参数列表

// 优先级从低到高排列
const (
	_           int = iota
	LOWEST          // 最低的
	SUM             // + -
	PRODUCT         // * /
	PREFIX          // -1
	CALL            // 函数调用，最高
)

// pratt parsing 的主要逻辑
func (p *Parser) parseExpr(precedence int) ast.Expr {
	prefix := p.prefixParseFns[p.curToken.Type]
	if prefix == nil {
		p.noPrefixParseFnError(p.curToken.Type)
		return nil
	}
	leftExpr := prefix()

	// 如果外部算符优先级没有后面遇到的的高，会循环下去
	for !p.peekTokenIs(token.SEMICOLON) && precedence < p.peekPrecedence() {
		infix := p.infixParseFns[p.peek_Tok.Type]
		if infix == nil {
			return leftExpr
		}
		p.nextToken()
		leftExpr = infix(leftExpr) // 合并中缀表达式
	}

	return leftExpr
}

type prefixParseFn func() ast.Expr
type infixParseFn func(ast.Expr) ast.Expr

// 前缀算符关联函数
p.prefixParseFns = make(map[token.Type]prefixParseFn)
// 标识符：变量名、函数名
p.registerPrefix(token.IDENT, p.parseIdentifier)
// 整数字面量：5、10
p.registerPrefix(token.INT, p.parseIntLiteral)
// 负号：-5
p.registerPrefix(token.MINUS, p.parsePrefixExpression)
// 分组(左括号)：3*(1+2)
p.registerPrefix(token.LPAREN, p.parseGroupExpr)

// 中缀算符关联函数
p.infixParseFns = make(map[token.Type]infixParseFn)
// 二元算术运算：+ - * /
p.registerInfix(token.PLUS, p.parseInfixExpr)
p.registerInfix(token.MINUS, p.parseInfixExpr)
p.registerInfix(token.ASTERISK, p.parseInfixExpr)
p.registerInfix(token.SLASH, p.parseInfixExpr)
// 函数调用(左括号)： add(1,2)
p.registerInfix(token.LPAREN, p.parseCallExpr)

func (p *Parser) parseIdentifier() ast.Expr {
	// 注意这里不调用 nextToken, 这很重要
	return &ast.Identifier{
		Token: p.curToken,
		Value: p.curToken.Literal,
	}
}

// int 作为prefix的关联函数
func (p *Parser) parseIntLiteral() ast.Expr {
	lit := &ast.Int_Literal{Token: p.curToken}

	v, err := strconv.ParseInt(p.curToken.Literal, 0, 64)
	if err != nil {
		p.errs = append(p.errs, fmt.Sprintf("无法将%s转换为int", p.curToken.Literal))
		return nil
	}
	lit.Value = v
	return lit
}

func (p *Parser) parsePrefixExpression() ast.Expr {
	expression := &ast.PrefixExpression{
		Token:    p.curToken,
		Operator: p.curToken.Literal,
	}
	p.nextToken()
	// 注意这里，是pratt parsing的关键
	// 传入优先级为 PREFIX, -3*5 , -add(1,2)  只有CALL大于此优先级
	expression.Right = p.parseExpr(PREFIX)
	return expression
}

-3*5 => (-3)*5
-add(1,2) => -(add(1,2))

func (p *Parser) parseGroupExpr() ast.Expr {
	p.nextToken()
	exp := p.parseExpr(LOWEST)
	if !p.expectPeek(token.RPAREN) { // 吃掉 )
		return nil
	}
	return exp
}

// 中缀算符的关联函数 + - * /
func (p *Parser) parseInfixExpr(left ast.Expr) ast.Expr {
	expr := &ast.Infix_Expr{
		Token:    p.curToken,
		Left:     left,
		Operator: p.curToken.Literal,
	}

	precedence := p.curPrecedence()
	p.nextToken()
	expr.Right = p.parseExpr(precedence)

	return expr
}

func (p *Parser) parseCallExpr(fn ast.Expr) ast.Expr {
	exp := &ast.Call_Expr{Token: p.curToken, Function: fn}
	exp.Arguments = p.parseCallArgs()
	return exp
}

func (p *Parser) parseCallArgs() []ast.Expr {
	args := []ast.Expr{}

	// 没有参数的情况
	if p.peekTokenIs(token.RPAREN) {
		p.nextToken()
		return args
	}
	// 解析参数
	p.nextToken()
	args = append(args, p.parseExpr(LOWEST))
	for p.peekTokenIs(token.COMMA) {
		p.nextToken()
		p.nextToken()
		args = append(args, p.parseExpr(LOWEST))
	}
	if !p.expectPeek(token.RPAREN) {
		return nil
	}
	return args
}

func (p *Parser) parseExpr(precedence int) ast.Expr {
	prefix := p.prefixParseFns[p.curToken.Type]
	if prefix == nil {
		p.noPrefixParseFnError(p.curToken.Type)
		return nil
	}
	leftExpr := prefix()

	// 如果当前算符优先级没有后面的高，会循环下去
	for !p.peekTokenIs(token.SEMICOLON) && precedence < p.peekPrecedence() {
		infix := p.infixParseFns[p.peek_Tok.Type]
		if infix == nil {
			return leftExpr
		}
		p.nextToken()
		leftExpr = infix(leftExpr) // 合并中缀表达式
	}

	return leftExpr
}