1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0
3
4#ifndef LALR_H
5#define LALR_H
6
7#include <QtCore/qset.h>
8#include <QtCore/qstack.h>
9#include <QtCore/qmap.h>
10#include <QtCore/qstring.h>
11#include <QtCore/qtextstream.h>
12#include <QtCore/qpair.h>
13
14#include <algorithm>
15#include <functional>
16#include <set>
17#include <list>
18
19class Rule;
20class State;
21class Grammar;
22class Item;
23class State;
24class Arrow;
25class Automaton;
26
27
28// names
29typedef std::list<QString>::iterator Name;
30typedef std::list<Name> NameList;
31typedef std::set<Name> NameSet;
32
33// items
34typedef std::list<Item> ItemList;
35typedef ItemList::iterator ItemPointer;
36
37// rules
38typedef std::list<Rule> debug_infot;
39typedef debug_infot::iterator RulePointer;
40typedef QMultiMap<Name, RulePointer> RuleMap;
41
42// states
43typedef std::list<State> StateList;
44typedef StateList::iterator StatePointer;
45
46// arrows
47typedef QMap<Name, StatePointer> Bundle;
48
49class Rule
50{
51public:
52 void clear ()
53 {
54 lhs = Name ();
55 rhs.clear ();
56 prec = Name ();
57 }
58
59public:
60 Name lhs;
61 NameList rhs;
62 Name prec;
63};
64
65class Lookback
66{
67public:
68 Lookback (StatePointer s, Name n):
69 state (s), nt (n) {}
70
71 inline bool operator == (const Lookback &other) const
72 { return state == other.state && nt == other.nt; }
73
74 inline bool operator != (const Lookback &other) const
75 { return state != other.state || nt != other.nt; }
76
77 bool operator < (const Lookback &other) const;
78
79public:
80 StatePointer state;
81 Name nt;
82};
83
84class Item
85{
86public:
87 inline NameList::iterator begin_rhs () const
88 { return rule->rhs.begin (); }
89
90 inline NameList::iterator end_rhs () const
91 { return rule->rhs.end (); }
92
93 inline bool operator == (const Item &other) const
94 { return rule == other.rule && dot == other.dot; }
95
96 inline bool operator != (const Item &other) const
97 { return rule != other.rule || dot != other.dot; }
98
99 inline bool isReduceItem () const
100 { return dot == rule->rhs.end (); }
101
102 Item next () const;
103
104public:
105 RulePointer rule;
106 NameList::iterator dot;
107};
108
109class State
110{
111public:
112 State (Grammar *grammar);
113
114 inline bool operator == (const State &other) const
115 { return kernel == other.kernel; }
116
117 inline bool operator != (const State &other) const
118 { return kernel != other.kernel; }
119
120 QPair<ItemPointer, bool> insert (const Item &item);
121 QPair<ItemPointer, bool> insertClosure (const Item &item);
122
123public: // attributes
124 ItemList kernel;
125 ItemList closure;
126 Bundle bundle;
127 QMap<Name, NameSet> reads;
128 QMap<Name, NameSet> follows;
129 RulePointer defaultReduce;
130};
131
132/////////////////////////////////////////////////////////////
133// digraph
134/////////////////////////////////////////////////////////////
135template <typename _Tp>
136class Node
137{
138public:
139 typedef std::set<Node<_Tp> > Repository;
140 typedef typename Repository::iterator iterator;
141 typedef typename std::list<iterator>::iterator edge_iterator;
142
143public:
144 static iterator get (_Tp data);
145
146 QPair<edge_iterator, bool> insertEdge (iterator other) const;
147
148 inline edge_iterator begin () const
149 { return outs.begin (); }
150
151 inline edge_iterator end () const
152 { return outs.end (); }
153
154 inline bool operator == (const Node<_Tp> &other) const
155 { return data == other.data; }
156
157 inline bool operator != (const Node<_Tp> &other) const
158 { return data != other.data; }
159
160 inline bool operator < (const Node<_Tp> &other) const
161 { return data < other.data; }
162
163 static inline iterator begin_nodes ()
164 { return repository ().begin (); }
165
166 static inline iterator end_nodes ()
167 { return repository ().end (); }
168
169 static Repository &repository ()
170 {
171 static Repository r;
172 return r;
173 }
174
175public: // attributes
176 mutable bool root;
177 mutable int dfn;
178 mutable _Tp data;
179 mutable std::list<iterator> outs;
180
181protected:
182 inline Node () {}
183
184 inline Node (_Tp d):
185 root (true), dfn (0), data (d) {}
186};
187
188template <typename _Tp>
189typename Node<_Tp>::iterator Node<_Tp>::get (_Tp data)
190{
191 Node<_Tp> tmp (data);
192 iterator it = repository ().find (tmp);
193
194 if (it != repository ().end ())
195 return it;
196
197 return repository ().insert (tmp).first;
198}
199
200template <typename _Tp>
201QPair<typename std::list<typename Node<_Tp>::iterator>::iterator, bool> Node<_Tp>::insertEdge(typename Node<_Tp>::iterator other) const
202{
203 edge_iterator it = std::find (outs.begin (), outs.end (), other);
204
205 if (it != outs.end ())
206 return qMakePair (it, false);
207
208 other->root = false;
209 return qMakePair (outs.insert (outs.end (), other), true);
210}
211
212/////////////////////////////////////////////////////////////
213// Grammar
214/////////////////////////////////////////////////////////////
215class Grammar
216{
217public:
218 Grammar ();
219
220 Name intern (const QString &id);
221 Name intern (const char *id) { return intern(id: QString::fromUtf8(utf8: id)); }
222
223 inline bool isTerminal (Name name) const
224 { return terminals.find (x: name) != terminals.end (); }
225
226 inline bool isNonTerminal (Name name) const
227 { return non_terminals.find (x: name) != non_terminals.end (); }
228
229 void buildRuleMap ();
230 void buildExtendedGrammar ();
231
232public:
233 QString merged_output;
234 QString table_name;
235 QString decl_file_name;
236 QString impl_file_name;
237 QString token_prefix;
238 std::list<QString> names;
239 Name start;
240 NameSet terminals;
241 NameSet non_terminals;
242 QMap<Name, QString> spells;
243 debug_infot rules;
244 RuleMap rule_map;
245 RulePointer goal;
246 Name tk_end;
247 Name accept_symbol;
248 NameSet declared_lhs;
249 int expected_shift_reduce;
250 int expected_reduce_reduce;
251
252 enum Assoc {
253 NonAssoc,
254 Left,
255 Right
256 };
257
258 struct TokenInfo {
259 Assoc assoc;
260 int prec;
261 };
262
263 QMap<Name, TokenInfo> token_info;
264 Assoc current_assoc;
265 int current_prec;
266};
267
268class Read
269{
270public:
271 inline Read () {}
272
273 inline Read (StatePointer s, Name n):
274 state (s), nt (n) {}
275
276 inline bool operator == (const Read &other) const
277 { return state == other.state && nt == other.nt; }
278
279 inline bool operator != (const Read &other) const
280 { return state != other.state || nt != other.nt; }
281
282 bool operator < (const Read &other) const;
283
284public:
285 StatePointer state;
286 Name nt;
287};
288
289class Include
290{
291public:
292 inline Include () {}
293
294 inline Include (StatePointer s, Name n):
295 state (s), nt (n) {}
296
297 inline bool operator == (const Include &other) const
298 { return state == other.state && nt == other.nt; }
299
300 inline bool operator != (const Include &other) const
301 { return state != other.state || nt != other.nt; }
302
303 bool operator < (const Include &other) const;
304
305public:
306 StatePointer state;
307 Name nt;
308};
309
310class Automaton
311{
312public:
313 Automaton (Grammar *g);
314
315 QPair<StatePointer, bool> internState (const State &state);
316
317 typedef Node<Read> ReadsGraph;
318 typedef ReadsGraph::iterator ReadNode;
319
320 typedef Node<Include> IncludesGraph;
321 typedef IncludesGraph::iterator IncludeNode;
322
323 void build ();
324 void buildNullables ();
325
326 void buildLookbackSets ();
327
328 void buildDirectReads ();
329 void buildReadsDigraph ();
330 void buildReads ();
331 void visitReadNode (ReadNode node);
332
333 void buildIncludesAndFollows ();
334 void buildIncludesDigraph ();
335 void visitIncludeNode (IncludeNode node);
336
337 void buildLookaheads ();
338
339 void buildDefaultReduceActions ();
340
341 void closure (StatePointer state);
342
343 int id (RulePointer rule);
344 int id (StatePointer state);
345 int id (Name name);
346
347 void dump (QTextStream &out, IncludeNode incl);
348 void dump (QTextStream &out, ReadNode rd);
349 void dump (QTextStream &out, const Lookback &lp);
350
351public: // ### private
352 Grammar *_M_grammar;
353 StateList states;
354 StatePointer start;
355 NameSet nullables;
356 QMultiMap<ItemPointer, Lookback> lookbacks;
357 QMap<ItemPointer, NameSet> lookaheads;
358
359private:
360 QStack<ReadsGraph::iterator> _M_reads_stack;
361 int _M_reads_dfn;
362
363 QStack<IncludesGraph::iterator> _M_includes_stack;
364 int _M_includes_dfn;
365};
366
367namespace std {
368bool operator < (Name a, Name b);
369bool operator < (StatePointer a, StatePointer b);
370bool operator < (ItemPointer a, ItemPointer b);
371}
372
373QTextStream &operator << (QTextStream &out, const Name &n);
374QTextStream &operator << (QTextStream &out, const Rule &r);
375QTextStream &operator << (QTextStream &out, const Item &item);
376QTextStream &operator << (QTextStream &out, const NameSet &ns);
377
378QT_BEGIN_NAMESPACE
379QTextStream &qerr();
380QTextStream &qout();
381QT_END_NAMESPACE
382
383#endif // LALR_H
384

source code of qtbase/src/tools/qlalr/lalr.h