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

--- This module defines the basic data structures for
--- representing graphs and hypergraphs and the corresponding
--- graph parsers.

{-# OPTIONS_CYMAKE -Wno-incomplete-patterns -Wno-overlapping #-}

module Grappa where

--- All nodes are numbered.
type Node = Int

--- A type for the edge labels `t` can be passed as a type parameter.
--- In the simplest case this can be just strings representing their labels.
--- The tentacle numbers correspond to the position of a node in the
--- list of incident nodes.
type Edge t = (t, [Node])

--- A graph is declared as a list of edges each with its incident nodes
type Graph t = [Edge t]

--- The type of a graph parser. It is parameterized over the
--- type `res` of semantic values associated to graphs.
type Grappa t res = Graph t -> (res, Graph t)

--- Access the semantic representation of the result of a graph parser.
getSemRep :: (res, Graph t) -> res
getSemRep (r,_) = r

-- Some primitives for the construction of graph parsers.

--- Given an arbitrary value `v`, `pSucceed` always succeeds
--- returning `v` as a result without any consumption of the input graph `g`.
pSucceed :: res -> Grappa t res
pSucceed v g = (v, g)

--- `eoi` succeeds only if the graph is already completely consumed.
--- In this case, the result `()` is returned
eoi :: Grappa t ()
eoi [] = ((), [])

--- The parser `edge e` succeeds only if the given edge `e` is part of the
--- given input graph `g`.
edge :: Data t => Edge t -> Grappa t ()
edge e g | g =:= (g1 ++ e:g2) = ((), g1 ++ g2)
 where g1, g2 free

--- The choice between two parsers.
(<|>) :: Grappa t res -> Grappa t res -> Grappa t res
(p1 <|> _ ) g = p1 g
(_  <|> p2) g = p2 g

--- The successive application of two parsers where the result
--- is constructed by function application. 
(<*>) :: Grappa t (r1->r2) -> Grappa t r1 -> Grappa t r2
(p <*> q) g = case p g of
               (pv, g1) -> case q g1 of
                             (qv, g2) -> (pv qv, g2)

(<$>) :: (res1->res2) -> Grappa t res1 -> Grappa t res2
f <$> p = pSucceed f <*> p

(<$)  :: res1 -> Grappa t res2 -> Grappa t res1
f <$ p = const f <$> p

(<*)  :: Grappa t res1 -> Grappa t res2 -> Grappa t res1
p <* q = (\x _ -> x) <$> p <*> q

(*>)  :: Grappa t res1 -> Grappa t res2 -> Grappa t res2
p *> q = (\_ x -> x) <$> p <*> q


--- The combinator `chain p (n1,n2)` can be used to identify
--- a non-empty chain of graphs that can be parsed with `p`.
--- This chain has to be anchored between the nodes `n1` and `n2`.
chain :: ((Node,Node) -> Grappa t a) -> (Node,Node) -> Grappa t [a]
chain p (n1,n2) = (:[]) <$> p (n1,n2)
chain p (n1,n2) = (:)   <$> p (n1,n) <*> chain p (n,n2)
 where n free