in Doing Books, Theory of Computation

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.

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.

which returns

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:

Now we can mapcat the right-hand side:

which returns

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.

And it passed all the tests:

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

The code is surprisingly super-straight forward.

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

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

Write a Comment

Comment