]>
Commit | Line | Data |
---|---|---|
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 |
97 | typedef struct shifts |
98 | { | |
a70083a3 AD |
99 | short nshifts; |
100 | short shifts[1]; | |
aa2aab3c AD |
101 | } shifts; |
102 | ||
2cec70b9 | 103 | shifts *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 | |
142 | typedef struct errs | |
143 | { | |
144 | short nerrs; | |
145 | short errs[1]; | |
aa2aab3c | 146 | } errs; |
a70083a3 | 147 | |
2cec70b9 AD |
148 | errs *errs_new PARAMS ((int n)); |
149 | errs *errs_dup PARAMS ((errs *src)); | |
f59c437a | 150 | |
a70083a3 | 151 | |
aa2aab3c AD |
152 | /*-------------. |
153 | | Reductions. | | |
154 | `-------------*/ | |
a70083a3 AD |
155 | |
156 | typedef struct reductions | |
157 | { | |
a70083a3 AD |
158 | short nreds; |
159 | short rules[1]; | |
aa2aab3c | 160 | } reductions; |
d0fb370f | 161 | |
80dac38c | 162 | reductions *reductions_new PARAMS ((int n)); |
f693ad14 AD |
163 | |
164 | ||
165 | /*----------. | |
166 | | State_t. | | |
167 | `----------*/ | |
168 | ||
169 | typedef 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 | ||
205 | void state_rule_lookaheads_print PARAMS ((state_t *state, rule_t *rule, | |
206 | FILE *out)); | |
207 | ||
a70083a3 | 208 | #endif /* !STATE_H_ */ |