Skip to content

Instantly share code, notes, and snippets.

@cjohnson318
Created May 29, 2019 13:54
Show Gist options
  • Save cjohnson318/2594e22c4d0f6773926391a0b8b7e11c to your computer and use it in GitHub Desktop.
Save cjohnson318/2594e22c4d0f6773926391a0b8b7e11c to your computer and use it in GitHub Desktop.
Simple Deterministic Push Down Automata in Kotlin
val pass: Unit = Unit
data class State(val state: String)
data class Event(val event: String)
data class StackSymbol(val symbol: String)
enum class StackActionType {
PUSH,
POP,
PASS,
}
data class StackAction(val type: StackActionType, val symbol: StackSymbol?)
data class CurrentStateEvent(val state: State, val event: Event, val peek: StackSymbol?)
data class NextStateAction(val state: State, val action: StackAction? = null)
class TransitionTable {
private var stateTable = mutableMapOf<CurrentStateEvent, NextStateAction>()
fun addTransition(current: State, event: Event, peek: StackSymbol?, next: State, action: StackAction? = null) {
val currentStateEvent = CurrentStateEvent(current, event, peek)
stateTable[currentStateEvent] = NextStateAction(next, action)
}
fun getNextState(currentStateEvent: CurrentStateEvent): NextStateAction? {
return when (currentStateEvent) {
in stateTable -> stateTable[currentStateEvent]
else -> null
}
}
}
class Stack<T> {
var stack = mutableListOf<T>()
fun push(item: T) {
stack.add(item)
}
fun pop(): T? {
return when {
stack.count() > 0 -> stack.removeAt(stack.count()-1)
else -> null
}
}
fun peek(): T? {
return when {
stack.count() > 0 -> stack[stack.count()-1]
else -> null
}
}
}
class DeterministicPushDownAutomata constructor(initial: State, val transitionTable: TransitionTable) {
val error = NextStateAction(State("error"))
var state = initial
var stack = Stack<StackSymbol>()
fun send(event: Event) {
val currentStateEvent = CurrentStateEvent(state, event, stack.peek())
val next = transitionTable.getNextState(currentStateEvent) ?: error
println("Received $event. Transitioning from $state to $next")
state = next.state
if (next.action != null) {
when (next.action.type) {
StackActionType.PUSH -> stack.push(next.action.symbol!!)
StackActionType.POP -> stack.pop()
StackActionType.PASS -> pass
}
}
}
}
fun main(args: Array<String>) {
val initial = State("initial")
val halt = State("halt")
val error = State("error")
val openParen = Event("open-paren")
val closeParen = Event("close-paren")
val semicolon = Event("EOL")
val openParenSymbol = StackSymbol("(")
val closeParenSymbol = StackSymbol(")")
val pushOpenParen = StackAction(StackActionType.PUSH, openParenSymbol)
val pushCloseParen = StackAction(StackActionType.PUSH, closeParenSymbol)
val popParen = StackAction(StackActionType.POP, null)
val table = TransitionTable()
table.addTransition(initial, openParen, null, initial, pushOpenParen)
table.addTransition(initial, openParen, openParenSymbol, initial, pushOpenParen)
table.addTransition(initial, openParen, closeParenSymbol, initial, pushOpenParen)
table.addTransition(initial, closeParen, null, error)
table.addTransition(initial, closeParen, openParenSymbol, initial, popParen)
table.addTransition(initial, closeParen, closeParenSymbol, initial, pushCloseParen)
table.addTransition(initial, semicolon, null, halt)
table.addTransition(initial, semicolon, openParenSymbol, error)
table.addTransition(initial, semicolon, closeParenSymbol, error)
val dpda = DeterministicPushDownAutomata(initial, table)
dpda.send(openParen)
dpda.send(openParen)
dpda.send(closeParen)
dpda.send(openParen)
dpda.send(closeParen)
dpda.send(closeParen)
dpda.send(semicolon)
println(dpda.state)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment