IncrementalEngine.ml 6.51 KB
Newer Older
1 2 3 4 5 6 7 8 9 10
(* This signature describes the incremental LR engine. *)

(* In this mode, the user controls the lexer, and the parser suspends
   itself when it needs to read a new token. *)

module type INCREMENTAL_ENGINE = sig

  type token

  (* The type ['a result] represents an intermediate or final result of the
11 12 13 14 15 16 17 18 19 20 21
     parser. An intermediate result is a suspension: it records the parser's
     current state, and allows parsing to be resumed. The parameter ['a] is
     the type of the semantic value that will eventually be produced if the
     parser succeeds. *)

  (* [Accepted] and [Rejected] are final results. [Accepted] carries a
     semantic value. *)

  (* [InputNeeded] is an intermediate result. It means that the parser wishes
     to read one token before continuing. *)

22 23 24 25 26 27 28 29 30 31
  (* [AboutToReduce] is an intermediate result. It means that the parser is
     about to perform a reduction step. It does not need more input at this
     point. The parser suspends itself at this point only in order to give the
     user an opportunity to observe this reduction step. *)

  (* [HandlingError] is an intermediate result. It means that the parser has
     detected an error and is currently handling it, in several steps. It does
     not need more input at this point. The parser suspends itself at this
     point only in order to give the user an opportunity to handle this error
     in a different manner, if desired. *)
32

33
  type env
34

35 36
  type production

37 38 39 40
  type 'a result = private
    | InputNeeded of env
    | AboutToReduce of env * production
    | HandlingError of env
41 42 43 44
    | Accepted of 'a
    | Rejected

  (* [offer] allows the user to resume the parser after it has suspended
45 46 47
     itself with a result of the form [InputNeeded env]. [offer] expects the
     old result as well as a new token and produces a new result. It does not
     raise any exception. *)
48 49

  val offer:
50
    'a result ->
51 52 53
    token * Lexing.position * Lexing.position ->
    'a result

54 55 56 57
  (* [resume] allows the user to resume the parser after it has suspended
     itself with a result of the form [AboutToReduce (env, prod)] or
     [HandlingError env]. [resume] expects the old result and produces a new
     result. It does not raise any exception. *)
58

59 60
  val resume:
    'a result ->
61 62
    'a result

63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
  (* The abstract type ['a lr1state] describes the non-initial states of the
     LR(1) automaton. The index ['a] represents the type of the semantic value
     associated with this state's incoming symbol. *)

  type 'a lr1state

  (* An element is a pair of a non-initial state [s] and a semantic value [v]
     associated with the incoming symbol of this state. The idea is, the value
     [v] was pushed onto the stack just before the state [s] was entered. Thus,
     for some type ['a], the type [s] has type ['a lr1state] and the value [v]
     has type ['a]. In other words, the type [element] is an existential type. *)

  type element =
    | Element: 'a lr1state * 'a * Lexing.position * Lexing.position -> element

  (* A stream is a list whose elements are produced on demand. *)

  type 'a stream =
      'a head Lazy.t

  and 'a head =
    | Nil
    | Cons of 'a * 'a stream

87 88 89 90 91 92 93 94
  (* The length of a stream. *)

  val length: 'a stream -> int

  (* Folding over a stream. *)

  val foldr: ('a -> 'b -> 'b) -> 'a stream -> 'b -> 'b

POTTIER Francois's avatar
POTTIER Francois committed
95 96 97 98
  (* The parser's state can be viewed as a stream of elements. This stream is
     empty if the parser is in an initial state; otherwise, it is non-empty.
     The parser's current LR(1) state is the one found in the top element of
     this stream. *)
99

100
  val view: env -> element stream
101

102
end
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
(* This signature is a fragment of the inspection API that is made available
   to the user when [--inspection] is used. This fragment contains type
   definitions for symbols. *)

module type SYMBOLS = sig

  (* The type ['a terminal] represents a terminal symbol. The type ['a
     nonterminal] represents a nonterminal symbol. In both cases, the index
     ['a] represents the type of the semantic values associated with this
     symbol. The concrete definitions of these types are generated. *)

  type 'a terminal
  type 'a nonterminal

  (* The type ['a symbol] represents a terminal or nonterminal symbol. It is
     the disjoint union of the types ['a terminal] and ['a nonterminal]. *)

  type 'a symbol =
    | T : 'a terminal -> 'a symbol
    | N : 'a nonterminal -> 'a symbol

  (* The type [xsymbol] is an existentially quantified version of the type
     ['a symbol]. This type is useful in situations where the index ['a]
     is not statically known. *)

  type xsymbol = 
    | X : 'a symbol -> xsymbol

end

134 135
(* This signature describes the inspection API that is made available to the
   user when [--inspection] is used. *)
136 137 138

module type INSPECTION = sig

139 140 141 142
  (* The types of symbols are described above. *)

  include SYMBOLS

143 144
  (* The type ['a lr1state] is meant to be the same as in [INCREMENTAL_ENGINE]. *)

145
  type 'a lr1state
146

147 148 149 150
  (* The type [production] is meant to be the same as in [INCREMENTAL_ENGINE].
     It represents a production of the grammar. A production can be examined
     via the functions [lhs] and [rhs] below. *)

151 152
  type production

153 154 155 156
  (* An LR(0) item is a pair of a production [prod] and a valid index [i] into
     this production. That is, if the length of [rhs prod] is [n], then [i] is
     comprised between 0 and [n], inclusive. *)

157
  type item =
158 159 160 161 162 163 164 165
      production * int

  (* [incoming_symbol s] is the incoming symbol of the state [s], that is,
     the symbol that the parser must recognize before (has recognized when)
     it enters the state [s]. This function gives access to the semantic
     value [v] stored in a stack element [Element (s, v, _, _)]. Indeed,
     by case analysis on the symbol [incoming_symbol s], one discovers the
     type ['a] of the value [v]. *)
166

POTTIER Francois's avatar
POTTIER Francois committed
167
  val incoming_symbol: 'a lr1state -> 'a symbol
168

169 170 171
  (* [lhs prod] is the left-hand side of the production [prod]. This is
     always a non-terminal symbol. *)

172 173
  val lhs: production -> xsymbol

174 175 176
  (* [rhs prod] is the right-hand side of the production [prod]. This is
     a (possibly empty) sequence of (terminal or nonterminal) symbols. *)

177 178
  val rhs: production -> xsymbol list

179 180 181 182
  (* [items s] is the set of the LR(0) items in the LR(0) core of the LR(1)
     state [s]. This set is presented as a list, in an arbitrary order. *)

  val items: 'a lr1state -> item list
183

184 185
end

186 187 188 189 190 191 192 193 194 195 196 197
(* This signature combines the incremental API and the inspection API. *)

module type EVERYTHING = sig

  include INCREMENTAL_ENGINE

  include INSPECTION
    with type 'a lr1state := 'a lr1state
    with type production := production

end