176 else |
176 else |
177 (None, rhss_ref ins skipped); |
177 (None, rhss_ref ins skipped); |
178 |
178 |
179 (*list all terminals that can start the given rhss*) |
179 (*list all terminals that can start the given rhss*) |
180 fun look_rhss starts rhss_ref = |
180 fun look_rhss starts rhss_ref = |
181 let fun look [] _ = [] |
181 let fun look [] _ result = result |
182 | look ((symbs, _, _) :: todos) done = |
182 | look ((symbs, _, _) :: todos) done result = |
183 let val (start_token, skipped) = rhss_start symbs []; |
183 let val (start_token, skipped) = rhss_start symbs []; |
184 |
184 |
185 (*process all nonterminals on which the lookahead |
185 (*process all nonterminals on which the lookahead |
186 depends and build the new todo and done lists for |
186 depends and build the new todo and done lists for |
187 the look function*) |
187 the look function*) |
188 fun look2 [] todos = look todos (done union skipped) |
188 fun look2 [] todos result = |
189 | look2 (rhss_ref :: ls) todos = |
189 look todos (done union skipped) result |
190 if rhss_ref mem done then look2 ls todos |
190 | look2 (rhss_ref :: ls) todos result = |
|
191 if rhss_ref mem done then look2 ls todos result |
191 else case assoc (starts, rhss_ref) of |
192 else case assoc (starts, rhss_ref) of |
192 Some tks => tks union (look2 ls todos) |
193 Some tks => look2 ls todos (tks union result) |
193 | None => let val (_, rhss) = hd (!rhss_ref); |
194 | None => |
194 in look2 ls (rhss union todos) end; |
195 let val (_, rhss) = hd (!rhss_ref); |
|
196 in look2 ls (rhss @ todos) result end; |
195 in case start_token of |
197 in case start_token of |
196 Some tk => start_token ins (look2 skipped todos) |
198 Some tk => look2 skipped todos (start_token ins result) |
197 | None => look2 skipped todos |
199 | None => look2 skipped todos result |
198 end; |
200 end; |
199 |
201 |
200 val (_, rhss) = hd (!rhss_ref); |
202 val (_, rhss) = hd (!rhss_ref); |
201 in look rhss [rhss_ref] end; |
203 in look rhss [rhss_ref] [] end; |
202 |
204 |
203 (*make a table that contains all possible starting terminals |
205 (*make a table that contains all possible starting terminals |
204 for each nonterminal*) |
206 for each nonterminal*) |
205 fun mk_starts [] starts = starts |
207 fun mk_starts [] starts = starts |
206 | mk_starts ((_, rhss_ref) :: ps) starts = |
208 | mk_starts ((_, rhss_ref) :: ps) starts = |
208 |
210 |
209 val starts = mk_starts ref_gram []; |
211 val starts = mk_starts ref_gram []; |
210 |
212 |
211 (*add list of allowed starting tokens to productions*) |
213 (*add list of allowed starting tokens to productions*) |
212 fun mk_lookahead (_, rhss_ref) = |
214 fun mk_lookahead (_, rhss_ref) = |
213 let (*add item to lookahead list (a list containing pairs of token and |
215 let (*compares two values of type token option |
214 rhss that can be started with it*) |
216 (used for speed reasons)*) |
|
217 fun matching_opt_tks (Some tk1, Some tk2) = |
|
218 matching_tokens (tk1, tk2) |
|
219 | matching_opt_tks _ = false; |
|
220 |
|
221 (*add item to lookahead list (a list containing pairs of token and |
|
222 rhss that can be started with it)*) |
215 fun add_start new_rhs tokens table = |
223 fun add_start new_rhs tokens table = |
216 let fun add [] [] = [] |
224 let fun add [] [] = [] |
217 | add (tk :: tks) [] = |
225 | add (tk :: tks) [] = |
218 (tk, [new_rhs]) :: (add tks []) |
226 (tk, [new_rhs]) :: (add tks []) |
219 | add tokens ((tk, rhss) :: ss) = |
227 | add tokens ((tk, rhss) :: ss) = |
220 if tk mem tokens then |
228 if gen_mem matching_opt_tks (tk, tokens) then |
221 (tk, new_rhs :: rhss) :: (add (tokens \ tk) ss) |
229 (tk, new_rhs :: rhss) :: (add (tokens \ tk) ss) |
222 else |
230 else |
223 (tk, rhss) :: (add tokens ss); |
231 (tk, rhss) :: (add tokens ss); |
224 in add tokens table end; |
232 in add tokens table end; |
225 |
233 |
226 (*combine all lookaheads of a list of nonterminals*) |
234 (*combine all lookaheads of a list of nonterminals*) |
227 fun combine_starts rhss_refs = |
235 fun combine_starts rhss_refs = |
228 foldr (op union) |
236 foldr (gen_union matching_opt_tks) |
229 ((map (fn rhss_ref => let val Some tks = assoc (starts, rhss_ref) |
237 ((map (fn rhss_ref => let val Some tks = assoc (starts, rhss_ref) |
230 in tks end) rhss_refs), []); |
238 in tks end) rhss_refs), []); |
231 |
239 |
232 (*get lookahead for a rhs and update lhs' lookahead list*) |
240 (*get lookahead for a rhs and update lhs' lookahead list*) |
233 fun look_rhss [] table = table |
241 fun look_rhss [] table = table |
234 | look_rhss ((rhs as (symbs, id, prec)) :: rs) table = |
242 | look_rhss ((rhs as (symbs, id, prec)) :: rs) table = |
235 let val (start_token, skipped) = rhss_start symbs []; |
243 let val (start_token, skipped) = rhss_start symbs []; |
236 val starts = case start_token of |
244 val starts = case start_token of |
237 Some tk => Some tk |
245 Some tk => gen_ins matching_opt_tks |
238 ins (combine_starts skipped) |
246 (Some tk, combine_starts skipped) |
239 | None => if skipped subset lambdas then |
247 | None => if skipped subset lambdas then |
240 [None] |
248 [None] |
241 else |
249 else |
242 combine_starts skipped; |
250 combine_starts skipped; |
243 in look_rhss rs (add_start rhs starts table) end; |
251 in look_rhss rs (add_start rhs starts table) end; |