1 /****************************************************************************
3 ** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).
4 ** All rights reserved.
5 ** Contact: Nokia Corporation (qt-info@nokia.com)
7 ** This file is part of the utils of the Qt Toolkit.
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
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.
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.
28 ** If you have questions regarding the use of this file, please contact
29 ** Nokia at qt-info@nokia.com.
40 ****************************************************************************/
45 NFA
NFA::createSingleInputNFA(InputType input
)
49 result
.addTransition(result
.initialState
, input
, result
.finalState
);
53 NFA
NFA::createSymbolNFA(const QString
&symbol
)
55 NFA result
= NFA::createSingleInputNFA(Epsilon
);
56 result
.states
[result
.finalState
].symbol
= symbol
;
60 void NFA::initialize(int size
)
65 finalState
= size
- 1;
68 void NFA::addTransition(int from
, InputType input
, int to
)
70 assertValidState(from
);
73 states
[from
].transitions
.insertMulti(input
, to
);
76 void NFA::copyFrom(const NFA
&other
, int baseState
)
78 assertValidState(baseState
);
79 assertValidState(baseState
+ other
.states
.count() - 1);
81 for (int i
= 0; i
< other
.states
.count(); ++i
) {
82 State s
= other
.states
.at(i
);
84 for (TransitionMap::Iterator it
= s
.transitions
.begin(),
85 end
= s
.transitions
.end(); it
!= end
; ++it
)
88 states
[baseState
+ i
] = s
;
92 void NFA::initializeFromPair(const NFA
&a
, const NFA
&b
,
93 int *initialA
, int *finalA
,
94 int *initialB
, int *finalB
)
96 initialize(a
.states
.count() + b
.states
.count() + 2);
99 int baseIdxB
= 1 + a
.states
.count();
101 *initialA
= a
.initialState
+ baseIdxA
;
102 *finalA
= a
.finalState
+ baseIdxA
;
104 *initialB
= b
.initialState
+ baseIdxB
;
105 *finalB
= b
.finalState
+ baseIdxB
;
107 copyFrom(a
, baseIdxA
);
108 copyFrom(b
, baseIdxB
);
111 NFA
NFA::createAlternatingNFA(const NFA
&a
, const NFA
&b
)
115 int newInitialA
, newFinalA
,
116 newInitialB
, newFinalB
;
118 result
.initializeFromPair(a
, b
, &newInitialA
, &newFinalA
,
119 &newInitialB
, &newFinalB
);
121 result
.addTransition(result
.initialState
, Epsilon
, newInitialA
);
122 result
.addTransition(result
.initialState
, Epsilon
, newInitialB
);
124 result
.addTransition(newFinalA
, Epsilon
, result
.finalState
);
125 result
.addTransition(newFinalB
, Epsilon
, result
.finalState
);
130 NFA
NFA::createConcatenatingNFA(const NFA
&a
, const NFA
&b
)
134 int initialA
, finalA
,
137 result
.initializeFromPair(a
, b
, &initialA
, &finalA
, &initialB
, &finalB
);
139 result
.addTransition(result
.initialState
, Epsilon
, initialA
);
140 result
.addTransition(finalA
, Epsilon
, initialB
);
141 result
.addTransition(finalB
, Epsilon
, result
.finalState
);
145 NFA
NFA::createOptionalNFA(const NFA
&a
)
149 result
.initialize(a
.states
.count() + 2);
152 int initialA
= a
.initialState
+ baseIdxA
;
153 int finalA
= a
.finalState
+ baseIdxA
;
155 result
.copyFrom(a
, baseIdxA
);
157 result
.addTransition(result
.initialState
, Epsilon
, initialA
);
158 result
.addTransition(result
.initialState
, Epsilon
, result
.finalState
);
160 result
.addTransition(finalA
, Epsilon
, initialA
);
161 result
.addTransition(finalA
, Epsilon
, result
.finalState
);
166 NFA
NFA::createStringNFA(const QByteArray
&str
)
169 foreach (char c
, str
) {
170 NFA ch
= NFA::createSingleInputNFA(c
);
171 if (result
.isEmpty())
174 result
= NFA::createConcatenatingNFA(result
, ch
);
179 NFA
NFA::createSetNFA(const QSet
<InputType
> &set
)
182 result
.initialize(set
.count() + 2);
185 for (QSet
<InputType
>::ConstIterator it
= set
.constBegin(), end
= set
.constEnd();
186 it
!= end
; ++it
, ++state
) {
187 result
.addTransition(result
.initialState
, Epsilon
, state
);
188 result
.addTransition(state
, *it
, result
.finalState
);
192 foreach (InputType input, set) {
193 NFA ch = NFA::createSingleInputNFA(input);
194 if (result.isEmpty())
197 result = NFA::createAlternatingNFA(result, ch);
203 NFA
NFA::createZeroOrOneNFA(const NFA
&a
)
205 NFA epsilonNFA
= createSingleInputNFA(Epsilon
);
206 return NFA::createAlternatingNFA(a
, epsilonNFA
);
209 NFA
NFA::applyQuantity(const NFA
&a
, int minOccurrences
, int maxOccurrences
)
212 NFA epsilonNFA
= createSingleInputNFA(Epsilon
);
214 if (minOccurrences
== 0) {
215 result
= NFA::createAlternatingNFA(result
, epsilonNFA
);
221 for (int i
= 0; i
< minOccurrences
; ++i
)
222 result
= NFA::createConcatenatingNFA(result
, a
);
224 for (int i
= minOccurrences
; i
< maxOccurrences
; ++i
)
225 result
= NFA::createConcatenatingNFA(result
, NFA::createAlternatingNFA(a
, epsilonNFA
));
232 qDebug() << "NFA has" << states
.count() << "states";
233 qDebug() << "initial state is" << initialState
;
234 qDebug() << "final state is" << finalState
;
236 for (int i
= 0; i
< states
.count(); ++i
) {
237 const State
&s
= states
.at(i
);
238 for (TransitionMap::ConstIterator it
= s
.transitions
.constBegin(),
239 end
= s
.transitions
.constEnd(); it
!= end
; ++it
)
240 qDebug() << "transition from state" << i
<< "to" << it
.value() << "through"
241 << (it
.key() == Epsilon
? QString("Epsilon") : QString(char(it
.key())));
242 if (!s
.symbol
.isEmpty())
243 qDebug() << "State" << i
<< "leads to symbol" << s
.symbol
;
248 typedef QSet
<int> DFAState
;
250 // that's a bad hash, but it's good enough for us
251 // and it allows us to use the nice QHash API :)
252 inline uint
qHash(const DFAState
&state
)
255 foreach (int s
, state
)
260 DFA
NFA::toDFA() const
263 result
.reserve(states
.count());
265 QHash
<QString
, int> symbolReferenceCounts
;
267 QSet
<int> symbolStates
;
268 for (int i
= 0; i
< states
.count(); ++i
)
269 if (!states
.at(i
).symbol
.isEmpty())
270 symbolStates
.insert(i
);
272 QHash
<int, QString
> epsilonStates
;
273 for (int i
= 0; i
< states
.count(); ++i
) {
274 const State
&s
= states
.at(i
);
275 for (TransitionMap::ConstIterator transition
= s
.transitions
.constBegin(), end
= s
.transitions
.constEnd();
276 transition
!= end
; ++transition
)
277 if (transition
.key() == Epsilon
&& symbolStates
.contains(transition
.value()))
278 epsilonStates
.insert(i
, states
.at(transition
.value()).symbol
);
283 lastCount
= epsilonStates
.count();
284 for (int i
= 0; i
< states
.count(); ++i
) {
285 const State
&s
= states
.at(i
);
286 for (TransitionMap::ConstIterator transition
= s
.transitions
.constBegin(), end
= s
.transitions
.constEnd();
287 transition
!= end
; ++transition
)
288 if (transition
.key() == Epsilon
&& epsilonStates
.contains(transition
.value()))
289 epsilonStates
.insert(i
, epsilonStates
.value(transition
.value()));
292 } while (lastCount
!= epsilonStates
.count());
294 for (int i
= 0; i
< states
.count(); ++i
) {
295 const State
&s
= states
.at(i
);
296 for (TransitionMap::ConstIterator transition
= s
.transitions
.constBegin(), end
= s
.transitions
.constEnd();
297 transition
!= end
; ++transition
) {
298 if (transition
.key() == Epsilon
)
300 if (symbolStates
.contains(transition
.value())) {
301 const QString symbol
= states
.at(transition
.value()).symbol
;
302 symbolReferenceCounts
[symbol
]++;
303 } else if (epsilonStates
.contains(transition
.value())) {
304 const QString symbol
= epsilonStates
.value(transition
.value());
305 symbolReferenceCounts
[symbol
]++;
310 for (QHash<QString, int>::ConstIterator symIt = symbolReferenceCounts.constBegin(), symEnd = symbolReferenceCounts.constEnd();
311 symIt != symEnd; ++symIt)
312 qDebug() << "symbol" << symIt.key() << "is reached" << symIt.value() << "times";
317 QSet
<InputType
> validInput
;
318 foreach (const State
&s
, states
)
319 for (TransitionMap::ConstIterator it
= s
.transitions
.constBegin(),
320 end
= s
.transitions
.constEnd(); it
!= end
; ++it
)
321 if (it
.key() != Epsilon
)
322 validInput
.insert(it
.key());
324 // A DFA state can consist of multiple NFA states.
325 // the dfaStateMap maps from these to the actual
326 // state index within the resulting DFA vector
327 QHash
<DFAState
, int> dfaStateMap
;
328 QStack
<DFAState
> pendingDFAStates
;
330 DFAState startState
= epsilonClosure(QSet
<int>() << initialState
);
333 dfaStateMap
.insert(startState
, 0);
335 pendingDFAStates
.push(startState
);
337 while (!pendingDFAStates
.isEmpty()) {
338 DFAState state
= pendingDFAStates
.pop();
339 // qDebug() << "processing" << state << "from the stack of pending states";
341 foreach (InputType input
, validInput
) {
343 QSet
<int> reachableStates
;
345 foreach (int nfaState
, state
) {
346 const TransitionMap
&transitions
= states
.at(nfaState
).transitions
;
347 TransitionMap::ConstIterator it
= transitions
.find(input
);
348 while (it
!= transitions
.constEnd() && it
.key() == input
) {
349 reachableStates
.insert(it
.value());
354 if (reachableStates
.isEmpty())
357 // qDebug() << "can reach" << reachableStates << "from input" << char(input);
359 QSet
<int> closure
= epsilonClosure(reachableStates
);
361 // qDebug() << "closure is" << closure;
363 if (!dfaStateMap
.contains(closure
)) {
364 int dfaState
= result
.count();
365 result
.append(State());
368 int refCount
= INT_MAX
;
369 foreach (int nfaState
, closure
)
370 if (!states
.at(nfaState
).symbol
.isEmpty()) {
371 // qDebug() << "closure also contains symbol" << states.at(nfaState).symbol;
372 QString candidate
= states
.at(nfaState
).symbol
;
373 int candidateRefCount
=symbolReferenceCounts
.value(candidate
, INT_MAX
);
374 if (candidateRefCount
< refCount
) {
375 refCount
= candidateRefCount
;
379 if (!symbol
.isEmpty())
380 result
.last().symbol
= symbol
;
382 dfaStateMap
.insert(closure
, dfaState
);
384 Q_ASSERT(!pendingDFAStates
.contains(closure
));
385 pendingDFAStates
.prepend(closure
);
388 result
[dfaStateMap
.value(state
)].transitions
.insert(input
, dfaStateMap
.value(closure
));
395 QSet
<int> NFA::epsilonClosure(const QSet
<int> &initialClosure
) const
397 QSet
<int> closure
= initialClosure
;
398 closure
.reserve(closure
.count() * 4);
400 QStack
<int> stateStack
;
401 stateStack
.resize(closure
.count());
402 qCopy(closure
.constBegin(), closure
.constEnd(), stateStack
.begin());
404 while (!stateStack
.isEmpty()) {
405 int t
= stateStack
.pop();
406 const TransitionMap
&transitions
= states
.at(t
).transitions
;
407 TransitionMap::ConstIterator it
= transitions
.find(Epsilon
);
408 while (it
!= transitions
.constEnd() && it
.key() == Epsilon
) {
409 const int u
= it
.value();
410 if (!closure
.contains(u
)) {
421 void NFA::setTerminationSymbol(const QString
&symbol
)
423 states
[finalState
].symbol
= symbol
;
426 void DFA::debug() const
428 qDebug() << "DFA has" << count() << "states";
430 for (int i
= 0; i
< count(); ++i
) {
431 const State
&s
= at(i
);
432 if (s
.transitions
.isEmpty()) {
433 qDebug() << "State" << i
<< "has no transitions";
435 for (TransitionMap::ConstIterator it
= s
.transitions
.constBegin(),
436 end
= s
.transitions
.constEnd(); it
!= end
; ++it
)
437 qDebug() << "transition from state" << i
<< "to" << it
.value() << "through"
438 << (it
.key() == Epsilon
? QString("Epsilon") : QString(char(it
.key())));
440 if (!s
.symbol
.isEmpty())
441 qDebug() << "State" << i
<< "leads to symbol" << s
.symbol
;
446 DFA
DFA::minimize() const
448 QVector
<bool> inequivalentStates(count() * count());
449 inequivalentStates
.fill(false);
451 for (int i
= 0; i
< count(); ++i
)
452 for (int j
= 0; j
< i
; ++j
) {
453 if (i
!= j
&& at(i
).symbol
!= at(j
).symbol
)
454 inequivalentStates
[i
* count() + j
] = true;
460 for (int i
= 0; i
< count(); ++i
)
461 for (int j
= 0; j
< count(); ++j
) {
465 if (inequivalentStates
[i
* count() + j
])
468 if (at(i
).transitions
.keys() != at(j
).transitions
.keys()) {
469 inequivalentStates
[i
* count() + j
] = true;
474 foreach (InputType a
, at(i
).transitions
.keys()) {
475 int r
= at(i
).transitions
.value(a
, -1);
478 int s
= at(j
).transitions
.value(a
, -1);
482 if (inequivalentStates
[r
* count() + s
]
484 inequivalentStates
[i
* count() + j
] = true;
492 QHash
<int, int> statesToEliminate
;
493 for (int i
= 0; i
< count(); ++i
)
494 for (int j
= 0; j
< i
; ++j
)
495 if (!inequivalentStates
[i
* count() + j
]) {
496 statesToEliminate
.insertMulti(i
, j
);
500 qDebug() << "states to eliminiate:" << statesToEliminate.count();;
501 qDebug() << "merging" << statesToEliminate;