Go手写四则运算计算器：实现Yacc归约逻辑
本文介绍如何在Go语言中手动实现一个简单的四则运算计算器，核心在于模拟Yacc编译器的移进/归约（Shift/Reduce）思想。通过设计状态机进行词法分析，识别数字、操作符及括号，构建记号流；随后使用栈结构进行语法分析，根据优先级规则实时执行乘除或括号的归约计算，最终输出结果。
项目目标与核心原理
本项目旨在编写一个基于Go语言的命令行计算器，能够接收形如 1+2*(3-4) 的输入并返回计算结果。为了实现这一目标，我们深入理解编译原理中的“移进/归约”算法，将其从复杂的语法解析简化为支持加、减、乘、除以及左右括号的数值计算。
整体架构流程
系统的运行分为两个主要阶段：词法扫描（Lexer）和语法分析/计算（Parser）。
- 读取输入：程序从标准输入循环读取一行表达式字符串。
- 词法扫描：逐字符遍历字符串，利用有限状态机将字符序列转换为记号（Token）队列，包括整数、浮点数、运算符和括号。
- 语法分析：将生成的记号逐一压入计算栈。每压入一个新记号，立即检查栈顶是否存在满足优先级的“归约条件”。
- 执行归约：若检测到可归约模式（如连续的数字与运算符），则弹出相应节点进行运算，并将结果作为一个新的值节点重新压回栈中。
- 输出结果：当所有记号处理完毕后，对栈内剩余内容进行最终清理与计算，得到最终结果。
第一阶段：记号扫描 (Lexer)
词法分析的核心是将输入的文本拆解为具有语义的类型。本例采用简单的手动有限状态机来实现，而非依赖外部工具。
第1步：定义状态与记号类型
首先定义必要的状态常量和记号标识。记号主要用于区分整型字面量、浮点字面量以及各种二元运算符。
package tokens
type TOKENS string
const IntLiteral TOKENS = "INT"
const DoubleLiteral TOKENS = "DBL"
const ADD TOKENS = "ADD"
const SUB TOKENS = "SUB"
const MUL TOKENS = "MUL"
const DIV TOKENS = "DIV"
const LB TOKENS = "LB"
const RB TOKENS = "RB"
const UNKNOWN TOKENS = "UNKNOWN"
type Token struct {
Token TOKENS
Value string
Position int
}
func OfRune(t TOKENS, r rune, from int) *Token {
return &Token {
Token: t,
Value : string(r),
Position: from,
}
}
func OfString(t TOKENS, s string, from int) *Token {
return &Token {
Token: t,
Value : s,
Position: from,
}
}第2步：实现有限状态转换 (States & Lexer)
状态机主要包含三种内部状态：INITIAL（初始/空闲态）、INT_STATUS（正在解析整数）和 FRAG_STATUS（正在解析小数部分）。遇到空格时触发当前数字的归约并重置状态。以下是解析主函数：
type STATES int
const INITIAL STATES = 1
const INT_STATUS STATES = 11
const DOT_STATUS STATES = 12
const FRAG_STATUS STATES = 13在 lexer.go 中，通过遍历每一行输入字符串（并在末尾附加 '\n' 以确保最后一个数字被正确捕获），驱动状态机跳转：
func Parse(line string) ([]*tokens.Token, error) {
var state = &(tLexerState{
state: states.INITIAL,
tokens: make([]*tokens.Token, 0),
buffer: make([]rune, 0),
i0 : 0,
i1 : 0,
d0: 0,
d1: 0,
})
for i, it := range line + "\n" {
e := parseChar(state, i, it)
if e != nil {
return nil, e
}
}
return state.tokens, nil
}具体逻辑如下：
- 初始状态 (
INITIAL)：如果是数字或负号，转入INT_STATUS；如果是一元运算符（如+ - * / ( )），直接生成对应的符号记号。 - 整数状态 (
INT_STATUS)：继续吸收数字字符；如果遇到小数点，存入缓冲并转入DOT_STATUS；如果遇到运算符或右括号，将缓冲区的内容作为IntLiteral或DoubleLiteral提交，并重置状态。 - 小数状态 (
DOT_STATUS&FRAG_STATUS)：负责解析小数点后的尾数片段，直至遇到非数字字符时提交浮点记号。
第二阶段：栈式语法分析与计算 (Parser)
解析器通过维护一个混合类型的栈来工作，栈中既可以存放待处理的记号（Token Node），也可以存放已经计算出的中间结果（Value Node）。
第3步：栈节点设计与类型映射
为了支持不同类型的节点，我们定义了统一的栈节点结构，并提供了方便的工厂方法：
type tStackNodeType int
const NODE_VALUE tStackNodeType = 1
const NODE_TOKEN tStackNodeType = 2
type tStackNode struct {
flag tStackNodeType
token *tokens.Token
value float64
} // ... 省略工厂函数代码 tStackNode 还提供了 getTokenType() 方法，用于统一判断节点在栈中的角色，例如将整型和浮点型都视为 DoubleLiteral，以便匹配优先级相同的相邻数值。
第4步：核心的归约循环
在每次获取新记号并压栈后，都会调用 reduce() 方法来尝试执行归约。这是体现移进/归约思想的关键步骤：
func (me *tParser) reduce() {
// ... 打印堆栈状态 ...
for {
// 1. 优先处理高优先级的乘法或除法
if me.reduceMulOrDiv() { continue }
// 2. 处理括号内的内容
if me.reduceBrackets() { continue }
// 3. 如果没有更多记号了，执行最后的加减合并
if !me.moreToken() {
if me.reduceAddOrSub() { break }
}
// ... 结束本轮检测 ...
break
}
}- 乘法归约 (
reduceMulOrDiv)：检测栈顶是否为 “数值 -> 乘号 -> 数值”。如果是，弹出这三个节点，执行数学运算，并将结果作为NODE_VALUE压回栈顶。此优先级最高。 - 括号归约 (
reduceBrackets)：当检测到栈顶是左括号(LB)时，开始持续弹出元素直到遇见右括号(RB)。在弹出的过程中，依次执行加法或减法，计算出括号内的总和，最后将总和压回栈并丢弃括号。 - 加减归约 (
reduceAddOrSub)：通常在没有高优先级算子时可推迟，但在无新记号输入时（!me.moreToken()）需要强制清空栈内剩余的加减序列，得出最终答案。
主程序入口与交互体验
结合上述模块，在主程序中建立无限循环以提供交互式命令行体验：
func main() {
reader := bufio.NewReader(os.Stdin)
for {
fmt.Printf("=> ")
arrBytes, _, err := reader.ReadLine()
if err != nil {
panic(err.Error())
}
line := strings.TrimSpace(string(arrBytes))
expression := line
tokens, e := lexer.Parse(expression)
if e != nil {
println(e.Error())
} else {
e,v := parser.Parse(tokens)
if e != nil {
println(e.Error())
}
fmt.Println(strconv.FormatFloat(v, 'f', 10, 64))
}
}
}程序会打印每一步的归约过程，展示栈的动态变化，便于调试和学习。以下是复杂表达式的运行示例：
=> 1+2*(3-4*(5/6+(7-8*9)))
stack => 1
stack => 1 +
stack => 1 + 2
stack => 1 + 2 *
stack => 1 + 2 * (
stack => 1 + 2 * ( 3
... (中间过程省略) ...
stack => 1 + 519.3333333333
520.3333333333以上就是Go手写四则运算计算器yacc归约实现的详细内容，更多关于Golang基础教程的资料请关注本站其它相关文章！
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
