Debian Codegraph @

ipl/packs/ibpag2/iiparse.lib

raw
1 ############################################################################
2 #
3 # Name: iiparse.lib
4 #
5 # Title: LR parser code
6 #
7 # Author: Richard L. Goerwitz
8 #
9 # Version: 1.31
10 #
11 ############################################################################
12 #
13 # LR parser code for use by Ibpag2-generated files. Entry point is
14 # iiparse(infile, fail_on_error). Infile is the stream from which
15 # input is to be taken. Infile is passed as argument 1 to the
16 # user-supplied lexical analyzer, iilex_module() (where _module is
17 # the string supplied with the -m option to Ibpag2). If
18 # fail_on_error is nonnull, the parser, iiparse, will fail on errors,
19 # rather than abort. Iiparse() returns the top element on its value
20 # stack on a successful parse (which can be handy).
21 #
22 # Iilex_module() must suspend integers for tokens and may also set
23 # iilval_module to the actual string values. Tokens -2, -1, and 0
24 # are reserved. -2 is epsilon, and -1 is error. 0 is EOF, and is
25 # automatically appended to the token stream when iilex_module, the
26 # tokenizer, fails. These values should not normally be returned by
27 # the analyzer. In general, it is a good idea to $include
28 # iilex_module from your Ibpag2 source files, so that it can use the
29 # symbolic %token names declared in the original Ibpag2 source file.
30 # As implied above ("suspend"), iilex_module must be a generator,
31 # failing on EOF.
32 #
33 # If desired, the user may include his or her own error-handling
34 # routine. It must be called iiparse_module (where _module is once
35 # again the module name supplied to ibpag2 via the -m option). The
36 # global variable line_number_module is automatically defined below,
37 # so a typical arrangement would be for the lexical analyzer to
38 # initialize line_number_module to 0, and increment by 1 for each
39 # line read. The error handler, iierror_module() can then display
40 # this variable. Note that the error handler should accept a single
41 # string argument (set by iiparse to describe the error just
42 # encountered).
43 #
44 ############################################################################
45 #
46 # See also: ibpag2.icn
47 #
48 ############################################################################
49
50 $$line 50 "iiparse.lib"
51
52 # These defines are output by Ibpag2 ahead of time (with the module
53 # name appended, if need be):
54 #
55 # $define iierrok recover_shifts := &null;
56 # $define IIERROR iidirective ||:= "error";
57 # $define IIACCEPT iidirective ||:= "accept";
58 # $define iiclearin iidirective ||:= "clearin";
59
60 # Warning! If you change the name of the value stack, change it also
61 # in ibreader.icn, procedure write_action_as_procedure().
62 #
63 global $iilval, $errors, $line_number, $state_stack, $value_stack,
64 $iidirective, $recover_shifts, $discards
65
66 #
67 # iiparse: file x anything -> ?
68 # (stream, fail_on_error) -> ?
69 #
70 # Where stream is an open file, where fail_on_error is a switch
71 # that (if nonnull) tells the iiparse to fail, rather than abort,
72 # on error, and where ? represents the user-defined result of a
73 # completed parse of file, from the current location up to the
74 # point where the parser executes an "accept" action.
75 #
76 procedure $iiparse(stream, fail_on_error)
77
78 local token, next_token, act, ruleno, newsym, rhsize, arglist,
79 result, tmp, func
80 static atbl, gtbl, ttbl
81
82 initial {
83 $iidirective := ""
84 atbl := $atbl_insertion_point
85 gtbl := $gtbl_insertion_point
86 ttbl := $ttbl_insertion_point
87 $$line 86 "iiparse.lib"
88 \$iilex | stop("no iilex tokenizer defined")
89 }
90
91 $$ifndef IIDEBUG
92 $iidebug := 1
93 $$endif # not IIDEBUG
94
95 $state_stack := [1]
96 $value_stack := []
97
98 $errors := 0 # errors is global
99 next_token := create $iilex(stream, fail_on_error) | 0
100
101 token := @next_token
102 repeat {
103 #
104 # Begin cycle by checking whether there is a valid action
105 # for state $state_stack[1] and lookahead token. Atbl and
106 # gtbl here have a "backwards" structure: t[token][state]
107 # (usually they go t[state][token]).
108 #
109 if act := \ (\atbl[token])[$state_stack[1]] then {
110 $$ifdef COMPRESSED_TABLES
111 act := $uncompress_action(act)
112 $$endif #COMPRESSED TABLES
113 act ? {
114 # There's a valid action: Perform it.
115 case move(1) of {
116 "s": {
117 #
118 # Shift action format, e.g. s2.1 = shift and
119 # go to state 2 by rule 1.
120 #
121 push($state_stack, integer(tab(find("."))))
122 push($value_stack, $iilval)
123 ="."; ruleno := integer(tab(many(&digits)))
124 pos(0) | stop("malformed action: ", act)
125 #
126 # If, while recovering, we can manage to
127 # shift 3 tokens, then we consider ourselves
128 # resynchronized. Don't count error (-1).
129 #
130 if token ~= -1 then {
131 if \$recover_shifts +:= 1 then {
132 # 3 shifts = successful recovery
133 if $recover_shifts > 4 then {
134 $recover_shifts := &null
135 $discards := 0
136 }
137 }
138 }
139 $iidebug("s", ttbl, token, ruleno)
140 token := @next_token | break
141 }
142 "r": {
143 #
144 # Reduce action format, e.g. r1<S>2 = reduce
145 # by rule 1 (LHS = S, RHS length = 2).
146 #
147 ruleno := integer(1(tab(find("<")), move(1)))
148 newsym := 1(tab(find(">")), move(1))
149 rhsize := integer(tab(many(&digits)))
150 arglist := []
151 every 1 to rhsize do {
152 pop($state_stack)
153 push(arglist, pop($value_stack))
154 }
155 # on the structure of gtbl, see above on atbl
156 push($state_stack, gtbl[newsym][$state_stack[1]])
157 #
158 # The actions are in procedures having the same
159 # name as the number of their rule, bracketed
160 # by underscores followed by the current module.
161 #
162 if func := proc("_" || ruleno || "_" || $module)
163 then {
164 result := func!arglist | arglist[-1] | &null
165 tmp := $iidirective
166 $iidirective := ""
167 #
168 # IIERROR, IIACCEPT, iierrok, and iiclearin
169 # are implemented using a search through a global
170 # iidirective variable; see the $defines
171 # above
172 #
173 if *tmp > 0 then {
174 if find("clearin", tmp) then
175 token := @next_token
176 if find("error", tmp) then {
177 # restore stacks & fake an error
178 pop($state_stack)
179 every 1 to rhsize do
180 push($value_stack, !arglist)
181 $errors +:= 1
182 next_token := create (token |
183 (|@next_token))
184 token := -1
185 next
186 }
187 if find("accept", tmp) then {
188 $iidebug("a", ttbl, token, ruleno)
189 return result
190 }
191 }
192 }
193 # If there is no action code for this rule...
194 else {
195 # ...push the value of the last RHS arg.
196 # For 0-length e-productions, push &null.
197 result := arglist[-1] | &null
198 }
199 push($value_stack, result)
200 $iidebug("r", ttbl, token, ruleno)
201 }
202 # We're done. Return the last-generated value.
203 "a": {
204 $iidebug("a", ttbl, token, ruleno)
205 return $value_stack[1]
206 }
207 }
208 }
209 }
210 #
211 # ...but if there is *no* action for atbl[token][$state_stack[1]],
212 # then we have an error.
213 #
214 else {
215 if \$recover_shifts := 0 then {
216 #
217 # If we're already in an error state, discard the
218 # current token, and increment the number of discards
219 # we have made. 500 is too many; abort.
220 #
221 if ($discards +:= 1) > 500 then {
222 if \$iierror
223 then $iierror("fatal error: can't resynchronize")
224 else write(&errout, "fatal error: can't resynchronize")
225 if \fail_on_error then fail
226 else stop()
227 }
228 $iidebug("e", ttbl, token)
229 #
230 # We were in the process of recovering, and the late
231 # token didn't help; discard it and try again.
232 #
233 token := @next_token | break
234 } else {
235 $errors +:= 1 # global error count
236 $discards := $recover_shifts := 0
237 if \$iierror
238 then $iierror(image(\ttbl[token]) | image(token))
239 else write(&errout, "parse error")
240 #
241 # If error appears in a RHS, pop states until we get to
242 # a spot where error (-1) is a valid lookahead token:
243 #
244 if \ttbl[-1] then {
245 until *$state_stack = 0 do {
246 if \atbl[-1][$state_stack[1]] then {
247 $iidebug("e", ttbl, token)
248 next_token := create (token | (|@next_token))
249 token := -1
250 break next
251 } else pop($state_stack) & pop($value_stack)
252 }
253 # If we get past here, the stack is now empty. Abort.
254 }
255 if \fail_on_error then fail
256 else stop()
257 }
258 }
259 }
260
261 #
262 # If we get to here without hitting a final state, then we aren't
263 # going to get a valid parse. Abort.
264 #
265 if \$iierror
266 then $iierror("unexpected EOF")
267 else write(&errout, "unexpected EOF")
268
269 if \fail_on_error then fail
270 else stop()
271
272 end
273
274
275 $$ifdef IIDEBUG
276
277 record production(LHS, RHS, POS, LOOK, no, prec, assoc)
278 #
279 # iidebug
280 #
281 procedure $iidebug(action, ttbl, token, ruleno)
282
283 local p, t, state
284 static rule_list
285 initial {
286 rule_list := $rule_list_insertion_point
287 $$line 279 "iiparse.lib"
288 }
289
290 case action of {
291 "a" : writes(&errout, "accepting ") & state := $state_stack[1]
292 "e" : writes(&errout, "***ERROR***\n") &
293 writes(&errout, "recovery shifts = ", $recover_shifts,"\n") &
294 writes(&errout, "discarded tokens = ", $discards, "\n") &
295 writes(&errout, "total error count = ", $errors, "\n") &
296 writes(&errout, "error action ") & state := $state_stack[1]
297 "r" : writes(&errout, "reducing ") & state := $state_stack[2]
298 "s" : writes(&errout, "shifting ") & state := $state_stack[2]
299 default : stop("malformed action argument to iidebug")
300 }
301
302 t := image(token) || (" (" || (\ttbl[token] | "unknown") || ")")
303 writes(&errout, "on lookahead ", t, ", in state ", state)
304 if \ruleno then {
305 (p := !rule_list).no = ruleno |
306 stop("no rule number ", tbl[symbol][state])
307 write(&errout, "; rule ", $production_2_string(p, ttbl))
308 }
309 # for errors, ruleno is null
310 else write(&errout)
311
312 write(&errout, " state stack now: ")
313 every write(&errout, "\t", image(!$state_stack))
314 write(&errout, " value stack now: ")
315 if *$value_stack > 0
316 then every write(&errout, "\t", image(!$value_stack))
317 else write(&errout, "\t(empty)")
318
319 return
320
321 end
322
323
324 #
325 # production_2_string: production record -> string
326 # p -> s
327 #
328 # Stringizes an image of the LHS and RHS of production p in
329 # human-readable form.
330 #
331 procedure $production_2_string(p, ibtoktbl)
332
333 local s, m, t
334
335 s := image(p.LHS) || " -> "
336 every m := !p.RHS do {
337 if t := \ (\ibtoktbl)[m]
338 then s ||:= t || " "
339 else s ||:= image(m) || " "
340 }
341 # if the POS field is nonnull, print it
342 s ||:= "(POS = " || image(\p.POS) || ") "
343 # if the LOOK field is nonnull, print it, too
344 s ||:= "lookahead = " || image(\p.LOOK)
345
346 return trim(s)
347
348 end
349 $$endif # IIDEBUG
350
351
352 $$ifdef COMPRESSED_TABLES
353
354 #
355 # uncompress_action
356 #
357 procedure $uncompress_action(action)
358
359 local next_chunk, full_action
360
361 next_chunk := create ord(!action)
362 case $in_ib_bits(next_chunk, 2) of {
363 0: {
364 full_action := "s"
365 full_action ||:= $in_ib_bits(next_chunk, 11)
366 full_action ||:= "."
367 full_action ||:= $in_ib_bits(next_chunk, 11)
368 }
369 1: {
370 full_action := "r"
371 full_action ||:= $in_ib_bits(next_chunk, 11)
372 full_action ||:= "<"
373 full_action ||:= $in_ib_bits(next_chunk, 11)
374 full_action ||:= ">"
375 full_action ||:= $in_ib_bits(next_chunk, 8)
376 }
377 2: {
378 full_action := "a"
379 }
380 }
381
382 return full_action
383
384 end
385
386
387 #
388 # in_ib_bits: like inbits (IPL), but with coexpression for file
389 #
390 procedure $in_ib_bits(next_chunk, len)
391
392 local i, byte, old_byte_mask
393 static old_byte, old_len, byte_length
394 initial {
395 old_byte := old_len := 0
396 byte_length := 8
397 }
398
399 old_byte_mask := (0 < 2^old_len - 1) | 0
400 old_byte := iand(old_byte, old_byte_mask)
401 i := ishift(old_byte, len-old_len)
402
403 len -:= (len > old_len) | {
404 old_len -:= len
405 return i
406 }
407
408 while byte := @next_chunk do {
409 i := ior(i, ishift(byte, len-byte_length))
410 len -:= (len > byte_length) | {
411 old_len := byte_length-len
412 old_byte := byte
413 return i
414 }
415 }
416
417 end
418
419 $$endif # COMPRESSED_TABLES