Add parsing and tacky generation for binary operators

Fix grammar to handle left associativity

Update parser for binary operators

Update tacky generation for binary operators

2 files changed, 125 insertions, 31 deletions

diff --git a/src/cljcc/parser.clj b/src/cljcc/parser.clj
index 8852d91..bee6d32 100644
--- a/src/cljcc/parser.clj
+++ b/src/cljcc/parser.clj
@@ -1,6 +1,7 @@
 (ns cljcc.parser
   (:require
-   [instaparse.core :as insta]))
+   [instaparse.core :as insta]
+   [clojure.pprint :as pp]))
 
 (def whitespace
   (insta/parser
@@ -14,11 +15,32 @@
     function = #'int\\b' identifier <'('> #'void\\b' <')'> <'{'> statement <'}'>
     statement = #'return\\b' exp <';'>
     exp = exp-prime
-    <exp-prime> = constant | unop-exp | <'('> exp-prime <')'>
+    <exp-prime> = <'('> exp-prime <')'> | unop-exp | constant-exp
     unop-exp = unop exp
     unop = #'-' | #'~'
     identifier = #'[a-zA-Z_]\\w*\\b'
-    constant = #'[0-9]+\\b'
+    constant-exp = #'[0-9]+\\b'
+    keyword = #'int\\b' | #'return\\b' | #'void\\b'"
+   :auto-whitespace whitespace))
+
+(def binop-parser
+  (insta/parser
+   "<program> = function+
+    function = #'int\\b' identifier <'('> #'void\\b' <')'> <'{'> statement <'}'>
+    statement = #'return\\b' exp <';'>
+    exp = exp-prime
+    <exp-prime> = mul-div-mod | add-exp | sub-exp
+    add-exp = exp-prime <'+'> mul-div-mod
+    sub-exp = exp-prime <'-'> mul-div-mod
+    <mul-div-mod> = term | mul-exp | div-exp | mod-exp
+    mul-exp = mul-div-mod <'*'> term
+    div-exp = mul-div-mod <'/'> term
+    mod-exp = mul-div-mod <'%'> term
+    <term> = constant-exp | unary-exp | <'('> exp-prime <')'>
+    unary-exp = unary-operator term
+    unary-operator = #'-' | #'~'
+    identifier = #'[a-zA-Z_]\\w*\\b'
+    constant-exp = #'[0-9]+\\b'
     keyword = #'int\\b' | #'return\\b' | #'void\\b'"
    :auto-whitespace whitespace))
 
@@ -26,7 +48,7 @@
   (not (insta/failure? result)))
 
 (defn parse [source]
-  (c-parser source))
+  (binop-parser source))
 
 (comment
 
@@ -41,6 +63,20 @@
    return -(((((10)))));
    }")
 
