| 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 |