engineTypes.ml 14.1 KB
Newer Older
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
(* 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. *)

type ('state, 'semantic_value) stack = {

  (* 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;

  (* The start and end positions of the chunk of input that this cell
     represents. *)

  startp: Lexing.position;
  endp: Lexing.position;

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

  next: ('state, 'semantic_value) stack;

}

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

47 48
(* A parsing environment contains all of the parser's state (except for the
   current program point). *)
49 50 51

type ('state, 'semantic_value, 'token) env = {

52 53 54 55 56 57
  (* 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;

58
  (* The last token that was obtained from the lexer, together with its start
59 60
     and end positions. Warning: before the first call to the lexer has taken
     place, a dummy (and possibly invalid) token is stored here. *)
61

62
  triple: 'token * Lexing.position * Lexing.position;
63 64 65 66

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

67
  stack: ('state, 'semantic_value) stack;
68 69 70 71

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

72
  current: 'state;
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 137 138 139 140 141 142 143 144 145 146 147 148 149 150 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

}

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

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

module type TABLE = sig

  (* The type of automaton states. *)

  type state

  (* 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

  (* The type of semantic values. *)

  type semantic_value

  (* 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

  (* The type of productions. *)

  type production

  (* 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

  (* This is the automaton's goto table. It maps a pair of a state and a
     production to a new state.

     This convention is slightly different from the textbook approach. The
     goto table is usually indexed by a state and a non-terminal symbol. *)

  val goto: state -> production -> state

  (* 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
197
        by the length of the right-hand side of the production;
198 199 200 201

     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
202 203 204 205 206
        computed in step 3;

     5. returning the new stack computed in steps 2 and 4. The environment
        is not affected: the caller of the semantic action is responsible
        for writing the new stack into [env.stack].
207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224

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

  (* If production [prod] is an accepting production, then the semantic action
     is responsible for raising exception [Accept], instead of returning
     normally. This convention allows us to not distinguish between regular
     productions and accepting productions. All we have to do is catch that
     exception at top level. *)

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

  exception Accept of semantic_value
  exception Error

  type semantic_action =
225
      (state, semantic_value, token) env -> (state, semantic_value) stack
226 227 228 229 230 231 232 233

  val semantic_action: production -> semantic_action

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

234 235 236 237 238 239 240
  (* If the flag [log] is false, then the logging functions are guaranteed
     to do nothing, so it is not necessary to call them. If [log] is true,
     the logging functions may or may not have an effect. This flag is
     logically superfluous, but saves time in the table-based back-end. *)

  val log : bool

241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260
  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

    (* Lookahead token is now <terminal> (<pos>-<pos>) *)

261
    val lookahead_token: terminal -> Lexing.position -> Lexing.position -> unit
262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280

    (* 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

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

281
(* This signature describes the monolithic (traditional) LR engine. *)
282

283 284 285
(* In this interface, the parser controls the lexer. *)

module type MONOLITHIC_ENGINE = sig
286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304

  type state

  type token

  type semantic_value

  (* 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) ->
    Lexing.lexbuf ->
    semantic_value

305 306 307 308 309 310 311 312
end

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

(* This signature describes the incremental LR engine. *)

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

314 315 316 317
module type INCREMENTAL_ENGINE = sig

  type token

318
  (* The type ['a result] represents an intermediate or final result of the
319
     parser. An intermediate result can be thought of as a suspension: it
320 321 322
     records the parser's current state, and allows parsing to be resumed.
     The parameter ['a] is the type of the final semantic value that will
     be produced if the parser succeeds. *)
323 324

  (* [InputNeeded] is an intermediate result, which means that the parser
325 326 327 328 329 330
     wishes to read one token before continuing. [HandlingError] is also
     an intermediate result, which means that the parser has detected and
     is trying to handle an error. It does not need more input at this
     point; it is suspending itself only in order to give the user an
     opportunity to handle this error in a different manner, if desired.
     [Accepted] and [Rejected] are final results. *)
331

332 333 334
  (* The type [('a, 'pc) env] is shared by [InputNeeded] and [HandlingError].
     As above, the parameter ['a] is the type of the final semantic value.
     The phantom type parameter ['pc] is instantiated with [input_needed]
335
     or [handling_error], as appropriate. This prevents the user from
336
     calling [offer] when she should call [handle], or vice-versa. *)
337 338 339 340

  type input_needed
  type handling_error

341
  type ('a, 'pc) env
342

343 344 345 346
  type 'a result =
    | InputNeeded of ('a, input_needed) env
    | HandlingError of ('a, handling_error) env
    | Accepted of 'a
347 348 349
    | Rejected

  (* [offer] allows the user to resume the parser after it has suspended
350 351 352
     itself with a result of the form [InputNeeded env] result. [offer]
     expects [env] as well as a new token and produces a new result. It
     does not raise any exception. *)
353 354

  val offer:
355
    ('a, input_needed) env ->
356
    token * Lexing.position * Lexing.position ->
357
    'a result
358

359 360 361
  (* [handle] allows the user to resume the parser after it has suspended
     itself with a result of the form [HandlingError env]. [handle] expects
     [env] and produces a new result. It does not raise any exception. *)
362

363
  val handle:
364 365
    ('a, handling_error) env ->
    'a result
366

367 368
  (* The incremental interface is more general than the monolithic one.
     [entry] can be (and is indeed) implemented by first calling [start],
369
     then calling [offer] and [handle] in a loop, until a final result
370
     is obtained. *)
371

372
end
373

374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396
module type INCREMENTAL_ENGINE_START = sig

  (* [start] is an entry point. It requires just a start state, and begins
     the parsing process. It produces a result, which usually will be an
     [InputNeeded] result. (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] should really produce a result of type ['a result], for a
     fixed ['a] that depends on the state [s]. We cannot express this, so
     we use [semantic_value result], which is safe. The table back-end
     uses [Obj.magic] to produce safe specialized versions of [start]. *)

  type state
  type semantic_value
  type 'a result

  val start:
    state ->
    semantic_value result

end

397 398 399 400 401
(* --------------------------------------------------------------------------- *)

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

402 403 404 405 406
(* 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. *)

407 408 409
module type ENGINE = sig

  include MONOLITHIC_ENGINE
410

411
  include INCREMENTAL_ENGINE
412 413 414
    with type token := token

  include INCREMENTAL_ENGINE_START
415 416
    with type state := state
     and type semantic_value := semantic_value
417
     and type 'a result := 'a result
418 419

end