| 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 |
|