Skip to content

Instantly share code, notes, and snippets.

@hkolbeck
Created April 23, 2010 05:29
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save hkolbeck/376226 to your computer and use it in GitHub Desktop.
Save hkolbeck/376226 to your computer and use it in GitHub Desktop.
package nfa
import "fmt"
type nfa struct {
Q []chan string
q0, F int
monitor chan int
input chan string
output chan string
running bool
current string
}
func (parent *nfa) controller() {
var active int
for parent.running {
select {
case in := <-parent.input: {
if !parent.running {
active++
parent.current = in
parent.Q[parent.q0] <- in
}
}
case m := <-parent.monitor: {
active += m
if active == 0 {
parent.running = false
parent.output <- fmt.Sprintf("Did not accept: %v\n", parent.current)
}
}
case <-parent.Q[parent.F] : {
parent.running = false
parent.output <- fmt.Sprintf("Accepted: %v\n", parent.current)
}
}
}
}
func (parent *nfa) state(inbound chan string, delta map[byte][]int, epsilon []int) {
for {
seen := make(map[string]bool, 100)
for parent.running {
input := <-inbound
if !seen[input] {
transitions, _ := delta[input[0]]
for _, t := range transitions {
parent.Q[t] <- input[1:]
parent.monitor <- 1
}
for _, t := range epsilon {
parent.Q[t] <- input[1:]
parent.monitor <- 1
}
seen[input] = true
}
parent.monitor <- -1
}
}
}
func NewNFA(Q, q0 int, delta []map[byte][]int, F []int) (in, out chan string) {
states := make([]chan string, Q + 1)
epsilon := make([][]int, Q)
in = make(chan string, 10)
out = make(chan string, 10)
for i := range states {
states[i] = make(chan string, 10)
}
for i := 0; i < Q; i++ {
epsilon[i], _ = delta[i]['\000']
}
for _,f := range F {
if len(epsilon[f]) < cap(epsilon[f]) {
epsilon[f] = epsilon[f][0:len(epsilon[f]) + 1]
} else {
temp := make([]int, len(epsilon[f]) + 1)
copy(temp, epsilon[f])
epsilon[f] = temp
epsilon[f][len(epsilon[f]) - 1] = len(states) - 1
}
}
n := &nfa{states, q0, Q + 1, make(chan int, 100), in, out, false, ""}
for i := 0; i < Q; i++ {
go n.state(states[i], delta[i], epsilon[i])
}
go n.controller()
return
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment