Skip to content

Instantly share code, notes, and snippets.

@belkadan belkadan/state_machine.coffee Secret
Created Apr 1, 2014

Embed
What would you like to do?
lex = (input) ->
while input != ""
input = input.trim()
matches = input.match(/^[a-zA-Z_]+/)
matches = input.match(/^".*?"|'.*?'/) unless matches
matches = input.match(/^\d+/) unless matches
matches = input.match(/^[-(),:>]/) unless matches
throw "unexpected character '#{input[0]}'" unless matches
[tok] = matches
input = input.substr(tok.length)
tok
isValidStateName = (name) ->
return /^(\d|'|")/.test(name)
class State
constructor: (@name, @start, @final) ->
@transitions = []
class Transition
class AnyTransition extends Transition
constructor: (@kind) ->
switch @kind
when 'letter', 'number', 'space', 'symbol'
else
throw "unknown set for 'any': #{@kind}"
toString: ->
"any #{@kind} -> #{this.destinationName || 'error'}"
match: (input) ->
switch @kind
when 'letter'
return input.substr(1) if /^[a-zA-Z_]/.test(input)
when 'number'
return input.substr(1) if /^\d/.test(input)
when 'space'
return input.substr(1) if /^[ \t]/.test(input)
when 'space'
return input.substr(1) if /^[^a-zA-Z_0-9 \t]/.test(input)
else
return null
class PlainTransition extends Transition
constructor: (@quotedText) ->
toString: ->
"#{@quotedText} -> #{this.destinationName || 'error'}"
match: (input) ->
return input.substr(@quotedText.length - 2) if input.substr(0, @quotedText.length - 2) == (@quotedText[1..-2])
return null
parseState = (tokens) ->
isStart = false
isFinal = false
if tokens[0] == 'start'
console.log("start!")
isStart = true
tokens.shift()
if tokens[0] == 'final'
isFinal = true
tokens.shift()
if tokens[0] == 'state'
tokens.shift()
name = tokens.shift()
throw "expected new state label, but got '#{name}'" unless isValidStateName(name)
throw "expected colon after state, but got '#{tokens[0]}'" unless tokens[0] == ':'
tokens.shift()
return new State(name, isStart, isFinal)
parseTransition = (tokens) ->
label = tokens.shift()
if label == 'any'
kind = tokens.shift()
transition = new AnyTransition(kind)
else
throw "expected transition label, but got '#{label}" unless /^['"]/.test(label)
transition = new PlainTransition(label)
arrowStart = tokens.shift()
throw "expected -> after transition label, but got '#{arrowStart}'" unless arrowStart == '-'
arrowEnd = tokens.shift()
throw "expected -> after transition label, but got '#{arrowStart}#{arrowEnd}'" unless arrowEnd == '>'
dst = tokens.shift()
unless dst == 'error'
throw "expected destination state label, but got '#{dst}'" unless isValidStateName(dst)
transition.destinationName = dst
return transition
parse = (tokens) ->
states = []
while tokens.length
switch tokens[0]
when 'state', 'start', 'final'
currentState = parseState(tokens)
states.push(currentState)
else
transition = parseTransition(tokens)
throw "no current state" unless currentState?
currentState.transitions.push(transition)
return states
class StateMachine
constructor: (states, @whitespaceSensitive) ->
console.log(states)
@states = {}
for state in states
throw "duplicate state #{state.name}" if @states[state.name]?
@states[state.name] = state
if state.start
throw "multiple start states: #{@startState.name} and #{state.name}" if @startState?
@startState = state
throw "missing start state" unless @startState?
for state in states
for transition in state.transitions
destination = transition.destinationName
continue unless destination?
raise "destination state #{destination} doesn't exist" unless @states[destination]?
match: (input, visitedStates = null) ->
@currentState = @startState
while input != ""
input = input.trim() unless @whitespaceSensitive
visitedStates.push(@currentState.name) if visitedStates?
input = this.transition(input)
return this.isFinal()
transition: (input) ->
for transition in @currentState.transitions
remainingInput = transition.match(input)
break if remainingInput?
if remainingInput?
@currentState = @states[transition.destinationName]
else
@currentState = null
return if @currentState? then remainingInput else ""
isError: () ->
!@currentState?
isFinal: () ->
@currentState?.final
window.runStateMachine = (machineDescription, inputText, whitespaceSensitive) ->
try
machine = new StateMachine(parse(lex(machineDescription)), whitespaceSensitive)
catch error
return "Error: #{error}"
output = for line in inputText.split("\n")
continue if line.trim() == ""
visitedStates = []
isMatch = machine.match(line, visitedStates)
result = line + ": "
result += visitedStates.join(', ')
if machine.currentState
result += ", #{machine.currentState.name} -- "
else
result += ", X -- "
result += if isMatch then "Match!" else "No match."
return output.join('\n')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.