|
1
8
9 package beaver.comp;
10
11 import java.io.DataOutputStream  ;
12 import java.io.IOException ;
13 import java.util.ArrayList ;
14 import java.util.Arrays ;
15
16 import beaver.spec.Grammar;
17 import beaver.spec.GrammarSymbol;
18 import beaver.spec.Terminal;
19
20
23 class ParsingTables
24 {
25
26 public final State first_state;
27
28
29 final int n_term;
30
31
32 short[] actions;
33
34
35 short[] lookaheads;
36
37
41 int[] terminal_offsets;
42
43
47 int[] nonterminal_offsets;
48
49
50 int last_action_index;
51
52
53 short[] default_actions;
54
55
56 boolean compressed;
57
58 ParsingTables(Grammar grammar, State first_state)
59 {
60 int num_states = countStates(first_state);
61
62 this.first_state = first_state;
63 this.n_term = grammar.terminals.length;
64
65 default_actions = new short[num_states + 1];
66 terminal_offsets = new int[num_states + 1];
67 nonterminal_offsets = new int[num_states + 1];
68
69 Arrays.fill(terminal_offsets, UNUSED_OFFSET);
70 Arrays.fill(nonterminal_offsets, UNUSED_OFFSET);
71
72 actions = new short[16384]; lookaheads = new short[actions.length];
74
75 Arrays.fill(lookaheads, (short) -1);
76
77 ArrayList list_of_action_lists = new ArrayList (num_states * 2);
78 for (State state = first_state; state != null; state = state.next)
79 {
80 if (state.default_action != null)
81 {
82 default_actions[state.id] = state.default_action.getId();
83 compressed = true;
84 }
85
86 if (state.terminal_lookahead_actions.num_actions > 0)
87 {
88 list_of_action_lists.add(state.terminal_lookahead_actions);
89 }
90
91 if (state.nonterminal_lookahead_actions.num_actions > 0)
92 {
93 list_of_action_lists.add(state.nonterminal_lookahead_actions);
94 }
95 }
96 Action.List[] action_lists = (Action.List[]) list_of_action_lists.toArray(new Action.List[list_of_action_lists.size()]);
97 Arrays.sort(action_lists, Action.List.NUM_ACTIONS_CMP);
98
99 renumberSymbols(grammar, action_lists);
100
101 int start_index = 0;
102 for (int i = 0; i < action_lists.length; i++)
103 {
104 Action.List list = action_lists[i];
105 int offset = findOffset(list, start_index);
106 if (list.first.lookahead instanceof Terminal)
107 {
108 if (terminal_offsets[list.state.id] != UNUSED_OFFSET)
109 throw new IllegalStateException ("terminal offset " + list.state.id + " is used");
110 terminal_offsets[list.state.id] = offset;
111 }
112 else
113 {
114 if (nonterminal_offsets[list.state.id] != UNUSED_OFFSET)
115 throw new IllegalStateException ("nonterminal offset " + list.state.id + " is used");
116 nonterminal_offsets[list.state.id] = offset;
117 }
118 last_action_index = Math.max(last_action_index, offset + list.last.lookahead.id);
119 start_index = advanceStartIndex(start_index);
120 }
121 }
122
123 private void renumberSymbols(Grammar grammar, Action.List[] action_lists)
124 {
125 for (int i = 0; i < action_lists.length; i++)
126 {
127 for (Action act = action_lists[i].first; act != null; act = act.next)
128 {
129 act.lookahead.nrefs++;
130 }
131 }
132 Arrays.sort(grammar.terminals, 1, grammar.terminals.length, GrammarSymbol.NUMBER_OF_REFERENCES_COMPARATOR);
133 Arrays.sort(grammar.nonterminals, GrammarSymbol.NUMBER_OF_REFERENCES_COMPARATOR);
134
135 for (int i = 1 ; i < grammar.terminals.length; i++)
136 {
137 grammar.terminals[i].id = (short) i;
138 }
139 for (int i = 0; i < grammar.nonterminals.length; i++)
140 {
141 grammar.nonterminals[i].id = (short) (i + grammar.terminals.length);
142 }
143 for (int i = 0; i < action_lists.length; i++)
144 {
145 action_lists[i].sort();
146 }
147 }
148
149 private int advanceStartIndex(int start_index)
150 {
151 while (start_index < actions.length && actions[start_index] != 0)
152 start_index++;
153 return start_index;
154 }
155
156 private int findOffset(Action.List action_list, int start_index)
157 {
158 int min_lookahead_id = action_list.first.lookahead.id;
159 int max_lookahead_id = action_list.last.lookahead.id;
160 int range = max_lookahead_id - min_lookahead_id + 1;
161
162 while (true) {
164 int last_index = actions.length - range;
165
166 for (int index = start_index; index <= last_index; index++)
167 {
168 if (actions[index] != 0)
169 continue;
170
171 int offset = index - min_lookahead_id;
172 if (tryInsertActions(action_list, offset))
173 {
174 insertActions(action_list, offset);
175 return offset;
176 }
177 }
178
179 if (actions.length >= 1024 * 1024) throw new IllegalStateException ("cannot find place for some actions in parsing tables");
181
182 actions = expand(actions);
183 int len = lookaheads.length;
184 lookaheads = expand(lookaheads);
185 Arrays.fill(lookaheads, len, lookaheads.length, (short) -1);
186 }
187 }
188
189 private void insertActions(Action.List action_list, int offset)
190 {
191 for (Action act = action_list.first; act != null; act = act.next)
192 {
193 int index = offset + act.lookahead.id;
194 if (actions[index] != 0)
195 throw new IllegalStateException ("inserting action in occupied slot");
196 actions[index] = act.getId();
197 }
198 }
199
200 private boolean tryInsertActions(Action.List action_list, int offset)
201 {
202 if (canInsertActions(action_list, offset))
203 {
204 insertLookaheads(action_list, offset);
205
206 if (action_list.first.lookahead.id >= n_term || !hasCollisions())
207 return true;
208
209 removeLookaheads(action_list, offset);
210 }
211 return false;
212 }
213
214 private boolean canInsertActions(Action.List action_list, int offset)
215 {
216 for (Action act = action_list.first; act != null; act = act.next)
217 {
218 if (actions[offset + act.lookahead.id] != 0)
219 return false;
220 }
221 return true;
222 }
223
224 private void insertLookaheads(Action.List action_list, int offset)
225 {
226 for (Action act = action_list.first; act != null; act = act.next)
227 {
228 int index = offset + act.lookahead.id;
229 if (lookaheads[index] >= 0)
230 throw new IllegalStateException ("lookahead collision during initial insert");
231 lookaheads[index] = act.lookahead.id;
232 }
233 }
234
235 private void removeLookaheads(Action.List action_list, int offset)
236 {
237 for (Action act = action_list.first; act != null; act = act.next)
238 {
239 lookaheads[offset + act.lookahead.id] = -1;
240 }
241 }
242
243 private boolean hasCollisions()
244 {
245 for (State state = first_state; state != null; state = state.next)
246 {
247 int offset = terminal_offsets[state.id];
248 if (offset == UNUSED_OFFSET)
249 continue;
250
251 Action act = state.terminal_lookahead_actions.first;
252 for (int la = 0; la < n_term; la++)
253 {
254 if (act != null && act.lookahead.id == la)
255 {
256 act = act.next;
257 continue;
258 }
259 int index = offset + la;
260 if (0 <= index && index < lookaheads.length && lookaheads[index] == la)
261 return true;
262 }
263 }
264 return false;
265 }
266
267 void writeTo(DataOutputStream data_stream) throws IOException
268 {
269 int len;
270
271 data_stream.writeInt(len = last_action_index + 1);
272 for (int i = 0; i < len; i++)
273 {
274 data_stream.writeShort(actions[i]);
275 }
276 for (int i = 0; i < len; i++)
277 {
278 data_stream.writeShort(lookaheads[i]);
279 }
280
281 data_stream.writeInt(len = terminal_offsets.length);
282 for (int i = 0; i < len; i++)
283 {
284 data_stream.writeInt(terminal_offsets[i]);
285 }
286 for (int i = 0; i < len; i++)
287 {
288 data_stream.writeInt(nonterminal_offsets[i]);
289 }
290
291 data_stream.writeInt(compressed ? len : (len = 0));
292 for (int i = 0; i < len; i++)
293 {
294 data_stream.writeShort(default_actions[i]);
295 }
296 }
297
298 static final int UNUSED_OFFSET = Integer.MIN_VALUE;
299
300 static int countStates(State state)
301 {
302 while (state.next != null)
303 state = state.next;
304 return state.id;
305 }
306
307 static short[] expand(short[] array)
308 {
309 short[] temp = new short[array.length * 2];
310 System.arraycopy(array, 0, temp, 0, array.length);
311 return temp;
312 }
313 } |
Popular Tags |
Java API By Example, From Geeks To Geeks.