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 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136
|
(**************************************************************************)
(* *)
(* Menhir *)
(* *)
(* Franois Pottier and Yann Rgis-Gianas, INRIA Rocquencourt *)
(* *)
(* Copyright 2005 Institut National de Recherche en Informatique et *)
(* en Automatique. All rights reserved. This file is distributed *)
(* under the terms of the Q Public License version 1.0, with the *)
(* change described in file LICENSE. *)
(* *)
(**************************************************************************)
(* This module discovers and publishes information about the
automaton.
It determines the shape of the stack when a state is about to be
entered, when a production is about to be reduced, and when a goto
transition is about to be taken.
It also determines which states should be represented (that is,
need to physically exist on the stack at runtime) and which symbols
need to keep track of (start or end) positions.
It also determines which automaton states could potentially perform
error recovery, and which states could have to deal with an [error]
token. *)
open Grammar
(* ------------------------------------------------------------------------- *)
(* A representation of stack shapes. *)
(* A word is a representation of a stack or stack suffix. *)
type word
(* [fold] folds over a word. At each cell, [f] is applied to the
accumulator, to a Boolean flag that tells whether the cell holds a
state, and to the symbol associated with the cell. The stack is
visited from bottom to top. *)
val fold: ('a -> bool -> Symbol.t -> 'a) -> 'a -> word -> 'a
(* [fold_top f accu s] is analogous to [fold], but only folds over the
top stack cell, if there is one, so that [f] is either not invoked
at all or invoked just once. *)
val fold_top: (bool -> Symbol.t -> 'a) -> 'a -> word -> 'a
(* ------------------------------------------------------------------------- *)
(* Information about the stack. *)
(* [stack s] is the structure of the stack at state [s]. *)
val stack: Lr1.node -> word
(* [prodstack prod] is the structure of the stack when production
[prod] is about to be reduced. This function should not be called
if production [prod] is never reduced. *)
val prodstack: Production.index -> word
(* [gotostack nt] is the structure of the stack when a shift
transition over nonterminal [nt] is about to be taken. It
consists of just one cell. *)
val gotostack: Nonterminal.t -> word
(* [rewind s] explains how to rewind the stack when dealing with an
error in state [s]. It produces an instruction to either die
(because no state on the stack can handle errors) or pop a suffix
of the stack. In the latter case, one reaches a state that is
either represented (its identity is physically stored in the
bottommost cell that is popped) or unrepresented (its identity is
statically known). *)
type instruction =
| Die
| DownTo of word * state
and state =
| Represented
| UnRepresented of Lr1.node
val rewind: Lr1.node -> instruction
(* ------------------------------------------------------------------------- *)
(* Information about which states and positions need to physically
exist on the stack. *)
(* [represented s] tells whether state [s] must have an explicit
representation, that is, whether it is pushed onto the stack. *)
val represented: Lr1.node -> bool
(* [startp symbol] and [endp symbol] tell whether start or end
positions must be recorded for symbol [symbol]. *)
val startp: Symbol.t -> bool
val endp: Symbol.t -> bool
(* ------------------------------------------------------------------------- *)
(* Information about error handling. *)
(* [recoverer s] tells whether state [s] can potentially do error
recovery. *)
val recoverer: Lr1.node -> bool
(* [errorpeeker s] tells whether state [s] can potentially peek at an
error. This is the case if, in state [s], [env.shifted] may be -1,
that is, if an error token may be on the stream. *)
val errorpeeker: Lr1.node -> bool
(* ------------------------------------------------------------------------- *)
(* Information about which productions are reduced and where. *)
(* [ever_reduced prod] tells whether production [prod] is ever reduced. *)
val ever_reduced: Production.index -> bool
(* [fold_reduced prod] folds over all states that can reduce
production [prod]. *)
val fold_reduced: (Lr1.node -> 'a -> 'a) -> Production.index -> 'a -> 'a
(* ------------------------------------------------------------------------- *)
(* Miscellaneous. *)
(* [universal symbol] tells whether every represented state has an
outgoing transition along [symbol]. *)
val universal: Symbol.t -> bool
|