compiler.go

   1 package main
   2
   3 import (
   4         "fmt"
   5         "strings"
   6
   7         "golang.org/x/exp/slices"
   8 )
   9
  10 type op int
  11
  12 const (
  13         imm op = iota
  14         arg
  15         plus
  16         min
  17         mul
  18         div
  19 )
  20
  21 type AST struct {
  22         Op     op
  23         Left   *AST
  24         Right  *AST
  25         Value  int
  26         Parent *AST
  27 }
  28
  29 func main() {
  30         //a := &AST{Op: imm, N: 5
  31         //b := &AST{Op: plus, A: a, B: &AST{Op: arg, N: 0}}
  32         input := "[ a b ] ((a*b) + (5*5))-3"
  33         //input := "[ a b ] (a*a) + (5*5)"
  34
  35         variables, program := extractVariables(input)
  36
  37         fmt.Println(variables, program)
  38         Tree := AST{}
  39         firstPass(variables, program, &Tree)
  40         fmt.Println(Tree)
  41         secondPass(&Tree)
  42         slices.Sort(variables)
  43         thirdPass(&Tree, variables)
  44         printer(&Tree)
  45
  46 }
  47
  48 func printer(tree *AST) {
  49         switch {
  50         case tree.Op == imm:
  51                 fmt.Print(tree.Value)
  52         case tree.Op == arg:
  53                 fmt.Printf("%c", tree.Value)
  54         default:
  55                 fmt.Print("(")
  56                 switch tree.Op {
  57                 case min:
  58                         fmt.Print("-")
  59                 case plus:
  60                         fmt.Print("+")
  61                 case div:
  62                         fmt.Print("/")
  63                 case mul:
  64                         fmt.Print("*")
  65                 }
  66                 fmt.Print(",")
  67                 printer(tree.Left)
  68                 fmt.Print(",")
  69                 printer(tree.Right)
  70                 fmt.Print(")")
  71
  72         }
  73 }
  74
  75 // firstPass Is a function that makes the first pass of the compiler,
  76 // it converts the variable and program into an AST
  77 func firstPass(variables, program []rune, node *AST) {
  78         pass := node
  79         switch program[0] {
  80         case '-':
  81                 node.Op = min
  82         case '+':
  83                 node.Op = plus
  84         case '*':
  85                 node.Op = mul
  86         case '/':
  87                 node.Op = div
  88         case '(':
  89                 if node.Left == nil {
  90                         node.Left = &AST{}
  91                         node.Left.Parent = node
  92                         pass = node.Left
  93                 } else {
  94                         node.Right = &AST{}
  95                         node.Right.Parent = node
  96                         pass = node.Right
  97                 }
  98         case ')':
  99                 pass = node.Parent
 100
 101         default:
 102                 if program[0] > 47 && program[0] < 58 {
 103                         var zeroOp op
 104                         if node.Op == zeroOp {
 105                                 node.Left = &AST{Op: imm, Value: int(program[0]) - 48}
 106                                 //a := &AST{Op: imm, N: 5
 107                         } else {
 108                                 node.Right = &AST{Op: imm, Value: int(program[0]) - 48}
 109                         }
 110                 } else if slices.Contains(variables, program[0]) {
 111                         //var zeroOp op
 112                         if node.Op != plus && node.Op != min && node.Op != mul && node.Op != div {
 113                                 node.Left = &AST{Op: arg, Value: int(program[0])}
 114                                 //a := &AST{Op: imm, N: 5
 115                         } else {
 116                                 node.Right = &AST{Op: arg, Value: int(program[0])}
 117                         }
 118
 119                 }
 120
 121         }
 122         if len(program) > 1 {
 123                 firstPass(variables, program[1:], pass)
 124
 125         }
 126         return
 127
 128 }
 129
 130 // secondPass takes an AST and reduces the operations that only include imm
 131 // values so the program results in a more compact one with precalculated imms
 132 func secondPass(node *AST) {
 133         if node.Op == arg {
 134                 return
 135         }
 136         if node.Op == imm {
 137                 return
 138         }
 139         if node.Right.Op == imm && node.Left.Op == imm {
 140
 141                 switch node.Op {
 142                 case min:
 143                         node.Value = node.Left.Value - node.Right.Value
 144                 case plus:
 145                         node.Value = node.Left.Value + node.Right.Value
 146                 case mul:
 147                         node.Value = node.Left.Value * node.Right.Value
 148                 case div:
 149                         node.Value = node.Left.Value / node.Right.Value
 150                 }
 151                 node.Op = imm
 152                 node.Left = nil
 153                 node.Right = nil
 154                 return
 155         }
 156         if node.Left.Op != arg && node.Left.Op != imm {
 157                 secondPass(node.Left)
 158         }
 159         if node.Right.Op != arg && node.Right.Op != imm {
 160                 secondPass(node.Right)
 161         }
 162 }
 163
 164 func thirdPass(node *AST, variables []rune) {
 165         /////////////////////////////////////////THINKING SPACE/////////////////////
 166         //
 167         //   If I am a imm I just load to R0
 168         //   If I am an arg I just load to R0
 169         //
 170         //
 171         //   If I am an operator then I put my answer to my father  on R0
 172         //   If my left child is a imm or arg just call it and then SW
 173         //   If my right child is a imm or arg just call it then SW then operate
 174         //   If my left is an operand then call it(not sure about this one)
 175         //   If my right is an operand PU then call it then SW then PO then SW
 176         //   If i am an operand at the end always just operate AD MU DI SU
 177         //
 178         ////////////////////////////////////////////////////////////////////////////
 179         switch node.Op {
 180         case arg:
 181                 number, found := slices.BinarySearch(variables, rune(node.Value))
 182                 if found {
 183                         fmt.Printf("AR %d\n", number)
 184                 }
 185
 186         case imm:
 187                 fmt.Printf("IM %d\n", node.Value)
 188         default:
 189                 switch node.Left.Op {
 190                 case arg:
 191                         number, valid := slices.BinarySearch(variables, rune(node.Left.Value))
 192                         if valid {
 193                                 fmt.Printf("AR %d\n", number)
 194                         }
 195                 case imm:
 196                         fmt.Printf("IM %d\n", node.Left.Value)
 197                 default:
 198                         thirdPass(node.Left, variables)
 199                 }
 200
 201                 switch node.Right.Op {
 202                 case arg:
 203                         fmt.Println("SW")
 204                         number, valid := slices.BinarySearch(variables, rune(node.Right.Value))
 205                         if valid {
 206                                 fmt.Printf("AR %d\n", number)
 207                         }
 208                         fmt.Println("SW")
 209                 case imm:
 210                         fmt.Println("SW")
 211                         fmt.Printf("IM %d\n", node.Right.Value)
 212                         fmt.Println("SW")
 213                 default:
 214                         fmt.Println("PU")
 215                         thirdPass(node.Right, variables)
 216                         fmt.Println("SW")
 217                         fmt.Println("PO")
 218                 }
 219
 220                 //need to think about which kind of child nodes make me want to PU & PO
 221                 switch node.Op {
 222                 case mul:
 223                         fmt.Println("MU")
 224                 case div:
 225                         fmt.Println("DI")
 226                 case min:
 227                         fmt.Println("SU")
 228                 case plus:
 229                         fmt.Println("AD")
 230
 231                 }
 232
 233         }
 234
 235 }
 236
 237 // extractVariables receives the original program string and converts it in
 238 // two rune slices, the first containing the variables and a second containing
 239 // the trimmed program
 240 func extractVariables(input string) ([]rune, []rune) {
 241         variables := strings.Split(input, "]")
 242         // Cleaning out the variables that are gettting extracted
 243         variables[0] = strings.Split(variables[0], "[")[1]
 244         variables[0] = strings.Trim(variables[0], " ")
 245         cleanVariables := []rune(variables[0])
 246         var resultVariables []rune
 247         for _, v := range cleanVariables {
 248                 if v != ' ' {
 249                         resultVariables = append(resultVariables, v)
 250                 }
 251         }
 252
 253         //Cleaning out the program that is getting extracted
 254         variables[1] = strings.Trim(variables[1], " ")
 255         cleanProgram := []rune(variables[1])
 256         var resultProgram []rune
 257         for _, v := range cleanProgram {
 258                 if v != ' ' {
 259                         resultProgram = append(resultProgram, v)
 260
 261                 }
 262
 263         }
 264
 265         return resultVariables, resultProgram
 266 }