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         //TODO(josuer08): Change this for a argv reader and all of the printing can
  31         // be moved to writing to a file or just use standalone with redirection not
  32         //quite sure about it.
  33         input := "[ a b ] ((a*b) + (5*5))-3"
  34
  35         variables, program := extractVariables(input)
  36         //fmt.Println(variables, program)
  37         Tree := AST{}
  38         firstPass(variables, program, &Tree)
  39         //fmt.Println(Tree)
  40         secondPass(&Tree)
  41         slices.Sort(variables)
  42         thirdPass(&Tree, variables)
  43         //printer(&Tree)
  44
  45 }
  46
  47 // printer si a function that prints in Reverse Pollish Notation the AST
  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                         } else {
 107                                 node.Right = &AST{Op: imm, Value: int(program[0]) - 48}
 108                         }
 109                 } else if slices.Contains(variables, program[0]) {
 110                         if node.Op != plus && node.Op != min && node.Op != mul && node.Op != div {
 111                                 node.Left = &AST{Op: arg, Value: int(program[0])}
 112                         } else {
 113                                 node.Right = &AST{Op: arg, Value: int(program[0])}
 114                         }
 115                 }
 116         }
 117         if len(program) > 1 {
 118                 firstPass(variables, program[1:], pass)
 119         }
 120 }
 121
 122 // secondPass takes an AST and reduces the operations that only include imm
 123 // values so the program results in a more compact one with precalculated imms
 124 func secondPass(node *AST) {
 125         if node.Op == arg {
 126                 return
 127         }
 128         if node.Op == imm {
 129                 return
 130         }
 131         if node.Right.Op == imm && node.Left.Op == imm {
 132                 switch node.Op {
 133                 case min:
 134                         node.Value = node.Left.Value - node.Right.Value
 135                 case plus:
 136                         node.Value = node.Left.Value + node.Right.Value
 137                 case mul:
 138                         node.Value = node.Left.Value * node.Right.Value
 139                 case div:
 140                         node.Value = node.Left.Value / node.Right.Value
 141                 }
 142                 node.Op = imm
 143                 node.Left = nil
 144                 node.Right = nil
 145                 return
 146         }
 147         if node.Left.Op != arg && node.Left.Op != imm {
 148                 secondPass(node.Left)
 149         }
 150         if node.Right.Op != arg && node.Right.Op != imm {
 151                 secondPass(node.Right)
 152         }
 153 }
 154
 155 func thirdPass(node *AST, variables []rune) {
 156         switch node.Op {
 157         case arg:
 158                 number, found := slices.BinarySearch(variables, rune(node.Value))
 159                 if found {
 160                         fmt.Printf("AR %d\n", number)
 161                 }
 162         case imm:
 163                 fmt.Printf("IM %d\n", node.Value)
 164         default:
 165                 switch node.Left.Op {
 166                 case arg:
 167                         number, valid := slices.BinarySearch(variables, rune(node.Left.Value))
 168                         if valid {
 169                                 fmt.Printf("AR %d\n", number)
 170                         }
 171                 case imm:
 172                         fmt.Printf("IM %d\n", node.Left.Value)
 173                 default:
 174                         thirdPass(node.Left, variables)
 175                 }
 176                 switch node.Right.Op {
 177                 case arg:
 178                         fmt.Println("SW")
 179                         number, valid := slices.BinarySearch(variables, rune(node.Right.Value))
 180                         if valid {
 181                                 fmt.Printf("AR %d\n", number)
 182                         }
 183                         fmt.Println("SW")
 184                 case imm:
 185                         fmt.Println("SW")
 186                         fmt.Printf("IM %d\n", node.Right.Value)
 187                         fmt.Println("SW")
 188                 default:
 189                         fmt.Println("PU")
 190                         thirdPass(node.Right, variables)
 191                         fmt.Println("SW")
 192                         fmt.Println("PO")
 193                 }
 194                 switch node.Op {
 195                 case mul:
 196                         fmt.Println("MU")
 197                 case div:
 198                         fmt.Println("DI")
 199                 case min:
 200                         fmt.Println("SU")
 201                 case plus:
 202                         fmt.Println("AD")
 203
 204                 }
 205
 206         }
 207
 208 }
 209
 210 // extractVariables receives the original program string and converts it in
 211 // two rune slices, the first containing the variables and a second containing
 212 // the trimmed program
 213 func extractVariables(input string) ([]rune, []rune) {
 214         variables := strings.Split(input, "]")
 215         // Cleaning out the variables that are gettting extracted
 216         variables[0] = strings.Split(variables[0], "[")[1]
 217         variables[0] = strings.Trim(variables[0], " ")
 218         cleanVariables := []rune(variables[0])
 219         var resultVariables []rune
 220         for _, v := range cleanVariables {
 221                 if v != ' ' {
 222                         resultVariables = append(resultVariables, v)
 223                 }
 224         }
 225         //Cleaning out the program that is getting extracted
 226         variables[1] = strings.Trim(variables[1], " ")
 227         cleanProgram := []rune(variables[1])
 228         var resultProgram []rune
 229         for _, v := range cleanProgram {
 230                 if v != ' ' {
 231                         resultProgram = append(resultProgram, v)
 232                 }
 233         }
 234         return resultVariables, resultProgram
 235 }