RegExpOps.hs

module RegExpOps where
import RegExp
import List

nullable r =
  case r of
    Zero -> False
    One -> True
    S _ -> False
    r1 :& r2  -> nullable r1 && nullable r2
    r1 :! r2  -> nullable r1 || nullable r2
    r1 :-! r2 -> nullable r1 && not (nullable r2)
    Many re -> True
    Some re -> nullable re

--nullR r = if nullable r then e else z

first r =
  case r of
    Zero -> []
    One -> []
    S i -> [i]
    r1 :& r2  -> first r1 `union` (if nullable r1 then first r2 else [])
    r1 :! r2  -> first r1 `union` first r2
--  r1 :-! r2 -> first r1 \\ first r2         -- this is wrong!
    r1 :-! r2 -> first r1 -- `union` first r2
    Many re -> first re
    Some re -> first re

follow i r =
  case r of
    Zero -> Zero
    One -> Zero
    S i' -> if i'==i then One else Zero
    r1 :& r2  -> follow i r1 & r2 ! (if nullable r1 then follow i r2 else Zero) 
    r1 :! r2  -> follow i r1 ! follow i r2
    r1 :-! r2 -> follow i r1 -! follow i r2
    Many re -> follow i re & Many re
    Some re ->  follow i re & Many re

factors r = (nullable r,[(i,r')|i<-sort (first r),let r'=follow i r,r'/=Zero])

factorsR (n,fs) = (if n then e else z) ! alts [S i & r|(i,r)<-fs]