Debian Codegraph @

ipl/packs/ibpag2/iiglrpar.lib

raw
1 ############################################################################
2 #
3 # Name: iiglrpar.lib
4 #
5 # Title: Quasi-GLR parser code
6 #
7 # Author: Richard L. Goerwitz
8 #
9 # Version: 1.20
10 #
11 ############################################################################
12 #
13 # This file contains quasi-GLR parser code for use by Ibpag2's
14 # output. See below on what I mean by "quasi-GLR." Entry point is
15 # iiparse(infile, fail_on_error). Infile is the stream from which
16 # input is to be taken. Infile is passed as argument 1 to the
17 # user-supplied lexical analyzer, iilex_module() (where _module is
18 # the string supplied with the -m option to Ibpag2). If
19 # fail_on_error is nonnull, the parser, iiparse, will fail on errors,
20 # rather than abort. Iiparse() returns the top element on its value
21 # stack on a successful parse (which can be handy).
22 #
23 # Iilex_module() must suspend integers for tokens and may also set
24 # iilval_module to the actual string values. Tokens -2, -1, and 0
25 # are reserved. -2 is epsilon, and -1 is error. 0 is EOF, and is
26 # automatically appended to the token stream when iilex_module, the
27 # tokenizer, fails. These values should not normally be returned by
28 # the analyzer. In general, it is a good idea to $include
29 # iilex_module from your Ibpag2 source files, so that it can use the
30 # symbolic %token names declared in the original Ibpag2 source file.
31 # As implied above ("suspend"), iilex_module must be a generator,
32 # failing on EOF.
33 #
34 # If desired, you may include your own error-handling routine. It
35 # must be called iiparse_module (where _module is once again the
36 # module name supplied to ibpag2 via the -m option). The global
37 # variable line_number_module is automatically defined below, so a
38 # typical arrangement would be for the lexical analyzer to initialize
39 # line_number_module to 0, and increment by 1 for each line read.
40 # The error handler, iierror_module() can then display this variable.
41 # Note that the error handler should accept a single string argument
42 # (set by iiparse to describe the token on the input stream when the
43 # error was encountered).
44 #
45 # I label this parser "GLR" because it does support multiple parallel
46 # parsers (like GLR parsers are supposed to). I use the qualifier
47 # "quasi," though, because it does not use a graph-structured stack.
48 # Instead it copies both value and state stacks (in fact, the whole
49 # parser environment) when creating new automata to handle
50 # alternative parse paths. Slower, yes. But it enables the user to
51 # use almost precisely the action and input format that is used for
52 # the standard parser.
53 #
54 # Note that iiparse(), as implemented here, may suspend multiple
55 # results. So be sure to call it in some context where multiple
56 # results can be used (e.g. every parse := iiparse(&input, 1), or the
57 # like). Note also that when new parser "edges" get created, a
58 # rather cumbersome recursive copy routine is used. Sorry, but it's
59 # necessary to prevent unintended side-effects.
60 #
61 ############################################################################
62 #
63 # The algorithm:
64 #
65 # A = list of active parsers needing action lookup
66 # S = list of parsers to be shifted
67 # R = list of parsers to be reduced
68 # B = list of parsers that "choked"
69 #
70 # for every token on the input stream
71 # begin
72 # until length of R = 0 and length of A = 0
73 # begin
74 # - pop successive parsers off of A, and placing them in S,
75 # R, or B, depending on parse table directives; suspend a
76 # result for each parser that has reached an accepting
77 # state
78 # - pop successive parsers off of R, reducing them, and
79 # placing them back in A; perform the action code
80 # associated with each reduction
81 # end
82 # - pop successive parsers off of S, shifting them, and placing
83 # them back in A; mark recovering parsers as recovered when
84 # they have successfully shifted three tokens
85 # if length of A = 0 and token not = EOF
86 # then
87 # - initiate error recovery on the parsers in B, i.e. for
88 # each parser in B that is not already recovering, pop its
89 # stack until error (-1) can legally be shifted, then shift
90 # error, mark the parser as recovering from an error, and
91 # place it back in A; if the parser is already recovering,
92 # discard the current token
93 # else
94 # - clobber the parsers in B
95 # end
96 # end
97 #
98 # Note that when a given active parser in A is being classified
99 # as needing a reduction, shift, suspension, or entry into the error
100 # list (B), more than one action may apply due to ambiguity in the
101 # grammar. At such points, the parser environment is duplicated,
102 # once for each alternative pathway, and each of the new parsers is
103 # then entered into the appropriate list (R or S; if accept is an
104 # alternative, the classification routine suspends).
105 #
106 # Note also that when performing the action code associated with
107 # reductions, parsers may be reclassified as erroneous, accepting,
108 # etc. via "semantic" directives like IIERROR and IIACCEPT. See the
109 # README file. Multiple-result action code will cause new parser
110 # threads to be created, just as ambiguities in the grammar do within
111 # the classification routine above.
112 #
113 #############################################################################
114 #
115 # See also: ibpag2.icn, iiparse.icn
116 #
117 ############################################################################
118
119 $$line 119 "iiglrpar.lib"
120
121 $$ifndef IIDEBUG
122 $$define $iidebug 1
123 $$define show_new_forest 1
124 $$endif # not IIDEBUG
125
126 # These defines are output by Ibpag2 ahead of time (with the module
127 # name appended, if need be):
128 #
129 # IIERROR
130 # IIACCEPT
131 # iiprune - GLR mode only
132 # iiisolate - GLR mode only
133 # iierrok
134 # iiclearin
135
136 # Parser environment + lookahead and pending action field.
137 #
138 record $ib_pe(state_stack, value_stack, action, errors,
139 recover_shifts, discards, clearin)
140
141 # Warning! If you change the name of the value stack, change it also
142 # in ibreader.icn, procedure write_action_as_procedure().
143 #
144 global $iilval, $line_number, $state_stack, $value_stack,
145 $iidirective, $ttbl, $errors, $discard_token
146
147 #
148 # iiparse: file x anything -> ?s (a generator)
149 # (stream, fail_on_error) -> ?
150 #
151 # Where stream is an open file, where fail_on_error is a switch
152 # that (if nonnull) tells the iiparse to fail, rather than abort,
153 # on error, and where ?s represent the user-defined results of a
154 # completed parse of file, from the current location up to the
155 # point where the parser executes an "accept" action. Note that
156 # iiparse, as implemented here, is a generator.
157 #
158 procedure $iiparse(stream, fail_on_error)
159
160 local token, next_token, actives, reducers, shifters, barfers
161 #global ttbl, errors
162 static atbl
163 initial {
164 $iidirective := ""
165 atbl := $atbl_insertion_point
166 $ttbl := $ttbl_insertion_point
167 $$line 166 "iiglrpar.lib"
168 \$iilex | stop("no iilex tokenizer defined")
169 }
170
171 actives := [ $ib_pe([1], [], &null, 0) ]
172 $state_stack := actives[1].state_stack
173 $value_stack := actives[1].value_stack
174 $errors := actives[1].errors
175 reducers := list()
176 shifters := list()
177 # I get tired of bland error code. We'll call the list of
178 # parsers in an error state "barfers" :-).
179 barfers := list()
180
181 next_token := create $iilex(stream, fail_on_error) | 0
182
183 token := @next_token
184 #
185 # After this ^, new tokens are read in near the end of the repeat
186 # loop. None is read in on an error, since then we will try again
187 # on the token that caused the error.
188 #
189 repeat {
190 until *actives = *reducers = 0
191 do {
192
193 # Prune out parsers that are doing the same thing as some
194 # other parser.
195 #
196 $$ifdef AUTO_PRUNE
197 auto_prune(actives)
198 $$endif
199
200 # Suspends $value_stack[1] on accept actions. Otherwise,
201 # puts parsers that need shifting into the shifters list,
202 # parsers that need reducing into the reducers list, and
203 # error-state parsers into the barfers list. Creates new
204 # parser environments as needed.
205 #
206 suspend $ib_action(atbl, token, actives, shifters,
207 reducers, barfers)
208
209 # Perform reductions. If instructed via the iiaccept
210 # macro, simulate an accept action, and suspend with a
211 # result.
212 #
213 suspend $perform_reductions(token, actives, shifters,
214 reducers, barfers)
215 }
216
217 # Shift token for every parser in the shifters list. This
218 # will create a bunch of new active parsers.
219 #
220 $perform_shifts(token, actives, shifters)
221 #
222 # If we get to here and have no actives, and we're not at the
223 # end of the input stream, then we are at an error impasse.
224 # Do formal error recovery.
225 #
226 if *actives = 0 & token ~=== 0 then {
227 suspend $perform_barfs(atbl, token, actives, barfers,fail_on_error)
228 #
229 # Perform_barfs sets discard_token if recovery was
230 # unsuccessful on the last token, and it needs discarding.
231 #
232 if \$discard_token := &null then
233 token := @next_token | break
234 #
235 # If there *still* aren't any active parsers, we've
236 # reached an impasse (or there are no error productions).
237 # Abort.
238 #
239 if *actives = 0 then {
240 if \fail_on_error then fail
241 else stop()
242 }
243 }
244 else {
245 #
246 # Parsers in an error state should be weeded out, since if
247 # we get to here, we have some valid parsers still going.
248 # I.e. only use them if there are *no* actives (see above).
249 #
250 $$ifdef IIDEBUG
251 write(&errout, "+++ pruning ", *barfers, " erroneous parsers")
252 while parser := pop(barfers)
253 do $iidebug("p", token, &null, parser)
254 $$else
255 while pop(barfers)
256 $$endif #IIDEBUG
257 #
258 # Get the next token. Only do this if we have active
259 # parsers not recovering from an error, i.e., if we're here.
260 #
261 token := @next_token | break
262 }
263 }
264
265 end
266
267
268 #
269 # ib_action
270 #
271 procedure $ib_action(atbl, token, actives, shifters, reducers,
272 barfers)
273
274 local a, act, num, parser, new_parser
275
276 # While there is an active parser, take it off the actives list,
277 # and...
278 while parser := pop(actives) do {
279
280 # ...check for a valid action (if none, then there is an
281 # error; put it into the barfers list).
282 #
283 if a := \ (\atbl[token])[parser.state_stack[1]]
284 then {
285 a ? {
286 # Keep track of how many actions we've seen.
287 num := 0
288
289 # Snip off successive actions. If there's no
290 # ambiguity, there will be only one action, & no
291 # additional parser environments will be created.
292 #
293 while {
294 $$ifdef COMPRESSED_TABLES
295 # "\x80" is the accept action; uncompress_action
296 # does its own move()ing
297 act := $uncompress_action()
298 $$else
299 act := ="a" | {
300 tab(any('sr')) || tab(upto('.<')) ||
301 ((="<" || tab(find(">")+1)) | =".") ||
302 tab(many(&digits))
303 }
304 $$endif #COMPRESSED TABLES
305 }
306 do {
307 # New parser environment only needed for num > 1.
308 #
309 if (num +:= 1) > 1 then {
310 new_parser := $fullcopy(parser)
311 show_new_forest("=== table conflict; new parser",
312 actives, shifters, reducers, barfers, new_parser)
313 }
314 else new_parser := parser
315 new_parser.action := act
316
317 # Classify the action as s, r, or a, and place i
318 # the appropriate list (or suspend a result if a).
319 #
320 case act[1] of {
321 "s" : put(shifters, new_parser)
322 "r" : put(reducers, new_parser)
323 "a" : {
324 $iidebug("a", token, ruleno, parser)
325 suspend parser.value_stack[1]
326 }
327 }
328 }
329 }
330 }
331 else {
332 #
333 # Error. Parser will get garbage collected before another
334 # token is read from iilex, unless the parsers all fail -
335 # in which case, error recovery will be tried.
336 #
337 $iidebug("e", token, &null, parser)
338 put(barfers, parser)
339 }
340 }
341
342 end
343
344
345 #
346 # perform_reductions
347 #
348 procedure $perform_reductions(token, actives, shifters, reducers, barfers)
349
350 local parser, ruleno, newsym, rhsize, arglist, result, num,
351 new_parser, tmp, p
352 static gtbl
353 initial {
354 gtbl := $gtbl_insertion_point
355 $$line 336 "iiglrpar.lib"
356 }
357
358 while parser := get(reducers)
359 do {
360
361 # Set up global state and value stacks, so that the action
362 # code can access them.
363 #
364 $state_stack := parser.state_stack
365 $value_stack := parser.value_stack
366 $errors := parser.errors
367
368 # Finally, perform the given action:
369 #
370 parser.action ? {
371 #
372 # Reduce action format, e.g. r1<S>2 = reduce by rule 1
373 # (LHS = S, RHS length = 2).
374 #
375 move(1)
376 ruleno := integer(1(tab(find("<")), move(1)))
377 newsym := 1(tab(find(">")), move(1))
378 rhsize := integer(tab(many(&digits)))
379 arglist := []
380 every 1 to rhsize do {
381 pop($state_stack)
382 push(arglist, pop($value_stack))
383 }
384 # Gtbl is "backwards," i.e. token first, state second.
385 # The value produced is the "goto" state.
386 #
387 push($state_stack, gtbl[newsym][$state_stack[1]])
388 #
389 # The actions are in procedures having the same name as
390 # the number of their rule, bracketed by underscores, &
391 # followed by the current module name. If there is such a
392 # procedure associated with the current reduce action,
393 # call it.
394 #
395 if func := proc("_" || ruleno || "_" || $module)
396 then {
397 num := 0
398 #
399 # For every valid result from the action code for the
400 # current reduction, create a new parser if need be
401 # (i.e. if num > 1), and check iidirective. Push the
402 # result onto the stack of the new parser & put the
403 # new parser into the actives list.
404 #
405 every result := func!arglist do {
406 # For all but the first result, create a new parser.
407 if (num +:= 1) > 1 then {
408 new_parser := $fullcopy(parser)
409 pop(new_parser.value_stack) # take off pushed result
410 show_new_forest("=== multi-result action; new parser",
411 actives, shifters, reducers, barfers, new_parser)
412 }
413 else new_parser := parser
414 #
415 # IIERROR, IIACCEPT, iierrok, iiisolate, and iiprune
416 # are all implemented using a search through a global
417 # iidirective variable; see the $defines described
418 # above.
419 #
420 tmp := $iidirective
421 $iidirective := ""
422 if *tmp > 0 then {
423 if find("clearin", tmp) then {
424 # see perform_shifts() below
425 new_parser.clearin := 1
426 }
427 if find("error", tmp) then {
428 $iidebug("e", token, ruleno, new_parser)
429 put(barfers, new_parser)
430 next
431 }
432 if find("errok", tmp) then {
433 new_parser.recover_shifts := &null
434 new_parser.discards := 0
435 }
436 if find("prune", tmp) then {
437 # Garden path.
438 $iidebug("p", token, ruleno, new_parser)
439 break next
440 }
441 if find("isolate", tmp) then {
442 # Prune all but the current parser.
443 $$ifdef IIDEBUG
444 write(&errout, "+++ isolating by pruning")
445 while p := pop(actives) do
446 $iidebug("p", token, ruleno, p)
447 while p := pop(reducers) do
448 $iidebug("p", token, ruleno, p)
449 while p := pop(shifters) do
450 $iidebug("p", token, ruleno, p)
451 while p := pop(barfers) do
452 $iidebug("p", token, ruleno, p)
453 $$else
454 while pop(actives)
455 while pop(reducers)
456 while pop(shifters)
457 while pop(barfers)
458 $$endif #IIDEBUG
459 push(new_parser.value_stack, result)
460 $iidebug("r", token, ruleno, new_parser)
461 put(actives, new_parser)
462 break next
463 }
464 if find("accept", tmp) then {
465 $iidebug("a", token, ruleno, new_parser)
466 suspend result
467 next
468 }
469 }
470 #
471 # Push result onto the new parser thread's value
472 # stack.
473 #
474 push(new_parser.value_stack, result)
475 $iidebug("r", token, ruleno, new_parser)
476 put(actives, new_parser)
477 #
478 # Action code must have the stack in its original
479 # form. So restore the stack's old form before
480 # going back to the action code.
481 #
482 if num = 1 then
483 $value_stack := parser.value_stack[2:0]
484 }
485 #
486 # If the action code for this rule failed, push &null.
487 # But first check $iidirective.
488 #
489 if num = 0 then {
490 #
491 # Same $iidirective code as above repeated
492 # (inelegantly) because it accesses too many
493 # variables to be easily isolated.
494 #
495 tmp := $iidirective
496 $iidirective := ""
497 if *tmp > 0 then {
498 if find("clearin", tmp) then {
499 # see perform_shifts() below
500 parser.clearin := 1
501 }
502 if find("error", tmp) then {
503 $iidebug("e", token, ruleno, parser)
504 put(barfers, parser)
505 next
506 }
507 if find("errok", tmp) then {
508 parser.recover_shifts := &null
509 parser.discards := 0
510 }
511 if find("prune", tmp) then {
512 # Garden path.
513 $iidebug("p", token, ruleno, parser)
514 next # go back to enclosing while pop...
515 }
516 if find("isolate", tmp) then {
517 # Prune all but the current parser.
518 $$ifdef IIDEBUG
519 write(&errout, "+++ isolating by pruning")
520 while p := pop(actives) do
521 $iidebug("p", token, ruleno, p)
522 while p := pop(reducers) do
523 $iidebug("p", token, ruleno, p)
524 while p := pop(shifters) do
525 $iidebug("p", token, ruleno, p)
526 while p := pop(barfers) do
527 $iidebug("p", token, ruleno, p)
528 $$else
529 while pop(actives)
530 while pop(reducers)
531 while pop(shifters)
532 while pop(barfers)
533 $$endif #IIDEBUG
534 }
535 if find("accept", tmp) then {
536 $iidebug("a", token, ruleno, parser)
537 suspend arglist[-1] | &null
538 next
539 }
540 }
541 # Finally, push the result!
542 result := arglist[-1] | &null
543 push(parser.value_stack, result)
544 $iidebug("r", token, ruleno, parser)
545 put(actives, parser)
546 }
547 }
548 # If there is no action code for this rule...
549 else {
550 # ...push the value of the last RHS arg.
551 # For 0-length e-productions, push &null.
552 result := arglist[-1] | &null
553 push(parser.value_stack, result)
554 $iidebug("r", token, ruleno, parser)
555 put(actives, parser)
556 }
557 }
558 }
559
560 end
561
562
563 #
564 # perform_shifts
565 #
566 procedure $perform_shifts(token, actives, shifters)
567
568 local parser, ruleno
569
570 *shifters = 0 & fail
571
572 while parser := pop(shifters) do {
573 #
574 # One of the iidirectives is iiclearin, i.e. clear the input
575 # token and try again on the next token.
576 #
577 \parser.clearin := &null & {
578 put(actives, parser)
579 next
580 }
581 parser.action ? {
582 #
583 # Shift action format, e.g. s2.1 = shift and go to state 2
584 # by rule 1.
585 #
586 move(1)
587 push(parser.state_stack, integer(tab(find("."))))
588 push(parser.value_stack, $iilval)
589 ="."; ruleno := integer(tab(many(&digits)))
590 pos(0) | stop("malformed action: ", act)
591 #
592 # If, while recovering, we can manage to shift 3 tokens,
593 # then we consider ourselves resynchronized. Don't count
594 # the error token (-1).
595 #
596 if token ~= -1 then {
597 if \parser.recover_shifts +:= 1 then {
598 # 3 shifts make a successful recovery
599 if parser.recover_shifts > 4 then {
600 parser.recover_shifts := &null
601 parser.discards := 0
602 }
603 }
604 }
605 $iidebug("s", token, ruleno, parser)
606 }
607 put(actives, parser)
608 }
609
610 return
611
612 end
613
614
615 #
616 # perform_barfs
617 #
618 procedure $perform_barfs(atbl, token, actives, barfers, fail_on_error)
619
620 #
621 # Note how this procedure has its own local reducers and shifters
622 # list. These are *not* passed from the parent environment!
623 #
624 local parser, count, reducers, shifters, recoverers
625
626 # To hold the list of parsers that need to shift error (-1).
627 recoverers := list()
628
629 count := 0
630 while parser := pop(barfers) do {
631 count +:= 1
632 if \parser.recover_shifts := 0 then {
633 #
634 # If we're already in an error state, discard the
635 # current token, and increment the number of discards
636 # we have made. 500 is too many; abort.
637 #
638 if (parser.discards +:= 1) > 500 then {
639 if proc($iierror)
640 then $iierror("fatal error: can't resynchronize")
641 else write(&errout, "fatal error: can't resynchronize")
642 if \fail_on_error then fail
643 else stop()
644 }
645 # try again on this one with the next token
646 put(actives, parser)
647 } else {
648 parser.errors +:= 1 # error count for this parser
649 parser.discards := parser.recover_shifts := 0
650 # If this is our first erroneous parser, print a message.
651 if count = 1 then {
652 if proc($iierror)
653 then $iierror(image(\$ttbl[token]) | image(token))
654 else write(&errout, "parse error")
655 }
656 #
657 # If error appears in a RHS, pop states until we get to a
658 # spot where error (-1) is a valid lookahead token:
659 #
660 if \$ttbl[-1] then {
661 until *parser.state_stack = 0 do {
662 if \atbl[-1][parser.state_stack[1]] then {
663 put(recoverers, parser)
664 break next
665 } else pop(parser.state_stack) & pop(parser.value_stack)
666 }
667 }
668 # If we get past here, the stack is now empty or there
669 # are no error productions. Abandon this parser.
670 $iidebug("p", token, &null, parser)
671 }
672 }
673
674 # Parsers still recovering are in the actives list; those that
675 # need to shift error (-1) are in the recoverers list. The
676 # following turns recoverers into actives:
677 #
678 if *recoverers > 0 then {
679 reducers := list() # a scratch list
680 shifters := list() # ditto
681 until *recoverers = *reducers = 0 do {
682 $$ifdef AUTO_PRUNE
683 auto_prune(actives)
684 $$endif
685 suspend $ib_action(atbl, -1, recoverers, shifters,
686 reducers, barfers)
687 suspend $perform_reductions(-1, recoverers, shifters,
688 reducers, barfers)
689 }
690 $perform_shifts(-1, recoverers, shifters)
691 every put(actives, !recoverers)
692 }
693 #
694 # If there were no recoverers, we've already shifted the error
695 # token, and are discarding tokens from the input stream. Note
696 # that if one parser was recovering, they *all* should be
697 # recovering, since if one was not recovering, it the erroneous
698 # parsers should all have been discarded by the calling proc.
699 #
700 else
701 $discard_token := 1
702
703 end
704
705
706 $$ifdef IIDEBUG
707
708 record production(LHS, RHS, POS, LOOK, no, prec, assoc)
709 #
710 # iidebug
711 #
712 procedure $iidebug(action, token, ruleno, parser)
713
714 local p, t, state
715 static rule_list
716 initial {
717 rule_list := $rule_list_insertion_point
718 $$line 693 "iiglrpar.lib"
719 }
720
721 write(&errout, "--- In parser ", image(parser), ":")
722 case action of {
723 "a" : writes(&errout, "accepting ") &
724 state := parser.state_stack[1]
725 "e" : writes(&errout, "***ERROR***\n") &
726 write(&errout, "recover shifts = ",
727 parser.recover_shifts) &
728 write(&errout, "discarded tokens = ",
729 parser.discards) &
730 writes(&errout, "error action ") &
731 state := parser.state_stack[1]
732 "p" : writes(&errout, "***PRUNING***\n") &
733 writes(&errout, "prune action ") &
734 state := parser.state_stack[1]
735 "r" : writes(&errout, "reducing ") &
736 state := parser.state_stack[2]
737 "s" : writes(&errout, "shifting ") &
738 state := parser.state_stack[2]
739 default : stop("malformed action argument to iidebug")
740 }
741
742 t := image(token) || (" (" || (\$ttbl[token] | "unknown") || ")")
743 writes(&errout, "on lookahead ", t, ", in state ", state)
744 if \ruleno then {
745 (p := !rule_list).no === ruleno &
746 write(&errout, "; rule ", $production_2_string(p, $ttbl))
747 }
748 # for errors, ruleno is null
749 else write(&errout)
750
751 write(&errout, " state stack now: ")
752 every write(&errout, "\t", image(!parser.state_stack))
753 write(&errout, " value stack now: ")
754 if *parser.value_stack > 0
755 then every write(&errout, "\t", image(!parser.value_stack))
756 else write(&errout, "\t(empty)")
757
758 return
759
760 end
761
762
763 #
764 # production_2_string: production record -> string
765 # p -> s
766 #
767 # Stringizes an image of the LHS and RHS of production p in
768 # human-readable form.
769 #
770 procedure $production_2_string(p, ibtoktbl)
771
772 local s, m, t
773
774 s := image(p.LHS) || " -> "
775 every m := !p.RHS do {
776 if t := \ (\ibtoktbl)[m]
777 then s ||:= t || " "
778 else s ||:= image(m) || " "
779 }
780 # if the POS field is nonnull, print it
781 s ||:= "(POS = " || image(\p.POS) || ") "
782 # if the LOOK field is nonnull, print it, too
783 s ||:= "lookahead = " || image(\p.LOOK)
784
785 return trim(s)
786
787 end
788
789 #
790 # show_new_forest
791 #
792 procedure show_new_forest(msg, actives, shifters, reducers, barfers, parser)
793 write(&errout, msg)
794 write(&errout, " List of active parsers:")
795 every write(&errout, "\t", image(!actives))
796 every write(&errout, "\t", image(!shifters))
797 every write(&errout, "\t", image(!reducers))
798 every write(&errout, "\t", image(!barfers), " (error)")
799 write(&errout, "\tnew -> ", image(parser))
800 end
801 $$endif # IIDEBUG
802
803
804 $$ifdef COMPRESSED_TABLES
805
806 #
807 # uncompress_action
808 #
809 procedure $uncompress_action()
810
811 local next_chunk, full_action
812
813 next_chunk := create ord(!&subject[&pos:0])
814 case $in_ib_bits(next_chunk, 2) of {
815 0: {
816 full_action := "s"
817 full_action ||:= $in_ib_bits(next_chunk, 11)
818 full_action ||:= "."
819 full_action ||:= $in_ib_bits(next_chunk, 11)
820 move(3)
821 }
822 1: {
823 full_action := "r"
824 full_action ||:= $in_ib_bits(next_chunk, 11)
825 full_action ||:= "<"
826 full_action ||:= $in_ib_bits(next_chunk, 11)
827 full_action ||:= ">"
828 full_action ||:= $in_ib_bits(next_chunk, 8)
829 move(4)
830 }
831 2: {
832 full_action := "a"
833 move(1)
834 }
835 } | fail
836
837 return full_action
838
839 end
840
841
842 #
843 # in_ib_bits: like inbits (IPL), but with coexpression for file
844 #
845 procedure $in_ib_bits(next_chunk, len)
846
847 local i, byte, old_byte_mask
848 static old_byte, old_len, byte_length
849 initial {
850 old_byte := old_len := 0
851 byte_length := 8
852 }
853
854 old_byte_mask := (0 < 2^old_len - 1) | 0
855 old_byte := iand(old_byte, old_byte_mask)
856 i := ishift(old_byte, len-old_len)
857
858 len -:= (len > old_len) | {
859 old_len -:= len
860 return i
861 }
862
863 while byte := @next_chunk do {
864 i := ior(i, ishift(byte, len-byte_length))
865 len -:= (len > byte_length) | {
866 old_len := byte_length-len
867 old_byte := byte
868 return i
869 }
870 }
871
872 end
873
874 $$endif # COMPRESSED_TABLES
875
876 #
877 # fullcopy: make full recursive copy of object obj
878 #
879 procedure $fullcopy(obj)
880
881 local retval, i, k
882
883 case type(obj) of {
884 "co-expression" : return obj
885 "cset" : return obj
886 "file" : return obj
887 "integer" : return obj
888 "list" : {
889 retval := list(*obj)
890 every i := 1 to *obj do
891 retval[i] := $fullcopy(obj[i])
892 return retval
893 }
894 "null" : return &null
895 "procedure" : return obj
896 "real" : return obj
897 "set" : {
898 retval := set()
899 every insert(retval, $fullcopy(!obj))
900 return retval
901 }
902 "string" : return obj
903 "table" : {
904 retval := table(obj[[]])
905 every k := key(obj) do
906 insert(retval, $fullcopy(k), $fullcopy(obj[k]))
907 return retval
908 }
909 # probably a record; if not, we're dealing with a new
910 # version of Icon or a nonstandard implementation, and
911 # we're screwed
912 default : {
913 retval := copy(obj)
914 every i := 1 to *obj do
915 retval[i] := $fullcopy(obj[i])
916 return retval
917 }
918 }
919
920 end
921
922
923 $$ifdef AUTO_PRUNE
924 procedure auto_prune(actives)
925
926 new_actives := []
927 while parser1 := pop(actives) do {
928 every parser2 := actives[j := 1 to *actives] do {
929 parser1.state_stack[1] = parser2.state_stack[1] | next
930 *parser1.value_stack = *parser2.value_stack | next
931 every i := 1 to *parser1.value_stack do {
932 parser1.value_stack[i] === parser2.value_stack[i] |
933 break next
934 }
935 if parser1.errors < parser2.errors then
936 actives[j] := parser1
937 break next
938 }
939 put(new_actives, parser1)
940 }
941
942 every put(actives, !new_actives)
943 return &null
944
945 end
946 $$endif # AUTO_PRUNE