GrammarProducts (empty) → 0.0.0.2

raw patch · 16 files changed

+2107/−0 lines, 16 filesdep +ADPfusiondep +FormalGrammarsdep +HaTeXsetup-changed

Dependencies added: ADPfusion, FormalGrammars, HaTeX, PrimitiveArray, ansi-wl-pprint, base, bytestring, cmdargs, containers, data-default, lens, newtype, parsers, semigroups, transformers, trifecta

Files

FormalLanguage/GrammarProduct.hs +67/−0
FormalLanguage/GrammarProduct/Op/Add.hs +60/−0
FormalLanguage/GrammarProduct/Op/Chomsky.hs +157/−0
FormalLanguage/GrammarProduct/Op/Chomsky/Proof.hs +76/−0
FormalLanguage/GrammarProduct/Op/Common.hs +37/−0
FormalLanguage/GrammarProduct/Op/Greibach.hs +135/−0
FormalLanguage/GrammarProduct/Op/Greibach/Proof.hs +161/−0
FormalLanguage/GrammarProduct/Op/Linear.hs +73/−0
FormalLanguage/GrammarProduct/Op/Power.hs +27/−0
FormalLanguage/GrammarProduct/Op/Subtract.hs +34/−0
FormalLanguage/GrammarProduct/Parser.hs +355/−0
GramProd.hs +130/−0
GrammarProducts.cabal +116/−0
LICENSE +675/−0
Setup.hs +2/−0
changelog +2/−0

+ FormalLanguage/GrammarProduct.hs view

@@ -0,0 +1,67 @@++-- | This module contains the top-level functionality required to define+-- "products of grammars" (or more sloppily "how to multiply dynamic+-- programming algorithms"). Some operators (like '(><)') will check if both+-- grammars are compatible with the operation and fail if not.+--+-- TODO Later on we probably will be able to multiply without restrictions.++module FormalLanguage.GrammarProduct+  ( (><)+  , gAdd+  , gSubtract+  , gPower+  ) where++import Data.Monoid++import FormalLanguage.CFG.Grammar++import FormalLanguage.GrammarProduct.Op.Greibach as Greibach+import FormalLanguage.GrammarProduct.Op.Chomsky  as Chomsky+import FormalLanguage.GrammarProduct.Op.Linear   as Linear+import FormalLanguage.GrammarProduct.Op.Add+import FormalLanguage.GrammarProduct.Op.Subtract as S+import FormalLanguage.GrammarProduct.Op.Power as P++++-- |++gAdd g h = runAdd $ (Add g) <> (Add h)++gSubtract g h = S.subtract g h++gPower = P.power++++-- | The product of two grammars.+--+-- In general, it is quite hard to define the product of two context-free+-- grammars in a way that keeps associativity and also "does what we want it to+-- do" (see paper). For linear grammars it is much easier. Also, for grammars+-- in certain normal forms, a simpler definition is possible. Due to this, we+-- make the choice of the actual way on how to multiply based on the type of+-- grammars given. This, however, should only affect the resulting rules, not+-- the (multi-tape) language that the operations yields.+--+-- TODO I think, left-linear could reasonably be expanded to both, left- and+-- right-linear and maybe linear in general.+--+-- NOTE A proof for associativity is possible, but generally hard, so we prefer+-- to let the framework perform the proof for us.++(><) :: Grammar -> Grammar -> Grammar+g >< h+  | isLeftLinear g && isLeftLinear h = runLinear $ Linear g <> Linear h+--  | isChomskyNF  g && isChomskyNF  h = runCNF $ CNF g <> CNF h+--  | isGreibachNF g && isGreibachNF h = runTwoGNF $ TwoGNF g <> TwoGNF h+  | otherwise                        = error "Grammars in general CFG form are not handled. You need to convert into either Greibach- or Chomsky normal form. This might change in the future"++-- | The addition operation defined for two grammars of the same dimension. It+-- forms a monoid under the 'Add' newtype.++(.+) :: Grammar -> Grammar -> Grammar+g .+ h = runAdd $ Add g <> Add h+

+ FormalLanguage/GrammarProduct/Op/Add.hs view

