summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/.gitignore1
-rw-r--r--src/compress.cpp286
-rw-r--r--src/compress.h60
-rw-r--r--src/cppgenerator.cpp746
-rw-r--r--src/cppgenerator.h98
-rw-r--r--src/dotgraph.cpp102
-rw-r--r--src/dotgraph.h59
-rw-r--r--src/grammar.cpp123
-rw-r--r--src/grammar_p.h119
-rw-r--r--src/lalr.cpp783
-rw-r--r--src/lalr.g800
-rw-r--r--src/lalr.h502
-rw-r--r--src/main.cpp185
-rw-r--r--src/parsetable.cpp127
-rw-r--r--src/parsetable.h59
-rw-r--r--src/recognizer.cpp488
-rw-r--r--src/recognizer.h111
-rw-r--r--src/src.pro22
18 files changed, 4671 insertions, 0 deletions
diff --git a/src/.gitignore b/src/.gitignore
new file mode 100644
index 0000000..ce75745
--- /dev/null
+++ b/src/.gitignore
@@ -0,0 +1 @@
+qlalr
diff --git a/src/compress.cpp b/src/compress.cpp
new file mode 100644
index 0000000..d94d38d
--- /dev/null
+++ b/src/compress.cpp
@@ -0,0 +1,286 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the test suite module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+
+#include <QtCore/QtDebug>
+#include <QtCore/QList>
+
+#include <algorithm>
+#include <iterator>
+#include <iostream>
+#include "compress.h"
+
+#define QLALR_NO_CHECK_SORTED_TABLE
+
+struct _Fit: public std::binary_function<int, int, bool>
+{
+ inline bool operator () (int a, int b) const
+ {
+ return a == 0 || b == 0 || a == b;
+ }
+};
+
+struct _PerfectMatch: public std::binary_function<int, int, bool>
+{
+ inline bool operator () (int a, int b) const
+ { return a == b; }
+};
+
+struct _GenerateCheck
+{
+ QVector<int>::const_iterator iterator;
+ int initial;
+
+ _GenerateCheck (QVector<int>::const_iterator it, int i):
+ iterator (it),
+ initial (i) {}
+
+ inline int operator () ()
+ {
+ int check = initial++;
+ return *iterator++ ? check : -1;
+ }
+};
+
+class UncompressedRow
+{
+public:
+ typedef const int *const_iterator;
+ typedef const int *iterator;
+
+public:
+ inline UncompressedRow ():
+ _M_index (0),
+ _M_begin (0),
+ _M_end (0),
+ _M_beginNonZeros (0),
+ _M_endNonZeros (0) {}
+
+ inline UncompressedRow (int index, const_iterator begin, const_iterator end)
+ { assign (index, begin, end); }
+
+ inline int index () const { return _M_index; }
+ inline const_iterator begin () const { return _M_begin; }
+ inline const_iterator end () const { return _M_end; }
+
+ inline void assign (int index, const_iterator begin, const_iterator end)
+ {
+ _M_index = index;
+ _M_begin = begin;
+ _M_end = end;
+
+ _M_beginNonZeros = _M_begin;
+ _M_endNonZeros = _M_end;
+
+ for (_M_beginNonZeros = _M_begin; _M_beginNonZeros != _M_end && ! _M_beginNonZeros [0]; ++_M_beginNonZeros)
+ /*continue*/ ;
+
+#if 0
+ for (_M_endNonZeros = _M_end; _M_endNonZeros != _M_beginNonZeros && ! _M_endNonZeros [-1]; --_M_endNonZeros)
+ /*continue*/ ;
+#endif
+ }
+
+ inline int at (int index) const
+ { return _M_begin [index]; }
+
+ inline bool isEmpty () const
+ { return _M_begin == _M_end; }
+
+ inline int size () const
+ { return _M_end - _M_begin; }
+
+ inline int nonZeroElements () const
+ { return _M_endNonZeros - _M_beginNonZeros; }
+
+ inline int count (int value) const
+ { return std::count (begin (), end (), value); }
+
+ inline const_iterator beginNonZeros () const
+ { return _M_beginNonZeros; }
+
+ inline const_iterator endNonZeros () const
+ { return _M_endNonZeros; }
+
+private:
+ int _M_index;
+ const_iterator _M_begin;
+ const_iterator _M_end;
+ const_iterator _M_beginNonZeros;
+ const_iterator _M_endNonZeros;
+};
+
+struct _SortUncompressedRow: public std::binary_function<UncompressedRow, UncompressedRow, bool>
+{
+ inline bool operator () (const UncompressedRow &a, const UncompressedRow &b) const
+ { return a.count (0) > b.count (0); }
+};
+
+Compress::Compress ()
+{
+}
+
+void Compress::operator () (int *table, int row_count, int column_count)
+{
+ index.clear ();
+ info.clear ();
+ check.clear ();
+
+ QVector<UncompressedRow> sortedTable (row_count);
+
+ for (int i = 0; i < row_count; ++i)
+ {
+ int *begin = &table [i * column_count];
+ int *end = begin + column_count;
+
+ sortedTable [i].assign (i, begin, end);
+ }
+
+ qSort (sortedTable.begin (), sortedTable.end (), _SortUncompressedRow ());
+
+#ifndef QLALR_NO_CHECK_SORTED_TABLE
+ int previous_zeros = INT_MAX;
+
+ foreach (UncompressedRow row, sortedTable)
+ {
+ int zeros = row.count (0);
+
+ Q_ASSERT (zeros <= previous_zeros);
+ zeros = previous_zeros;
+ qDebug () << "OK!";
+ }
+#endif
+
+ index.fill (-999999, row_count);
+
+ foreach (UncompressedRow row, sortedTable)
+ {
+ int first_token = std::distance (row.begin (), row.beginNonZeros ());
+ QVector<int>::iterator pos = info.begin ();
+
+ while (pos != info.end ())
+ {
+ if (pos == info.begin ())
+ {
+ // try to find a perfect match
+ QVector<int>::iterator pm = std::search (pos, info.end (), row.beginNonZeros (), row.endNonZeros (), _PerfectMatch ());
+
+ if (pm != info.end ())
+ {
+ pos = pm;
+ break;
+ }
+ }
+
+ pos = std::search (pos, info.end (), row.beginNonZeros (), row.endNonZeros (), _Fit ());
+
+ if (pos == info.end ())
+ break;
+
+ int idx = std::distance (info.begin (), pos) - first_token;
+ bool conflict = false;
+
+ for (int j = 0; ! conflict && j < row.size (); ++j)
+ {
+ if (row.at (j) == 0)
+ conflict |= idx + j >= 0 && check [idx + j] == j;
+
+ else
+ conflict |= check [idx + j] == j;
+ }
+
+ if (! conflict)
+ break;
+
+ ++pos;
+ }
+
+ if (pos == info.end ())
+ {
+ int size = info.size ();
+
+ info.resize (info.size () + row.nonZeroElements ());
+ check.resize (info.size ());
+
+ std::fill (check.begin () + size, check.end (), -1);
+ pos = info.begin () + size;
+ }
+
+ int offset = std::distance (info.begin (), pos);
+ index [row.index ()] = offset - first_token;
+
+ for (const int *it = row.beginNonZeros (); it != row.endNonZeros (); ++it, ++pos)
+ {
+ if (*it)
+ *pos = *it;
+ }
+
+ int i = row.index ();
+
+ for (int j = 0; j < row.size (); ++j)
+ {
+ if (row.at (j) == 0)
+ continue;
+
+ check [index [i] + j] = j;
+ }
+ }
+
+#if 0
+ foreach (UncompressedRow row, sortedTable)
+ {
+ int i = row.index ();
+ Q_ASSERT (i < sortedTable.size ());
+
+ for (int j = 0; j < row.size (); ++j)
+ {
+ if (row.at (j) == 0)
+ {
+ Q_ASSERT (index [i] + j < 0 || check [index [i] + j] != j);
+ continue;
+ }
+
+ Q_ASSERT ( info [index [i] + j] == row.at (j));
+ Q_ASSERT (check [index [i] + j] == j);
+ }
+ }
+#endif
+}
diff --git a/src/compress.h b/src/compress.h
new file mode 100644
index 0000000..d2aae1b
--- /dev/null
+++ b/src/compress.h
@@ -0,0 +1,60 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the utils of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef COMPRESS_H
+#define COMPRESS_H
+
+#include <QtCore/QVector>
+
+class Compress
+{
+public:
+ Compress ();
+
+ void operator () (int *table, int row_count, int column_count);
+
+public:
+ QVector<int> index;
+ QVector<int> info;
+ QVector<int> check;
+};
+
+#endif // COMPRESS_H
diff --git a/src/cppgenerator.cpp b/src/cppgenerator.cpp
new file mode 100644
index 0000000..b68a715
--- /dev/null
+++ b/src/cppgenerator.cpp
@@ -0,0 +1,746 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the utils of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+
+#include <QtCore/QtCore>
+
+#include "cppgenerator.h"
+#include "lalr.h"
+#include "recognizer.h"
+
+QString CppGenerator::copyrightHeader() const
+{
+ return QLatin1String(
+ "/****************************************************************************\n"
+ "**\n"
+ "** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).\n"
+ "** All rights reserved.\n"
+ "** Contact: Nokia Corporation (qt-info@nokia.com)\n"
+ "**\n"
+ "** This file is part of the QtCore module of the Qt Toolkit.\n"
+ "**\n"
+ "** $QT_BEGIN_LICENSE:LGPL$\n"
+ "** No Commercial Usage\n"
+ "** This file contains pre-release code and may not be distributed.\n"
+ "** You may use this file in accordance with the terms and conditions\n"
+ "** contained in the Technology Preview License Agreement accompanying\n"
+ "** this package.\n"
+ "**\n"
+ "** GNU Lesser General Public License Usage\n"
+ "** Alternatively, this file may be used under the terms of the GNU Lesser\n"
+ "** General Public License version 2.1 as published by the Free Software\n"
+ "** Foundation and appearing in the file LICENSE.LGPL included in the\n"
+ "** packaging of this file. Please review the following information to\n"
+ "** ensure the GNU Lesser General Public License version 2.1 requirements\n"
+ "** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.\n"
+ "**\n"
+ "** In addition, as a special exception, Nokia gives you certain additional\n"
+ "** rights. These rights are described in the Nokia Qt LGPL Exception\n"
+ "** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.\n"
+ "**\n"
+ "** If you have questions regarding the use of this file, please contact\n"
+ "** Nokia at qt-info@nokia.com.\n"
+ "**\n"
+ "**\n"
+ "**\n"
+ "**\n"
+ "**\n"
+ "**\n"
+ "**\n"
+ "**\n"
+ "** $QT_END_LICENSE$\n"
+ "**\n"
+ "****************************************************************************/\n"
+ "\n");
+}
+
+QString CppGenerator::privateCopyrightHeader() const
+{
+ return QLatin1String(
+ "//\n"
+ "// W A R N I N G\n"
+ "// -------------\n"
+ "//\n"
+ "// This file is not part of the Qt API. It exists for the convenience\n"
+ "// of other Qt classes. This header file may change from version to\n"
+ "// version without notice, or even be removed.\n"
+ "//\n"
+ "// We mean it.\n"
+ "//\n");
+}
+
+QString CppGenerator::startIncludeGuard(const QString &fileName)
+{
+ const QString normalized(QString(fileName).replace(QLatin1Char('.'), QLatin1Char('_')).toUpper());
+
+ return QString::fromLatin1("#ifndef %1\n"
+ "#define %2\n").arg(normalized, normalized);
+}
+
+QString CppGenerator::endIncludeGuard(const QString &fileName)
+{
+ const QString normalized(QString(fileName).replace(QLatin1Char('.'), QLatin1Char('_')).toUpper());
+
+ return QString::fromLatin1("#endif // %1\n").arg(normalized);
+}
+
+void CppGenerator::operator () ()
+{
+ // action table...
+ state_count = aut.states.size ();
+ terminal_count = grammar.terminals.size ();
+ non_terminal_count = grammar.non_terminals.size ();
+
+#define ACTION(i, j) table [(i) * terminal_count + (j)]
+#define GOTO(i, j) pgoto [(i) * non_terminal_count + (j)]
+
+ int *table = new int [state_count * terminal_count];
+ ::memset (table, 0, state_count * terminal_count * sizeof (int));
+
+ int *pgoto = new int [state_count * non_terminal_count];
+ ::memset (pgoto, 0, state_count * non_terminal_count * sizeof (int));
+
+ accept_state = -1;
+ int shift_reduce_conflict_count = 0;
+ int reduce_reduce_conflict_count = 0;
+
+ for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state)
+ {
+ int q = aut.id (state);
+
+ for (Bundle::iterator a = state->bundle.begin (); a != state->bundle.end (); ++a)
+ {
+ int symbol = aut.id (a.key ());
+ int r = aut.id (a.value ());
+
+ Q_ASSERT (r < state_count);
+
+ if (grammar.isNonTerminal (a.key ()))
+ {
+ Q_ASSERT (symbol >= terminal_count && symbol < grammar.names.size ());
+ GOTO (q, symbol - terminal_count) = r;
+ }
+
+ else
+ ACTION (q, symbol) = r;
+ }
+
+ for (ItemPointer item = state->closure.begin (); item != state->closure.end (); ++item)
+ {
+ if (item->dot != item->end_rhs ())
+ continue;
+
+ int r = aut.id (item->rule);
+
+ NameSet lookaheads = aut.lookaheads.value (item);
+
+ if (item->rule == grammar.goal)
+ accept_state = q;
+
+ foreach (Name s, lookaheads)
+ {
+ int &u = ACTION (q, aut.id (s));
+
+ if (u == 0)
+ u = - r;
+
+ else if (u < 0)
+ {
+ if (verbose)
+ qout << "*** Warning. Found a reduce/reduce conflict in state " << q << " on token ``" << s << "'' between rule "
+ << r << " and " << -u << endl;
+
+ ++reduce_reduce_conflict_count;
+
+ u = qMax (u, -r);
+
+ if (verbose)
+ qout << "\tresolved using rule " << -u << endl;
+ }
+
+ else if (u > 0)
+ {
+ if (item->rule->prec != grammar.names.end() && grammar.token_info.contains (s))
+ {
+ Grammar::TokenInfo info_r = grammar.token_info.value (item->rule->prec);
+ Grammar::TokenInfo info_s = grammar.token_info.value (s);
+
+ if (info_r.prec > info_s.prec)
+ u = -r;
+ else if (info_r.prec == info_s.prec)
+ {
+ switch (info_r.assoc) {
+ case Grammar::Left:
+ u = -r;
+ break;
+ case Grammar::Right:
+ // shift... nothing to do
+ break;
+ case Grammar::NonAssoc:
+ u = 0;
+ break;
+ } // switch
+ }
+ }
+
+ else
+ {
+ ++shift_reduce_conflict_count;
+
+ if (verbose)
+ qout << "*** Warning. Found a shift/reduce conflict in state " << q << " on token ``" << s << "'' with rule " << r << endl;
+ }
+ }
+ }
+ }
+ }
+
+ if (shift_reduce_conflict_count || reduce_reduce_conflict_count)
+ {
+ if (shift_reduce_conflict_count != grammar.expected_shift_reduce
+ || reduce_reduce_conflict_count != grammar.expected_reduce_reduce)
+ qerr << "*** Conflicts: " << shift_reduce_conflict_count << " shift/reduce, " << reduce_reduce_conflict_count << " reduce/reduce" << endl;
+
+ if (verbose)
+ qout << endl << "*** Conflicts: " << shift_reduce_conflict_count << " shift/reduce, " << reduce_reduce_conflict_count << " reduce/reduce" << endl
+ << endl;
+ }
+
+ QBitArray used_rules (grammar.rules.count ());
+
+ int q = 0;
+ for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state, ++q)
+ {
+ for (int j = 0; j < terminal_count; ++j)
+ {
+ int &u = ACTION (q, j);
+
+ if (u < 0)
+ used_rules.setBit (-u - 1);
+ }
+ }
+
+ for (int i = 0; i < used_rules.count (); ++i)
+ {
+ if (! used_rules.testBit (i))
+ {
+ RulePointer rule = grammar.rules.begin () + i;
+
+ if (rule != grammar.goal)
+ qerr << "*** Warning: Rule ``" << *rule << "'' is useless!" << endl;
+ }
+ }
+
+ q = 0;
+ for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state, ++q)
+ {
+ for (int j = 0; j < terminal_count; ++j)
+ {
+ int &u = ACTION (q, j);
+
+ if (u >= 0)
+ continue;
+
+ RulePointer rule = grammar.rules.begin () + (- u - 1);
+
+ if (state->defaultReduce == rule)
+ u = 0;
+ }
+ }
+
+ // ... compress the goto table
+ defgoto.resize (non_terminal_count);
+ for (int j = 0; j < non_terminal_count; ++j)
+ {
+ count.fill (0, state_count);
+
+ int &mx = defgoto [j];
+
+ for (int i = 0; i < state_count; ++i)
+ {
+ int r = GOTO (i, j);
+
+ if (! r)
+ continue;
+
+ ++count [r];
+
+ if (count [r] > count [mx])
+ mx = r;
+ }
+ }
+
+ for (int i = 0; i < state_count; ++i)
+ {
+ for (int j = 0; j < non_terminal_count; ++j)
+ {
+ int &r = GOTO (i, j);
+
+ if (r == defgoto [j])
+ r = 0;
+ }
+ }
+
+ compressed_action (table, state_count, terminal_count);
+ compressed_goto (pgoto, state_count, non_terminal_count);
+
+ delete[] table;
+ table = 0;
+
+ delete[] pgoto;
+ pgoto = 0;
+
+#undef ACTION
+#undef GOTO
+
+ if (! grammar.merged_output.isEmpty())
+ {
+ QFile f(grammar.merged_output);
+ if (! f.open (QFile::WriteOnly))
+ {
+ fprintf (stderr, "*** cannot create %s\n", qPrintable(grammar.merged_output));
+ return;
+ }
+
+ QTextStream out (&f);
+
+ // copyright headers must come first, otherwise the headers tests will fail
+ if (copyright)
+ {
+ out << copyrightHeader()
+ << privateCopyrightHeader()
+ << endl;
+ }
+
+ out << "// This file was generated by qlalr - DO NOT EDIT!\n";
+
+ out << startIncludeGuard(grammar.merged_output) << endl;
+
+ if (copyright) {
+ out << "#if defined(ERROR)" << endl
+ << "# undef ERROR" << endl
+ << "#endif" << endl << endl;
+ }
+
+ generateDecl (out);
+ generateImpl (out);
+ out << p.decls();
+ out << p.impls();
+ out << endl;
+
+ out << endIncludeGuard(grammar.merged_output) << endl;
+
+ return;
+ }
+
+ // default behaviour
+ QString declFileName = grammar.table_name.toLower () + QLatin1String("_p.h");
+ QString bitsFileName = grammar.table_name.toLower () + QLatin1String(".cpp");
+
+ { // decls...
+ QFile f (declFileName);
+ f.open (QFile::WriteOnly);
+ QTextStream out (&f);
+
+ QString prot = declFileName.toUpper ().replace (QLatin1Char ('.'), QLatin1Char ('_'));
+
+ // copyright headers must come first, otherwise the headers tests will fail
+ if (copyright)
+ {
+ out << copyrightHeader()
+ << privateCopyrightHeader()
+ << endl;
+ }
+
+ out << "// This file was generated by qlalr - DO NOT EDIT!\n";
+
+ out << "#ifndef " << prot << endl
+ << "#define " << prot << endl
+ << endl;
+
+ if (copyright) {
+ out << "#include <QtCore/qglobal.h>" << endl << endl;
+ out << "QT_BEGIN_NAMESPACE" << endl << endl;
+ }
+ generateDecl (out);
+ if (copyright)
+ out << "QT_END_NAMESPACE" << endl;
+
+ out << "#endif // " << prot << endl << endl;
+ } // end decls
+
+ { // bits...
+ QFile f (bitsFileName);
+ f.open (QFile::WriteOnly);
+ QTextStream out (&f);
+
+ // copyright headers must come first, otherwise the headers tests will fail
+ if (copyright)
+ out << copyrightHeader();
+
+ out << "// This file was generated by qlalr - DO NOT EDIT!\n";
+
+ out << "#include \"" << declFileName << "\"" << endl << endl;
+ if (copyright)
+ out << "QT_BEGIN_NAMESPACE" << endl << endl;
+ generateImpl(out);
+ if (copyright)
+ out << "QT_END_NAMESPACE" << endl;
+
+ } // end bits
+
+ if (! grammar.decl_file_name.isEmpty ())
+ {
+ QFile f (grammar.decl_file_name);
+ f.open (QFile::WriteOnly);
+ QTextStream out (&f);
+ out << p.decls();
+ }
+
+ if (! grammar.impl_file_name.isEmpty ())
+ {
+ QFile f (grammar.impl_file_name);
+ f.open (QFile::WriteOnly);
+ QTextStream out (&f);
+ out << p.impls();
+ }
+}
+
+QString CppGenerator::debugInfoProt() const
+{
+ QString prot = QLatin1String("QLALR_NO_");
+ prot += grammar.table_name.toUpper();
+ prot += QLatin1String("_DEBUG_INFO");
+ return prot;
+}
+
+void CppGenerator::generateDecl (QTextStream &out)
+{
+ out << "class " << grammar.table_name << endl
+ << "{" << endl
+ << "public:" << endl
+ << " enum VariousConstants {" << endl;
+
+ foreach (Name t, grammar.terminals)
+ {
+ QString name = *t;
+ int value = std::distance (grammar.names.begin (), t);
+
+ if (name == QLatin1String ("$end"))
+ name = QLatin1String ("EOF_SYMBOL");
+
+ else if (name == QLatin1String ("$accept"))
+ name = QLatin1String ("ACCEPT_SYMBOL");
+
+ else
+ name.prepend (grammar.token_prefix);
+
+ out << " " << name << " = " << value << "," << endl;
+ }
+
+ out << endl
+ << " ACCEPT_STATE = " << accept_state << "," << endl
+ << " RULE_COUNT = " << grammar.rules.size () << "," << endl
+ << " STATE_COUNT = " << state_count << "," << endl
+ << " TERMINAL_COUNT = " << terminal_count << "," << endl
+ << " NON_TERMINAL_COUNT = " << non_terminal_count << "," << endl
+ << endl
+ << " GOTO_INDEX_OFFSET = " << compressed_action.index.size () << "," << endl
+ << " GOTO_INFO_OFFSET = " << compressed_action.info.size () << "," << endl
+ << " GOTO_CHECK_OFFSET = " << compressed_action.check.size () << endl
+ << " };" << endl
+ << endl
+ << " static const char *const spell [];" << endl
+ << " static const short lhs [];" << endl
+ << " static const short rhs [];" << endl;
+
+ if (debug_info)
+ {
+ QString prot = debugInfoProt();
+
+ out << endl << "#ifndef " << prot << endl
+ << " static const int rule_index [];" << endl
+ << " static const int rule_info [];" << endl
+ << "#endif // " << prot << endl << endl;
+ }
+
+ out << " static const short goto_default [];" << endl
+ << " static const short action_default [];" << endl
+ << " static const short action_index [];" << endl
+ << " static const short action_info [];" << endl
+ << " static const short action_check [];" << endl
+ << endl
+ << " static inline int nt_action (int state, int nt)" << endl
+ << " {" << endl
+ << " const int yyn = action_index [GOTO_INDEX_OFFSET + state] + nt;" << endl
+ << " if (yyn < 0 || action_check [GOTO_CHECK_OFFSET + yyn] != nt)" << endl
+ << " return goto_default [nt];" << endl
+ << endl
+ << " return action_info [GOTO_INFO_OFFSET + yyn];" << endl
+ << " }" << endl
+ << endl
+ << " static inline int t_action (int state, int token)" << endl
+ << " {" << endl
+ << " const int yyn = action_index [state] + token;" << endl
+ << endl
+ << " if (yyn < 0 || action_check [yyn] != token)" << endl
+ << " return - action_default [state];" << endl
+ << endl
+ << " return action_info [yyn];" << endl
+ << " }" << endl
+ << "};" << endl
+ << endl
+ << endl;
+}
+
+void CppGenerator::generateImpl (QTextStream &out)
+{
+ int idx = 0;
+
+ out << "const char *const " << grammar.table_name << "::spell [] = {";
+ idx = 0;
+
+ QMap<Name, int> name_ids;
+ bool first_nt = true;
+
+ for (Name t = grammar.names.begin (); t != grammar.names.end (); ++t, ++idx)
+ {
+ bool terminal = grammar.isTerminal (t);
+
+ if (! (debug_info || terminal))
+ break;
+
+ name_ids.insert (t, idx);
+
+ if (idx)
+ out << ", ";
+
+ if (! (idx % 10))
+ out << endl << " ";
+
+ if (terminal)
+ {
+ QString spell = grammar.spells.value (t);
+
+ if (spell.isEmpty ())
+ out << "0";
+ else
+ out << "\"" << spell << "\"";
+ }
+ else
+ {
+ if (first_nt)
+ {
+ first_nt = false;
+ QString prot = debugInfoProt();
+ out << endl << "#ifndef " << prot << endl;
+ }
+ out << "\"" << *t << "\"";
+ }
+ }
+
+ if (debug_info)
+ out << endl << "#endif // " << debugInfoProt() << endl;
+
+ out << "};" << endl << endl;
+
+ out << "const short " << grammar.table_name << "::lhs [] = {";
+ idx = 0;
+ for (RulePointer rule = grammar.rules.begin (); rule != grammar.rules.end (); ++rule, ++idx)
+ {
+ if (idx)
+ out << ", ";
+
+ if (! (idx % 10))
+ out << endl << " ";
+
+ out << aut.id (rule->lhs);
+ }
+ out << "};" << endl << endl;
+
+ out << "const short " << grammar.table_name << "::rhs [] = {";
+ idx = 0;
+ for (RulePointer rule = grammar.rules.begin (); rule != grammar.rules.end (); ++rule, ++idx)
+ {
+ if (idx)
+ out << ", ";
+
+ if (! (idx % 10))
+ out << endl << " ";
+
+ out << rule->rhs.size ();
+ }
+ out << "};" << endl << endl;
+
+ if (debug_info)
+ {
+ QString prot = debugInfoProt();
+
+ out << endl << "#ifndef " << prot << endl;
+ out << "const int " << grammar.table_name << "::rule_info [] = {";
+ idx = 0;
+ for (RulePointer rule = grammar.rules.begin (); rule != grammar.rules.end (); ++rule, ++idx)
+ {
+ out << endl << " ";
+
+ if (idx)
+ out << ", ";
+ else
+ out << " ";
+
+ out << name_ids.value(rule->lhs);
+
+ foreach (Name n, rule->rhs)
+ out << ", " << name_ids.value (n);
+ }
+ out << "};" << endl << endl;
+
+ out << "const int " << grammar.table_name << "::rule_index [] = {";
+ idx = 0;
+ int offset = 0;
+ for (RulePointer rule = grammar.rules.begin (); rule != grammar.rules.end (); ++rule, ++idx)
+ {
+ if (idx)
+ out << ", ";
+
+ if (! (idx % 10))
+ out << endl << " ";
+
+ out << offset;
+ offset += rule->rhs.size () + 1;
+ }
+ out << "};" << endl
+ << "#endif // " << prot << endl << endl;
+ }
+
+ out << "const short " << grammar.table_name << "::action_default [] = {";
+ idx = 0;
+ for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state, ++idx)
+ {
+ if (state != aut.states.begin ())
+ out << ", ";
+
+ if (! (idx % 10))
+ out << endl << " ";
+
+ if (state->defaultReduce != grammar.rules.end ())
+ out << aut.id (state->defaultReduce);
+ else
+ out << "0";
+ }
+ out << "};" << endl << endl;
+
+ out << "const short " << grammar.table_name << "::goto_default [] = {";
+ for (int i = 0; i < defgoto.size (); ++i)
+ {
+ if (i)
+ out << ", ";
+
+ if (! (i % 10))
+ out << endl << " ";
+
+ out << defgoto [i];
+ }
+ out << "};" << endl << endl;
+
+ out << "const short " << grammar.table_name << "::action_index [] = {";
+ for (int i = 0; i < compressed_action.index.size (); ++i)
+ {
+ if (! (i % 10))
+ out << endl << " ";
+
+ out << compressed_action.index [i] << ", ";
+ }
+ out << endl;
+ for (int i = 0; i < compressed_goto.index.size (); ++i)
+ {
+ if (i)
+ out << ", ";
+
+ if (! (i % 10))
+ out << endl << " ";
+
+ out << compressed_goto.index [i];
+ }
+ out << "};" << endl << endl;
+
+ out << "const short " << grammar.table_name << "::action_info [] = {";
+ for (int i = 0; i < compressed_action.info.size (); ++i)
+ {
+ if (! (i % 10))
+ out << endl << " ";
+
+ out << compressed_action.info [i] << ", ";
+ }
+ out << endl;
+ for (int i = 0; i < compressed_goto.info.size (); ++i)
+ {
+ if (i)
+ out << ", ";
+
+ if (! (i % 10))
+ out << endl << " ";
+
+ out << compressed_goto.info [i];
+ }
+ out << "};" << endl << endl;
+
+ out << "const short " << grammar.table_name << "::action_check [] = {";
+ for (int i = 0; i < compressed_action.check.size (); ++i)
+ {
+ if (! (i % 10))
+ out << endl << " ";
+
+ out << compressed_action.check [i] << ", ";
+ }
+ out << endl;
+ for (int i = 0; i < compressed_goto.check.size (); ++i)
+ {
+ if (i)
+ out << ", ";
+
+ if (! (i % 10))
+ out << endl << " ";
+
+ out << compressed_goto.check [i];
+ }
+ out << "};" << endl << endl;
+}
diff --git a/src/cppgenerator.h b/src/cppgenerator.h
new file mode 100644
index 0000000..e6f22be
--- /dev/null
+++ b/src/cppgenerator.h
@@ -0,0 +1,98 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the utils of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef CPPGENERATOR_H
+#define CPPGENERATOR_H
+
+#include "lalr.h"
+#include "compress.h"
+
+class Grammar;
+class Automaton;
+class Recognizer;
+
+class CppGenerator
+{
+public:
+ CppGenerator(const Recognizer &p, Grammar &grammar, Automaton &aut, bool verbose):
+ p (p),
+ grammar (grammar),
+ aut (aut),
+ verbose (verbose),
+ debug_info (false),
+ copyright (false) {}
+
+ void operator () ();
+
+ bool debugInfo () const { return debug_info; }
+ void setDebugInfo (bool d) { debug_info = d; }
+
+ void setCopyright (bool t) { copyright = t; }
+
+private:
+ void generateDecl (QTextStream &out);
+ void generateImpl (QTextStream &out);
+
+ QString debugInfoProt() const;
+ QString copyrightHeader() const;
+ QString privateCopyrightHeader() const;
+
+private:
+ static QString startIncludeGuard(const QString &fileName);
+ static QString endIncludeGuard(const QString &fileName);
+
+ const Recognizer &p;
+ Grammar &grammar;
+ Automaton &aut;
+ bool verbose;
+ int accept_state;
+ int state_count;
+ int terminal_count;
+ int non_terminal_count;
+ bool debug_info;
+ bool copyright;
+ Compress compressed_action;
+ Compress compressed_goto;
+ QVector<int> count;
+ QVector<int> defgoto;
+};
+
+#endif // CPPGENERATOR_H
diff --git a/src/dotgraph.cpp b/src/dotgraph.cpp
new file mode 100644
index 0000000..5433b31
--- /dev/null
+++ b/src/dotgraph.cpp
@@ -0,0 +1,102 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the utils of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+
+#include <QtCore/QTextStream>
+
+#include "lalr.h"
+#include "dotgraph.h"
+
+DotGraph::DotGraph(QTextStream &o):
+ out (o)
+{
+}
+
+void DotGraph::operator () (Automaton *aut)
+{
+ Grammar *g = aut->_M_grammar;
+
+ out << "digraph {" << endl << endl;
+
+ out << "subgraph Includes {" << endl;
+ for (Automaton::IncludesGraph::iterator incl = Automaton::IncludesGraph::begin_nodes ();
+ incl != Automaton::IncludesGraph::end_nodes (); ++incl)
+ {
+ for (Automaton::IncludesGraph::edge_iterator edge = incl->begin (); edge != incl->end (); ++edge)
+ {
+ out << "\t\"(" << aut->id (incl->data.state) << ", " << incl->data.nt << ")\"";
+ out << "\t->\t";
+ out << "\"(" << aut->id ((*edge)->data.state) << ", " << (*edge)->data.nt << ")\"\t";
+ out << "[label=\"" << incl->data.state->follows [incl->data.nt] << "\"]";
+ out << endl;
+ }
+ }
+ out << "}" << endl << endl;
+
+
+ out << "subgraph LRA {" << endl;
+ //out << "node [shape=record];" << endl << endl;
+
+ for (StatePointer q = aut->states.begin (); q != aut->states.end (); ++q)
+ {
+ int state = aut->id (q);
+
+ out << "\t" << state << "\t[shape=record,label=\"{";
+
+ out << "<0> State " << state;
+
+ int index = 1;
+ for (ItemPointer item = q->kernel.begin (); item != q->kernel.end (); ++item)
+ out << "| <" << index++ << "> " << *item;
+
+ out << "}\"]" << endl;
+
+ for (Bundle::iterator a = q->bundle.begin (); a != q->bundle.end (); ++a)
+ {
+ const char *clr = g->isTerminal (a.key ()) ? "blue" : "red";
+ out << "\t" << state << "\t->\t" << aut->id (*a) << "\t[color=\"" << clr << "\",label=\"" << a.key () << "\"]" << endl;
+ }
+ out << endl;
+ }
+
+ out << "}" << endl;
+ out << endl << endl << "}" << endl;
+}
diff --git a/src/dotgraph.h b/src/dotgraph.h
new file mode 100644
index 0000000..15d5734
--- /dev/null
+++ b/src/dotgraph.h
@@ -0,0 +1,59 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the utils of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef DOTGRAPH_H
+#define DOTGRAPH_H
+
+QT_FORWARD_DECLARE_CLASS(QTextStream);
+class Automaton;
+
+class DotGraph
+{
+public:
+ DotGraph (QTextStream &out);
+
+ void operator () (Automaton *a);
+
+private:
+ QTextStream &out;
+};
+
+#endif // DOTGRAPH_H
diff --git a/src/grammar.cpp b/src/grammar.cpp
new file mode 100644
index 0000000..1a7a318
--- /dev/null
+++ b/src/grammar.cpp
@@ -0,0 +1,123 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the utils of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "grammar_p.h"
+
+const char *const grammar::spell [] = {
+ "end of file", "identifier", "string literal", "%decl", "%expect", "%expect-lr", "%impl", "%left", "%merged_output", "%nonassoc",
+ "%parser", "%prec", "%right", "%start", "%token", "%token_prefix", ":", "|", ";", 0,
+ 0, 0};
+
+const int grammar::lhs [] = {
+ 22, 23, 23, 29, 25, 28, 28, 28, 28, 28,
+ 28, 28, 24, 24, 31, 32, 32, 33, 33, 34,
+ 34, 34, 31, 35, 35, 36, 37, 37, 38, 38,
+ 30, 30, 26, 26, 40, 39, 41, 41, 44, 43,
+ 43, 42, 42, 27, 45};
+
+const int grammar:: rhs[] = {
+ 4, 1, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 1, 2, 2, 1, 2, 2, 2, 1,
+ 1, 1, 2, 1, 2, 1, 1, 1, 1, 2,
+ 0, 1, 1, 2, 2, 4, 3, 6, 0, 0,
+ 2, 1, 2, 0, 2};
+
+const int grammar::action_default [] = {
+ 44, 2, 44, 0, 0, 0, 0, 13, 0, 0,
+ 3, 0, 0, 0, 8, 10, 11, 9, 7, 6,
+ 12, 20, 22, 0, 21, 0, 44, 31, 0, 14,
+ 26, 24, 23, 25, 4, 33, 1, 0, 34, 44,
+ 35, 42, 39, 40, 0, 31, 44, 40, 43, 0,
+ 31, 41, 29, 27, 28, 32, 38, 30, 36, 31,
+ 37, 5, 44, 16, 15, 18, 19, 17, 45};
+
+const int grammar::goto_default [] = {
+ 3, 2, 13, 26, 36, 41, 10, 27, 61, 29,
+ 64, 63, 23, 32, 31, 52, 55, 38, 39, 42,
+ 43, 59, 44, 0};
+
+const int grammar::action_index [] = {
+ -22, -22, 54, 1, 5, 15, 20, -22, -1, 6,
+ -22, 3, 2, 35, -22, -22, -22, -22, -22, -22,
+ -22, -22, -22, 10, -22, 7, -22, 14, 9, -22,
+ -22, -22, 8, -22, -22, -22, 11, -2, -22, -22,
+ -22, -22, -3, 16, 13, 14, -22, 17, -22, 4,
+ 14, -22, -22, -22, -22, 14, -22, -22, -22, 14,
+ -22, -22, 0, -22, 12, -22, -22, -22, -22,
+
+ 2, -24, -2, -24, -24, -24, -24, -24, -24, -24,
+ -24, -24, -24, -24, -24, -24, -24, -24, -24, -24,
+ -24, -24, -24, -24, -24, -24, -4, -24, -24, -24,
+ -24, -24, -14, -24, -24, -24, -24, -24, -24, -24,
+ -24, -24, -24, -24, -24, 0, -16, -15, -24, -24,
+ 15, -24, -24, -24, -24, -10, -24, -24, -24, 1,
+ -24, -24, -3, -24, -1, -24, -24, -24, -24};
+
+const int grammar::action_info [] = {
+ 17, 68, 66, 20, 19, 51, 14, 18, 34, 30,
+ 62, 30, 37, 62, 40, 45, 15, 48, 48, 0,
+ 0, 16, 0, 0, 0, 0, 0, 49, 49, 0,
+ 46, 0, 0, 53, 54, 0, 0, 0, 0, 0,
+ 0, 0, 21, 0, 22, 0, 0, 24, 25, 28,
+ 0, 0, 0, 0, 0, 0, 0, 4, 5, 6,
+ 8, 0, 9, 0, 11, 0, 0, 0, 0, 12,
+ 0, 0, 0, 0, 0, 0,
+
+ 33, 35, 65, 7, 47, 57, 50, 1, 58, 60,
+ 67, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 56, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0};
+
+const int grammar::action_check [] = {
+ 1, 0, 2, 1, 1, 1, 1, 1, 1, 1,
+ 1, 1, 1, 1, 16, 18, 1, 1, 1, -1,
+ -1, 1, -1, -1, -1, -1, -1, 11, 11, -1,
+ 17, -1, -1, 19, 20, -1, -1, -1, -1, -1,
+ -1, -1, 7, -1, 9, -1, -1, 12, 13, 14,
+ -1, -1, -1, -1, -1, -1, -1, 3, 4, 5,
+ 6, -1, 8, -1, 10, -1, -1, -1, -1, 15,
+ -1, -1, -1, -1, -1, -1,
+
+ 14, 5, 5, 5, 20, 15, 21, 5, 8, 8,
+ 11, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+ -1, -1, -1, 8, -1, -1, -1, -1, -1, -1,
+ -1, -1, -1, -1, -1, -1, -1, -1, -1};
+
diff --git a/src/grammar_p.h b/src/grammar_p.h
new file mode 100644
index 0000000..4a4ec12
--- /dev/null
+++ b/src/grammar_p.h
@@ -0,0 +1,119 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the utils of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef GRAMMAR_P_H
+#define GRAMMAR_P_H
+
+class grammar
+{
+public:
+ enum {
+ EOF_SYMBOL = 0,
+ COLON = 16,
+ DECL = 19,
+ DECL_FILE = 3,
+ ERROR = 21,
+ EXPECT = 4,
+ EXPECT_RR = 5,
+ ID = 1,
+ IMPL = 20,
+ IMPL_FILE = 6,
+ LEFT = 7,
+ MERGED_OUTPUT = 8,
+ NONASSOC = 9,
+ OR = 17,
+ PARSER = 10,
+ PREC = 11,
+ RIGHT = 12,
+ SEMICOLON = 18,
+ START = 13,
+ STRING_LITERAL = 2,
+ TOKEN = 14,
+ TOKEN_PREFIX = 15,
+
+ ACCEPT_STATE = 68,
+ RULE_COUNT = 45,
+ STATE_COUNT = 69,
+ TERMINAL_COUNT = 22,
+ NON_TERMINAL_COUNT = 24,
+
+ GOTO_INDEX_OFFSET = 69,
+ GOTO_INFO_OFFSET = 76,
+ GOTO_CHECK_OFFSET = 76
+ };
+
+ static const char *const spell [];
+ static const int lhs [];
+ static const int rhs [];
+ static const int goto_default [];
+ static const int action_default [];
+ static const int action_index [];
+ static const int action_info [];
+ static const int action_check [];
+
+ inline int nt_action (int state, int nt) const
+ {
+ const int *const goto_index = &action_index [GOTO_INDEX_OFFSET];
+ const int *const goto_check = &action_check [GOTO_CHECK_OFFSET];
+
+ const int yyn = goto_index [state] + nt;
+
+ if (yyn < 0 || goto_check [yyn] != nt)
+ return goto_default [nt];
+
+ const int *const goto_info = &action_info [GOTO_INFO_OFFSET];
+ return goto_info [yyn];
+ }
+
+ inline int t_action (int state, int token) const
+ {
+ const int yyn = action_index [state] + token;
+
+ if (yyn < 0 || action_check [yyn] != token)
+ return - action_default [state];
+
+ return action_info [yyn];
+ }
+};
+
+
+#endif // GRAMMAR_P_H
+
diff --git a/src/lalr.cpp b/src/lalr.cpp
new file mode 100644
index 0000000..cef4368
--- /dev/null
+++ b/src/lalr.cpp
@@ -0,0 +1,783 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the utils of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+
+#include "lalr.h"
+#include <limits.h>
+
+#include <algorithm>
+
+#define QLALR_NO_DEBUG_NULLABLES
+#define QLALR_NO_DEBUG_LOOKBACKS
+#define QLALR_NO_DEBUG_DIRECT_READS
+#define QLALR_NO_DEBUG_READS
+#define QLALR_NO_DEBUG_INCLUDES
+#define QLALR_NO_DEBUG_LOOKAHEADS
+
+QT_BEGIN_NAMESPACE
+QTextStream qerr (stderr, QIODevice::WriteOnly);
+QTextStream qout (stdout, QIODevice::WriteOnly);
+
+bool operator < (Name a, Name b)
+{
+ return *a < *b;
+}
+
+bool operator < (ItemPointer a, ItemPointer b)
+{
+ return &*a < &*b;
+}
+
+bool operator < (StatePointer a, StatePointer b)
+{
+ return &*a < &*b;
+}
+QT_END_NAMESPACE
+
+bool Read::operator < (const Read &other) const
+{
+ if (state == other.state)
+ return nt < other.nt;
+
+ return state < other.state;
+}
+
+bool Include::operator < (const Include &other) const
+{
+ if (state == other.state)
+ return nt < other.nt;
+
+ return state < other.state;
+}
+
+bool Lookback::operator < (const Lookback &other) const
+{
+ if (state == other.state)
+ return nt < other.nt;
+
+ return state < other.state;
+}
+
+QTextStream &operator << (QTextStream &out, const Name &n)
+{
+ return out << *n;
+}
+
+QTextStream &operator << (QTextStream &out, const Rule &r)
+{
+ out << *r.lhs << " ::=";
+
+ for (NameList::const_iterator name = r.rhs.begin (); name != r.rhs.end (); ++name)
+ out << " " << **name;
+
+ return out;
+}
+
+QTextStream &operator << (QTextStream &out, const NameSet &ns)
+{
+ out << "{";
+
+ for (NameSet::const_iterator n = ns.begin (); n != ns.end (); ++n)
+ {
+ if (n != ns.begin ())
+ out << ", ";
+
+ out << *n;
+ }
+
+ return out << "}";
+}
+
+Item Item::next () const
+{
+ Q_ASSERT (! isReduceItem ());
+
+ Item n;
+ n.rule = rule;
+ n.dot = dot;
+ ++n.dot;
+
+ return n;
+}
+
+QTextStream &operator << (QTextStream &out, const Item &item)
+{
+ RulePointer r = item.rule;
+
+ out << *r->lhs << ":";
+ for (NameList::iterator name = r->rhs.begin (); name != r->rhs.end (); ++name)
+ {
+ out << " ";
+
+ if (item.dot == name)
+ out << ". ";
+
+ out << **name;
+ }
+
+ if (item.isReduceItem ())
+ out << " .";
+
+ return out;
+}
+
+State::State (Grammar *g):
+ defaultReduce (g->rules.end ())
+{
+}
+
+QPair<ItemPointer, bool> State::insert (const Item &item)
+{
+ ItemPointer it = qFind (kernel.begin (), kernel.end (), item);
+
+ if (it != kernel.end ())
+ return qMakePair (it, false);
+
+ return qMakePair (kernel.insert (it, item), true);
+}
+
+QPair<ItemPointer, bool> State::insertClosure (const Item &item)
+{
+ ItemPointer it = qFind (closure.begin (), closure.end (), item);
+
+ if (it != closure.end ())
+ return qMakePair (it, false);
+
+ return qMakePair (closure.insert (it, item), true);
+}
+
+
+/////////////////////////////////////////////////////////////
+// Grammar
+/////////////////////////////////////////////////////////////
+Grammar::Grammar ():
+ start (names.end ())
+{
+ expected_shift_reduce = 0;
+ expected_reduce_reduce = 0;
+ current_prec = 0;
+ current_assoc = NonAssoc;
+
+ table_name = QLatin1String ("parser_table");
+
+ tk_end = intern ("$end");
+ terminals.insert (tk_end);
+ spells.insert (tk_end, "end of file");
+
+ /*tk_error= terminals.insert (intern ("error"))*/;
+}
+
+Name Grammar::intern (const QString &id)
+{
+ Name name = qFind (names.begin (), names.end (), id);
+
+ if (name == names.end ())
+ name = names.insert (names.end (), id);
+
+ return name;
+}
+
+void Grammar::buildRuleMap ()
+{
+ NameSet undefined;
+ for (RulePointer rule = rules.begin (); rule != rules.end (); ++rule)
+ {
+ for (NameList::iterator it = rule->rhs.begin (); it != rule->rhs.end (); ++it)
+ {
+ Name name = *it;
+ if (isTerminal (name) || declared_lhs.find (name) != declared_lhs.end ()
+ || undefined.find (name) != undefined.end ())
+ continue;
+
+ undefined.insert(name);
+ fprintf (stderr, "*** Warning. Symbol `%s' is not defined\n", qPrintable (*name));
+ }
+
+ rule_map.insert (rule->lhs, rule);
+ }
+}
+
+void Grammar::buildExtendedGrammar ()
+{
+ accept_symbol = intern ("$accept");
+ goal = rules.insert (rules.end (), Rule ());
+ goal->lhs = accept_symbol;
+ goal->rhs.push_back (start);
+ goal->rhs.push_back (tk_end);
+
+ non_terminals.insert (accept_symbol);
+}
+
+struct _Nullable: public std::unary_function<Name, bool>
+{
+ Automaton *_M_automaton;
+
+ _Nullable (Automaton *aut):
+ _M_automaton (aut) {}
+
+ bool operator () (Name name) const
+ { return _M_automaton->nullables.find (name) != _M_automaton->nullables.end (); }
+};
+
+Automaton::Automaton (Grammar *g):
+ _M_grammar (g),
+ start (states.end ())
+{
+}
+
+int Automaton::id (RulePointer rule)
+{
+ return 1 + std::distance (_M_grammar->rules.begin (), rule);
+}
+
+int Automaton::id (Name name)
+{
+ return std::distance (_M_grammar->names.begin (), name);
+}
+
+int Automaton::id (StatePointer state)
+{
+ return std::distance (states.begin (), state);
+}
+
+void Automaton::build ()
+{
+ Item item;
+ item.rule = _M_grammar->goal;
+ item.dot = _M_grammar->goal->rhs.begin ();
+
+ State tmp (_M_grammar);
+ tmp.insert (item);
+ start = internState (tmp).first;
+
+ closure (start);
+
+ buildNullables ();
+ buildLookbackSets ();
+ buildReads ();
+ buildIncludesAndFollows ();
+ buildLookaheads ();
+ buildDefaultReduceActions ();
+}
+
+void Automaton::buildNullables ()
+{
+ bool changed = true;
+
+ while (changed)
+ {
+ changed = false;
+
+ for (RulePointer rule = _M_grammar->rules.begin (); rule != _M_grammar->rules.end (); ++rule)
+ {
+ NameList::iterator nn = std::find_if (rule->rhs.begin (), rule->rhs.end (), std::not1 (_Nullable (this)));
+
+ if (nn == rule->rhs.end ())
+ changed |= nullables.insert (rule->lhs).second;
+ }
+ }
+
+#ifndef QLALR_NO_DEBUG_NULLABLES
+ qerr << "nullables = {" << nullables << endl;
+#endif
+}
+
+QPair<StatePointer, bool> Automaton::internState (const State &state)
+{
+ StatePointer it = qFind (states.begin (), states.end (), state);
+
+ if (it != states.end ())
+ return qMakePair (it, false);
+
+ return qMakePair (states.insert (it, state), true);
+}
+
+struct _Bucket
+{
+ QLinkedList<ItemPointer> items;
+
+ void insert (ItemPointer item)
+ { items.push_back (item); }
+
+ State toState (Automaton *aut)
+ {
+ State st (aut->_M_grammar);
+
+ for (QLinkedList<ItemPointer>::iterator item = items.begin (); item != items.end (); ++item)
+ st.insert ((*item)->next ());
+
+ return st;
+ }
+};
+
+void Automaton::closure (StatePointer state)
+{
+ if (! state->closure.empty ()) // ### not true.
+ return;
+
+ typedef QMap<Name, _Bucket> bucket_map_type;
+
+ bucket_map_type buckets;
+ QStack<ItemPointer> working_list;
+
+ for (ItemPointer item = state->kernel.begin (); item != state->kernel.end (); ++item)
+ working_list.push (item);
+
+ state->closure = state->kernel;
+
+ while (! working_list.empty ())
+ {
+ ItemPointer item = working_list.top ();
+ working_list.pop ();
+
+ if (item->isReduceItem ())
+ continue;
+
+ buckets [*item->dot].insert (item);
+
+ if (_M_grammar->isNonTerminal (*item->dot))
+ {
+ foreach (RulePointer rule, _M_grammar->rule_map.values (*item->dot))
+ {
+ Item ii;
+ ii.rule = rule;
+ ii.dot = rule->rhs.begin ();
+
+ QPair<ItemPointer, bool> r = state->insertClosure (ii);
+
+ if (r.second)
+ working_list.push (r.first);
+ }
+ }
+ }
+
+ QList<StatePointer> todo;
+
+ for (bucket_map_type::iterator bucket = buckets.begin (); bucket != buckets.end (); ++bucket)
+ {
+ QPair<StatePointer, bool> r = internState (bucket->toState (this));
+
+ StatePointer target = r.first;
+
+ if (r.second)
+ todo.push_back (target);
+
+ state->bundle.insert (bucket.key(), target);
+ }
+
+ while (! todo.empty ())
+ {
+ closure (todo.front ());
+ todo.pop_front ();
+ }
+}
+
+void Automaton::buildLookbackSets ()
+{
+ for (StatePointer p = states.begin (); p != states.end (); ++p)
+ {
+ for (Bundle::iterator a = p->bundle.begin (); a != p->bundle.end (); ++a)
+ {
+ Name A = a.key ();
+
+ if (! _M_grammar->isNonTerminal (A))
+ continue;
+
+ foreach (RulePointer rule, _M_grammar->rule_map.values (A))
+ {
+ StatePointer q = p;
+
+ for (NameList::iterator dot = rule->rhs.begin (); dot != rule->rhs.end (); ++dot)
+ q = q->bundle.value (*dot, states.end ());
+
+ Q_ASSERT (q != states.end ());
+
+ ItemPointer item = q->closure.begin ();
+
+ for (; item != q->closure.end (); ++item)
+ {
+ if (item->rule == rule && item->dot == item->end_rhs ())
+ break;
+ }
+
+ if (item == q->closure.end ())
+ {
+ Q_ASSERT (q == p);
+ Q_ASSERT (rule->rhs.begin () == rule->rhs.end ());
+
+ for (item = q->closure.begin (); item != q->closure.end (); ++item)
+ {
+ if (item->rule == rule && item->dot == item->end_rhs ())
+ break;
+ }
+ }
+
+ Q_ASSERT (item != q->closure.end ());
+
+ lookbacks.insert (item, Lookback (p, A));
+
+#ifndef QLALR_NO_DEBUG_LOOKBACKS
+ qerr << "*** (" << id (q) << ", " << *rule << ") lookback (" << id (p) << ", " << *A << ")" << endl;
+#endif
+ }
+ }
+ }
+}
+
+void Automaton::buildDirectReads ()
+{
+ for (StatePointer q = states.begin (); q != states.end (); ++q)
+ {
+ for (Bundle::iterator a = q->bundle.begin (); a != q->bundle.end (); ++a)
+ {
+ if (! _M_grammar->isNonTerminal (a.key ()))
+ continue;
+
+ StatePointer r = a.value ();
+
+ for (Bundle::iterator z = r->bundle.begin (); z != r->bundle.end (); ++z)
+ {
+ Name sym = z.key ();
+
+ if (! _M_grammar->isTerminal (sym))
+ continue;
+
+ q->reads [a.key ()].insert (sym);
+ }
+ }
+
+#ifndef QLALR_NO_DEBUG_DIRECT_READS
+ for (QMap<Name, NameSet>::iterator dr = q->reads.begin (); dr != q->reads.end (); ++dr)
+ qerr << "*** DR(" << id (q) << ", " << dr.key () << ") = " << dr.value () << endl;
+#endif
+ }
+}
+
+void Automaton::buildReadsDigraph ()
+{
+ for (StatePointer q = states.begin (); q != states.end (); ++q)
+ {
+ for (Bundle::iterator a = q->bundle.begin (); a != q->bundle.end (); ++a)
+ {
+ if (! _M_grammar->isNonTerminal (a.key ()))
+ continue;
+
+ StatePointer r = a.value ();
+
+ for (Bundle::iterator z = r->bundle.begin (); z != r->bundle.end (); ++z)
+ {
+ Name sym = z.key ();
+
+ if (! _M_grammar->isNonTerminal(sym) || nullables.find (sym) == nullables.end ())
+ continue;
+
+ ReadsGraph::iterator source = ReadsGraph::get (Read (q, a.key ()));
+ ReadsGraph::iterator target = ReadsGraph::get (Read (r, sym));
+
+ source->insertEdge (target);
+
+#ifndef QLALR_NO_DEBUG_READS
+ qerr << "*** ";
+ dump (qerr, source);
+ qerr << " reads ";
+ dump (qerr, target);
+ qerr << endl;
+#endif
+ }
+ }
+ }
+}
+
+void Automaton::buildReads ()
+{
+ buildDirectReads ();
+ buildReadsDigraph ();
+
+ _M_reads_dfn = 0;
+
+ for (ReadsGraph::iterator node = ReadsGraph::begin_nodes (); node != ReadsGraph::end_nodes (); ++node)
+ {
+ if (! node->root)
+ continue;
+
+ visitReadNode (node);
+ }
+
+ for (ReadsGraph::iterator node = ReadsGraph::begin_nodes (); node != ReadsGraph::end_nodes (); ++node)
+ visitReadNode (node);
+}
+
+void Automaton::visitReadNode (ReadNode node)
+{
+ if (node->dfn != 0)
+ return; // nothing to do
+
+ int N = node->dfn = ++_M_reads_dfn;
+ _M_reads_stack.push (node);
+
+#ifndef QLALR_NO_DEBUG_INCLUDES
+ // qerr << "*** Debug. visit node (" << id (node->data.state) << ", " << node->data.nt << ") N = " << N << endl;
+#endif
+
+ for (ReadsGraph::edge_iterator edge = node->begin (); edge != node->end (); ++edge)
+ {
+ ReadsGraph::iterator r = *edge;
+ Name nt = r->data.nt;
+
+ visitReadNode (r);
+
+ node->dfn = qMin (N, r->dfn);
+
+ NameSet &dst = node->data.state->reads [node->data.nt];
+ NameSet &src = r->data.state->reads [r->data.nt];
+ dst.insert (src.begin (), src.end ());
+ }
+
+ if (node->dfn == N)
+ {
+ ReadsGraph::iterator tos = _M_reads_stack.top ();
+
+ do {
+ tos = _M_reads_stack.top ();
+ _M_reads_stack.pop ();
+ tos->dfn = INT_MAX;
+ } while (tos != node);
+ }
+}
+
+void Automaton::buildIncludesAndFollows ()
+{
+ for (StatePointer p = states.begin (); p != states.end (); ++p)
+ p->follows = p->reads;
+
+ buildIncludesDigraph ();
+
+ _M_includes_dfn = 0;
+
+ for (IncludesGraph::iterator node = IncludesGraph::begin_nodes (); node != IncludesGraph::end_nodes (); ++node)
+ {
+ if (! node->root)
+ continue;
+
+ visitIncludeNode (node);
+ }
+
+ for (IncludesGraph::iterator node = IncludesGraph::begin_nodes (); node != IncludesGraph::end_nodes (); ++node)
+ visitIncludeNode (node);
+}
+
+void Automaton::buildIncludesDigraph ()
+{
+ for (StatePointer pp = states.begin (); pp != states.end (); ++pp)
+ {
+ for (Bundle::iterator a = pp->bundle.begin (); a != pp->bundle.end (); ++a)
+ {
+ Name name = a.key ();
+
+ if (! _M_grammar->isNonTerminal (name))
+ continue;
+
+ foreach (RulePointer rule, _M_grammar->rule_map.values (name))
+ {
+ StatePointer p = pp;
+
+ for (NameList::iterator A = rule->rhs.begin (); A != rule->rhs.end (); ++A)
+ {
+ NameList::iterator dot = A;
+ ++dot;
+
+ if (_M_grammar->isNonTerminal (*A) && dot == rule->rhs.end ())
+ {
+ // found an include edge.
+ IncludesGraph::iterator target = IncludesGraph::get (Include (pp, name));
+ IncludesGraph::iterator source = IncludesGraph::get (Include (p, *A));
+
+ source->insertEdge (target);
+
+#ifndef QLALR_NO_DEBUG_INCLUDES
+ qerr << "*** (" << id (p) << ", " << *A << ") includes (" << id (pp) << ", " << *name << ")" << endl;
+#endif // QLALR_NO_DEBUG_INCLUDES
+
+ continue;
+ }
+
+ p = p->bundle.value (*A);
+
+ if (! _M_grammar->isNonTerminal (*A))
+ continue;
+
+ NameList::iterator first_not_nullable = std::find_if (dot, rule->rhs.end (), std::not1 (_Nullable (this)));
+ if (first_not_nullable != rule->rhs.end ())
+ continue;
+
+ // found an include edge.
+ IncludesGraph::iterator target = IncludesGraph::get (Include (pp, name));
+ IncludesGraph::iterator source = IncludesGraph::get (Include (p, *A));
+
+ source->insertEdge (target);
+
+#ifndef QLALR_NO_DEBUG_INCLUDES
+ qerr << "*** (" << id (p) << ", " << *A << ") includes (" << id (pp) << ", " << *name << ")" << endl;
+#endif // QLALR_NO_DEBUG_INCLUDES
+ }
+ }
+ }
+ }
+}
+
+void Automaton::visitIncludeNode (IncludeNode node)
+{
+ if (node->dfn != 0)
+ return; // nothing to do
+
+ int N = node->dfn = ++_M_includes_dfn;
+ _M_includes_stack.push (node);
+
+#ifndef QLALR_NO_DEBUG_INCLUDES
+ // qerr << "*** Debug. visit node (" << id (node->data.state) << ", " << node->data.nt << ") N = " << N << endl;
+#endif
+
+ for (IncludesGraph::edge_iterator edge = node->begin (); edge != node->end (); ++edge)
+ {
+ IncludesGraph::iterator r = *edge;
+ Name nt = r->data.nt;
+
+ visitIncludeNode (r);
+
+ node->dfn = qMin (N, r->dfn);
+
+#ifndef QLALR_NO_DEBUG_INCLUDES
+ qerr << "*** Merge. follows";
+ dump (qerr, node);
+ qerr << " += follows";
+ dump (qerr, r);
+ qerr << endl;
+#endif
+
+ NameSet &dst = node->data.state->follows [node->data.nt];
+ NameSet &src = r->data.state->follows [r->data.nt];
+
+ dst.insert (src.begin (), src.end ());
+ }
+
+ if (node->dfn == N)
+ {
+ IncludesGraph::iterator tos = _M_includes_stack.top ();
+
+ do {
+ tos = _M_includes_stack.top ();
+ _M_includes_stack.pop ();
+ tos->dfn = INT_MAX;
+ } while (tos != node);
+ }
+}
+
+void Automaton::buildLookaheads ()
+{
+ for (StatePointer p = states.begin (); p != states.end (); ++p)
+ {
+ for (ItemPointer item = p->closure.begin (); item != p->closure.end (); ++item)
+ {
+ foreach (Lookback lookback, lookbacks.values (item))
+ {
+ StatePointer q = lookback.state;
+
+#ifndef QLALR_NO_DEBUG_LOOKAHEADS
+ qerr << "(" << id (p) << ", " << *item->rule << ") lookbacks ";
+ dump (qerr, lookback);
+ qerr << " with follows (" << id (q) << ", " << lookback.nt << ") = " << q->follows [lookback.nt] << endl;
+#endif
+
+ lookaheads [item].insert (q->follows [lookback.nt].begin (), q->follows [lookback.nt].end ());
+ }
+ }
+
+ // propagate the lookahead in the kernel
+ ItemPointer k = p->kernel.begin ();
+ ItemPointer c = p->closure.begin ();
+
+ for (; k != p->kernel.end (); ++k, ++c)
+ lookaheads [k] = lookaheads [c];
+ }
+}
+
+void Automaton::buildDefaultReduceActions ()
+{
+ for (StatePointer state = states.begin (); state != states.end (); ++state)
+ {
+ ItemPointer def = state->closure.end ();
+ int size = -1;
+
+ for (ItemPointer item = state->closure.begin (); item != state->closure.end (); ++item)
+ {
+ if (item->dot != item->end_rhs ())
+ continue;
+
+ int la = lookaheads.value (item).size ();
+ if (def == state->closure.end () || la > size)
+ {
+ def = item;
+ size = la;
+ }
+ }
+
+ if (def != state->closure.end ())
+ {
+ Q_ASSERT (size >= 0);
+ state->defaultReduce = def->rule;
+ }
+ }
+}
+
+void Automaton::dump (QTextStream &out, IncludeNode incl)
+{
+ out << "(" << id (incl->data.state) << ", " << incl->data.nt << ")";
+}
+
+void Automaton::dump (QTextStream &out, ReadNode rd)
+{
+ out << "(" << id (rd->data.state) << ", " << rd->data.nt << ")";
+}
+
+void Automaton::dump (QTextStream &out, const Lookback &lp)
+{
+ out << "(" << id (lp.state) << ", " << lp.nt << ")";
+}
diff --git a/src/lalr.g b/src/lalr.g
new file mode 100644
index 0000000..cee223d
--- /dev/null
+++ b/src/lalr.g
@@ -0,0 +1,800 @@
+-----------------------------------------------------------------------------
+--
+-- Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+-- All rights reserved.
+-- Contact: Nokia Corporation (qt-info@nokia.com)
+--
+-- This file is part of the QLALR project on Qt Labs.
+--
+-- $QT_BEGIN_LICENSE:LGPL$
+-- No Commercial Usage
+-- This file contains pre-release code and may not be distributed.
+-- You may use this file in accordance with the terms and conditions
+-- contained in the Technology Preview License Agreement accompanying
+-- this package.
+--
+-- GNU Lesser General Public License Usage
+-- Alternatively, this file may be used under the terms of the GNU Lesser
+-- General Public License version 2.1 as published by the Free Software
+-- Foundation and appearing in the file LICENSE.LGPL included in the
+-- packaging of this file. Please review the following information to
+-- ensure the GNU Lesser General Public License version 2.1 requirements
+-- will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+--
+-- In addition, as a special exception, Nokia gives you certain additional
+-- rights. These rights are described in the Nokia Qt LGPL Exception
+-- version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+--
+-- If you have questions regarding the use of this file, please contact
+-- Nokia at qt-info@nokia.com.
+--
+--
+--
+--
+--
+--
+--
+--
+-- $QT_END_LICENSE$
+--
+-----------------------------------------------------------------------------
+
+
+%parser grammar
+
+%decl recognizer.h
+%impl recognizer.cpp
+
+%token ID "identifier"
+%token STRING_LITERAL "string literal"
+
+%token DECL_FILE "%decl"
+%token EXPECT "%expect"
+%token EXPECT_RR "%expect-lr"
+%token IMPL_FILE "%impl"
+%token LEFT "%left"
+%token MERGED_OUTPUT "%merged_output"
+%token NONASSOC "%nonassoc"
+%token PARSER "%parser"
+%token PREC "%prec"
+%token RIGHT "%right"
+%token START "%start"
+%token TOKEN "%token"
+%token TOKEN_PREFIX "%token_prefix"
+
+%token COLON ":"
+%token OR "|"
+%token SEMICOLON ";"
+
+%token DECL
+%token IMPL
+
+%token ERROR
+
+%start Specification
+
+
+/:
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the QLALR project on Qt Labs.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include <QtCore/QtDebug>
+#include <QtCore/QString>
+#include <QtCore/QFile>
+#include <QtCore/QTextStream>
+
+#include "$header"
+#include "lalr.h"
+
+#include <cstdlib>
+
+class Recognizer: protected $table
+{
+public:
+ Recognizer (Grammar *grammar, bool no_lines);
+ ~Recognizer();
+
+ bool parse (const QString &input_file = QString ());
+
+ inline QString decls () const { return _M_decls; }
+ inline QString impls () const { return _M_impls; }
+
+protected:
+ inline void reallocateStack ();
+
+ inline QString &sym (int index)
+ { return sym_stack [tos + index - 1]; }
+
+protected: // scanner
+ int nextToken();
+
+ inline void inp ()
+ {
+ if (_M_currentChar != _M_lastChar)
+ {
+ ch = *_M_currentChar++;
+
+ if (ch == QLatin1Char('\n'))
+ ++_M_line;
+ }
+ else
+ ch = QChar();
+ }
+
+ QString expand (const QString &text) const;
+
+protected:
+ // recognizer
+ int tos;
+ int stack_size;
+ QVector<QString> sym_stack;
+ int *state_stack;
+
+ QString _M_contents;
+ QString::const_iterator _M_firstChar;
+ QString::const_iterator _M_lastChar;
+ QString::const_iterator _M_currentChar;
+
+ // scanner
+ QChar ch;
+ int _M_line;
+ int _M_action_line;
+ Grammar *_M_grammar;
+ RulePointer _M_current_rule;
+ QString _M_input_file;
+
+ QString _M_decls;
+ QString _M_impls;
+ QString _M_current_value;
+ bool _M_no_lines;
+};
+:/
+
+/.
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the QLALR project on Qt Labs.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "recognizer.h"
+#include <cstdlib>
+#include <cstring>
+#include <cctype>
+
+Recognizer::Recognizer (Grammar *grammar, bool no_lines):
+ tos(0),
+ stack_size(0),
+ state_stack(0),
+ _M_line(1),
+ _M_action_line(0),
+ _M_grammar(grammar),
+ _M_no_lines(no_lines)
+{
+}
+
+Recognizer::~Recognizer()
+{
+ if (stack_size)
+ ::qFree(state_stack);
+}
+
+inline void Recognizer::reallocateStack()
+{
+ if (! stack_size)
+ stack_size = 128;
+ else
+ stack_size <<= 1;
+
+ sym_stack.resize (stack_size);
+
+ if (! state_stack)
+ state_stack = reinterpret_cast<int*> (::qMalloc(stack_size * sizeof(int)));
+ else
+ state_stack = reinterpret_cast<int*> (::qRealloc(state_stack, stack_size * sizeof(int)));
+}
+
+int Recognizer::nextToken()
+{
+ QString text;
+
+ Lagain:
+ while (ch.isSpace ())
+ inp ();
+
+ if (ch.isNull ())
+ return EOF_SYMBOL;
+
+ int token = ch.unicode ();
+
+ if (token == '"')
+ {
+ inp(); // skip "
+ text.clear ();
+ while (! ch.isNull () && ch != QLatin1Char ('"'))
+ {
+ if (ch == QLatin1Char ('\\'))
+ {
+ text += ch;
+ inp();
+ }
+ text += ch;
+ inp ();
+ }
+
+ if (ch == QLatin1Char ('"'))
+ inp ();
+ else
+ qerr << _M_input_file << ":" << _M_line << ": Warning. Expected `\"'" << endl;
+
+ _M_current_value = text;
+ return (token = STRING_LITERAL);
+ }
+
+ else if (ch.isLetterOrNumber () || ch == QLatin1Char ('_'))
+ {
+ text.clear ();
+ do { text += ch; inp (); }
+ while (ch.isLetterOrNumber () || ch == QLatin1Char ('_') || ch == QLatin1Char ('.'));
+ _M_current_value = text;
+ return (token = ID);
+ }
+
+ else if (token == '%')
+ {
+ text.clear ();
+
+ do { inp (); }
+ while (ch.isSpace ());
+
+ do { text += ch; inp (); }
+ while (ch.isLetterOrNumber () || ch == QLatin1Char ('_') || ch == QLatin1Char ('-'));
+
+ if (text == QLatin1String("token_prefix"))
+ return (token = TOKEN_PREFIX);
+ else if (text == QLatin1String("merged_output"))
+ return (token = MERGED_OUTPUT);
+ else if (text == QLatin1String("token"))
+ return (token = TOKEN);
+ else if (text == QLatin1String("start"))
+ return (token = START);
+ else if (text == QLatin1String("parser"))
+ return (token = PARSER);
+ else if (text == QLatin1String("decl"))
+ return (token = DECL_FILE);
+ else if (text == QLatin1String("impl"))
+ return (token = IMPL_FILE);
+ else if (text == QLatin1String("expect"))
+ return (token = EXPECT);
+ else if (text == QLatin1String("expect-rr"))
+ return (token = EXPECT_RR);
+ else if (text == QLatin1String("left"))
+ return (token = LEFT);
+ else if (text == QLatin1String("right"))
+ return (token = RIGHT);
+ else if (text == QLatin1String("nonassoc"))
+ return (token = NONASSOC);
+ else if (text == QLatin1String("prec"))
+ return (token = PREC);
+ else
+ {
+ qerr << _M_input_file << ":" << _M_line << ": Unknown keyword `" << text << "'" << endl;
+ exit (EXIT_FAILURE);
+ return (token = ERROR);
+ }
+ }
+
+ inp ();
+
+ if (token == '-' && ch == QLatin1Char ('-'))
+ {
+ do { inp (); }
+ while (! ch.isNull () && ch != QLatin1Char ('\n'));
+ goto Lagain;
+ }
+
+ else if (token == ':' && ch == QLatin1Char (':'))
+ {
+ inp ();
+ if (ch != QLatin1Char ('='))
+ return (token = ERROR);
+ inp ();
+ return (token = COLON);
+ }
+
+ else if (token == '/' && ch == QLatin1Char (':'))
+ {
+ _M_action_line = _M_line;
+
+ text.clear ();
+ if (! _M_no_lines)
+ text += QLatin1String ("\n#line ") + QString::number (_M_action_line) + " \"" + _M_input_file + "\"\n";
+ inp (); // skip ':'
+
+ forever
+ {
+ while (! ch.isNull ())
+ {
+ token = ch.unicode ();
+ inp ();
+
+ if (token == ':' && ch == QLatin1Char ('/'))
+ break;
+
+ text += QLatin1Char (token);
+ }
+
+ if (ch != QLatin1Char ('/'))
+ return (token = ERROR);
+
+ inp ();
+
+ if (ch.isNull () || ch.isSpace ())
+ {
+ _M_current_value = text;
+ return (token = DECL);
+ }
+ else
+ text += QLatin1String (":/");
+ }
+ }
+
+ else if (token == '/' && ch == QLatin1Char ('.'))
+ {
+ _M_action_line = _M_line;
+
+ text.clear ();
+ if (! _M_no_lines)
+ text += QLatin1String ("\n#line ") + QString::number (_M_action_line) + " \"" + _M_input_file + "\"\n";
+
+ inp (); // skip ':'
+
+ forever
+ {
+ while (! ch.isNull ())
+ {
+ token = ch.unicode ();
+ inp ();
+
+ if (token == '.' && ch == QLatin1Char ('/'))
+ break;
+
+ text += QLatin1Char (token);
+ }
+
+ if (ch != QLatin1Char ('/'))
+ return (token = ERROR);
+
+ inp ();
+
+ if (ch.isNull () || ch.isSpace ())
+ {
+ _M_current_value = text;
+ return (token = IMPL);
+ }
+ else
+ text += QLatin1String ("./");
+ }
+ }
+
+ switch (token) {
+ case ':':
+ return (token = COLON);
+
+ case ';':
+ return (token = SEMICOLON);
+
+ case '|':
+ return (token = OR);
+
+ default:
+ break;
+ }
+
+ return token;
+}
+
+bool Recognizer::parse (const QString &input_file)
+{
+ _M_input_file = input_file;
+
+ QFile file(_M_input_file);
+ if (! file.open(QFile::ReadOnly))
+ {
+ qerr << "qlalr: no input file\n";
+ return false;
+ }
+
+ QString _M_contents = QTextStream(&file).readAll();
+ _M_firstChar = _M_contents.constBegin();
+ _M_lastChar = _M_contents.constEnd();
+ _M_currentChar = _M_firstChar;
+ _M_line = 1;
+
+ int yytoken = -1;
+ inp ();
+
+ reallocateStack();
+
+ _M_current_rule = _M_grammar->rules.end ();
+ _M_decls.clear ();
+ _M_impls.clear ();
+
+ tos = 0;
+ state_stack[++tos] = 0;
+
+ while (true)
+ {
+ if (yytoken == -1 && - TERMINAL_COUNT != action_index [state_stack [tos]])
+ yytoken = nextToken();
+
+ int act = t_action (state_stack [tos], yytoken);
+
+ if (act == ACCEPT_STATE)
+ return true;
+
+ else if (act > 0)
+ {
+ if (++tos == stack_size)
+ reallocateStack();
+
+ sym_stack [tos] = _M_current_value;
+ state_stack [tos] = act;
+ yytoken = -1;
+ }
+
+ else if (act < 0)
+ {
+ int r = - act - 1;
+
+ tos -= rhs [r];
+ act = state_stack [tos++];
+
+ switch (r) {
+./
+
+----------------------------------------------------------- SPECS
+Specification ::= Options Tokens Start Rules ;
+
+Options ::= Empty ;
+Options ::= Options Option ;
+
+StartHeader ::= START ID ;
+/.
+case $rule_number: {
+ Name name = _M_grammar->intern (sym(2));
+ _M_grammar->start = name;
+ _M_grammar->non_terminals.insert (name);
+} break;
+./
+
+Start ::= StartHeader UserActionOpt ;
+
+----------------------------------------------------------- OPTIONS
+Option ::= PARSER ID ;
+/.
+case $rule_number: {
+ _M_grammar->table_name = sym(2);
+} break;
+./
+
+Option ::= MERGED_OUTPUT ID ;
+/.
+case $rule_number: {
+ _M_grammar->merged_output = sym(2);
+} break;
+./
+
+Option ::= DECL_FILE ID ;
+/.
+case $rule_number: {
+ _M_grammar->decl_file_name = sym(2);
+} break;
+./
+
+
+Option ::= IMPL_FILE ID ;
+/.
+case $rule_number: {
+ _M_grammar->impl_file_name = sym(2);
+} break;
+./
+
+Option ::= EXPECT ID ;
+/.
+case $rule_number: {
+ _M_grammar->expected_shift_reduce = sym(2).toInt();
+} break;
+./
+
+Option ::= EXPECT_RR ID ;
+/.
+case $rule_number: {
+ _M_grammar->expected_reduce_reduce = sym(2).toInt();
+} break;
+./
+
+
+Option ::= TOKEN_PREFIX ID ;
+/.
+case $rule_number: {
+ _M_grammar->token_prefix = sym(2);
+} break;
+./
+
+
+----------------------------------------------------------- TOKENS
+Tokens ::= Empty ;
+Tokens ::= Tokens Token ;
+
+Token ::= TOKEN TerminalList ;
+
+TerminalList ::= Terminal ;
+
+TerminalList ::= TerminalList Terminal ;
+
+Terminal ::= ID Empty ;
+/.case $rule_number:./
+
+Terminal ::= ID STRING_LITERAL ;
+/.case $rule_number: {
+ Name name = _M_grammar->intern (sym(1));
+ _M_grammar->terminals.insert (name);
+ _M_grammar->spells.insert (name, sym(2));
+} break;
+./
+
+PrecHeader: LEFT ;
+/.
+case $rule_number: {
+ _M_grammar->current_assoc = Grammar::Left;
+ ++_M_grammar->current_prec;
+} break;
+./
+
+PrecHeader: RIGHT ;
+/.
+case $rule_number: {
+ _M_grammar->current_assoc = Grammar::Right;
+ ++_M_grammar->current_prec;
+} break;
+./
+
+PrecHeader: NONASSOC ;
+/.
+case $rule_number: {
+ _M_grammar->current_assoc = Grammar::NonAssoc;
+ ++_M_grammar->current_prec;
+} break;
+./
+
+Token ::= PrecHeader TokenList ;
+
+TokenList ::= TokenId ;
+TokenList ::= TokenList TokenId ;
+
+TokenId ::= ID ;
+/.
+case $rule_number: {
+ Name name = _M_grammar->intern (sym(1));
+ _M_grammar->terminals.insert (name);
+
+ Grammar::TokenInfo info;
+ info.prec = _M_grammar->current_prec;
+ info.assoc = _M_grammar->current_assoc;
+ _M_grammar->token_info.insert (name, info);
+} break;
+./
+
+----------------------------------------------------------- Code
+Code ::= DECL ;
+/.
+case $rule_number: {
+ _M_decls += expand (sym(1));
+} break;
+./
+
+
+Code ::= IMPL ;
+/.
+case $rule_number: {
+ _M_impls += expand (sym(1));
+} break;
+./
+
+UserAction ::= Code ;
+UserAction ::= UserAction Code ;
+
+UserActionOpt ::= ;
+UserActionOpt ::= UserAction ;
+
+----------------------------------------------------------- RULES
+Rules ::= Empty ;
+Rules ::= Rules Rule ;
+
+RuleHeader ::= ID COLON ;
+/.
+case $rule_number: {
+ _M_current_rule = _M_grammar->rules.insert (_M_grammar->rules.end (), Rule ());
+ _M_current_rule->lhs = _M_grammar->intern (sym(1));
+ _M_grammar->declared_lhs.insert (_M_current_rule->lhs);
+
+ if (_M_grammar->terminals.find (_M_current_rule->lhs) != _M_grammar->terminals.end ())
+ {
+ qerr << _M_input_file << ":" << _M_line << ": Invalid non terminal `" << *_M_current_rule->lhs << "'" << endl;
+ return false;
+ }
+
+ _M_grammar->non_terminals.insert (_M_current_rule->lhs);
+} break;
+./
+
+
+Rule ::= RuleHeader RuleDefinition SEMICOLON UserActionOpt ;
+
+RuleDefinition ::= Symbols PrecOpt UserActionOpt ;
+RuleDefinition ::= RuleDefinition NewRule OR Symbols PrecOpt UserActionOpt ;
+
+NewRule ::= ;
+/.
+case $rule_number: {
+ Name lhs = _M_current_rule->lhs;
+ _M_current_rule = _M_grammar->rules.insert (_M_grammar->rules.end (), Rule ());
+ _M_current_rule->lhs = lhs;
+ _M_grammar->declared_lhs.insert (_M_current_rule->lhs);
+
+ if (_M_grammar->terminals.find (_M_current_rule->lhs) != _M_grammar->terminals.end ())
+ {
+ qerr << _M_input_file << ":" << _M_line << ": Invalid non terminal `" << *_M_current_rule->lhs << "'" << endl;
+ return false;
+ }
+
+ _M_grammar->non_terminals.insert (_M_current_rule->lhs);
+} break;
+./
+
+PrecOpt ::= ;
+/.
+case $rule_number: {
+ _M_current_rule->prec = _M_grammar->names.end ();
+
+ for (NameList::iterator it = _M_current_rule->rhs.begin (); it != _M_current_rule->rhs.end (); ++it)
+ {
+ if (! _M_grammar->isTerminal (*it))
+ continue;
+
+ _M_current_rule->prec = *it;
+ }
+} break;
+./
+
+PrecOpt ::= PREC ID ;
+/.
+case $rule_number: {
+ Name tok = _M_grammar->intern (sym(2));
+ if (! _M_grammar->isTerminal (tok))
+ {
+ qerr << _M_input_file << ":" << _M_line << ": `" << *tok << " is not a terminal symbol" << endl;
+ _M_current_rule->prec = _M_grammar->names.end ();
+ }
+ else
+ _M_current_rule->prec = tok;
+} break;
+./
+
+----------------------------------------------------------- SYMBOLS
+Symbols ::= Empty ;
+Symbols ::= Symbols ID ;
+/.
+case $rule_number: {
+ Name name = _M_grammar->intern (sym(2));
+
+ if (_M_grammar->terminals.find (name) == _M_grammar->terminals.end ())
+ _M_grammar->non_terminals.insert (name);
+
+ _M_current_rule->rhs.push_back (name);
+} break;
+./
+
+----------------------------------------------------------- HELPERS
+Empty ::= ;
+/.
+case $rule_number: {
+ sym(1) = QString();
+} break;
+./
+
+
+
+
+----------------------------------------------------------- END
+/.
+ } // switch
+
+ state_stack [tos] = nt_action (act, lhs [r] - TERMINAL_COUNT);
+ }
+
+ else
+ {
+ break;
+ }
+ }
+
+ qerr << _M_input_file << ":" << _M_line << ": Syntax error" << endl;
+ return false;
+}
+
+./
diff --git a/src/lalr.h b/src/lalr.h
new file mode 100644
index 0000000..8259a25
--- /dev/null
+++ b/src/lalr.h
@@ -0,0 +1,502 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the utils of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef LALR_H
+#define LALR_H
+
+#include <functional>
+
+#include <QtCore/QSet>
+#include <QtCore/QStack>
+#include <QtCore/QMap>
+#include <QtCore/QLinkedList>
+#include <QtCore/QString>
+#include <QtCore/QTextStream>
+#include <QtCore/QPair>
+
+class Rule;
+class State;
+class Grammar;
+class Item;
+class State;
+class Arrow;
+class Automaton;
+
+template <typename _Tp >
+class OrderedSet : protected QMap<_Tp, bool>
+{
+ typedef QMap<_Tp, bool> _Base;
+
+public:
+ class const_iterator
+ {
+ typename _Base::const_iterator _M_iterator;
+
+ public:
+ const_iterator () {}
+
+ const_iterator (const typename _Base::const_iterator &it):
+ _M_iterator (it) {}
+
+ const _Tp &operator * () const
+ { return _M_iterator.key (); }
+
+ const _Tp *operator -> () const
+ { return &_M_iterator.key (); }
+
+ const_iterator &operator ++ ()
+ { ++_M_iterator; return *this; }
+
+ const_iterator operator ++ (int) const
+ {
+ const_iterator me (*this);
+ ++_M_iterator;
+ return me;
+ }
+
+ bool operator == (const const_iterator &other) const
+ { return _M_iterator == other._M_iterator; }
+
+ bool operator != (const const_iterator &other) const
+ { return _M_iterator != other._M_iterator; }
+ };
+
+ typedef const_iterator iterator;
+
+public:
+ OrderedSet () {}
+
+ const_iterator begin () const
+ { return const_iterator (_Base::begin ()); }
+
+ const_iterator end () const
+ { return const_iterator (_Base::end ()); }
+
+ bool isEmpty () const
+ { return _Base::isEmpty (); }
+
+ int size () const
+ { return _Base::size (); }
+
+ const_iterator find (const _Tp &elt) const
+ { return const_iterator (_Base::find (elt)); }
+
+ QPair<const_iterator, bool> insert (const _Tp &elt)
+ {
+ int elts = _Base::size ();
+ const_iterator it (_Base::insert (typename _Base::key_type (elt), true));
+ return qMakePair (it, elts != _Base::size ());
+ }
+
+ QPair<const_iterator, bool> insert (const_iterator, const _Tp &elt)
+ {
+ int elts = _Base::size ();
+ const_iterator it (_Base::insert (typename _Base::key_type (elt), true));
+ return qMakePair (it, elts != _Base::size ());
+ }
+
+ const _Tp &operator [] (const _Tp &elt)
+ { return *insert (elt)->first; }
+
+ template <typename _InputIterator>
+ void insert (_InputIterator first, _InputIterator last)
+ {
+ for (; first != last; ++first)
+ insert (*first);
+ }
+};
+
+// names
+typedef QLinkedList<QString>::iterator Name;
+typedef QLinkedList<Name> NameList;
+typedef OrderedSet<Name> NameSet;
+
+// items
+typedef QLinkedList<Item> ItemList;
+typedef ItemList::iterator ItemPointer;
+
+// rules
+typedef QLinkedList<Rule> debug_infot;
+typedef debug_infot::iterator RulePointer;
+typedef QMultiMap<Name, RulePointer> RuleMap;
+
+// states
+typedef QLinkedList<State> StateList;
+typedef StateList::iterator StatePointer;
+
+// arrows
+typedef QMap<Name, StatePointer> Bundle;
+
+class Rule
+{
+public:
+ void clear ()
+ {
+ lhs = Name ();
+ rhs.clear ();
+ prec = Name ();
+ }
+
+public:
+ Name lhs;
+ NameList rhs;
+ Name prec;
+};
+
+class Lookback
+{
+public:
+ Lookback (StatePointer s, Name n):
+ state (s), nt (n) {}
+
+ inline bool operator == (const Lookback &other) const
+ { return state == other.state && nt == other.nt; }
+
+ inline bool operator != (const Lookback &other) const
+ { return state != other.state || nt != other.nt; }
+
+ bool operator < (const Lookback &other) const;
+
+public:
+ StatePointer state;
+ Name nt;
+};
+
+class Item
+{
+public:
+ inline NameList::iterator begin_rhs () const
+ { return rule->rhs.begin (); }
+
+ inline NameList::iterator end_rhs () const
+ { return rule->rhs.end (); }
+
+ inline bool operator == (const Item &other) const
+ { return rule == other.rule && dot == other.dot; }
+
+ inline bool operator != (const Item &other) const
+ { return rule != other.rule || dot != other.dot; }
+
+ inline bool isReduceItem () const
+ { return dot == rule->rhs.end (); }
+
+ Item next () const;
+
+public:
+ RulePointer rule;
+ NameList::iterator dot;
+};
+
+class State
+{
+public:
+ State (Grammar *grammar);
+
+ inline bool operator == (const State &other) const
+ { return kernel == other.kernel; }
+
+ inline bool operator != (const State &other) const
+ { return kernel != other.kernel; }
+
+ QPair<ItemPointer, bool> insert (const Item &item);
+ QPair<ItemPointer, bool> insertClosure (const Item &item);
+
+public: // attributes
+ ItemList kernel;
+ ItemList closure;
+ Bundle bundle;
+ QMap<Name, NameSet> reads;
+ QMap<Name, NameSet> follows;
+ RulePointer defaultReduce;
+};
+
+/////////////////////////////////////////////////////////////
+// digraph
+/////////////////////////////////////////////////////////////
+template <typename _Tp>
+class Node
+{
+public:
+ typedef OrderedSet<Node<_Tp> > Repository;
+ typedef typename Repository::iterator iterator;
+ typedef typename QLinkedList<iterator>::iterator edge_iterator;
+
+public:
+ static iterator get (_Tp data);
+
+ QPair<edge_iterator, bool> insertEdge (iterator other) const;
+
+ inline edge_iterator begin () const
+ { return outs.begin (); }
+
+ inline edge_iterator end () const
+ { return outs.end (); }
+
+ inline bool operator == (const Node<_Tp> &other) const
+ { return data == other.data; }
+
+ inline bool operator != (const Node<_Tp> &other) const
+ { return data != other.data; }
+
+ inline bool operator < (const Node<_Tp> &other) const
+ { return data < other.data; }
+
+ static inline iterator begin_nodes ()
+ { return repository ().begin (); }
+
+ static inline iterator end_nodes ()
+ { return repository ().end (); }
+
+ static Repository &repository ()
+ {
+ static Repository r;
+ return r;
+ }
+
+public: // attributes
+ mutable bool root;
+ mutable int dfn;
+ mutable _Tp data;
+ mutable QLinkedList<iterator> outs;
+
+protected:
+ inline Node () {}
+
+ inline Node (_Tp d):
+ root (true), dfn (0), data (d) {}
+};
+
+template <typename _Tp>
+typename Node<_Tp>::iterator Node<_Tp>::get (_Tp data)
+{
+ Node<_Tp> tmp (data);
+ iterator it = repository ().find (tmp);
+
+ if (it != repository ().end ())
+ return it;
+
+ return repository ().insert (tmp).first;
+}
+
+template <typename _Tp>
+QPair<typename QLinkedList<typename Node<_Tp>::iterator>::iterator, bool> Node<_Tp>::insertEdge (typename Node<_Tp>::iterator other) const
+{
+ edge_iterator it = qFind (outs.begin (), outs.end (), other);
+
+ if (it != outs.end ())
+ return qMakePair (it, false);
+
+ other->root = false;
+ return qMakePair (outs.insert (outs.end (), other), true);
+}
+
+/////////////////////////////////////////////////////////////
+// Grammar
+/////////////////////////////////////////////////////////////
+class Grammar
+{
+public:
+ Grammar ();
+
+ Name intern (const QString &id);
+
+ inline bool isTerminal (Name name) const
+ { return terminals.find (name) != terminals.end (); }
+
+ inline bool isNonTerminal (Name name) const
+ { return non_terminals.find (name) != non_terminals.end (); }
+
+ void buildRuleMap ();
+ void buildExtendedGrammar ();
+
+public:
+ QString merged_output;
+ QString table_name;
+ QString decl_file_name;
+ QString impl_file_name;
+ QString token_prefix;
+ QLinkedList<QString> names;
+ Name start;
+ NameSet terminals;
+ NameSet non_terminals;
+ QMap<Name, QString> spells;
+ debug_infot rules;
+ RuleMap rule_map;
+ RulePointer goal;
+ Name tk_end;
+ Name accept_symbol;
+ NameSet declared_lhs;
+ int expected_shift_reduce;
+ int expected_reduce_reduce;
+
+ enum Assoc {
+ NonAssoc,
+ Left,
+ Right
+ };
+
+ struct TokenInfo {
+ Assoc assoc;
+ int prec;
+ };
+
+ QMap<Name, TokenInfo> token_info;
+ Assoc current_assoc;
+ int current_prec;
+};
+
+class Read
+{
+public:
+ inline Read () {}
+
+ inline Read (StatePointer s, Name n):
+ state (s), nt (n) {}
+
+ inline bool operator == (const Read &other) const
+ { return state == other.state && nt == other.nt; }
+
+ inline bool operator != (const Read &other) const
+ { return state != other.state || nt != other.nt; }
+
+ bool operator < (const Read &other) const;
+
+public:
+ StatePointer state;
+ Name nt;
+};
+
+class Include
+{
+public:
+ inline Include () {}
+
+ inline Include (StatePointer s, Name n):
+ state (s), nt (n) {}
+
+ inline bool operator == (const Include &other) const
+ { return state == other.state && nt == other.nt; }
+
+ inline bool operator != (const Include &other) const
+ { return state != other.state || nt != other.nt; }
+
+ bool operator < (const Include &other) const;
+
+public:
+ StatePointer state;
+ Name nt;
+};
+
+class Automaton
+{
+public:
+ Automaton (Grammar *g);
+
+ QPair<StatePointer, bool> internState (const State &state);
+
+ typedef Node<Read> ReadsGraph;
+ typedef ReadsGraph::iterator ReadNode;
+
+ typedef Node<Include> IncludesGraph;
+ typedef IncludesGraph::iterator IncludeNode;
+
+ void build ();
+ void buildNullables ();
+
+ void buildLookbackSets ();
+
+ void buildDirectReads ();
+ void buildReadsDigraph ();
+ void buildReads ();
+ void visitReadNode (ReadNode node);
+
+ void buildIncludesAndFollows ();
+ void buildIncludesDigraph ();
+ void visitIncludeNode (IncludeNode node);
+
+ void buildLookaheads ();
+
+ void buildDefaultReduceActions ();
+
+ void closure (StatePointer state);
+
+ int id (RulePointer rule);
+ int id (StatePointer state);
+ int id (Name name);
+
+ void dump (QTextStream &out, IncludeNode incl);
+ void dump (QTextStream &out, ReadNode rd);
+ void dump (QTextStream &out, const Lookback &lp);
+
+public: // ### private
+ Grammar *_M_grammar;
+ StateList states;
+ StatePointer start;
+ NameSet nullables;
+ QMultiMap<ItemPointer, Lookback> lookbacks;
+ QMap<ItemPointer, NameSet> lookaheads;
+
+private:
+ QStack<ReadsGraph::iterator> _M_reads_stack;
+ int _M_reads_dfn;
+
+ QStack<IncludesGraph::iterator> _M_includes_stack;
+ int _M_includes_dfn;
+};
+
+QT_BEGIN_NAMESPACE
+bool operator < (Name a, Name b);
+bool operator < (StatePointer a, StatePointer b);
+bool operator < (ItemPointer a, ItemPointer b);
+QT_END_NAMESPACE
+
+QTextStream &operator << (QTextStream &out, const Name &n);
+QTextStream &operator << (QTextStream &out, const Rule &r);
+QTextStream &operator << (QTextStream &out, const Item &item);
+QTextStream &operator << (QTextStream &out, const NameSet &ns);
+
+QT_BEGIN_NAMESPACE
+// ... hmm
+extern QTextStream qerr;
+extern QTextStream qout;
+QT_END_NAMESPACE
+
+#endif // LALR_H
diff --git a/src/main.cpp b/src/main.cpp
new file mode 100644
index 0000000..8b2fc91
--- /dev/null
+++ b/src/main.cpp
@@ -0,0 +1,185 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the utils of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include <QtCore/QCoreApplication>
+#include <QtCore/QFile>
+#include <QtCore/QStringList>
+#include <QtCore/QtDebug>
+
+#include <cstdlib>
+
+#include "lalr.h"
+#include "dotgraph.h"
+#include "parsetable.h"
+#include "cppgenerator.h"
+#include "recognizer.h"
+
+#define QLALR_NO_DEBUG_TABLE
+#define QLALR_NO_DEBUG_DOT
+
+static void help_me ()
+{
+ qerr << "Usage: qlalr [options] [input file name]" << endl
+ << endl
+ << " --help, -h\t\tdisplay this help and exit" << endl
+ << " --verbose, -v\t\tverbose output" << endl
+ << " --no-debug\t\tno debug information" << endl
+ << " --no-lines\t\tno #line directives" << endl
+ << " --dot\t\t\tgenerate a graph" << endl
+ << " --qt\t\tadd the Qt copyright header and Qt-specific types and macros" << endl
+ << endl;
+ exit (0);
+}
+
+int main (int argc, char *argv[])
+{
+ QCoreApplication app (argc, argv);
+
+ bool generate_dot = false;
+ bool generate_report = false;
+ bool no_lines = false;
+ bool debug_info = true;
+ bool troll_copyright = false;
+ QString file_name = 0;
+
+ QStringList args = app.arguments ();
+ args.removeFirst ();
+
+ foreach (QString arg, args)
+ {
+ if (arg == QLatin1String ("-h") || arg == QLatin1String ("--help"))
+ help_me ();
+
+ else if (arg == QLatin1String ("-v") || arg == QLatin1String ("--verbose"))
+ generate_report = true;
+
+ else if (arg == QLatin1String ("--dot"))
+ generate_dot = true;
+
+ else if (arg == QLatin1String ("--no-lines"))
+ no_lines = true;
+
+ else if (arg == QLatin1String ("--no-debug"))
+ debug_info = false;
+
+ else if (arg == QLatin1String ("--qt"))
+ troll_copyright = true;
+
+ else if (file_name.isEmpty ())
+ file_name = arg;
+
+ else
+ qerr << "*** Warning. Ignore argument `" << arg << "'" << endl;
+ }
+
+ if (file_name.isEmpty ())
+ {
+ help_me ();
+ exit (EXIT_SUCCESS);
+ }
+
+ Grammar grammar;
+ Recognizer p (&grammar, no_lines);
+
+ if (! p.parse (file_name))
+ exit (EXIT_FAILURE);
+
+ if (grammar.rules.isEmpty ())
+ {
+ qerr << "*** Fatal. No rules!" << endl;
+ exit (EXIT_FAILURE);
+ }
+
+ else if (grammar.start == grammar.names.end ())
+ {
+ qerr << "*** Fatal. No start symbol!" << endl;
+ exit (EXIT_FAILURE);
+ }
+
+ grammar.buildExtendedGrammar ();
+ grammar.buildRuleMap ();
+
+ Automaton aut (&grammar);
+ aut.build ();
+
+ CppGenerator gen (p, grammar, aut, generate_report);
+ gen.setDebugInfo (debug_info);
+ gen.setCopyright (troll_copyright);
+ gen ();
+
+ if (generate_dot)
+ {
+ DotGraph genDotFile (qout);
+ genDotFile (&aut);
+ }
+
+ else if (generate_report)
+ {
+ ParseTable genParseTable (qout);
+ genParseTable(&aut);
+ }
+
+ return EXIT_SUCCESS;
+}
+
+QString Recognizer::expand (const QString &text) const
+{
+ QString code = text;
+
+ if (_M_grammar->start != _M_grammar->names.end ())
+ {
+ code = code.replace (QLatin1String("$start_id"), QString::number (std::distance (_M_grammar->names.begin (), _M_grammar->start)));
+ code = code.replace (QLatin1String("$start"), *_M_grammar->start);
+ }
+
+ code = code.replace (QLatin1String("$header"), _M_grammar->table_name.toLower () + QLatin1String("_p.h"));
+
+ code = code.replace (QLatin1String("$table"), _M_grammar->table_name);
+ code = code.replace (QLatin1String("$parser"), _M_grammar->table_name);
+
+ if (_M_current_rule != _M_grammar->rules.end ())
+ {
+ code = code.replace (QLatin1String("$rule_number"), QString::number (std::distance (_M_grammar->rules.begin (), _M_current_rule)));
+ code = code.replace (QLatin1String("$rule"), *_M_current_rule->lhs);
+ }
+
+ return code;
+}
diff --git a/src/parsetable.cpp b/src/parsetable.cpp
new file mode 100644
index 0000000..509ddf1
--- /dev/null
+++ b/src/parsetable.cpp
@@ -0,0 +1,127 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the utils of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+
+#include <QtCore/QTextStream>
+#include "lalr.h"
+#include "parsetable.h"
+
+ParseTable::ParseTable (QTextStream &o):
+ out (o)
+{
+}
+
+void ParseTable::operator () (Automaton *aut)
+{
+ Grammar *g = aut->_M_grammar;
+
+ int rindex = 1;
+ for (RulePointer rule = g->rules.begin (); rule != g->rules.end (); ++rule)
+ out << rindex++ << ")\t" << *rule << endl;
+ out << endl << endl;
+
+ int index = 0;
+ for (StatePointer state = aut->states.begin (); state != aut->states.end (); ++state)
+ {
+ out << "state " << index++ << endl << endl;
+
+ for (ItemPointer item = state->kernel.begin (); item != state->kernel.end (); ++item)
+ {
+ out << " * " << *item;
+
+ if (item->dot == item->end_rhs ())
+ out << " " << aut->lookaheads [item];
+
+ out << endl;
+ }
+
+ bool first = true;
+ for (Bundle::iterator arrow = state->bundle.begin (); arrow != state->bundle.end (); ++arrow)
+ {
+ if (! g->isTerminal (arrow.key ()))
+ continue;
+
+ if (first)
+ out << endl;
+
+ first = false;
+
+ out << " " << *arrow.key () << " shift, and go to state " << std::distance (aut->states.begin (), *arrow) << endl;
+ }
+
+ first = true;
+ for (ItemPointer item = state->closure.begin (); item != state->closure.end (); ++item)
+ {
+ if (item->dot != item->end_rhs () || item->rule == state->defaultReduce)
+ continue;
+
+ if (first)
+ out << endl;
+
+ first = false;
+
+ foreach (Name la, aut->lookaheads.value (item))
+ out << " " << *la << " reduce using rule " << aut->id (item->rule) << " (" << *item->rule->lhs << ")" << endl;
+ }
+
+ first = true;
+ for (Bundle::iterator arrow = state->bundle.begin (); arrow != state->bundle.end (); ++arrow)
+ {
+ if (! g->isNonTerminal (arrow.key ()))
+ continue;
+
+ if (first)
+ out << endl;
+
+ first = false;
+
+ out << " " << *arrow.key () << " go to state " << std::distance (aut->states.begin (), *arrow) << endl;
+ }
+
+ if (state->defaultReduce != g->rules.end ())
+ {
+ out << endl
+ << " $default reduce using rule " << aut->id (state->defaultReduce) << " (" << *state->defaultReduce->lhs << ")" << endl;
+ }
+
+ out << endl;
+ }
+}
diff --git a/src/parsetable.h b/src/parsetable.h
new file mode 100644
index 0000000..88ab2e5
--- /dev/null
+++ b/src/parsetable.h
@@ -0,0 +1,59 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the utils of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef PARSETABLE_H
+#define PARSETABLE_H
+
+QT_FORWARD_DECLARE_CLASS(QTextStream);
+class Automaton;
+
+class ParseTable
+{
+public:
+ ParseTable (QTextStream &out);
+
+ void operator () (Automaton *a);
+
+private:
+ QTextStream &out;
+};
+
+#endif // PARSETABLE_H
diff --git a/src/recognizer.cpp b/src/recognizer.cpp
new file mode 100644
index 0000000..48f372e
--- /dev/null
+++ b/src/recognizer.cpp
@@ -0,0 +1,488 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the utils of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "recognizer.h"
+#include <cstdlib>
+#include <cstring>
+#include <cctype>
+
+Recognizer::Recognizer (Grammar *grammar, bool no_lines):
+ tos(0),
+ stack_size(0),
+ state_stack(0),
+ _M_line(1),
+ _M_action_line(0),
+ _M_grammar(grammar),
+ _M_no_lines(no_lines)
+{
+}
+
+Recognizer::~Recognizer()
+{
+ if (stack_size)
+ ::qFree(state_stack);
+}
+
+inline void Recognizer::reallocateStack()
+{
+ if (! stack_size)
+ stack_size = 128;
+ else
+ stack_size <<= 1;
+
+ sym_stack.resize (stack_size);
+
+ if (! state_stack)
+ state_stack = reinterpret_cast<int*> (::qMalloc(stack_size * sizeof(int)));
+ else
+ state_stack = reinterpret_cast<int*> (::qRealloc(state_stack, stack_size * sizeof(int)));
+}
+
+int Recognizer::nextToken()
+{
+ QString text;
+
+ Lagain:
+ while (ch.isSpace ())
+ inp ();
+
+ if (ch.isNull ())
+ return EOF_SYMBOL;
+
+ int token = ch.unicode ();
+
+ if (token == '"')
+ {
+ inp(); // skip "
+ text.clear ();
+ while (! ch.isNull () && ch != QLatin1Char ('"'))
+ {
+ if (ch == QLatin1Char ('\\'))
+ {
+ text += ch;
+ inp();
+ }
+ text += ch;
+ inp ();
+ }
+
+ if (ch == QLatin1Char ('"'))
+ inp ();
+ else
+ qerr << _M_input_file << ":" << _M_line << ": Warning. Expected `\"'" << endl;
+
+ _M_current_value = text;
+ return (token = STRING_LITERAL);
+ }
+
+ else if (ch.isLetterOrNumber () || ch == QLatin1Char ('_'))
+ {
+ text.clear ();
+ do { text += ch; inp (); }
+ while (ch.isLetterOrNumber () || ch == QLatin1Char ('_') || ch == QLatin1Char ('.'));
+ _M_current_value = text;
+ return (token = ID);
+ }
+
+ else if (token == '%')
+ {
+ text.clear ();
+
+ do { inp (); }
+ while (ch.isSpace ());
+
+ do { text += ch; inp (); }
+ while (ch.isLetterOrNumber () || ch == QLatin1Char ('_') || ch == QLatin1Char ('-'));
+
+ if (text == QLatin1String("token_prefix"))
+ return (token = TOKEN_PREFIX);
+ else if (text == QLatin1String("merged_output"))
+ return (token = MERGED_OUTPUT);
+ else if (text == QLatin1String("token"))
+ return (token = TOKEN);
+ else if (text == QLatin1String("start"))
+ return (token = START);
+ else if (text == QLatin1String("parser"))
+ return (token = PARSER);
+ else if (text == QLatin1String("decl"))
+ return (token = DECL_FILE);
+ else if (text == QLatin1String("impl"))
+ return (token = IMPL_FILE);
+ else if (text == QLatin1String("expect"))
+ return (token = EXPECT);
+ else if (text == QLatin1String("expect-rr"))
+ return (token = EXPECT_RR);
+ else if (text == QLatin1String("left"))
+ return (token = LEFT);
+ else if (text == QLatin1String("right"))
+ return (token = RIGHT);
+ else if (text == QLatin1String("nonassoc"))
+ return (token = NONASSOC);
+ else if (text == QLatin1String("prec"))
+ return (token = PREC);
+ else
+ {
+ qerr << _M_input_file << ":" << _M_line << ": Unknown keyword `" << text << "'" << endl;
+ exit (EXIT_FAILURE);
+ return (token = ERROR);
+ }
+ }
+
+ inp ();
+
+ if (token == '-' && ch == QLatin1Char ('-'))
+ {
+ do { inp (); }
+ while (! ch.isNull () && ch != QLatin1Char ('\n'));
+ goto Lagain;
+ }
+
+ else if (token == ':' && ch == QLatin1Char (':'))
+ {
+ inp ();
+ if (ch != QLatin1Char ('='))
+ return (token = ERROR);
+ inp ();
+ return (token = COLON);
+ }
+
+ else if (token == '/' && ch == QLatin1Char (':'))
+ {
+ _M_action_line = _M_line;
+
+ text.clear ();
+ if (! _M_no_lines)
+ text += QLatin1String ("\n#line ") + QString::number (_M_action_line) + " \"" + _M_input_file + "\"\n";
+ inp (); // skip ':'
+
+ forever
+ {
+ while (! ch.isNull ())
+ {
+ token = ch.unicode ();
+ inp ();
+
+ if (token == ':' && ch == QLatin1Char ('/'))
+ break;
+
+ text += QLatin1Char (token);
+ }
+
+ if (ch != QLatin1Char ('/'))
+ return (token = ERROR);
+
+ inp ();
+
+ if (ch.isNull () || ch.isSpace ())
+ {
+ _M_current_value = text;
+ return (token = DECL);
+ }
+ else
+ text += QLatin1String (":/");
+ }
+ }
+
+ else if (token == '/' && ch == QLatin1Char ('.'))
+ {
+ _M_action_line = _M_line;
+
+ text.clear ();
+ if (! _M_no_lines)
+ text += QLatin1String ("\n#line ") + QString::number (_M_action_line) + " \"" + _M_input_file + "\"\n";
+
+ inp (); // skip ':'
+
+ forever
+ {
+ while (! ch.isNull ())
+ {
+ token = ch.unicode ();
+ inp ();
+
+ if (token == '.' && ch == QLatin1Char ('/'))
+ break;
+
+ text += QLatin1Char (token);
+ }
+
+ if (ch != QLatin1Char ('/'))
+ return (token = ERROR);
+
+ inp ();
+
+ if (ch.isNull () || ch.isSpace ())
+ {
+ _M_current_value = text;
+ return (token = IMPL);
+ }
+ else
+ text += QLatin1String ("");
+ }
+ }
+
+ switch (token) {
+ case ':':
+ return (token = COLON);
+
+ case ';':
+ return (token = SEMICOLON);
+
+ case '|':
+ return (token = OR);
+
+ default:
+ break;
+ }
+
+ return token;
+}
+
+bool Recognizer::parse (const QString &input_file)
+{
+ _M_input_file = input_file;
+
+ QFile file(_M_input_file);
+ if (! file.open(QFile::ReadOnly))
+ {
+ qerr << "qlalr: no input file\n";
+ return false;
+ }
+
+ QString _M_contents = QTextStream(&file).readAll();
+ _M_firstChar = _M_contents.constBegin();
+ _M_lastChar = _M_contents.constEnd();
+ _M_currentChar = _M_firstChar;
+ _M_line = 1;
+
+ int yytoken = -1;
+ inp ();
+
+ reallocateStack();
+
+ _M_current_rule = _M_grammar->rules.end ();
+ _M_decls.clear ();
+ _M_impls.clear ();
+
+ tos = 0;
+ state_stack[++tos] = 0;
+
+ while (true)
+ {
+ if (yytoken == -1 && - TERMINAL_COUNT != action_index [state_stack [tos]])
+ yytoken = nextToken();
+
+ int act = t_action (state_stack [tos], yytoken);
+
+ if (act == ACCEPT_STATE)
+ return true;
+
+ else if (act > 0)
+ {
+ if (++tos == stack_size)
+ reallocateStack();
+
+ sym_stack [tos] = _M_current_value;
+ state_stack [tos] = act;
+ yytoken = -1;
+ }
+
+ else if (act < 0)
+ {
+ int r = - act - 1;
+
+ tos -= rhs [r];
+ act = state_stack [tos++];
+
+ switch (r) {
+
+case 3: {
+ Name name = _M_grammar->intern (sym(2));
+ _M_grammar->start = name;
+ _M_grammar->non_terminals.insert (name);
+} break;
+
+case 5: {
+ _M_grammar->table_name = sym(2);
+} break;
+
+case 6: {
+ _M_grammar->merged_output = sym(2);
+} break;
+
+case 7: {
+ _M_grammar->decl_file_name = sym(2);
+} break;
+
+case 8: {
+ _M_grammar->impl_file_name = sym(2);
+} break;
+
+case 9: {
+ _M_grammar->expected_shift_reduce = sym(2).toInt();
+} break;
+
+case 10: {
+ _M_grammar->expected_reduce_reduce = sym(2).toInt();
+} break;
+
+case 11: {
+ _M_grammar->token_prefix = sym(2);
+} break;
+case 17:case 18: {
+ Name name = _M_grammar->intern (sym(1));
+ _M_grammar->terminals.insert (name);
+ _M_grammar->spells.insert (name, sym(2));
+} break;
+
+case 19: {
+ _M_grammar->current_assoc = Grammar::Left;
+ ++_M_grammar->current_prec;
+} break;
+
+case 20: {
+ _M_grammar->current_assoc = Grammar::Right;
+ ++_M_grammar->current_prec;
+} break;
+
+case 21: {
+ _M_grammar->current_assoc = Grammar::NonAssoc;
+ ++_M_grammar->current_prec;
+} break;
+
+case 25: {
+ Name name = _M_grammar->intern (sym(1));
+ _M_grammar->terminals.insert (name);
+
+ Grammar::TokenInfo info;
+ info.prec = _M_grammar->current_prec;
+ info.assoc = _M_grammar->current_assoc;
+ _M_grammar->token_info.insert (name, info);
+} break;
+
+case 26: {
+ _M_decls += expand (sym(1));
+} break;
+
+case 27: {
+ _M_impls += expand (sym(1));
+} break;
+
+case 34: {
+ _M_current_rule = _M_grammar->rules.insert (_M_grammar->rules.end (), Rule ());
+ _M_current_rule->lhs = _M_grammar->intern (sym(1));
+ _M_grammar->declared_lhs.insert (_M_current_rule->lhs);
+
+ if (_M_grammar->terminals.find (_M_current_rule->lhs) != _M_grammar->terminals.end ())
+ {
+ qerr << _M_input_file << ":" << _M_line << ": Invalid non terminal `" << *_M_current_rule->lhs << "'" << endl;
+ return false;
+ }
+
+ _M_grammar->non_terminals.insert (_M_current_rule->lhs);
+} break;
+
+case 38: {
+ Name lhs = _M_current_rule->lhs;
+ _M_current_rule = _M_grammar->rules.insert (_M_grammar->rules.end (), Rule ());
+ _M_current_rule->lhs = lhs;
+ _M_grammar->declared_lhs.insert (_M_current_rule->lhs);
+
+ if (_M_grammar->terminals.find (_M_current_rule->lhs) != _M_grammar->terminals.end ())
+ {
+ qerr << _M_input_file << ":" << _M_line << ": Invalid non terminal `" << *_M_current_rule->lhs << "'" << endl;
+ return false;
+ }
+
+ _M_grammar->non_terminals.insert (_M_current_rule->lhs);
+} break;
+
+case 39: {
+ _M_current_rule->prec = _M_grammar->names.end ();
+
+ for (NameList::iterator it = _M_current_rule->rhs.begin (); it != _M_current_rule->rhs.end (); ++it)
+ {
+ if (! _M_grammar->isTerminal (*it))
+ continue;
+
+ _M_current_rule->prec = *it;
+ }
+} break;
+
+case 40: {
+ Name tok = _M_grammar->intern (sym(2));
+ if (! _M_grammar->isTerminal (tok))
+ {
+ qerr << _M_input_file << ":" << _M_line << ": `" << *tok << " is not a terminal symbol" << endl;
+ _M_current_rule->prec = _M_grammar->names.end ();
+ }
+ else
+ _M_current_rule->prec = tok;
+} break;
+
+case 42: {
+ Name name = _M_grammar->intern (sym(2));
+
+ if (_M_grammar->terminals.find (name) == _M_grammar->terminals.end ())
+ _M_grammar->non_terminals.insert (name);
+
+ _M_current_rule->rhs.push_back (name);
+} break;
+
+case 43: {
+ sym(1) = QString();
+} break;
+
+ } // switch
+
+ state_stack [tos] = nt_action (act, lhs [r] - TERMINAL_COUNT);
+ }
+
+ else
+ {
+ break;
+ }
+ }
+
+ qerr << _M_input_file << ":" << _M_line << ": Syntax error" << endl;
+ return false;
+}
+
diff --git a/src/recognizer.h b/src/recognizer.h
new file mode 100644
index 0000000..384f2e6
--- /dev/null
+++ b/src/recognizer.h
@@ -0,0 +1,111 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the utils of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include <QtCore/QtDebug>
+#include <QtCore/QString>
+#include <QtCore/QFile>
+#include <QtCore/QTextStream>
+
+#include "grammar_p.h"
+#include "lalr.h"
+
+#include <cstdlib>
+
+class Recognizer: protected grammar
+{
+public:
+ Recognizer (Grammar *grammar, bool no_lines);
+ ~Recognizer();
+
+ bool parse (const QString &input_file = QString ());
+
+ inline QString decls () const { return _M_decls; }
+ inline QString impls () const { return _M_impls; }
+
+protected:
+ inline void reallocateStack ();
+
+ inline QString &sym (int index)
+ { return sym_stack [tos + index - 1]; }
+
+protected: // scanner
+ int nextToken();
+
+ inline void inp ()
+ {
+ if (_M_currentChar != _M_lastChar)
+ {
+ ch = *_M_currentChar++;
+
+ if (ch == QLatin1Char('\n'))
+ ++_M_line;
+ }
+ else
+ ch = QChar();
+ }
+
+ QString expand (const QString &text) const;
+
+protected:
+ // recognizer
+ int tos;
+ int stack_size;
+ QVector<QString> sym_stack;
+ int *state_stack;
+
+ QString _M_contents;
+ QString::const_iterator _M_firstChar;
+ QString::const_iterator _M_lastChar;
+ QString::const_iterator _M_currentChar;
+
+ // scanner
+ QChar ch;
+ int _M_line;
+ int _M_action_line;
+ Grammar *_M_grammar;
+ RulePointer _M_current_rule;
+ QString _M_input_file;
+
+ QString _M_decls;
+ QString _M_impls;
+ QString _M_current_value;
+ bool _M_no_lines;
+};
diff --git a/src/src.pro b/src/src.pro
new file mode 100644
index 0000000..1994a73
--- /dev/null
+++ b/src/src.pro
@@ -0,0 +1,22 @@
+
+TEMPLATE = app
+QT = core
+CONFIG += console
+TARGET = qlalr
+mac:CONFIG -= app_bundle
+
+SOURCES += compress.cpp \
+ cppgenerator.cpp \
+ dotgraph.cpp \
+ lalr.cpp \
+ main.cpp \
+ parsetable.cpp \
+ recognizer.cpp \
+ grammar.cpp
+
+HEADERS += compress.h \
+ cppgenerator.h \
+ dotgraph.h \
+ lalr.h \
+ parsetable.h \
+ grammar_p.h
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-06 14:01:19 +0000