(******************************************************************************)
(*                                                                            *)
                                                                       
(*                                                                            *)
                          ,  Paris                        
                   , PPS , Université Paris Diderot              
(*                                                                            *)
     . All rights reserved . This file is distributed under the  
   terms of the GNU General Public License version 2 , as described in the    
(*  file LICENSE.                                                             *)
(*                                                                            *)
(******************************************************************************)

open Grammar

(* -------------------------------------------------------------------------- *)

(* This is the type of derivations. Derivations are forests: see inside. *)

type t

(* This is the type of derivations contexts, or derivations with a
   derivation-shaped hole. *)

type context

(* -------------------------------------------------------------------------- *)

(* Construction. *)

(* [empty] is the forest that consists of a single empty tree. *)

val empty: t

  [ tail pos rhs ] is the forest : ( i ) whose first element is the empty tree , 
    and ( ii ) whose remaining elements are the symbols found at positions 
    greater than or equal to [ pos ] in the array [ rhs ] .
   and (ii) whose remaining elements are the symbols found at positions
   greater than or equal to [pos] in the array [rhs]. *)

val tail: int -> Symbol.t array -> t

  [ build pos rhs forest comment ] is the forest : ( i ) whose first element is 
    the tree that has the non - terminal symbol [ rhs.(pos ) ] at its root and the 
    forest [ forest ] below its root , and ( ii ) whose remaining elements are the 
    symbols found at positions greater than [ pos ] in the array [ rhs ] .
   the tree that has the non-terminal symbol [rhs.(pos)] at its root and the
   forest [forest] below its root, and (ii) whose remaining elements are the
   symbols found at positions greater than [pos] in the array [rhs]. *)

val build: int -> Symbol.t array -> t -> string option -> t

  [ prepend symbol forest ] is the forest : ( i ) whose first element is the 
    symbol [ symbol ] , and ( ii ) whose remaining elements form the forest 
    [ forest ] .
   symbol [symbol], and (ii) whose remaining elements form the forest
   [forest]. *)

val prepend: Symbol.t -> t -> t

(* -------------------------------------------------------------------------- *)

(* Factoring. *)

(* [factor] factors the maximal common derivation context out of a
   nonempty family of derivations. It produces a pair of the context
   and of the residual derivations. *)

val factor: t Item.Map.t -> context * t Item.Map.t

(* -------------------------------------------------------------------------- *)

(* Display. *)

(* [print] prints a derivation. *)

val print: out_channel -> t -> unit

(* [printc] prints a derivation context. *)

val printc: out_channel -> context -> unit


****************************************************************************
                                                                            
                                                                            
                                                                            
  file LICENSE.                                                             
                                                                            
****************************************************************************
 -------------------------------------------------------------------------- 
 This is the type of derivations. Derivations are forests: see inside. 
 This is the type of derivations contexts, or derivations with a
   derivation-shaped hole. 
 -------------------------------------------------------------------------- 
 Construction. 
 [empty] is the forest that consists of a single empty tree. 
 -------------------------------------------------------------------------- 
 Factoring. 
 [factor] factors the maximal common derivation context out of a
   nonempty family of derivations. It produces a pair of the context
   and of the residual derivations. 
 -------------------------------------------------------------------------- 
 Display. 
 [print] prints a derivation. 
 [printc] prints a derivation context. 
                                                                       
                          ,  Paris                        
                   , PPS , Université Paris Diderot              
     . All rights reserved . This file is distributed under the  
   terms of the GNU General Public License version 2 , as described in the    

open Grammar



type t


type context




val empty: t

  [ tail pos rhs ] is the forest : ( i ) whose first element is the empty tree , 
    and ( ii ) whose remaining elements are the symbols found at positions 
    greater than or equal to [ pos ] in the array [ rhs ] .
   and (ii) whose remaining elements are the symbols found at positions
   greater than or equal to [pos] in the array [rhs]. *)

val tail: int -> Symbol.t array -> t

  [ build pos rhs forest comment ] is the forest : ( i ) whose first element is 
    the tree that has the non - terminal symbol [ rhs.(pos ) ] at its root and the 
    forest [ forest ] below its root , and ( ii ) whose remaining elements are the 
    symbols found at positions greater than [ pos ] in the array [ rhs ] .
   the tree that has the non-terminal symbol [rhs.(pos)] at its root and the
   forest [forest] below its root, and (ii) whose remaining elements are the
   symbols found at positions greater than [pos] in the array [rhs]. *)

val build: int -> Symbol.t array -> t -> string option -> t

  [ prepend symbol forest ] is the forest : ( i ) whose first element is the 
    symbol [ symbol ] , and ( ii ) whose remaining elements form the forest 
    [ forest ] .
   symbol [symbol], and (ii) whose remaining elements form the forest
   [forest]. *)

val prepend: Symbol.t -> t -> t




val factor: t Item.Map.t -> context * t Item.Map.t




val print: out_channel -> t -> unit


val printc: out_channel -> context -> unit

