1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the utils of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #ifndef NFA_H

    43 #define NFA_H

    44 

    45 #include <QMap>

    46 #include <QHash>

    47 #include <QString>

    48 #include <QVector>

    49 #include <QDebug>

    50 #include <QStack>

    51 #include <QByteArray>

    52 

    53 #include "global.h"

    54 

    55 typedef QHash<InputType, int> TransitionMap;

    56 

    57 struct State

    58 {

    59     QString symbol;

    60     TransitionMap transitions;

    61 };

    62 

    63 inline QDataStream &operator<<(QDataStream &stream, const State &state)

    64 {

    65     return stream << state.symbol << state.transitions;

    66 }

    67 

    68 inline QDataStream &operator>>(QDataStream &stream, State &state)

    69 {

    70     return stream >> state.symbol >> state.transitions;

    71 }

    72 

    73 struct DFA : public QVector<State>

    74 {

    75     void debug() const;

    76     DFA minimize() const;

    77 };

    78 

    79 class NFA

    80 {

    81 public:

    82     static NFA createSingleInputNFA(InputType input);

    83     static NFA createSymbolNFA(const QString &symbol);

    84     static NFA createAlternatingNFA(const NFA &a, const NFA &b);

    85     static NFA createConcatenatingNFA(const NFA &a, const NFA &b);

    86     static NFA createOptionalNFA(const NFA &a);

    87 

    88     // convenience

    89     static NFA createStringNFA(const QByteArray &str);

    90     static NFA createSetNFA(const QSet<InputType> &set);

    91     static NFA createZeroOrOneNFA(const NFA &a);

    92     static NFA applyQuantity(const NFA &a, int minOccurrences, int maxOccurrences);

    93 

    94     void setTerminationSymbol(const QString &symbol);

    95     

    96     DFA toDFA() const;

    97 

    98     inline bool isEmpty() const { return states.isEmpty(); }

    99     inline int stateCount() const { return states.count(); }

   100 

   101     void debug();

   102 

   103 private:

   104     void initialize(int size);

   105     void addTransition(int from, InputType input, int to);

   106     void copyFrom(const NFA &other, int baseState);

   107 

   108     void initializeFromPair(const NFA &a, const NFA &b,

   109                             int *initialA, int *finalA,

   110                             int *initialB, int *finalB);

   111 

   112     QSet<int> epsilonClosure(const QSet<int> &initialClosure) const;

   113 

   114     inline void assertValidState(int state)

   115     { Q_UNUSED(state); Q_ASSERT(state >= 0); Q_ASSERT(state < states.count()); }

   116     

   117 #if defined(AUTOTEST)

   118 public:

   119 #endif

   120     int initialState;

   121     int finalState;

   122 

   123     QVector<State> states;

   124 };

   125 

   126 #endif // NFA_H

   127