Debian Codegraph @

ipl/packs/ibpag2/slrtbls.icn

raw
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