golang 四则运算计算器yacc归约手写实现
来源：脚本之家
时间：2023-01-13 08:44:46 466浏览 收藏
对于一个Golang开发者来说，牢固扎实的基础是十分重要的，golang学习网就来带大家一点点的掌握基础知识点。今天本篇文章带大家了解《golang 四则运算计算器yacc归约手写实现》，主要介绍了计算器、四则运算、yacc、归约，希望对大家的知识积累有所帮助，快点收藏起来吧，否则需要时就找不到了！
缘起
最近拜读前桥和弥[日]的>
开头一章便是教读者使用lex/yacc工具
制作四则运算器
其中yacc的移进/归约/梯度下降的思想很有启发
于是使用golang练习之
目标
- 制作一个四则运算器, 从os.Stdin读入一行表达式, 然后输出计算过程和结果
- 支持+ - * /
- 支持左右括号
- 支持负数
难点
记号扫描(lexer)
- 逐字符扫描记号
- 单字符记号可直接识别, + - * / ( )
多字符记号, 此处只有浮点数, 通过有限状态的转换进行识别
+ '-' = INT_STATUS
+ 'd' = INT_STATUS
+ '.' = DOT_STATUS
+ 'SPACE | + | - | * | / | ( | )' = INITIAL
+ 'd' = FRAG_STATUS
+ 'SPACE | + | - | * | / | ( | )' = INITIAL
运算优先级
- /优先级最高, 可以立即归约计算
- 括号次之, 遇到右括号, 应当触发+ -归约
- 程序末尾, 没有新的记号剩余, 对+ -进行归约
识别负数
- 简单起见, 本程序总是使用浮点数作为基本计算单位
- 把负号识别为浮点数的可选部分: 浮点数 = -?d+(.d+)?
总体流程
- 从os.Stdin读入一行表达式字符串
- 逐字符扫描记号流, 放入记号队列
- 逐记号出队, 置入计算栈
- 判断栈顶是否符合归约条件, 是则进行计算
- 记号队列空, 对计算栈进行最终计算
- 输出结果
main.go
从os.Stdin循环读入行
调用lexer.Parse获得记号流
调用parser.Parse进行计算
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))
}
}
}
tokens/tokens.go
定义记号
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,
}
}
states/states.go
定义lexer的状态
type STATES int const INITIAL STATES = 1 const INT_STATUS STATES = 11 const DOT_STATUS STATES = 12 const FRAG_STATUS STATES = 13
lexer/lexer.go
记号扫描
type tLexerState struct {
state states.STATES
tokens []*tokens.Token
buffer []rune
i0 int
i1 int
d0 int
d1 int
}
func (me *tLexerState) AppendToken(t *tokens.Token) {
me.tokens = append(me.tokens, t)
}
func (me *tLexerState) AppendChar(it rune) {
me.buffer = append(me.buffer, it)
}
func (me *tLexerState) BufferSize() int {
return len(me.buffer)
}
func (me *tLexerState) IntSize() int {
return me.i1 - me.i0 + 1
}
func (me *tLexerState) FragSize() int {
return me.d1 - me.d0 + 1
}
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
}
func parseChar(state *tLexerState, i int, it rune) error {
var e error = nil
switch state.state {
case states.INITIAL:
e = parseCharWhenInitial(state, i, it)
break
case states.INT_STATUS:
e = parseCharWhenInt(state, i, it)
break
case states.DOT_STATUS:
e = parseCharWhenDot(state, i, it)
break
case states.FRAG_STATUS:
e = parseCharWhenFrag(state, i, it)
break
}
return e
}
func parseCharWhenInitial(state *tLexerState, i int, it rune) error {
if is_minus(it) || is_0_to_9(it) {
state.state = states.INT_STATUS
state.buffer = make([]rune, 0)
state.buffer = append(state.buffer, it)
state.i0 = i
state.i1 = i
} else if is_space(it){
return nil
} else if is_add(it) {
state.AppendToken(tokens.OfRune(tokens.ADD, it, i))
} else if is_sub(it) {
state.AppendToken(tokens.OfRune(tokens.SUB, it, i))
} else if is_mul(it) {
state.AppendToken(tokens.OfRune(tokens.MUL, it, i))
} else if is_div(it) {
state.AppendToken(tokens.OfRune(tokens.DIV, it, i))
} else if is_lb(it) {
state.AppendToken(tokens.OfRune(tokens.LB, it, i))
} else if is_rb(it) {
state.AppendToken(tokens.OfRune(tokens.RB, it, i))
} else {
return errors.New(fmt.Sprintf("parseCharWhenInitial, invalid char %c at %d", it, i))
}
return nil
}
func parseCharWhenInt(state *tLexerState, i int, it rune) error {
if is_0_to_9(it) {
if state.BufferSize() >= 10 {
return errors.New(fmt.Sprintf("too large int number at %v", i))
} else {
state.AppendChar(it)
state.i1 = i
}
} else if is_dot(it) {
state.AppendChar(it)
state.state = states.DOT_STATUS
} else if is_space(it) {
state.AppendToken(tokens.OfString(tokens.IntLiteral, string(state.buffer), state.i1))
state.state = states.INITIAL
} else if is_rb(it) {
state.AppendToken(tokens.OfString(tokens.IntLiteral, string(state.buffer), state.i1))
state.AppendToken(tokens.OfRune(tokens.RB, it, i))
state.state = states.INITIAL
} else if is_add(it) {
state.AppendToken(tokens.OfString(tokens.IntLiteral, string(state.buffer), state.i1))
state.AppendToken(tokens.OfRune(tokens.ADD, it, i))
state.state = states.INITIAL
} else if is_sub(it) {
state.AppendToken(tokens.OfString(tokens.IntLiteral, string(state.buffer), state.i1))
state.AppendToken(tokens.OfRune(tokens.SUB, it, i))
state.state = states.INITIAL
} else if is_mul(it) {
state.AppendToken(tokens.OfString(tokens.IntLiteral, string(state.buffer), state.i1))
state.AppendToken(tokens.OfRune(tokens.MUL, it, i))
state.state = states.INITIAL
} else if is_div(it) {
state.AppendToken(tokens.OfString(tokens.IntLiteral, string(state.buffer), state.i1))
state.AppendToken(tokens.OfRune(tokens.DIV, it, i))
state.state = states.INITIAL
} else {
return errors.New(fmt.Sprintf("parseCharWhenInt, invalid char %c at %d", it, i))
}
return nil
}
func parseCharWhenDot(state *tLexerState, i int, it rune) error {
if is_0_to_9(it) {
state.state = states.FRAG_STATUS
state.AppendChar(it)
state.d0 = i
state.d1 = i
} else {
return errors.New(fmt.Sprintf("parseCharWhenDot, invalid char %c at %d", it, i))
}
return nil
}
func parseCharWhenFrag(state *tLexerState, i int, it rune) error {
if is_0_to_9(it) {
if state.FragSize() >= 10 {
return errors.New(fmt.Sprintf("too many chars for a double value at %d", i))
} else {
state.AppendChar(it)
state.d1 = i
}
} else if is_space(it) {
state.AppendToken(tokens.OfString(tokens.DoubleLiteral, string(state.buffer), state.i1))
state.state = states.INITIAL
} else if is_add(it) {
state.AppendToken(tokens.OfString(tokens.DoubleLiteral, string(state.buffer), state.i1))
state.AppendToken(tokens.OfRune(tokens.ADD, it, i))
state.state = states.INITIAL
} else if is_sub(it) {
state.AppendToken(tokens.OfString(tokens.DoubleLiteral, string(state.buffer), state.i1))
state.AppendToken(tokens.OfRune(tokens.SUB, it, i))
state.state = states.INITIAL
} else if is_mul(it) {
state.AppendToken(tokens.OfString(tokens.DoubleLiteral, string(state.buffer), state.i1))
state.AppendToken(tokens.OfRune(tokens.MUL, it, i))
state.state = states.INITIAL
} else if is_div(it) {
state.AppendToken(tokens.OfString(tokens.DoubleLiteral, string(state.buffer), state.i1))
state.AppendToken(tokens.OfRune(tokens.DIV, it, i))
state.state = states.INITIAL
} else if is_rb(it) {
state.AppendToken(tokens.OfString(tokens.DoubleLiteral, string(state.buffer), state.i1))
state.AppendToken(tokens.OfRune(tokens.RB, it, i))
state.state = states.INITIAL
} else {
return errors.New(fmt.Sprintf("parseCharWhenFrag, invalid char %c at %d", it, i))
}
return nil
}
parser/tStackNode.go
定义计算栈的一个节点. 计算栈中有两种节点: 已归约的值节点, 和尚未计算的记号节点
type tStackNodeType int
const NODE_VALUE tStackNodeType = 1
const NODE_TOKEN tStackNodeType = 2
type tStackNode struct {
flag tStackNodeType
token *tokens.Token
value float64
}
func newValueNode(value float64) *tStackNode {
return &tStackNode{
flag: NODE_VALUE,
value: value,
token: nil,
}
}
func newTokenNode(token *tokens.Token) *tStackNode {
return &tStackNode{
flag: NODE_TOKEN,
token: token,
value: 0,
}
}
func (me *tStackNode) getTokenType() tokens.TOKENS {
switch me.flag {
case NODE_VALUE:
return tokens.DoubleLiteral
case NODE_TOKEN:
switch me.token.Token {
case tokens.IntLiteral:
fallthrough
case tokens.DoubleLiteral:
return tokens.DoubleLiteral
default:
return me.token.Token
}
}
return tokens.UNKNOWN
}
func (me *tStackNode) getDoubleValue() float64 {
switch me.flag {
case NODE_VALUE:
return me.value
case NODE_TOKEN:
switch me.token.Token {
case tokens.IntLiteral:
fallthrough
case tokens.DoubleLiteral:
v1,e1 := strconv.ParseFloat(me.token.Value, 64)
if e1 != nil {
panic(e1)
}
return v1
}
}
panic("value not avaiable")
}
parser/parser.go
type tParser struct {
tokens []*tokens.Token
stack []*tStackNode
total int
position int
}
func newParser(tokens []*tokens.Token) *tParser {
return &tParser{
tokens: tokens,
stack: make([]*tStackNode, 0),
total : len(tokens),
position: -1,
}
}
func (me *tParser) showStack() string {
lst := make([]string, 0)
for _,it := range me.stack {
switch it.flag {
case NODE_VALUE:
lst = append(lst, strconv.FormatFloat(it.value, 'f', 10, 64))
break
case NODE_TOKEN:
switch it.token.Token {
case tokens.DoubleLiteral:
fallthrough
case tokens.IntLiteral:
lst = append(lst, it.token.Value)
break
default:
lst = append(lst, it.token.Value)
break
}
}
}
return strings.Join(lst, " ")
}
func (me *tParser) moreToken() bool {
return me.position = me.total {
return nil
}
return me.tokens[me.position]
}
func (me *tParser) reduce() {
sCurrentStack := ""
var fnCheckState = func() {
sStackState := me.showStack()
if sStackState != sCurrentStack {
sCurrentStack = sStackState
fmt.Printf("stack => %s\n", sStackState)
}
}
for {
fnCheckState()
if me.reduceMulOrDiv() {
continue
}
if me.reduceBrackets() {
continue
}
if !me.moreToken() {
if me.reduceAddOrSub() {
break
}
}
fnCheckState()
//time.Sleep(1*time.Second)
break
}
}
func (me *tParser) stackPop() *tStackNode {
if me.isStackEmpty() {
return nil
}
var iStackSize = len(me.stack)
var last = me.stack[iStackSize - 1]
me.stack = me.stack[:(iStackSize-1)]
return last
}
func (me *tParser) stackPopN(n int) []*tStackNode {
if me.isStackEmpty() {
return nil
}
var iStackSize = len(me.stack)
if iStackSize
<h2>输出</h2>
<blockquote><p>=> 1+2*(3-4*(5/6+(7-8*9)))<br>stack => 1<br>stack => 1 +<br>stack => 1 + 2<br>stack => 1 + 2 *<br>stack => 1 + 2 * (<br>stack => 1 + 2 * ( 3<br>stack => 1 + 2 * ( 3 -<br>stack => 1 + 2 * ( 3 - 4<br>stack => 1 + 2 * ( 3 - 4 *<br>stack => 1 + 2 * ( 3 - 4 * (<br>stack => 1 + 2 * ( 3 - 4 * ( 5<br>stack => 1 + 2 * ( 3 - 4 * ( 5 /<br>stack => 1 + 2 * ( 3 - 4 * ( 5 / 6<br>stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333<br>stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 +<br>stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + (<br>stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7<br>stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7 -<br>stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7 - 8<br>stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7 - 8 *<br>stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7 - 8 * 9<br>stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7 - 72.0000000000<br>stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7 - 72.0000000000 )<br>stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + -65.0000000000<br>stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + -65.0000000000 )<br>stack => 1 + 2 * ( 3 - 4 * -64.1666666667<br>stack => 1 + 2 * ( 3 - -256.6666666667<br>stack => 1 + 2 * ( 3 - -256.6666666667 )<br>stack => 1 + 2 * 259.6666666667<br>stack => 1 + 519.3333333333<br>520.3333333333<br>=></p></blockquote>
<p>文中关于golang的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《golang 四则运算计算器yacc归约手写实现》文章吧，也可关注golang学习网公众号了解相关技术文章。</p>
声明：本文转载于：脚本之家 如有侵犯，请联系study_golang@163.com删除
相关阅读
更多>
-
261 收藏
-
191 收藏
-
198 收藏
最新阅读
更多>
-
140 收藏
-
147 收藏
-
378 收藏
-
255 收藏
-
287 收藏
-
393 收藏
-
310 收藏
-
110 收藏
-
412 收藏
-
423 收藏
-
274 收藏
-
379 收藏
课程推荐
更多>
-
- 前端进阶之JavaScript设计模式
- 设计模式是开发人员在软件开发过程中面临一般问题时的解决方案，代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景，打造一站式知识长龙服务，适合有JS基础的同学学习。
- 立即学习 543次学习
-
- GO语言核心编程课程
- 本课程采用真实案例，全面具体可落地，从理论到实践，一步一步将GO核心编程技术、编程思想、底层实现融会贯通，使学习者贴近时代脉搏，做IT互联网时代的弄潮儿。
- 立即学习 516次学习
-
- 简单聊聊mysql8与网络通信
- 如有问题加微信：Le-studyg；在课程中，我们将首先介绍MySQL8的新特性，包括性能优化、安全增强、新数据类型等，帮助学生快速熟悉MySQL8的最新功能。接着，我们将深入解析MySQL的网络通信机制，包括协议、连接管理、数据传输等，让
- 立即学习 500次学习
-
- JavaScript正则表达式基础与实战
- 在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
- 立即学习 487次学习
-
- 从零制作响应式网站—Grid布局
- 本系列教程将展示从零制作一个假想的网络科技公司官网，分为导航，轮播，关于我们，成功案例，服务流程，团队介绍，数据部分，公司动态，底部信息等内容区块。网站整体采用CSSGrid布局，支持响应式，有流畅过渡和展现动画。
- 立即学习 485次学习