1 /* BEGIN INCLUDE FILE ..... lalr_configuration_sets.incl.pl1 ..... 07/28/76 J Falksen */ 2 3 /* format: style4,indattr,idind30 */ 4 dcl null_set fixed bin internal static options (constant) init (0); 5 dcl read_set fixed bin internal static options (constant) init (1); 6 dcl multi_la_set fixed bin internal static options (constant) init (2); 7 dcl apply_set fixed bin internal static options (constant) init (3); 8 dcl contention_set fixed bin internal static options (constant) init (4); 9 dcl inadequate_set fixed bin internal static options (constant) init (5); 10 dcl adequate_set fixed bin internal static options (constant) init (6); 11 dcl empty_set fixed bin internal static options (constant) init (7); 12 13 dcl set_type (0:7) char (15) char internal static options (constant) init ( 14 "null_set", 15 "read_set", 16 "multi_la_set", 17 "apply_set", 18 "contention_set", 19 "inadequate_set", 20 "adequate_set", 21 "empty_set"); 22 23 dcl set_size fixed bin; 24 dcl set_ptr ptr; 25 dcl 1 set (set_size) aligned based (set_ptr), 26 2 type fixed bin, /* Type of set. */ 27 2 symbol fixed bin, /* Symbol or contention level. */ 28 2 first fixed bin, /* First configuration of the set. */ 29 2 last fixed bin, /* Last configuration of the set. */ 30 2 basis_set_length fixed bin, /* Number of configuration's in basis set for read, apply, and 31 inadequate sets. Zero or other sets. */ 32 2 link fixed bin; /* In lalr_make_lr0_cfsm_: link to the next set whose 33 basis set has the same hash value. 34 In lalr_remove_inadequacies_: link from level 1 look ahead 35 and contention sets to the corresponding adequate sets. 36 Zero in other look ahead and contention sets and all 37 empty sets. Link to self in all other sets. */ 38 39 dcl configuration_size fixed bin; 40 dcl configuration_ptr ptr; 41 dcl 1 configuration (configuration_size) aligned based (configuration_ptr), 42 2 symbol fixed bin (17) unaligned, 43 2 next_set fixed bin (17) unaligned, 44 2 production fixed bin (17) unaligned, 45 2 mark fixed bin (17) unaligned; 46 dcl 1 configuration_doublet (configuration_size) aligned based (configuration_ptr), 47 2 symbol_and_next_set fixed bin (35), 48 2 production_and_mark fixed bin (35); 49 dcl configuration_entry (configuration_size) fixed bin (71) aligned based (configuration_ptr); 50 51 dcl 1 contention_configuration (configuration_size) aligned based (configuration_ptr), 52 2 symbol fixed bin (17) unaligned, 53 2 next_set fixed bin (17) unaligned, 54 2 final_set fixed bin (17) unaligned, 55 2 initial_configuration fixed bin (17) unaligned; 56 dcl 1 contention_configuration_doublet (configuration_size) aligned based (configuration_ptr), 57 2 symbol_and_next_set fixed bin (35), 58 2 final_set_and_initial_configuration fixed bin (35); 59 dcl contention_configuration_entry (configuration_size) fixed bin (71) aligned based (configuration_ptr); 60 61 dcl 1 lookahead_configuration (configuration_size) aligned based (configuration_ptr), 62 2 symbol fixed bin (17) unaligned, 63 2 next_set fixed bin (17) unaligned, 64 2 adequate_set fixed bin (17) unaligned, 65 2 mbz fixed bin (17) unaligned; 66 67 /* 68 ^O Meaning of configuration table entries 69 70 ^O 1. in APPLY and INADEQUATE sets (ignored in ADEQUATE set except by get_next_reads) 71 ^O production (>0) => Production being applied (productions_list entry). 72 ^O mark (=1) => Marking first symbol, production name. 73 ^O symbol (<0) => Variable naming the production (variables_list entry). 74 ^O next_set (=0) => -not used- 75 76 ^O 2. in READ, INADEQUATE, and ADEQUATE sets 77 ^O production (>0) => Production in which symbol being read (productions_list entry). 78 ^O mark (>1) => Which symbol being read (counting productions_list(i).first_symbol as 1). 79 ^O symbol (<0) => Variable being read (variables_list entry), 80 ^O (>=0) => terminal being read (terminals_list entry). 81 ^O next_set (>0) => Next set to examine when symbol read. 82 83 ^O 3. in CONTENTION set 84 ^O final_set (<0) => Final set to examine when lookahead successful. 85 ^O initial_configuration (>0) 86 => Initial configuration in this chain. 87 ^O symbol (>=0) => Terminal being looked ahead at (terminals_list entry). 88 ^O abs(next_set) (>0) 89 => Next set to examine if still in contention. 90 91 ^O 4. in LOOKAHEAD set 92 ^O adequate_set (>0) => adequate set headed for (used by trace back) 93 ^O mbz (=0) => -not used- 94 ^O symbol (>=0) => The terminal being looked at (terminals_list entry). 95 ^O next_set (<0) => Next set to examine when terminal present. 96 97 */ 98 99 dcl states_size fixed bin; 100 dcl states_ptr ptr; 101 dcl 1 states (states_size) aligned based (states_ptr), 102 2 type fixed bin, 103 2 first fixed bin unaligned, 104 2 last fixed bin unaligned, 105 2 next fixed bin unaligned, 106 2 owner fixed bin unaligned, 107 2 stack_delete fixed bin unaligned, 108 2 production fixed bin unaligned; 109 110 dcl transitions_size fixed bin (19); 111 dcl transitions_ptr ptr; 112 dcl 1 transitions (transitions_size) aligned based (transitions_ptr), 113 2 symbol fixed bin unaligned, 114 2 next_state fixed bin unaligned; 115 dcl transitions_double (transitions_size) fixed bin (35) aligned based (transitions_ptr); 116 117 dcl vtr_ptr ptr; 118 dcl 1 vtr aligned based (vtr_ptr), 119 2 varb (0:variables_list_size) unaligned, /* Heads of lists of transitions on each variable. */ 120 3 last fixed bin (17), /* vtr.trans index of last transition on this variable. */ 121 3 one bit (1), /* True if all transitions are to the same next set. */ 122 3 first fixed bin (17) unsigned, /* vtr.trans index of first transition on this variable. */ 123 2 trans (131071) aligned, 124 3 from fixed bin unaligned, /* set index of set making the transition */ 125 3 to fixed bin unaligned; /* set index of the set to which the transition is being made. */ 126 127 /* Note: Elements of vtr.trans and transitions must be structurally equivalent since lalr_make_dpda_ 128 copies slices from one to the other by aliasing bit strings onto them. 129 Elements of transitions must also be structurally equivalent to those of DPDA since 130 lalr_compress_dpda_ copies slices from transitions to dpda by the same technique. */ 131 132 /* 133 ^O Meaning of states type mnemonics. 134 ^O 135 ^O (letters before _) 136 ^O rs Read and stack. 137 ^O rns Read but do not stack (a.k.a. lookahead one). 138 Can also stack on some transitions if optimized. 139 ^O mla Multiple lookahead (lookahead > one). 140 ^O as Apply (possibly insignificant) semantics. 141 ^O 142 ^O (after _) 143 ^O t Table of transitions. 144 ^O ust Use shared table. 145 ^O def Table of transitions with a default look transition or 146 ^O a read or look transition on the marked symbol (but 147 ^O not both). This type is created by the optimization 148 ^O phase only. 149 con Table of transitions which continue to another table. 150 This type is created by the optimization phase only. 151 single Table of transitions all having the same next state. 152 This type is used only with apply tables and is never shared. 153 */ 154 dcl 1 null_states_type internal static options (constant), 155 2 null fixed bin init (-1); 156 dcl final fixed bin internal static options (constant) init (0); 157 dcl rs_t fixed bin internal static options (constant) init (1); 158 dcl rs_ust fixed bin internal static options (constant) init (2); 159 dcl rns_t fixed bin internal static options (constant) init (3); 160 dcl rns_ust fixed bin internal static options (constant) init (4); 161 dcl mla_t fixed bin internal static options (constant) init (5); 162 dcl mla_ust fixed bin internal static options (constant) init (6); 163 dcl as_t fixed bin internal static options (constant) init (7); 164 dcl as_ust fixed bin internal static options (constant) init (8); 165 dcl rns_def fixed bin internal static options (constant) init (9); 166 dcl mla_def fixed bin internal static options (constant) init (10); 167 dcl rns_con fixed bin internal static options (constant) init (11); 168 dcl mla_con fixed bin internal static options (constant) init (12); 169 dcl as_single fixed bin internal static options (constant) init (13); 170 171 dcl erased_lookback fixed bin internal static options (constant) init (0); 172 dcl dont_care_state fixed bin internal static options (constant) init (-1); 173 dcl dont_care_symbol fixed bin internal static options (constant) init (-1); 174 dcl continuation_symbol fixed bin internal static options (constant) init (-2); 175 dcl erased_read_look fixed bin internal static options (constant) init (-3); 176 177 /* Note: various procedures rely on the following invariants: 178 179 ^O dont_care_state < erased_lookback <= 0 < lbound (states, 1) 180 ^O erased_read_look < continuation_symbol < dont_care_symbol 181 ^O < 0 <= lbound (terminals_list, 1) */ 182 183 184 /* Format of states and transitions entries: 185 186 Each states entry specifies a state. states.type(i) specifies the 187 "type" of state, for the i-th state. states.first(i) [f value below] 188 specifies the first entry of transitions to use. states.last(i) [l 189 value below] specifies the last. 190 191 For states types: rs_t, rs_ust, rns_t, rns_ust, mla_t, mla_ust, 192 rns_def, mla_def, rns_con, and mla_con: 193 194 transitions(f), ..., transitions(l) is the table of terminal symbol/ 195 next state pairs. transitions.symbol is a terminal to read. In state 196 types rns_def and mla_def the value dont_care_symbol is used for a 197 default look transition. In state types rns_con and mla_con the 198 value continuation_symbol is used as filler in the first entry. 199 Within the optimization phase, the value erased_read_look is given 200 to transitions.symbol in rs_t and rns_t states to represent a 201 transition that has been erased. transitions.next_state is the 202 corresponding next state, i.e., states entry. Negative implies that 203 the terminal symbol is being looked ahead at. In state types rns_con 204 and mla_con the first entry specifies the state at which the 205 terminal symbol/next state pairs continue. For states type rs_ust, 206 rns_ust, and mla_ust states.last(i) is not valid after optimization. 207 states.last(states.owner(i)) should be used instead. 208 209 states.production(i) is the look ahead level (zero for read states) 210 and states.stack_delete (i) is zero. After optimization, 211 states.production(i) will still be one for rns_t, rns_ust, rns_def, 212 and rns_con states even if the state now makes only read 213 transitions. 214 215 216 For all states types as_t, as_ust, and as_single: 217 218 states.stack_delete(i) is the number of entries to be deleted from 219 the parse and lex stacks. (This is one less than the number of 220 symbols in the production.) states.production(i) is the production 221 (productions_list index) being applied. 222 223 transitions(f), ..., transitions(l) is a table of look back / next 224 state pairs. 225 226 transitions.symbol is a lookback value, i.e., a value that can occur 227 in the parsing stack, the number of a state that has already been 228 referenced. transitions.next_state is the corresponding next state 229 value, i.e., next states entry. A value of zero is given to 230 transitions.symbol to represent a transition that has been erased by 231 the optimization phase. In as_single states having only one 232 transitions entry, the value dont_care_state is used as a don't care 233 state number in transitions.symbol. 234 235 236 For state types rs_t, rns_t, mla_t, and as_t: 237 238 states.next(i) is the index of the first state (other than state i) 239 using the i-th state's transition table or zero if no other state 240 uses the table. states.owner(i) is the index of the last state 241 (possibly state i) using the i-th state's transition table. 242 243 For states types rs_ust, rns_ust, mla_ust, as_ust, rns_def, mla_def, 244 rns_con, and mla_con: 245 246 states.next(i) is the index of the next state using the same 247 transition table as the i-th state or zero if the i-th state is the 248 last state using the table. states.owner(i) is the first state using 249 the transition table (i.e., the xxx_t type state). 250 251 /* END INCLUDE FILE ..... lalr_configuration_sets.incl.pl1 ..... */