From e80e269c313952b4d427fa6a5a9729ea15e43f39 Mon Sep 17 00:00:00 2001 From: Lucca Hirschi Date: Mon, 2 Jul 2012 15:44:26 +0200 Subject: [PATCH] Print labels (=QName -> qname.ml? ) + structure of the translation function in Compil --- run_tests | 2 ++ src/asta.ml | 21 +++++++++++++++++++-- src/asta.mli | 39 +++++++++++++++++++++++++++++++++------ src/compil.ml | 35 ++++++++++++++++++++++++++++++++++- src/compil.mli | 3 ++- src/qNameSet.ml | 18 ++++++++++++++++++ src/qNameSet.mli | 3 +++ src/test.ml | 2 +- 8 files changed, 112 insertions(+), 11 deletions(-) diff --git a/run_tests b/run_tests index 867fbe2..d6fba68 100755 --- a/run_tests +++ b/run_tests @@ -1,3 +1,5 @@ ./test.native ./tests/docs/tiny.xml '/child::site/child::regions' +echo "\n" ./test.native ./tests/docs/tiny.xml -f ./tests/queries/Treebank.xml.queries +echo "\n" ./test.native ./tests/docs/tiny.xml '/descendant::listitem[not(descendant::keyword/child::emph)]/descendant::parlist' diff --git a/src/asta.ml b/src/asta.ml index 670bb35..8b9682c 100644 --- a/src/asta.ml +++ b/src/asta.ml @@ -35,7 +35,7 @@ struct let print fmt (st,la,f) = Format.fprintf fmt "(%a,%s,%a)" State.print st - "TODO la" + (QNameSet.to_string la) Formula.print f end @@ -44,6 +44,8 @@ struct include Set.Make(Transition) end +type transition = Transition.t + type t = { mutable reco : StateSet.t; mutable selec : StateSet.t; @@ -71,7 +73,7 @@ let transitions asta st = | (a,s,l) :: tl -> (s,l) :: (remove_states tl) in remove_states (SetT.elements (SetT.filter filter asta.trans)) -let dummy = { +let empty = { reco = StateSet.empty; selec = StateSet.empty; bottom = StateSet.empty; @@ -79,6 +81,21 @@ let dummy = { trans = SetT.empty; } +let any_label = QNameSet.complement (QNameSet.empty) + +let new_state () = State.make() + +let add_tr ast tr = ast.trans <- (SetT.add tr (ast.trans)) + +let add_reco ast st = ast.reco <- (StateSet.add st (ast.reco)) + +let add_selec ast st = ast.selec <- (StateSet.add st (ast.selec)) + +let add_bot ast st = ast.bottom <- (StateSet.add st (ast.bottom)) + +let add_top ast st = ast.top <- (StateSet.add st (ast.top)) + +let top_states ast = StateSet.elements ast.top let print fmt asta = let pp = Format.fprintf fmt in diff --git a/src/asta.mli b/src/asta.mli index dff376f..a0d589f 100644 --- a/src/asta.mli +++ b/src/asta.mli @@ -2,8 +2,8 @@ (* *) (* TAToo *) (* *) -(* Lucca Hirschi, ? *) -(* ? *) +(* Lucca Hirschi, ? *) +(* ? *) (* *) (* Copyright 2010-2012 Université Paris-Sud and Centre National de la *) (* Recherche Scientifique. All rights reserved. This file is *) @@ -16,15 +16,18 @@ (** Implementation of alternating selecting tree automata (ASTA) *) -type state +type state = State.t (** The type of states *) -type label +type label = QNameSet.t (** The type of labels of the transitions *) -type formula +type formula = Formula.t (** The type of transition formulae *) +type transition = (state*label*formula) +(** The type of transitions *) + type t (** The type of ASTAs *) @@ -34,9 +37,33 @@ val transition : t -> state -> label -> formula val transitions : t -> state -> (label*formula) list (** Give the list of labels and formulae from transitions for a given state *) -val dummy : t +val empty : t (** The empty automaton *) +val any_label : label +(** Set of all labels which can occur in a tree *) + +val new_state : unit -> state +(** Give a new state (different from all others states) *) + +val add_tr : t -> transition -> unit +(** Add a transition to an asta *) + +val add_reco : t -> state -> unit +(** Add a state to the recognizing states of an asta *) + +val add_selec : t -> state -> unit +(** Add a state to the recognizing states of an asta *) + +val add_bot : t -> state -> unit +(** Add a state to the bottom states of an asta *) + +val add_top : t -> state -> unit +(** Add a state to the top states of an asta *) + +val top_states : t -> state list +(** Give the list of top states of an ASTA *) + val print : Format.formatter -> t -> unit (** Describe the automaton as text *) diff --git a/src/compil.ml b/src/compil.ml index 30440f3..610360b 100644 --- a/src/compil.ml +++ b/src/compil.ml @@ -13,4 +13,37 @@ (* *) (***********************************************************************) -let trad qu = Asta.dummy +open XPath.Ast +open Formula.Infix + +exception Not_core_XPath of path +(** Raised whenever the XPath query contains not implemented structures *) + +let trans query = + let asta = Asta.empty in + let rec trans = function + | [s] -> trans_last s + | s :: tl -> trans_step s; trans tl + | [] -> () + + and trans_init () = (* add THE top state *) + let top_st = Asta.new_state () in + let or_top = + List.fold_left (fun acc x -> (`Left *+ x +| acc)) + Formula.true_ (Asta.top_states asta) + in + Asta.add_tr asta (top_st, Asta.any_label, or_top) + + and trans_last (ax,test,pred) = (* a selecting state is needed *) + () + + and trans_step (ax,test,pred) = + () + + and trans_pr p = () + + in + match query with + | Absolute steps -> trans_init(); trans steps; asta + | AbsoluteDoS steps as x -> raise (Not_core_XPath x) + | Relative steps as x -> raise (Not_core_XPath x) diff --git a/src/compil.mli b/src/compil.mli index e21975d..2552957 100644 --- a/src/compil.mli +++ b/src/compil.mli @@ -15,5 +15,6 @@ (** Implementation of compilation from XPath queries into ASTA *) -val trad : XPath.Ast.path -> Asta.t + +val trans : XPath.Ast.path -> Asta.t (** Compilation function *) diff --git a/src/qNameSet.ml b/src/qNameSet.ml index 4035957..8746b09 100644 --- a/src/qNameSet.ml +++ b/src/qNameSet.ml @@ -16,3 +16,21 @@ include FiniteCofinite.Make(Ptset.Make(QName)) module Weak = FiniteCofinite.Weak(Ptset.Weak(QName)) + +(* BEGIN : Lucca Hirschi *) +let to_string set = + String.concat " " + [ + (match (kind set) with + | `Finite -> "F(" + | `Cofinite -> "Cof(") + ; + if is_empty (complement set) then + "ø" + else + ( String.concat " " + (List.map (fun name -> QName.to_string name) (elements (complement set)))) + ; + ")" + ] +(* END : Lucca Hirschi *) diff --git a/src/qNameSet.mli b/src/qNameSet.mli index 71d1478..810fa29 100644 --- a/src/qNameSet.mli +++ b/src/qNameSet.mli @@ -20,3 +20,6 @@ include FiniteCofinite.S with type elt = QName.t module Weak : FiniteCofinite.S with type elt = QName.t + +val to_string : t -> string +(** Lucca Hirschi: print *) diff --git a/src/test.ml b/src/test.ml index 8b69fd8..334e572 100644 --- a/src/test.ml +++ b/src/test.ml @@ -37,7 +37,7 @@ let query = open Format -let asta = Compil.trad query +let asta = Compil.trans query let () = fprintf err_formatter "Query: %a\n%!" XPath.Ast.print query; -- 2.17.1