Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | (* Modified by Matthew Fluet on 2011-06-17. |
2 | * Use simple file name (rather than absolute paths) in line directives in output. | |
3 | *) | |
4 | (* Modified by Vesa Karvonen on 2007-12-18. | |
5 | * Create line directives in output. | |
6 | *) | |
7 | (* ML-Yacc Parser Generator (c) 1989, 1990 Andrew W. Appel, David R. Tarditi *) | |
8 | ||
9 | functor ParseGenFun(structure ParseGenParser : PARSE_GEN_PARSER | |
10 | structure MakeTable : MAKE_LR_TABLE | |
11 | structure Verbose : VERBOSE | |
12 | structure PrintStruct : PRINT_STRUCT | |
13 | ||
14 | sharing MakeTable.LrTable = PrintStruct.LrTable | |
15 | sharing MakeTable.Errs = Verbose.Errs | |
16 | ||
17 | structure Absyn : ABSYN | |
18 | ) : PARSE_GEN = | |
19 | struct | |
20 | val sub = Array.sub | |
21 | infix 9 sub | |
22 | structure Grammar = MakeTable.Grammar | |
23 | structure Header = ParseGenParser.Header | |
24 | ||
25 | open Header Grammar | |
26 | ||
27 | (* approx. maximum length of a line *) | |
28 | ||
29 | val lineLength = 70 | |
30 | ||
31 | (* record type describing names of structures in the program being | |
32 | generated *) | |
33 | ||
34 | datatype names = NAMES | |
35 | of {miscStruct : string, (* Misc{n} struct name *) | |
36 | tableStruct : string, (* LR table structure *) | |
37 | tokenStruct : string, (* Tokens{n} struct name *) | |
38 | actionsStruct : string, (* Actions structure *) | |
39 | valueStruct: string, (* semantic value structure *) | |
40 | ecStruct : string, (* error correction structure *) | |
41 | arg: string, (* user argument for parser *) | |
42 | tokenSig : string, (* TOKENS{n} signature *) | |
43 | miscSig :string, (* Signature for Misc structure *) | |
44 | dataStruct:string, (* name of structure in Misc *) | |
45 | (* which holds parser data *) | |
46 | dataSig:string (* signature for this structure *) | |
47 | ||
48 | } | |
49 | ||
50 | val DEBUG = true | |
51 | exception Semantic | |
52 | ||
53 | (* common functions and values used in printing out program *) | |
54 | ||
55 | datatype values = VALS | |
56 | of {say : string -> unit, | |
57 | saydot : string -> unit, | |
58 | sayln : string -> unit, | |
59 | fmtPos : {line : int, col : int} option -> string, | |
60 | pureActions: bool, | |
61 | pos_type : string, | |
62 | arg_type : string, | |
63 | ntvoid : string, | |
64 | termvoid : string, | |
65 | start : Grammar.nonterm, | |
66 | hasType : Grammar.symbol -> bool, | |
67 | ||
68 | (* actual (user) name of terminal *) | |
69 | ||
70 | termToString : Grammar.term -> string, | |
71 | symbolToString : Grammar.symbol -> string, | |
72 | ||
73 | (* type symbol comes from the HDR structure, | |
74 | and is now abstract *) | |
75 | ||
76 | term : (Header.symbol * ty option) list, | |
77 | nonterm : (Header.symbol * ty option) list, | |
78 | terms : Grammar.term list, | |
79 | ||
80 | (* tokenInfo is the user inserted spec in | |
81 | the *_TOKEN sig*) | |
82 | tokenInfo : string option} | |
83 | ||
84 | structure SymbolHash = Hash(type elem = string | |
85 | val gt = (op >) : string*string -> bool) | |
86 | ||
87 | structure TermTable = Table(type key = Grammar.term | |
88 | val gt = fn (T i,T j) => i > j) | |
89 | ||
90 | structure SymbolTable = Table( | |
91 | type key = Grammar.symbol | |
92 | val gt = fn (TERM(T i),TERM(T j)) => i>j | |
93 | | (NONTERM(NT i),NONTERM(NT j)) => i>j | |
94 | | (NONTERM _,TERM _) => true | |
95 | | (TERM _,NONTERM _) => false) | |
96 | ||
97 | (* printTypes: function to print the following types in the LrValues | |
98 | structure and a structure containing the datatype svalue: | |
99 | ||
100 | type svalue -- it holds semantic values on the parse | |
101 | stack | |
102 | type pos -- the type of line numbers | |
103 | type result -- the type of the value that results | |
104 | from the parse | |
105 | ||
106 | The type svalue is set equal to the datatype svalue declared | |
107 | in the structure named by valueStruct. The datatype svalue | |
108 | is declared inside the structure named by valueStruct to deal | |
109 | with the scope of constructors. | |
110 | *) | |
111 | ||
112 | val printTypes = fn (VALS {say,sayln,term,nonterm,symbolToString,pos_type, | |
113 | arg_type, | |
114 | termvoid,ntvoid,saydot,hasType,start, | |
115 | pureActions,...}, | |
116 | NAMES {valueStruct,...},symbolType) => | |
117 | let val prConstr = fn (symbol,SOME s) => | |
118 | say (" | " ^ (symbolName symbol) ^ " of " ^ | |
119 | (if pureActions then "" else "unit -> ") ^ | |
120 | " (" ^ tyName s ^ ")" | |
121 | ) | |
122 | | _ => () | |
123 | in sayln "local open Header in"; | |
124 | sayln ("type pos = " ^ pos_type); | |
125 | sayln ("type arg = " ^ arg_type); | |
126 | sayln ("structure " ^ valueStruct ^ " = "); | |
127 | sayln "struct"; | |
128 | say ("datatype svalue = " ^ termvoid ^ " | " ^ ntvoid ^ " of" ^ | |
129 | (if pureActions then "" else " unit -> ") ^ " unit"); | |
130 | app prConstr term; | |
131 | app prConstr nonterm; | |
132 | sayln "\nend"; | |
133 | sayln ("type svalue = " ^ valueStruct ^ ".svalue"); | |
134 | say "type result = "; | |
135 | case symbolType (NONTERM start) | |
136 | of NONE => sayln "unit" | |
137 | | SOME t => (say (tyName t); sayln ""); | |
138 | sayln "end" | |
139 | end | |
140 | ||
141 | (* function to print Tokens{n} structure *) | |
142 | ||
143 | val printTokenStruct = | |
144 | fn (VALS {say, sayln, termToString, hasType,termvoid,terms, | |
145 | pureActions,tokenInfo,...}, | |
146 | NAMES {miscStruct,tableStruct,valueStruct, | |
147 | tokenStruct,tokenSig,dataStruct,...}) => | |
148 | (sayln ("structure " ^ tokenStruct ^ " : " ^ tokenSig ^ " ="); | |
149 | sayln "struct"; | |
150 | (case tokenInfo of | |
151 | NONE => () | |
152 | | _ => sayln ("open "^dataStruct^".Header")); | |
153 | sayln ("type svalue = " ^ dataStruct ^ ".svalue"); | |
154 | sayln "type ('a,'b) token = ('a,'b) Token.token"; | |
155 | let val f = fn term as T i => | |
156 | (say "fun "; say (termToString term); | |
157 | say " ("; | |
158 | if (hasType (TERM term)) then say "i," else (); | |
159 | say "p1,p2) = Token.TOKEN ("; | |
160 | say (dataStruct ^ "." ^ tableStruct ^ ".T "); | |
161 | say (Int.toString i); | |
162 | say ",("; | |
163 | say (dataStruct ^ "." ^ valueStruct ^ "."); | |
164 | if (hasType (TERM term)) then | |
165 | (say (termToString term); | |
166 | if pureActions then say " i" | |
167 | else say " (fn () => i)") | |
168 | else say termvoid; | |
169 | say ","; | |
170 | sayln "p1,p2))") | |
171 | in app f terms | |
172 | end; | |
173 | sayln "end") | |
174 | ||
175 | (* function to print signatures out - takes print function which | |
176 | does not need to insert line breaks *) | |
177 | ||
178 | val printSigs = fn (VALS {term,tokenInfo,...}, | |
179 | NAMES {tokenSig,tokenStruct,miscSig, | |
180 | dataStruct, dataSig, ...}, | |
181 | say) => | |
182 | say ("signature " ^ tokenSig ^ " =\nsig\n"^ | |
183 | (case tokenInfo of NONE => "" | SOME s => (s^"\n"))^ | |
184 | "type ('a,'b) token\ntype svalue\n" ^ | |
185 | (List.foldr (fn ((s,ty),r) => String.concat [ | |
186 | "val ", symbolName s, | |
187 | (case ty | |
188 | of NONE => ": " | |
189 | | SOME l => ": (" ^ (tyName l) ^ ") * "), | |
190 | " 'a * 'a -> (svalue,'a) token\n", r]) "" term) ^ | |
191 | "end\nsignature " ^ miscSig ^ | |
192 | "=\nsig\nstructure Tokens : " ^ tokenSig ^ | |
193 | "\nstructure " ^ dataStruct ^ ":" ^ dataSig ^ | |
194 | "\nsharing type " ^ dataStruct ^ | |
195 | ".Token.token = Tokens.token\nsharing type " ^ | |
196 | dataStruct ^ ".svalue = Tokens.svalue\nend\n") | |
197 | ||
198 | (* function to print structure for error correction *) | |
199 | ||
200 | val printEC = fn (keyword : term list, | |
201 | preferred_change : (term list * term list) list, | |
202 | noshift : term list, | |
203 | value : (term * string) list, | |
204 | VALS {termToString, say,sayln,terms,saydot,hasType, | |
205 | termvoid,pureActions,...}, | |
206 | NAMES {ecStruct,tableStruct,valueStruct,...}) => | |
207 | let | |
208 | ||
209 | val sayterm = fn (T i) => (say "(T "; say (Int.toString i); say ")") | |
210 | ||
211 | val printBoolCase = fn ( l : term list) => | |
212 | (say "fn "; | |
213 | app (fn t => (sayterm t; say " => true"; say " | ")) l; | |
214 | sayln "_ => false") | |
215 | ||
216 | val printTermList = fn (l : term list) => | |
217 | (sayln "nil"; app (fn t => (say " $$ "; sayterm t)) (rev l)) | |
218 | ||
219 | ||
220 | fun printChange () = | |
221 | (sayln "val preferred_change : (term list * term list) list = "; | |
222 | app (fn (d,i) => | |
223 | (say"("; printTermList d; say ","; printTermList i; | |
224 | sayln ")::" | |
225 | ) | |
226 | ) preferred_change; | |
227 | sayln "nil") | |
228 | ||
229 | val printErrValues = fn (l : (term * string) list) => | |
230 | (sayln "local open Header in"; | |
231 | sayln "val errtermvalue="; | |
232 | say "fn "; | |
233 | app (fn (t,s) => | |
234 | (sayterm t; say " => "; | |
235 | saydot valueStruct; say (termToString t); | |
236 | say "("; | |
237 | if pureActions then () else say "fn () => "; | |
238 | say "("; say s; say "))"; | |
239 | sayln " | " | |
240 | ) | |
241 | ) l; | |
242 | say "_ => "; | |
243 | say (valueStruct ^ "."); | |
244 | sayln termvoid; sayln "end") | |
245 | ||
246 | ||
247 | val printNames = fn () => | |
248 | let val f = fn term => ( | |
249 | sayterm term; say " => "; | |
250 | sayln (String.concat["\"", termToString term, "\""]); | |
251 | say " | ") | |
252 | in (sayln "val showTerminal ="; | |
253 | say "fn "; | |
254 | app f terms; | |
255 | sayln "_ => \"bogus-term\"") | |
256 | end | |
257 | ||
258 | val ecTerms = | |
259 | List.foldr (fn (t,r) => | |
260 | if hasType (TERM t) orelse List.exists (fn (a,_)=>a=t) value | |
261 | then r | |
262 | else t::r) | |
263 | [] terms | |
264 | ||
265 | in say "structure "; | |
266 | say ecStruct; | |
267 | sayln "="; | |
268 | sayln "struct"; | |
269 | say "open "; | |
270 | sayln tableStruct; | |
271 | sayln "infix 5 $$"; | |
272 | sayln "fun x $$ y = y::x"; | |
273 | sayln "val is_keyword ="; | |
274 | printBoolCase keyword; | |
275 | printChange(); | |
276 | sayln "val noShift = "; | |
277 | printBoolCase noshift; | |
278 | printNames (); | |
279 | printErrValues value; | |
280 | say "val terms : term list = "; | |
281 | printTermList ecTerms; | |
282 | sayln "end" | |
283 | end | |
284 | ||
285 | val printAction = fn (rules, | |
286 | VALS {hasType,say,sayln,fmtPos,termvoid,ntvoid, | |
287 | symbolToString,saydot,start,pureActions,...}, | |
288 | NAMES {actionsStruct,valueStruct,tableStruct,arg,...}) => | |
289 | let val printAbsynRule = Absyn.printRule(say,sayln,fmtPos) | |
290 | val is_nonterm = fn (NONTERM i) => true | _ => false | |
291 | val numberRhs = fn r => | |
292 | List.foldl (fn (e,(r,table)) => | |
293 | let val num = case SymbolTable.find(e,table) | |
294 | of SOME i => i | |
295 | | NONE => 1 | |
296 | in ((e,num,hasType e orelse is_nonterm e)::r, | |
297 | SymbolTable.insert((e,num+1),table)) | |
298 | end) (nil,SymbolTable.empty) r | |
299 | ||
300 | val saySym = symbolToString | |
301 | ||
302 | val printCase = fn (i:int, r as {lhs=lhs as (NT lhsNum),prec, | |
303 | rhs,code,rulenum}) => | |
304 | ||
305 | (* mkToken: Build an argument *) | |
306 | ||
307 | let open Absyn | |
308 | val mkToken = fn (sym,num : int,typed) => | |
309 | let val symString = symbolToString sym | |
310 | val symNum = symString ^ (Int.toString num) | |
311 | in PTUPLE[WILD, | |
312 | PTUPLE[if not (hasType sym) then | |
313 | (if is_nonterm sym then | |
314 | PAPP(valueStruct^"."^ntvoid, | |
315 | PVAR symNum) | |
316 | else WILD) | |
317 | else | |
318 | PAPP(valueStruct^"."^symString, | |
319 | if num=1 andalso pureActions | |
320 | then AS(symNum,PVAR symString) | |
321 | else PVAR symNum), | |
322 | if num=1 then AS(symString^"left", | |
323 | PVAR(symNum^"left")) | |
324 | else PVAR(symNum^"left"), | |
325 | if num=1 then AS(symString^"right", | |
326 | PVAR(symNum^"right")) | |
327 | else PVAR(symNum^"right")]] | |
328 | end | |
329 | ||
330 | val numberedRhs = #1 (numberRhs rhs) | |
331 | ||
332 | (* construct case pattern *) | |
333 | ||
334 | val pat = PTUPLE[PINT i,PLIST(map mkToken numberedRhs, | |
335 | SOME (PVAR "rest671"))] | |
336 | ||
337 | (* remove terminals in argument list w/o types *) | |
338 | ||
339 | val argsWithTypes = | |
340 | List.foldr (fn ((_,_,false),r) => r | |
341 | | (s as (_,_,true),r) => s::r) nil numberedRhs | |
342 | ||
343 | (* construct case body *) | |
344 | ||
345 | val defaultPos = EVAR "defaultPos" | |
346 | val resultexp = EVAR "result" | |
347 | val resultpat = PVAR "result" | |
348 | val code = CODE code | |
349 | val rest = EVAR "rest671" | |
350 | ||
351 | val body = | |
352 | LET([VB(resultpat, | |
353 | EAPP(EVAR(valueStruct^"."^ | |
354 | (if hasType (NONTERM lhs) | |
355 | then saySym(NONTERM lhs) | |
356 | else ntvoid)), | |
357 | if pureActions then code | |
358 | else if argsWithTypes=nil then FN(WILD,code) | |
359 | else | |
360 | FN(WILD, | |
361 | let val body = | |
362 | LET(map (fn (sym,num:int,_) => | |
363 | let val symString = symbolToString sym | |
364 | val symNum = symString ^ Int.toString num | |
365 | in VB(if num=1 then | |
366 | AS(symString,PVAR symNum) | |
367 | else PVAR symNum, | |
368 | EAPP(EVAR symNum,UNIT)) | |
369 | end) (rev argsWithTypes), | |
370 | code) | |
371 | in if hasType (NONTERM lhs) then | |
372 | body else SEQ(body,UNIT) | |
373 | end)))], | |
374 | ETUPLE[EAPP(EVAR(tableStruct^".NT"),EINT(lhsNum)), | |
375 | case rhs | |
376 | of nil => ETUPLE[resultexp,defaultPos,defaultPos] | |
377 | | r =>let val (rsym,rnum,_) = hd(numberedRhs) | |
378 | val (lsym,lnum,_) = hd(rev numberedRhs) | |
379 | in ETUPLE[resultexp, | |
380 | EVAR (symbolToString lsym ^ | |
381 | Int.toString lnum ^ "left"), | |
382 | EVAR (symbolToString rsym ^ | |
383 | Int.toString rnum ^ "right")] | |
384 | end, | |
385 | rest]) | |
386 | in printAbsynRule (RULE(pat,body)) | |
387 | end | |
388 | ||
389 | val prRules = fn () => | |
390 | (sayln "fn (i392,defaultPos,stack,"; | |
391 | say " ("; say arg; sayln "):arg) =>"; | |
392 | sayln "case (i392,stack)"; | |
393 | say "of "; | |
394 | app (fn (rule as {rulenum,...}) => | |
395 | (printCase(rulenum,rule); say "| ")) rules; | |
396 | sayln "_ => raise (mlyAction i392)") | |
397 | ||
398 | in say "structure "; | |
399 | say actionsStruct; | |
400 | sayln " ="; | |
401 | sayln "struct "; | |
402 | sayln "exception mlyAction of int"; | |
403 | sayln "local open Header in"; | |
404 | sayln "val actions = "; | |
405 | prRules(); | |
406 | sayln "end"; | |
407 | say "val void = "; | |
408 | saydot valueStruct; | |
409 | sayln termvoid; | |
410 | say "val extract = "; | |
411 | say "fn a => (fn "; | |
412 | saydot valueStruct; | |
413 | if hasType (NONTERM start) | |
414 | then say (symbolToString (NONTERM start)) | |
415 | else say "ntVOID"; | |
416 | sayln " x => x"; | |
417 | sayln "| _ => let exception ParseInternal"; | |
418 | say "\tin raise ParseInternal end) a "; | |
419 | sayln (if pureActions then "" else "()"); | |
420 | sayln "end" | |
421 | end | |
422 | ||
423 | val make_parser = fn ((header, | |
424 | DECL {eop,change,keyword,nonterm,prec, | |
425 | term, control,value} : declData, | |
426 | rules : rule list),spec,error : pos -> string -> unit, | |
427 | wasError : unit -> bool) => | |
428 | let | |
429 | val verbose = List.exists (fn VERBOSE=>true | _ => false) control | |
430 | val defaultReductions = not (List.exists (fn NODEFAULT=>true | _ => false) control) | |
431 | val pos_type = | |
432 | let fun f nil = NONE | |
433 | | f ((POS s)::r) = SOME s | |
434 | | f (_::r) = f r | |
435 | in f control | |
436 | end | |
437 | val start = | |
438 | let fun f nil = NONE | |
439 | | f ((START_SYM s)::r) = SOME s | |
440 | | f (_::r) = f r | |
441 | in f control | |
442 | end | |
443 | val name = | |
444 | let fun f nil = NONE | |
445 | | f ((PARSER_NAME s)::r) = SOME s | |
446 | | f (_::r) = f r | |
447 | in f control | |
448 | end | |
449 | val header_decl = | |
450 | let fun f nil = NONE | |
451 | | f ((FUNCTOR s)::r) = SOME s | |
452 | | f (_::r) = f r | |
453 | in f control | |
454 | end | |
455 | ||
456 | val token_sig_info_decl = | |
457 | let fun f nil = NONE | |
458 | | f ((TOKEN_SIG_INFO s)::_) = SOME s | |
459 | | f (_::r) = f r | |
460 | in f control | |
461 | end | |
462 | ||
463 | val arg_decl = | |
464 | let fun f nil = ("()","unit") | |
465 | | f ((PARSE_ARG s)::r) = s | |
466 | | f (_::r) = f r | |
467 | in f control | |
468 | end | |
469 | ||
470 | val noshift = | |
471 | let fun f nil = nil | |
472 | | f ((NSHIFT s)::r) = s | |
473 | | f (_::r) = f r | |
474 | in f control | |
475 | end | |
476 | ||
477 | val pureActions = | |
478 | let fun f nil = false | |
479 | | f ((PURE)::r) = true | |
480 | | f (_::r) = f r | |
481 | in f control | |
482 | end | |
483 | ||
484 | val term = | |
485 | case term | |
486 | of NONE => (error {line = 1, col = 0} "missing %term definition"; nil) | |
487 | | SOME l => l | |
488 | ||
489 | val nonterm = | |
490 | case nonterm | |
491 | of NONE => (error {line = 1, col = 0} "missing %nonterm definition"; nil) | |
492 | | SOME l => l | |
493 | ||
494 | val pos_type = | |
495 | case pos_type | |
496 | of NONE => (error {line = 1, col = 0} "missing %pos definition"; "") | |
497 | | SOME l => l | |
498 | ||
499 | ||
500 | val termHash = | |
501 | List.foldr (fn ((symbol,_),table) => | |
502 | let val name = symbolName symbol | |
503 | in if SymbolHash.exists(name,table) then | |
504 | (error (symbolPos symbol) | |
505 | ("duplicate definition of " ^ name ^ " in %term"); | |
506 | table) | |
507 | else SymbolHash.add(name,table) | |
508 | end) SymbolHash.empty term | |
509 | ||
510 | val isTerm = fn name => SymbolHash.exists(name,termHash) | |
511 | ||
512 | val symbolHash = | |
513 | List.foldr (fn ((symbol,_),table) => | |
514 | let val name = symbolName symbol | |
515 | in if SymbolHash.exists(name,table) then | |
516 | (error (symbolPos symbol) | |
517 | (if isTerm name then | |
518 | name ^ " is defined as a terminal and a nonterminal" | |
519 | else | |
520 | "duplicate definition of " ^ name ^ " in %nonterm"); | |
521 | table) | |
522 | else SymbolHash.add(name,table) | |
523 | end) termHash nonterm | |
524 | ||
525 | fun makeUniqueId s = | |
526 | if SymbolHash.exists(s,symbolHash) then makeUniqueId (s ^ "'") | |
527 | else s | |
528 | ||
529 | val _ = if wasError() then raise Semantic else () | |
530 | ||
531 | val numTerms = SymbolHash.size termHash | |
532 | val numNonterms = SymbolHash.size symbolHash - numTerms | |
533 | ||
534 | val symError = fn sym => fn err => fn symbol => | |
535 | error (symbolPos symbol) | |
536 | (symbolName symbol^" in "^err^" is not defined as a " ^ sym) | |
537 | ||
538 | val termNum : string -> Header.symbol -> term = | |
539 | let val termError = symError "terminal" | |
540 | in fn stmt => | |
541 | let val stmtError = termError stmt | |
542 | in fn symbol => | |
543 | case SymbolHash.find(symbolName symbol,symbolHash) | |
544 | of NONE => (stmtError symbol; T ~1) | |
545 | | SOME i => T (if i<numTerms then i | |
546 | else (stmtError symbol; ~1)) | |
547 | end | |
548 | end | |
549 | ||
550 | val nontermNum : string -> Header.symbol -> nonterm = | |
551 | let val nontermError = symError "nonterminal" | |
552 | in fn stmt => | |
553 | let val stmtError = nontermError stmt | |
554 | in fn symbol => | |
555 | case SymbolHash.find(symbolName symbol,symbolHash) | |
556 | of NONE => (stmtError symbol; NT ~1) | |
557 | | SOME i => if i>=numTerms then NT (i-numTerms) | |
558 | else (stmtError symbol;NT ~1) | |
559 | end | |
560 | end | |
561 | ||
562 | val symbolNum : string -> Header.symbol -> Grammar.symbol = | |
563 | let val symbolError = symError "symbol" | |
564 | in fn stmt => | |
565 | let val stmtError = symbolError stmt | |
566 | in fn symbol => | |
567 | case SymbolHash.find(symbolName symbol,symbolHash) | |
568 | of NONE => (stmtError symbol; NONTERM (NT ~1)) | |
569 | | SOME i => if i>=numTerms then NONTERM(NT (i-numTerms)) | |
570 | else TERM(T i) | |
571 | end | |
572 | end | |
573 | ||
574 | (* map all symbols in the following values to terminals and check that | |
575 | the symbols are defined as terminals: | |
576 | ||
577 | eop : symbol list | |
578 | keyword: symbol list | |
579 | prec: (lexvalue * (symbol list)) list | |
580 | change: (symbol list * symbol list) list | |
581 | *) | |
582 | ||
583 | val eop = map (termNum "%eop") eop | |
584 | val keyword = map (termNum "%keyword") keyword | |
585 | val prec = map (fn (a,l) => | |
586 | (a,case a | |
587 | of LEFT => map (termNum "%left") l | |
588 | | RIGHT => map (termNum "%right") l | |
589 | | NONASSOC => map (termNum "%nonassoc") l | |
590 | )) prec | |
591 | val change = | |
592 | let val mapTerm = termNum "%prefer, %subst, or %change" | |
593 | in map (fn (a,b) => (map mapTerm a, map mapTerm b)) change | |
594 | end | |
595 | val noshift = map (termNum "%noshift") noshift | |
596 | val value = | |
597 | let val mapTerm = termNum "%value" | |
598 | in map (fn (a,b) => (mapTerm a,b)) value | |
599 | end | |
600 | val (rules,_) = | |
601 | let val symbolNum = symbolNum "rule" | |
602 | val nontermNum = nontermNum "rule" | |
603 | val termNum = termNum "%prec tag" | |
604 | in List.foldr | |
605 | (fn (RULE {lhs,rhs,code,prec},(l,n)) => | |
606 | ( {lhs=nontermNum lhs,rhs=map symbolNum rhs, | |
607 | code=code,prec=case prec | |
608 | of NONE => NONE | |
609 | | SOME t => SOME (termNum t), | |
610 | rulenum=n}::l,n-1)) | |
611 | (nil,length rules-1) rules | |
612 | end | |
613 | ||
614 | val _ = if wasError() then raise Semantic else () | |
615 | ||
616 | (* termToString: map terminals back to strings *) | |
617 | ||
618 | val termToString = | |
619 | let val data = Array.array(numTerms,"") | |
620 | val unmap = fn (symbol,_) => | |
621 | let val name = symbolName symbol | |
622 | in Array.update(data, | |
623 | case SymbolHash.find(name,symbolHash) of | |
624 | SOME i => i | |
625 | | NONE => raise Fail "termToString", | |
626 | name) | |
627 | end | |
628 | val _ = app unmap term | |
629 | in fn T i => | |
630 | if DEBUG andalso (i<0 orelse i>=numTerms) | |
631 | then "bogus-num" ^ (Int.toString i) | |
632 | else data sub i | |
633 | end | |
634 | ||
635 | val nontermToString = | |
636 | let val data = Array.array(numNonterms,"") | |
637 | val unmap = fn (symbol,_) => | |
638 | let val name = symbolName symbol | |
639 | in Array.update(data, | |
640 | case SymbolHash.find(name,symbolHash) of | |
641 | SOME i => i-numTerms | |
642 | | NONE => raise Fail "nontermToString", | |
643 | name) | |
644 | end | |
645 | val _ = app unmap nonterm | |
646 | in fn NT i => | |
647 | if DEBUG andalso (i<0 orelse i>=numNonterms) | |
648 | then "bogus-num" ^ (Int.toString i) | |
649 | else data sub i | |
650 | end | |
651 | ||
652 | (* create functions mapping terminals to precedence numbers and rules to | |
653 | precedence numbers. | |
654 | ||
655 | Precedence statements are listed in order of ascending (tighter binding) | |
656 | precedence in the specification. We receive a list composed of pairs | |
657 | containing the kind of precedence (left,right, or assoc) and a list of | |
658 | terminals associated with that precedence. The list has the same order as | |
659 | the corresponding declarations did in the specification. | |
660 | ||
661 | Internally, a tighter binding has a higher precedence number. We give | |
662 | precedences using multiples of 3: | |
663 | ||
664 | p+2 = right associative (force shift of symbol) | |
665 | p+1 = precedence for rule | |
666 | p = left associative (force reduction of rule) | |
667 | ||
668 | Nonassociative terminals are given also given a precedence of p+1. The | |
669 | table generator detects when the associativity of a nonassociative terminal | |
670 | is being used to resolve a shift/reduce conflict by checking if the | |
671 | precedences of the rule and the terminal are equal. | |
672 | ||
673 | A rule is given the precedence of its rightmost terminal *) | |
674 | ||
675 | val termPrec = | |
676 | let val precData = Array.array(numTerms, NONE : int option) | |
677 | val addPrec = fn termPrec => fn term as (T i) => | |
678 | case precData sub i | |
679 | of SOME _ => | |
680 | error {line = 1, col = 0} ("multiple precedences specified for terminal " ^ | |
681 | (termToString term)) | |
682 | | NONE => Array.update(precData,i,termPrec) | |
683 | val termPrec = fn ((LEFT,_) ,i) => i | |
684 | | ((RIGHT,_),i) => i+2 | |
685 | | ((NONASSOC,l),i) => i+1 | |
686 | val _ = List.foldl (fn (args as ((_,l),i)) => | |
687 | (app (addPrec (SOME (termPrec args))) l; i+3)) | |
688 | 0 prec | |
689 | in fn (T i) => | |
690 | if DEBUG andalso (i < 0 orelse i >= numTerms) then | |
691 | NONE | |
692 | else precData sub i | |
693 | end | |
694 | ||
695 | val elimAssoc = fn i => (i - (i mod 3) + 1) | |
696 | val rulePrec = | |
697 | let fun findRightTerm (nil,r) = r | |
698 | | findRightTerm (TERM t :: tail,r) = | |
699 | findRightTerm(tail,SOME t) | |
700 | | findRightTerm (_ :: tail,r) = findRightTerm(tail,r) | |
701 | in fn rhs => | |
702 | case findRightTerm(rhs,NONE) | |
703 | of NONE => NONE | |
704 | | SOME term => | |
705 | case termPrec term | |
706 | of SOME i => SOME (elimAssoc i) | |
707 | | a => a | |
708 | end | |
709 | ||
710 | val grammarRules = | |
711 | let val conv = fn {lhs,rhs,code,prec,rulenum} => | |
712 | {lhs=lhs,rhs =rhs,precedence= | |
713 | case prec | |
714 | of SOME t => (case termPrec t | |
715 | of SOME i => SOME(elimAssoc i) | |
716 | | a => a) | |
717 | | _ => rulePrec rhs, | |
718 | rulenum=rulenum} | |
719 | in map conv rules | |
720 | end | |
721 | ||
722 | (* get start symbol *) | |
723 | ||
724 | val start = | |
725 | case start | |
726 | of NONE => #lhs (hd grammarRules) | |
727 | | SOME name => | |
728 | nontermNum "%start" name | |
729 | ||
730 | val symbolType = | |
731 | let val data = Array.array(numTerms+numNonterms,NONE : ty option) | |
732 | fun unmap (symbol,ty) = | |
733 | Array.update(data, | |
734 | case SymbolHash.find(symbolName symbol,symbolHash) of | |
735 | SOME i => i | |
736 | | NONE => raise Fail "symbolType", | |
737 | ty) | |
738 | val _ = (app unmap term; app unmap nonterm) | |
739 | in fn NONTERM(NT i) => | |
740 | if DEBUG andalso (i<0 orelse i>=numNonterms) | |
741 | then NONE | |
742 | else data sub (i+numTerms) | |
743 | | TERM (T i) => | |
744 | if DEBUG andalso (i<0 orelse i>=numTerms) | |
745 | then NONE | |
746 | else data sub i | |
747 | end | |
748 | ||
749 | val symbolToString = | |
750 | fn NONTERM i => nontermToString i | |
751 | | TERM i => termToString i | |
752 | ||
753 | val grammar = GRAMMAR {rules=grammarRules, | |
754 | terms=numTerms,nonterms=numNonterms, | |
755 | eop = eop, start=start,noshift=noshift, | |
756 | termToString = termToString, | |
757 | nontermToString = nontermToString, | |
758 | precedence = termPrec} | |
759 | ||
760 | val name' = case name | |
761 | of NONE => "" | |
762 | | SOME s => symbolName s | |
763 | ||
764 | val names = NAMES {miscStruct=name' ^ "LrValsFun", | |
765 | valueStruct="MlyValue", | |
766 | tableStruct="LrTable", | |
767 | tokenStruct="Tokens", | |
768 | actionsStruct="Actions", | |
769 | ecStruct="EC", | |
770 | arg= #1 arg_decl, | |
771 | tokenSig = name' ^ "_TOKENS", | |
772 | miscSig = name' ^ "_LRVALS", | |
773 | dataStruct = "ParserData", | |
774 | dataSig = "PARSER_DATA"} | |
775 | ||
776 | val (table,stateErrs,corePrint,errs) = | |
777 | MakeTable.mkTable(grammar,defaultReductions) | |
778 | ||
779 | val entries = ref 0 (* save number of action table entries here *) | |
780 | ||
781 | in let val result = TextIO.openOut (spec ^ ".sml") | |
782 | val sigs = TextIO.openOut (spec ^ ".sig") | |
783 | val specFile = OS.Path.file spec | |
784 | val resultFile = specFile ^ ".sml" | |
785 | val line = ref 1 | |
786 | val col = ref 0 | |
787 | val pr = fn s => TextIO.output(result,s) | |
788 | val say = fn s => | |
789 | (CharVector.app (fn #"\n" => (line := !line + 1 ; col := 0) | |
790 | | _ => col := !col + 1) | |
791 | s | |
792 | ; pr s) | |
793 | val saydot = fn s => (say (s ^ ".")) | |
794 | val sayln = fn t => (say t; say "\n") | |
795 | fun fmtLineDir {line, col} path = | |
796 | String.concat ["(*#line ", Int.toString line, ".", | |
797 | Int.toString (col+1), " \"", path, "\"*)"] | |
798 | val fmtPos = | |
799 | fn NONE => (fmtLineDir {line = !line, col = 0} resultFile) ^ "\n" | |
800 | | SOME pos => fmtLineDir pos specFile | |
801 | val termvoid = makeUniqueId "VOID" | |
802 | val ntvoid = makeUniqueId "ntVOID" | |
803 | val hasType = fn s => case symbolType s | |
804 | of NONE => false | |
805 | | _ => true | |
806 | val terms = let fun f n = if n=numTerms then nil | |
807 | else (T n) :: f(n+1) | |
808 | in f 0 | |
809 | end | |
810 | val values = VALS {say=say,sayln=sayln,saydot=saydot,fmtPos=fmtPos, | |
811 | termvoid=termvoid, ntvoid = ntvoid, | |
812 | hasType=hasType, pos_type = pos_type, | |
813 | arg_type = #2 arg_decl, | |
814 | start=start,pureActions=pureActions, | |
815 | termToString=termToString, | |
816 | symbolToString=symbolToString,term=term, | |
817 | nonterm=nonterm,terms=terms, | |
818 | tokenInfo=token_sig_info_decl} | |
819 | ||
820 | val (NAMES {miscStruct,tableStruct,dataStruct,tokenSig,tokenStruct,dataSig,...}) = names | |
821 | in case header_decl | |
822 | of NONE => (say "functor "; say miscStruct; | |
823 | sayln "(structure Token : TOKEN)"; | |
824 | say " : sig structure "; | |
825 | say dataStruct; | |
826 | say " : "; sayln dataSig; | |
827 | say " structure "; | |
828 | say tokenStruct; say " : "; sayln tokenSig; | |
829 | sayln " end") | |
830 | | SOME s => say s; | |
831 | sayln " = "; | |
832 | sayln "struct"; | |
833 | sayln ("structure " ^ dataStruct ^ "="); | |
834 | sayln "struct"; | |
835 | sayln "structure Header = "; | |
836 | sayln "struct"; | |
837 | say (fmtPos (SOME {line = 1, col = 1})); | |
838 | sayln header; | |
839 | say (fmtPos NONE); | |
840 | sayln "end"; | |
841 | sayln "structure LrTable = Token.LrTable"; | |
842 | sayln "structure Token = Token"; | |
843 | sayln "local open LrTable in "; | |
844 | entries := PrintStruct.makeStruct{table=table,print=say, | |
845 | name = "table", | |
846 | verbose=verbose}; | |
847 | sayln "end"; | |
848 | printTypes(values,names,symbolType); | |
849 | printEC (keyword,change,noshift,value,values,names); | |
850 | printAction(rules,values,names); | |
851 | sayln "end"; | |
852 | printTokenStruct(values,names); | |
853 | sayln "end"; | |
854 | printSigs(values,names,fn s => TextIO.output(sigs,s)); | |
855 | TextIO.closeOut sigs; | |
856 | TextIO.closeOut result; | |
857 | MakeTable.Errs.printSummary (fn s => TextIO.output(TextIO.stdOut,s)) errs | |
858 | end; | |
859 | if verbose then | |
860 | let val f = TextIO.openOut (spec ^ ".desc") | |
861 | val say = fn s=> TextIO.output(f,s) | |
862 | val printRule = | |
863 | let val rules = Array.fromList grammarRules | |
864 | in fn say => | |
865 | let val prRule = fn {lhs,rhs,precedence,rulenum} => | |
866 | ((say o nontermToString) lhs; say " : "; | |
867 | app (fn s => (say (symbolToString s); say " ")) rhs) | |
868 | in fn i => prRule (rules sub i) | |
869 | end | |
870 | end | |
871 | in Verbose.printVerbose | |
872 | {termToString=termToString,nontermToString=nontermToString, | |
873 | table=table, stateErrs=stateErrs,errs = errs,entries = !entries, | |
874 | print=say, printCores=corePrint,printRule=printRule}; | |
875 | TextIO.closeOut f | |
876 | end | |
877 | else () | |
878 | end | |
879 | ||
880 | val parseGen = fn spec => | |
881 | let val (result,inputSource) = ParseGenParser.parse spec | |
882 | in make_parser(getResult result,spec,Header.error inputSource, | |
883 | errorOccurred inputSource) | |
884 | end | |
885 | end; |