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

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