ce076d4d3c887b04f6fc082de49ea9a29b50a5ac
1 /* Compute look-ahead criteria for bison,
2 Copyright 1984, 1986, 1989, 2000 Free Software Foundation, Inc.
4 This file is part of Bison, the GNU Compiler Compiler.
6 Bison is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 Bison is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with Bison; see the file COPYING. If not, write to
18 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
22 /* Compute how to make the finite state machine deterministic; find
23 which rules need lookahead in each state, and which lookahead
24 tokens they accept. */
35 /* All the decorated states, indexed by the state number. Warning:
36 there is a state_TABLE in LR0.c, but it is different and static.
38 state_t
*state_table
= NULL
;
48 extern void berror
PARAMS ((const char *));
54 static short **includes
;
55 static shorts
**lookback
;
58 static short *VERTICES
;
75 INDEX
[i
] = height
= top
;
77 base
= F
+ i
* tokensetsize
;
78 fp3
= base
+ tokensetsize
;
83 while ((j
= *rp
++) >= 0)
88 if (INDEX
[i
] > INDEX
[j
])
92 fp2
= F
+ j
* tokensetsize
;
99 if (INDEX
[i
] == height
)
110 fp2
= F
+ j
* tokensetsize
;
120 digraph (short **relation
)
124 infinity
= ngotos
+ 2;
125 INDEX
= XCALLOC (short, ngotos
+ 1);
126 VERTICES
= XCALLOC (short, ngotos
+ 1);
131 for (i
= 0; i
< ngotos
; i
++)
134 for (i
= 0; i
< ngotos
; i
++)
136 if (INDEX
[i
] == 0 && R
[i
])
145 set_state_table (void)
147 /* NSTATES + 1 because lookahead for the pseudo state number NSTATES
148 might be used (see conflicts.c). It is too opaque for me to
149 provide a probably less hacky implementation. --akim */
150 state_table
= XCALLOC (state_t
, nstates
+ 1);
154 for (sp
= first_state
; sp
; sp
= sp
->next
)
156 state_table
[sp
->number
].state
= sp
;
157 state_table
[sp
->number
].accessing_symbol
= sp
->accessing_symbol
;
163 for (sp
= first_shift
; sp
; sp
= sp
->next
)
164 state_table
[sp
->number
].shift_table
= sp
;
169 for (rp
= first_reduction
; rp
; rp
= rp
->next
)
170 state_table
[rp
->number
].reduction_table
= rp
;
173 /* Initializing the lookaheads members. Please note that it must be
174 performed after having set some of the other members which are
175 used below. Change with extreme caution. */
179 for (i
= 0; i
< nstates
; i
++)
182 reductions
*rp
= state_table
[i
].reduction_table
;
183 shifts
*sp
= state_table
[i
].shift_table
;
185 state_table
[i
].lookaheads
= count
;
189 || (sp
&& !ISVAR (state_table
[sp
->shifts
[0]].accessing_symbol
))))
192 state_table
[i
].consistent
= 1;
195 for (k
= 0; k
< sp
->nshifts
; k
++)
196 if (state_table
[sp
->shifts
[k
]].accessing_symbol
197 == error_token_number
)
199 state_table
[i
].consistent
= 0;
203 state_table
[nstates
].lookaheads
= count
;
217 for (itemp
= ritem
; *itemp
; itemp
++)
243 size_t nLA
= state_table
[nstates
].lookaheads
;
247 LA
= XCALLOC (unsigned, nLA
* tokensetsize
);
248 LAruleno
= XCALLOC (short, nLA
);
249 lookback
= XCALLOC (shorts
*, nLA
);
252 for (i
= 0; i
< nstates
; i
++)
253 if (!state_table
[i
].consistent
)
254 if ((rp
= state_table
[i
].reduction_table
))
255 for (j
= 0; j
< rp
->nreds
; j
++)
256 *np
++ = rp
->rules
[j
];
271 goto_map
= XCALLOC (short, nvars
+ 1) - ntokens
;
272 temp_map
= XCALLOC (short, nvars
+ 1) - ntokens
;
275 for (sp
= first_shift
; sp
; sp
= sp
->next
)
277 for (i
= sp
->nshifts
- 1; i
>= 0; i
--)
279 symbol
= state_table
[sp
->shifts
[i
]].accessing_symbol
;
281 if (ISTOKEN (symbol
))
284 if (ngotos
== MAXSHORT
)
285 fatal (_("too many gotos (max %d)"), MAXSHORT
);
293 for (i
= ntokens
; i
< nsyms
; i
++)
299 for (i
= ntokens
; i
< nsyms
; i
++)
300 goto_map
[i
] = temp_map
[i
];
302 goto_map
[nsyms
] = ngotos
;
303 temp_map
[nsyms
] = ngotos
;
305 from_state
= XCALLOC (short, ngotos
);
306 to_state
= XCALLOC (short, ngotos
);
308 for (sp
= first_shift
; sp
; sp
= sp
->next
)
311 for (i
= sp
->nshifts
- 1; i
>= 0; i
--)
313 state2
= sp
->shifts
[i
];
314 symbol
= state_table
[state2
].accessing_symbol
;
316 if (ISTOKEN (symbol
))
319 k
= temp_map
[symbol
]++;
320 from_state
[k
] = state1
;
321 to_state
[k
] = state2
;
325 XFREE (temp_map
+ ntokens
);
330 /*----------------------------------------------------------.
331 | Map a state/symbol pair into its numeric representation. |
332 `----------------------------------------------------------*/
335 map_goto (int state
, int symbol
)
342 low
= goto_map
[symbol
];
343 high
= goto_map
[symbol
+ 1] - 1;
347 middle
= (low
+ high
) / 2;
348 s
= from_state
[middle
];
379 nwords
= ngotos
* tokensetsize
;
380 F
= XCALLOC (unsigned, nwords
);
382 reads
= XCALLOC (short *, ngotos
);
383 edge
= XCALLOC (short, ngotos
+ 1);
387 for (i
= 0; i
< ngotos
; i
++)
389 stateno
= to_state
[i
];
390 sp
= state_table
[stateno
].shift_table
;
396 for (j
= 0; j
< k
; j
++)
398 symbol
= state_table
[sp
->shifts
[j
]].accessing_symbol
;
401 SETBIT (rowp
, symbol
);
406 symbol
= state_table
[sp
->shifts
[j
]].accessing_symbol
;
407 if (nullable
[symbol
])
408 edge
[nedges
++] = map_goto (stateno
, symbol
);
413 reads
[i
] = rp
= XCALLOC (short, nedges
+ 1);
415 for (j
= 0; j
< nedges
; j
++)
423 rowp
+= tokensetsize
;
428 for (i
= 0; i
< ngotos
; i
++)
440 add_lookback_edge (int stateno
, int ruleno
, int gotono
)
447 i
= state_table
[stateno
].lookaheads
;
448 k
= state_table
[stateno
+ 1].lookaheads
;
450 while (!found
&& i
< k
)
452 if (LAruleno
[i
] == ruleno
)
460 sp
= XCALLOC (shorts
, 1);
461 sp
->next
= lookback
[i
];
468 transpose (short **R_arg
, int n
)
477 nedges
= XCALLOC (short, n
);
479 for (i
= 0; i
< n
; i
++)
489 new_R
= XCALLOC (short *, n
);
490 temp_R
= XCALLOC (short *, n
);
492 for (i
= 0; i
< n
; i
++)
497 sp
= XCALLOC (short, k
+ 1);
506 for (i
= 0; i
< n
; i
++)
512 *temp_R
[*sp
++]++ = i
;
523 build_relations (void)
541 short **new_includes
;
543 includes
= XCALLOC (short *, ngotos
);
544 edge
= XCALLOC (short, ngotos
+ 1);
545 states
= XCALLOC (short, maxrhs
+ 1);
547 for (i
= 0; i
< ngotos
; i
++)
550 state1
= from_state
[i
];
551 symbol1
= state_table
[to_state
[i
]].accessing_symbol
;
553 for (rulep
= derives
[symbol1
]; *rulep
> 0; rulep
++)
559 for (rp
= ritem
+ rrhs
[*rulep
]; *rp
> 0; rp
++)
562 sp
= state_table
[stateno
].shift_table
;
565 for (j
= 0; j
< k
; j
++)
567 stateno
= sp
->shifts
[j
];
568 if (state_table
[stateno
].accessing_symbol
== symbol2
)
572 states
[length
++] = stateno
;
575 if (!state_table
[stateno
].consistent
)
576 add_lookback_edge (stateno
, *rulep
, i
);
584 /* JF added rp>=ritem && I hope to god its right! */
585 if (rp
>= ritem
&& ISVAR (*rp
))
587 stateno
= states
[--length
];
588 edge
[nedges
++] = map_goto (stateno
, *rp
);
597 includes
[i
] = shortp
= XCALLOC (short, nedges
+ 1);
598 for (j
= 0; j
< nedges
; j
++)
604 new_includes
= transpose (includes
, ngotos
);
606 for (i
= 0; i
< ngotos
; i
++)
612 includes
= new_includes
;
621 compute_FOLLOWS (void)
627 for (i
= 0; i
< ngotos
; i
++)
638 compute_lookaheads (void)
647 shorts
*sptmp
; /* JF */
650 for (i
= 0; i
< state_table
[nstates
].lookaheads
; i
++)
652 fp3
= rowp
+ tokensetsize
;
653 for (sp
= lookback
[i
]; sp
; sp
= sp
->next
)
656 fp2
= F
+ tokensetsize
* sp
->value
;
664 for (i
= 0; i
< state_table
[nstates
].lookaheads
; i
++)
666 /* JF removed ref to freed storage */
667 for (sp
= lookback
[i
]; sp
; sp
= sptmp
)
682 tokensetsize
= WORDSIZE (ntokens
);
691 compute_lookaheads ();