Debian Codegraph @

ipl/packs/ibpag2/slritems.icn

raw
1 ############################################################################
2 #
3 # Name: slritems.icn
4 #
5 # Title: compute item sets for a grammar
6 #
7 # Author: Richard L. Goerwitz
8 #
9 # Version: 1.10
10 #
11 ############################################################################
12 #
13 # Contains make_slr_item_sets(start_symbol, st), slr_goto(l, symbol,
14 # st), slr_closure(l, st). The user need only worry about
15 # make_slr_item_sets() initially. The slr_goto() routine may be
16 # useful later when constructing action and goto tables.
17 #
18 # Slr_closure(l, st) accepts a list of items as its first argument, a
19 # list or set of the productions in the grammar as its second, and
20 # returns the closure of item list l, in the form of another item
21 # list.
22 #
23 # Note also that the production record structure (LHS, RHS, POS,
24 # LOOK...) has a POS field, and therefore can serve also as an item.
25 # In fact, any structure can be used, as long as its first three
26 # fields are LHS, RHS, and POS.
27 #
28 # See the "Dragon Book" (cited in first.icn) p. 222 ff.
29 #
30 # Slr_goto(l, symbol, st) accepts a list as its first argument, a
31 # string or integer as its second (string = nonterminal, integer =
32 # terminal), and a list or set for its third, returning another list.
33 # Arg 1 must be an item list, as generated either by another call to
34 # slr_goto() or by closure of the start production of the augmented
35 # grammar. Arg 2, symbol, is some terminal or nonterminal symbol.
36 # Arg 3 is the list or set of all productions in the current grammar.
37 # The return value is the closure of the set of all items [A -> aX.b]
38 # such that [A -> a.Xb] is in l (arg 1).
39 #
40 # make_slr_item_sets(start_sym, st) takes a string, start_sym, as its
41 # first argument, and a list or set of productions as its second.
42 # Returns a list of canonical LR(0) item sets or states. It returns,
43 # in other words, a list of lists of items. Items can be any record
44 # type that has LHS, RHS, and POS as its first three fields.
45 #
46 # See the "Dragon Book," example 4.35 (p. 224).
47 #
48 ############################################################################
49 #
50 # Links: ibutil
51 #
52 ############################################################################
53
54 # link ibutil
55
56 #
57 # slr_closure: list x list/set -> list
58 # (l2, st) -> l2
59 #
60 # Where l is a list of items, where st is a list/set of all
61 # productions in the grammar from which l was derived, and where
62 # l(2) is the SLR closure of l, as constructed using the standard
63 # SLR closure operation.
64 #
65 # Ignore the third to fifth arguments, len to added. They are
66 # used internally by recursive calls to slr_closure().
67 #
68 procedure slr_closure(l, st, len, LHS_tbl, added)
69
70 local p, i, new_p, symbol
71 static LHS_tbl_tbl
72 initial LHS_tbl_tbl := table()
73
74 if /LHS_tbl then {
75 if /LHS_tbl_tbl[st] := table() then {
76 # makes looking up all rules with a given LHS easier
77 every p := !st do {
78 /LHS_tbl_tbl[st][p.LHS] := list()
79 put(LHS_tbl_tbl[st][p.LHS], p)
80 }
81 }
82 LHS_tbl := LHS_tbl_tbl[st]
83 }
84
85 /len := 0
86 /added := set()
87
88 # Len tells us where the elements in l start that we haven't yet
89 # tried to generate more items from. These elements are basically
90 # the items added on the last recursive call (or the "core," if
91 # there has not yet been a recursive call).
92 #
93 every i := len+1 to *l do {
94 /l[i].POS := 1
95 # Fails if dot (i.e. l[i].POS) is at the end of the RHS;
96 # also fails if the current symbol (i.e. l[i].RHS[l[i].POS])
97 # is a nonterminal.
98 symbol := l[i].RHS[l[i].POS]
99 # No need to add productions having symbol as their LHS if
100 # we've already done so for this particular l.
101 member(added, symbol) & next
102 every p := !\LHS_tbl[symbol] do {
103 # Make a copy of p, but with dot set to position 1.
104 new_p := copy(p)
105 # Set POS to 1 for non-epsilon productions; otherwise to 2.
106 if *new_p.RHS = 1 & new_p.RHS[1] === -2 then
107 new_p.POS := 2
108 else new_p.POS := 1
109 # if new_p isn't in l, add it to the end of l
110 if not equivalent_items(new_p, !l) then
111 put(l, new_p)
112 }
113 insert(added, symbol)
114 }
115 return {
116 # If nothing new has been added, sort the result and return...
117 if *l = i then sortff(l, 1, 2, 3)
118 # ...otherwise, try to add more items to l.
119 else slr_closure(l, st, i, LHS_tbl, added)
120 }
121
122 end
123
124
125 #
126 # slr_goto: list x string|integer x list|set -> list
127 # (l, symbol, st) -> l2
128 #
129 # Where l is an item set previously returned by slr_goto or (for
130 # the start symbol of the augmented grammar) by slr_closure(),
131 # where symbol is a string (nonterminal) or integer (terminal),
132 # where st is a list or set of all productions in the current
133 # grammar, and where l2 is the SLR closure of the set of all items
134 # [A -> aX.b] such that [A -> a.Xb] is in l.
135 #
136 # The idea is just to move the dots for all productions where the
137 # dots precede "symbol," creating a new item list for the "moved"
138 # items, and then performing a slr_closure() on that new item list.
139 # Note that items can be represented by any structure where fields
140 # 1, 2, and 3 are LHS, RHS, and POS.
141 #
142 # Note that slr_goto(l, symbol, st) may yield a result that's
143 # structurally equivalent to one already in the sets of items thus
144 # far generated. This won't normally happen, because slr_goto()
145 # saves old results, never re-calcing for the same l x symbol
146 # combination. Still, a duplicate result could theoretically
147 # happen.
148 #
149 procedure slr_goto(l, symbol, st)
150
151 local item, item2, l2, iteml_symbol_table
152 static iteml_symbol_table_table
153 initial iteml_symbol_table_table := table()
154
155 # Keep old results for this grammar (st) in a table of tables of
156 # tables!
157 #
158 /iteml_symbol_table_table[st] := table()
159 iteml_symbol_table := iteml_symbol_table_table[st]
160
161 # See if we've already performed this same calculation.
162 #
163 if l2 := \(\iteml_symbol_table[l])[symbol]
164 then return l2
165
166 l2 := list()
167 every item := !l do {
168 # Subscripting operation fails if the dot's at end.
169 if item.RHS[item.POS] === symbol
170 then {
171 item2 := copy(item) # copy is nonrecursive
172 item2.POS +:= 1
173 put(l2, item2)
174 }
175 }
176 if *l2 = 0 then fail
177 else l2 := slr_closure(l2, st)
178 #
179 # Keep track of item lists and symbols we've already seen.
180 #
181 /iteml_symbol_table[l] := table()
182 /iteml_symbol_table[l][symbol] := l2
183
184 if *l2 > 0 then
185 return l2
186 else fail
187
188 end
189
190
191 #
192 # make_slr_item_sets: string x list|set -> list
193 # (start_sym, st) -> l
194 #
195 # Where start_sym is the start symbol for the grammar defined by
196 # the productions contained in st, and where l is the list of item
197 # lists generated by the standard LR(0) set-of-items construction
198 # algorithm.
199 #
200 # Ignore the third and fourth arguments. They are used internally
201 # by recursive calls.
202 #
203 procedure make_slr_item_sets(start_sym, st, C, len)
204
205 local i, next_items, item_list, new_list, item, symbol
206
207 #
208 # First extend the old start symbol and use the result as the new
209 # start symbol for the augmented grammar to which the set-of-items
210 # construction will be applied.
211 #
212 # &trace := -1
213 /C := [slr_closure(
214 [production("`_" || start_sym || "_'", [start_sym], 1)],st)]
215 /len := 0
216
217 # Iterate through C (the list of item-lists), doing gotos, and adding
218 # new states, until no more states can be added to C.
219 #
220 every item_list := C[i := len+1 to *C] do {
221 if \DEBUG then
222 print_item_list(C, i)
223 # collect all symbols after the dot for the the items in C[i]...
224 next_items := set()
225 every item := !item_list do
226 insert(next_items, item.RHS[item.POS])
227 # ...now, try to do a slr_goto() for every collected symbol.
228 every symbol := !next_items do {
229 new_list := slr_goto(item_list, symbol, st) | next
230 if not equivalent_item_lists(new_list, !C)
231 then put(C, new_list)
232 }
233 }
234 # If nothing has been inserted, return C and quit; otherwise, call
235 # recursively and try again.
236 #
237 return {
238 if i = *C then C
239 else make_slr_item_sets(&null, st, C, i)
240 }
241
242 end
243
244