golang Four-step operation calculator Yacc reduction handwriting implementation

origin

Recently I read Maehashi Kazuya [hiro]'s <<Homemade Programming Language>>

The first chapter is to teach readers to use the lex/yacc tool

Making four calculators

Among them, the idea of yacc's advancement/reduction/gradient descent is very inspiring

So use golang to practice

Target

Make a four-character operator, read a line of expressions, and then output the calculation process and results
Support + - * /
Support left and right brackets
Support negative numbers

difficulty

Scan the mark (lexer)

Scan the mark by character
Single character tokens can be directly identified, + - * / ( )

Multi-character tokens, where there are only floating-point numbers, and are recognized by finite state conversion.

<INITIAL> + '-' = INT_STATUS

<INITIAL> + 'd' = INT_STATUS

<INT_STATUS> + '.' = DOT_STATUS

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

<DOT_STATUS> + 'd' = FRAG_STATUS

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

Computation priority

/The highest priority is possible, and the calculation can be immediately reduced
Next is brackets. When the closing bracket is encountered, +-reduction should be triggered.
At the end of the program, no new marks remain, and a +-reduce

Identify negative numbers

For simplicity, this program always uses floating point numbers as the basic calculation unit
Identify the negative sign as an optional part of a floating point number: Floating point number = -?d+(.d+)?

Overall process

Read into a one-line expression string
Scan the mark stream character by character and put it into the mark queue
Dequeue by sign, place the calculation stack
Determine whether the top of the stack meets the reduction conditions, then perform calculations
The mark queue is empty, and the final calculation of the calculation stack is performed.
Output result

Reading from loop into line

Call to get the token stream

Call to calculate

func main() {
    reader := ()
    for {
        ("=> ")
        arrBytes, _, err := ()
        if err != nil {
            panic(())
        }
        line := (string(arrBytes))
        expression := line
        tokens, e := (expression)
        if e != nil {
            println(())
        } else {
            e,v := (tokens)
            if e != nil {
                println(())
            }
            ((v, 'f', 10, 64))
        }
    }
}

tokens/

Definition mark

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/

Define the state of lexer

type STATES int
const INITIAL STATES = 1
const INT_STATUS STATES = 11
const DOT_STATUS STATES = 12
const FRAG_STATUS STATES = 13

lexer/

Scan the mark

