diff options
Diffstat (limited to 'src/GF/Parsing/MCFG/Naive.hs')
| -rw-r--r-- | src/GF/Parsing/MCFG/Naive.hs | 110 |
1 files changed, 75 insertions, 35 deletions
diff --git a/src/GF/Parsing/MCFG/Naive.hs b/src/GF/Parsing/MCFG/Naive.hs index 4b994e726..932261d2b 100644 --- a/src/GF/Parsing/MCFG/Naive.hs +++ b/src/GF/Parsing/MCFG/Naive.hs @@ -1,6 +1,7 @@ -module GF.Parsing.MCFG.Naive (parse) where +module GF.Parsing.MCFG.Naive (parse, parseR) where +import Control.Monad (guard) -- GF modules import GF.Data.GeneralDeduction @@ -13,21 +14,72 @@ import GF.Data.SortedList import GF.Data.Assoc import GF.System.Tracing +import GF.Infra.Print + ---------------------------------------------------------------------- -- * parsing --- | Builds a chart from the initial agenda, given by prediction, and --- the inference rules +-- | Builds a chart from the initial agenda, given by prediction, and the inference rules parse :: (Ord t, Ord n, Ord c, Ord l) => MCFParser c n l t -parse mcfg starts toks +parse pinfo starts toks = [ Abs (cat, makeRangeRec lins) (zip rhs rrecs) fun | Active (Abs cat _Nil fun, rhs) lins rrecs <- chartLookup chart Final ] - where chart = process mcfg toks + where chart = process pinfo toks -process :: (Ord t, Ord n, Ord c, Ord l) => MCFGrammar c n l t -> Input t -> NChart c n l -process mcfg toks +-- | Builds a chart from the initial agenda, given by prediction, and the inference rules +-- parseR :: (Ord t, Ord n, Ord c, Ord l) => MCFParser c n l t +parseR pinfo starts + = [ Abs (cat, makeRangeRec lins) (zip rhs rrecs) fun | + Active (Abs cat _Nil fun, rhs) lins rrecs <- chartLookup chart Final ] + where chart = processR pinfo + +process :: (Ord t, Ord n, Ord c, Ord l) => MCFPInfo c n l t -> Input t -> NChart c n l +process pinfo toks = tracePrt "MCFG.Naive - chart size" prtSizes $ - buildChart keyof [convert, combine] (predict toks mcfg) + buildChart keyof [convert, combine] (predict pinfo toks) + +processR :: (Ord n, Ord c, Ord l) => MCFPInfo c n l Range -> NChart c n l +processR pinfo + = tracePrt "MCFG.Naive Range - chart size" prtSizes $ + buildChart keyof [convert, combine] (predictR pinfo) + + +---------------------------------------------------------------------- +-- * inference rules + +-- Creates an Active Item of every Rule in the Grammar to give the initial Agenda +predict :: (Ord l, Ord t) => MCFPInfo c n l t -> Input t -> [Item c n l] +predict pinfo toks = tracePrt "MCFG.Naive - predicted rules" (prt . length) $ + do Rule abs (Cnc _ _ lins) <- rulesMatchingInput pinfo toks + lins' <- rangeRestRec toks lins + return $ Active (abs, []) lins' [] + +-- Creates an Active Item of every Rule in the Grammar to give the initial Agenda +predictR :: (Ord l) => MCFPInfo c n l Range -> [Item c n l] +predictR pinfo = tracePrt "MCFG.Naive Range - predicted rules" (prt . length) $ + do Rule abs (Cnc _ _ lins) <- allRules pinfo + return $ Active (abs, []) lins [] + +-- | Creates an Active Item every time it is possible to combine +-- an Active Item from the agenda with a Passive Item from the Chart +combine :: (Ord n, Ord c, Ord l) => NChart c n l -> Item c n l -> [Item c n l] +combine chart item@(Active (Abs _ (c:_) _, _) _ _) = + do Passive _c rrec <- chartLookup chart (Pass c) + combine2 chart rrec item +combine chart (Passive c rrec) = + do item <- chartLookup chart (Act c) + combine2 chart rrec item +combine _ _ = [] + +combine2 chart rrec (Active (Abs nt (c:find) f, found) lins rrecs) = + do lins' <- substArgRec (length found) rrec lins + return $ Active (Abs nt find f, found ++ [c]) lins' (rrecs ++ [rrec]) + +-- | Active Items with nothing to find are converted to Passive Items +convert :: (Ord n, Ord c, Ord l) => NChart c n l -> Item c n l -> [Item c n l] +convert _ (Active (Abs cat [] fun, _) lins _) = [Passive cat (makeRangeRec lins)] +convert _ _ = [] + ---------------------------------------------------------------------- -- * type definitions @@ -57,32 +109,20 @@ prtSizes chart = "final=" ++ show (length (chartLookup chart Final)) ++ ", active=" ++ show (sum [length (chartLookup chart k) | k@(Act _) <- chartKeys chart ]) ----------------------------------------------------------------------- --- * inference rules - --- Creates an Active Item of every Rule in the Grammar to give the initial Agenda -predict :: Ord t => Input t -> MCFGrammar c n l t -> [Item c n l] -predict toks mcfg = [ Active (abs, []) lins' [] | - Rule abs (Cnc _ _ lins) <- mcfg, - lins' <- rangeRestRec toks lins ] - --- | Creates an Active Item every time it is possible to combine --- an Active Item from the agenda with a Passive Item from the Chart -combine :: (Ord n, Ord c, Ord l) => NChart c n l -> Item c n l -> [Item c n l] -combine chart (Active (Abs nt (c:find) f, found) lins rrecs) = - do Passive _ rrec <- chartLookup chart (Pass c) - lins' <- concLinRec $ substArgRec (length found) rrec lins - return $ Active (Abs nt find f, found ++ [c]) lins' (rrecs ++ [rrec]) -combine chart (Passive c rrec) = - do Active (Abs nt (c:find) f, found) lins rrecs <- chartLookup chart (Act c) - lins' <- concLinRec $ substArgRec (length found) rrec lins - return $ Active (Abs nt find f, found ++ [c]) lins' (rrecs ++ [rrec]) -combine _ _ = [] - --- | Active Items with nothing to find are converted to Passive Items -convert :: (Ord n, Ord c, Ord l) => NChart c n l -> Item c n l -> [Item c n l] -convert _ (Active (Abs cat [] _, _) lins _) = [Passive cat rrec] - where rrec = makeRangeRec lins -convert _ _ = [] +prtChart chart = concat [ "\n*** KEY: " ++ prt k ++ + prtBefore "\n " (chartLookup chart k) | + k <- chartKeys chart ] + +instance (Print c, Print n, Print l) => Print (Item c n l) where + prt (Active (abs, cs) lrec rrecs) = "? " ++ prt abs ++ " . " ++ prtSep " " cs ++ ";\n\t" ++ + "{" ++ prtSep " " lrec ++ "}" ++ + ( if null rrecs then ";" else ";\n\t" ++ + "{" ++ prtSep "} {" (map (prtSep " ") rrecs) ++ "}" ) + prt (Passive c rrec) = "- " ++ prt c ++ "; {" ++ prtSep " " rrec ++ "}" + +instance Print c => Print (NKey c) where + prt (Act c) = "Active " ++ prt c + prt (Pass c) = "Passive " ++ prt c + prt (Final) = "Final" |