Expression -> AST -> Intermediate code -> C code

ast.go

package main

import (
    "os"
    "io"
    "fmt"
    "unicode"
)

type ASTNode interface {
    toInst(*[]Inst)
    wDepth(depth int, w io.Writer)
}

type Inst interface {
    toC(w io.Writer)
}

type MemLoad string

type Operator int

type Bin struct {
    Op    rune
    Left  ASTNode
    Right ASTNode
}

type Value string

const (
    AddOp Operator = iota
    SubOp
    MulOp
    DivOp
)

func main() {
    expr := []rune(os.Args[1])
    ast, err := parseTree(expr)
    if err != nil {
        panic(err)
    }
    f, err := os.Create("calc.c")
    if err != nil {
        panic(err)
    }
    ASTDumpToC(f, ast)
    f.Close()
}

func ASTWriteTo(w io.Writer, ast ASTNode) {
    ast.wDepth(0, w)
}

func ASTDumpToC(w io.Writer, ast ASTNode) {
    s := "#include <stdio.h>\n\nint main(void)\n{\n    int stk[512], *p = stk, x, y;\n"
    fmt.Fprintf(w, s)

    var insts []Inst
    ast.toInst(&insts)

    for _,inst := range insts {
        inst.toC(w)
    }

    s = "    printf(\"%%d\\n\", *stk);\n    return 0;\n}\n"
    fmt.Fprintf(w, s)
}

func parseTree(rr []rune) (ASTNode, error) {
    var ast []ASTNode
    var oper []rune

    for i := 0; i < len(rr); i++ {
        switch {
        default:
            if unicode.IsPrint(rr[i]) {
                return nil, fmt.Errorf("ast: unknown rune: %c", rr[i])
            }
            return nil, fmt.Errorf("ast: unknown rune: %U", rr[i])
        case rr[i] == '(':
            oper = append(oper, '(')
        case rr[i] == ')':
            for oper[len(oper)-1] != '(' {
                y, x := ast[len(ast)-1], ast[len(ast)-2]
                ast = ast[:len(ast)-2]

                ast = append(ast, &Bin{
                    Op: oper[len(oper)-1],
                    Left: x,
                    Right: y,
                })

                oper = oper[:len(oper)-1]
            }
            oper = oper[:len(oper)-1]
        case rr[i] == '+' || rr[i] == '-':
            for len(oper) > 0 && validPlus(oper) {
                y, x := ast[len(ast)-1], ast[len(ast)-2]
                ast = ast[:len(ast)-2]

                ast = append(ast, &Bin{
                    Op: oper[len(oper)-1],
                    Left: x,
                    Right: y,
                })

                oper = oper[:len(oper)-1]
            }
            oper = append(oper, rr[i])
        case rr[i] == '*' || rr[i] == '/':
            for len(oper) > 0 && validMult(oper) {
                y, x := ast[len(ast)-1], ast[len(ast)-2]
                ast = ast[:len(ast)-2]

                ast = append(ast, &Bin{
                    Op: oper[len(oper)-1],
                    Left: x,
                    Right: y,
                })

                oper = oper[:len(oper)-1]
            }
            oper = append(oper, rr[i])
        case unicode.IsSpace(rr[i]):
            // do nothing
        case unicode.IsDigit(rr[i]):
            s := i

            for i < len(rr) && unicode.IsDigit(rr[i]) {
                i++
            }

            ast = append(ast, Value(rr[s:i]))
            i--
        }
    }

    for len(oper) > 0 {
        if oper[len(oper)-1] == '(' {
            return nil, fmt.Errorf("ast: mismatched parenthesis")
        }

        y, x := ast[len(ast)-1], ast[len(ast)-2]
        ast = ast[:len(ast)-2]

        ast = append(ast, &Bin{
            Op: oper[len(oper)-1],
            Left: x,
            Right: y,
        })

        oper = oper[:len(oper)-1]
    }

    return ast[0], nil
}

func validPlus(oper []rune) bool {
    top := oper[len(oper)-1]
    return top != '('
}

func validMult(oper []rune) bool {
    top := oper[len(oper)-1]
    return top != '(' && top != '+' && top != '-'
}

func (v Value) wDepth(depth int, w io.Writer) {
    spaces(depth, w)
    fmt.Fprintf(w, "%d\n", v)
}

func (v Value) toInst(insts *[]Inst) {
    *insts = append(*insts, MemLoad(v))
}

func (expr *Bin) wDepth(depth int, w io.Writer) {
    spaces(depth, w)
    fmt.Fprintf(w, "%c\n", expr.Op)
    expr.Left.wDepth(depth + 1, w)
    expr.Right.wDepth(depth + 1, w)
}

func (expr *Bin) toInst(insts *[]Inst) {
    var i Inst

    expr.Left.toInst(insts)
    expr.Right.toInst(insts)

    switch expr.Op {
    case '+':
        i = AddOp
    case '-':
        i = SubOp
    case '*':
        i = MulOp
    case '/':
        i = DivOp
    }

    *insts = append(*insts, i)
}

func spaces(depth int, w io.Writer) {
    for i := 0; i < depth; i++ {
        fmt.Fprintf(w, "  ")
    }
}

func (op Operator) toC(w io.Writer) {
    fmt.Fprintf(w, "    y = *--p;\n    x = *--p;\n")

    switch op {
    case AddOp:
        fmt.Fprintf(w, "    *p++ = x + y;\n")
    case SubOp:
        fmt.Fprintf(w, "    *p++ = x - y;\n")
    case MulOp:
        fmt.Fprintf(w, "    *p++ = x * y;\n")
    case DivOp:
        fmt.Fprintf(w, "    *p++ = x / y;\n")
    }
}

func (mem MemLoad) toC(w io.Writer) {
    fmt.Fprintf(w, "    *p++ = %s;\n", mem)
}