bundles/menhirLib/menhir-20120123/src/invariant.mli

   1 (**************************************************************************)
   2 (*                                                                        *)
   3 (*  Menhir                                                                *)
   4 (*                                                                        *)
   5 (*  François Pottier, INRIA Rocquencourt                                  *)
   6 (*  Yann Régis-Gianas, PPS, Université Paris Diderot                      *)
   7 (*                                                                        *)
   8 (*  Copyright 2005-2008 Institut National de Recherche en Informatique    *)
   9 (*  et en Automatique. All rights reserved. This file is distributed      *)
  10 (*  under the terms of the Q Public License version 1.0, with the change  *)
  11 (*  described in file LICENSE.                                            *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 (* This module discovers and publishes information about the
  16    automaton.
  17
  18    It determines the shape of the stack when a state is about to be
  19    entered, when a production is about to be reduced, and when a goto
  20    transition is about to be taken.
  21
  22    It also determines which states should be represented (that is,
  23    need to physically exist on the stack at runtime) and which symbols
  24    need to keep track of (start or end) positions.
  25
  26    It also determines which automaton states could potentially perform
  27    error recovery, and which states could have to deal with an [error]
  28    token. *)
  29
  30 open Grammar
  31
  32 (* ------------------------------------------------------------------------- *)
  33 (* A representation of stack shapes. *)
  34
  35 (* A word is a representation of a stack or stack suffix. *)
  36
  37 type word
  38
  39 (* [fold] folds over a word. At each cell, [f] is applied to the
  40    accumulator, to a Boolean flag that tells whether the cell holds a
  41    state, to the set of possible states of the cell, and to the symbol
  42    associated with the cell. The stack is visited from bottom to top. *)
  43
  44 val fold: ('a -> bool -> Symbol.t -> Lr1.NodeSet.t -> 'a) -> 'a -> word -> 'a
  45
  46 (* [fold_top f accu s] is analogous to [fold], but only folds over the
  47    top stack cell, if there is one, so that [f] is either not invoked
  48    at all or invoked just once. *)
  49
  50 val fold_top: (bool -> Symbol.t -> 'a) -> 'a -> word -> 'a
  51
  52 (* ------------------------------------------------------------------------- *)
  53 (* Information about the stack. *)
  54
  55 (* [stack s] is the structure of the stack at state [s]. *)
  56
  57 val stack: Lr1.node -> word
  58
  59 (* [prodstack prod] is the structure of the stack when production
  60    [prod] is about to be reduced. This function should not be called
  61    if production [prod] is never reduced. *)
  62
  63 val prodstack: Production.index -> word
  64
  65 (* [gotostack nt] is the structure of the stack when a shift
  66    transition over nonterminal [nt] is about to be taken. It
  67    consists of just one cell. *)
  68
  69 val gotostack: Nonterminal.t -> word
  70
  71 (* [rewind s] explains how to rewind the stack when dealing with an
  72    error in state [s]. It produces an instruction to either die
  73    (because no state on the stack can handle errors) or pop a suffix
  74    of the stack. In the latter case, one reaches a state that is
  75    either represented (its identity is physically stored in the
  76    bottommost cell that is popped) or unrepresented (its identity is
  77    statically known). *)
  78
  79 type instruction =
  80   | Die
  81   | DownTo of word * state
  82
  83 and state =
  84   | Represented
  85   | UnRepresented of Lr1.node
  86
  87 val rewind: Lr1.node -> instruction
  88
  89 (* ------------------------------------------------------------------------- *)
  90 (* Information about which states and positions need to physically
  91    exist on the stack. *)
  92
  93 (* [represented s] tells whether state [s] must have an explicit
  94    representation, that is, whether it is pushed onto the stack. *)
  95
  96 val represented: Lr1.node -> bool
  97
  98 (* [startp symbol] and [endp symbol] tell whether start or end
  99    positions must be recorded for symbol [symbol]. *)
 100
 101 val startp: Symbol.t -> bool
 102 val endp: Symbol.t -> bool
 103
 104 (* ------------------------------------------------------------------------- *)
 105 (* Information about error handling. *)
 106
 107 (* [recoverer s] tells whether state [s] can potentially do error
 108    recovery. *)
 109
 110 val recoverer: Lr1.node -> bool
 111
 112 (* [errorpeeker s] tells whether state [s] can potentially peek at an
 113    error. This is the case if, in state [s], [env.shifted] may be -1,
 114    that is, if an error token may be on the stream. *)
 115
 116 val errorpeeker: Lr1.node -> bool
 117
 118 (* ------------------------------------------------------------------------- *)
 119 (* Information about which productions are reduced and where. *)
 120
 121 (* [ever_reduced prod] tells whether production [prod] is ever reduced. *)
 122
 123 val ever_reduced: Production.index -> bool
 124
 125 (* [fold_reduced prod] folds over all states that can reduce
 126    production [prod]. *)
 127
 128 val fold_reduced: (Lr1.node -> 'a -> 'a) -> Production.index -> 'a -> 'a
 129
 130 (* ------------------------------------------------------------------------- *)
 131 (* Information about default reductions. *)
 132
 133 (* [has_default_reduction s] tells whether state [s] has a default reduction,
 134    and, if so, upon which set of tokens. *)
 135 val has_default_reduction : Lr1.node -> (Production.index * TerminalSet.t) option
 136
 137 (* ------------------------------------------------------------------------- *)
 138 (* Miscellaneous. *)
 139
 140 (* [universal symbol] tells whether every represented state has an
 141    outgoing transition along [symbol]. *)
 142
 143 val universal: Symbol.t -> bool
 144