]> git.saurik.com Git - bison.git/blame - src/state.h
* src/output.c (prepare): Drop the muscle `ntbase' which
[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
33 A core represents one state. States are numbered in the number
34 field. When generate_states is finished, the starting state is
35 state 0 and nstates is the number of states. (A transition to a
36 state whose state number is nstates indicates termination.) All
37 the cores are chained together and first_state points to the first
38 one (state 0).
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
42 accessing_symbol of the core.
43
44 Each core contains a vector of nitems items which are the indices
45 in the ritems vector of the items that are selected in this state.
46
47 The link field is used for chaining buckets that hash states by
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
aa2aab3c 91
aa2aab3c
AD
92/*---------.
93| Shifts. |
94`---------*/
95
a70083a3
AD
96typedef struct shifts
97{
a70083a3
AD
98 short nshifts;
99 short shifts[1];
aa2aab3c
AD
100} shifts;
101
a70083a3 102
f59c437a
AD
103#define SHIFTS_ALLOC(Nshifts) \
104 (shifts *) xcalloc ((unsigned) (sizeof (shifts) \
105 + (Nshifts - 1) * sizeof (short)), 1)
a70083a3 106
d954473d
AD
107shifts * shifts_new PARAMS ((int n));
108
109
b608206e
AD
110/* What is the symbol which is shifted by SHIFTS->shifts[Shift]? Can
111 be a token (amongst which the error token), or non terminals in
112 case of gotos. */
113
114#define SHIFT_SYMBOL(Shifts, Shift) \
f693ad14 115 (state_table[Shifts->shifts[Shift]]->accessing_symbol)
b608206e 116
aa2aab3c
AD
117/* Is the SHIFTS->shifts[Shift] a real shift? (as opposed to gotos.) */
118
119#define SHIFT_IS_SHIFT(Shifts, Shift) \
b608206e 120 (ISTOKEN (SHIFT_SYMBOL (Shifts, Shift)))
aa2aab3c
AD
121
122/* Is the SHIFTS->shifts[Shift] a goto?. */
123
124#define SHIFT_IS_GOTO(Shifts, Shift) \
125 (!SHIFT_IS_SHIFT (Shifts, Shift))
126
127/* Is the SHIFTS->shifts[Shift] then handling of the error token?. */
128
129#define SHIFT_IS_ERROR(Shifts, Shift) \
b608206e 130 (SHIFT_SYMBOL (Shifts, Shift) == error_token_number)
aa2aab3c 131
9839bbe5
AD
132/* When resolving a SR conflicts, if the reduction wins, the shift is
133 disabled. */
134
135#define SHIFT_DISABLE(Shifts, Shift) \
136 (Shifts->shifts[Shift] = 0)
137
138#define SHIFT_IS_DISABLED(Shifts, Shift) \
139 (Shifts->shifts[Shift] == 0)
140
aa2aab3c
AD
141
142/*-------.
143| Errs. |
144`-------*/
a70083a3
AD
145
146typedef struct errs
147{
148 short nerrs;
149 short errs[1];
aa2aab3c 150} errs;
a70083a3 151
f59c437a
AD
152#define ERRS_ALLOC(Nerrs) \
153 (errs *) xcalloc ((unsigned) (sizeof (errs) \
154 + (Nerrs - 1) * sizeof (short)), 1)
155
a70083a3 156
aa2aab3c
AD
157/*-------------.
158| Reductions. |
159`-------------*/
a70083a3
AD
160
161typedef struct reductions
162{
a70083a3
AD
163 short nreds;
164 short rules[1];
aa2aab3c 165} reductions;
d0fb370f 166
f59c437a
AD
167#define REDUCTIONS_ALLOC(Nreductions) \
168 (reductions *) xcalloc ((unsigned) (sizeof (reductions) \
169 + (Nreductions - 1) * sizeof (short)), 1)
170
f693ad14
AD
171
172
173/*----------.
174| State_t. |
175`----------*/
176
177typedef struct state_s
178{
179 struct state_s *next;
180 struct state_s *link;
181
182 short number;
183 short accessing_symbol;
184 shifts *shifts;
185 reductions *reductions;
186 errs *errs;
187
188 /* Nonzero if no lookahead is needed to decide what to do in state S. */
189 char consistent;
190
191 /* Used in LALR, not LR(0). */
3877f72b
AD
192 /* Pseudo pointer into LA. */
193 short lookaheadsp;
194 int nlookaheads;
f693ad14
AD
195
196 /* Its items. */
197 short nitems;
198 short items[1];
199} state_t;
200
201#define STATE_ALLOC(Nitems) \
202 (state_t *) xcalloc ((unsigned) (sizeof (state_t) \
203 + (Nitems - 1) * sizeof (short)), 1)
204
a70083a3 205#endif /* !STATE_H_ */