{-| This model contains unit-tests for 'GLL.Combinators.Interface'.

= Included examples

  * Elementary parsers
  * Sequencing
  * Alternatives
  * Simple binding
  * Binding with alternatives
  * Recursion (non-left)

  * Higher-order patterns:

      * Optional
      * Kleene-closure / positive closure
      * Seperator
      * Inline choice

  * Ambiguities:

      * "aaa"
      * longambig
      * aho_s
      * EEE

  * Left recursion
  * Hidden left-recursion
-}
module GLL.Combinators.Test.BinaryInterface where

import Control.Monad
import Data.Char (ord)
import Data.List (sort, nub)
import Data.IORef

import GLL.Combinators.BinaryInterface
import GLL.Parseable.Char ()

-- | Defines and executes multiple1 unit-tests 
main :: IO ()
main = do
    IORef Integer
count <- Integer -> IO (IORef Integer)
forall a. a -> IO (IORef a)
newIORef Integer
1
    let test :: Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef a)
mref [Char]
name s t a
p t ([t], [a])
arg_pairs = do
            Integer
i <- IORef Integer -> IO Integer
forall a. IORef a -> IO a
readIORef IORef Integer
count
            IORef Integer -> (Integer -> Integer) -> IO ()
forall a. IORef a -> (a -> a) -> IO ()
modifyIORef IORef Integer
count Integer -> Integer
forall a. Enum a => a -> a
succ
            IORef Char
subcount <- Char -> IO (IORef Char)
forall a. a -> IO (IORef a)
newIORef Char
'a'
            [Char] -> IO ()