-  (parse "int main(void) {
+  (pp/pprint (parse "int main(void) {
    return -(((((10)))));
    }"))
+
+  (pp/pprint
+   (binop-parser
+    "int main(void) {
+    return -1 * 2 - ~3 * -(-4 + 5);
+     }"))
+
+  (pp/pprint
+   (binop-parser
+    "int main(void) {
+       return -2;
+     }"))
+
+  ())
diff --git a/src/cljcc/tacky.clj b/src/cljcc/tacky.clj
index 4772766..d87a909 100644
--- a/src/cljcc/tacky.clj
+++ b/src/cljcc/tacky.clj
@@ -23,45 +23,93 @@
    {:type :variable
     :value (create-identifier identifier)}))
 
-(defn constant [^String v]
+(defn constant-instruction [^String v]
   {:type :constant
    :value (Long. v)})
 
-(defn unop-operator [^String unop]
+(defn- unary-operator [^String unop]
   (condp = unop
     "~" :complement
     "-" :negate))
 
-(defn unary-instruction [unop src dst]
+(defn- binary-operator [binop]
+  (condp = binop
+    :add-exp :add
+    :sub-exp :sub
+    :mul-exp :mul
+    :div-exp :div
+    :mod-exp :mod))
+
+(defn- unary-instruction [unary-operator src dst]
   {:type :unary
-   :unary-operator unop
+   :unary-operator unary-operator
    :dst dst
    :src src})
 
+(defn- binary-instruction [binary-operator src1 src2 dst]
+  {:type :binary
+   :binary-operator binary-operator
+   :src1 src1
+   :src2 src2
+   :dst dst})
+
 (defn return-instruction [val]
   {:type :return
    :val val})
 
-(defn exp-instructions [exp]
-  (when-let [expr (second exp)]
-    (condp = (first expr)
-      :constant {:val (constant (second expr))}
-      :unop-exp (let [inner (exp-instructions (nth expr 2))
-                      dst (variable)
-                      src (:val inner)
-                      unop (unop-operator (second (second expr)))
-                      inst (unary-instruction unop  src dst)]
-                  {:val dst
-                   :instructions (conj (:instructions inner) inst)}))))
-
-(defn ret-instructions [exp]
+(def binary-exprs
+  #{:add-exp
+    :sub-exp
+    :mul-exp
+    :mod-exp
+    :div-exp})
+
+(defn- binary-expr? [v]
+  (contains? binary-exprs v))
+
+(declare expression-handler)
+
+(defn- constant-expr-handler [e]
+  {:val (constant-instruction (second e))})
+
+(defn- unary-expr-handler [e]
+  (let [inner (expression-handler (nth e 2))
+        dst (variable)
+        src (:val inner)
+        unary-operator (unary-operator (second (second e)))
+        instruction (unary-instruction unary-operator src dst)]
+    {:val dst
+     :instructions (flatten [(:instructions inner) instruction])}))
+
+(defn- binary-expr-handler [e]
+  (let [e1 (expression-handler (nth e 1))
+        e2 (expression-handler (nth e 2))
+        src1 (:val e1)
+        src2 (:val e2)
+        dst (variable)
+        binary-operator (binary-operator (first e))
+        instruction (binary-instruction binary-operator src1 src2 dst)]
+    {:val dst
+     :instructions (flatten [(:instructions e1) (:instructions e2) instruction])}))
+
+(defn- expression-handler [e]
+  (when-let [exp-type (first e)]
+    (cond
+      (= exp-type :constant-exp) (constant-expr-handler e)
+      (= exp-type :unary-exp) (unary-expr-handler e)
+      (binary-expr? exp-type) (binary-expr-handler e))))
+
+(defn- exp-instructions [exp]
+  (expression-handler (second exp)))
+
+(defn- ret-instructions [exp]
   (let [e (exp-instructions exp)
         val (:val e)
         instructions (:instructions e)]
-    (conj instructions (return-instruction val))))
+    (conj (vec instructions) (return-instruction val))))
 
-(defn statement-transform [_ret-keyword exp]
-  {:instructions (reverse (ret-instructions exp))})
+(defn- statement-transform [_ret-keyword exp]
+  {:instructions (remove nil? (ret-instructions exp))})
 
 (defn tacky-generate [ast]
   (reset! counter 0)
@@ -71,7 +119,19 @@
 
   (reset! counter 0)
 
-  (pp/pprint (tacky-generate (p/parse "int main(void) {return -~-8;}")))
+  (pp/pprint
+   (tacky-generate
+    (p/parse "int main(void) {return 1 * 2 - 3 * (4 + 5);}")))
+
+  (pp/pprint
+   (p/parse "int main(void) {return 1 * 2 - 3 * (4 + 5);}"))
+
+  (pp/pprint
+   (p/parse "int main(void) {return 1 + 2 + -3 + -(4 + 5);}"))
+
+  (pp/pprint
+   (tacky-generate
+    (p/parse "int main(void) {return 1 + 2 + -3 + -(4 + 5);}")))
 
   (pp/pprint
    (exp-instructions [:exp [:constant "2"]]))
@@ -104,14 +164,12 @@
   (pp/pprint
    (exp-instructions ex-exp))
 
-  (pp/pprint
-   (ret-instructions ex-ret))
-
   (def exprg
     "int main(void) {
      return -(~(-8));
    }")
 
-  (pp/pprint (parse "int main(void) {return 2;}"))
+  (pp/pprint
+   (ret-instructions ex-ret))
 
-  (pp/pprint (parse exprg)))
+  ())