item.mli 2.98 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13
(******************************************************************************)
(*                                                                            *)
(*                                   Menhir                                   *)
(*                                                                            *)
(*                       François Pottier, Inria Paris                        *)
(*              Yann Régis-Gianas, PPS, Université Paris Diderot              *)
(*                                                                            *)
(*  Copyright Inria. All rights reserved. This file is distributed under the  *)
(*  terms of the GNU General Public License version 2, as described in the    *)
(*  file LICENSE.                                                             *)
(*                                                                            *)
(******************************************************************************)

14 15 16 17 18 19 20 21 22 23
open Grammar

(* An LR(0) item encodes a pair of integers, namely the index of the
   production and the index of the bullet in the production's
   right-hand side. *)

type t
val import: Production.index * int -> t
val export: t -> Production.index * int

24 25 26 27 28 29
(* An item can be encoded as an integer. This is used in the table
   back-end only. The decoding function (really a copy of [export])
   is in [TableInterpreter]. *)

val marshal: t -> int

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
(* Comparison. *)

val equal: t -> t -> bool

(* [def item] looks up the production associated with this item in the
   grammar and returns [prod, nt, rhs, pos, length], where [prod] is
   the production's index, [nt] and [rhs] represent the production,
   [pos] is the position of the bullet in the item, and [length] is
   the length of the production's right-hand side. *)

val def: t -> Production.index * Nonterminal.t * Symbol.t array * int * int

(* If [item] is a start item, [startnt item] returns the start
   nonterminal that corresponds to [item]. *)

val startnt: t -> Nonterminal.t

(* Printing. *)

val print: t -> string

(* Classifying items as shift or reduce items. A shift item is one
   where the bullet can still advance. A reduce item is one where the
   bullet has reached the end of the right-hand side. *)

type kind =
  | Shift of Symbol.t * t
  | Reduce of Production.index

val classify: t -> kind

(* Sets of items and maps over items. Hashing these data structures is
   specifically allowed. *)

module Set : GSet.S with type element = t
module Map : GMap.S with type key = t
                     and type Domain.t = Set.t

(* This functor performs precomputation that helps efficiently compute
   the closure of an LR(0) or LR(1) state. The precomputation requires
   time linear in the size of the grammar. The nature of the lookahead
   sets remains abstract. *)

module Closure (L : Lookahead.S) : sig

  (* A state maps items to lookahead information. *)

  type state = L.t Map.t

  (* This takes the closure of a state through all epsilon transitions. *)

  val closure: state -> state

end