IncrementalEngine.ml 3.4 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 22 23 24 25 26
     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. *)

  (* [HandlingError] is also 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. *)
27 28 29 30 31 32 33 34

  (* 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]
     or [handling_error], as appropriate. This prevents the user from
     calling [offer] when she should call [handle], or vice-versa. *)

  type input_needed
35
  type about_to_reduce
36 37 38 39
  type handling_error

  type ('a, 'pc) env

40 41
  type production

42 43
  type 'a result =
    | InputNeeded of ('a, input_needed) env
44
    | AboutToReduce of ('a, about_to_reduce) env * production
45 46 47 48 49
    | HandlingError of ('a, handling_error) env
    | Accepted of 'a
    | Rejected

  (* [offer] allows the user to resume the parser after it has suspended
50 51 52
     itself with a result of the form [InputNeeded env]. [offer] expects [env]
     as well as a new token and produces a new result. It does not raise any
     exception. *)
53 54 55 56 57 58 59 60 61 62 63 64 65 66

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

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

  val handle:
    ('a, handling_error) env ->
    'a result

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

  (* We offer a read-only view of the parser's state as a stream of elements. *)

  val view: (_, _) env -> element stream

95
end