Theory of Computation #2

Exercise 1.1.2: Write a lexical analyzer directly from the following transition diagram. And from ex3. Build a transition table from the diagram and write a lexical analyzer based on that table.

I use Clojure again and want to write it in an intelligent way. OK, the idea is that I have a function which takes the current state and the next symbol. Depending on the transitions it returns a new state.

I use this format because I can then use it recursively.

I will decode the states in the following matter.

Start is: State 0
From start to letter: State 1
From start to colon: State 2
From colon to equal: State 3
From start to digit: State 4

Therefore we have the following transitions:

(def transitionsex2
  [{:letter 1 :colon 2 :digit 4} ; state 0
   {:digit 1 :letter 1 :EOL true} ; state 1 
   {:equal 3} ; state 2
   {:EOL true} ; state 3
   {:digit 4 :EOL true} ; state 4
   ])

Thanks to this data structure our function is super easy. The saying about data structures seems to be true:

Smart data structures and dumb code works a lot better than the other way around. — esr

Which you can see looking at our function:

(defn transition
  "Takes a state and symbol and returns
   the next state"
  [state symbol]
  ((transitionsex2 state) symbol))

Pretty neat, huh? Lastly, finally some tests to test if our function seem to work:

(deftest ex2
  (is (= (transition 0 :letter) 1))
  (is (= (transition 3 :EOL) true))
  (is (= (transition 1 :letter) 1))
  (is (= (transition 4 :float) nil)))

And the tests successfully passed. Great