Attention une mise à jour du serveur va être effectuée le lundi 17 mai entre 13h et 13h30. Cette mise à jour va générer une interruption du service de quelques minutes.

EngineTypes.ml 14.2 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 Library General Public License version 2, with a         *)
(*  special exception on linking, as described in the file LICENSE.           *)
(*                                                                            *)
(******************************************************************************)

14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
(* This file defines several types and module types that are used in the
   specification of module [Engine]. *)

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

(* It would be nice if we could keep the structure of stacks and environments
   hidden. However, stacks and environments must be accessible to semantic
   actions, so the following data structure definitions must be public. *)

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

(* A stack is a linked list of cells. A sentinel cell -- which is its own
   successor -- is used to mark the bottom of the stack. The sentinel cell
   itself is not significant -- it contains dummy values. *)

29
type ('state, 'semantic_value, 'location) stack = {
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

  (* The state that we should go back to if we pop this stack cell. *)

  (* This convention means that the state contained in the top stack cell is
     not the current state [env.current]. It also means that the state found
     within the sentinel is a dummy -- it is never consulted. This convention
     is the same as that adopted by the code-based back-end. *)

  state: 'state;

  (* The semantic value associated with the chunk of input that this cell
     represents. *)

  semv: 'semantic_value;

45
  (* The location associated with the chunk of input that this cell
46 47
     represents. *)

48
  location: 'location;
49 50 51 52

  (* The next cell down in the stack. If this is a self-pointer, then this
     cell is the sentinel, and the stack is conceptually empty. *)

53
  next: ('state, 'semantic_value, 'location) stack;
54 55 56 57 58

}

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

59 60
(* A parsing environment contains all of the parser's state (except for the
   current program point). *)
61

