-
Notifications
You must be signed in to change notification settings - Fork 0
/
Cyk.hs
87 lines (67 loc) · 2.83 KB
/
Cyk.hs
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
module Cyk where
import Data.List
import ChomskyTest
import Types
import Chomsky
--for testing
toWord :: [Char] -> WorD
toWord [] = []
toWord (x:xs) = [x] : toWord xs
breakdown :: Rule -> [Rule']
breakdown rule@(lhs,rhs) = [ (lhs, subrule) | subrule <- rhs ]
breakdownRules :: Grammar -> [Rule']
breakdownRules grammar = concatMap (breakdown) rules
where
(_, _, _, _, rules) = grammar
--the the input lists should be sorted
merge :: (a -> a -> Bool) -> [a] -> [a] -> [a]
merge _ [] list2 = list2
merge _ list1 [] = list1
merge rel list1@(x:xs) list2@(y:ys)
| rel x y = x : merge rel xs list2
| otherwise = y : merge rel list1 ys
mergesort :: (a -> a -> Bool) -> [a] -> [a]
mergesort _ [x] = [x]
mergesort rel xs = merge rel (mergesort rel firstHalf) (mergesort rel secondHalf)
where
half = length xs `div` 2
firstHalf = take half xs
secondHalf = drop half xs
descartes :: [[a]] -> [[a]]
descartes [] = [[]]
descartes (x:xs) = [ a : dx | a <- x, dx <- descartes xs]
sliceWord :: [a] -> [([a], [a])]
sliceWord word@(x:xs) = slcwrdHelper [x] xs
where
slcwrdHelper :: [a] -> [a] -> [([a], [a])]
slcwrdHelper xs [y] = [(xs, [y])]
slcwrdHelper xs other@(y:ys) = (xs, other) : slcwrdHelper (xs ++ [y]) ys
--slcwrdHelper [x] ys = [([x], ys)]
--slcwrdHelper xs ys = (xs, ys) : slcwrdHelper (init xs) (last xs : ys)
--searchForWord a b == c // a -> rhs to search for; b -> rules to filter (sorted by rhs); c -> lhs-s of each rule that has passed the query
searchForWord :: WorD -> [Rule'] -> [Symbol]
searchForWord _ [] = []
searchForWord word rules@(r:rs)
| word < rhs = []
| word > rhs = searchForWord word rs
| otherwise = lhs : searchForWord word rs
where (lhs, rhs) = r
cyk :: [Rule'] -> WorD -> [Symbol]
cyk rules [t] = searchForWord [t] rules
cyk rules word = nub $ concatMap (flip (searchForWord) rules) descartesWords
where
descartesWords = concat [ descartes [cyk rules pre, cyk rules suf] | w@(pre,suf) <- sliceWord word]
isInLanguage :: WorD -> Grammar -> Bool
isInLanguage word grammar = start `elem` (cyk rules' word)
where
rules' = mergesort (\(_,a) (_,b) -> a < b) $ breakdownRules $ cgrammar
(start, eps, nonterminals, terminals, rules) = cgrammar
cgrammar
| not (isChomsky grammar) = chomsky grammar
| otherwise = grammar
sortedbrules1 = mergesort (\(_,a) (_,b) -> a < b) $ breakdownRules $ chomsky grammar1
sortedbrules2 = mergesort (\(_,a) (_,b) -> a < b) $ breakdownRules $ chomsky grammar2
sortedbrules3 = mergesort (\(_,a) (_,b) -> a < b) $ breakdownRules $ chomsky grammar3
sortedbrules4 = mergesort (\(_,a) (_,b) -> a < b) $ breakdownRules $ grammar4
sortedbrules5 = mergesort (\(_,a) (_,b) -> a < b) $ breakdownRules $ grammar5
sortedbrules6 = mergesort (\(_,a) (_,b) -> a < b) $ breakdownRules $ grammar6