Skip to content

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
You can’t perform that action at this time.