1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
|
#ifndef _INCLUDED_STATE_H_
#define _INCLUDED_STATE_H_
#include <iosfwd>
#include <vector>
#include <set>
#include "../statetype/statetype.h"
#include "../next/next.h"
#include "../srconflict/srconflict.h"
#include "../rrconflict/rrconflict.h"
class Item;
class Production;
class StateItem;
class Rules;
class State
{
using Vector = std::vector<State *>;
public:
using ConstIter = Vector::const_iterator;
private:
friend std::ostream &operator<<(std::ostream &out,
State const *state);
StateItem::Vector d_itemVector;
size_t d_nKernelItems;
std::vector<size_t> d_reducible; // d_itemVector offsets containing
// reducible items
size_t d_nTransitions; // elements in d_nextVector minus
// removed elements because of
// conflicts
size_t d_nReductions; // elements in d_reducible minus
// reductions having empty LA-sets
size_t d_defaultReducible; // the d_reducible index of
// the reduction to use as default
// (or npos)
size_t d_maxLAsize; // the default reduction becomes
// the one having the largest
// LAset size
size_t d_summedLAsize; // sum of all lookaheadsets of all
// non-default reductions.
Next::Vector d_nextVector; // Vector of Next elements
// describing where to transit to
// next.
size_t d_idx; // index of this state in the
// vector of States
size_t d_nTerminalTransitions;
SRConflict d_srConflict;
RRConflict d_rrConflict;
StateType d_stateType;
static Vector s_state;
static State *s_acceptState;
static std::ostream &(State::*s_insert)(std::ostream &out) const;
public:
bool isAcceptState() const;
bool nextContains(Next::ConstIter *iter,
Symbol const *symbol) const;
size_t idx() const;
size_t nextOn(Symbol const *token) const;
// All reduction members operate with indices in d_reducible,
// so *not* with d_stateItem indices
size_t defaultReduction() const; // def. reduction idx or npos
StateItem const *reduction(size_t idx) const; // 0 or reduction item
size_t reductions() const; // number of reductions
size_t reductionsLAsize() const; // summed LA set sizes of all
// non-default reductions
Symbol const *nextTerminal(size_t *idx) const;
// Next terminal at
// d_next[*idx], 0 if none
size_t terminalTransitions() const;
size_t transitions() const;
Next::Vector const &next() const;
static size_t nStates();
static void allStates();
// defines all grammar-states and
// lookahead sets
static void define(Rules const &rules);
static ConstIter begin(); // iterator to the first State *
static ConstIter end(); // and beyond the last
int type() const; // StateType accessor
private:
State(size_t idx);
void addDependents(Symbol const *symbol, size_t itemIdx);
// from notreducible from setitems: determine all
// dependent state items and X-link d_itemVector
// and d_nextVector
void addKernelItem(StateItem const &stateItem);
void addNext(Symbol const *symbol, size_t idx);
// from notreducible from setitems:
// add a new Next element to d_nextVector
void addState(Item::Vector const &kernel);
void construct(); // construct a state, and by recursion all other
// states as well
size_t findKernel(Item::Vector const &kernel) const;
void notReducible(size_t idx);
// handle items in setItems() that aren't
// reducible
void setItems(); // fill d_itemVector with this state's items
// add the productions of `symbol' to d_itemVector,
// make them depend on d_itemVector[idx]
void addProductions(Symbol const *symbol);
Next::ConstIter nextFind(Symbol const *symbol) const;
std::ostream &insertStd(std::ostream &out) const;
std::ostream &insertExt(std::ostream &out) const;
std::ostream &skipInsertion(std::ostream &out) const;
static void initialState();
static State &newState();
void nextState(Next &next);
bool hasKernel(Item::Vector const &kernel) const;
void checkConflicts();
void summarizeActions();
void showSRConflicts(Rules const &rules) const;
void showRRConflicts(Rules const &rules) const;
static void determineLAsets();
void computeLAsets();
void distributeLAsetOf(StateItem &item);
void inspectTransitions(std::set<size_t> &todo);
};
#include "state.f"
#endif
|
