Debian Codegraph @

ipl/packs/ibpag2/shrnktbl.icn

raw
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