putStrLn ([Char]
">> testing " [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ Integer -> [Char]
forall a. Show a => a -> [Char]
show Integer
i [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
" (" [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
name [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
")")
            t ([t], [a]) -> (([t], [a]) -> IO ()) -> IO ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ t ([t], [a])
arg_pairs ((([t], [a]) -> IO ()) -> IO ()) -> (([t], [a]) -> IO ()) -> IO ()
forall a b. (a -> b) -> a -> b
$ \([t]
str,[a]
res) -> do
                case Maybe (MemoRef a)
mref of -- empty memtable between parses
                    Maybe (MemoRef a)
Nothing     -> () -> IO ()
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return ()
                    Just MemoRef a
ref    -> MemoRef a -> IO ()
forall a. MemoRef a -> IO ()
memClear MemoRef a
ref 
                Char
j <- IORef Char -> IO Char
forall a. IORef a -> IO a
readIORef IORef Char
subcount
                IORef Char -> (Char -> Char) -> IO ()
forall a. IORef a -> (a -> a) -> IO ()
modifyIORef IORef Char
subcount Char -> Char
forall a. Enum a => a -> a
succ
                let parse_res :: [a]
parse_res   = ParseOptions -> CombinatorOptions -> s t a -> [t] -> [a]
forall t (s :: * -> * -> *) a.
(Show t, Parseable t, IsSymbExpr s) =>
ParseOptions -> CombinatorOptions -> s t a -> [t] -> [a]
parseWithParseOptions [ParseOption
noSelectTest] [CombinatorOption
useMemoisation] s t a
p [t]
str
                    norm :: (Ord a, Eq a) => [a] -> [a]
                    norm :: forall a. (Ord a, Eq a) => [a] -> [a]
norm        = Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
take Int
100 ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
forall a. Ord a => [a] -> [a]
sort ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
forall a. Eq a => [a] -> [a]
nub
                    norm_p_res :: [a]
norm_p_res  = [a] -> [a]
forall a. (Ord a, Eq a) => [a] -> [a]
norm [a]
parse_res
                    b :: Bool
b           = [a]
norm_p_res [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
== [a] -> [a]
forall a. (Ord a, Eq a) => [a] -> [a]
norm [a]
res
                [Char] -> IO ()
putStrLn ([Char]
"  >> " [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char
j,Char
')',Char
' '] [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ Bool -> [Char]
forall a. Show a => a -> [Char]
show Bool
b)
                Bool -> IO () -> IO ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless Bool
b ([Char] -> IO ()
putStrLn ([Char]
"    >> " [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [a] -> [Char]
forall a. Show a => a -> [Char]
show [a]
norm_p_res))

    --  Elementary parsers
    Maybe (MemoRef Any)
-> [Char]
-> SymbExpr Char Integer
-> [([Char], [Integer])]
-> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"eps1" (Integer -> SymbExpr Char Integer
forall t a. (Show t, Ord t) => a -> BNF t a
satisfy Integer
0) [([Char]
"", [Integer
0])]
    Maybe (MemoRef Any)
-> [Char]
-> SymbExpr Char Integer
-> [([Char], [Integer])]
-> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"eps2" (Integer -> SymbExpr Char Integer
forall t a. (Show t, Ord t) => a -> BNF t a
satisfy Integer
0) [([Char]
"", [Integer
0]), ([Char]
"111", [])]
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Char -> [([Char], [Char])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"single" (Char -> SymbExpr Char Char
char Char
'a') [([Char]
"a", [Char
'a'])
                    ,([Char]
"abc", [])]
    Maybe (MemoRef Any)
-> [Char]
-> SymbExpr Char Integer
-> [([Char], [Integer])]
-> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"semfun1" (Integer
1 Integer -> SymbExpr Char Char -> SymbExpr Char Integer
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a') [([Char]
"a", [Integer
1])]

    --  Elementary combinators
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char [Char] -> [([Char], [[Char]])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"<**>" ((\Char
b -> [Char
'1',Char
b]) (Char -> [Char]) -> SymbExpr Char Char -> BNF Char (Char -> [Char])
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' BNF Char (Char -> [Char])
-> SymbExpr Char Char -> SymbExpr Char [Char]
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> Char -> SymbExpr Char Char
char Char
'b')
         [([Char]
"ab", [[Char]
"1b"])
         ,([Char]
"b", [])]
   
    --  Alternation
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"<||>" (Char -> Int
ord (Char -> Int) -> SymbExpr Char Char -> BNF Char (Char -> Int)
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' BNF Char (Char -> Int) -> SymbExpr Char Char -> SymbExpr Char Int
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> Char -> SymbExpr Char Char
char Char
'b' SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Char -> Int
ord (Char -> Int) -> SymbExpr Char Char -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> Char -> SymbExpr Char Char
char Char
'c')
         [([Char]
"a", []), ([Char]
"ab", [Int
98]), ([Char]
"c", [Int
99]), ([Char]
"cab", [])]

    --  Simple binding
    let pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<:=> Char -> Int
ord (Char -> Int) -> SymbExpr Char Char -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'b'
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"<:=>" SymbExpr Char Int
pX [([Char]
"ab",[Int
97]),([Char]
"a",[])]

    --  Simple binding
    let pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> Char -> Int
ord (Char -> Int) -> SymbExpr Char Char -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'b'
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"<::=>" SymbExpr Char Int
pX [([Char]
"ab",[Int
97]),([Char]
"a",[])]

    let  pX :: SymbExpr Char [Char]
pX = [Char]
"X" [Char] -> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<:=> (Char -> [Char] -> [Char]) -> [Char] -> Char -> [Char]
forall a b c. (a -> b -> c) -> b -> a -> c
flip (:) ([Char] -> Char -> [Char])
-> SymbExpr Char [Char] -> BNF Char (Char -> [Char])
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char [Char]
pY BNF Char (Char -> [Char])
-> SymbExpr Char Char -> SymbExpr Char [Char]
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> Char -> SymbExpr Char Char
char Char
'a'
         pY :: BNF Char String
         pY :: SymbExpr Char [Char]
pY = [Char]
"Y" [Char] -> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<:=> (\Char
x Char
y -> [Char
x,Char
y]) (Char -> Char -> [Char])
-> SymbExpr Char Char -> BNF Char (Char -> [Char])
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> Char -> SymbExpr Char Char
char Char
'b' BNF Char (Char -> [Char])
-> SymbExpr Char Char -> SymbExpr Char [Char]
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> Char -> SymbExpr Char Char
char Char
'c'
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char [Char] -> [([Char], [[Char]])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"<::=> 2" SymbExpr Char [Char]
pX [([Char]
"bca", [[Char]
"abc"]), ([Char]
"cba", [])]

    --  Binding with alternatives
    let pX :: SymbExpr Char Char
pX = [Char]
"X" [Char] -> SymbExpr Char Char -> SymbExpr Char Char
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> SymbExpr Char Char
pY SymbExpr Char Char -> SymbExpr Char Char -> SymbExpr Char Char
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'c'
        pY :: SymbExpr Char Char
pY = [Char]
"Y" [Char] -> SymbExpr Char Char -> SymbExpr Char Char
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char Char -> SymbExpr Char Char -> SymbExpr Char Char
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Char -> SymbExpr Char Char
char Char
'b'
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Char -> [([Char], [Char])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"<::=> <||>" SymbExpr Char Char
pX [([Char]
"ac", [Char]
"a"), ([Char]
"bc", [Char]
"b")]

    --  (Right) Recursion
    let pX :: BNF Char Int
        pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> (Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int -> Int) -> SymbExpr Char Char -> BNF Char (Int -> Int)
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' BNF Char (Int -> Int) -> SymbExpr Char Int -> SymbExpr Char Int
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char Int
pX SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => a -> BNF t a
satisfy Int
0 
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"rec1" SymbExpr Char Int
pX [([Char]
"", [Int
0]), ([Char]
"aa",[Int
2]), (Int -> Char -> [Char]
forall a. Int -> a -> [a]
replicate Int
42 Char
'a', [Int
42]), ([Char]
"bbb", [])]

    --  EBNF
    let pX :: BNF Char (Maybe Char)
pX = [Char]
"X" [Char] -> BNF Char (Maybe Char) -> BNF Char (Maybe Char)
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> Maybe Char -> Maybe Char
forall a. a -> a
id (Maybe Char -> Maybe Char)
-> SymbExpr Char Char -> BNF Char (Maybe Char -> Maybe Char)
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' BNF Char (Maybe Char -> Maybe Char)
-> SymbExpr Char Char -> BNF Char (Maybe Char -> Maybe Char)
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'b' BNF Char (Maybe Char -> Maybe Char)
-> BNF Char (Maybe Char) -> BNF Char (Maybe Char)
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char Char -> BNF Char (Maybe Char)
forall t a. (Show t, Ord t) => BNF t a -> BNF t (Maybe a)
optional (Char -> SymbExpr Char Char
char Char
'z')
    Maybe (MemoRef Any)
-> [Char]
-> BNF Char (Maybe Char)
-> [([Char], [Maybe Char])]
-> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"optional" BNF Char (Maybe Char)
pX [([Char]
"abz", [Char -> Maybe Char
forall a. a -> Maybe a
Just Char
'z']), ([Char]
"abab", []), ([Char]
"ab", [Maybe Char
forall a. Maybe a
Nothing])]

    let pX :: SymbExpr Char Char
pX = [Char]
"X" [Char] -> SymbExpr Char Char -> SymbExpr Char Char
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> (Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char Char -> SymbExpr Char Char -> SymbExpr Char Char
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Char -> SymbExpr Char Char
char Char
'b')
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Char -> [([Char], [Char])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"<||> optional" (SymbExpr Char Char
pX SymbExpr Char Char -> BNF Char (Maybe Char) -> SymbExpr Char Char
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** SymbExpr Char Char -> BNF Char (Maybe Char)
forall t a. (Show t, Ord t) => BNF t a -> BNF t (Maybe a)
optional (Char -> SymbExpr Char Char
char Char
'z'))
                [([Char]
"az", [Char]
"a"), ([Char]
"bz", [Char]
"b"), ([Char]
"z", []), ([Char]
"b", [Char]
"b"), ([Char]
"a", [Char]
"a")]

    let pX :: BNF Char Int
        pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> (Int
1 Int -> BNF Char (Maybe Char) -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ SymbExpr Char Char -> BNF Char (Maybe Char)
forall t a. (Show t, Ord t) => BNF t a -> BNF t (Maybe a)
optional (Char -> SymbExpr Char Char
char Char
'a') SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int
2 Int -> BNF Char (Maybe Char) -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ SymbExpr Char Char -> BNF Char (Maybe Char)
forall t a. (Show t, Ord t) => BNF t a -> BNF t (Maybe a)
optional (Char -> SymbExpr Char Char
char Char
'b'))
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"optional-ambig" (SymbExpr Char Int
pX SymbExpr Char Int -> BNF Char (Maybe Char) -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** SymbExpr Char Char -> BNF Char (Maybe Char)
forall t a. (Show t, Ord t) => BNF t a -> BNF t (Maybe a)
optional (Char -> SymbExpr Char Char
char Char
'z'))
                [([Char]
"az", [Int
1]), ([Char]
"bz", [Int
2]), ([Char]
"z", [Int
1,Int
2]), ([Char]
"b", [Int
2]), ([Char]
"a", [Int
1])]

    let pX :: BNF Char Char 
        pX :: SymbExpr Char Char
pX = [Char]
"X" [Char] -> SymbExpr Char Char -> SymbExpr Char Char
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> Char -> Char
forall a. a -> a
id (Char -> Char) -> SymbExpr Char Char -> BNF Char (Char -> Char)
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' BNF Char (Char -> Char) -> SymbExpr Char Char -> SymbExpr Char Char
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> (Char -> SymbExpr Char Char
char Char
'b' SymbExpr Char Char -> SymbExpr Char Char -> SymbExpr Char Char
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Char -> SymbExpr Char Char
char Char
'c')
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Char -> [([Char], [Char])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"inline choice (1)" SymbExpr Char Char
pX
                [([Char]
"ab", [Char]
"b"), ([Char]
"ac", [Char]
"c"), ([Char]
"a", []), ([Char]
"b", [])]

    let pX :: BNF Char Int
        pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> [Char] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([Char] -> Int) -> SymbExpr Char [Char] -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Char -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t [a]
multiple (Char -> SymbExpr Char Char
char Char
'1')
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"multiple" SymbExpr Char Int
pX [([Char]
"", [Int
0]), ([Char]
"11", [Int
2]), (Int -> Char -> [Char]
forall a. Int -> a -> [a]
replicate Int
12 Char
'1', [Int
12])]

    let pX :: BNF Char Int
        pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> [Char] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([Char] -> Int) -> SymbExpr Char [Char] -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Char -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t [a]
multiple1 (Char -> SymbExpr Char Char
char Char
'1')
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"multiple1" SymbExpr Char Int
pX [([Char]
"", []), ([Char]
"11", [Int
2]), (Int -> Char -> [Char]
forall a. Int -> a -> [a]
replicate Int
12 Char
'1', [Int
12])]

    let pX :: BNF Char Int
        pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> Int
1 Int -> SymbExpr Char [Char] -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ SymbExpr Char Char -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t [a]
multiple (Char -> SymbExpr Char Char
char Char
'a') SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int
2 Int -> SymbExpr Char [Char] -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ SymbExpr Char Char -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t [a]
multiple (Char -> SymbExpr Char Char
char Char
'b')
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"(multiple <||> multiple) <**> optional" (SymbExpr Char Int
pX SymbExpr Char Int -> BNF Char (Maybe Char) -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** SymbExpr Char Char -> BNF Char (Maybe Char)
forall t a. (Show t, Ord t) => BNF t a -> BNF t (Maybe a)
optional (Char -> SymbExpr Char Char
char Char
'z'))
                [([Char]
"az", [Int
1]), ([Char]
"bz", [Int
2]), ([Char]
"z", [Int
1,Int
2])
                ,([Char]
"", [Int
1,Int
2]), ([Char]
"b", [Int
2]), ([Char]
"a", [Int
1])]

    let pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> SymbExpr Char Int
pY SymbExpr Char Int -> BNF Char (Maybe Char) -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** SymbExpr Char Char -> BNF Char (Maybe Char)
forall t a. (Show t, Ord t) => BNF t a -> BNF t (Maybe a)
optional (Char -> SymbExpr Char Char
char Char
'z')
         where pY :: SymbExpr Char Int
pY = [Char]
"Y" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> [Char] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([Char] -> Int) -> SymbExpr Char [Char] -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Char -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t [a]
multiple (Char -> SymbExpr Char Char
char Char
'a')
                          SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> [Char] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([Char] -> Int) -> SymbExpr Char [Char] -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Char -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t [a]
multiple1 (Char -> SymbExpr Char Char
char Char
'b') SymbExpr Char Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'e'
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"multiple & multiple1 & optional" 
        SymbExpr Char Int
pX  [([Char]
"aaaz", [Int
3]), ([Char]
"bbbez", [Int
3]), ([Char]
"ez", []), ([Char]
"z", [Int
0])
            ,([Char]
"aa", [Int
2]), ([Char]
"bbe", [Int
2]) 
            ]

    -- multiple with nullable argument
    let pX :: BNF Char Int
        pX :: SymbExpr Char Int
pX = Int
1 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'1' SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => a -> BNF t a
satisfy Int
0
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char [Int] -> [([Char], [[Int]])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"multiple (nullable arg)" 
        (SymbExpr Char Int -> SymbExpr Char [Int]
forall t a. (Show t, Ord t) => BNF t a -> BNF t [a]
multiple SymbExpr Char Int
pX) [([Char]
"11", [[Int
1,Int
1]]), ([Char]
"",[[]]), ([Char]
"e", [])]

    --  Simple ambiguities
    let pX :: SymbExpr Char [Char]
pX = [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
(++) ([Char] -> [Char] -> [Char])
-> SymbExpr Char [Char] -> BNF Char ([Char] -> [Char])
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char [Char]
pA BNF Char ([Char] -> [Char])
-> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char [Char]
pB
        pA :: SymbExpr Char [Char]
pA = [Char]
"a" [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char [Char]
-> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> [Char]
"aa" [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'a'
        pB :: SymbExpr Char [Char]
pB = [Char]
"b" [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char [Char]
-> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> [Char]
"bb" [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'a' 
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char [Char] -> [([Char], [[Char]])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"aaa" SymbExpr Char [Char]
pX   [([Char]
"aaa", [[Char]
"aab", [Char]
"abb"])
                    ,([Char]
"aa", [[Char]
"ab"])]

    let pX :: SymbExpr Char [Int]
pX = (\Int
x Int
y -> [Int
x,Int
y]) (Int -> Int -> [Int])
-> SymbExpr Char Char -> BNF Char (Int -> Int -> [Int])
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' BNF Char (Int -> Int -> [Int])
-> SymbExpr Char Int -> BNF Char (Int -> [Int])
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char Int
pL BNF Char (Int -> [Int]) -> SymbExpr Char Int -> SymbExpr Char [Int]
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char Int
pL SymbExpr Char [Int] -> SymbExpr Char Char -> SymbExpr Char [Int]
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'e'
        pL :: BNF Char Int
        pL :: SymbExpr Char Int
pL =    Int
1 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'b'
            SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int
2 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'b' SymbExpr Char Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'c'
            SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int
3 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'c' SymbExpr Char Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'd'
            SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int
4 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'd'
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char [Int] -> [([Char], [[Int]])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"longambig" SymbExpr Char [Int]
pX [([Char]
"abcde", [[Int
1,Int
3],[Int
2,Int
4]]), ([Char]
"abcdd", [])]

    let pX :: BNF Char Int
        pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> (Int
1 Int -> SymbExpr Char [Char] -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ SymbExpr Char Char -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t [a]
multiple1 (Char -> SymbExpr Char Char
char Char
'a') SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int
2 Int -> SymbExpr Char [Char] -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ SymbExpr Char Char -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t [a]
multiple (Char -> SymbExpr Char Char
char Char
'b'))
        pY :: SymbExpr Char Int
pY = [Char]
"Y" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) (Int -> Int -> Int) -> SymbExpr Char Int -> BNF Char (Int -> Int)
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Int
pX BNF Char (Int -> Int) -> SymbExpr Char Int -> SymbExpr Char Int
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char Int
pY
                   SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => a -> BNF t a
satisfy Int
0
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"multiple1 & multiple & recursion + ambiguities" SymbExpr Char Int
pY
        [([Char]
"ab", [Int
3]),([Char]
"aa", [Int
1,Int
2]), (Int -> Char -> [Char]
forall a. Int -> a -> [a]
replicate Int
10 Char
'a', [Int
1..Int
10])]

    let pX :: BNF Char Int
        pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=>  Int
1 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => a -> BNF t a
satisfy Int
0
        pY :: SymbExpr Char Int
pY = [Char]
"Y" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) (Int -> Int -> Int) -> SymbExpr Char Int -> BNF Char (Int -> Int)
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Int
pX BNF Char (Int -> Int) -> SymbExpr Char Int -> SymbExpr Char Int
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char Int
pY
    -- shouldn't this be 1 + infinite 0's?
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"no parse infinite rec?" SymbExpr Char Int
pY 
        [([Char]
"a", [])]

    let pS :: BNF Char Int
        pS :: SymbExpr Char Int
pS = [Char]
"S" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> ((\Int
x Int
y -> Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
yInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int -> Int -> Int)
-> SymbExpr Char Char -> BNF Char (Int -> Int -> Int)
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'1' BNF Char (Int -> Int -> Int)
-> SymbExpr Char Int -> BNF Char (Int -> Int)
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char Int
pS BNF Char (Int -> Int) -> SymbExpr Char Int -> SymbExpr Char Int
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char Int
pS) SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => a -> BNF t a
satisfy Int
0    
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"aho_S" SymbExpr Char Int
pS [([Char]
"", [Int
0]), ([Char]
"1", [Int
1]), (Int -> Char -> [Char]
forall a. Int -> a -> [a]
replicate Int
5 Char
'1', [Int
5])]


    let pS :: SymbExpr Char [Char]
pS = [Char]
"S" [Char] -> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> ((\[Char]
x [Char]
y -> Char
'1'Char -> [Char] -> [Char]
forall a. a -> [a] -> [a]
:[Char]
x[Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++[Char]
y) ([Char] -> [Char] -> [Char])
-> SymbExpr Char Char -> BNF Char ([Char] -> [Char] -> [Char])
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'1' BNF Char ([Char] -> [Char] -> [Char])
-> SymbExpr Char [Char] -> BNF Char ([Char] -> [Char])
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char [Char]
pS BNF Char ([Char] -> [Char])
-> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char [Char]
pS) SymbExpr Char [Char]
-> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> [Char] -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => a -> BNF t a
satisfy [Char]
"0"
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char [Char] -> [([Char], [[Char]])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"aho_S" SymbExpr Char [Char]
pS [([Char]
"", [[Char]
"0"]), ([Char]
"1", [[Char]
"100"]), ([Char]
"11", [[Char]
"10100", [Char]
"11000"])
                    ,(Int -> Char -> [Char]
forall a. Int -> a -> [a]
replicate Int
5 Char
'1', [[Char]]
aho_S_5)]

    let pE :: BNF Char Int
        pE :: SymbExpr Char Int
pE = [Char]
"E" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> (\Int
x Int
y Int
z -> Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
yInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
z) (Int -> Int -> Int -> Int)
-> SymbExpr Char Int -> BNF Char (Int -> Int -> Int)
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Int
pE BNF Char (Int -> Int -> Int)
-> SymbExpr Char Int -> BNF Char (Int -> Int)
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char Int
pE BNF Char (Int -> Int) -> SymbExpr Char Int -> SymbExpr Char Int
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char Int
pE 
                             SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int
1 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'1'
                             SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => a -> BNF t a
satisfy Int
0
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"EEE" SymbExpr Char Int
pE [([Char]
"", [Int
0]), ([Char]
"1", [Int
1]), ([Char]
"11", [Int
2])
                  ,(Int -> Char -> [Char]
forall a. Int -> a -> [a]
replicate Int
5 Char
'1', [Int
5]), ([Char]
"112", [])]

    let pE :: SymbExpr Char [Char]
pE = [Char]
"E" [Char] -> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> (\[Char]
x [Char]
y [Char]
z -> [Char]
x[Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++[Char]
y[Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++[Char]
z) ([Char] -> [Char] -> [Char] -> [Char])
-> SymbExpr Char [Char] -> BNF Char ([Char] -> [Char] -> [Char])
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char [Char]
pE BNF Char ([Char] -> [Char] -> [Char])
-> SymbExpr Char [Char] -> BNF Char ([Char] -> [Char])
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char [Char]
pE BNF Char ([Char] -> [Char])
-> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char [Char]
pE 
                             SymbExpr Char [Char]
-> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> [Char]
"1" [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'1'
                             SymbExpr Char [Char]
-> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> [Char] -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => a -> BNF t a
satisfy [Char]
"0"
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char [Char] -> [([Char], [[Char]])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"EEE ambig" SymbExpr Char [Char]
pE [([Char]
"", [[Char]
"0"]), ([Char]
"1", [[Char]
"1"])
                        ,([Char]
"11", [[Char]
"110", [Char]
"011", [Char]
"101"]), ([Char]
"111", [[Char]]
_EEE_3)]

    let pX :: BNF Char Int
        pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=>  Int -> (Char -> Int) -> Maybe Char -> Int
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Int
0 (Int -> Char -> Int
forall a b. a -> b -> a
const Int
1) (Maybe Char -> Int) -> BNF Char (Maybe Char) -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Char -> BNF Char (Maybe Char)
forall t a. (Show t, Ord t) => BNF t a -> BNF t (Maybe a)
optional (Char -> SymbExpr Char Char
char Char
'z') 
                    SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> (Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int -> Int) -> SymbExpr Char Int -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Int
pX SymbExpr Char Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'1'
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"simple left-recursion" SymbExpr Char Int
pX [([Char]
"", [Int
0]), ([Char]
"z11", [Int
3]), ([Char]
"z", [Int
1])
                                    ,(Int -> Char -> [Char]
forall a. Int -> a -> [a]
replicate Int
100 Char
'1', [Int
100])]

    let pX :: BNF Char Int
        pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => a -> BNF t a
satisfy Int
0 
                    SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> (Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int -> Int) -> SymbExpr Char Int -> BNF Char (Int -> Int)
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ SymbExpr Char Int
pB BNF Char (Int -> Int) -> SymbExpr Char Int -> SymbExpr Char Int
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char Int
pX SymbExpr Char Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'1'
        pB :: BNF Char Int 
        pB :: SymbExpr Char Int
pB = Int -> (Char -> Int) -> Maybe Char -> Int
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Int
0 (Int -> Char -> Int
forall a b. a -> b -> a
const Int
0) (Maybe Char -> Int) -> BNF Char (Maybe Char) -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Char -> BNF Char (Maybe Char)
forall t a. (Show t, Ord t) => BNF t a -> BNF t (Maybe a)
optional (Char -> SymbExpr Char Char
char Char
'z')
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"hidden left-recursion" SymbExpr Char Int
pX 
        [([Char]
"", [Int
0]), ([Char]
"zz11", [Int
2]), ([Char]
"z11", [Int
2]), ([Char]
"11", [Int
2])
        ,(Int -> Char -> [Char]
forall a. Int -> a -> [a]
replicate Int
100 Char
'1', [Int
100])]

    let pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) (Int -> Int -> Int) -> SymbExpr Char Int -> BNF Char (Int -> Int)
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Int
pY BNF Char (Int -> Int) -> SymbExpr Char Int -> SymbExpr Char Int
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char Int
pA
        pA :: BNF Char Int 
        pA :: SymbExpr Char Int
pA = Int
1 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'b' SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => a -> BNF t a
satisfy Int
0
        pY :: SymbExpr Char Int
pY = [Char]
"Y" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => a -> BNF t a
satisfy Int
0 SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> SymbExpr Char Int
pX 
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"hidden left-recursion + infinite derivations" SymbExpr Char Int
pX
        [([Char]
"", [Int
0]), ([Char]
"ab", [Int
1]), ([Char]
"ababab", [Int
3])]

    [Char] -> IO ()
putStrLn [Char]
"Tests that use memoisation"

    let tab :: MemoRef a
tab = MemoRef a
forall a. MemoRef a
newMemoTable
        pX :: BNF Char Int
        pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> (Int
1 Int -> SymbExpr Char [Char] -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ SymbExpr Char Char -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t [a]
multiple1 (Char -> SymbExpr Char Char
char Char
'a') SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int
2 Int -> SymbExpr Char [Char] -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ SymbExpr Char Char -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t [a]
multiple (Char -> SymbExpr Char Char
char Char
'b'))
        pY :: SymbExpr Char Int
pY = MemoRef [Int] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Ord t, Show t) => MemoRef [a] -> BNF t a -> BNF t a
memo MemoRef [Int]
forall a. MemoRef a
tab ([Char]
"Y" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) (Int -> Int -> Int) -> SymbExpr Char Int -> BNF Char (Int -> Int)
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Int
pX BNF Char (Int -> Int) -> SymbExpr Char Int -> SymbExpr Char Int
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char Int
pY
                   SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => a -> BNF t a
satisfy Int
0)
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test (MemoRef Any -> Maybe (MemoRef Any)
forall a. a -> Maybe a
Just MemoRef Any
forall a. MemoRef a
tab) [Char]
"multiple1 & multiple & recursion + ambiguities" SymbExpr Char Int
pY
        [([Char]
"ab", [Int
3]),([Char]
"aa", [Int
1,Int
2]), (Int -> Char -> [Char]
forall a. Int -> a -> [a]
replicate Int
10 Char
'a', [Int
1..Int
10])]

    let tab :: MemoRef a
tab = MemoRef a
forall a. MemoRef a
newMemoTable 
        pX :: BNF Char Int
        pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=>  Int
1 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => a -> BNF t a
satisfy Int
0
        pY :: SymbExpr Char Int
pY = MemoRef [Int] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Ord t, Show t) => MemoRef [a] -> BNF t a -> BNF t a
memo MemoRef [Int]
forall a. MemoRef a
tab ([Char]
"Y" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) (Int -> Int -> Int) -> SymbExpr Char Int -> BNF Char (Int -> Int)
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Int
pX BNF Char (Int -> Int) -> SymbExpr Char Int -> SymbExpr Char Int
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char Int
pY)
    -- shouldn't this be 1 + infinite 0's?
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test (MemoRef Any -> Maybe (MemoRef Any)
forall a. a -> Maybe a
Just MemoRef Any
forall a. MemoRef a
tab) [Char]
"no parse infinite rec?" SymbExpr Char Int
pY 
        [([Char]
"a", [])]

    --  Higher ambiguities
    let tab :: MemoRef a
tab = MemoRef a
forall a. MemoRef a
newMemoTable
        pE :: BNF Char Int
        pE :: SymbExpr Char Int
pE = MemoRef [Int] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Ord t, Show t) => MemoRef [a] -> BNF t a -> BNF t a
memo MemoRef [Int]
forall a. MemoRef a
tab ([Char]
"E" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> (\Int
x Int
y Int
z -> Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
yInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
z) (Int -> Int -> Int -> Int)
-> SymbExpr Char Int -> BNF Char (Int -> Int -> Int)
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Int
pE BNF Char (Int -> Int -> Int)
-> SymbExpr Char Int -> BNF Char (Int -> Int)
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char Int
pE BNF Char (Int -> Int) -> SymbExpr Char Int -> SymbExpr Char Int
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char Int
pE 
                             SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int
1 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'1'
                             SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => a -> BNF t a
satisfy Int
0)
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test (MemoRef Any -> Maybe (MemoRef Any)
forall a. a -> Maybe a
Just MemoRef Any
forall a. MemoRef a
tab) [Char]
"EEE" SymbExpr Char Int
pE [([Char]
"", [Int
0]), ([Char]
"1", [Int
1]), ([Char]
"11", [Int
2])
                             ,(Int -> Char -> [Char]
forall a. Int -> a -> [a]
replicate Int
5 Char
'1', [Int
5]), ([Char]
"112", [])]

    let tab :: MemoRef a
tab = MemoRef a
forall a. MemoRef a
newMemoTable
        pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) (Int -> Int -> Int) -> SymbExpr Char Int -> BNF Char (Int -> Int)
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Int
pY BNF Char (Int -> Int) -> SymbExpr Char Int -> SymbExpr Char Int
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char Int
pA
        pA :: BNF Char Int
        pA :: SymbExpr Char Int
pA = Int
1 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'b' SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => a -> BNF t a
satisfy Int
0
        pY :: SymbExpr Char Int
pY = MemoRef [Int] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Ord t, Show t) => MemoRef [a] -> BNF t a -> BNF t a
memo MemoRef [Int]
forall a. MemoRef a
tab ([Char]
"Y" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => a -> BNF t a
satisfy Int
0 SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> SymbExpr Char Int
pX)
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test (MemoRef Any -> Maybe (MemoRef Any)
forall a. a -> Maybe a
Just MemoRef Any
forall a. MemoRef a
tab) [Char]
"hidden left-recursion + infinite derivations" SymbExpr Char Int
pX
        [([Char]
"", [Int
0]), ([Char]
"ab", [Int
1]), ([Char]
"ababab", [Int
3])]

    [Char] -> IO ()
putStrLn [Char]
"Testing ambiguity reduction combinators"
    let pX :: SymbExpr Char [Char]
pX = [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
(++) ([Char] -> [Char] -> [Char])
-> SymbExpr Char [Char] -> BNF Char ([Char] -> [Char])
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char [Char]
pA BNF Char ([Char] -> [Char])
-> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**>>> SymbExpr Char [Char]
pB
        pA :: SymbExpr Char [Char]
pA = [Char]
"a" [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char [Char]
-> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> [Char]
"aa" [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'a'
        pB :: SymbExpr Char [Char]
pB = [Char]
"b" [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char [Char]
-> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> [Char]
"bb" [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'a' 
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char [Char] -> [([Char], [[Char]])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"A<A" SymbExpr Char [Char]
pX   [([Char]
"aaa", [[Char]
"aab"]),([Char]
"aa", [[Char]
"ab"])]

    let pX :: SymbExpr Char [Char]
pX = [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
(++) ([Char] -> [Char] -> [Char])
-> SymbExpr Char [Char] -> BNF Char ([Char] -> [Char])
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char [Char]
pA BNF Char ([Char] -> [Char])
-> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<<<**> SymbExpr Char [Char]
pB
        pA :: SymbExpr Char [Char]
pA = [Char]
"a" [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char [Char]
-> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> [Char]
"aa" [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'a'
        pB :: SymbExpr Char [Char]
pB = [Char]
"b" [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char [Char]
-> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> [Char]
"bb" [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'a' SymbExpr Char [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'a' 
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char [Char] -> [([Char], [[Char]])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"A>A" SymbExpr Char [Char]
pX   [([Char]
"aaa", [[Char]
"abb"]),([Char]
"aa", [[Char]
"ab"])] 

    let pX :: SymbExpr Char [Int]
pX = [Char]
"X" [Char] -> SymbExpr Char [Int] -> SymbExpr Char [Int]
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<:=> SymbExpr Char Int -> SymbExpr Char [Int]
forall t a. (Show t, Ord t) => BNF t a -> BNF t [a]
multiple SymbExpr Char Int
pY
         where pY :: BNF Char Int
               pY :: SymbExpr Char Int
pY = Int
1 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'1' SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int
2 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'1' SymbExpr Char Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'1'
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char [Int] -> [([Char], [[Int]])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"multiple" SymbExpr Char [Int]
pX 
      [([Char]
"", [[]]), ([Char]
"1", [[Int
1]]), ([Char]
"11", [[Int
1,Int
1],[Int
2]]), ([Char]
"111", [[Int
1,Int
1,Int
1], [Int
2,Int
1], [Int
1,Int
2]])]

    let pX :: SymbExpr Char [Int]
pX = [Char]
"X" [Char] -> SymbExpr Char [Int] -> SymbExpr Char [Int]
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<:=> SymbExpr Char Int -> SymbExpr Char [Int]
forall t a. (Show t, Ord t) => BNF t a -> BNF t [a]
some SymbExpr Char Int
pY
         where pY :: BNF Char Int
               pY :: SymbExpr Char Int
pY = Int
1 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'1' SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int
2 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'1' SymbExpr Char Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'1'
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char [Int] -> [([Char], [[Int]])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"some" SymbExpr Char [Int]
pX 
      [([Char]
"", [[]]), ([Char]
"1", [[Int
1]]), ([Char]
"11", [[Int
2]]), ([Char]
"111", [[Int
2,Int
1]])]

{-
    -- a combinatar `fewest` (variant of multiple) should behave as follows
    let pX = "X" <:=> fewest pY
         where pY = 1 <$$ char '1' <||> 2 <$$ char '1' <** char '1'
    test Nothing "some" pX 
      [("", [[]]), ("1", [[1]]), ("11", [[2]]), ("111", [[2,1], [1,2]])]
-}

    let pX :: SymbExpr Char [Int]
pX = [Char]
"X" [Char] -> SymbExpr Char [Int] -> SymbExpr Char [Int]
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<:=> SymbExpr Char Int -> SymbExpr Char [Int]
forall t a. (Show t, Ord t) => BNF t a -> BNF t [a]
many SymbExpr Char Int
pY
         where pY :: BNF Char Int 
               pY :: SymbExpr Char Int
pY = Int
1 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'1' SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int
2 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'1' SymbExpr Char Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'1'
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char [Int] -> [([Char], [[Int]])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"many" SymbExpr Char [Int]
pX 
      [([Char]
"", [[]]), ([Char]
"1", [[Int
1]]), ([Char]
"11", [[Int
1,Int
1]]), ([Char]
"111", [[Int
1,Int
1,Int
1]])]
 
    let pX :: SymbExpr Char [Char]
pX = [Char]
"X" [Char] -> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<:=> [Char]
"1" [Char] -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'1' SymbExpr Char [Char]
-> SymbExpr Char [Char] -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> SymbExpr Char Char -> SymbExpr Char Char -> SymbExpr Char [Char]
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t [a]
multipleSepBy (Char -> SymbExpr Char Char
char Char
'1') (Char -> SymbExpr Char Char
char Char
';')
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char [Char] -> [([Char], [[Char]])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"multipleSepBy" SymbExpr Char [Char]
pX
      [([Char]
"", [[Char]
""]), ([Char]
"1", [[Char]
"1", [Char]
"1"]), ([Char]
"1;1", [[Char]
"11"])]

    -- pX matches epsilon, therefore leading to infinitely many derivations
    let pX :: BNF Char Int 
        pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> Int
1 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'1' SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> [Int] -> Int
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum ([Int] -> Int) -> SymbExpr Char [Int] -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Int -> SymbExpr Char Char -> SymbExpr Char [Int]
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t [a]
multipleSepBy SymbExpr Char Int
pX (Char -> SymbExpr Char Char
char Char
';')
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"multipleSepBy2" SymbExpr Char Int
pX
      [([Char]
"", [Int
0]), ([Char]
"1", [Int
1,Int
1]), ([Char]
"1;1", [Int
2]), ([Char]
";1", [Int
1]),  ([Char]
";1;1", [Int
2])]

    let pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<:=> [Char] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([Char] -> Int) -> SymbExpr Char [Char] -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Char -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t [a]
multiple (Char -> SymbExpr Char Char
char Char
'1')
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"multiple1" SymbExpr Char Int
pX
      [([Char]
"", [Int
0]), ([Char]
"11", [Int
2]), (Int -> Char -> [Char]
forall a. Int -> a -> [a]
replicate Int
10 Char
'1', [Int
10])]

    let pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<:=> [Char] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([Char] -> Int) -> SymbExpr Char [Char] -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Char -> SymbExpr Char [Char]
forall t a. (Show t, Ord t) => BNF t a -> BNF t [a]
multiple (Char -> SymbExpr Char Char
char Char
'1') SymbExpr Char Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'z'
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"multiple2" SymbExpr Char Int
pX
      [([Char]
"", []), ([Char]
"11z", [Int
2]), (Int -> Char -> [Char]
forall a. Int -> a -> [a]
replicate Int
10 Char
'1' [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
"z", [Int
10])]

    let pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<:=> [()] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([()] -> Int) -> BNF Char [()] -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> BNF Char () -> BNF Char [()]
forall t a. (Show t, Ord t) => BNF t a -> BNF t [a]
multiple BNF Char ()
pEps SymbExpr Char Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t a
<** Char -> SymbExpr Char Char
char Char
'z'
          where pEps :: BNF Char ()
pEps = () -> BNF Char ()
forall t a. (Show t, Ord t) => a -> BNF t a
satisfy () BNF Char () -> BNF Char () -> BNF Char ()
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> () () -> SymbExpr Char Char -> BNF Char ()
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'1'
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"multiple & epsilon" SymbExpr Char Int
pX
      [([Char]
"", []), ([Char]
"z", [Int
0])]

    let pX :: BNF Char Int 
        pX :: SymbExpr Char Int
pX = [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> Int
1 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'1' SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> [Int] -> Int
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum ([Int] -> Int) -> SymbExpr Char [Int] -> SymbExpr Char Int
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Int -> SymbExpr Char Char -> SymbExpr Char [Int]
forall t a b. (Show t, Ord t) => BNF t a -> BNF t b -> BNF t [a]
multipleSepBy SymbExpr Char Int
pX (Char -> SymbExpr Char Char
char Char
';')
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char [Int] -> [([Char], [[Int]])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"multipleSepBy and multiple" (SymbExpr Char Int -> SymbExpr Char [Int]
forall t a. (Show t, Ord t) => BNF t a -> BNF t [a]
multiple SymbExpr Char Int
pX)
      -- why not ("", [[0]]) ??
      [([Char]
"", [[]]), ([Char]
"1", [[Int
1],[Int
1]]), ([Char]
"1;1", [[Int
1,Int
0,Int
1],[Int
1,Int
1],[Int
2]])
      ,([Char]
";1;1", [[Int
0,Int
1,Int
0,Int
1],[Int
0,Int
1,Int
1], [Int
0,Int
2], [Int
1,Int
0,Int
1], [Int
1,Int
1], [Int
2]])]
{-
    let pX :: BNF Char Int 
        pX = "X" <::=> 1 <$$ char '1' <||> sum <$$> multipleSepBy pX (char ';')
    test Nothing "manySepBy and multiple" (many pX)
      -- why not ("", [[0]]) ??
      [("", [[]]), ("1", [[1],[1]]), ("1;1", [[1,0,1]])]-}

    let pX :: BNF Char Int -> BNF Char Int
        pX :: SymbExpr Char Int -> SymbExpr Char Int
pX SymbExpr Char Int
p = SymbExpr Char Int -> [Char] -> [Char]
forall t a. (Show t, Ord t) => BNF t a -> [Char] -> [Char]
mkNt SymbExpr Char Int
p [Char]
"X" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<::=> SymbExpr Char Int
p SymbExpr Char Int -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => BNF t a -> BNF t a -> BNF t a
<||> Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) (Int -> Int -> Int) -> SymbExpr Char Int -> BNF Char (Int -> Int)
forall t a b. (Show t, Ord t) => (a -> b) -> BNF t a -> BNF t b
<$$> SymbExpr Char Int -> SymbExpr Char Int
pX (SymbExpr Char Int
p) BNF Char (Int -> Int) -> SymbExpr Char Int -> SymbExpr Char Int
forall t a b.
(Show t, Ord t) =>
BNF t (a -> b) -> BNF t a -> BNF t b
<**> SymbExpr Char Int
p
    Maybe (MemoRef Any)
-> [Char] -> SymbExpr Char Int -> [([Char], [Int])] -> IO ()
forall {t :: * -> *} {a} {t} {s :: * -> * -> *} {a}.
(Foldable t, Show a, Parseable t, IsSymbExpr s, Ord a) =>
Maybe (MemoRef a) -> [Char] -> s t a -> t ([t], [a]) -> IO ()
test Maybe (MemoRef Any)
forall a. Maybe a
Nothing [Char]
"sequence" (SymbExpr Char Int -> SymbExpr Char Int
pX ([Char]
"hash" [Char] -> SymbExpr Char Int -> SymbExpr Char Int
forall t a. (Show t, Ord t) => [Char] -> BNF t a -> BNF t a
<:=> Int
1 Int -> SymbExpr Char Char -> SymbExpr Char Int
forall t b a. (Show t, Ord t) => b -> BNF t a -> BNF t b
<$$ Char -> SymbExpr Char Char
char Char
'1'))
      [([Char]
"1", [Int
1]), ([Char]
"11",[Int
2]),([Char]
"111", [Int
3])
      ,([Char]
"", []), ([Char]
"21",[]), ([Char]
"1(1)1", [])]

    {- tests fails to terminate as the grammar is infinitely big
    let pX :: BNF Char Int -> BNF Char Int
        pX p = mkNt p "X" <::=> p 
                          <||> (+) <$$> pX (within (char '(') p (char ')')) <**> p
    test Nothing "growing sequence (left-recursive)" (pX ("hash" <:=> 1 <$$ char '1'))
      [("1", [1]), ("(1)1",[2]),("((1))(1)1", [3])
      ,("", []), ("11",[]), ("1(1)1", [])]
    -}
    {-let pX :: BNF Char Int -> BNF Char Int
        pX p = mkNt p "X" <::=> p 
                          <||> (+) <$$> p <**> pX (within (char '(') p (char ')'))
    test Nothing "growing sequence (right-recursive)" 
      (pX ("hash" <:=> 1 <$$ char '1'))
      [("1", [1]),("1(1)",[2]),("1(1)((1))", [3]),("1(1)((1))(((1)))",[4])
      ,("", []), ("11",[]), ("1(1)1", []), ("1(1)(1)", [])]-}
 where
    aho_S_5 :: [[Char]]
aho_S_5 = [[Char]
"10101010100",[Char]
"10101011000",[Char]
"10101100100",[Char]
"10101101000",[Char]
"10101110000",[Char]
"10110010100",[Char]
"10110011000",[Char]
"10110100100",[Char]
"10110101000",[Char]
"10110110000",[Char]
"10111000100",[Char]
"10111001000",[Char]
"10111010000",[Char]
"10111100000",[Char]
"11001010100",[Char]
"11001011000",[Char]
"11001100100",[Char]
"11001101000",[Char]
"11001110000",[Char]
"11010010100",[Char]
"11010011000",[Char]
"11010100100",[Char]
"11010101000",[Char]
"11010110000",[Char]
"11011000100",[Char]
"11011001000",[Char]
"11011010000",[Char]
"11011100000",[Char]
"11100010100",[Char]
"11100011000",[Char]
"11100100100",[Char]
"11100101000",[Char]
"11100110000",[Char]
"11101000100",[Char]
"11101001000",[Char]
"11101010000",[Char]
"11101100000",[Char]
"11110000100",[Char]
"11110001000",[Char]
"11110010000",[Char]
"11110100000",[Char]
"11111000000"]

    _EEE_3 :: [[Char]]
_EEE_3 = [[Char]
"00111",[Char]
"01011",[Char]
"01101",[Char]
"01110",[Char]
"10011",[Char]
"10101",[Char]
"10110",[Char]
"11001",[Char]
"11010",[Char]
"111",[Char]
"11100"]