IncrementalEngine.ml 3.3 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
35
36
37
38
39
40
41
42
43
44
45

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

  type ('a, 'pc) env

  type 'a result =
    | InputNeeded of ('a, input_needed) env
    | HandlingError of ('a, handling_error) env
    | Accepted of 'a
    | Rejected

  (* [offer] allows the user to resume the parser after it has suspended
46
47
48
     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. *)
49
50
51
52
53
54
55
56
57
58
59
60
61
62

  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

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

91
end