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 :: 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 |