1 ! Copyright (C) 2008, 2009 Doug Coleman, Daniel Ehrenberg.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: kernel accessors regexp.classes math.bits assocs sequences
4 arrays sets regexp.dfa math fry regexp.minimize ;
5 IN: regexp.disambiguate
9 : make-partition ( choices classes -- partition )
10 zip [ first ] partition [ values ] bi@ parts boa ;
12 : powerset-partition ( classes -- partitions )
13 [ length [ 2^ ] keep ] keep '[
14 _ <bits> _ make-partition
17 : partition>class ( parts -- class )
19 [ <or-class> ] bi@ <not-class> 2array <and-class> ;
21 : get-transitions ( partition state-transitions -- next-states )
22 [ in>> ] dip '[ _ at ] map prune ;
24 : disambiguate ( dfa -- nfa )
27 [ keys powerset-partition ] keep '[
29 [ _ get-transitions ] bi
33 ] change-transitions ;
35 : nfa>dfa ( nfa -- dfa )
38 construct-dfa minimize ;