type tLexerState struct {
    state 
    tokens []*
    buffer []rune
    i0 int
    i1 int
    d0 int
    d1 int
}
func (me *tLexerState) AppendToken(t *) {
     = append(, t)
}
func (me *tLexerState) AppendChar(it rune) {
     = append(, it)
}
func (me *tLexerState) BufferSize() int {
    return len()
}
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) ([]*, error) {
    var state = &(tLexerState{
        state: ,
        tokens: make([]*, 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 , nil
}
func parseChar(state *tLexerState, i int, it rune) error {
    var e error = nil
    switch  {
    case :
        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) {
         = states.INT_STATUS
         = make([]rune, 0)
         = append(, it)
        state.i0 = i
        state.i1 = i
    } else if is_space(it){
        return nil
    } else if is_add(it) {
        ((, it, i))
    } else if is_sub(it) {
        ((, it, i))
    } else if is_mul(it) {
        ((, it, i))
    } else if is_div(it) {
        ((, it, i))
    } else if is_lb(it) {
        ((, it, i))
    }  else if is_rb(it) {
        ((, it, i))
    } else {
        return (("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 () >= 10 {
            return (("too large int number at %v", i))
        } else {
            (it)
            state.i1 = i
        }
    } else if is_dot(it) {
        (it)
         = states.DOT_STATUS
    } else if is_space(it) {
        ((, string(), state.i1))
         = 
    } else if is_rb(it) {
        ((, string(), state.i1))
        ((, it, i))
         = 
    }  else if is_add(it) {
        ((, string(), state.i1))
        ((, it, i))
         = 
    } else if is_sub(it) {
        ((, string(), state.i1))
        ((, it, i))
         = 
    } else if is_mul(it) {
        ((, string(), state.i1))
        ((, it, i))
         = 
    } else if is_div(it) {
        ((, string(), state.i1))
        ((, it, i))
         = 
    } else {
        return (("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) {
         = states.FRAG_STATUS
        (it)
        state.d0 = i
        state.d1 = i
    } else {
        return (("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 () >= 10 {
            return (("too many chars for a double value at %d", i))
        } else {
            (it)
            state.d1 = i
        }
    } else if is_space(it) {
        ((, string(), state.i1))
         = 
    } else if is_add(it) {
        ((, string(), state.i1))
        ((, it, i))
         = 
    } else if is_sub(it) {
        ((, string(), state.i1))
        ((, it, i))
         = 
    } else if is_mul(it) {
        ((, string(), state.i1))
        ((, it, i))
         = 
    } else if is_div(it) {
        ((, string(), state.i1))
        ((, it, i))
         = 
    } else if is_rb(it) {
        ((, string(), state.i1))
        ((, it, i))
         = 
    } else {
        return (("parseCharWhenFrag, invalid char %c at %d", it, i))
    }
    return nil
}

parser/

Define a node on the calculation stack. There are two nodes in the calculation stack: a reduced value node, and a notation node that has not been calculated yet

type tStackNodeType int
const NODE_VALUE tStackNodeType = 1
const NODE_TOKEN tStackNodeType = 2
type tStackNode struct {
    flag tStackNodeType
    token *
    value float64
}
func newValueNode(value float64) *tStackNode {
    return &tStackNode{
        flag: NODE_VALUE,
        value: value,
        token: nil,
    }
}
func newTokenNode(token *) *tStackNode {
    return &tStackNode{
        flag: NODE_TOKEN,
        token: token,
        value: 0,
    }
}
func (me *tStackNode) getTokenType()  {
    switch  {
    case NODE_VALUE:
        return 
    case NODE_TOKEN:
        switch  {
        case :
            fallthrough
        case :
            return 
        default:
            return 
        }
    }
    return 
}
func (me *tStackNode) getDoubleValue() float64 {
    switch  {
    case NODE_VALUE:
        return 
    case NODE_TOKEN:
        switch  {
        case :
            fallthrough
        case :
            v1,e1 := (, 64)
            if e1 != nil {
                panic(e1)
            }
            return v1
        }
    }
    panic("value not avaiable")
}

parser/

type tParser struct {
    tokens []*
    stack []*tStackNode
    total int
    position int
}
func newParser(tokens []*)  *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  {
        switch  {
        case NODE_VALUE:
            lst = append(lst, (, 'f', 10, 64))
            break
        case NODE_TOKEN:
            switch  {
            case :
                fallthrough
            case :
                lst = append(lst, )
                break
            default:
                lst = append(lst, )
                break
            }
        }
    }
    return (lst, " ")
}
func (me *tParser) moreToken() bool {
    return  <  - 1
}
func (me *tParser) nextToken() * {
    if !() {
        return nil
    }
    ++
    return ()
}
func (me *tParser) currentToken() * {
    if  >=  {
        return nil
    }
    return []
}
func (me *tParser) reduce() {
    sCurrentStack := ""
    var fnCheckState = func() {
        sStackState := ()
        if sStackState != sCurrentStack {
            sCurrentStack = sStackState
            ("stack => %s\n", sStackState)
        }
    }
    for {
        fnCheckState()
        if () {
            continue
        }
        if () {
            continue
        }
        if !() {
            if () {
                break
            }
        }
        fnCheckState()
        //(1*)
        break
    }
}
func (me *tParser) stackPop() *tStackNode {
    if () {
        return nil
    }
    var iStackSize = len()
    var last = [iStackSize - 1]
     = [:(iStackSize-1)]
    return last
}
func (me *tParser) stackPopN(n int) []*tStackNode {
    if () {
        return nil
    }
    var iStackSize = len()
    if iStackSize < n {
        return nil
    }
    var lstTailItems = [(iStackSize - n):]
     = [:(iStackSize-n)]
    return lstTailItems
}
func (me *tParser) stackTakeN(n int) []*tStackNode {
    if () {
        return nil
    }
    var iStackSize = len()
    if iStackSize < n {
        return nil
    }
    var lstHeadItems = [:n]
     = [n+1:]
    return lstHeadItems
}
func (me *tParser) stackPush(it *tStackNode) {
     = append(, it)
}
func (me *tParser) reduceMulOrDiv() bool {
    if () {
        return false
    }
    if (, , ) {
        var lstTailNodes = (3)
        v1 := lstTailNodes[0].getDoubleValue()
        v2 := lstTailNodes[2].getDoubleValue()
        var v = v1*v2
        (newValueNode(v))
        return true
    } else if (, , ) {
        var lstTailNodes = (3)
        v1 := lstTailNodes[0].getDoubleValue()
        v2 := lstTailNodes[2].getDoubleValue()
        if v2 == 0 {
            panic(("div by zero, %v / %v", v1, v2))
        }
        var v = v1/v2
        (newValueNode(v))
        return true
    }
    return false
}
func (me *tParser) reduceBrackets() bool {
    if () {
        return false
    }
    if () {
        rb := ()
        var v float64 = 0
        for {
            if (, ) {
                var lstTailNodes = (2)
                v += lstTailNodes[1].getDoubleValue()
                (newValueNode(v))
                return true
            } else if (, ) {
                var lstTailNodes = (2)
                v1 := lstTailNodes[1].getDoubleValue()
                v = v + v1
            } else if (, ) {
                var lstTailNodes = (2)
                v1 := lstTailNodes[1].getDoubleValue()
                v = v - v1
            } else {
                panic(("LB not found at %v", ))
            }
        }
    }
    return false
}
func (me *tParser) reduceAddOrSub() bool {
    var v float64 = 0
    for {
        if () {
            break
        }
        if (, ) {
            var lstTailNodes = (2)
            v1 := lstTailNodes[1].getDoubleValue()
            v = v + v1
        } else if (, ) {
            var lstTailNodes = (2)
            v1 := lstTailNodes[1].getDoubleValue()
            v = v - v1
        } else if len()==1 && () {
            it := ()
            v += ()
            (newValueNode(v))
            return true
        } else {
            panic("invalid expression")
        }
    }
    return false
}
func (me *tParser) isStackEmpty() bool {
    return len() == 0
}
func (me *tParser) isStackRMatch(args...) bool {
    var iArgsSize = len(args)
    if iArgsSize <= 0 {
        return false
    }
    var iStackSize = len()
    if iStackSize < iArgsSize {
        return false
    }
    for i,it := range args {
        var n = iStackSize - iArgsSize + i
        var xStackNode = [n]
        if it != () {
            return false
        }
    }
    return true
}
func (me *tParser) isStackLMatch(args...) bool {
    var iArgsSize = len(args)
    if iArgsSize <= 0 {
        return false
    }
    var iStackSize = len()
    if iStackSize < iArgsSize {
        return false
    }
    for i,it := range args {
        var xStackNode = [i]
        if it != () {
            return false
        }
    }
    return true
}
func (me *tParser) parse() (error, float64) {
    for {
        t := ()
        if t == nil {
            break
        }
        (newTokenNode(t))
        ()
    }
    var iStackSize = len()
    if iStackSize == 1 && [0].getTokenType() ==  {
        return nil, [0].getDoubleValue()
    }
    panic(("failed parsing expression %s", ()))
}
func Parse(tokens []*) (error, float64) {
    parser := newParser(tokens)
    return ()
}

Output

=> 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
=>

The above is the detailed content of the golang four-step operation calculator yacc reduction handwritten implementation. For more information about golang four-step operation calculator yacc reduction, please pay attention to my other related articles!