Debian Codegraph @

ipl/packs/ibpag2/follow.icn

raw
1 ############################################################################
2 #
3 # Name: follow.icn
4 #
5 # Title: compute follow sets for grammar
6 #
7 # Author: Richard L. Goerwitz
8 #
9 # Version: 1.15
10 #
11 ############################################################################
12 #
13 # This file contains FIRST(st, symbol...) and FOLLOW(start_symbol,
14 # st, symbol). For FIRST(), arg1 is a list of productions. Arg 2 is
15 # a string (nonterminal) or an integer (terminal). FIRST may take
16 # more than one symbol argument. FOLLOW takes a string as its first
17 # argument, a list of productions as its second, and a symbol as its
18 # third. There is never any need to call FOLLOW with any more than
19 # one symbol. The return values for FIRST() and FOLLOW() may be
20 # described as follows:
21 #
22 # FIRST returns the set of all terminal symbols that begin valid
23 # prefixes of the first symbol argument, or, if this contains
24 # epsilon, of the first symbol -- <epsilon> ++ the set of terminals
25 # beginning valid prefixes of the second symbol, etc.... The first
26 # argument, st, contains the production list over which FIRST is to
27 # be computed.
28 #
29 # FOLLOW is similar, except that it accepts only one symbol argument,
30 # and returns the set of nonterminals that begin valid prefixes of
31 # symbols that may follow symbol in the grammar defined by the
32 # productions in st.
33 #
34 # Both FIRST() and FOLLOW() are optimized. When called for the first
35 # time with a specific production list (st), both FIRST() and
36 # FOLLOW() create the necessary data structures to calculate their
37 # respective return values. Once created, these data structures are
38 # saved, and re-used for subsequent calls with the same st argument.
39 # The implications for the user are two: 1) The first call to FOLLOW
40 # or FIRST for a given production list will take a while to return,
41 # but 2) subsequent calls will return much faster. Naturally, you
42 # can call both FIRST() and FOLLOW() with various st arguments
43 # throughout the life of a given program.
44 #
45 ############################################################################
46 #
47 # Links: none
48 #
49 ############################################################################
50
51
52 #
53 # FIRST: list|set x string|integer... -> set
54 # (st, symbols...) -> FIRST_set
55 #
56 # Where symbols are strings or integers (nonterminal or terminal
57 # symbols in a production in the list or set of productions, st),
58 # and where FIRST_set is a set of integers corresponding to
59 # terminal symbols that begin valid prefixes of symbols[1], or if
60 # that derives epsilon, of symbols[1] -- epsilon ++ symbols[2],
61 # unless that derives epsilon, etc...
62 #
63 procedure FIRST(st, symbols[])
64
65 local i, result, FIRST_tbl
66 static FIRST_tbl_tbl
67 initial FIRST_tbl_tbl := table()
68
69 /FIRST_tbl_tbl[st] := make_FIRST_sets(st)
70 FIRST_tbl := FIRST_tbl_tbl[st]
71
72 result := set()
73 i := 0
74 while *symbols >= (i +:= 1) do {
75 /FIRST_tbl[symbols[i]] & iohno(90, image(symbols[i]))
76 if not member(FIRST_tbl[symbols[i]], -2) then {
77 # We're done if no epsilons.
78 result ++:= FIRST_tbl[symbols[i]]
79 break
80 } else {
81 # Remove the epsilon & try the next symbol in p.RHS.
82 result ++:= FIRST_tbl[symbols[i]] -- FIRST_tbl[-2]
83 }
84 }
85 # If we get to here without finding a symbol that doesn't derive
86 # epsilon, then give up and insert <epsilon> into result.
87 if i > *symbols then
88 result ++:= FIRST_tbl[-2]
89
90 return result
91
92 end
93
94
95 #
96 # FOLLOW: list|set x string|integer -> set
97 # (st, symbol) -> FOLLOW_set
98 #
99 procedure FOLLOW(start_symbol, st, symbol)
100
101 static FOLLOW_tbl_tbl
102 initial FOLLOW_tbl_tbl := table()
103
104 /FOLLOW_tbl_tbl[st] := make_slr_FOLLOW_sets(start_symbol, st)
105 return FOLLOW_tbl_tbl[st][symbol]
106
107 end
108
109
110 #
111 # Below is the procedure make_slr_FOLLOW_sets(start_symbol, st),
112 # which accepts a string, a set, and a table as its arguments and
113 # returns another table. The first argument must contain the start
114 # symbol for the set (or list) of productions contained in the second
115 # argument. Returns a table of FOLLOW sets, where keys = symbols and
116 # values = follow sets for those symbols.
117 #
118 # The algorithm - somewhat inefficiently implemented here - works out
119 # as follows:
120 #
121 # 1. Place $ (internal 0) in FOLLOW_tbl[start_symbol].
122 # 2. Initialize FOLLOW_tbl[symbol] to { } for every other symbol.
123 # 3. For each production A -> aBb do FOLLOW_tbl[B] ++:= FIRST(b) --
124 # FIRST(<epsilon>).
125 # 4. For each production A -> aBb where FIRST(b) contains
126 # <epsilon> and for each production A -> aB, do FOLLOW_tbl[B] ++:=
127 # FOLLOW_tbl[A].
128 #
129 # Repeat steps 3 and 4 until no FOLLOW set can be expanded, at which
130 # point return the FOLLOW table.
131 #
132 # Note that <epsilon> is represented internally by -2.
133 #
134
135
136 #
137 # make_slr_FOLLOW_sets: string x set/list -> table
138 # (start_symbol, st) -> FOLLOW_tbl
139 #
140 # Where start_symbol is the start symbol for the grammar defined
141 # by the set/list of productions in st, and where FOLLOW_tbl is a
142 # table of follow sets (keys = symbols, values = follow sets for
143 # the symbols).
144 #
145 procedure make_slr_FOLLOW_sets(start_symbol, st)
146
147 local FOLLOW_tbl, k, size, old_size, p, i, j
148
149 FOLLOW_tbl := table()
150 # step 1 above; note that 0 = EOF
151 FOLLOW_tbl[start_symbol] := set([0])
152
153 # step 2
154 every k := (!st).LHS do
155 /FOLLOW_tbl[k] := set()
156
157 # steps 3 and 4
158 size := 0
159 #
160 # When the old size of the FOLLOW sets equals the new size, we are
161 # done because nothing was added to the FOLLOW sets on the last
162 # pass.
163 #
164 while old_size ~===:= size do {
165 size := 0
166 every p := !st do {
167 every i := 1 to *p.RHS-1 do {
168 type(p.RHS[i]) == "string" | next
169 /FOLLOW_tbl[p.RHS[i]] & iohno(90, image(p.RHS[i]))
170 # Go through every RHS symbol until we get a FIRST set
171 # without an epsilon move.
172 every j := i+1 to *p.RHS do {
173 if member(FIRST(st, p.RHS[j]), -2) then {
174 FOLLOW_tbl[p.RHS[i]] ++:=
175 FIRST(st, p.RHS[j]) -- FIRST(st, -2)
176 } else {
177 FOLLOW_tbl[p.RHS[i]] ++:= FIRST(st, p.RHS[j])
178 size +:= *FOLLOW_tbl[p.RHS[i]]
179 break next
180 }
181 }
182 # If we get past "break next" then b in A -> aBb =>*
183 # <epsilon>; add FOLLOW_tbl[A] to FOLLOW_tbl[B].
184 FOLLOW_tbl[p.RHS[i]] ++:= FOLLOW_tbl[p.LHS]
185 size +:= *FOLLOW_tbl[p.RHS[i]]
186 }
187 # Add FOLLOW_tbl[A] to FOLLOW_tbl[B] for the last symbol in the
188 # RHS of every rule.
189 type(p.RHS[*p.RHS]) == "string" | next
190 /FOLLOW_tbl[p.RHS[*p.RHS]] & iohno(90, image(p.RHS[*p.RHS]))
191 FOLLOW_tbl[p.RHS[*p.RHS]] ++:= FOLLOW_tbl[p.LHS]
192 size +:= *FOLLOW_tbl[p.RHS[*p.RHS]]
193 }
194 }
195
196 # Print human-readable version of FOLLOW_tbl if instructed to do so.
197 if \DEBUG then
198 print_follow_sets(FOLLOW_tbl)
199
200 # check for useless nonterminal symbols
201 every k := (!st).LHS do
202 *FOLLOW_tbl[k] = 0 & iohno(91, k)
203
204 return FOLLOW_tbl
205
206 end
207
208
209 #
210 # Below is the routine make_FIRST_sets(st), which accepts as its one
211 # argument a list or set of production records, and which returns a
212 # table t, where t's keys are symbols from the grammar defined by the
213 # productions in st, and where the values assocated with each of
214 # these keys is the FIRST set for that key.
215 #
216 # Production records are structures where the first two fields, LHS
217 # and RHS, contain the left-hand and right-hand side of each rule in
218 # a given grammar. The right-hand side is a linked list of integers
219 # (used for terminals) and strings (used for nonterminals). LHS must
220 # contain a string. Terminals below 1 are reserved. Currently three
221 # are actually used:
222 #
223 # 0 EOF
224 # -1 error
225 # -2 epsilon
226 #
227 # For a description of the FIRST() construction algorithm, see Alfred
228 # Aho, Ravi Sethi, and Jeffrey D. Ullman _Compilers_ (Reading,
229 # Massachusetts: Addison & Wesley, 1986), section 4.4, page 189.
230 # Their algorithm is not strictly suitable, as is, for use here. I
231 # thank Dave Schaumann of the University of Arizona at Tuscon for
232 # explaining to me the iterative construction algorithm that in fact
233 # *is* suitable.
234 #
235 # FIRST is computed on an iterative basis as follows:
236 #
237 # 1. For every terminal symbol a, FIRST(a) = { a }
238 # 2. For every non-terminal symbol A, initialize FIRST(A) = { }
239 # 3. For every production A -> <epsilon>, add <epsilon> to FIRST(A)
240 # 4. For each production of the grammar having the form X -> Y1
241 # Y2 ... Yn, perform the following procedure:
242 # i := 1
243 # while i <= number-of-RHS-symbols do {
244 # if <epsilon> is not in FIRST(Y[i]) then {
245 # FIRST(X) ++:= FIRST(Y[i])
246 # break
247 # } else {
248 # FIRST(X) ++:= FIRST(Y[i]) -- FIRST[<epsilon>]
249 # i +:= 1
250 # }
251 # }
252 # if i > number-of-RHS-symbols then
253 # # <epsilon> is in FIRST(Y[i])
254 # FIRST(X) ++:= FIRST[epsilon]
255 # 5. Repeat step 3 until no new symbols or <epsilon> can be added
256 # to any FIRST set
257 #
258
259
260 #
261 # make_FIRST_sets: set/list -> table
262 # st -> t
263 #
264 # Where st is a set or list of production records, and t is a
265 # table of FIRST sets, where the keys = terminal or nonterminal
266 # symbols and the values = sets of terminal symbols.
267 #
268 # Epsilon move is -2; terminals are positive integers;
269 # nonterminals are strings. Error is -1; EOF is 0.
270 #
271 procedure make_FIRST_sets(st)
272
273 local FIRST_tbl, symbol, p, old_size, size, i
274
275 FIRST_tbl := table()
276 FIRST_tbl[0] := set([0])
277
278 # steps 1, 2, and 3 above
279 every p := !st do {
280 # check for empty RHS (an error)
281 *p.RHS = 0 & iohno(11, production_2_string(p))
282 # step 1
283 every symbol := !p.RHS do {
284 if type(symbol) == "integer"
285 then FIRST_tbl[symbol] := set([symbol])
286 }
287 # step 2
288 /FIRST_tbl[p.LHS] := set() &
289 # step 3
290 if *p.RHS = 1 then {
291 if p.RHS[1] === -2 # -2 is epsilon
292 then insert(FIRST_tbl[p.LHS], -2)
293 }
294 }
295
296 # steps 4 and 5 above
297 size := 0
298 #
299 # When the old size of the FIRST sets equals the new size, we are
300 # done. As long as they're unequal, set old_size to size and try
301 # to add to the FIRST sets.
302 #
303 while old_size ~===:= size do {
304 size := 0
305 every p := !st do {
306 every i := 1 to *p.RHS do {
307 \FIRST_tbl[p.RHS[i]] | iohno(90, image(p.RHS[i]))
308 if not member(FIRST_tbl[p.RHS[i]], -2) then {
309 # We're done with this pass if no epsilons.
310 FIRST_tbl[p.LHS] ++:= FIRST_tbl[p.RHS[i]]
311 size +:= *FIRST_tbl[p.LHS]
312 break next
313 } else {
314 # Remove the epsilon & try the next symbol in p.RHS.
315 FIRST_tbl[p.LHS] ++:= FIRST_tbl[p.RHS[i]] -- FIRST_tbl[-2]
316 }
317 }
318 # If we get past the every...do structure without
319 # break+next-ing, then we are still finding epsilons. In
320 # this case, add epsilon to FIRST_tbl[p.LHS].
321 FIRST_tbl[p.LHS] ++:= FIRST_tbl[-2]
322 size +:= *FIRST_tbl[p.LHS]
323 }
324 }
325
326 # Print human-readable version of FIRST_tbl if instructed to do so.
327 if \DEBUG then
328 print_first_sets(FIRST_tbl)
329
330 return FIRST_tbl
331
332 end