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