]> git.saurik.com Git - bison.git/blame - src/state.h
Renaming file to glr.c.
[bison.git] / src / state.h
CommitLineData
d0fb370f 1/* Type definitions for nondeterministic finite state machine for bison,
d954473d 2 Copyright 1984, 1989, 2000, 2001 Free Software Foundation, Inc.
d0fb370f 3
a70083a3 4 This file is part of Bison, the GNU Compiler Compiler.
d0fb370f 5
a70083a3
AD
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)
9 any later version.
d0fb370f 10
a70083a3
AD
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.
d0fb370f 15
a70083a3
AD
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. */
d0fb370f
RS
20
21
22/* These type definitions are used to represent a nondeterministic
a70083a3
AD
23 finite state machine that parses the specified grammar. This
24 information is generated by the function generate_states in the
25 file LR0.
26
27 Each state of the machine is described by a set of items --
28 particular positions in particular rules -- that are the possible
29 places where parsing could continue when the machine is in this
30 state. These symbols at these items are the allowable inputs that
31 can follow now.
32
9801d40c 33 A core represents one state. States are numbered in the NUMBER
a70083a3 34 field. When generate_states is finished, the starting state is
9801d40c
AD
35 state 0 and NSTATES is the number of states. (FIXME: This sentence
36 is no longer true: A transition to a state whose state number is
37 NSTATES indicates termination.) All the cores are chained together
38 and FIRST_STATE points to the first one (state 0).
a70083a3
AD
39
40 For each state there is a particular symbol which must have been
41 the last thing accepted to reach that state. It is the
9801d40c 42 ACCESSING_SYMBOL of the core.
a70083a3 43
5123689b 44 Each core contains a vector of NITEMS items which are the indices
9801d40c 45 in the RITEMS vector of the items that are selected in this state.
a70083a3 46
db8837cb 47 The link field is used for chaining symbols that hash states by
a70083a3
AD
48 their itemsets. This is for recognizing equivalent states and
49 combining them when the states are generated.
50
51 The two types of transitions are shifts (push the lookahead token
52 and read another) and reductions (combine the last n things on the
53 stack via a rule, replace them with the symbol that the rule
54 derives, and leave the lookahead token alone). When the states are
55 generated, these transitions are represented in two other lists.
56
57 Each shifts structure describes the possible shift transitions out
58 of one state, the state whose number is in the number field. The
59 shifts structures are linked through next and first_shift points to
60 them. Each contains a vector of numbers of the states that shift
61 transitions can go to. The accessing_symbol fields of those
62 states' cores say what kind of input leads to them.
63
64 A shift to state zero should be ignored. Conflict resolution
65 deletes shifts by changing them to zero.
66
67 Each reductions structure describes the possible reductions at the
68 state whose number is in the number field. The data is a list of
69 nreds rules, represented by their rule numbers. first_reduction
70 points to the list of these structures.
71
72 Conflict resolution can decide that certain tokens in certain
73 states should explicitly be errors (for implementing %nonassoc).
74 For each state, the tokens that are errors for this reason are
75 recorded in an errs structure, which has the state number in its
76 number field. The rest of the errs structure is full of token
77 numbers.
78
79 There is at least one shift transition present in state zero. It
80 leads to a next-to-final state whose accessing_symbol is the
81 grammar's start symbol. The next-to-final state has one shift to
82 the final state, whose accessing_symbol is zero (end of input).
83 The final state has one shift, which goes to the termination state
84 (whose number is nstates-1). The reason for the extra state at the
85 end is to placate the parser's strategy of making all decisions one
86 token ahead of its actions. */
87
88#ifndef STATE_H_
89# define STATE_H_
90
c0263492 91# include "bitsetv.h"
aa2aab3c 92
aa2aab3c
AD
93/*---------.
94| Shifts. |
95`---------*/
96
a70083a3
AD
97typedef struct shifts
98{
a70083a3
AD
99 short nshifts;
100 short shifts[1];
aa2aab3c
AD
101} shifts;
102
2cec70b9 103shifts *shifts_new PARAMS ((int n));
d954473d
AD
104
105
b608206e
AD
106/* What is the symbol which is shifted by SHIFTS->shifts[Shift]? Can
107 be a token (amongst which the error token), or non terminals in
108 case of gotos. */
109
110#define SHIFT_SYMBOL(Shifts, Shift) \
29e88316 111 (states[Shifts->shifts[Shift]]->accessing_symbol)
b608206e 112
aa2aab3c
AD
113/* Is the SHIFTS->shifts[Shift] a real shift? (as opposed to gotos.) */
114
115#define SHIFT_IS_SHIFT(Shifts, Shift) \
b608206e 116 (ISTOKEN (SHIFT_SYMBOL (Shifts, Shift)))
aa2aab3c
AD
117
118/* Is the SHIFTS->shifts[Shift] a goto?. */
119
120#define SHIFT_IS_GOTO(Shifts, Shift) \
121 (!SHIFT_IS_SHIFT (Shifts, Shift))
122
123/* Is the SHIFTS->shifts[Shift] then handling of the error token?. */
124
125#define SHIFT_IS_ERROR(Shifts, Shift) \
007a50a4 126 (SHIFT_SYMBOL (Shifts, Shift) == errtoken->number)
aa2aab3c 127
9839bbe5
AD
128/* When resolving a SR conflicts, if the reduction wins, the shift is
129 disabled. */
130
131#define SHIFT_DISABLE(Shifts, Shift) \
132 (Shifts->shifts[Shift] = 0)
133
134#define SHIFT_IS_DISABLED(Shifts, Shift) \
135 (Shifts->shifts[Shift] == 0)
136
aa2aab3c
AD
137
138/*-------.
139| Errs. |
140`-------*/
a70083a3
AD
141
142typedef struct errs
143{
144 short nerrs;
145 short errs[1];
aa2aab3c 146} errs;
a70083a3 147
2cec70b9
AD
148errs *errs_new PARAMS ((int n));
149errs *errs_dup PARAMS ((errs *src));
f59c437a 150
a70083a3 151
aa2aab3c
AD
152/*-------------.
153| Reductions. |
154`-------------*/
a70083a3
AD
155
156typedef struct reductions
157{
a70083a3
AD
158 short nreds;
159 short rules[1];
aa2aab3c 160} reductions;
d0fb370f 161
80dac38c 162reductions *reductions_new PARAMS ((int n));
f693ad14
AD
163
164
165/*----------.
166| State_t. |
167`----------*/
168
169typedef struct state_s
170{
171 struct state_s *next;
172 struct state_s *link;
173
174 short number;
a49aecd5 175 symbol_number_t accessing_symbol;
f693ad14
AD
176 shifts *shifts;
177 reductions *reductions;
178 errs *errs;
179
180 /* Nonzero if no lookahead is needed to decide what to do in state S. */
181 char consistent;
182
183 /* Used in LALR, not LR(0). */
3877f72b 184 int nlookaheads;
c0263492
AD
185 bitsetv lookaheads;
186 rule_t **lookaheads_rule;
f693ad14 187
b408954b
AD
188 /* If some conflicts were solved thanks to precedence/associativity,
189 a human readable description of the resolution. */
190 const char *solved_conflicts;
191
192 /* Its items. Must be last, since ITEMS can be arbitrarily large.
193 */
0c2d3f4c 194 unsigned short nitems;
62a3e4f0 195 item_number_t items[1];
f693ad14
AD
196} state_t;
197
198#define STATE_ALLOC(Nitems) \
199 (state_t *) xcalloc ((unsigned) (sizeof (state_t) \
62a3e4f0 200 + (Nitems - 1) * sizeof (item_number_t)), 1)
f693ad14 201
10e5b8bd
AD
202/* Print on OUT all the lookaheads such that this STATE wants to
203 reduce this RULE. */
204
205void state_rule_lookaheads_print PARAMS ((state_t *state, rule_t *rule,
206 FILE *out));
207
a70083a3 208#endif /* !STATE_H_ */