![[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 [Research Unix] / researchv10dc / cmd / bison|
Return to state.h CVS log | Up to [Research Unix] / researchv10dc / cmd / bison |
1.1 root 1: /* Type definitions for nondeterministic finite state machine for bison,
2: Copyright (C) 1984 Bob Corbett and Free Software Foundation, Inc.
3:
4: BISON is distributed in the hope that it will be useful, but WITHOUT ANY
5: WARRANTY. No author or distributor accepts responsibility to anyone
6: for the consequences of using it or for whether it serves any
7: particular purpose or works at all, unless he says so in writing.
8: Refer to the BISON General Public License for full details.
9:
10: Everyone is granted permission to copy, modify and redistribute BISON,
11: but only under the conditions described in the BISON General Public
12: License. A copy of this license is supposed to have been given to you
13: along with BISON so you can know your rights and responsibilities. It
14: should be in a file named COPYING. Among other things, the copyright
15: notice and this notice must be preserved on all copies.
16:
17: In other words, you are welcome to use, share and improve this program.
18: You are forbidden to forbid anyone else to use, share and improve
19: what you give them. Help stamp out software-hoarding! */
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, and for which there is no core structure).
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.