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.