-- Exercise on Context Free Grammars and LL(1) grammars
-- Give a proper definition to all functions left undefined

import Data.List (partition,nub)

-- v is the type of non-terminals
-- For terminals we use characters (but $ is reserved for end of word)

data Symbol v = Terminal Char | NonTerminal v

data Production v = Production v [Symbol v]

prodNT :: Production v -> v
prodNT (Production v _) = v

prodSF :: Production v -> [Symbol v]
prodSF (Production _ sf) = sf

data CFG v = CFG v [Production v]

start :: CFG v -> v
start (CFG v _) = v

productions :: CFG v -> [Production v]
productions (CFG _ ps) = ps

nonterminals :: Eq v => CFG v -> [v]
nonterminals cfg = nub (map prodNT (productions cfg))

-- All the sentential forms derivable from a non-terminal
derivates :: Eq v => CFG v -> v -> [[Symbol v]]
derivates cfg v = map prodSF $ filter (\p -> prodNT p == v) (productions cfg)

{- Example : S -> AB | C
             A -> aA | epsilon
             B -> Bb | c
             C -> Cc | b
-}

data NT1 = Snt | Ant | Bnt | Cnt deriving (Eq,Show)

cfg1 :: CFG NT1
cfg1 = CFG Snt [Production Snt [NonTerminal Ant, NonTerminal Bnt],
                Production Snt [NonTerminal Cnt],
                Production Ant [Terminal 'a', NonTerminal Ant],
                Production Ant [],
                Production Bnt [NonTerminal Bnt, Terminal 'b'],
                Production Bnt [Terminal 'c'],
                Production Cnt [NonTerminal Cnt, Terminal 'c'],
                Production Cnt [Terminal 'b']]

-- Inefficient generation of all words (leftmost derivation)

-- Applying all possible productions to the leftmost symbol
leftProd :: Eq v => CFG v -> [Symbol v] -> [[Symbol v]]
leftProd = undefined

-- If a sentential form has only terminals, get the string
--  Otherwise Nothing
getWord :: [Symbol v] -> Maybe String
getWord = undefined

-- Partition a list of sentential forms into those that are
-- just words and those that still contain some non-terminal
partSF :: [[Symbol v]] -> ([String],[[Symbol v]])
partSF = undefined

-- All the words that can be generated from a sentential form
allWordsSF :: Eq v => CFG v -> [[Symbol v]] -> [String]
allWordsSF = undefined

-- All the words generated by a grammar
allWords :: Eq v => CFG v -> [String]
allWords = undefined


-- Construction of the set of nullable non-terminals

-- One-step: nullable with respect to a set of already known nullables
nullRel :: Eq v => CFG v -> [v] -> v -> Bool
nullRel = undefined

-- nvs = already known nullables, vs = non-terminals to check
nulls :: Eq v => CFG v -> [v] -> [v] -> [v]
nulls = undefined

nullables :: Eq v => CFG v -> [v]
nullables = undefined


-- All the possible first characters of a word generated by a non-terminal
firstsym :: Eq v => CFG v -> v -> [Char]
firstsym = undefined

-- All the characters that can come after a non-terminal
follow :: Eq v => CFG v -> v -> [Char]
follow cfg v = undefined

-- All the first characters that can be generated by a production
lookahead :: Eq v => CFG v -> Production v -> [Char]
lookahead = undefined

-- Test if a grammar is LL(1)
llone :: Eq v => CFG v -> Bool
llone = undefined

-- Assume the grammar is LL(1)

-- Parse an initial part of a string from a non-terminal
--  and return the remaining of the string
parseNT :: Eq v => CFG v -> v -> String -> Maybe String
parseNT = undefined

-- Determine whether a string is in the language of the grammar
parse :: Eq v => CFG v -> String -> Bool
parse = undefined