Theory of Computation #7

Let’s say we want to parse the string: xzy. We need a function which takes the string and returns whether it parses or not.

For this I’m thinking about a function which takes the current state and character and returns the next state.

(get-state :S \x) -> :A
(get-state :A \z) -> :A
etc.

Ok. We work with non-deterministic grammars therefore there are several paths available. But let’s start with the first one. The filter function seems to do a fine job extracting our options.

(filter #(% :A) test-grammar)

which returns

({:A {\y :B}}
 {:A {\z :A}})

That’s helpful. Now, we need to get the correct candidate and extract the next state. I changed my initial design a bit. I started out with the following format: {:State [\character :State]} but changed it to two hashmaps because of the nature of the problem.

First we extract the values, i.e. the right-hand side of the candidates. Here’s the code for candidates:

code> (filter #(% :A) test-grammar)
({:A {\y :B}} {:A {\z :A}})

Now we can mapcat the right-hand side:

(mapcat vals candidates)

which returns

code> (mapcat vals candidates)
({\y :B} {\z :A})

The next step is to map the characters on that list. This is a nice characteristics of hashmaps because our characters are our keywords. Then we filter it and return the first one. That’s the next state.

(defn get-state
  "Returns the next state given a state
   and character"
  [state character]
  (let [candidates (filter #(% state) test-grammar)]
    (first
     (filter identity
             (map #(% character) (mapcat vals candidates))))))

And it passed all the tests:

(deftest test-get-state
  (is (= (get-state :S \x) :A) )
  (is (= (get-state :S \y) nil))
  (is (= (get-state :A \y) :B))
  (is (= (get-state :A \z) :A))
  (is (= (get-state :B nil) true)))

Oki doki. So, now that we have the state, we need a function which takes a string and looks at the return value of our get-state stuff. It stops if the returning state is either nil (not valid) or true (valid).

(check-string "xzy") -> true
(check-string "xab") -> false

The code is surprisingly super-straight forward.

(defn test-string
  "Takes an input string and checks if it
   valid according to the grammar"
  [input-string]
  (loop [current-state :S
         rest-string input-string]
    (cond (= current-state nil) false
          (= current-state true) true
          :else (recur
                 (get-state current-state (first rest-string))
                 (rest rest-string)))))

We just get the state, compare it and return true or false. Now let’s throw some tests in:

(deftest test-test-string
  (is (= (test-string "xzy") true))
  (is (= (test-string "xyz") false))
  (is (= (test-string "xab") false))
  (is (= (test-string "xzzy") true))
  (is (= (test-string "") false)))  

And that’s it. That was surprisingly easy. And the code is super nice and easy. I have to say pretty great.