| 1 |
############################################################################ |
| 2 |
# |
| 3 |
# Name: shrnktbl.icn |
| 4 |
# |
| 5 |
# Title: table shrinker |
| 6 |
# |
| 7 |
# Author: Richard L. Goerwitz |
| 8 |
# |
| 9 |
# Version: 1.4 (later modified 4-Aug-2000/gmt) |
| 10 |
# |
| 11 |
############################################################################ |
| 12 |
# |
| 13 |
# Action/goto table shrinking routine. |
| 14 |
# |
| 15 |
# Entry point: shrink_tables(start_symbol, st, atbl, gtbl), where |
| 16 |
# start_symbol is the start symbol for the grammar whose productions |
| 17 |
# are contained in the list/set st, and where atbl and gtbl are the |
| 18 |
# action and goto tables, respectively. Returns &null, for lack of |
| 19 |
# anything better. |
| 20 |
# |
| 21 |
# Basically, this routine merges duplicate structures in atbl and |
| 22 |
# gtbl (if there are any), replaces the nonterminal symbols in the |
| 23 |
# action table with integers (including the start symbol), then |
| 24 |
# resets the goto table so that its keys point to these integers, |
| 25 |
# instead of to the original nonterminal symbol strings. |
| 26 |
# |
| 27 |
############################################################################ |
| 28 |
# |
| 29 |
# Links: equiv, lists, sets, tables, outbits |
| 30 |
# |
| 31 |
############################################################################ |
| 32 |
# |
| 33 |
# See also: ibpag2, slrtbls |
| 34 |
# |
| 35 |
############################################################################ |
| 36 |
|
| 37 |
# structs has equiv; outbits is for outputting variable-width integers |
| 38 |
# as 8-bit characters |
| 39 |
# |
| 40 |
link equiv |
| 41 |
link lists |
| 42 |
link sets |
| 43 |
link tables |
| 44 |
link outbits |
| 45 |
|
| 46 |
# |
| 47 |
# shrink_tables |
| 48 |
# |
| 49 |
procedure shrink_tables(grammar, atbl, gtbl) |
| 50 |
|
| 51 |
local t, k, seen, nontermtbl, r, a, action, state, by_rule, |
| 52 |
rule_len, LHS, keys |
| 53 |
|
| 54 |
# Create a table mapping nonterminal symbols to integers. |
| 55 |
nontermtbl := table() |
| 56 |
every r := !grammar.rules do |
| 57 |
# r is a production; production records have LHS, RHS,...no |
| 58 |
# fields, where the no field contains the rule number; we can |
| 59 |
# use this as an arbitrary representation for that rule's LHS |
| 60 |
# nonterminal |
| 61 |
insert(nontermtbl, r.LHS, r.no) |
| 62 |
|
| 63 |
# Replace old start symbol. |
| 64 |
grammar.start := nontermtbl[grammar.start] |
| 65 |
|
| 66 |
# Re-form the goto table to use the new integer values for |
| 67 |
# nonterminals. |
| 68 |
keys := set() |
| 69 |
every insert(keys, key(gtbl)) |
| 70 |
every k := !keys do { |
| 71 |
# first create a column for the new integer-valued nonterminal |
| 72 |
insert(gtbl, string(nontermtbl[k]), gtbl[k]) |
| 73 |
# then clobber the old column with a string-valued nonterminal |
| 74 |
gtbl[k] := &null |
| 75 |
} |
| 76 |
|
| 77 |
# Rewrite actions using a fixed field-width format. |
| 78 |
every t := !atbl do { |
| 79 |
every k := key(t) do { |
| 80 |
a := "" |
| 81 |
t[k] ? { |
| 82 |
while action := tab(any('sra')) do { |
| 83 |
case action of { |
| 84 |
"s": { |
| 85 |
outbits(0, 2) |
| 86 |
state := integer(tab(find("."))) |
| 87 |
every a ||:= outbits(state, 11) |
| 88 |
move(1) |
| 89 |
by_rule := integer(tab(many(&digits))) |
| 90 |
every a ||:= outbits(by_rule, 11) |
| 91 |
outbits() |
| 92 |
} |
| 93 |
"r": { |
| 94 |
outbits(1, 2) |
| 95 |
state := integer(tab(find("<"))) |
| 96 |
every a ||:= outbits(state, 11) |
| 97 |
move(1) |
| 98 |
LHS := nontermtbl[tab(find(">"))] |
| 99 |
every a ||:= outbits(LHS, 11) |
| 100 |
move(1) |
| 101 |
rule_len := integer(tab(many(&digits))) |
| 102 |
every a ||:= outbits(rule_len, 8) |
| 103 |
outbits() |
| 104 |
} |
| 105 |
"a": { |
| 106 |
outbits(2, 2) |
| 107 |
a ||:= outbits() |
| 108 |
} |
| 109 |
} |
| 110 |
} |
| 111 |
} |
| 112 |
t[k] := a |
| 113 |
} |
| 114 |
} |
| 115 |
|
| 116 |
# |
| 117 |
# Turn pointers to identical structures into pointers to the same |
| 118 |
# structure. |
| 119 |
# |
| 120 |
seen := set() |
| 121 |
every t := atbl | gtbl do { |
| 122 |
every k := key(t) do { |
| 123 |
if t[k] := equiv(t[k], !seen) |
| 124 |
then next else insert(seen, t[k]) |
| 125 |
} |
| 126 |
} |
| 127 |
|
| 128 |
# signal success |
| 129 |
return &null |
| 130 |
|
| 131 |
end |