273 lines
8.0 KiB
C++
273 lines
8.0 KiB
C++
/****************************************************************************
|
|
**
|
|
** Copyright (C) 2016 The Qt Company Ltd.
|
|
** Contact: https://www.qt.io/licensing/
|
|
**
|
|
** This file is part of the utils of the Qt Toolkit.
|
|
**
|
|
** $QT_BEGIN_LICENSE:GPL-EXCEPT$
|
|
** Commercial License Usage
|
|
** Licensees holding valid commercial Qt licenses may use this file in
|
|
** accordance with the commercial license agreement provided with the
|
|
** Software or, alternatively, in accordance with the terms contained in
|
|
** a written agreement between you and The Qt Company. For licensing terms
|
|
** and conditions see https://www.qt.io/terms-conditions. For further
|
|
** information use the contact form at https://www.qt.io/contact-us.
|
|
**
|
|
** GNU General Public License Usage
|
|
** Alternatively, this file may be used under the terms of the GNU
|
|
** General Public License version 3 as published by the Free Software
|
|
** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
|
|
** included in the packaging of this file. Please review the following
|
|
** information to ensure the GNU General Public License requirements will
|
|
** be met: https://www.gnu.org/licenses/gpl-3.0.html.
|
|
**
|
|
** $QT_END_LICENSE$
|
|
**
|
|
****************************************************************************/
|
|
|
|
#include <QtTest/QtTest>
|
|
#define AUTOTEST
|
|
#include "../main.cpp"
|
|
|
|
class tst_LexGen : public QObject
|
|
{
|
|
Q_OBJECT
|
|
private slots:
|
|
void nfa_singleInput();
|
|
void nfa_alternating();
|
|
void nfa_concatenating();
|
|
void nfa_optional();
|
|
void nfa_toDFA_data();
|
|
void nfa_toDFA();
|
|
void lexgen_data();
|
|
void lexgen();
|
|
};
|
|
|
|
void tst_LexGen::nfa_singleInput()
|
|
{
|
|
NFA nfa = NFA::createSingleInputNFA('a');
|
|
|
|
QCOMPARE(nfa.initialState, 0);
|
|
QCOMPARE(nfa.finalState, 1);
|
|
|
|
QCOMPARE(nfa.states.count(), 2);
|
|
|
|
QCOMPARE(nfa.states.at(0).transitions.count(), 1);
|
|
QVERIFY(nfa.states.at(0).transitions.contains('a'));
|
|
QCOMPARE(nfa.states.at(0).transitions.values('a').count(), 1);
|
|
QCOMPARE(nfa.states.at(0).transitions.value('a'), nfa.finalState);
|
|
|
|
QVERIFY(nfa.states.at(1).transitions.isEmpty());
|
|
}
|
|
|
|
void tst_LexGen::nfa_alternating()
|
|
{
|
|
NFA a = NFA::createSingleInputNFA('a');
|
|
NFA b = NFA::createSingleInputNFA('b');
|
|
NFA nfa = NFA::createAlternatingNFA(a, b);
|
|
|
|
const int initialA = 1;
|
|
const int finalA = 2;
|
|
|
|
const int initialB = 3;
|
|
const int finalB = 4;
|
|
|
|
QCOMPARE(nfa.states.count(), 6);
|
|
|
|
QCOMPARE(nfa.initialState, 0);
|
|
QCOMPARE(nfa.finalState, 5);
|
|
|
|
QList<int> initialTransitions = nfa.states.at(0).transitions.values(Epsilon);
|
|
QCOMPARE(initialTransitions.count(), 2);
|
|
QVERIFY(initialTransitions.contains(initialA));
|
|
QVERIFY(initialTransitions.contains(initialB));
|
|
|
|
// no need to test the individual a and b NFAs, the other
|
|
// autotest already takes care of that. Just check whether
|
|
// the epsilon transitions to the final state exist.
|
|
|
|
QCOMPARE(nfa.states.at(finalA).transitions.count(), 1);
|
|
QCOMPARE(nfa.states.at(finalA).transitions.values(Epsilon).count(), 1);
|
|
QCOMPARE(nfa.states.at(finalA).transitions.value(Epsilon), nfa.finalState);
|
|
|
|
QCOMPARE(nfa.states.at(finalB).transitions.count(), 1);
|
|
QCOMPARE(nfa.states.at(finalB).transitions.values(Epsilon).count(), 1);
|
|
QCOMPARE(nfa.states.at(finalB).transitions.value(Epsilon), nfa.finalState);
|
|
}
|
|
|
|
void tst_LexGen::nfa_concatenating()
|
|
{
|
|
NFA a = NFA::createSingleInputNFA('a');
|
|
NFA b = NFA::createSingleInputNFA('b');
|
|
NFA nfa = NFA::createConcatenatingNFA(a, b);
|
|
|
|
const int initialA = 1;
|
|
const int finalA = 2;
|
|
|
|
const int initialB = 3;
|
|
const int finalB = 4;
|
|
|
|
QCOMPARE(nfa.states.count(), 6);
|
|
|
|
QCOMPARE(nfa.initialState, 0);
|
|
QCOMPARE(nfa.finalState, 5);
|
|
|
|
QCOMPARE(nfa.states.at(0).transitions.count(), 1);
|
|
QCOMPARE(nfa.states.at(0).transitions.values(Epsilon).count(), 1);
|
|
QCOMPARE(nfa.states.at(0).transitions.value(Epsilon), initialA);
|
|
|
|
QCOMPARE(nfa.states.at(finalA).transitions.values(Epsilon).count(), 1);
|
|
QCOMPARE(nfa.states.at(finalA).transitions.value(Epsilon), initialB);
|
|
|
|
QCOMPARE(nfa.states.at(finalB).transitions.values(Epsilon).count(), 1);
|
|
QCOMPARE(nfa.states.at(finalB).transitions.value(Epsilon), nfa.finalState);
|
|
}
|
|
|
|
void tst_LexGen::nfa_optional()
|
|
{
|
|
NFA a = NFA::createSingleInputNFA('a');
|
|
NFA nfa = NFA::createOptionalNFA(a);
|
|
|
|
const int initialA = 1;
|
|
const int finalA = 2;
|
|
|
|
QCOMPARE(nfa.states.count(), 4);
|
|
|
|
QCOMPARE(nfa.initialState, 0);
|
|
QCOMPARE(nfa.finalState, 3);
|
|
|
|
QCOMPARE(nfa.states.at(0).transitions.count(), 2);
|
|
QList<int> initialTransitions = nfa.states.at(0).transitions.values(Epsilon);
|
|
QVERIFY(initialTransitions.contains(nfa.finalState));
|
|
QVERIFY(initialTransitions.contains(initialA));
|
|
|
|
QList<int> finalEpsilonATransitions = nfa.states.at(finalA).transitions.values(Epsilon);
|
|
QVERIFY(finalEpsilonATransitions.contains(initialA));
|
|
QVERIFY(finalEpsilonATransitions.contains(nfa.finalState));
|
|
}
|
|
|
|
Q_DECLARE_METATYPE(NFA);
|
|
Q_DECLARE_METATYPE(DFA);
|
|
|
|
void tst_LexGen::nfa_toDFA_data()
|
|
{
|
|
QTest::addColumn<NFA>("nfa");
|
|
QTest::addColumn<DFA>("expectedDFA");
|
|
|
|
NFA a = NFA::createSingleInputNFA('a');
|
|
NFA b = NFA::createSingleInputNFA('b');
|
|
NFA c = NFA::createSingleInputNFA('c');
|
|
|
|
NFA nfa;
|
|
DFA dfa;
|
|
|
|
dfa.clear();
|
|
dfa.resize(3);
|
|
dfa[0].transitions.insert('a', 1);
|
|
dfa[1].transitions.insert('b', 2);
|
|
|
|
nfa = NFA::createConcatenatingNFA(a, b);
|
|
|
|
QTest::newRow("simple concat") << nfa << dfa;
|
|
|
|
dfa.clear();
|
|
dfa.resize(3);
|
|
dfa[0].transitions.insert('a', 1);
|
|
dfa[0].transitions.insert('b', 2);
|
|
|
|
nfa = NFA::createAlternatingNFA(a, b);
|
|
|
|
QTest::newRow("simple alternate") << nfa << dfa;
|
|
|
|
}
|
|
|
|
void tst_LexGen::nfa_toDFA()
|
|
{
|
|
QFETCH(NFA, nfa);
|
|
QFETCH(DFA, expectedDFA);
|
|
|
|
DFA dfa = nfa.toDFA();
|
|
|
|
QCOMPARE(dfa.count(), expectedDFA.count());
|
|
for (int i = 0; i < dfa.count(); ++i) {
|
|
if (dfa.at(i).transitions != expectedDFA.at(i).transitions) {
|
|
qDebug() << "DFAs differ in state" << i;
|
|
qDebug() << "NFA:";
|
|
nfa.debug();
|
|
qDebug() << "Actual DFA:";
|
|
dfa.debug();
|
|
qDebug() << "Expected DFA:";
|
|
expectedDFA.debug();
|
|
QVERIFY(false);
|
|
}
|
|
}
|
|
}
|
|
|
|
void tst_LexGen::lexgen_data()
|
|
{
|
|
QTest::addColumn<QString>("ruleFile");
|
|
QTest::addColumn<QString>("input");
|
|
QTest::addColumn<QString>("expectedOutput");
|
|
|
|
QDir d(QString(SRCDIR));
|
|
d.cd("testdata");
|
|
foreach (QString test, d.entryList(QDir::Dirs | QDir::NoDotAndDotDot)) {
|
|
QString dir = d.absoluteFilePath(test) + '/';
|
|
QTest::newRow(qPrintable(test))
|
|
<< dir + "rules.lexgen"
|
|
<< dir + "input"
|
|
<< dir + "output"
|
|
;
|
|
}
|
|
}
|
|
|
|
void tst_LexGen::lexgen()
|
|
{
|
|
QFETCH(QString, ruleFile);
|
|
QFETCH(QString, input);
|
|
QFETCH(QString, expectedOutput);
|
|
|
|
Config conf;
|
|
QVERIFY(loadConfig(ruleFile, &conf));
|
|
DFA dfa = generateMachine(conf);
|
|
QVERIFY(!dfa.isEmpty());
|
|
conf.debug = true;
|
|
|
|
QFile f(input);
|
|
QVERIFY(f.open(QIODevice::ReadOnly));
|
|
input = QString::fromUtf8(f.readAll());
|
|
f.close();
|
|
if (input.endsWith(QLatin1Char('\n')))
|
|
input.chop(1);
|
|
// machine.debug();
|
|
bool ok = false;
|
|
QList<Symbol> symbols = tokenize(dfa, input, &conf, &ok);
|
|
QVERIFY(ok);
|
|
f.setFileName(expectedOutput);
|
|
QVERIFY(f.open(QIODevice::ReadOnly));
|
|
QStringList lines;
|
|
while (!f.atEnd()) {
|
|
QString line = QString::fromUtf8(f.readLine());
|
|
if (line.endsWith(QLatin1Char('\n')))
|
|
line.chop(1);
|
|
lines << line;
|
|
}
|
|
f.close();
|
|
|
|
// dfa.debug();
|
|
QCOMPARE(lines.count(), symbols.count());
|
|
|
|
for (int i = 0; i < lines.count(); ++i) {
|
|
QStringList l = lines.at(i).split(QChar::fromLatin1('|'));
|
|
QCOMPARE(l.count(), 2);
|
|
QString expectedToken = l.at(0);
|
|
QString expectedLexem = l.at(1);
|
|
QCOMPARE(symbols.at(i).token, expectedToken);
|
|
QCOMPARE(symbols.at(i).lexem, expectedLexem);
|
|
}
|
|
}
|
|
|
|
QTEST_MAIN(tst_LexGen)
|
|
#include "tst_lexgen.moc"
|