basis/regexp/disambiguate/disambiguate.factor

   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
   6
   7 TUPLE: parts in out ;
   8
   9 : make-partition ( choices classes -- partition )
  10     zip [ first ] partition [ values ] bi@ parts boa ;
  11
  12 : powerset-partition ( classes -- partitions )
  13     [ length [ 2^ ] keep ] keep '[
  14         _ <bits> _ make-partition
  15     ] map ;
  16
  17 : partition>class ( parts -- class )
  18     [ in>> ] [ out>> ] bi
  19     [ <or-class> ] bi@ <not-class> 2array <and-class> ;
  20
  21 : get-transitions ( partition state-transitions -- next-states )
  22     [ in>> ] dip '[ _ at ] map prune ;
  23
  24 : disambiguate ( dfa -- nfa )
  25     [
  26         [
  27             [ keys powerset-partition ] keep '[
  28                 [ partition>class ]
  29                 [ _ get-transitions ] bi
  30             ] H{ } map>assoc
  31             [ drop ] assoc-filter
  32         ] assoc-map
  33     ] change-transitions ;
  34
  35 : nfa>dfa ( nfa -- dfa )
  36     construct-dfa
  37     minimize disambiguate
  38     construct-dfa minimize ;