Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/branches/SMLNJ/src/ml-yacc/src/sigs.sml
ViewVC logotype

Annotation of /sml/branches/SMLNJ/src/ml-yacc/src/sigs.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 8 - (view) (download)

1 : monnier 2 (* ML-Yacc Parser Generator (c) 1989, 1991 Andrew W. Appel, David R. Tarditi
2 :     *
3 :     * $Log$
4 : monnier 8 * Revision 1.1.1.2 1998/01/18 01:00:09 monnier
5 :     * *** empty log message ***
6 : monnier 2 *
7 : monnier 8 * Revision 1.2 1997/05/20 16:23:21 dbm
8 :     * SML '97 sharing.
9 :     *
10 : monnier 2 # Revision 1.1.1.1 1997/01/14 01:38:06 george
11 :     # Version 109.24
12 :     #
13 :     * Revision 1.2 1996/02/26 15:02:38 george
14 :     * print no longer overloaded.
15 :     * use of makestring has been removed and replaced with Int.toString ..
16 :     * use of IO replaced with TextIO
17 :     *
18 :     * Revision 1.1.1.1 1996/01/31 16:01:46 george
19 :     * Version 109
20 :     *
21 :     *)
22 :    
23 :     signature HEADER =
24 :     sig
25 :     type pos = int
26 :     val lineno : pos ref
27 :     val text : string list ref
28 :    
29 :     type inputSource
30 :     val newSource : string * TextIO.instream * TextIO.outstream -> inputSource
31 :     val error : inputSource -> pos -> string -> unit
32 :     val warn : inputSource -> pos -> string -> unit
33 :     val errorOccurred : inputSource -> unit -> bool
34 :    
35 :     datatype symbol = SYMBOL of string * pos
36 :     val symbolName : symbol -> string
37 :     val symbolPos : symbol -> pos
38 :     val symbolMake : string * int -> symbol
39 :    
40 :     type ty
41 :     val tyName : ty -> string
42 :     val tyMake : string -> ty
43 :    
44 :     (* associativities: each kind of associativity is assigned a unique
45 :     integer *)
46 :    
47 :     datatype prec = LEFT | RIGHT | NONASSOC
48 :     datatype control = NODEFAULT | VERBOSE | PARSER_NAME of symbol |
49 :     FUNCTOR of string | START_SYM of symbol |
50 :     NSHIFT of symbol list | POS of string | PURE |
51 :     PARSE_ARG of string * string
52 :    
53 :     datatype rule = RULE of {lhs : symbol, rhs : symbol list,
54 :     code : string, prec : symbol option}
55 :    
56 :     datatype declData = DECL of
57 :     {eop : symbol list,
58 :     keyword : symbol list,
59 :     nonterm : (symbol * ty option) list option,
60 :     prec : (prec * (symbol list)) list,
61 :     change: (symbol list * symbol list) list,
62 :     term : (symbol * ty option) list option,
63 :     control : control list,
64 :     value : (symbol * string) list}
65 :    
66 :     val join_decls : declData * declData * inputSource * pos -> declData
67 :    
68 :     type parseResult
69 :     val getResult : parseResult -> string * declData * rule list
70 :     end;
71 :    
72 :     signature PARSE_GEN_PARSER =
73 :     sig
74 :     structure Header : HEADER
75 :     val parse : string -> Header.parseResult * Header.inputSource
76 :     end;
77 :    
78 :     signature PARSE_GEN =
79 :     sig
80 :     val parseGen : string -> unit
81 :     end;
82 :    
83 :     signature GRAMMAR =
84 :     sig
85 :    
86 :     datatype term = T of int
87 :     datatype nonterm = NT of int
88 :     datatype symbol = TERM of term | NONTERM of nonterm
89 :    
90 :     (* grammar:
91 :     terminals should be numbered from 0 to terms-1,
92 :     nonterminals should be numbered from 0 to nonterms-1,
93 :     rules should be numbered between 0 and (length rules) - 1,
94 :     higher precedence binds tighter,
95 :     start nonterminal should not occur on the rhs of any rule
96 :     *)
97 :    
98 :     datatype grammar = GRAMMAR of
99 :     {rules: {lhs : nonterm, rhs : symbol list,
100 :     precedence : int option, rulenum : int } list,
101 :     terms: int,
102 :     nonterms: int,
103 :     start : nonterm,
104 :     eop : term list,
105 :     noshift : term list,
106 :     precedence : term -> int option,
107 :     termToString : term -> string,
108 :     nontermToString : nonterm -> string}
109 :     end
110 :    
111 :     (* signature for internal version of grammar *)
112 :    
113 :     signature INTGRAMMAR =
114 :     sig
115 :     structure Grammar : GRAMMAR
116 :     structure SymbolAssoc : TABLE
117 :     structure NontermAssoc : TABLE
118 :    
119 :     sharing type SymbolAssoc.key = Grammar.symbol
120 :     sharing type NontermAssoc.key = Grammar.nonterm
121 :    
122 :     datatype rule = RULE of
123 :     {lhs : Grammar.nonterm,
124 :     rhs : Grammar.symbol list,
125 :    
126 :     (* internal number of rule - convenient for producing LR graph *)
127 :    
128 :     num : int,
129 :     rulenum : int,
130 :     precedence : int option}
131 :    
132 :     val gtTerm : Grammar.term * Grammar.term -> bool
133 :     val eqTerm : Grammar.term * Grammar.term -> bool
134 :    
135 :     val gtNonterm : Grammar.nonterm * Grammar.nonterm -> bool
136 :     val eqNonterm : Grammar.nonterm * Grammar.nonterm -> bool
137 :    
138 :     val gtSymbol : Grammar.symbol * Grammar.symbol -> bool
139 :     val eqSymbol : Grammar.symbol * Grammar.symbol -> bool
140 :    
141 :     (* Debugging information will be generated only if DEBUG is true. *)
142 :    
143 :     val DEBUG : bool
144 :    
145 :     val prRule : (Grammar.symbol -> string) * (Grammar.nonterm -> string) *
146 :     (string -> 'b) -> rule -> unit
147 :     val prGrammar : (Grammar.symbol -> string)*(Grammar.nonterm -> string) *
148 :     (string -> unit) -> Grammar.grammar -> unit
149 :     end
150 :    
151 :     signature CORE =
152 :     sig
153 :     structure Grammar : GRAMMAR
154 :     structure IntGrammar : INTGRAMMAR
155 :     sharing Grammar = IntGrammar.Grammar
156 :    
157 :     datatype item = ITEM of
158 :     { rule : IntGrammar.rule,
159 :     dot : int,
160 :    
161 :     (* rhsAfter: The portion of the rhs of a rule that lies after the dot *)
162 :    
163 :     rhsAfter: Grammar.symbol list }
164 :    
165 :     (* eqItem and gtItem compare items *)
166 :    
167 :     val eqItem : item * item -> bool
168 :     val gtItem : item * item -> bool
169 :    
170 :     (* functions for maintaining ordered item lists *)
171 :    
172 :     val insert : item * item list -> item list
173 :     val union : item list * item list -> item list
174 :    
175 :     (* core: a set of items. It is represented by an ordered list of items.
176 :     The list is in ascending order The rule numbers and the positions of the
177 :     dots are used to order the items. *)
178 :    
179 :     datatype core = CORE of item list * int (* state # *)
180 :    
181 :     (* gtCore and eqCore compare the lists of items *)
182 :    
183 :     val gtCore : core * core -> bool
184 :     val eqCore : core * core -> bool
185 :    
186 :     (* functions for debugging *)
187 :    
188 :     val prItem : (Grammar.symbol -> string) * (Grammar.nonterm -> string) *
189 :     (string -> unit) -> item -> unit
190 :     val prCore : (Grammar.symbol -> string) * (Grammar.nonterm -> string) *
191 :     (string -> unit) -> core -> unit
192 :     end
193 :    
194 :     signature CORE_UTILS =
195 :     sig
196 :    
197 :     structure Grammar : GRAMMAR
198 :     structure IntGrammar : INTGRAMMAR
199 :     structure Core : CORE
200 :    
201 :     sharing Grammar = IntGrammar.Grammar = Core.Grammar
202 :     sharing IntGrammar = Core.IntGrammar
203 :    
204 :     (* mkFuncs: create functions for the set of productions derived from a
205 :     nonterminal, the cores that result from shift/gotos from a core,
206 :     and return a list of rules *)
207 :    
208 :     val mkFuncs : Grammar.grammar ->
209 :     { produces : Grammar.nonterm -> IntGrammar.rule list,
210 :    
211 :     (* shifts: take a core and compute all the cores that result from shifts/gotos
212 :     on symbols *)
213 :    
214 :     shifts : Core.core -> (Grammar.symbol*Core.item list) list,
215 :     rules: IntGrammar.rule list,
216 :    
217 :     (* epsProds: take a core compute epsilon productions for it *)
218 :    
219 :     epsProds : Core.core -> IntGrammar.rule list}
220 :     end
221 :    
222 :     signature LRGRAPH =
223 :     sig
224 :     structure Grammar : GRAMMAR
225 :     structure IntGrammar : INTGRAMMAR
226 :     structure Core : CORE
227 :    
228 :     sharing Grammar = IntGrammar.Grammar = Core.Grammar
229 :     sharing IntGrammar = Core.IntGrammar
230 :    
231 :     type graph
232 :     val edges : Core.core * graph -> {edge:Grammar.symbol,to:Core.core} list
233 :     val nodes : graph -> Core.core list
234 :     val shift : graph -> int * Grammar.symbol -> int (* int = state # *)
235 :     val core : graph -> int -> Core.core (* get core for a state *)
236 :    
237 :     (* mkGraph: compute the LR(0) sets of items *)
238 :    
239 :     val mkGraph : Grammar.grammar ->
240 :     {graph : graph,
241 :     produces : Grammar.nonterm -> IntGrammar.rule list,
242 :     rules : IntGrammar.rule list,
243 :     epsProds: Core.core -> IntGrammar.rule list}
244 :    
245 :     val prGraph: (Grammar.symbol -> string)*(Grammar.nonterm -> string) *
246 :     (string -> unit) -> graph -> unit
247 :     end
248 :    
249 :     signature LOOK =
250 :     sig
251 :     structure Grammar : GRAMMAR
252 :     structure IntGrammar : INTGRAMMAR
253 :     sharing Grammar = IntGrammar.Grammar
254 :    
255 :     val union : Grammar.term list * Grammar.term list -> Grammar.term list
256 :     val make_set : Grammar.term list -> Grammar.term list
257 :    
258 :     val mkFuncs : {rules : IntGrammar.rule list, nonterms : int,
259 :     produces : Grammar.nonterm -> IntGrammar.rule list} ->
260 :     {nullable: Grammar.nonterm -> bool,
261 :     first : Grammar.symbol list -> Grammar.term list}
262 :    
263 :     val prLook : (Grammar.term -> string) * (string -> unit) ->
264 :     Grammar.term list -> unit
265 :     end
266 :    
267 :     signature LALR_GRAPH =
268 :     sig
269 :     structure Grammar : GRAMMAR
270 :     structure IntGrammar : INTGRAMMAR
271 :     structure Core : CORE
272 :     structure Graph : LRGRAPH
273 :    
274 :     sharing Grammar = IntGrammar.Grammar = Core.Grammar = Graph.Grammar
275 :     sharing IntGrammar = Core.IntGrammar = Graph.IntGrammar
276 :     sharing Core = Graph.Core
277 :    
278 :     datatype lcore = LCORE of (Core.item * Grammar.term list) list * int
279 :     val addLookahead : {graph : Graph.graph,
280 :     first : Grammar.symbol list -> Grammar.term list,
281 :     eop : Grammar.term list,
282 :     nonterms : int,
283 :     nullable: Grammar.nonterm -> bool,
284 :     produces : Grammar.nonterm -> IntGrammar.rule list,
285 :     rules : IntGrammar.rule list,
286 :     epsProds : Core.core -> IntGrammar.rule list,
287 :     print : string -> unit, (* for debugging *)
288 :     termToString : Grammar.term -> string,
289 :     nontermToString : Grammar.nonterm -> string} ->
290 :     lcore list
291 :     val prLcore : (Grammar.symbol -> string) * (Grammar.nonterm -> string) *
292 :     (Grammar.term -> string) * (string -> unit) ->
293 :     lcore -> unit
294 :     end
295 :    
296 :     (* LR_ERRS: errors found while constructing an LR table *)
297 :    
298 :     signature LR_ERRS =
299 :     sig
300 :     structure LrTable : LR_TABLE
301 :    
302 :     (* RR = reduce/reduce,
303 :     SR = shift/reduce
304 :     NS: non-shiftable terminal found on the rhs of a rule
305 :     NOT_REDUCED n: rule number n was not reduced
306 :     START n : start symbol found on the rhs of rule n *)
307 :    
308 :     datatype err = RR of LrTable.term * LrTable.state * int * int
309 :     | SR of LrTable.term * LrTable.state * int
310 :     | NS of LrTable.term * int
311 :     | NOT_REDUCED of int
312 :     | START of int
313 :    
314 :     val summary : err list -> {rr : int, sr: int,
315 :     not_reduced : int, start : int,nonshift : int}
316 :    
317 :     val printSummary : (string -> unit) -> err list -> unit
318 :    
319 :     end
320 :    
321 :     (* PRINT_STRUCT: prints a structure which includes a value 'table' and a
322 :     structure Table whose signature matches LR_TABLE. The table in the printed
323 :     structure will contain the same information as the one passed to
324 :     printStruct, although the representation may be different. It returns
325 :     the number of entries left in the table after compaction.*)
326 :    
327 :     signature PRINT_STRUCT =
328 :     sig
329 :     structure LrTable : LR_TABLE
330 :     val makeStruct :
331 :     {table : LrTable.table,
332 :     name : string,
333 :     print: string -> unit,
334 :     verbose : bool
335 :     } -> int
336 :     end
337 :    
338 :     (* VERBOSE: signature for a structure which takes a table and creates a
339 :     verbose description of it *)
340 :    
341 :     signature VERBOSE =
342 :     sig
343 :     structure Errs : LR_ERRS
344 :     val printVerbose :
345 :     {table : Errs.LrTable.table,
346 :     entries : int,
347 :     termToString : Errs.LrTable.term -> string,
348 :     nontermToString : Errs.LrTable.nonterm -> string,
349 :     stateErrs : Errs.LrTable.state -> Errs.err list,
350 :     errs : Errs.err list,
351 :     print: string -> unit,
352 :     printCores : (string -> unit) -> Errs.LrTable.state -> unit,
353 :     printRule : (string -> unit) -> int -> unit} -> unit
354 :     end
355 :    
356 :     (* MAKE_LR_TABLE: signature for a structure which includes a structure
357 :     matching the signature LR_TABLE and a function which maps grammars
358 :     to tables *)
359 :    
360 :     signature MAKE_LR_TABLE =
361 :     sig
362 :     structure Grammar : GRAMMAR
363 :     structure Errs : LR_ERRS
364 :     structure LrTable : LR_TABLE
365 :     sharing Errs.LrTable = LrTable
366 :    
367 :     sharing type LrTable.term = Grammar.term
368 :     sharing type LrTable.nonterm = Grammar.nonterm
369 :    
370 :     (* boolean value determines whether default reductions will be used.
371 :     If it is true, reductions will be used. *)
372 :    
373 :     val mkTable : Grammar.grammar * bool ->
374 :     LrTable.table *
375 :     (LrTable.state -> Errs.err list) * (* errors in a state *)
376 :     ((string -> unit) -> LrTable.state -> unit) *
377 :     Errs.err list (* list of all errors *)
378 :     end;
379 :    
380 :     (* SHRINK_LR_TABLE: finds unique action entry rows in the action table
381 :     for the LR parser *)
382 :    
383 :     signature SHRINK_LR_TABLE =
384 :     sig
385 :     (* Takes an action table represented as a list of action rows.
386 :     It returns the number of unique rows left in the action table,
387 :     a list of integers which maps each original row to a unique
388 :     row, and a list of unique rows *)
389 :     structure LrTable : LR_TABLE
390 :     val shrinkActionList : LrTable.table * bool ->
391 :     (int * int list *
392 :     ((LrTable.term,LrTable.action) LrTable.pairlist *
393 :     LrTable.action) list) * int
394 :     end

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0