Instantly share code, notes, and snippets.

Embed
What would you like to do?
A pushdown automata in coffeescript
createResult = (state, symbols) -> {
resultState: state
pushSymbols: symbols.reverse()
}
createRule = (state, input, symbol, result) -> {
currentState: state
inputChar: input
stackSymbol: symbol
ruleResult: result
match: (s, i, y) -> true if (this.currentState == s && this.inputChar == i && this.stackSymbol == y)
}
createMachine = (rules, startState, initialSymbol, finalStates) -> {
transitionRules: rules
currentState: startState
symbolStack: [ initialSymbol ]
acceptanceStates: finalStates
update: (r) ->
this.symbolStack.push x for x in r.pushSymbols
this.currentState = r.resultState
read: (c) ->
return -1 if this.currentState == -1
y = this.symbolStack.pop()
for rule in this.transitionRules
if rule.match this.currentState, c, y
return this.update rule.ruleResult
# no rules matched, enter dead configuration
this.symbolStack.push y
this.currentState = -1
readAll: (s) -> this.read x for x in s.split ''
acceptedInput: () -> this.currentState in this.acceptanceStates
}
runMachine = (s) ->
selectStmtRules = [
createRule 0, 'i', 'S', createResult 3, [ 'A', 'S' ]
createRule 3, 'f', 'A', createResult 1, [ 'B' ]
createRule 1, 'i', 'S', createResult 3, [ 'A', 'S' ]
createRule 1, 'i', 'B', createResult 3, [ 'A', 'B' ]
createRule 1, 'e', 'B', createResult 2, [ 'C', 'D', 'E' ]
createRule 2, 'l', 'C', createResult 2, [ ]
createRule 2, 's', 'D', createResult 2, [ ]
createRule 2, 'e', 'E', createResult 1, [ ]
]
machine = createMachine selectStmtRules, 0, 'S', [ 1 ]
history = machine.readAll s
alert "Accepted: " + machine.acceptedInput() + " States: " + history.join ", "
runMachine "ifelse"
runMachine "ifelseelse"
runMachine "ififelseelse"
runMachine "ifi"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment