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