62
type ('state, 'semantic_value, 'token, 'location) env = {
63

64 65 66 67 68 69
  (* If this flag is true, then the first component of [env.triple] should
     be ignored, as it has been logically overwritten with the [error]
     pseudo-token. *)

  error: bool;

70 71
  (* The last token that was obtained from the lexer, together with its
     location . Warning: before the first call to the lexer has taken
72
     place, a dummy (and possibly invalid) token is stored here. *)
73

74
  triple: 'token * 'location;
75 76 77 78

  (* The stack. In [CodeBackend], it is passed around on its own,
     whereas, here, it is accessed via the environment. *)

79
  stack: ('state, 'semantic_value, 'location) stack;
80 81 82 83

  (* The current state. In [CodeBackend], it is passed around on its
     own, whereas, here, it is accessed via the environment. *)

84
  current: 'state;
85 86 87 88 89 90 91 92 93 94 95 96 97 98

}

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

(* This signature describes the parameters that must be supplied to the LR
   engine. *)

module type TABLE = sig

  (* The type of automaton states. *)

  type state

99 100 101 102
  (* States are numbered. *)

  val number: state -> int

103 104 105 106 107 108 109 110 111 112 113 114
  (* The type of tokens. These can be thought of as real tokens, that is,
     tokens returned by the lexer. They carry a semantic value. This type
     does not include the [error] pseudo-token. *)

  type token

  (* The type of terminal symbols. These can be thought of as integer codes.
     They do not carry a semantic value. This type does include the [error]
     pseudo-token. *)

  type terminal

115 116 117 118
  (* The type of nonterminal symbols. *)

  type nonterminal

119 120 121 122
  (* The type of semantic values. *)

  type semantic_value

123 124
  (* The type of locations. *)

125
  type location
126

127 128 129 130 131 132 133 134 135 136 137 138 139
  (* A token is conceptually a pair of a (non-[error]) terminal symbol and
     a semantic value. The following two functions are the pair projections. *)

  val token2terminal: token -> terminal
  val token2value: token -> semantic_value

  (* Even though the [error] pseudo-token is not a real token, it is a
     terminal symbol. Furthermore, for regularity, it must have a semantic
     value. *)

  val error_terminal: terminal
  val error_value: semantic_value

140 141 142 143
  (* [foreach_terminal] allows iterating over all terminal symbols. *)

  val foreach_terminal: (terminal -> 'a -> 'a) -> 'a -> 'a

144 145 146 147
  (* The type of productions. *)

  type production

148 149 150
  val production_index: production -> int
  val find_production: int -> production

151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214
  (* If a state [s] has a default reduction on production [prod], then, upon
     entering [s], the automaton should reduce [prod] without consulting the
     lookahead token. The following function allows determining which states
     have default reductions. *)

  (* Instead of returning a value of a sum type -- either [DefRed prod], or
     [NoDefRed] -- it accepts two continuations, and invokes just one of
     them. This mechanism allows avoiding a memory allocation. *)

  val default_reduction:
    state ->
    ('env -> production -> 'answer) ->
    ('env -> 'answer) ->
    'env -> 'answer

  (* An LR automaton can normally take three kinds of actions: shift, reduce,
     or fail. (Acceptance is a particular case of reduction: it consists in
     reducing a start production.) *)

  (* There are two variants of the shift action. [shift/discard s] instructs
     the automaton to discard the current token, request a new one from the
     lexer, and move to state [s]. [shift/nodiscard s] instructs it to move to
     state [s] without requesting a new token. This instruction should be used
     when [s] has a default reduction on [#]. See [CodeBackend.gettoken] for
     details. *)

  (* This is the automaton's action table. It maps a pair of a state and a
     terminal symbol to an action. *)

  (* Instead of returning a value of a sum type -- one of shift/discard,
     shift/nodiscard, reduce, or fail -- this function accepts three
     continuations, and invokes just one them. This mechanism allows avoiding
     a memory allocation. *)

  (* In summary, the parameters to [action] are as follows:

     - the first two parameters, a state and a terminal symbol, are used to
       look up the action table;

     - the next parameter is the semantic value associated with the above
       terminal symbol; it is not used, only passed along to the shift
       continuation, as explained below;

     - the shift continuation expects an environment; a flag that tells
       whether to discard the current token; the terminal symbol that
       is being shifted; its semantic value; and the target state of
       the transition;

     - the reduce continuation expects an environment and a production;

     - the fail continuation expects an environment;

     - the last parameter is the environment; it is not used, only passed
       along to the selected continuation. *)

  val action:
    state ->
    terminal ->
    semantic_value ->
    ('env -> bool -> terminal -> semantic_value -> state -> 'answer) ->
    ('env -> production -> 'answer) ->
    ('env -> 'answer) ->
    'env -> 'answer

215 216 217
  (* This is the automaton's goto table. This table maps a pair of a state
     and a nonterminal symbol to a new state. By extension, it also maps a
     pair of a state and a production to a new state. *)
218

219 220 221 222 223 224 225 226 227 228
  (* The function [goto_nt] can be applied to [s] and [nt] ONLY if the state
     [s] has an outgoing transition labeled [nt]. Otherwise, its result is
     undefined. Similarly, the call [goto_prod prod s] is permitted ONLY if
     the state [s] has an outgoing transition labeled with the nonterminal
     symbol [lhs prod]. The function [maybe_goto_nt] involves an additional
     dynamic check and CAN be called even if there is no outgoing transition. *)

  val       goto_nt  : state -> nonterminal -> state
  val       goto_prod: state -> production  -> state
  val maybe_goto_nt:   state -> nonterminal -> state option
229

230 231 232 233
  (* [is_start prod] tells whether the production [prod] is a start production. *)

  val is_start: production -> bool

234 235 236 237 238
  (* By convention, a semantic action is responsible for:

     1. fetching whatever semantic values and positions it needs off the stack;

     2. popping an appropriate number of cells off the stack, as dictated
239
        by the length of the right-hand side of the production;
240 241 242 243

     3. computing a new semantic value, as well as new start and end positions;

     4. pushing a new stack cell, which contains the three values
244 245
        computed in step 3;

246
     5. returning the new stack computed in steps 2 and 4.
247 248 249 250 251 252 253 254 255 256 257

     Point 1 is essentially forced upon us: if semantic values were fetched
     off the stack by this interpreter, then the calling convention for
     semantic actions would be variadic: not all semantic actions would have
     the same number of arguments. The rest follows rather naturally. *)

  (* Semantic actions are allowed to raise [Error]. *)

  exception Error

  type semantic_action =
258 259
        (state, semantic_value, token, location) env ->
        (state, semantic_value, location) stack
260 261 262

  val semantic_action: production -> semantic_action

263 264 265 266 267 268 269 270
  (* [may_reduce state prod] tests whether the state [state] is capable of
     reducing the production [prod]. This function is currently costly and
     is not used by the core LR engine. It is used in the implementation
     of certain functions, such as [force_reduction], which allow the engine
     to be driven programmatically. *)

  val may_reduce: state -> production -> bool

271 272 273 274 275
  (* The LR engine requires a number of hooks, which are used for logging. *)

  (* The comments below indicate the conventional messages that correspond
     to these hooks in the code-based back-end; see [CodeBackend]. *)

276 277
  (* If the flag [log] is false, then the logging functions are not called.
     If it is [true], then they are called. *)
278 279 280

  val log : bool

281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298
  module Log : sig

    (* State %d: *)

    val state: state -> unit

    (* Shifting (<terminal>) to state <state> *)

    val shift: terminal -> state -> unit

    (* Reducing a production should be logged either as a reduction
       event (for regular productions) or as an acceptance event (for
       start productions). *)

    (* Reducing production <production> / Accepting *)

    val reduce_or_accept: production -> unit

299
    (* Lookahead token is now <terminal> (location) *)
300

301
    val lookahead_token: terminal -> location -> unit
302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320

    (* Initiating error handling *)

    val initiating_error_handling: unit -> unit

    (* Resuming error handling *)

    val resuming_error_handling: unit -> unit

    (* Handling error in state <state> *)

    val handling_error: state -> unit

  end

end

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

321
(* This signature describes the monolithic (traditional) LR engine. *)
322

323 324 325
(* In this interface, the parser controls the lexer. *)

module type MONOLITHIC_ENGINE = sig
326 327 328 329 330 331 332

  type state

  type token

  type semantic_value

333 334
  type location

335 336 337 338 339 340 341 342 343
  (* An entry point to the engine requires a start state, a lexer, and a lexing
     buffer. It either succeeds and produces a semantic value, or fails and
     raises [Error]. *)

  exception Error

  val entry:
    state ->
    (Lexing.lexbuf -> token) ->
344
    (Lexing.lexbuf -> location) ->
345 346 347
    Lexing.lexbuf ->
    semantic_value

348 349 350 351
end

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

352
(* The following signatures describe the incremental LR engine. *)
353

354
(* First, see [INCREMENTAL_ENGINE] in the file [IncrementalEngine.ml]. *)
355

356 357 358 359
(* The [start] function is set apart because we do not wish to publish
   it as part of the generated [parser.mli] file. Instead, the table
   back-end will publish specialized versions of it, with a suitable
   type cast. *)
360

361 362
module type INCREMENTAL_ENGINE_START = sig

363 364 365 366 367 368 369 370 371 372 373
  (* [start] is an entry point. It requires a start state and a start position
     and begins the parsing process. If the lexer is based on an OCaml lexing
     buffer, the start position should be [lexbuf.lex_curr_p]. [start] produces
     a checkpoint, which usually will be an [InputNeeded] checkpoint. (It could
     be [Accepted] if this starting state accepts only the empty word. It could
     be [Rejected] if this starting state accepts no word at all.) It does not
     raise any exception. *)

  (* [start s pos] should really produce a checkpoint of type ['a checkpoint],
     for a fixed ['a] that depends on the state [s]. We cannot express this, so
     we use [semantic_value checkpoint], which is safe. The table back-end uses
374
     [Obj.magic] to produce safe specialized versions of [start]. *)
375 376

  type state
377
  type location
378
  type semantic_value
379
  type 'a checkpoint
380 381 382

  val start:
    state ->
383
    location ->
384
    semantic_value checkpoint
385 386 387

end

388 389 390 391 392 393 394 395
(* --------------------------------------------------------------------------- *)

(* This signature describes the LR engine, which combines the monolithic
   and incremental interfaces. *)

module type ENGINE = sig

  include MONOLITHIC_ENGINE
396

397
  include IncrementalEngine.INCREMENTAL_ENGINE
398
    with type token := token
399
     and type 'a lr1state = state (* useful for us; hidden from the end user *)
400
     and type location := location
401 402

  include INCREMENTAL_ENGINE_START
403 404
    with type state := state
     and type semantic_value := semantic_value
405
     and type 'a checkpoint := 'a checkpoint
406
     and type location := location
407 408

end
Frédéric Bour's avatar
Frédéric Bour committed
409 410 411 412 413 414 415 416 417 418 419 420 421 422 423

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

(* This signature describes the signature of locations manipulated by Menhir. *)

module type LOCATION = sig
  type t

  val empty_after : t -> t
  val join : t array -> t
  val trace : t -> string
  val get : Lexing.lexbuf -> t
end

module As_location(M : LOCATION) : LOCATION with type t = M.t = M