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