Go语言学习编程实践：实现简易计算器（包含词法器、语法树构建）

参考博主博客传送门
参考git代码，包含模块测试文件传送门

实现流程：
①把input输入的字符串进行拆分，变成一个一个单词，要设计词法分析器，大部分都设计相关的词法分析器。parser。它会不断读取每一个字符，然后生成对应的一个个词元。
我们将词元和词法分析器，分别用两个结构体表示出来。

type Token struct {
	Type string  //对应我们上面的词元类型
	Literal string // 实际的string字符
}

type Lexer struct {
	input string // 输入
	position int   // 当前位置                                                                                                                                                                                                                                                                                                                                                                                               
	readPosition int  // 将要读取的位置
	ch byte //当前字符
}

词法分析器操作：

不断读取字符串的每一个字符，更新结构体的值。
要注意考虑跳过空白字符/制表符。
对于数字要单独考虑，因为 ’567‘ 这是一个词元。

②构建语法树，要让计算机按照你想要的方式进行计算。遵循数学里面的计算法则。之前数据结构中学习二叉树时，都知道中缀表达式，对应了我们的计算规则。当然前缀/后缀也可以计算出正确的值，比如逆波兰式求职，这里不在赘述。可以看另一篇博客有通过后缀表达式计算值，安置传送门。
③考虑两种计算情况。
情况一：++i；某个操作符作为前缀与后面数字发生反应。同样还包括我们的-1。
情况二：1 + 2。操作符在中间。

// package calc
package main

import (
	"bufio"
	"bytes"
	"fmt"
	"os"
	"strconv"
)

const (
	ILLEGAL = "ILLEGAL"
	EOF     = "EOF"
	INT     = "INT"

	PLUS     = "+"
	MINUS    = "-"
	ASTERISK = "*"
	SLASH    = "/"

	LPAREN = "("
	RPAREN = ")"
)

const (
	_ int = iota
	LOWEST
	SUM     // +, -
	PRODUCT // *, /
	PREFIX  // -X
	CALL    // (X)
)

var precedences = map[string]int{
	PLUS:     SUM,
	MINUS:    SUM,
	SLASH:    PRODUCT,
	ASTERISK: PRODUCT,
	LPAREN:   CALL,
}

func Calc(input string) int64 {
	lexer := NewLex(input)
	parser := NewParser(lexer)

	exp := parser.ParseExpression(LOWEST)
	return Eval(exp)
}
func main() {

	reader := bufio.NewReader(os.Stdin)

	n, err := reader.ReadString('\n')
	if err != nil {
		fmt.Println("error")
	}

	//fmt.Println(n)
	fmt.Println(Calc(n))
}

func Eval(exp Expression) int64 {
	switch node := exp.(type) {
	case *IntegerLiteralExpression:
		return node.Value
	case *PrefixExpression:
		rightV := Eval(node.Right)
		return evalPrefixExpression(node.Operator, rightV)
	case *InfixExpression:
		leftV := Eval(node.Left)
		rightV := Eval(node.Right)
		return evalInfixExpression(leftV, node.Operator, rightV)
	}

	return 0
}

func evalPrefixExpression(operator string, right int64) int64 {
	if operator != "-" {
		return 0
	}
	return -right
}

func evalInfixExpression(left int64, operator string, right int64) int64 {

	switch operator {
	case "+":
		return left + right
	case "-":
		return left - right
	case "*":
		return left * right
	case "/":
		if right != 0 {
			return left / right
		} else {
			return 0
		}
	default:
		return 0
	}
}

type Token struct {
	Type    string
	Literal string
}

func newToken(tokenType string, c byte) Token {
	return Token{
		Type:    tokenType,
		Literal: string(c),
	}
}

type Lexer struct {
	input        string
	position     int
	readPosition int
	ch           byte
}

func NewLex(input string) *Lexer {
	l := &Lexer{input: input}
	l.readChar()
	return l
}

func (l *Lexer) NextToken() Token {
	var tok Token

	l.skipWhitespace() //跳过全部空白字符或制表符

	switch l.ch {
	case '(':
		tok = newToken(LPAREN, l.ch)
	case ')':
		tok = newToken(RPAREN, l.ch)
	case '+':
		tok = newToken(PLUS, l.ch)
	case '-':
		tok = newToken(MINUS, l.ch)
	case '/':
		tok = newToken(SLASH, l.ch)
	case '*':
		tok = newToken(ASTERISK, l.ch)
	case 0: //对于超出字符串范围的进行结束 EOF
		tok.Literal = ""
		tok.Type = EOF
	default:
		if isDigit(l.ch) {
			tok.Type = INT
			tok.Literal = l.readNumber()
			return tok
		} else {
			tok = newToken(ILLEGAL, l.ch) //非法字符处理
		}
	}

	l.readChar()
	return tok
}

func isDigit(ch byte) bool {
	return '0' <= ch && ch <= '9'
}

// 读一个字符，超出输入的字符串范围，就将当前字符置为0，结束读取
func (l *Lexer) readChar() {
	if l.readPosition >= len(l.input) {
		l.ch = 0
	} else {
		l.ch = l.input[l.readPosition]
	}
	l.position = l.readPosition
	l.readPosition += 1
}

// 读取数字的单独函数 因为345这是一个数
func (l *Lexer) readNumber() string {
	position := l.position
	for isDigit(l.ch) {
		l.readChar()
	}
	return l.input[position:l.position] //返回一个数据
}

// 知道是这些制表符就再往下读一个
func (l *Lexer) skipWhitespace() {
	for l.ch == ' ' || l.ch == '\t' || l.ch == '\n' || l.ch == '\r' {
		l.readChar()
	}
}

// ast

type Expression interface {
	String() string
}

type IntegerLiteralExpression struct {
	Token Token
	Value int64
}

func (il *IntegerLiteralExpression) String() string { return il.Token.Literal }

type PrefixExpression struct {
	Token    Token
	Operator string
	Right    Expression
}

func (pe *PrefixExpression) String() string {
	var out bytes.Buffer

	out.WriteString("(")
	out.WriteString(pe.Operator)
	out.WriteString(pe.Right.String())
	out.WriteString(")")

	return out.String()
}

type InfixExpression struct {
	Token    Token
	Left     Expression
	Operator string
	Right    Expression
}

func (ie *InfixExpression) String() string {
	var out bytes.Buffer

	out.WriteString("(")
	out.WriteString(ie.Left.String())
	out.WriteString(" ")
	out.WriteString(ie.Operator)
	out.WriteString(" ")
	out.WriteString(ie.Right.String())
	out.WriteString(")")

	return out.String()
}

// parser
type (
	prefixParseFn func() Expression //函数 返回参数是Expression接口
	infixParseFn  func(Expression) Expression
)

type Parser struct {
	l *Lexer

	curToken  Token
	peekToken Token

	prefixParseFns map[string]prefixParseFn //map的值是函数
	infixParseFns  map[string]infixParseFn

	errors []string
}

// 往结构体里面筛方法
func (p *Parser) registerPrefix(tokenType string, fn prefixParseFn) {
	p.prefixParseFns[tokenType] = fn
}

func (p *Parser) registerInfix(tokenType string, fn infixParseFn) {
	p.infixParseFns[tokenType] = fn
}

func NewParser(l *Lexer) *Parser {
	p := &Parser{
		l:      l,
		errors: []string{},
	}
	//这个结构体加入三种方法
	p.prefixParseFns = make(map[string]prefixParseFn)
	p.registerPrefix(INT, p.parseIntegerLiteral)
	p.registerPrefix(MINUS, p.parsePrefixExpression)
	p.registerPrefix(LPAREN, p.parseGroupedExpression)
	//这个加入四种方法 + - * /
	p.infixParseFns = make(map[string]infixParseFn)
	p.registerInfix(PLUS, p.parseInfixExpression)
	p.registerInfix(MINUS, p.parseInfixExpression)
	p.registerInfix(SLASH, p.parseInfixExpression)
	p.registerInfix(ASTERISK, p.parseInfixExpression)

	p.nextToken()
	p.nextToken()

	return p
}

func (p *Parser) ParseExpression(precedence int) Expression {
	prefix := p.prefixParseFns[p.curToken.Type]
	returnExp := prefix()

	for precedence < p.peekPrecedence() {
		infix := p.infixParseFns[p.peekToken.Type]
		if infix == nil {
			return returnExp
		}

		p.nextToken()
		returnExp = infix(returnExp)
	}

	return returnExp
}

func (p *Parser) peekPrecedence() int {
	if p, ok := precedences[p.peekToken.Type]; ok {
		return p
	}
	return LOWEST
}

func (p *Parser) curPrecedence() int {
	if p, ok := precedences[p.curToken.Type]; ok {
		return p
	}
	return LOWEST
}

func (p *Parser) peekError(t string) {
	msg := fmt.Sprintf("expected next token to be %s, got %s instend",
		t, p.peekToken.Type)
	p.errors = append(p.errors, msg)
}

func (p *Parser) expectPeek(t string) bool {
	if p.peekTokenIs(t) {
		p.nextToken()
		return true
	} else {
		p.peekError(t)
		return false
	}
}

func (p *Parser) peekTokenIs(t string) bool {
	return p.peekToken.Type == t
}

func (p *Parser) nextToken() {
	p.curToken = p.peekToken
	p.peekToken = p.l.NextToken()
}

func (p *Parser) parseIntegerLiteral() Expression {

	lit := &IntegerLiteralExpression{Token: p.curToken}

	value, err := strconv.ParseInt(p.curToken.Literal, 0, 64)
	if err != nil {
		msg := fmt.Sprintf("could not parse %q as integer", p.curToken.Literal)
		p.errors = append(p.errors, msg)
		return nil
	}

	lit.Value = value
	return lit
}

func (p *Parser) parsePrefixExpression() Expression {

	expression := &PrefixExpression{
		Token:    p.curToken,
		Operator: p.curToken.Literal,
	}
	p.nextToken()
	expression.Right = p.ParseExpression(PREFIX)
	return expression
}

func (p *Parser) parseGroupedExpression() Expression {
	p.nextToken()
	exp := p.ParseExpression(LOWEST)

	if !p.expectPeek(RPAREN) {
		return nil
	}
	return exp
}

func (p *Parser) parseInfixExpression(left Expression) Expression {

	expression := &InfixExpression{
		Token:    p.curToken,
		Operator: p.curToken.Literal,
		Left:     left,
	}

	precedence := p.curPrecedence()
	p.nextToken()

	// // 通过降低优先级，来达到右结合
	//if expression.Operator == "+" {
	//	expression.Right = p.parseExpression(precedence - 1)
	//} else {
	//	expression.Right = p.parseExpression(precedence)
	//}
	expression.Right = p.ParseExpression(precedence)

	return expression
}

func (p *Parser) Errors() []string {
	return p.errors
}

原文链接：https://blog.csdn.net/weixin_43786143/article/details/129320609