1/* Compute look-ahead criteria for Bison.
2
3   Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004, 2005,
4   2006 Free Software Foundation, Inc.
5
6   This file is part of Bison, the GNU Compiler Compiler.
7
8   Bison is free software; you can redistribute it and/or modify
9   it under the terms of the GNU General Public License as published by
10   the Free Software Foundation; either version 2, or (at your option)
11   any later version.
12
13   Bison is distributed in the hope that it will be useful,
14   but WITHOUT ANY WARRANTY; without even the implied warranty of
15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16   GNU General Public License for more details.
17
18   You should have received a copy of the GNU General Public License
19   along with Bison; see the file COPYING.  If not, write to
20   the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21   Boston, MA 02110-1301, USA.  */
22
23
24/* Compute how to make the finite state machine deterministic; find
25   which rules need look-ahead in each state, and which look-ahead
26   tokens they accept.  */
27
28#include <config.h>
29#include "system.h"
30
31#include <bitset.h>
32#include <bitsetv.h>
33#include <quotearg.h>
34
35#include "LR0.h"
36#include "complain.h"
37#include "derives.h"
38#include "getargs.h"
39#include "gram.h"
40#include "lalr.h"
41#include "nullable.h"
42#include "reader.h"
43#include "relation.h"
44#include "symtab.h"
45
46goto_number *goto_map;
47static goto_number ngotos;
48state_number *from_state;
49state_number *to_state;
50
51/* Linked list of goto numbers.  */
52typedef struct goto_list
53{
54  struct goto_list *next;
55  goto_number value;
56} goto_list;
57
58
59/* LA is a LR by NTOKENS matrix of bits.  LA[l, i] is 1 if the rule
60   LArule[l] is applicable in the appropriate state when the next
61   token is symbol i.  If LA[l, i] and LA[l, j] are both 1 for i != j,
62   it is a conflict.  */
63
64static bitsetv LA = NULL;
65size_t nLA;
66
67
68/* And for the famous F variable, which name is so descriptive that a
69   comment is hardly needed.  <grin>.  */
70static bitsetv F = NULL;
71
72static goto_number **includes;
73static goto_list **lookback;
74
75
76
77
78static void
79set_goto_map (void)
80{
81  state_number s;
82  goto_number *temp_map;
83
84  goto_map = xcalloc (nvars + 1, sizeof *goto_map);
85  temp_map = xnmalloc (nvars + 1, sizeof *temp_map);
86
87  ngotos = 0;
88  for (s = 0; s < nstates; ++s)
89    {
90      transitions *sp = states[s]->transitions;
91      int i;
92      for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
93	{
94	  ngotos++;
95
96	  /* Abort if (ngotos + 1) would overflow.  */
97	  assert (ngotos != GOTO_NUMBER_MAXIMUM);
98
99	  goto_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
100	}
101    }
102
103  {
104    goto_number k = 0;
105    int i;
106    for (i = ntokens; i < nsyms; i++)
107      {
108	temp_map[i - ntokens] = k;
109	k += goto_map[i - ntokens];
110      }
111
112    for (i = ntokens; i < nsyms; i++)
113      goto_map[i - ntokens] = temp_map[i - ntokens];
114
115    goto_map[nsyms - ntokens] = ngotos;
116    temp_map[nsyms - ntokens] = ngotos;
117  }
118
119  from_state = xcalloc (ngotos, sizeof *from_state);
120  to_state = xcalloc (ngotos, sizeof *to_state);
121
122  for (s = 0; s < nstates; ++s)
123    {
124      transitions *sp = states[s]->transitions;
125      int i;
126      for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
127	{
128	  goto_number k = temp_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
129	  from_state[k] = s;
130	  to_state[k] = sp->states[i]->number;
131	}
132    }
133
134  free (temp_map);
135}
136
137
138
139/*----------------------------------------------------------.
140| Map a state/symbol pair into its numeric representation.  |
141`----------------------------------------------------------*/
142
143static goto_number
144map_goto (state_number s0, symbol_number sym)
145{
146  goto_number high;
147  goto_number low;
148  goto_number middle;
149  state_number s;
150
151  low = goto_map[sym - ntokens];
152  high = goto_map[sym - ntokens + 1] - 1;
153
154  for (;;)
155    {
156      assert (low <= high);
157      middle = (low + high) / 2;
158      s = from_state[middle];
159      if (s == s0)
160	return middle;
161      else if (s < s0)
162	low = middle + 1;
163      else
164	high = middle - 1;
165    }
166}
167
168
169static void
170initialize_F (void)
171{
172  goto_number **reads = xnmalloc (ngotos, sizeof *reads);
173  goto_number *edge = xnmalloc (ngotos + 1, sizeof *edge);
174  goto_number nedges = 0;
175
176  goto_number i;
177
178  F = bitsetv_create (ngotos, ntokens, BITSET_FIXED);
179
180  for (i = 0; i < ngotos; i++)
181    {
182      state_number stateno = to_state[i];
183      transitions *sp = states[stateno]->transitions;
184
185      int j;
186      FOR_EACH_SHIFT (sp, j)
187	bitset_set (F[i], TRANSITION_SYMBOL (sp, j));
188
189      for (; j < sp->num; j++)
190	{
191	  symbol_number sym = TRANSITION_SYMBOL (sp, j);
192	  if (nullable[sym - ntokens])
193	    edge[nedges++] = map_goto (stateno, sym);
194	}
195
196      if (nedges == 0)
197	reads[i] = NULL;
198      else
199	{
200	  reads[i] = xnmalloc (nedges + 1, sizeof reads[i][0]);
201	  memcpy (reads[i], edge, nedges * sizeof edge[0]);
202	  reads[i][nedges] = END_NODE;
203	  nedges = 0;
204	}
205    }
206
207  relation_digraph (reads, ngotos, &F);
208
209  for (i = 0; i < ngotos; i++)
210    free (reads[i]);
211
212  free (reads);
213  free (edge);
214}
215
216
217static void
218add_lookback_edge (state *s, rule *r, goto_number gotono)
219{
220  int ri = state_reduction_find (s, r);
221  goto_list *sp = xmalloc (sizeof *sp);
222  sp->next = lookback[(s->reductions->look_ahead_tokens - LA) + ri];
223  sp->value = gotono;
224  lookback[(s->reductions->look_ahead_tokens - LA) + ri] = sp;
225}
226
227
228
229static void
230build_relations (void)
231{
232  goto_number *edge = xnmalloc (ngotos + 1, sizeof *edge);
233  state_number *states1 = xnmalloc (ritem_longest_rhs () + 1, sizeof *states1);
234  goto_number i;
235
236  includes = xnmalloc (ngotos, sizeof *includes);
237
238  for (i = 0; i < ngotos; i++)
239    {
240      int nedges = 0;
241      symbol_number symbol1 = states[to_state[i]]->accessing_symbol;
242      rule **rulep;
243
244      for (rulep = derives[symbol1 - ntokens]; *rulep; rulep++)
245	{
246	  bool done;
247	  int length = 1;
248	  item_number const *rp;
249	  state *s = states[from_state[i]];
250	  states1[0] = s->number;
251
252	  for (rp = (*rulep)->rhs; ! item_number_is_rule_number (*rp); rp++)
253	    {
254	      s = transitions_to (s->transitions,
255				  item_number_as_symbol_number (*rp));
256	      states1[length++] = s->number;
257	    }
258
259	  if (!s->consistent)
260	    add_lookback_edge (s, *rulep, i);
261
262	  length--;
263	  done = false;
264	  while (!done)
265	    {
266	      done = true;
267	      /* Each rhs ends in an item number, and there is a
268		 sentinel before the first rhs, so it is safe to
269		 decrement RP here.  */
270	      rp--;
271	      if (ISVAR (*rp))
272		{
273		  /* Downcasting from item_number to symbol_number.  */
274		  edge[nedges++] = map_goto (states1[--length],
275					     item_number_as_symbol_number (*rp));
276		  if (nullable[*rp - ntokens])
277		    done = false;
278		}
279	    }
280	}
281
282      if (nedges == 0)
283	includes[i] = NULL;
284      else
285	{
286	  int j;
287	  includes[i] = xnmalloc (nedges + 1, sizeof includes[i][0]);
288	  for (j = 0; j < nedges; j++)
289	    includes[i][j] = edge[j];
290	  includes[i][nedges] = END_NODE;
291	}
292    }
293
294  free (edge);
295  free (states1);
296
297  relation_transpose (&includes, ngotos);
298}
299
300
301
302static void
303compute_FOLLOWS (void)
304{
305  goto_number i;
306
307  relation_digraph (includes, ngotos, &F);
308
309  for (i = 0; i < ngotos; i++)
310    free (includes[i]);
311
312  free (includes);
313}
314
315
316static void
317compute_look_ahead_tokens (void)
318{
319  size_t i;
320  goto_list *sp;
321
322  for (i = 0; i < nLA; i++)
323    for (sp = lookback[i]; sp; sp = sp->next)
324      bitset_or (LA[i], LA[i], F[sp->value]);
325
326  /* Free LOOKBACK. */
327  for (i = 0; i < nLA; i++)
328    LIST_FREE (goto_list, lookback[i]);
329
330  free (lookback);
331  bitsetv_free (F);
332}
333
334
335/*-----------------------------------------------------.
336| Count the number of look-ahead tokens required for S |
337| (N_LOOK_AHEAD_TOKENS member).                        |
338`-----------------------------------------------------*/
339
340static int
341state_look_ahead_tokens_count (state *s)
342{
343  int k;
344  int n_look_ahead_tokens = 0;
345  reductions *rp = s->reductions;
346  transitions *sp = s->transitions;
347
348  /* We need a look-ahead either to distinguish different
349     reductions (i.e., there are two or more), or to distinguish a
350     reduction from a shift.  Otherwise, it is straightforward,
351     and the state is `consistent'.  */
352  if (rp->num > 1
353      || (rp->num == 1 && sp->num &&
354	  !TRANSITION_IS_DISABLED (sp, 0) && TRANSITION_IS_SHIFT (sp, 0)))
355    n_look_ahead_tokens += rp->num;
356  else
357    s->consistent = 1;
358
359  for (k = 0; k < sp->num; k++)
360    if (!TRANSITION_IS_DISABLED (sp, k) && TRANSITION_IS_ERROR (sp, k))
361      {
362	s->consistent = 0;
363	break;
364      }
365
366  return n_look_ahead_tokens;
367}
368
369
370/*-----------------------------------------------------.
371| Compute LA, NLA, and the look_ahead_tokens members.  |
372`-----------------------------------------------------*/
373
374static void
375initialize_LA (void)
376{
377  state_number i;
378  bitsetv pLA;
379
380  /* Compute the total number of reductions requiring a look-ahead.  */
381  nLA = 0;
382  for (i = 0; i < nstates; i++)
383    nLA += state_look_ahead_tokens_count (states[i]);
384  /* Avoid having to special case 0.  */
385  if (!nLA)
386    nLA = 1;
387
388  pLA = LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
389  lookback = xcalloc (nLA, sizeof *lookback);
390
391  /* Initialize the members LOOK_AHEAD_TOKENS for each state whose reductions
392     require look-ahead tokens.  */
393  for (i = 0; i < nstates; i++)
394    {
395      int count = state_look_ahead_tokens_count (states[i]);
396      if (count)
397	{
398	  states[i]->reductions->look_ahead_tokens = pLA;
399	  pLA += count;
400	}
401    }
402}
403
404
405/*----------------------------------------------.
406| Output the look-ahead tokens for each state.  |
407`----------------------------------------------*/
408
409static void
410look_ahead_tokens_print (FILE *out)
411{
412  state_number i;
413  int j, k;
414  fprintf (out, "Look-ahead tokens: BEGIN\n");
415  for (i = 0; i < nstates; ++i)
416    {
417      reductions *reds = states[i]->reductions;
418      bitset_iterator iter;
419      int n_look_ahead_tokens = 0;
420
421      if (reds->look_ahead_tokens)
422	for (k = 0; k < reds->num; ++k)
423	  if (reds->look_ahead_tokens[k])
424	    ++n_look_ahead_tokens;
425
426      fprintf (out, "State %d: %d look-ahead tokens\n",
427	       i, n_look_ahead_tokens);
428
429      if (reds->look_ahead_tokens)
430	for (j = 0; j < reds->num; ++j)
431	  BITSET_FOR_EACH (iter, reds->look_ahead_tokens[j], k, 0)
432	  {
433	    fprintf (out, "   on %d (%s) -> rule %d\n",
434		     k, symbols[k]->tag,
435		     reds->rules[j]->number);
436	  };
437    }
438  fprintf (out, "Look-ahead tokens: END\n");
439}
440
441void
442lalr (void)
443{
444  initialize_LA ();
445  set_goto_map ();
446  initialize_F ();
447  build_relations ();
448  compute_FOLLOWS ();
449  compute_look_ahead_tokens ();
450
451  if (trace_flag & trace_sets)
452    look_ahead_tokens_print (stderr);
453}
454
455
456void
457lalr_free (void)
458{
459  state_number s;
460  for (s = 0; s < nstates; ++s)
461    states[s]->reductions->look_ahead_tokens = NULL;
462  bitsetv_free (LA);
463}
464