Created
April 23, 2010 05:29
-
-
Save hkolbeck/376226 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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