1 /* Compute lookahead criteria for Bison.
3 Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004, 2005,
4 2006, 2007 Free Software Foundation, Inc.
6 This file is part of Bison, the GNU Compiler Compiler.
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)
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.
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. */
24 /* Compute how to make the finite state machine deterministic; find
25 which rules need lookahead in each state, and which lookahead
26 tokens they accept. */
46 goto_number
*goto_map
;
47 static goto_number ngotos
;
48 state_number
*from_state
;
49 state_number
*to_state
;
51 /* Linked list of goto numbers. */
52 typedef struct goto_list
54 struct goto_list
*next
;
59 /* LA is an NLA 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,
64 static bitsetv LA
= NULL
;
68 /* And for the famous F variable, which name is so descriptive that a
69 comment is hardly needed. <grin>. */
70 static bitsetv F
= NULL
;
72 static goto_number
**includes
;
73 static goto_list
**lookback
;
82 goto_number
*temp_map
;
84 goto_map
= xcalloc (nvars
+ 1, sizeof *goto_map
);
85 temp_map
= xnmalloc (nvars
+ 1, sizeof *temp_map
);
88 for (s
= 0; s
< nstates
; ++s
)
90 transitions
*sp
= states
[s
]->transitions
;
92 for (i
= sp
->num
- 1; i
>= 0 && TRANSITION_IS_GOTO (sp
, i
); --i
)
96 /* Abort if (ngotos + 1) would overflow. */
97 aver (ngotos
!= GOTO_NUMBER_MAXIMUM
);
99 goto_map
[TRANSITION_SYMBOL (sp
, i
) - ntokens
]++;
106 for (i
= ntokens
; i
< nsyms
; i
++)
108 temp_map
[i
- ntokens
] = k
;
109 k
+= goto_map
[i
- ntokens
];
112 for (i
= ntokens
; i
< nsyms
; i
++)
113 goto_map
[i
- ntokens
] = temp_map
[i
- ntokens
];
115 goto_map
[nsyms
- ntokens
] = ngotos
;
116 temp_map
[nsyms
- ntokens
] = ngotos
;
119 from_state
= xcalloc (ngotos
, sizeof *from_state
);
120 to_state
= xcalloc (ngotos
, sizeof *to_state
);
122 for (s
= 0; s
< nstates
; ++s
)
124 transitions
*sp
= states
[s
]->transitions
;
126 for (i
= sp
->num
- 1; i
>= 0 && TRANSITION_IS_GOTO (sp
, i
); --i
)
128 goto_number k
= temp_map
[TRANSITION_SYMBOL (sp
, i
) - ntokens
]++;
130 to_state
[k
] = sp
->states
[i
]->number
;
139 /*----------------------------------------------------------.
140 | Map a state/symbol pair into its numeric representation. |
141 `----------------------------------------------------------*/
144 map_goto (state_number s0
, symbol_number sym
)
151 low
= goto_map
[sym
- ntokens
];
152 high
= goto_map
[sym
- ntokens
+ 1] - 1;
157 middle
= (low
+ high
) / 2;
158 s
= from_state
[middle
];
172 goto_number
**reads
= xnmalloc (ngotos
, sizeof *reads
);
173 goto_number
*edge
= xnmalloc (ngotos
+ 1, sizeof *edge
);
174 goto_number nedges
= 0;
178 F
= bitsetv_create (ngotos
, ntokens
, BITSET_FIXED
);
180 for (i
= 0; i
< ngotos
; i
++)
182 state_number stateno
= to_state
[i
];
183 transitions
*sp
= states
[stateno
]->transitions
;
186 FOR_EACH_SHIFT (sp
, j
)
187 bitset_set (F
[i
], TRANSITION_SYMBOL (sp
, j
));
189 for (; j
< sp
->num
; j
++)
191 symbol_number sym
= TRANSITION_SYMBOL (sp
, j
);
192 if (nullable
[sym
- ntokens
])
193 edge
[nedges
++] = map_goto (stateno
, sym
);
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
;
207 relation_digraph (reads
, ngotos
, &F
);
209 for (i
= 0; i
< ngotos
; i
++)
218 add_lookback_edge (state
*s
, rule
*r
, goto_number gotono
)
220 int ri
= state_reduction_find (s
, r
);
221 goto_list
*sp
= xmalloc (sizeof *sp
);
222 sp
->next
= lookback
[(s
->reductions
->lookahead_tokens
- LA
) + ri
];
224 lookback
[(s
->reductions
->lookahead_tokens
- LA
) + ri
] = sp
;
230 build_relations (void)
232 goto_number
*edge
= xnmalloc (ngotos
+ 1, sizeof *edge
);
233 state_number
*states1
= xnmalloc (ritem_longest_rhs () + 1, sizeof *states1
);
236 includes
= xnmalloc (ngotos
, sizeof *includes
);
238 for (i
= 0; i
< ngotos
; i
++)
241 symbol_number symbol1
= states
[to_state
[i
]]->accessing_symbol
;
244 for (rulep
= derives
[symbol1
- ntokens
]; *rulep
; rulep
++)
248 item_number
const *rp
;
249 state
*s
= states
[from_state
[i
]];
250 states1
[0] = s
->number
;
252 for (rp
= (*rulep
)->rhs
; ! item_number_is_rule_number (*rp
); rp
++)
254 s
= transitions_to (s
->transitions
,
255 item_number_as_symbol_number (*rp
));
256 states1
[length
++] = s
->number
;
260 add_lookback_edge (s
, *rulep
, i
);
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. */
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
])
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
;
297 relation_transpose (&includes
, ngotos
);
303 compute_FOLLOWS (void)
307 relation_digraph (includes
, ngotos
, &F
);
309 for (i
= 0; i
< ngotos
; i
++)
317 compute_lookahead_tokens (void)
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
]);
327 for (i
= 0; i
< nLA
; i
++)
328 LIST_FREE (goto_list
, lookback
[i
]);
335 /*----------------------------------------------------.
336 | Count the number of lookahead tokens required for S |
337 | (N_LOOKAHEAD_TOKENS member). |
338 `----------------------------------------------------*/
341 state_lookahead_tokens_count (state
*s
)
343 int n_lookahead_tokens
= 0;
344 reductions
*rp
= s
->reductions
;
345 transitions
*sp
= s
->transitions
;
347 /* We need a lookahead either to distinguish different
348 reductions (i.e., there are two or more), or to distinguish a
349 reduction from a shift. Otherwise, it is straightforward,
350 and the state is `consistent'. There is no need to check that
351 transition 0 hasn't been disabled before checking if it is a
352 shift since transitions are only disabled during conflict
353 resolution, and that hasn't happened yet. */
354 aver (sp
->num
== 0 || !TRANSITION_IS_DISABLED (sp
, 0));
356 || (rp
->num
== 1 && sp
->num
&& TRANSITION_IS_SHIFT (sp
, 0)))
357 n_lookahead_tokens
+= rp
->num
;
361 return n_lookahead_tokens
;
365 /*----------------------------------------------------.
366 | Compute LA, NLA, and the lookahead_tokens members. |
367 `----------------------------------------------------*/
375 /* Compute the total number of reductions requiring a lookahead. */
377 for (i
= 0; i
< nstates
; i
++)
378 nLA
+= state_lookahead_tokens_count (states
[i
]);
379 /* Avoid having to special case 0. */
383 pLA
= LA
= bitsetv_create (nLA
, ntokens
, BITSET_FIXED
);
384 lookback
= xcalloc (nLA
, sizeof *lookback
);
386 /* Initialize the members LOOKAHEAD_TOKENS for each state whose reductions
387 require lookahead tokens. */
388 for (i
= 0; i
< nstates
; i
++)
390 int count
= state_lookahead_tokens_count (states
[i
]);
393 states
[i
]->reductions
->lookahead_tokens
= pLA
;
400 /*---------------------------------------------.
401 | Output the lookahead tokens for each state. |
402 `---------------------------------------------*/
405 lookahead_tokens_print (FILE *out
)
409 fprintf (out
, "Lookahead tokens: BEGIN\n");
410 for (i
= 0; i
< nstates
; ++i
)
412 reductions
*reds
= states
[i
]->reductions
;
413 bitset_iterator iter
;
414 int n_lookahead_tokens
= 0;
416 if (reds
->lookahead_tokens
)
417 for (k
= 0; k
< reds
->num
; ++k
)
418 if (reds
->lookahead_tokens
[k
])
419 ++n_lookahead_tokens
;
421 fprintf (out
, "State %d: %d lookahead tokens\n",
422 i
, n_lookahead_tokens
);
424 if (reds
->lookahead_tokens
)
425 for (j
= 0; j
< reds
->num
; ++j
)
426 BITSET_FOR_EACH (iter
, reds
->lookahead_tokens
[j
], k
, 0)
428 fprintf (out
, " on %d (%s) -> rule %d\n",
430 reds
->rules
[j
]->number
);
433 fprintf (out
, "Lookahead tokens: END\n");
444 compute_lookahead_tokens ();
446 if (trace_flag
& trace_sets
)
447 lookahead_tokens_print (stderr
);
452 lalr_update_state_numbers (state_number old_to_new
[], state_number nstates_old
)
454 goto_number ngotos_reachable
= 0;
455 symbol_number nonterminal
= 0;
456 aver (nsyms
== nvars
+ ntokens
);
459 for (i
= 0; i
< ngotos
; ++i
)
461 while (i
== goto_map
[nonterminal
])
462 goto_map
[nonterminal
++] = ngotos_reachable
;
463 /* If old_to_new[from_state[i]] = nstates_old, remove this goto
465 if (old_to_new
[from_state
[i
]] != nstates_old
)
467 /* from_state[i] is not removed, so it and thus to_state[i] are
468 reachable, so to_state[i] != nstates_old. */
469 aver (old_to_new
[to_state
[i
]] != nstates_old
);
470 from_state
[ngotos_reachable
] = old_to_new
[from_state
[i
]];
471 to_state
[ngotos_reachable
] = old_to_new
[to_state
[i
]];
476 while (nonterminal
<= nvars
)
478 aver (ngotos
== goto_map
[nonterminal
]);
479 goto_map
[nonterminal
++] = ngotos_reachable
;
481 ngotos
= ngotos_reachable
;
489 for (s
= 0; s
< nstates
; ++s
)
490 states
[s
]->reductions
->lookahead_tokens
= NULL
;