1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
----------------------------------------------------------------------
-- |
-- Maintainer : PL
-- Stability : (stable)
-- Portability : (portable)
--
-- > CVS $Date: 2005/04/11 13:52:51 $
-- > CVS $Author: peb $
-- > CVS $Revision: 1.1 $
--
-- Implementation of /incremental/ deductive parsing,
-- i.e. parsing one word at the time.
-----------------------------------------------------------------------------
module GF.NewParsing.IncrementalChart
(-- * Type definitions
IncrementalChart,
-- * Functions
chartLookup,
buildChart,
chartList
) where
import Array
import GF.Data.SortedList
import GF.Data.Assoc
----------------------------------------------------------------------
-- main functions
chartLookup :: (Ord item, Ord key) =>
IncrementalChart item key
-> Int -> key -> SList item
buildChart :: (Ord item, Ord key) =>
(item -> key) -- ^ key lookup function
-> (Int -> item -> SList item) -- ^ all inference rules for position k, collected
-> (Int -> SList item) -- ^ all axioms for position k, collected
-> (Int, Int) -- ^ input bounds
-> IncrementalChart item key
chartList :: (Ord item, Ord key) =>
IncrementalChart item key -- ^ the final chart
-> (Int -> item -> edge) -- ^ function building an edge from
-- the position and the item
-> [edge]
type IncrementalChart item key = Array Int (Assoc key (SList item))
----------
chartLookup chart k key = (chart ! k) ? key
buildChart keyof rules axioms bounds = finalChartArray
where buildState k = limit (rules k) $ axioms k
finalChartList = map buildState [fst bounds .. snd bounds]
finalChartArray = listArray bounds $ map stateAssoc finalChartList
stateAssoc state = accumAssoc id [ (keyof item, item) | item <- state ]
chartList chart combine = [ combine k item |
(k, state) <- assocs chart,
item <- concatMap snd $ aAssocs state ]
|
