The following source code is tested in DrScheme, version 4.1.4.
The first version of automaton.
#lang slideshow
(define b-machine-states
'((init (c more))
(more (a more)
(d more)
(r end))
(end (r end))))
(define (b-machine stream)
(letrec ([walker (lambda (state stream)
(or (empty? stream)
(let ([transitions
(cdr (assv state b-machine-states))])
(let ([1st (first stream)])
(let ([new-state (assv 1st transitions)])
(if new-state
(walker (cadr new-state) (rest stream))
false))))))])
(walker 'init stream)))
(b-machine '(c a r))
(b-machine '(c a d r))
(b-machine '(c a x))
The goto version of automaton.
#lang scheme
(define b-machine
(letrec ([init
(lambda (stream)
(or (empty? stream)
(case (first stream)
[(c) (more (rest stream))]
[else false])))]
[more
(lambda (stream)
(or (empty? stream)
(case (first stream)
[(a) (more (rest stream))]
[(d) (more (rest stream))]
[(r) (end (rest stream))]
[else false])))]
[end
(lambda (stream)
(or (empty? stream)
(case (first stream)
[(r) (end (rest stream))]
[else false])))])
init))
(b-machine '(c a r))
(b-machine '(c a d r))
(b-machine '(c a x))
The second version of automaton.
#lang scheme
(define-syntax automaton
(syntax-rules (-> :)
[(_ init-state
(state : (cndn -> new-state) ...)
...)
(letrec ([state
(lambda (stream)
(or (empty? stream)
(case (first stream)
[cndn (new-state (rest stream))]
...
[else false])))]
...)
init-state)]))
(define b-machine
(automaton init
(init : ((c) -> more))
(more : ((a) -> more)
((d) -> more)
((r) -> end))
(end : ((r) -> end))))
(b-machine '(c a r))
(b-machine '(c a d r))
(b-machine '(c a x))
The following code is really an elegant DSL for automaon.
(automaton init
(init : ((c) -> more))
(more : ((a) -> more)
((d) -> more)
((r) -> end))
(end : ((r) -> end)))
I have also implemented the first and goto version of automaton in Ruby.
The first version of automaton in Ruby
$b_machine_states = {
"init" => {"c" => "more"},
"more" => {"a" => "more",
"d" => "more",
"r" => "end"},
"end" => {"r" => "end"}}
def walker(state, stream)
if stream.empty?
return true
end
first = stream[0]
transitions = $b_machine_states[state]
new_state = transitions[first]
if new_state == nil
return false
else
rest = stream[1, stream.length()]
return walker(new_state, rest)
end
end
def b_machine(stream)
walker("init", stream)
end
print b_machine("car") , "\n"
print b_machine("cadr") , "\n"
print b_machine("cax") , "\n"
The goto version of automaton in Ruby
class Automaton
def accept(stream)
return init(stream)
end
private
def init(stream)
if stream.empty?
return true
end
first = stream[0]
case first
when "c"
return more(rest(stream))
else
false
end
end
def more(stream)
if stream.empty?
return true
end
first = stream[0]
case first
when "a"
return more(rest(stream))
when "d"
return more(rest(stream))
when "r"
return terminate(rest(stream))
else
return false
end
end
def terminate(stream)
if stream.empty?
return true
end
first = stream[0]
case first
when "r"
return terminate(rest(stream))
else
return false
end
end
def rest(stream)
return stream[1, stream.length()]
end
end
auto = Automaton.new()
print auto.accept("car") , "\n"
print auto.accept("cadr") , "\n"
print auto.accept("cax"), "\n"
For the second version of automaton, I can't find a way to implement it in Ruby because Ruby does not have a macro system similar to Scheme. I am happy to know if anyone has a solution.
No comments:
Post a Comment