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 NFA_H
30 #define NFA_H
31 
32 #include <QMap>
33 #include <QHash>
34 #include <QString>
35 #include <QVector>
36 #include <QDebug>
37 #include <QStack>
38 #include <QByteArray>
39 
40 #include "global.h"
41 
42 typedef QHash<InputType, int> TransitionMap;
43 
44 struct State
45 {
46     QString symbol;
47     TransitionMap transitions;
48 };
49 
50 inline QDataStream &operator<<(QDataStream &stream, const State &state)
51 {
52     return stream << state.symbol << state.transitions;
53 }
54 
55 inline QDataStream &operator>>(QDataStream &stream, State &state)
56 {
57     return stream >> state.symbol >> state.transitions;
58 }
59 
60 struct DFA : public QVector<State>
61 {
62     void debug() const;
63     DFA minimize() const;
64 };
65 
66 class NFA
67 {
68 public:
69     static NFA createSingleInputNFA(InputType input);
70     static NFA createSymbolNFA(const QString &symbol);
71     static NFA createAlternatingNFA(const NFA &a, const NFA &b);
72     static NFA createConcatenatingNFA(const NFA &a, const NFA &b);
73     static NFA createOptionalNFA(const NFA &a);
74 
75     // convenience
76     static NFA createStringNFA(const QByteArray &str);
77     static NFA createSetNFA(const QSet<InputType> &set);
78     static NFA createZeroOrOneNFA(const NFA &a);
79     static NFA applyQuantity(const NFA &a, int minOccurrences, int maxOccurrences);
80 
81     void setTerminationSymbol(const QString &symbol);
82 
83     DFA toDFA() const;
84 
isEmpty()85     inline bool isEmpty() const { return states.isEmpty(); }
stateCount()86     inline int stateCount() const { return states.count(); }
87 
88     void debug();
89 
90 private:
91     void initialize(int size);
92     void addTransition(int from, InputType input, int to);
93     void copyFrom(const NFA &other, int baseState);
94 
95     void initializeFromPair(const NFA &a, const NFA &b,
96                             int *initialA, int *finalA,
97                             int *initialB, int *finalB);
98 
99     QSet<int> epsilonClosure(const QSet<int> &initialClosure) const;
100 
assertValidState(int state)101     inline void assertValidState(int state)
102     { Q_UNUSED(state); Q_ASSERT(state >= 0); Q_ASSERT(state < states.count()); }
103 
104 #if defined(AUTOTEST)
105 public:
106 #endif
107     int initialState;
108     int finalState;
109 
110     QVector<State> states;
111 };
112 
113 #endif // NFA_H
114 
115