99精品欧美一区,男人的天堂视频在线观看免费,午夜福利视频看片

緣起

最近拜讀前橋和彌[日]的<<自制編程語言>>

開頭一章便是教讀者使用lex/yacc工具

制作四則運(yùn)算器

其中yacc的移進(jìn)/歸約/梯度下降的思想很有啟發(fā)

于是使用golang練習(xí)之

目標(biāo)

制作一個(gè)四則運(yùn)算器, 從os.Stdin讀入一行表達(dá)式, 然后輸出計(jì)算過程和結(jié)果
支持+ - * /
支持左右括號(hào)
支持負(fù)數(shù)

難點(diǎn)

記號(hào)掃描(lexer)

逐字符掃描記號(hào)
單字符記號(hào)可直接識(shí)別, + - * / ( )

多字符記號(hào), 此處只有浮點(diǎn)數(shù), 通過有限狀態(tài)的轉(zhuǎn)換進(jìn)行識(shí)別

<INITIAL> + '-' = INT_STATUS

<INITIAL> + 'd' = INT_STATUS

<INT_STATUS> + '.' = DOT_STATUS

<INT_STATUS> + 'SPACE | + | - | * | / | ( | )' = INITIAL

<DOT_STATUS> + 'd' = FRAG_STATUS

<FRAG_STATUS> + 'SPACE | + | - | * | / | ( | )' = INITIAL

運(yùn)算優(yōu)先級(jí)

/優(yōu)先級(jí)最高, 可以立即歸約計(jì)算
括號(hào)次之, 遇到右括號(hào), 應(yīng)當(dāng)觸發(fā)+ -歸約
程序末尾, 沒有新的記號(hào)剩余, 對+ -進(jìn)行歸約

識(shí)別負(fù)數(shù)

簡單起見, 本程序總是使用浮點(diǎn)數(shù)作為基本計(jì)算單位
把負(fù)號(hào)識(shí)別為浮點(diǎn)數(shù)的可選部分: 浮點(diǎn)數(shù) = -?d+(.d+)?

總體流程

從os.Stdin讀入一行表達(dá)式字符串
逐字符掃描記號(hào)流, 放入記號(hào)隊(duì)列
逐記號(hào)出隊(duì), 置入計(jì)算棧
判斷棧頂是否符合歸約條件, 是則進(jìn)行計(jì)算
記號(hào)隊(duì)列空, 對計(jì)算棧進(jìn)行最終計(jì)算
輸出結(jié)果

main.go

從os.Stdin循環(huán)讀入行

調(diào)用lexer.Parse獲得記號(hào)流

調(diào)用parser.Parse進(jìn)行計(jì)算

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

定義記號(hào)

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的狀態(tài)

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

記號(hào)掃描

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

定義計(jì)算棧的一個(gè)節(jié)點(diǎn). 計(jì)算棧中有兩種節(jié)點(diǎn): 已歸約的值節(jié)點(diǎn), 和尚未計(jì)算的記號(hào)節(jié)點(diǎn)

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 - 1
}
func (me *tParser) nextToken() *tokens.Token {
 if !me.moreToken() {
  return nil
 }
 me.position++
 return me.currentToken()
}
func (me *tParser) currentToken() *tokens.Token {
 if 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 < n {
  return nil
 }
 var lstTailItems = me.stack[(iStackSize - n):]
 me.stack = me.stack[:(iStackSize-n)]
 return lstTailItems
}
func (me *tParser) stackTakeN(n int) []*tStackNode {
 if me.isStackEmpty() {
  return nil
 }
 var iStackSize = len(me.stack)
 if iStackSize < n {
  return nil
 }
 var lstHeadItems = me.stack[:n]
 me.stack = me.stack[n+1:]
 return lstHeadItems
}
func (me *tParser) stackPush(it *tStackNode) {
 me.stack = append(me.stack, it)
}
func (me *tParser) reduceMulOrDiv() bool {
 if me.isStackEmpty() {
  return false
 }
 if me.isStackRMatch(tokens.DoubleLiteral, tokens.MUL, tokens.DoubleLiteral) {
  var lstTailNodes = me.stackPopN(3)
  v1 := lstTailNodes[0].getDoubleValue()
  v2 := lstTailNodes[2].getDoubleValue()
  var v = v1*v2
  me.stackPush(newValueNode(v))
  return true
 } else if me.isStackRMatch(tokens.DoubleLiteral, tokens.DIV, tokens.DoubleLiteral) {
  var lstTailNodes = me.stackPopN(3)
  v1 := lstTailNodes[0].getDoubleValue()
  v2 := lstTailNodes[2].getDoubleValue()
  if v2 == 0 {
panic(fmt.Sprintf("div by zero, %v / %v", v1, v2))
  }
  var v = v1/v2
  me.stackPush(newValueNode(v))
  return true
 }
 return false
}
func (me *tParser) reduceBrackets() bool {
 if me.isStackEmpty() {
  return false
 }
 if me.isStackRMatch(tokens.RB) {
  rb := me.stackPop()
  var v float64 = 0
  for {
if me.isStackRMatch(tokens.LB, tokens.DoubleLiteral) {
 var lstTailNodes = me.stackPopN(2)
 v += lstTailNodes[1].getDoubleValue()
 me.stackPush(newValueNode(v))
 return true
} else if me.isStackRMatch(tokens.ADD, tokens.DoubleLiteral) {
 var lstTailNodes = me.stackPopN(2)
 v1 := lstTailNodes[1].getDoubleValue()
 v = v + v1
} else if me.isStackRMatch(tokens.SUB, tokens.DoubleLiteral) {
 var lstTailNodes = me.stackPopN(2)
 v1 := lstTailNodes[1].getDoubleValue()
 v = v - v1
} else {
 panic(fmt.Sprintf("LB not found at %v", rb.token.Position))
}
  }
 }
 return false
}
func (me *tParser) reduceAddOrSub() bool {
 var v float64 = 0
 for {
  if me.isStackEmpty() {
break
  }
  if me.isStackRMatch(tokens.ADD, tokens.DoubleLiteral) {
var lstTailNodes = me.stackPopN(2)
v1 := lstTailNodes[1].getDoubleValue()
v = v + v1
  } else if me.isStackRMatch(tokens.SUB, tokens.DoubleLiteral) {
var lstTailNodes = me.stackPopN(2)
v1 := lstTailNodes[1].getDoubleValue()
v = v - v1
  } else if len(me.stack)==1 && me.isStackRMatch(tokens.DoubleLiteral) {
it := me.stackPop()
v += it.getDoubleValue()
me.stackPush(newValueNode(v))
return true
  } else {
panic("invalid expression")
  }
 }
 return false
}
func (me *tParser) isStackEmpty() bool {
 return len(me.stack) == 0
}
func (me *tParser) isStackRMatch(args...tokens.TOKENS) bool {
 var iArgsSize = len(args)
 if iArgsSize <= 0 {
  return false
 }
 var iStackSize = len(me.stack)
 if iStackSize < iArgsSize {
  return false
 }
 for i,it := range args {
  var n = iStackSize - iArgsSize + i
  var xStackNode = me.stack[n]
  if it != xStackNode.getTokenType() {
return false
  }
 }
 return true
}
func (me *tParser) isStackLMatch(args...tokens.TOKENS) bool {
 var iArgsSize = len(args)
 if iArgsSize <= 0 {
  return false
 }
 var iStackSize = len(me.stack)
 if iStackSize < iArgsSize {
  return false
 }
 for i,it := range args {
  var xStackNode = me.stack[i]
  if it != xStackNode.getTokenType() {
return false
  }
 }
 return true
}
func (me *tParser) parse() (error, float64) {
 for {
  t := me.nextToken()
  if t == nil {
break
  }
  me.stackPush(newTokenNode(t))
  me.reduce()
 }
 var iStackSize = len(me.stack)
 if iStackSize == 1 && me.stack[0].getTokenType() == tokens.DoubleLiteral {
  return nil, me.stack[0].getDoubleValue()
 }
 panic(fmt.Sprintf("failed parsing expression %s", me.showStack()))
}
func Parse(tokens []*tokens.Token) (error, float64) {
 parser := newParser(tokens)
 return parser.parse()
}

輸出

=> 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 + 2 * ( 3 -
stack => 1 + 2 * ( 3 - 4
stack => 1 + 2 * ( 3 - 4 *
stack => 1 + 2 * ( 3 - 4 * (
stack => 1 + 2 * ( 3 - 4 * ( 5
stack => 1 + 2 * ( 3 - 4 * ( 5 /
stack => 1 + 2 * ( 3 - 4 * ( 5 / 6
stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333
stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 +
stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + (
stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7
stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7 -
stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7 - 8
stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7 - 8 *
stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7 - 8 * 9
stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7 - 72.0000000000
stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7 - 72.0000000000 )
stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + -65.0000000000
stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + -65.0000000000 )
stack => 1 + 2 * ( 3 - 4 * -64.1666666667
stack => 1 + 2 * ( 3 - -256.6666666667
stack => 1 + 2 * ( 3 - -256.6666666667 )
stack => 1 + 2 * 259.6666666667
stack => 1 + 519.3333333333
520.3333333333
=>

以上就是golang 四則運(yùn)算計(jì)算器 yacc 歸約手寫實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于golang四則運(yùn)算計(jì)算器yacc歸約的資料請關(guān)注本站其它相關(guān)文章！

美國穩(wěn)定服務(wù)器

版權(quán)聲明：本站文章來源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學(xué)習(xí)參考，不代表本站立場，如有內(nèi)容涉嫌侵權(quán)，請聯(lián)系alex-e#qq.com處理。

排名優(yōu)化：網(wǎng)站排名優(yōu)化方法有什么，如何做有效果

老域名：怎樣才算老域名，老域名建站有什么影響

內(nèi)容優(yōu)化：關(guān)鍵字排名要做哪些方面的優(yōu)化，怎樣做

技巧：網(wǎng)站轉(zhuǎn)化率究竟是什么，有什么提升的技巧

一下吧：外貿(mào)站優(yōu)化有哪些基本的做法和注意事項(xiàng)

概要：競價(jià)推廣費(fèi)用大概要多少呢，競價(jià)推廣好不好

一下吧：SEO中site是什么意思，作用和應(yīng)用是怎樣的

郵箱：付費(fèi)郵箱有哪些優(yōu)勢，付費(fèi)郵箱挑選要考慮什么

集群是什么意思：集群是什么意思，都有哪些優(yōu)勢呢