# 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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.