1(* ML-Yacc Parser Generator (c) 1989 Andrew W. Appel, David R. Tarditi *)
2
3(* base.sig: Base signature file for SML-Yacc.  This file contains signatures
4   that must be loaded before any of the files produced by ML-Yacc are loaded
5*)
6
7(* STREAM: signature for a lazy stream.*)
8
9signature STREAM =
10 sig type 'xa stream
11     val streamify : (unit -> '_a) -> '_a stream
12     val cons : '_a * '_a stream -> '_a stream
13     val get : '_a stream -> '_a * '_a stream
14 end
15
16(* LR_TABLE: signature for an LR Table.
17
18   The list of actions and gotos passed to mkLrTable must be ordered by state
19   number. The values for state 0 are the first in the list, the values for
20    state 1 are next, etc.
21*)
22
23signature LR_TABLE =
24    sig
25        datatype ('a,'b) pairlist = EMPTY | PAIR of 'a * 'b * ('a,'b) pairlist
26	datatype state = STATE of int
27	datatype term = T of int
28	datatype nonterm = NT of int
29	datatype action = SHIFT of state
30			| REDUCE of int
31			| ACCEPT
32			| ERROR
33	type table
34	
35	val numStates : table -> int
36	val numRules : table -> int
37	val describeActions : table -> state ->
38				(term,action) pairlist * action
39	val describeGoto : table -> state -> (nonterm,state) pairlist
40	val action : table -> state * term -> action
41	val goto : table -> state * nonterm -> state
42	val initialState : table -> state
43	exception Goto of state * nonterm
44
45	val mkLrTable : {actions : ((term,action) pairlist * action) array,
46			 gotos : (nonterm,state) pairlist array,
47			 numStates : int, numRules : int,
48			 initialState : state} -> table
49    end
50
51(* TOKEN: signature revealing the internal structure of a token. This signature
52   TOKEN distinct from the signature {parser name}_TOKENS produced by ML-Yacc.
53   The {parser name}_TOKENS structures contain some types and functions to
54    construct tokens from values and positions.
55
56   The representation of token was very carefully chosen here to allow the
57   polymorphic parser to work without knowing the types of semantic values
58   or line numbers.
59
60   This has had an impact on the TOKENS structure produced by SML-Yacc, which
61   is a structure parameter to lexer functors.  We would like to have some
62   type 'a token which functions to construct tokens would create.  A
63   constructor function for a integer token might be
64
65	  INT: int * 'a * 'a -> 'a token.
66 
67   This is not possible because we need to have tokens with the representation
68   given below for the polymorphic parser.
69
70   Thus our constructur functions for tokens have the form:
71
72	  INT: int * 'a * 'a -> (svalue,'a) token
73
74   This in turn has had an impact on the signature that lexers for SML-Yacc
75   must match and the types that a user must declare in the user declarations
76   section of lexers.
77*)
78
79signature TOKEN =
80    sig
81	structure LrTable : LR_TABLE
82        datatype ('a,'b) token = TOKEN of LrTable.term * ('a * 'b * 'b)
83	val sameToken : ('a,'b) token * ('a,'b) token -> bool
84    end
85
86(* LR_PARSER: signature for a polymorphic LR parser *)
87
88signature LR_PARSER =
89    sig
90	structure Stream: STREAM
91	structure LrTable : LR_TABLE
92	structure Token : TOKEN
93
94	sharing LrTable = Token.LrTable
95
96	exception ParseError
97
98	val parse : {table : LrTable.table,
99		     lexer : ('_b,'_c) Token.token Stream.stream,
100		     arg: 'arg,
101		     saction : int *
102			       '_c *
103				(LrTable.state * ('_b * '_c * '_c)) list * 
104				'arg ->
105				     LrTable.nonterm *
106				     ('_b * '_c * '_c) *
107				     ((LrTable.state *('_b * '_c * '_c)) list),
108		     void : '_b,
109		     ec : { is_keyword : LrTable.term -> bool,
110			    noShift : LrTable.term -> bool,
111			    preferred_change : (LrTable.term list * LrTable.term list) list,
112			    errtermvalue : LrTable.term -> '_b,
113			    showTerminal : LrTable.term -> string,
114			    terms: LrTable.term list,
115			    error : string * '_c * '_c -> unit
116			   },
117		     lookahead : int  (* max amount of lookahead used in *)
118				      (* error correction *)
119			} -> '_b *
120			     (('_b,'_c) Token.token Stream.stream)
121    end
122
123(* LEXER: a signature that most lexers produced for use with SML-Yacc's
124   output will match.  The user is responsible for declaring type token,
125   type pos, and type svalue in the UserDeclarations section of a lexer.
126
127   Note that type token is abstract in the lexer.  This allows SML-Yacc to
128   create a TOKENS signature for use with lexers produced by ML-Lex that
129   treats the type token abstractly.  Lexers that are functors parametrized by
130   a Tokens structure matching a TOKENS signature cannot examine the structure
131   of tokens.
132*)
133
134signature LEXER =
135   sig
136       structure UserDeclarations :
137	   sig
138	        type ('a,'b) token
139		type pos
140		type svalue
141	   end
142	val makeLexer : (int -> string) -> unit -> 
143         (UserDeclarations.svalue,UserDeclarations.pos) UserDeclarations.token
144   end
145
146(* ARG_LEXER: the %arg option of ML-Lex allows users to produce lexers which
147   also take an argument before yielding a function from unit to a token
148*)
149
150signature ARG_LEXER =
151   sig
152       structure UserDeclarations :
153	   sig
154	        type ('a,'b) token
155		type pos
156		type svalue
157		type arg
158	   end
159	val makeLexer : (int -> string) -> UserDeclarations.arg -> unit -> 
160         (UserDeclarations.svalue,UserDeclarations.pos) UserDeclarations.token
161   end
162
163(* PARSER_DATA: the signature of ParserData structures in {parser name}LrValsFun
164   produced by  SML-Yacc.  All such structures match this signature.  
165
166   The {parser name}LrValsFun produces a structure which contains all the values
167   except for the lexer needed to call the polymorphic parser mentioned
168   before.
169
170*)
171
172signature PARSER_DATA =
173   sig
174        (* the type of line numbers *)
175
176	type pos
177
178	(* the type of semantic values *)
179
180	type svalue
181
182         (* the type of the user-supplied argument to the parser *)
183 	type arg
184 
185	(* the intended type of the result of the parser.  This value is
186	   produced by applying extract from the structure Actions to the
187	   final semantic value resultiing from a parse.
188	 *)
189
190	type result
191
192	structure LrTable : LR_TABLE
193	structure Token : TOKEN
194	sharing Token.LrTable = LrTable
195
196	(* structure Actions contains the functions which mantain the
197	   semantic values stack in the parser.  Void is used to provide
198	   a default value for the semantic stack.
199	 *)
200
201	structure Actions : 
202	  sig
203	      val actions : int * pos *
204		   (LrTable.state * (svalue * pos * pos)) list * arg->
205		         LrTable.nonterm * (svalue * pos * pos) *
206			 ((LrTable.state *(svalue * pos * pos)) list)
207	      val void : svalue
208	      val extract : svalue -> result
209	  end
210
211	(* structure EC contains information used to improve error
212	   recovery in an error-correcting parser *)
213
214	structure EC :
215	   sig
216	     val is_keyword : LrTable.term -> bool
217	     val noShift : LrTable.term -> bool
218 	     val preferred_change : (LrTable.term list * LrTable.term list) list
219	     val errtermvalue : LrTable.term -> svalue
220	     val showTerminal : LrTable.term -> string
221	     val terms: LrTable.term list
222	   end
223
224	(* table is the LR table for the parser *)
225
226	val table : LrTable.table
227    end
228
229(* signature PARSER is the signature that most user parsers created by 
230   SML-Yacc will match.
231*)
232
233signature PARSER =
234    sig
235        structure Token : TOKEN
236	structure Stream : STREAM
237	exception ParseError
238
239	(* type pos is the type of line numbers *)
240
241	type pos
242
243	(* type result is the type of the result from the parser *)
244
245	type result
246
247         (* the type of the user-supplied argument to the parser *)
248 	type arg
249	
250	(* type svalue is the type of semantic values for the semantic value
251	   stack
252	 *)
253
254	type svalue
255
256	(* val makeLexer is used to create a stream of tokens for the parser *)
257
258	val makeLexer : (int -> string) ->
259			 (svalue,pos) Token.token Stream.stream
260
261	(* val parse takes a stream of tokens and a function to print
262	   errors and returns a value of type result and a stream containing
263	   the unused tokens
264	 *)
265
266	val parse : int * ((svalue,pos) Token.token Stream.stream) *
267		    (string * pos * pos -> unit) * arg ->
268				result * (svalue,pos) Token.token Stream.stream
269
270	val sameToken : (svalue,pos) Token.token * (svalue,pos) Token.token ->
271				bool
272     end
273
274(* signature ARG_PARSER is the signature that will be matched by parsers whose
275    lexer takes an additional argument.
276*)
277
278signature ARG_PARSER = 
279    sig
280        structure Token : TOKEN
281	structure Stream : STREAM
282	exception ParseError
283
284	type arg
285	type lexarg
286	type pos
287	type result
288	type svalue
289
290	val makeLexer : (int -> string) -> lexarg ->
291			 (svalue,pos) Token.token Stream.stream
292	val parse : int * ((svalue,pos) Token.token Stream.stream) *
293		    (string * pos * pos -> unit) * arg ->
294				result * (svalue,pos) Token.token Stream.stream
295
296	val sameToken : (svalue,pos) Token.token * (svalue,pos) Token.token ->
297				bool
298     end
299
300