| 1 |
############################################################################ |
| 2 |
# |
| 3 |
# Name: slrtbls.icn |
| 4 |
# |
| 5 |
# Title: slr table generation routines |
| 6 |
# |
| 7 |
# Author: Richard L. Goerwitz |
| 8 |
# |
| 9 |
# Version: 1.20 |
| 10 |
# |
| 11 |
############################################################################ |
| 12 |
# |
| 13 |
# Contains make_slr_tables(grammar, atbl, gtbl, noconflict, |
| 14 |
# like_yacc), where grammar is an ib_grammar record (as returned by |
| 15 |
# ibreader), where atbl and gtbl are initialized (default &null) hash |
| 16 |
# tables, and where noconflict is a switch that, if nonnull, directs |
| 17 |
# the resolver to abort on unresolvable conflicts. Returns &null if |
| 18 |
# successful in filling out atbl and gtbl. If likeyacc is nonnull, |
| 19 |
# make_slr_tables will resolve reduce/reduce conflicts by order of |
| 20 |
# occurrence in the grammar, just like YACC. Shift/reduce conflicts |
| 21 |
# will be resolved in favor of shift. |
| 22 |
# |
| 23 |
# The reason for the noconflict switch is that there are parsers that |
| 24 |
# can accept tables with multiple action entries, i.e. parsers that |
| 25 |
# can use tables generated by ambiguous grammars. |
| 26 |
# |
| 27 |
# In this routine's case, success is identified with creating a |
| 28 |
# standard SLR action and goto table. Note that both tables end up |
| 29 |
# as tables of tables, with symbols being the primary or first key, |
| 30 |
# and state numbers being the second. This is the reverse of the |
| 31 |
# usual arrangement, but turns out to save a lot of space. Atbl |
| 32 |
# values are of the form "s2.3", "r4<A>10", "a", etc. The string |
| 33 |
# "s2.3" means "shift the current lookahead token, and enter state 2 |
| 34 |
# via rule 3." By way of contrast, "r4<A>10" means "reduce by rule |
| 35 |
# number 4, which has A as its LHS symbol and 10 RHS symbols." A |
| 36 |
# single "a" means "accept." |
| 37 |
|
| 38 |
# Atbl entries may contain more than one action. The actions are |
| 39 |
# simply concatenated: "s2.3r4<A>10a". Conflicts may be resolved |
| 40 |
# later by associativity or precedence, if available. Unresolvable |
| 41 |
# conflicts only cause error termination if the 5th and final |
| 42 |
# argument is nonnull (see above on "noconflict"). |
| 43 |
# |
| 44 |
# Gtbl entries are simpler than atble entries, consisting of a single |
| 45 |
# integer. |
| 46 |
# |
| 47 |
############################################################################ |
| 48 |
# |
| 49 |
# Links: follow, slritems, iohno |
| 50 |
# |
| 51 |
############################################################################ |
| 52 |
|
| 53 |
# declared in ibreader.icn |
| 54 |
# record ib_grammar(start, rules, tbl) |
| 55 |
|
| 56 |
#link follow, slritems, iohno#, ximage |
| 57 |
|
| 58 |
# |
| 59 |
# make_slr_tables |
| 60 |
# |
| 61 |
procedure make_slr_tables(grammar, atbl, gtbl, noconflict, like_yacc) |
| 62 |
|
| 63 |
local start_symbol, st, C, i, augmented_start_symbol, item, |
| 64 |
symbol, new_item_list, j, action |
| 65 |
|
| 66 |
# Initialize start symbol and rule list/set (either is okay). |
| 67 |
start_symbol := grammar.start |
| 68 |
st := grammar.rules |
| 69 |
|
| 70 |
# Number the rules, and then construct the canonical LR(0) item sets. |
| 71 |
every i := 1 to *st do st[i].no := i |
| 72 |
C := make_slr_item_sets(start_symbol, st) |
| 73 |
|
| 74 |
# Now, go through each item in each item set in C filling out the |
| 75 |
# action (atbl) and goto table (gtbl) as we go. |
| 76 |
# |
| 77 |
augmented_start_symbol := "`_" || start_symbol || "_'" |
| 78 |
every i := 1 to *C do { |
| 79 |
every item := !C[i] do { |
| 80 |
# if the dot's *not* at the end of the production... |
| 81 |
if symbol := item.RHS[item.POS] then { |
| 82 |
# if were looking at a terminal, enter a shift action |
| 83 |
if type(symbol) == "integer" then { |
| 84 |
if symbol = -2 then next # Never shift epsilon! |
| 85 |
new_item_list := slr_goto(C[i], symbol, st) |
| 86 |
every j := 1 to *C do { |
| 87 |
if equivalent_item_lists(new_item_list, C[j]) then { |
| 88 |
action := "s" || j || "." || item.no |
| 89 |
resolve(st, atbl, symbol, i, action, |
| 90 |
noconflict, like_yacc) |
| 91 |
break next |
| 92 |
} |
| 93 |
} |
| 94 |
# if we're looking at a nonterminal, add action to gtbl |
| 95 |
} else { |
| 96 |
new_item_list := slr_goto(C[i], symbol, st) |
| 97 |
every j := 1 to *C do { |
| 98 |
if equivalent_item_lists(new_item_list, C[j]) then { |
| 99 |
/gtbl[symbol] := table() |
| 100 |
/gtbl[symbol][i] := j | |
| 101 |
gtbl[symbol][i] =:= j | |
| 102 |
iohno(80, image(symbol), ".", image(i), ":", j) |
| 103 |
break next |
| 104 |
} |
| 105 |
} |
| 106 |
} |
| 107 |
# ...else if the dot *is* at the end of the production |
| 108 |
} else { |
| 109 |
if item.LHS == augmented_start_symbol then { |
| 110 |
action := "a" |
| 111 |
# 0 = EOF |
| 112 |
resolve(st, atbl, 0, i, action, noconflict, like_yacc) |
| 113 |
} else { |
| 114 |
# add a reduce for every symbol in FOLLOW(item.LHS) |
| 115 |
every symbol := !FOLLOW(start_symbol, st, item.LHS) do { |
| 116 |
# RHS size is 0 for epsilon. |
| 117 |
if item.RHS[1] === -2 then { |
| 118 |
action := "r" || item.no || "<" || item.LHS || |
| 119 |
">0" |
| 120 |
} else |
| 121 |
action := "r" || item.no || "<" || item.LHS || |
| 122 |
">" || *item.RHS |
| 123 |
resolve(st, atbl, symbol, i, action, |
| 124 |
noconflict, like_yacc) |
| 125 |
} |
| 126 |
} |
| 127 |
} |
| 128 |
} |
| 129 |
} |
| 130 |
|
| 131 |
return |
| 132 |
|
| 133 |
end |
| 134 |
|
| 135 |
|
| 136 |
# |
| 137 |
# resolve: list|set x table x string|integer, integer, anything, anything |
| 138 |
# -> string |
| 139 |
# (st, tbl, symbol, state, action, noconflict, like_yacc) |
| 140 |
# -> new_action_list |
| 141 |
# |
| 142 |
# Add action to action table, resolving conflicts by precedence |
| 143 |
# and associativity, if need be. If noconflict is nonnull, abort |
| 144 |
# on unresolvable conflicts. Fails on shift/shift "conflicts," or |
| 145 |
# if an identical action is already present in the table entry to |
| 146 |
# be modified. If like_yacc is nonnull, resolve reduce/reduce |
| 147 |
# conflicts by their order of occurrence in the grammar; resolve |
| 148 |
# shift/reduce conflicts in favor of shift. |
| 149 |
# |
| 150 |
procedure resolve(st, tbl, symbol, state, action, noconflict, like_yacc) |
| 151 |
|
| 152 |
local actions, chr, a, ruleno, p, newp |
| 153 |
|
| 154 |
/tbl[symbol] := table() |
| 155 |
/tbl[symbol][state] := "" |
| 156 |
|
| 157 |
# If this action is already present, then don't re-enter it. Just |
| 158 |
# fail. |
| 159 |
# |
| 160 |
tbl[symbol][state] ? { |
| 161 |
while a := tab(any('sra')) do { |
| 162 |
a ||:= tab(upto('.<')) |
| 163 |
a ||:= { (="<" || tab(find(">")+1)) | ="." } |
| 164 |
a ||:= tab(many(&digits)) |
| 165 |
if a == action then fail |
| 166 |
} |
| 167 |
} |
| 168 |
|
| 169 |
# Get rule number for the new action specified as arg 5, and |
| 170 |
# fetch its source production. |
| 171 |
action ? { |
| 172 |
case move(1) of { |
| 173 |
"s": ruleno := (tab(find(".")+1), tab(many(&digits))) |
| 174 |
"r": ruleno := 1(tab(find("<")), move(1)) |
| 175 |
"a": return tbl[symbol][state] := action || tbl[symbol][state] |
| 176 |
} | iohno(70, tbl[symbol][state]) |
| 177 |
(newp := !st).no = ruleno | |
| 178 |
iohno(72, tbl[symbol][state]) |
| 179 |
} |
| 180 |
|
| 181 |
# Resolve any conflicts that might be present. |
| 182 |
# |
| 183 |
actions := "" |
| 184 |
tbl[symbol][state] ? { |
| 185 |
while a := tab(any('sra')) do { |
| 186 |
# Snip out the old action, and put it into a. |
| 187 |
a ||:= tab(upto('.<')) |
| 188 |
a ||:= { (="<" || tab(find(">")+1)) | ="." } |
| 189 |
a ||:= tab(many(&digits)) |
| 190 |
# |
| 191 |
# Get the old action's rule number, and use it to fetch |
| 192 |
# the full production that it is keyed to. |
| 193 |
# |
| 194 |
a ? { |
| 195 |
case move(1) of { |
| 196 |
"s": ruleno := (tab(find(".")+1), tab(many(&digits))) |
| 197 |
"r": ruleno := 1(tab(find("<")), move(1)) |
| 198 |
"a": return tbl[symbol][state] := a || actions || action |
| 199 |
} | iohno(70, tbl[symbol][state]) |
| 200 |
# Go through rule list; find the one whose number is ruleno. |
| 201 |
(p := !st).no = ruleno | |
| 202 |
iohno(71, tbl[symbol][state]) |
| 203 |
} |
| 204 |
|
| 205 |
# Check precedences to see if we can resolve the conflict |
| 206 |
# this way. |
| 207 |
# |
| 208 |
if \newp.prec > \p.prec then |
| 209 |
# discard the old action, a |
| 210 |
return tbl[symbol][state] := actions || action || tab(0) |
| 211 |
else if \newp.prec < \p.prec then |
| 212 |
# discard the new action, action |
| 213 |
return tbl[symbol][state] := actions || a || tab(0) |
| 214 |
else { |
| 215 |
# |
| 216 |
# If, however, both precedences are the same (i.e. |
| 217 |
# newp.prec === p.prec), then we must check the |
| 218 |
# associativities. Right implies shift; left, reduce. |
| 219 |
# If there is no associativity, then we have a |
| 220 |
# conflict. Nonassociative ("n") implies error. |
| 221 |
# |
| 222 |
case action[1] of { |
| 223 |
default: iohno(70, tbl[symbol][state]) |
| 224 |
# case "a" is handled above; look for "s" & "r" |
| 225 |
"s" : { |
| 226 |
if a[1] == "s" then fail # no shift/shift "conflict" |
| 227 |
else if a[1] == "r" then { |
| 228 |
newp.assoc === p.assoc | { |
| 229 |
iohno(40, "state " || state || "; token " || |
| 230 |
symbol || "; rules " || newp.no || |
| 231 |
"," || p.no) |
| 232 |
} |
| 233 |
case newp.assoc of { |
| 234 |
"n" : iohno(41, production_2_string(newp)) |
| 235 |
&null: { # no associativity given |
| 236 |
if \noconflict & /like_yacc then |
| 237 |
iohno(46, "state " || state || |
| 238 |
"; token " || symbol || |
| 239 |
"; rules " || newp.no || |
| 240 |
"," || p.no) |
| 241 |
else { |
| 242 |
write(&errout, "warning: shift/reduce", |
| 243 |
" conflict in state " || state || |
| 244 |
"; token " || symbol || |
| 245 |
"; rules " || newp.no || |
| 246 |
"," || p.no) |
| 247 |
if \like_yacc then { |
| 248 |
write(&errout, "resolving in _ |
| 249 |
favor of shift.") |
| 250 |
return tbl[symbol][state] := |
| 251 |
actions || action || tab(0) |
| 252 |
} else { |
| 253 |
write(&errout, "creating multi-_ |
| 254 |
action table entry") |
| 255 |
return tbl[symbol][state] := |
| 256 |
actions || action || a || tab(0) |
| 257 |
} |
| 258 |
} |
| 259 |
} |
| 260 |
"l" : { # left associative |
| 261 |
# discard new action, action |
| 262 |
return tbl[symbol][state] := |
| 263 |
actions || a || tab(0) |
| 264 |
} |
| 265 |
"r" : { # right associative |
| 266 |
# remove old action, a |
| 267 |
return tbl[symbol][state] := |
| 268 |
actions || action || tab(0) |
| 269 |
} |
| 270 |
} |
| 271 |
} |
| 272 |
} |
| 273 |
"r" : { |
| 274 |
if a[1] == "r" then { |
| 275 |
# |
| 276 |
# If conflicts in general, and reduce-reduce |
| 277 |
# conflicts in specific are not okay... |
| 278 |
# |
| 279 |
if \noconflict & /like_yacc then { |
| 280 |
# ...abort, otherwise... |
| 281 |
iohno(42, "state " || state || "; token " || |
| 282 |
symbol || "; " || "; rules " || |
| 283 |
newp.no || "," || p.no) |
| 284 |
} else { |
| 285 |
# |
| 286 |
# ...flag reduce-reduce conficts, and |
| 287 |
# then resolve them by their order of |
| 288 |
# occurrence in the grammar. |
| 289 |
# |
| 290 |
write(&errout, "warning: reduce/reduce", |
| 291 |
" conflict in state ", state, |
| 292 |
"; token ", symbol, "; rules ", |
| 293 |
newp.no, ",", p.no) |
| 294 |
if \like_yacc then { |
| 295 |
write(&errout, "resolving by order of _ |
| 296 |
occurrence in the grammar") |
| 297 |
if newp.no > p.no |
| 298 |
# discard later production (newp) |
| 299 |
then return return tbl[symbol][state] := |
| 300 |
actions || a || tab(0) |
| 301 |
# discard later production (old p) |
| 302 |
else return tbl[symbol][state] := |
| 303 |
actions || action || tab(0) |
| 304 |
} else { |
| 305 |
# |
| 306 |
# If conflicts ok, but we aren't supposed |
| 307 |
# to resolve reduce-reduce conflicts by |
| 308 |
# order of rule occurrence: |
| 309 |
# |
| 310 |
write(&errout, "creating multi-action _ |
| 311 |
table entry") |
| 312 |
return tbl[symbol][state] := |
| 313 |
actions || action || a || tab(0) |
| 314 |
} |
| 315 |
} |
| 316 |
} else { |
| 317 |
# associativities must be the same for both rules: |
| 318 |
newp.assoc === p.assoc | { |
| 319 |
iohno(40, "state " || state || "; token " || |
| 320 |
symbol || "; rules " || newp.no || |
| 321 |
"," || p.no) |
| 322 |
} |
| 323 |
case newp.assoc of { |
| 324 |
"n" : iohno(41, production_2_string(newp)) |
| 325 |
&null: { |
| 326 |
if \noconflict & /like_yacc then |
| 327 |
iohno(46, "state " || state || |
| 328 |
"; token " || symbol || |
| 329 |
"; rules " || newp.no || |
| 330 |
"," || p.no) |
| 331 |
else { |
| 332 |
write(&errout, "warning: shift/reduce", |
| 333 |
" conflict in state " || state || |
| 334 |
"; token " || symbol || |
| 335 |
"; rules " || newp.no || |
| 336 |
"," || p.no) |
| 337 |
if \like_yacc then { |
| 338 |
write(&errout, "resolving in _ |
| 339 |
favor of shift.") |
| 340 |
return tbl[symbol][state] := |
| 341 |
actions || a || tab(0) |
| 342 |
} else { |
| 343 |
write(&errout, "creating multi-_ |
| 344 |
action table entry") |
| 345 |
return tbl[symbol][state] := |
| 346 |
actions || action || a || tab(0) |
| 347 |
} |
| 348 |
} |
| 349 |
} |
| 350 |
"r" : { |
| 351 |
# discard new action, action |
| 352 |
return tbl[symbol][state] := |
| 353 |
actions || a || tab(0) |
| 354 |
} |
| 355 |
"l" : { |
| 356 |
# remove old action, a |
| 357 |
return tbl[symbol][state] := |
| 358 |
actions || action || tab(0) |
| 359 |
} |
| 360 |
} |
| 361 |
} |
| 362 |
} |
| 363 |
} |
| 364 |
} |
| 365 |
} |
| 366 |
} |
| 367 |
|
| 368 |
return tbl[symbol][state] ||:= action |
| 369 |
|
| 370 |
end |