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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
(**************************************************************************)
(* *)
(* Menhir *)
(* *)
(* Franois Pottier and Yann Rgis-Gianas, INRIA Rocquencourt *)
(* *)
(* Copyright 2005 Institut National de Recherche en Informatique et *)
(* en Automatique. All rights reserved. This file is distributed *)
(* under the terms of the Q Public License version 1.0, with the *)
(* change described in file LICENSE. *)
(* *)
(**************************************************************************)
open Grammar
(* This module builds the LR(0) automaton associated with the grammar,
then provides access to it. It also provides facilities for
efficiently performing LR(1) constructions. *)
(* ------------------------------------------------------------------------ *)
(* The LR(0) automaton. *)
(* The nodes of the LR(0) automaton are numbered. *)
type node =
int
(* This is the number of nodes in the LR(0) automaton. *)
val n: int
(* These are the automaton's entry states. *)
val entry: node array
(* A node can be converted to the underlying LR(0) set of items. *)
val items: node -> Item.Set.t
(* ------------------------------------------------------------------------ *)
(* Help for building the LR(1) automaton. *)
(* An LR(1) state is internally represented as a pair of an LR(0)
state number and an array of concrete lookahead sets (whose length
depends on the LR(0) state). *)
type lr1state
(* An encoded LR(1) state can be turned into a concrete representation,
that is, a mapping of items to concrete lookahead sets. *)
type concretelr1state =
TerminalSet.t Item.Map.t
val export: lr1state -> concretelr1state
(* One can take the closure of a concrete LR(1) state. *)
val closure: concretelr1state -> concretelr1state
(* The core of an LR(1) state is the underlying LR(0) state. *)
val core: lr1state -> node
(* One can create an LR(1) start state out of an LR(0) start
node. *)
val start: node -> lr1state
(* Information about the transitions and reductions at a state. *)
val transitions: lr1state -> lr1state SymbolMap.t
val reductions: lr1state -> (TerminalSet.t * Production.index) list
(* Equality of states. The two states must have the same core. Then,
they are equal if and only if their lookahead sets are pointwise
equal. *)
val equal: lr1state -> lr1state -> bool
(* Subsumption between states. The two states must have the same
core. Then, one subsumes the other if and only if their lookahead
sets are (pointwise) in the subset relation. *)
val subsume: lr1state -> lr1state -> bool
(* Weak compatibility, in Pager's sense. The two states must have the
same core. *)
val compatible: lr1state -> lr1state -> bool
(* This function determines whether two (core-equivalent) states can
be merged without creating an end-of-stream conflict. *)
val eos_compatible: lr1state -> lr1state -> bool
(* Union of two states. The two states must have the same core. The
new state is obtained by pointwise union of the lookahead sets. *)
val union: lr1state -> lr1state -> lr1state
(* Restriction of a state to a set of tokens of interest. Every
lookahead set is intersected with that set. *)
val restrict: TerminalSet.t -> lr1state -> lr1state
(* Displaying a state. Only the kernel is displayed, not the
closure. *)
val print: lr1state -> string
|
