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