@@ -0,0 +1,60 @@+{-# LANGUAGE FlexibleInstances #-}++module FormalLanguage.GrammarProduct.Op.Add where++import Control.Lens+import Control.Lens.Fold+import Control.Newtype+import Data.List (genericReplicate)+import Data.Monoid hiding ((<>))+import Data.Semigroup+import qualified Data.Set as S+import Text.Printf++import FormalLanguage.CFG.Grammar++++-- | Add two grammars. Implemented as the union of production rules without any+-- renaming.++newtype Add a = Add {runAdd :: a}++++-- | Note that the semigroup on Add will create a new rule S_gh -> S_g | S_h in+-- case two start symbols with different rhs exist (If S_g, S_h are the same,+-- there is no problem).++instance Semigroup (Add Grammar) where+  (Add l) <> (Add r)+    | gDim l /= gDim r+    = error $ printf "ERROR: grammars \n%s\n and \n%s\n have different dimensions, cannot unify. (add %d %d)"+                (show l)+                (show r)+                (gDim l)+                (gDim r)+    | otherwise = Add $ Grammar (l^.tsyms <> r^.tsyms)+                                (l^.nsyms <> r^.nsyms) -- TODO add the newly created symbol to the non-terminals (or maybe just run ``fix T+N 's from the rules?'')+                                (l^.epsis <> r^.epsis)+                                (l^.rules <> r^.rules <> t)+                                s+                                (l^.name  <> r^.name)+    where s = case (l^.start,r^.start) of+                (Nothing, Nothing) -> Nothing+                (Nothing, Just k ) -> Just k+                (Just k , Nothing) -> Just k+                (Just k , Just l ) -> if k==l then Just k else error "need to create new symbol, see note on Semigroup (Add Grammar)"+          t = case (l^.start,r^.start) of+                (Just k , Just l ) -> if k==l then S.empty else error "this will create the new rule"+                _                  -> S.empty+                                --(if l^.start == r^.start+                                --  then l^.start+                                --  else error "maybe add another rule and a unique start symbol?")++instance Monoid (Add Grammar) where+  mempty = Add $ Grammar S.empty S.empty S.empty S.empty Nothing ""+  mappend = (<>)++-- idempotency is not made explicit here+

+ FormalLanguage/GrammarProduct/Op/Chomsky.hs view

@@ -0,0 +1,157 @@+{-# LANGUAGE UnicodeSyntax #-}+{-# LANGUAGE LambdaCase #-}+{-# LANGUAGE PatternGuards #-}++module FormalLanguage.GrammarProduct.Op.Chomsky where++import Control.Applicative+import Control.Lens+import Control.Lens.Fold+import Control.Newtype ()+import Data.Function (on)+import Data.List (genericReplicate,replicate,groupBy)+import Data.Maybe+import Data.Monoid hiding ((<>))+import Data.Semigroup+import qualified Data.Set as S+import Text.Printf+import System.IO.Unsafe++import FormalLanguage.CFG.Grammar+import FormalLanguage.CFG.Parser+import FormalLanguage.CFG.PrettyPrint.ANSI++import FormalLanguage.GrammarProduct.Op.Common++++newtype CNF = CNF { runCNF :: Grammar }++instance Semigroup CNF where+  (CNF g) <> (CNF h) = CNF $ Grammar ts ns es rs s (g^.name ++ h^.name) where+    ts = S.fromList $ g^..tsyms.folded ++ h^..tsyms.folded+    ns = collectNonTerminals rs -- this is needed since we generate completely new non-terminal symbols+    es = S.fromList $ g^..epsis.folded ++ h^..epsis.folded+    rs = S.fromList+       . concat+       $ [ chomskyCombine l r | l <- g^..rules.folded, r <- h^..rules.folded ]+    s  = liftA2 (\l r -> Symb $ l^.symb ++ r^.symb) (g^.start) (h^.start)++instance Monoid CNF where+  mempty = CNF $ Grammar S.empty S.empty S.empty (S.singleton undefined) (Just $ Symb []) ""+  mappend = (<>)++-- | Combine production rules a la Chomsky normal form.+--+-- TODO We need to be able to generate fresh rule name, as we are splitting+-- rules here! (this means that we need to lift this stuff into a+-- name-generating monad)++chomskyCombine :: Rule -> Rule -> [Rule]+chomskyCombine (Rule l f rs) (Rule a g bs)+  | [r] <- rs, [b] <- bs, isSymbT r, isSymbT b+  = [Rule (Symb $ l^.symb ++ a^.symb) [] {- (f++g) -} [Symb $ r^.symb ++ b^.symb]]+  | [r1,r2] <- rs, [b1,b2] <- bs, isSymbN r1, isSymbN r2, isSymbN b1, isSymbN b2+  = [Rule (Symb $ l^.symb ++ a^.symb) [] {- (f++g) -} [Symb $ r1^.symb ++ b1^.symb, Symb $ r2^.symb ++ b2^.symb]]+  | [r] <- rs, [b1,b2] <- bs, isSymbT r, isSymbN b1, isSymbN b2+  = let (z1,zs1) = symbToRules r b1+        (z2,zs2) = symbToRules r b2+    in  zs1 ++ zs2 ++ {-concatMap (extendRederive (length $ l^.symb) (length $ a^.symb))-}+        [ Rule (Symb $ l^.symb ++ a^.symb) [] {- (f++g) -} [ {- Symb $ r^.symb  ++ b1^.symb -} z1 , Symb $ genEps r ++ b2^.symb]+        , Rule (Symb $ l^.symb ++ a^.symb) [] {- (f++g) -} [Symb $ genEps r ++ b1^.symb, z2 {- Symb $ r^.symb  ++ b2^.symb -} ]+        ]+  | [r1,r2] <- rs, [b] <- bs, isSymbN r1, isSymbN r2, isSymbT b+  = let (z1,zs1) = symbToRules r1 b+        (z2,zs2) = symbToRules r2 b+    in  zs1 ++ zs2 ++ {-concatMap (extendRederive (length $ l^.symb) (length $ a^.symb))-}+        [ Rule (Symb $ l^.symb ++ a^.symb) [] {- (f++g) -} [{- Symb $ r1^.symb ++ b^.symb -} z1 , Symb $ r2^.symb ++ genEps b]+        , Rule (Symb $ l^.symb ++ a^.symb) [] {- (f++g) -} [Symb $ r1^.symb ++ genEps b, z2 {- Symb $ r2^.symb ++ b^.symb -} ]+        ]+  --+  -- extended Chomsky: Non-terminal -> Non-terminal+  --+  {-+  | [r] <- rs, [b] <- bs, nSymb r, nSymb b+  = [ Rule (Symb $ l^.symb ++ a^.symb) [] [ Symb $ r^.symb ++ b^.symb ] ]+  | [r] <- rs, [b1,b2] <- bs, nSymb r, nSymb b1, nSymb b2+  = []+  | [r1,r2] <- rs, [b] <- bs, nSymb r1, nSymb r2, nSymb b+  = []+  | [r] <- rs, [b] <- bs+  = []+  -}+  {-+  = [ Rule (Symb $ l^.symb ++ a^.symb) [] [ Symb $ r^.symb  ++ b1^.symb, Symb $ genEps r ++ b2^.symb ]+    , Rule (Symb $ l^.symb ++ a^.symb) [] [ Symb $ genEps r ++ b1^.symb, Symb $ r^.symb  ++ b2^.symb ]+    ]+  -}+  --+  -- extended Chomsky above+  --+  | otherwise = unsafePerformIO $ do+      print "======"+      printDoc $ rulesDoc $ S.singleton $ Rule l f rs+      printDoc $ rulesDoc $ S.singleton $ Rule a g bs+      fail "cannot handle (rule is not CNF):"+  -- | otherwise = error $ "cannot handle (rule is not CNF): " ++ show (printDoc $ rulesDoc $ S.singleton $ Rule l f rs, Rule a g bs)++{-+-- | Extend mixed rules and rederive CNF++extendRederive :: Int -> Int -> Rule -> [Rule]+extendRederive α β (Rule l f [r1,r2])+  | not (tSymb r1) && not (nSymb r1) && nSymb r2+  = let (newN,epsN,trmN,epsT) = genNewSymbols α β r1+    in  [ Rule l    f           [newN,r2]+        , Rule newN ( {- "nwNL_": -} f) [epsN,trmN]+        , Rule newN ( {- "nwNR_": -} f) [trmN,epsN]+        , Rule trmN ( {- "trmN_": -} f) [epsT]+        ]+  | nSymb r1 && not (tSymb r2) && not (nSymb r2)+  = let (newN,epsN,trmN,epsT) = genNewSymbols α β r2+    in  [ Rule l    f           [r1,newN]+        , Rule newN ( {- "nwNL_": -} f) [epsN,trmN]+        , Rule newN ( {- "nwNR_": -} f) [trmN,epsN]+        , Rule trmN ( {- "trmN_": -} f) [epsT]+        ]+extendRederive _ _ r = error $ "cannot handle (rule not in extendRederive form for CNF): " ++ show r++genNewSymbols :: Int -> Int -> Symb -> (Symb,Symb,Symb,Symb)+genNewSymbols α β x = (newN, epsN, trmN, epsT) where+  -- the new non-terminal, with term TN's replaced by non-term TN with same name (plus extension)+  newN = Symb . map (\case (T s) -> N ("N"++s) Singular ; z -> z) $ x^.symb+  -- the new non-terminal, with terms replaced by epsilons+  epsN = Symb . map (\case (T s) -> eps                 ; z -> z) $ x^.symb+  -- the new non-terminal for the terminal symbol, with terms replaced by non-term symbols+  -- TODO we can't just replace all N here with eps, tome could have been created from other prods.+  trmN = Symb . map (\case (T s) -> N ("T"++s) Singular ; N _ _ -> eps; z -> z) $ x^.symb+  -- finally the terminal +  epsT = Symb . map (\case (N _ _) -> eps               ; z -> z) $ x^.symb+-}++-- | ++symbToRules :: Symb -> Symb -> (Symb, [Rule])+symbToRules u' l'+  | isSymbN u' && isSymbT l' = go u' l'+  | isSymbT u' && isSymbN l' = let (s,rs) = go (over symb reverse l') (over symb reverse u')+                             in  ( over symb reverse s+                                 , map (\(Rule l [] rs) -> Rule (over symb reverse l) [] (map (over symb reverse) rs)) rs+                                 )+  | otherwise            = error $ "incompatible upper/lower: " ++ show (u',l')+  where+    -- in 'n' we have the partial non-terminal, in 't' the partial terminal+    go n t =+      let t' = Symb $ map (\case (T s) -> (N ("T"++s) Singular) ; z -> z) $ t^.symb+      in  ( Symb $ n^.symb ++ t'^.symb+          , [ Rule (Symb $ n^.symb ++ t'^.symb) [] [ Symb $ n^.symb ++ genEps t, Symb $ genEps n ++ genTermStar t ]+            , Rule (Symb $ n^.symb ++ t'^.symb) [] [ Symb $ genEps n ++ genTermStar t, Symb $ n^.symb ++ genEps t ]+            , Rule (Symb $ genEps n ++ genTermStar t)  [] [ Symb $ genEps n ++ t^.symb ]+            ]+          )++-- | Generate a certain number of epsilons++genTermStar :: Symb -> [TN]+genTermStar s = map (\case (T s) -> N ("S"++s) Singular ; z -> z) $ s^.symb+

+ FormalLanguage/GrammarProduct/Op/Chomsky/Proof.hs view

@@ -0,0 +1,76 @@++module FormalLanguage.GrammarProduct.Op.Chomsky.Proof where++import Control.Lens+import Control.Lens.Fold+import Control.Newtype ()+import Data.List (genericReplicate)+import Data.Monoid hiding ((<>))+import Data.Semigroup+import qualified Data.Set as S+import Text.Printf+import Data.List (groupBy)+import Data.Function (on)+import Data.Maybe+import Control.Applicative++import Text.PrettyPrint.ANSI.Leijen hiding ((<>))+import Text.Trifecta  --+import qualified Data.ByteString.Char8 as B+import           Control.Monad.Trans.State.Strict+import           Data.Default+import           Text.Trifecta.Delta++import FormalLanguage.CFG.Grammar+import FormalLanguage.CFG.PrettyPrint.ANSI+import FormalLanguage.CFG.PrettyPrint.LaTeX+import FormalLanguage.CFG.Parser++import FormalLanguage.GrammarProduct.Op.Chomsky++++-- * Proof of associativity of the 2-GNF.++-- | Run the 2-gnf grammar with the TwoGNF monoid which observes the 2 star+-- cases.++cNFassociativity :: (Grammar, Grammar, S.Set Rule, S.Set Rule, Bool)+cNFassociativity = ( l+                   , r+                   , (l^.rules) S.\\ (r^.rules)+                   , (r^.rules) S.\\ (l^.rules)+                   , l^.rules == r^.rules)  where+  l = runCNF $ (CNF g <>  CNF g) <> CNF g+  r = runCNF $  CNF g <> (CNF g  <> CNF g)+  g = cNFgrammar++cNFs = g where+  g = runCNF $ (CNF h <> CNF h)+  h = cNFgrammar++showTwo = printDoc $ grammarDoc $ runCNF  $ CNF cNFgrammar <> CNF cNFgrammar++-- * The simple 2-gnf grammar to run the proof on.++-- | Very simple 2-gnf form for proofs.++cNFgrammar = case g of+  Success g' -> g'+  Failure f  -> error $ show f+  where+  g = parseGrammar "testGrammar" twoGNF+  twoGNF = unlines+    [ "Grammar: CNF"+    , "N: A"+    , "N: B"+    , "N: C"+--    , "N: Sa"+    , "T: a"+    , "A  -> twoN <<< B C"+    , "A  -> oneT <<< a"+--    , "A  -> oneN <<< Sa"+--    , "Sa -> oneT <<< a"+    , "//"+    ]+

+ FormalLanguage/GrammarProduct/Op/Common.hs view

@@ -0,0 +1,37 @@+{-# LANGUAGE LambdaCase #-}++module FormalLanguage.GrammarProduct.Op.Common where++import qualified Data.Set as S+import Control.Lens++import FormalLanguage.CFG.Grammar++++-- | Collect all terminal symbols from a set of rules.+--+-- TODO move to FormalGrammars library+--+-- TODO i guess, this collects multidim stuff for now!!!++collectTerminals :: S.Set Rule -> S.Set Symb+collectTerminals = S.fromList . filter isSymbT . concatMap _rhs . S.toList++-- | Collect all non-terminal symbols from a set of rules.+--+-- TODO move to FormalGrammars library++collectNonTerminals :: S.Set Rule -> S.Set Symb+collectNonTerminals = S.fromList . filter isSymbN . concatMap (\r -> r^.lhs : r^.rhs) . S.toList++collectEpsilons :: S.Set Rule -> S.Set TN+collectEpsilons = S.fromList+                . filter (\case E -> True ; z -> False)+                . concatMap (view symb)+                . concatMap _rhs+                . S.toList++genEps :: Symb -> [TN]+genEps s = replicate (length $ s^.symb) E+

+ FormalLanguage/GrammarProduct/Op/Greibach.hs view

@@ -0,0 +1,135 @@+{-# LANGUAGE ParallelListComp #-}++module FormalLanguage.GrammarProduct.Op.Greibach where++import Control.Applicative+import Control.Lens+import Control.Lens.Fold+import Control.Newtype ()+import Data.Function (on)+import Data.List (genericReplicate)+import Data.List (groupBy)+import Data.Maybe+import Data.Monoid hiding ((<>))+import Data.Semigroup+import qualified Data.Set as S+import Text.Printf++import Text.Trifecta  --+import qualified Data.ByteString.Char8 as B+import           Control.Monad.Trans.State.Strict+import           Data.Default+import           Text.Trifecta.Delta++import FormalLanguage.CFG.Grammar+import FormalLanguage.CFG.Parser++import FormalLanguage.GrammarProduct.Op.Common++++-- * Proof of associativity of the 2-GNF.++-- | Wrap a grammar in 2-GNF form.+--+-- The 2-GNF has rules of the form: X -> a | aY | aYZ with "a" terminal, "Y",+-- "Z" non-terminals.++newtype TwoGNF = TwoGNF {runTwoGNF :: Grammar}++-- | Construct a grammar product for a grammar in 2-GNF form.+--+-- TODO check if grammar is in 2-GNF!++instance Semigroup TwoGNF where+  (TwoGNF g) <> (TwoGNF h) = TwoGNF $ Grammar ts ns es rs s (g^.name ++ h^.name) where+    ts = collectTerminals rs+    ns = collectNonTerminals rs+    es = g^.epsis <> h^.epsis -- this is kind of sketchy+    rs = S.fromList+       . map starRemove+       . catMaybes+       $ [ l <.> r+         | l <- concatMap (starExtend $ gDim g) . S.toList $ g^.rules+         , r <- concatMap (starExtend $ gDim h) . S.toList $ h^.rules+         ]+    s  = liftA2 (\l r -> Symb $ l^.symb ++ r^.symb) (g^.start) (h^.start)+    (<.>) :: Rule -> Rule -> Maybe Rule+    a <.> b | ((Just $ a^.lhs)==g^.start) `exactlyOne` ((Just $ b^.lhs)==h^.start) = Nothing+    a <.> b = Just+            $ Rule (Symb $ a^.lhs.symb ++ b^.lhs.symb)+                   [""]+                   (zipWith (\x y -> Symb $ x^.symb ++ y^.symb) (a^.rhs) (b^.rhs))+    exactlyOne False True  = True+    exactlyOne True  False = True+    exactlyOne _     _     = False+    -- | Extend a rule with ``epsilon-type'' productions to create 2-GNF for all rules+    starExtend :: Int -> Rule -> [Rule]+    starExtend k (Rule l f [t])   = [ Rule l f [t,stars k, stars k]]+    starExtend k (Rule l f [t,n]) = [ Rule l f [t,n,stars k]+                                    , Rule l f [t,stars k,n]+                                    ]+    -- assuming that we have a 2-gnf at most+    starExtend k r                = [r]+    stars :: Int -> Symb+    stars k = Symb $ replicate k E+    -- | Remove star-online columns.+    starRemove :: Rule -> Rule+    starRemove = over rhs (filter (any (not . isEpsilon) . getSymbs))+    isEpsilon E = True+    isEpsilon _ = False++-- | The start symbol for this instance needs to be "Just []" so as to preserve+-- the start symbol in a chain of (<>) operations.++instance Monoid TwoGNF where+  mempty = TwoGNF $ Grammar S.empty S.empty S.empty (S.singleton undefined) (Just $ Symb []) ""+  mappend = (<>)++++-- | Takes lists of symbols and aligns according to being+-- terminal/non-terminal:+--+-- aXbc / aXYb =>+--+-- aX-bc    a-Xbc+-- aXYb-    aXYb-+--+-- That is, create all alignments of non-terminals, but just ``left-align'' all+-- terminals. This will create all possible "alignments" of symbols. This is+-- why we return a list of lists.++{-+aligned :: [Symb] -> [Symb] -> [[Symb]]+aligned ls' rs' = go (groupBy ((==) `on` isSymbT) ls') (groupBy ((==) `on` isSymbT) rs') where+  dl = length . getSymbs . head $ ls'+  dr = length . getSymbs . head $ rs'+  go :: [[Symb]] -> [[Symb]] -> [[Symb]]+  go []     []     = []+  go (l:ls) []     = epsR l : go ls []+  go []     (r:rs) = epsL r : go [] rs+  go (l:ls) (r:rs)+    |  all isSymbT l+    && all isSymbT r = goT l r : go ls rs+    |  all isSymbN l+    && all isSymbN r = undefined -- [ ns : gs | ns <- goN l r, gs <- go ls rs ]+    |  all isSymbT l = epsR l : go ls     (r:rs)+    |  all isSymbT r = epsL r : go (l:ls) rs+  goT []     []     = []+  goT ls     []     = epsR ls+  goT []     rs     = epsL rs+  goT (l:ls) (r:rs) = (Symb $ l^.symb ++ r^.symb) : goT ls rs+  goN :: [Symb] -> [Symb] -> [[Symb]]+  goN []     []     = [[]]+  goN (l:ls) []     = epsR [l] : goN ls []+  goN []     (r:rs) = epsL [r] : goN [] rs+  goN lls rrs+    | length lls == length rrs = [[ Symb $ l^.symb ++ r^.symb | l <- lls | r <- rrs ]]+  goN lls@(l:ls) rrs@(r:rs)+    | length lls  < length rrs = undefined+    | length lls  > length rrs = undefined+  epsR ls = map (\(Symb s) -> Symb $ s ++ replicate dr (T "")) ls+  epsL rs = map (\(Symb s) -> Symb $ replicate dl (T "") ++ s) rs+-}+

+ FormalLanguage/GrammarProduct/Op/Greibach/Proof.hs view

@@ -0,0 +1,161 @@+{-# LANGUAGE PatternGuards #-}+{-# LANGUAGE ParallelListComp #-}++module FormalLanguage.GrammarProduct.Op.Greibach.Proof where++import Control.Lens+import Control.Lens.Fold+import Control.Newtype ()+import Data.List (genericReplicate)+import Data.Monoid hiding ((<>))+import Data.Semigroup+import qualified Data.Set as S+import Text.Printf+import Data.List (groupBy)+import Data.Function (on)+import Data.Maybe+import Control.Applicative++import Text.PrettyPrint.ANSI.Leijen hiding ((<>))+import Text.Trifecta  --+import qualified Data.ByteString.Char8 as B+import           Control.Monad.Trans.State.Strict+import           Data.Default+import           Text.Trifecta.Delta++import FormalLanguage.CFG.Grammar+import FormalLanguage.CFG.PrettyPrint.ANSI+import FormalLanguage.CFG.PrettyPrint.LaTeX+import FormalLanguage.CFG.Parser++import FormalLanguage.GrammarProduct.Op.Greibach+import FormalLanguage.GrammarProduct.Op.Common++++-- * Proof of associativity of the 2-GNF.++-- | Run the 2-gnf grammar with the TwoGNF monoid which observes the 2 star+-- cases.++twoGNFassociativity :: (Grammar, Grammar, S.Set Rule, S.Set Rule, Bool)+twoGNFassociativity = ( l+                      , r+                      , (l^.rules) S.\\ (r^.rules)+                      , (r^.rules) S.\\ (l^.rules)+                      , l^.rules == r^.rules)  where+  l = runTwoGNF $ (TwoGNF g <>  TwoGNF g) <> TwoGNF g+  r = runTwoGNF $  TwoGNF g <> (TwoGNF g  <> TwoGNF g)+  g = twoGNFgrammar++twoGNFs = g where+  g = runTwoGNF $ (TwoGNF h <> TwoGNF h)+  h = twoGNFgrammar++assocHelper l r = ( l+                  , r+                  , (l^.rules) S.\\ (r^.rules)+                  , (r^.rules) S.\\ (l^.rules)+                  , l^.rules == r^.rules)++-- * Proof that the 2 star cases are actually needed. We loose associativity+-- without those. As this version does not preserve associativity, we keep it+-- here, instead of the general Greibach version.++newtype FailGNF = FailGNF { runFailGNF :: Grammar }++-- |+--+-- TODO check correctness++instance Semigroup FailGNF where+  (FailGNF g) <> (FailGNF h) = FailGNF $ Grammar ts ns es rs s (g^.name ++ h^.name) where+    ts = collectTerminals rs+    ns = collectNonTerminals rs+    es = g^.epsis <> h^.epsis+    rs = S.fromList+       . map starRemove+       . concat+       $ [ l <.> r+         | l <- S.toList $ g^.rules+         , r <- S.toList $ h^.rules+         ]+    s  = liftA2 (\l r -> Symb $ l^.symb ++ r^.symb) (g^.start) (h^.start)+    (<.>) :: Rule -> Rule -> [Rule]+    a <.> b | ((Just $ a^.lhs)==g^.start) `exactlyOne` ((Just $ b^.lhs)==h^.start) = []+    a <.> b+      | [s,m]   <- a^.rhs+      , [t,n,o] <- b^.rhs+      = [ Rule (Symb $ a^.lhs.symb ++ b^.lhs.symb)+          [""]+          [Symb $ s^.symb ++ t^.symb, Symb $ m^.symb ++ n^.symb, Symb $ stars (length $ m^.symb) ^.symb ++ o^.symb ]+        , Rule (Symb $ a^.lhs.symb ++ b^.lhs.symb)+          [""]+          [Symb $ s^.symb ++ t^.symb, Symb $ stars (length $ m^.symb) ^.symb ++ n^.symb, Symb $ m^.symb ++ o^.symb ]+        ]+      | [s,m,o] <- a^.rhs+      , [t,n]   <- b^.rhs+      = [ Rule (Symb $ a^.lhs.symb ++ b^.lhs.symb)+          [""]+          [ Symb $ s^.symb ++ t^.symb+          , Symb $ m^.symb ++ n^.symb+          , Symb $ o^.symb ++ stars (length $ t^.symb) ^.symb+          ]+        , Rule (Symb $ a^.lhs.symb ++ b^.lhs.symb)+          [""]+          [ Symb $ s^.symb ++ t^.symb+          , Symb $ m^.symb ++ stars (length $ t^.symb) ^.symb+          , Symb $ o^.symb ++ n^.symb+          ]+        ]+    a <.> b = [ Rule  (Symb $ a^.lhs.symb ++ b^.lhs.symb)+                      [""]+                      (take 3 $ zipWith (\l r -> Symb $ l^.symb ++ r^.symb) (a^.rhs ++ repeat (stars (gDim g)))+                                                                            (b^.rhs ++ repeat (stars (gDim h)))+                      )+              ]+    exactlyOne False True  = True+    exactlyOne True  False = True+    exactlyOne _     _     = False+    stars :: Int -> Symb+    stars k = Symb $ replicate k E+    -- | Remove star-online columns.+    starRemove :: Rule -> Rule+    starRemove = over rhs (filter (any (not . isEpsilon) . getSymbs))+    isEpsilon E = True+    isEpsilon _ = False+++-- | Run the 2-gnf grammar without the star cases.++-- noStarFailure :: (S.Set Rule, S.Set Rule, +noStarFailure = assocHelper l r where+  l = runFailGNF $ (FailGNF g <>  FailGNF g) <> FailGNF g+  r = runFailGNF $  FailGNF g <> (FailGNF g  <> FailGNF g)+  g = twoGNFgrammar++-- * The simple 2-gnf grammar to run the proof on.++-- | Very simple 2-gnf form for proofs.++twoGNFgrammar = case g of+  Success g' -> g'+  Failure f  -> error $ show f+  where+  g = parseGrammar "testGrammar" twoGNF+  twoGNF = unlines+    [ "Grammar: TwoGNF"+    , "N: A"+    , "N: B"+    , "N: C"+    , "N: D"+    , "T: a"+    , "T: b"+    , "T: c"+--    , "S: X"+    , "A -> three <<< a B C"+    , "A -> two   <<< b D"+    , "A -> one   <<< c"+    , "//"+    ]+

+ FormalLanguage/GrammarProduct/Op/Linear.hs view

@@ -0,0 +1,73 @@+{-# LANGUAGE FlexibleInstances #-}++-- | Direct product of two grammars.+--+-- Currently implemented for linear grammars. Once we move to context-free+-- grammars with more than one non-terminal on the RHS, things become+-- interesting.++module FormalLanguage.GrammarProduct.Op.Linear where++import Data.Semigroup+import Control.Lens+import Control.Applicative+import qualified Data.Set as S+import Data.List (groupBy)+import Data.Function (on)++import FormalLanguage.CFG.Grammar++import FormalLanguage.GrammarProduct.Op.Common++++newtype Linear a = Linear {runLinear :: a}++++instance Semigroup (Linear Grammar) where+  (Linear g) <> (Linear h) = Linear $ Grammar ts ns es rs s (g^.name <> h^.name) where+    ts = g^.tsyms <> h^.tsyms+    ns = collectNonTerminals rs+    es = g^.epsis <> h^.epsis+    rs = S.fromList [ direct l r | l <- g^..rules.folded, r <- h^..rules.folded ]+    s  = liftA2 (\l r -> Symb $ l^.symb ++ r^.symb) (g^.start) (h^.start)+    direct (Rule l f rs) (Rule a g bs) = Rule (Symb $ l^.symb ++ a^.symb) (f++g) (mergeRHS rs bs)++instance Monoid (Linear Grammar) where+  mempty = Linear $ Grammar S.empty S.empty S.empty (S.singleton $ Rule (Symb []) [] []) Nothing ""+  mappend = (<>)++-- | Merges right-hand sides in a linear direct product. For full-fledged CFGs+-- in different normal forms, see the GNF and CNF implementations.++mergeRHS :: [Symb] -> [Symb] -> [Symb]+mergeRHS [] rs = rs -- neutral element+mergeRHS ls [] = ls -- neutral element+mergeRHS ls' rs' = concat $ go (groupRHS ls') (groupRHS rs') where+  dl = head ls'+  dr = head rs'+  go [] [] = []+  go [] (r:rs)+    | all isSymbT r = map (\(Symb z) -> Symb $ genEps dl ++ z) r : go [] rs+    | all isSymbN r = let [Symb z] = r+                      in  [Symb $ genEps dl ++ z] : go [] rs+  go (l:ls) []+    | all isSymbT l = map (\(Symb z) -> Symb $ z ++ genEps dr) l : go ls []+    | all isSymbN l = let [Symb z] = l+                      in  [Symb $ z ++ genEps dr] : go ls []+  go (l:ls) (r:rs)+    | all isSymbT l && all isSymbT r = goT l r : go ls rs+    | all isSymbN l && all isSymbN r = let [Symb y] = l+                                           [Symb z] = r+                                       in  [Symb $ y++z] : go ls rs+    | all isSymbN l = go [l] []  ++ go ls     (r:rs)+    | all isSymbN r = go []  [r] ++ go (l:ls) rs+    | otherwise     = go [l] []  ++ go [] [r] ++ go ls rs+  goT []            []            = []+  goT []            (Symb t : rs) = Symb (genEps dl ++ t) : goT [] rs+  goT (Symb t : ls) []            = Symb (t ++ genEps dr) : goT ls []+  goT (Symb u : ls) (Symb v : rs) = Symb (u++v)           : goT ls rs++groupRHS = groupBy ((==) `on` isSymbT)+

+ FormalLanguage/GrammarProduct/Op/Power.hs view

@@ -0,0 +1,27 @@++module FormalLanguage.GrammarProduct.Op.Power where++import Control.Newtype+import Data.Semigroup+import Control.Lens+import Control.Lens.Fold+import qualified Data.Set as S+import Data.List (genericReplicate)+import Text.Printf++import FormalLanguage.CFG.Grammar++++-- |++power :: Grammar -> Integer -> Grammar+power g k = Grammar ts ns es rs s nm where+  ts = g^.tsyms+  ns = S.map go $ g^.nsyms+  es = g^.epsis+  rs = S.map (\(Rule l f rs) -> Rule (go l) (f++f) (map go rs)) $ g^.rules+  s  = fmap go $ g^.start+  nm = concat . genericReplicate k $ g^.name+  go (Symb z) = Symb . concat $ genericReplicate k z+

+ FormalLanguage/GrammarProduct/Op/Subtract.hs view

@@ -0,0 +1,34 @@+{-# LANGUAGE FlexibleInstances #-}++module FormalLanguage.GrammarProduct.Op.Subtract where++import Control.Newtype+import Data.Semigroup+import Control.Lens+import Control.Lens.Fold+import qualified Data.Set as S+import Data.List (genericReplicate)+import Text.Printf++import FormalLanguage.CFG.Grammar++import FormalLanguage.GrammarProduct.Op.Common++++-- | Subtract two grammars.++subtract :: Grammar -> Grammar -> Grammar+subtract l r+    | gDim l /= gDim r = error $ printf "grammars %s and %s have different dimensions, cannot unify. (subtract)" (show l) (show r)+    | otherwise        = Grammar ts ns es rs s (l^.name ++ r^.name) where+        ts = collectTerminals rs+        ns = collectNonTerminals rs+        es = collectEpsilons rs+        rs = (l^.rules) S.\\ (r^.rules)+        s  = case (l^.start) of+               Nothing -> Nothing+               Just s' -> if anyOf (rules.folded.lhs) (==s') l+                            then l^.start+                            else Nothing+

+ FormalLanguage/GrammarProduct/Parser.hs view

@@ -0,0 +1,355 @@+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE StandaloneDeriving #-}+{-# LANGUAGE RankNTypes #-}+{-# LANGUAGE TemplateHaskell #-}+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+{-# LANGUAGE NoMonomorphismRestriction #-}+{-# LANGUAGE OverloadedStrings #-}++-- | This parser extends the @FormalLanguage.Parser@ parser of single- and+-- multi-dim grammars to accept grammar product definitions as well.++module FormalLanguage.GrammarProduct.Parser where++import Control.Arrow+import Control.Applicative+import Control.Lens+import Control.Monad (MonadPlus(..), guard, when)+import Control.Monad.Trans.Class+import Control.Monad.Trans.State.Strict+import Control.Monad.Trans.Reader+import Data.Default+import Data.Either+import Data.Map (Map)+import Data.Set (Set)+import Debug.Trace+import Data.List+import qualified Data.ByteString.Char8 as B+--import qualified Data.HashSet as H+import qualified Data.Map as M+import qualified Data.Set as S+import Text.Parser.Expression+import Text.Parser.Token.Highlight+import Text.Parser.Token.Style+import Text.Printf+import Text.Trifecta+import Text.Trifecta.Delta+import Text.Trifecta.Result+import Data.Semigroup ((<>),times1p)+import qualified Control.Newtype as T+--import Numeric.Natural.Internal+import Prelude hiding (subtract)+import Control.Monad++import FormalLanguage.CFG.Grammar+import FormalLanguage.CFG.Parser++import FormalLanguage.GrammarProduct++++-- | Parse a product grammar.++parseProduct :: String -> String -> Result [Grammar]+parseProduct fname cnts = parseString+  ((evalStateT . runGrammarP) productParser def)+  (Directed (B.pack fname) 0 0 0 0)+  cnts++-- | Parse all grammars and grammar products, prepending to the list.++productParser = go [] <* eof where+  go gs = do+    whiteSpace+    g' <- option Nothing $ Just <$> (try grammar <|> grammarProduct gs)+    case g' of+      Nothing -> return gs+      Just g  -> go (g:gs)++grammarProduct gs = do+  reserveGI "Product:"+  n <- identGI+  e <- getGrammar <$> expr (M.fromList [(g^.name,g) | g<-gs])+  reserveGI "//"+  return $ over (name) (const n) e++expr :: Map String Grammar -> Parse ExprGrammar+expr g = e where+  e = buildExpressionParser table term+  table = [ [ binary "^><" highDirect AssocLeft+            ]+          , [ binary "><"  exprDirect AssocLeft+            , binary "*"   exprPower  AssocLeft+            ]+          , [ binary "+"   exprPlus   AssocLeft+            , binary "-"   exprMinus  AssocLeft+            ]+          ]+  term  =   parens e+        <|> (choice gts <?> "previously defined grammar")+        <|> (ExprNumber <$> natural <?> "integral power of grammar")+  gts = map (fmap ExprGrammar . gterm) $ M.assocs g+  binary n f a = Infix (f <$ reserveGI n) a+  exprDirect l r = ExprGrammar $ (getGrammar l >< getGrammar r)+  exprPlus   l r = ExprGrammar $ gAdd (getGrammar l) (getGrammar r)+  exprMinus  l r = ExprGrammar $ gSubtract (getGrammar l) (getGrammar r)+  exprPower  l r = ExprGrammar $ gPower (getGrammar l) (getNumber r)+  highDirect l r = error "highDirect (not active)!" -- ExprGrammar . unDirect $ times1p (Natural $ getNumber r -1) (Direct $ getGrammar l)++data ExprGrammar+  = ExprGrammar { getGrammar :: Grammar }+  | ExprNumber  { getNumber  :: Integer }++gterm :: (String,Grammar) -> Parse Grammar+gterm (s,g) = g <$ reserveGI s++{-+data GS = GS+  { _ntsyms     :: Map String Integer+  , _tsyms      :: Set String+  , _gs         :: Map String Grammar+  , _gCount     :: Integer+  , _grammarUid :: Integer+  }+  deriving (Show)++instance Default GS where+  def = GS+    { _ntsyms     = def+    , _tsyms      = def+    , _gs         = def+    , _gCount     = def+    , _grammarUid = def+    }++makeLenses ''GS++-- | Parsing product expressions, producing a grammar, again++{-+expr :: Map String Grammar -> Parse Grammar+expr g = choice [directprod] where+  directprod = do+    gl <- choice gts+    reserve gi "><"+    gr <- choice gts+    return . unDirect $ Direct gl <> Direct gr+  gts = map gterm $ M.assocs g+-}++expr :: Map String Grammar -> Parse ExprGrammar+expr g = e where+  e = buildExpressionParser table term+  table = [ [ binary "^><" highDirect AssocLeft+            ]+          , [ binary "><"  exprDirect AssocLeft+            , binary "*"   exprPower  AssocLeft+            ]+          , [ binary "+"   exprPlus   AssocLeft+            , binary "-"   exprMinus  AssocLeft+            ]+          ]+  term  =   parens e+        <|> (choice gts <?> "previously defined grammar")+        <|> (ExprNumber <$> natural <?> "integral power of grammar")+  gts = map (fmap ExprGrammar . gterm) $ M.assocs g+  binary n f a = Infix (f <$ reserve gi n) a+  exprDirect l r = ExprGrammar . unDirect $ (Direct $ getGrammar l) <> (Direct $ getGrammar r)+  exprPlus   l r = ExprGrammar . unAdd $ (Add $ getGrammar l) <> (Add $ getGrammar r)+  exprMinus  l r = ExprGrammar $ subtract (getGrammar l) (getGrammar r)+  exprPower  l r = ExprGrammar $ power (getGrammar l) (getNumber r)+  highDirect l r = ExprGrammar . unDirect $ times1p (Natural $ getNumber r -1) (Direct $ getGrammar l)++data ExprGrammar+  = ExprGrammar { getGrammar :: Grammar }+  | ExprNumber  { getNumber  :: Integer }++gterm :: (String,Grammar) -> Parse Grammar+gterm (s,g) = g <$ reserve gi s++-- | Grammar product++gprod :: Parse Grammar+gprod = do+  reserve gi "Product:"+  n <- ident gi+  g <- use gs+  e <- getGrammar <$> expr g+  reserve gi "//"+  let g = e & gname .~ n+  gs <>= M.singleton (g ^. gname) g+  return g++data Product = Product+  deriving (Show)++-- |+--+-- TODO complain on indexed NTs with modulus '1'++grammar :: Parse Grammar+grammar = do+  -- reset some information+  ntsyms .= def+  tsyms  .= def+  -- new grammar+  gCount += 1+  -- begin parsing+  reserve gi "Grammar:"+  n <- ident gi+  (nts,ts) <- partitionEithers <$> ntsts+  rs <- concat <$> some rule+  reserve gi "//"+  let g = Grammar (S.fromList rs) n+  gs <>= M.singleton (g ^. gname) g+  return g++-- | Parse a single rule. Some rules come attached with an index. In that case,+-- each rule is inflated according to its modulus.+--+-- TODO add @fun@ to each PR++rule :: Parse [PR]+rule = do+  ln <- ident gi <?> "rule: lhs non-terminal"+  uses ntsyms (M.member ln) >>= guard <?> (printf "undeclared NT: %s" ln)+  i <- nTindex+  reserve gi "->"+  fun <- ident gi+  reserve gi "<<<"+  zs <- runUnlined $ some (Left <$> try ruleNts <|> Right <$> try ruleTs)+  whiteSpace+  s <- get+  let ret = runReaderT (genPR fun ln i zs) s+  return ret++-- | Generate one or more production rules from a parsed line.++genPR :: String -> String -> NtIndex -> [Either (String,NtIndex) String] -> ReaderT GS [] PR+genPR f ln i xs = go where+  go = do+    (l,(m,k)) <- genL i+    r <- genR m k xs+    return $ PR [l] r [f]+  genL NoIdx = do+    g <- view grammarUid+    return (Nt 1 [NTSym ln 1 0], (1,0))+  genL (WithVar v 0) = do+    g <- view grammarUid+    m <- views ntsyms (M.! ln)+    k <- lift [0 .. m-1]+    return (Nt 1 [NTSym ln m k], (m,k))+  genL (Range xs) = do+    g <- view grammarUid+    m <- views ntsyms (M.! ln)+    k <- lift xs+    return (Nt 1 [NTSym ln m k], (m,k))+  genR m k [] = do+    return []+  genR m k (Left (n,WithVar k' p) :rs) = do+    let (WithVar v 0) = i+    g <- view grammarUid+    nm <- views ntsyms (M.! n)+    when (v/=k') $ error "oops, index var wrong"+    rs' <- genR m k rs+    return (Nt 1 [NTSym n m ((k+p) `mod` m)] :rs')+  genR m k (Left (n,Range ls) :rs) = do+    g <- view grammarUid+    nm <- views ntsyms (M.! n)+    l <- lift ls+    rs' <- genR m k rs+    return (Nt 1 [NTSym n m l] :rs')+  genR m k (Left (n,NoIdx) :rs) = do+    g <- view grammarUid+    nm <- views ntsyms (M.! n)+    when (nm>1) $ error $ printf "oops, NoIdx given, but indexed NT in: %s" (show (nm,m,k,n,rs))+    rs' <- genR m k rs+    return (Nt 1 [NTSym n 1 0] :rs')+  genR m k (Right t :rs) = do+    g <- view grammarUid+    rs' <- genR m k rs+    return (T 1 [TSym t] :rs')++ruleNts :: ParseU (String,NtIndex)+ruleNts = do+  n <- ident gi <?> "rule: nonterminal identifier"+  i <- nTindex <?> "rule:" -- option ("",1) $ braces ((,) <$> ident gi <*> option 0 integer) <?> "rule: nonterminal index"+  lift $ uses ntsyms (M.member n) >>= guard <?> (printf "undeclared NT: %s" n)+  return (n,i)++nTindex :: ParseG NtIndex+nTindex = option NoIdx+  $   try (braces $ WithVar <$> ident gi <*> option 0 integer)+  <|> try (Range <$> braces (commaSep1 integer))+  <?> "non-terminal index"++data NtIndex+  = WithVar String Integer+  | Range [Integer]+  | NoIdx+  deriving (Show)++ruleTs :: ParseU String+ruleTs = do+  n <- ident gi <?> "rule: terminal identifier"+  lift $ uses tsyms (S.member n) >>= guard <?> (printf "undeclared T: %s" n)+  return n++ntsts :: Parse [Either NTSym TSym]+ntsts = concat <$> some (map Left <$> nts <|> map Right <$> ts)++-- |+--+-- TODO expand @NT@ symbols here or later?++nts :: Parse [NTSym]+nts = do+  reserve gi "NT:"+  n <- ident gi+  mdl <- option 1 $ braces natural+  let zs = map (NTSym n mdl) [0 .. mdl-1]+  ntsyms <>= M.singleton n mdl+  return zs++ts :: Parse [TSym]+ts = do+  reserve gi "T:"+  n <- ident gi+  let z = TSym n+  tsyms <>= S.singleton n+  return [z]++parseDesc = do+  whiteSpace+  {-+  gs <- some grammar+  let g = undefined -- M.fromList $ map ((^. gname) &&& id) gs+  ps <- some (gprod g)+  -}+  gsps <- some (grammar <|> gprod)+  eof+  let (gs,ps) = partition ((==1) . grammarDim) gsps+  return (gs,ps)++gi = set styleReserved rs emptyIdents where+  rs = H.fromList ["Grammar:", "NT:", "T:"]++newtype GrammarLang m a = GrammarLang {runGrammarLang :: m a }+  deriving (Functor,Applicative,Alternative,Monad,MonadPlus,Parsing,CharParsing)++instance MonadTrans GrammarLang where+  lift = GrammarLang+  {-# INLINE lift #-}++instance TokenParsing m => TokenParsing (GrammarLang m) where+  someSpace = GrammarLang $ someSpace `buildSomeSpaceParser` haskellCommentStyle++type Parse a = (Monad m, TokenParsing m, MonadPlus m) => StateT GS m a+type ParseU a = (Monad m, TokenParsing m, MonadPlus m) => Unlined (StateT GS m) a+type ParseG a = (Monad m, TokenParsing m, MonadPlus m) => m a++instance MonadTrans Unlined where+  lift = Unlined+  {-# INLINE lift #-}+-}+

+ GramProd.hs view

@@ -0,0 +1,130 @@+{-# LANGUAGE OverloadedStrings #-}+{-# LANGUAGE RecordWildCards #-}+{-# LANGUAGE DeriveDataTypeable #-}++-- | The @GramProd@ executable reads a grammatical description (from stdin or a+-- file) and produces a set of grammars, each written into a separate file.+--+-- It is possible to both, produce @LaTeX@ and @Haskell@ output. The Haskell+-- grammars require "ADPfusion" to be useful -- and you have to provide+-- algebras that actually evaluate parses.++module Main where++import Control.Lens+import Control.Monad+import Control.Monad.IO.Class+import Control.Monad.Trans.State.Strict+import Data.Default+import Data.Semigroup+import qualified Text.LaTeX.Base.Render as Latex+import System.Console.CmdArgs hiding (def)+import System.IO+import Text.PrettyPrint.ANSI.Leijen as Pretty hiding (line, (<>), (<$>))+import Text.Printf+import Text.Trifecta+import Text.Trifecta.Delta++import FormalLanguage.CFG.Grammar+import FormalLanguage.CFG.PrettyPrint.ANSI+import FormalLanguage.CFG.PrettyPrint.LaTeX+import FormalLanguage.CFG.PrettyPrint.Haskell+import FormalLanguage.GrammarProduct.Parser++++data Options+  = LaTeX+    { inFile :: String+    , outFile ::String+    }+  | Ansi+    { inFile :: String+    }+  | Haskell+    { inFile :: String+    , outFile :: String+    }+  deriving (Show,Data,Typeable)++optionLatex = LaTeX+  { inFile = ""+  , outFile = ""+  }++optionAnsi = Ansi+  { inFile = ""+  }++optionHaskell = Haskell+  { inFile = ""+  , outFile = ""+  }++main = do+  o <- cmdArgs $ modes [optionLatex,optionAnsi,optionHaskell]+  pr <- case (inFile o) of+          "" -> getContents >>= return . parseProduct "stdin"+          fn -> readFile fn >>= return . parseProduct fn+  case pr of+    Failure f -> putStrLn "failed:" >> printDoc f+    Success [] -> error "you did provide input?!"+    Success (s:ss) -> case o of+      LaTeX{..} -> case outFile of+        "" -> error "need to set output file name"+        fn -> renderFile fn $ renderLaTeX 2 s+      Ansi {..} -> printDoc $ grammarDoc s+      Haskell{..} -> case outFile of+        "" -> printDoc $ grammarHaskell s+        fn -> do h <- openFile fn WriteMode+                 hPutDoc h $ grammarHaskell s+                 hClose h++++{-+main :: IO ()+main = do+  o <- cmdArgs $ modes [optionLatex, optionHaskell]+  let g = runGrammarLang $ flip evalStateT def $ parseDesc+  r <- case infile o of+    "" -> getContents >>= return . parseString g (Directed "stdin" 0 0 0 0)+    fn -> parseFromFileEx g fn+  case r of+    Failure e -> liftIO $ displayIO stdout $ renderPretty 0.8 80 $ e <> linebreak+    Success (gs,ps) -> case o of+      Latex{..} -> do+        let latex g = Latex.renderFile (printf "%s/%s.tex" outdir (g^.gname)) . renderGrammarLaTeX columns $ g+        when withatoms $ mapM_ latex gs+        mapM_ latex ps+      Haskell{..} -> do+        let s = renderGrammarHaskell (if withatoms then gs else [] ++ ps)+        -- writeFile (printf "%s/%s.hs" outdir (g^.gname)) s+        putStrLn s++data Options+  = Latex+    { infile    :: String+    , outdir    :: String+    , withatoms :: Bool+    , columns   :: Int+    }+  | Haskell+    { infile    :: String+--    , outdir    :: String+    , withatoms :: Bool+    }+  deriving (Show,Data,Typeable)++optionLatex = Latex+  { infile    = ""    &= help "grammar file to read (stdin if not given)"+  , outdir    = "."   &= help "directory to put grammars in (./ if not given)"+  , withatoms = False &= help "if set, source grammars (atoms) are written to target, too"+  , columns   = 1     &= help "align grammar to 1 or 2 columns?"+  }++optionHaskell = Haskell+  {+  }+-}+

+ GrammarProducts.cabal view

@@ -0,0 +1,116 @@+name:           GrammarProducts+version:        0.0.0.2+author:         Christian Hoener zu Siederdissen, 2013+copyright:      Christian Hoener zu Siederdissen, Ivo L. Hofacker, Peter F. Stadler, 2013+homepage:       http://www.tbi.univie.ac.at/~choener/+maintainer:     choener@tbi.univie.ac.at+category:       Formal Languages, Bioinformatics+license:        GPL-3+license-file:   LICENSE+build-type:     Simple+stability:      experimental+cabal-version:  >= 1.6.0+synopsis:+                Grammar products and higher-dimensional grammars+description:+                An algebra of liner and context-free grammars.+                .+                This library provides the implementation of our theory of+                algebraic operations over linear and context-free grammars.+                Using algebraic operations, it is possible to construct complex+                dynamic programming algorithms from simpler "atomic" grammars.+                .+                Our most important contribution is the definition of a product+                of grammars which naturally leads to alignment-like algorithms+                on multiple tapes.+                .+                An efficient implementation of the resulting grammars is+                possible via the ADPfusion framework. The @FormalGrammars@+                library provides the required "Template Haskell" machinary.+                .+                Alternatively, the resulting grammars can also be+                pretty-printed in various ways (LaTeX, ANSI, Haskell module+                with signature and grammar).+                .+                .+                .+                Formal background can be found in two papers:+                @+                Christian Höner zu Siederdissen, Ivo L. Hofacker, and Peter F. Stadler+                .+                Product Grammars for Alignment and Folding+                .+                submitted+                @+                .+                and+                .+                @+                Christian Höner zu Siederdissen, Ivo L. Hofacker, and Peter F. Stadler+                .+                How to Multiply Dynamic Programming Algorithms+                .+                Brazilian Symposium on Bioinformatics (BSB 2013)+                .+                Lecture Notes in Bioinformatics 8213, Springer, Heidelberg+                @++++Extra-Source-Files:+  changelog++library+  build-depends:+    base >= 4 && < 5          ,+    ADPfusion      >= 0.2.0   ,+    ansi-wl-pprint            ,+    bytestring                ,+    containers                ,+    data-default              ,+    FormalGrammars >= 0.0.0.1 ,+    HaTeX                     ,+    lens                      ,+    newtype                   ,+    parsers                   ,+    PrimitiveArray >= 0.5.1.0 ,+    semigroups                ,+    transformers              ,+    trifecta+  exposed-modules:+    FormalLanguage.GrammarProduct+    FormalLanguage.GrammarProduct.Op.Add+    FormalLanguage.GrammarProduct.Op.Chomsky+    FormalLanguage.GrammarProduct.Op.Chomsky.Proof+    FormalLanguage.GrammarProduct.Op.Common+    FormalLanguage.GrammarProduct.Op.Greibach+    FormalLanguage.GrammarProduct.Op.Greibach.Proof+    FormalLanguage.GrammarProduct.Op.Linear+    FormalLanguage.GrammarProduct.Op.Power+    FormalLanguage.GrammarProduct.Op.Subtract+    FormalLanguage.GrammarProduct.Parser+--    BioInf.GrammarProducts+--    BioInf.GrammarProducts.Grammar+--    BioInf.GrammarProducts.Haskell+--    BioInf.GrammarProducts.Helper+--    BioInf.GrammarProducts.LaTeX+--    BioInf.GrammarProducts.Tools+--    BioInf.GrammarProducts.TH+  ghc-options:+    -O2++-- With grammar products, we need a refined way of turning input source files+-- into LaTeX and Haskell modules.++executable GrammarProductPP+  build-depends:+    cmdargs == 0.10.*+  main-is:+    GramProd.hs+  ghc-options:+    -O2++source-repository head+  type: git+  location: git://github.com/choener/GrammarProducts+

+ LICENSE view

@@ -0,0 +1,675 @@+              GNU GENERAL PUBLIC LICENSE+                Version 3, 29 June 2007++ Copyright (C) 2007 Free Software Foundation, Inc. <http://fsf.org/>+ Everyone is permitted to copy and distribute verbatim copies+ of this license document, but changing it is not allowed.++                     Preamble++  The GNU General Public License is a free, copyleft license for+software and other kinds of works.++  The licenses for most software and other practical works are designed+to take away your freedom to share and change the works.  By contrast,+the GNU General Public License is intended to guarantee your freedom to+share and change all versions of a program--to make sure it remains free+software for all its users.  We, the Free Software Foundation, use the+GNU General Public License for most of our software; it applies also to+any other work released this way by its authors.  You can apply it to+your programs, too.++  When we speak of free software, we are referring to freedom, not+price.  Our General Public Licenses are designed to make sure that you+have the freedom to distribute copies of free software (and charge for+them if you wish), that you receive source code or can get it if you+want it, that you can change the software or use pieces of it in new+free programs, and that you know you can do these things.++  To protect your rights, we need to prevent others from denying you+these rights or asking you to surrender the rights.  Therefore, you have+certain responsibilities if you distribute copies of the software, or if+you modify it: responsibilities to respect the freedom of others.++  For example, if you distribute copies of such a program, whether+gratis or for a fee, you must pass on to the recipients the same+freedoms that you received.  You must make sure that they, too, receive+or can get the source code.  And you must show them these terms so they+know their rights.++  Developers that use the GNU GPL protect your rights with two steps:+(1) assert copyright on the software, and (2) offer you this License+giving you legal permission to copy, distribute and/or modify it.++  For the developers' and authors' protection, the GPL clearly explains+that there is no warranty for this free software.  For both users' and+authors' sake, the GPL requires that modified versions be marked as+changed, so that their problems will not be attributed erroneously to+authors of previous versions.++  Some devices are designed to deny users access to install or run+modified versions of the software inside them, although the manufacturer+can do so.  This is fundamentally incompatible with the aim of+protecting users' freedom to change the software.  The systematic+pattern of such abuse occurs in the area of products for individuals to+use, which is precisely where it is most unacceptable.  Therefore, we+have designed this version of the GPL to prohibit the practice for those+products.  If such problems arise substantially in other domains, we+stand ready to extend this provision to those domains in future versions+of the GPL, as needed to protect the freedom of users.++  Finally, every program is threatened constantly by software patents.+States should not allow patents to restrict development and use of+software on general-purpose computers, but in those that do, we wish to+avoid the special danger that patents applied to a free program could+make it effectively proprietary.  To prevent this, the GPL assures that+patents cannot be used to render the program non-free.++  The precise terms and conditions for copying, distribution and+modification follow.++                TERMS AND CONDITIONS++  0. Definitions.++  "This License" refers to version 3 of the GNU General Public License.++  "Copyright" also means copyright-like laws that apply to other kinds of+works, such as semiconductor masks.+ +  "The Program" refers to any copyrightable work licensed under this+License.  Each licensee is addressed as "you".  "Licensees" and+"recipients" may be individuals or organizations.++  To "modify" a work means to copy from or adapt all or part of the work+in a fashion requiring copyright permission, other than the making of an+exact copy.  The resulting work is called a "modified version" of the+earlier work or a work "based on" the earlier work.++  A "covered work" means either the unmodified Program or a work based+on the Program.++  To "propagate" a work means to do anything with it that, without+permission, would make you directly or secondarily liable for+infringement under applicable copyright law, except executing it on a+computer or modifying a private copy.  Propagation includes copying,+distribution (with or without modification), making available to the+public, and in some countries other activities as well.++  To "convey" a work means any kind of propagation that enables other+parties to make or receive copies.  Mere interaction with a user through+a computer network, with no transfer of a copy, is not conveying.++  An interactive user interface displays "Appropriate Legal Notices"+to the extent that it includes a convenient and prominently visible+feature that (1) displays an appropriate copyright notice, and (2)+tells the user that there is no warranty for the work (except to the+extent that warranties are provided), that licensees may convey the+work under this License, and how to view a copy of this License.  If+the interface presents a list of user commands or options, such as a+menu, a prominent item in the list meets this criterion.++  1. Source Code.++  The "source code" for a work means the preferred form of the work+for making modifications to it.  "Object code" means any non-source+form of a work.++  A "Standard Interface" means an interface that either is an official+standard defined by a recognized standards body, or, in the case of+interfaces specified for a particular programming language, one that+is widely used among developers working in that language.++  The "System Libraries" of an executable work include anything, other+than the work as a whole, that (a) is included in the normal form of+packaging a Major Component, but which is not part of that Major+Component, and (b) serves only to enable use of the work with that+Major Component, or to implement a Standard Interface for which an+implementation is available to the public in source code form.  A+"Major Component", in this context, means a major essential component+(kernel, window system, and so on) of the specific operating system+(if any) on which the executable work runs, or a compiler used to+produce the work, or an object code interpreter used to run it.++  The "Corresponding Source" for a work in object code form means all+the source code needed to generate, install, and (for an executable+work) run the object code and to modify the work, including scripts to+control those activities.  However, it does not include the work's+System Libraries, or general-purpose tools or generally available free+programs which are used unmodified in performing those activities but+which are not part of the work.  For example, Corresponding Source+includes interface definition files associated with source files for+the work, and the source code for shared libraries and dynamically+linked subprograms that the work is specifically designed to require,+such as by intimate data communication or control flow between those+subprograms and other parts of the work.++  The Corresponding Source need not include anything that users+can regenerate automatically from other parts of the Corresponding+Source.++  The Corresponding Source for a work in source code form is that+same work.++  2. Basic Permissions.++  All rights granted under this License are granted for the term of+copyright on the Program, and are irrevocable provided the stated+conditions are met.  This License explicitly affirms your unlimited+permission to run the unmodified Program.  The output from running a+covered work is covered by this License only if the output, given its+content, constitutes a covered work.  This License acknowledges your+rights of fair use or other equivalent, as provided by copyright law.++  You may make, run and propagate covered works that you do not+convey, without conditions so long as your license otherwise remains+in force.  You may convey covered works to others for the sole purpose+of having them make modifications exclusively for you, or provide you+with facilities for running those works, provided that you comply with+the terms of this License in conveying all material for which you do+not control copyright.  Those thus making or running the covered works+for you must do so exclusively on your behalf, under your direction+and control, on terms that prohibit them from making any copies of+your copyrighted material outside their relationship with you.++  Conveying under any other circumstances is permitted solely under+the conditions stated below.  Sublicensing is not allowed; section 10+makes it unnecessary.++  3. Protecting Users' Legal Rights From Anti-Circumvention Law.++  No covered work shall be deemed part of an effective technological+measure under any applicable law fulfilling obligations under article+11 of the WIPO copyright treaty adopted on 20 December 1996, or+similar laws prohibiting or restricting circumvention of such+measures.++  When you convey a covered work, you waive any legal power to forbid+circumvention of technological measures to the extent such circumvention+is effected by exercising rights under this License with respect to+the covered work, and you disclaim any intention to limit operation or+modification of the work as a means of enforcing, against the work's+users, your or third parties' legal rights to forbid circumvention of+technological measures.++  4. Conveying Verbatim Copies.++  You may convey verbatim copies of the Program's source code as you+receive it, in any medium, provided that you conspicuously and+appropriately publish on each copy an appropriate copyright notice;+keep intact all notices stating that this License and any+non-permissive terms added in accord with section 7 apply to the code;+keep intact all notices of the absence of any warranty; and give all+recipients a copy of this License along with the Program.++  You may charge any price or no price for each copy that you convey,+and you may offer support or warranty protection for a fee.++  5. Conveying Modified Source Versions.++  You may convey a work based on the Program, or the modifications to+produce it from the Program, in the form of source code under the+terms of section 4, provided that you also meet all of these conditions:++    a) The work must carry prominent notices stating that you modified+    it, and giving a relevant date.++    b) The work must carry prominent notices stating that it is+    released under this License and any conditions added under section+    7.  This requirement modifies the requirement in section 4 to+    "keep intact all notices".++    c) You must license the entire work, as a whole, under this+    License to anyone who comes into possession of a copy.  This+    License will therefore apply, along with any applicable section 7+    additional terms, to the whole of the work, and all its parts,+    regardless of how they are packaged.  This License gives no+    permission to license the work in any other way, but it does not+    invalidate such permission if you have separately received it.++    d) If the work has interactive user interfaces, each must display+    Appropriate Legal Notices; however, if the Program has interactive+    interfaces that do not display Appropriate Legal Notices, your+    work need not make them do so.++  A compilation of a covered work with other separate and independent+works, which are not by their nature extensions of the covered work,+and which are not combined with it such as to form a larger program,+in or on a volume of a storage or distribution medium, is called an+"aggregate" if the compilation and its resulting copyright are not+used to limit the access or legal rights of the compilation's users+beyond what the individual works permit.  Inclusion of a covered work+in an aggregate does not cause this License to apply to the other+parts of the aggregate.++  6. Conveying Non-Source Forms.++  You may convey a covered work in object code form under the terms+of sections 4 and 5, provided that you also convey the+machine-readable Corresponding Source under the terms of this License,+in one of these ways:++    a) Convey the object code in, or embodied in, a physical product+    (including a physical distribution medium), accompanied by the+    Corresponding Source fixed on a durable physical medium+    customarily used for software interchange.++    b) Convey the object code in, or embodied in, a physical product+    (including a physical distribution medium), accompanied by a+    written offer, valid for at least three years and valid for as+    long as you offer spare parts or customer support for that product+    model, to give anyone who possesses the object code either (1) a+    copy of the Corresponding Source for all the software in the+    product that is covered by this License, on a durable physical+    medium customarily used for software interchange, for a price no+    more than your reasonable cost of physically performing this+    conveying of source, or (2) access to copy the+    Corresponding Source from a network server at no charge.++    c) Convey individual copies of the object code with a copy of the+    written offer to provide the Corresponding Source.  This+    alternative is allowed only occasionally and noncommercially, and+    only if you received the object code with such an offer, in accord+    with subsection 6b.++    d) Convey the object code by offering access from a designated+    place (gratis or for a charge), and offer equivalent access to the+    Corresponding Source in the same way through the same place at no+    further charge.  You need not require recipients to copy the+    Corresponding Source along with the object code.  If the place to+    copy the object code is a network server, the Corresponding Source+    may be on a different server (operated by you or a third party)+    that supports equivalent copying facilities, provided you maintain+    clear directions next to the object code saying where to find the+    Corresponding Source.  Regardless of what server hosts the+    Corresponding Source, you remain obligated to ensure that it is+    available for as long as needed to satisfy these requirements.++    e) Convey the object code using peer-to-peer transmission, provided+    you inform other peers where the object code and Corresponding+    Source of the work are being offered to the general public at no+    charge under subsection 6d.++  A separable portion of the object code, whose source code is excluded+from the Corresponding Source as a System Library, need not be+included in conveying the object code work.++  A "User Product" is either (1) a "consumer product", which means any+tangible personal property which is normally used for personal, family,+or household purposes, or (2) anything designed or sold for incorporation+into a dwelling.  In determining whether a product is a consumer product,+doubtful cases shall be resolved in favor of coverage.  For a particular+product received by a particular user, "normally used" refers to a+typical or common use of that class of product, regardless of the status+of the particular user or of the way in which the particular user+actually uses, or expects or is expected to use, the product.  A product+is a consumer product regardless of whether the product has substantial+commercial, industrial or non-consumer uses, unless such uses represent+the only significant mode of use of the product.++  "Installation Information" for a User Product means any methods,+procedures, authorization keys, or other information required to install+and execute modified versions of a covered work in that User Product from+a modified version of its Corresponding Source.  The information must+suffice to ensure that the continued functioning of the modified object+code is in no case prevented or interfered with solely because+modification has been made.++  If you convey an object code work under this section in, or with, or+specifically for use in, a User Product, and the conveying occurs as+part of a transaction in which the right of possession and use of the+User Product is transferred to the recipient in perpetuity or for a+fixed term (regardless of how the transaction is characterized), the+Corresponding Source conveyed under this section must be accompanied+by the Installation Information.  But this requirement does not apply+if neither you nor any third party retains the ability to install+modified object code on the User Product (for example, the work has+been installed in ROM).++  The requirement to provide Installation Information does not include a+requirement to continue to provide support service, warranty, or updates+for a work that has been modified or installed by the recipient, or for+the User Product in which it has been modified or installed.  Access to a+network may be denied when the modification itself materially and+adversely affects the operation of the network or violates the rules and+protocols for communication across the network.++  Corresponding Source conveyed, and Installation Information provided,+in accord with this section must be in a format that is publicly+documented (and with an implementation available to the public in+source code form), and must require no special password or key for+unpacking, reading or copying.++  7. Additional Terms.++  "Additional permissions" are terms that supplement the terms of this+License by making exceptions from one or more of its conditions.+Additional permissions that are applicable to the entire Program shall+be treated as though they were included in this License, to the extent+that they are valid under applicable law.  If additional permissions+apply only to part of the Program, that part may be used separately+under those permissions, but the entire Program remains governed by+this License without regard to the additional permissions.++  When you convey a copy of a covered work, you may at your option+remove any additional permissions from that copy, or from any part of+it.  (Additional permissions may be written to require their own+removal in certain cases when you modify the work.)  You may place+additional permissions on material, added by you to a covered work,+for which you have or can give appropriate copyright permission.++  Notwithstanding any other provision of this License, for material you+add to a covered work, you may (if authorized by the copyright holders of+that material) supplement the terms of this License with terms:++    a) Disclaiming warranty or limiting liability differently from the+    terms of sections 15 and 16 of this License; or++    b) Requiring preservation of specified reasonable legal notices or+    author attributions in that material or in the Appropriate Legal+    Notices displayed by works containing it; or++    c) Prohibiting misrepresentation of the origin of that material, or+    requiring that modified versions of such material be marked in+    reasonable ways as different from the original version; or++    d) Limiting the use for publicity purposes of names of licensors or+    authors of the material; or++    e) Declining to grant rights under trademark law for use of some+    trade names, trademarks, or service marks; or++    f) Requiring indemnification of licensors and authors of that+    material by anyone who conveys the material (or modified versions of+    it) with contractual assumptions of liability to the recipient, for+    any liability that these contractual assumptions directly impose on+    those licensors and authors.++  All other non-permissive additional terms are considered "further+restrictions" within the meaning of section 10.  If the Program as you+received it, or any part of it, contains a notice stating that it is+governed by this License along with a term that is a further+restriction, you may remove that term.  If a license document contains+a further restriction but permits relicensing or conveying under this+License, you may add to a covered work material governed by the terms+of that license document, provided that the further restriction does+not survive such relicensing or conveying.++  If you add terms to a covered work in accord with this section, you+must place, in the relevant source files, a statement of the+additional terms that apply to those files, or a notice indicating+where to find the applicable terms.++  Additional terms, permissive or non-permissive, may be stated in the+form of a separately written license, or stated as exceptions;+the above requirements apply either way.++  8. Termination.++  You may not propagate or modify a covered work except as expressly+provided under this License.  Any attempt otherwise to propagate or+modify it is void, and will automatically terminate your rights under+this License (including any patent licenses granted under the third+paragraph of section 11).++  However, if you cease all violation of this License, then your+license from a particular copyright holder is reinstated (a)+provisionally, unless and until the copyright holder explicitly and+finally terminates your license, and (b) permanently, if the copyright+holder fails to notify you of the violation by some reasonable means+prior to 60 days after the cessation.++  Moreover, your license from a particular copyright holder is+reinstated permanently if the copyright holder notifies you of the+violation by some reasonable means, this is the first time you have+received notice of violation of this License (for any work) from that+copyright holder, and you cure the violation prior to 30 days after+your receipt of the notice.++  Termination of your rights under this section does not terminate the+licenses of parties who have received copies or rights from you under+this License.  If your rights have been terminated and not permanently+reinstated, you do not qualify to receive new licenses for the same+material under section 10.++  9. Acceptance Not Required for Having Copies.++  You are not required to accept this License in order to receive or+run a copy of the Program.  Ancillary propagation of a covered work+occurring solely as a consequence of using peer-to-peer transmission+to receive a copy likewise does not require acceptance.  However,+nothing other than this License grants you permission to propagate or+modify any covered work.  These actions infringe copyright if you do+not accept this License.  Therefore, by modifying or propagating a+covered work, you indicate your acceptance of this License to do so.++  10. Automatic Licensing of Downstream Recipients.++  Each time you convey a covered work, the recipient automatically+receives a license from the original licensors, to run, modify and+propagate that work, subject to this License.  You are not responsible+for enforcing compliance by third parties with this License.++  An "entity transaction" is a transaction transferring control of an+organization, or substantially all assets of one, or subdividing an+organization, or merging organizations.  If propagation of a covered+work results from an entity transaction, each party to that+transaction who receives a copy of the work also receives whatever+licenses to the work the party's predecessor in interest had or could+give under the previous paragraph, plus a right to possession of the+Corresponding Source of the work from the predecessor in interest, if+the predecessor has it or can get it with reasonable efforts.++  You may not impose any further restrictions on the exercise of the+rights granted or affirmed under this License.  For example, you may+not impose a license fee, royalty, or other charge for exercise of+rights granted under this License, and you may not initiate litigation+(including a cross-claim or counterclaim in a lawsuit) alleging that+any patent claim is infringed by making, using, selling, offering for+sale, or importing the Program or any portion of it.++  11. Patents.++  A "contributor" is a copyright holder who authorizes use under this+License of the Program or a work on which the Program is based.  The+work thus licensed is called the contributor's "contributor version".++  A contributor's "essential patent claims" are all patent claims+owned or controlled by the contributor, whether already acquired or+hereafter acquired, that would be infringed by some manner, permitted+by this License, of making, using, or selling its contributor version,+but do not include claims that would be infringed only as a+consequence of further modification of the contributor version.  For+purposes of this definition, "control" includes the right to grant+patent sublicenses in a manner consistent with the requirements of+this License.++  Each contributor grants you a non-exclusive, worldwide, royalty-free+patent license under the contributor's essential patent claims, to+make, use, sell, offer for sale, import and otherwise run, modify and+propagate the contents of its contributor version.++  In the following three paragraphs, a "patent license" is any express+agreement or commitment, however denominated, not to enforce a patent+(such as an express permission to practice a patent or covenant not to+sue for patent infringement).  To "grant" such a patent license to a+party means to make such an agreement or commitment not to enforce a+patent against the party.++  If you convey a covered work, knowingly relying on a patent license,+and the Corresponding Source of the work is not available for anyone+to copy, free of charge and under the terms of this License, through a+publicly available network server or other readily accessible means,+then you must either (1) cause the Corresponding Source to be so+available, or (2) arrange to deprive yourself of the benefit of the+patent license for this particular work, or (3) arrange, in a manner+consistent with the requirements of this License, to extend the patent+license to downstream recipients.  "Knowingly relying" means you have+actual knowledge that, but for the patent license, your conveying the+covered work in a country, or your recipient's use of the covered work+in a country, would infringe one or more identifiable patents in that+country that you have reason to believe are valid.+  +  If, pursuant to or in connection with a single transaction or+arrangement, you convey, or propagate by procuring conveyance of, a+covered work, and grant a patent license to some of the parties+receiving the covered work authorizing them to use, propagate, modify+or convey a specific copy of the covered work, then the patent license+you grant is automatically extended to all recipients of the covered+work and works based on it.++  A patent license is "discriminatory" if it does not include within+the scope of its coverage, prohibits the exercise of, or is+conditioned on the non-exercise of one or more of the rights that are+specifically granted under this License.  You may not convey a covered+work if you are a party to an arrangement with a third party that is+in the business of distributing software, under which you make payment+to the third party based on the extent of your activity of conveying+the work, and under which the third party grants, to any of the+parties who would receive the covered work from you, a discriminatory+patent license (a) in connection with copies of the covered work+conveyed by you (or copies made from those copies), or (b) primarily+for and in connection with specific products or compilations that+contain the covered work, unless you entered into that arrangement,+or that patent license was granted, prior to 28 March 2007.++  Nothing in this License shall be construed as excluding or limiting+any implied license or other defenses to infringement that may+otherwise be available to you under applicable patent law.++  12. No Surrender of Others' Freedom.++  If conditions are imposed on you (whether by court order, agreement or+otherwise) that contradict the conditions of this License, they do not+excuse you from the conditions of this License.  If you cannot convey a+covered work so as to satisfy simultaneously your obligations under this+License and any other pertinent obligations, then as a consequence you may+not convey it at all.  For example, if you agree to terms that obligate you+to collect a royalty for further conveying from those to whom you convey+the Program, the only way you could satisfy both those terms and this+License would be to refrain entirely from conveying the Program.++  13. Use with the GNU Affero General Public License.++  Notwithstanding any other provision of this License, you have+permission to link or combine any covered work with a work licensed+under version 3 of the GNU Affero General Public License into a single+combined work, and to convey the resulting work.  The terms of this+License will continue to apply to the part which is the covered work,+but the special requirements of the GNU Affero General Public License,+section 13, concerning interaction through a network will apply to the+combination as such.++  14. Revised Versions of this License.++  The Free Software Foundation may publish revised and/or new versions of+the GNU General Public License from time to time.  Such new versions will+be similar in spirit to the present version, but may differ in detail to+address new problems or concerns.++  Each version is given a distinguishing version number.  If the+Program specifies that a certain numbered version of the GNU General+Public License "or any later version" applies to it, you have the+option of following the terms and conditions either of that numbered+version or of any later version published by the Free Software+Foundation.  If the Program does not specify a version number of the+GNU General Public License, you may choose any version ever published+by the Free Software Foundation.++  If the Program specifies that a proxy can decide which future+versions of the GNU General Public License can be used, that proxy's+public statement of acceptance of a version permanently authorizes you+to choose that version for the Program.++  Later license versions may give you additional or different+permissions.  However, no additional obligations are imposed on any+author or copyright holder as a result of your choosing to follow a+later version.++  15. Disclaimer of Warranty.++  THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY+APPLICABLE LAW.  EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT+HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY+OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO,+THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR+PURPOSE.  THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM+IS WITH YOU.  SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF+ALL NECESSARY SERVICING, REPAIR OR CORRECTION.++  16. Limitation of Liability.++  IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING+WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MODIFIES AND/OR CONVEYS+THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY+GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE+USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF+DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD+PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS),+EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF+SUCH DAMAGES.++  17. Interpretation of Sections 15 and 16.++  If the disclaimer of warranty and limitation of liability provided+above cannot be given local legal effect according to their terms,+reviewing courts shall apply local law that most closely approximates+an absolute waiver of all civil liability in connection with the+Program, unless a warranty or assumption of liability accompanies a+copy of the Program in return for a fee.++              END OF TERMS AND CONDITIONS++     How to Apply These Terms to Your New Programs++  If you develop a new program, and you want it to be of the greatest+possible use to the public, the best way to achieve this is to make it+free software which everyone can redistribute and change under these terms.++  To do so, attach the following notices to the program.  It is safest+to attach them to the start of each source file to most effectively+state the exclusion of warranty; and each file should have at least+the "copyright" line and a pointer to where the full notice is found.++    <one line to give the program's name and a brief idea of what it does.>+    Copyright (C) <year>  <name of author>++    This program is free software: you can redistribute it and/or modify+    it under the terms of the GNU General Public License as published by+    the Free Software Foundation, either version 3 of the License, or+    (at your option) any later version.++    This program is distributed in the hope that it will be useful,+    but WITHOUT ANY WARRANTY; without even the implied warranty of+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the+    GNU General Public License for more details.++    You should have received a copy of the GNU General Public License+    along with this program.  If not, see <http://www.gnu.org/licenses/>.++Also add information on how to contact you by electronic and paper mail.++  If the program does terminal interaction, make it output a short+notice like this when it starts in an interactive mode:++    <program>  Copyright (C) <year>  <name of author>+    This program comes with ABSOLUTELY NO WARRANTY; for details type `show w'.+    This is free software, and you are welcome to redistribute it+    under certain conditions; type `show c' for details.++The hypothetical commands `show w' and `show c' should show the appropriate+parts of the General Public License.  Of course, your program's commands+might be different; for a GUI interface, you would use an "about box".++  You should also get your employer (if you work as a programmer) or school,+if any, to sign a "copyright disclaimer" for the program, if necessary.+For more information on this, and how to apply and follow the GNU GPL, see+<http://www.gnu.org/licenses/>.++  The GNU General Public License does not permit incorporating your program+into proprietary programs.  If your program is a subroutine library, you+may consider it more useful to permit linking proprietary applications with+the library.  If this is what you want to do, use the GNU Lesser General+Public License instead of this License.  But first, please read+<http://www.gnu.org/philosophy/why-not-lgpl.html>.+

+ Setup.hs view

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

+ changelog view

@@ -0,0 +1,2 @@+0.0.0.2+    * Products of linear and context-free grammars