![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to state.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / GNUtools / bison|
Return to state.h CVS log | Up to [Apple XNU] / GNUtools / bison |
1.1 root 1: /* Type definitions for nondeterministic finite state machine for bison,
2: Copyright (C) 1984, 1989 Free Software Foundation, Inc.
3:
4: This file is part of Bison, the GNU Compiler Compiler.
5:
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.
10:
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.
15:
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, 675 Mass Ave, Cambridge, MA 02139, USA. */
19:
20:
21: /* These type definitions are used to represent a nondeterministic
22: finite state machine that parses the specified grammar.
23: This information is generated by the function generate_states
24: in the file LR0.
25:
26: Each state of the machine is described by a set of items --
27: particular positions in particular rules -- that are the possible
28: places where parsing could continue when the machine is in this state.
29: These symbols at these items are the allowable inputs that can follow now.
30:
31: A core represents one state. States are numbered in the number field.
32: When generate_states is finished, the starting state is state 0
33: and nstates is the number of states. (A transition to a state
34: whose state number is nstates indicates termination.) All the cores
35: are chained together and first_state points to the first one (state 0).
36:
37: For each state there is a particular symbol which must have been the
38: last thing accepted to reach that state. It is the accessing_symbol
39: of the core.
40:
41: Each core contains a vector of nitems items which are the indices
42: in the ritems vector of the items that are selected in this state.
43:
44: The link field is used for chaining buckets that hash states by
45: their itemsets. This is for recognizing equivalent states and
46: combining them when the states are generated.
47:
48: The two types of transitions are shifts (push the lookahead token
49: and read another) and reductions (combine the last n things on the
50: stack via a rule, replace them with the symbol that the rule derives,
51: and leave the lookahead token alone). When the states are generated,
52: these transitions are represented in two other lists.
53:
54: Each shifts structure describes the possible shift transitions out
55: of one state, the state whose number is in the number field.
56: The shifts structures are linked through next and first_shift points to them.
57: Each contains a vector of numbers of the states that shift transitions
58: can go to. The accessing_symbol fields of those states' cores say what kind
59: of input leads to them.
60:
61: A shift to state zero should be ignored. Conflict resolution
62: deletes shifts by changing them to zero.
63:
64: Each reductions structure describes the possible reductions at the state
65: whose number is in the number field. The data is a list of nreds rules,
66: represented by their rule numbers. first_reduction points to the list
67: of these structures.
68:
69: Conflict resolution can decide that certain tokens in certain
70: states should explicitly be errors (for implementing %nonassoc).
71: For each state, the tokens that are errors for this reason
72: are recorded in an errs structure, which has the state number
73: in its number field. The rest of the errs structure is full
74: of token numbers.
75:
76: There is at least one shift transition present in state zero.
77: It leads to a next-to-final state whose accessing_symbol is
78: the grammar's start symbol. The next-to-final state has one shift
79: to the final state, whose accessing_symbol is zero (end of input).
80: The final state has one shift, which goes to the termination state
81: (whose number is nstates-1).
82: The reason for the extra state at the end is to placate the parser's
83: strategy of making all decisions one token ahead of its actions. */
84:
85:
86: typedef
87: struct core
88: {
89: struct core *next;
90: struct core *link;
91: short number;
92: short accessing_symbol;
93: short nitems;
94: short items[1];
95: }
96: core;
97:
98:
99:
100: typedef
101: struct shifts
102: {
103: struct shifts *next;
104: short number;
105: short nshifts;
106: short shifts[1];
107: }
108: shifts;
109:
110:
111:
112: typedef
113: struct errs
114: {
115: short nerrs;
116: short errs[1];
117: }
118: errs;
119:
120:
121:
122: typedef
123: struct reductions
124: {
125: struct reductions *next;
126: short number;
127: short nreds;
128: short rules[1];
129: }
130: reductions;
131:
132:
133:
134: extern int nstates;
135: extern core *first_state;
136: extern shifts *first_shift;
137: extern reductions *first_reduction;
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.