summaryrefslogtreecommitdiffstats
path: root/util/qlalr
diff options
context:
space:
mode:
authorLars Knoll <lars.knoll@nokia.com>2009-03-23 09:34:13 (GMT)
committerSimon Hausmann <simon.hausmann@nokia.com>2009-03-23 09:34:13 (GMT)
commit67ad0519fd165acee4a4d2a94fa502e9e4847bd0 (patch)
tree1dbf50b3dff8d5ca7e9344733968c72704eb15ff /util/qlalr
downloadQt-67ad0519fd165acee4a4d2a94fa502e9e4847bd0.zip
Qt-67ad0519fd165acee4a4d2a94fa502e9e4847bd0.tar.gz
Qt-67ad0519fd165acee4a4d2a94fa502e9e4847bd0.tar.bz2
Long live Qt!
Diffstat (limited to 'util/qlalr')
-rw-r--r--util/qlalr/.gitignore1
-rw-r--r--util/qlalr/README1
-rw-r--r--util/qlalr/compress.cpp286
-rw-r--r--util/qlalr/compress.h60
-rw-r--r--util/qlalr/cppgenerator.cpp732
-rw-r--r--util/qlalr/cppgenerator.h99
-rw-r--r--util/qlalr/doc/qlalr.qdocconf65
-rw-r--r--util/qlalr/doc/src/classic.css97
-rw-r--r--util/qlalr/doc/src/images/qt-logo.pngbin0 -> 1422 bytes
-rw-r--r--util/qlalr/doc/src/images/trolltech-logo.pngbin0 -> 1512 bytes
-rw-r--r--util/qlalr/doc/src/qlalr.qdoc79
-rw-r--r--util/qlalr/dotgraph.cpp102
-rw-r--r--util/qlalr/dotgraph.h59
-rw-r--r--util/qlalr/examples/dummy-xml/dummy-xml.pro2
-rw-r--r--util/qlalr/examples/dummy-xml/ll/dummy-xml-ll.cpp83
-rw-r--r--util/qlalr/examples/dummy-xml/xml.g202
-rw-r--r--util/qlalr/examples/glsl/build.sh7
-rwxr-xr-xutil/qlalr/examples/glsl/glsl4
-rw-r--r--util/qlalr/examples/glsl/glsl-lex.l201
-rw-r--r--util/qlalr/examples/glsl/glsl.g621
-rw-r--r--util/qlalr/examples/glsl/glsl.pro4
-rw-r--r--util/qlalr/examples/lambda/COMPILE3
-rw-r--r--util/qlalr/examples/lambda/lambda.g41
-rw-r--r--util/qlalr/examples/lambda/lambda.pro3
-rw-r--r--util/qlalr/examples/lambda/main.cpp160
-rw-r--r--util/qlalr/examples/qparser/COMPILE3
-rw-r--r--util/qlalr/examples/qparser/calc.g93
-rw-r--r--util/qlalr/examples/qparser/calc.l20
-rw-r--r--util/qlalr/examples/qparser/qparser.cpp3
-rw-r--r--util/qlalr/examples/qparser/qparser.h111
-rw-r--r--util/qlalr/examples/qparser/qparser.pro4
-rw-r--r--util/qlalr/grammar.cpp123
-rw-r--r--util/qlalr/grammar_p.h119
-rw-r--r--util/qlalr/lalr.cpp783
-rw-r--r--util/qlalr/lalr.g803
-rw-r--r--util/qlalr/lalr.h502
-rw-r--r--util/qlalr/main.cpp185
-rw-r--r--util/qlalr/parsetable.cpp127
-rw-r--r--util/qlalr/parsetable.h59
-rw-r--r--util/qlalr/qlalr.pro21
-rw-r--r--util/qlalr/recognizer.cpp489
-rw-r--r--util/qlalr/recognizer.h111
42 files changed, 6468 insertions, 0 deletions
diff --git a/util/qlalr/.gitignore b/util/qlalr/.gitignore
new file mode 100644
index 0000000..ce75745
--- /dev/null
+++ b/util/qlalr/.gitignore
@@ -0,0 +1 @@
+qlalr
diff --git a/util/qlalr/README b/util/qlalr/README
new file mode 100644
index 0000000..b186fa1
--- /dev/null
+++ b/util/qlalr/README
@@ -0,0 +1 @@
+qlalr is used to generate parsers for QXmlStream and QtScript.
diff --git a/util/qlalr/compress.cpp b/util/qlalr/compress.cpp
new file mode 100644
index 0000000..f1daac8
--- /dev/null
+++ b/util/qlalr/compress.cpp
@@ -0,0 +1,286 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the QLALR project on Trolltech 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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@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/util/qlalr/compress.h b/util/qlalr/compress.h
new file mode 100644
index 0000000..8b7ac60
--- /dev/null
+++ b/util/qlalr/compress.h
@@ -0,0 +1,60 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the QLALR project on Trolltech 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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@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/util/qlalr/cppgenerator.cpp b/util/qlalr/cppgenerator.cpp
new file mode 100644
index 0000000..e85aa4c
--- /dev/null
+++ b/util/qlalr/cppgenerator.cpp
@@ -0,0 +1,732 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the QLALR project on Trolltech 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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@nokia.com.
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+
+#include <QtCore/QtCore>
+
+#include "cppgenerator.h"
+#include "lalr.h"
+#include "recognizer.h"
+
+QString CppGenerator::trollCopyrightHeader() const
+{
+ return QLatin1String(
+
+"/****************************************************************************\n"
+"**\n"
+"** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).\n"
+"** Contact: Qt Software Information (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 either Technology Preview License Agreement or the\n"
+"** Beta Release License Agreement.\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\n"
+"** additional rights. These rights are described in the Nokia Qt LGPL\n"
+"** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this\n"
+"** package.\n"
+"**\n"
+"** GNU General Public License Usage\n"
+"** Alternatively, this file may be used under the terms of the GNU\n"
+"** General Public License version 3.0 as published by the Free Software\n"
+"** Foundation and appearing in the file LICENSE.GPL included in the\n"
+"** packaging of this file. Please review the following information to\n"
+"** ensure the GNU General Public License version 3.0 requirements will be\n"
+"** met: http://www.gnu.org/copyleft/gpl.html.\n"
+"**\n"
+"** If you are unsure which license is appropriate for your use, please\n"
+"** contact the sales department at qt-sales@nokia.com.\n"
+"** $QT_END_LICENSE$\n"
+"**\n"
+"****************************************************************************/\n"
+ "\n");
+}
+
+QString CppGenerator::trollPrivateCopyrightHeader() 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);
+ out << "// This file was generated by qlalr - DO NOT EDIT!\n";
+
+ if (troll_copyright)
+ {
+ out << trollCopyrightHeader()
+ << trollPrivateCopyrightHeader()
+ << endl;
+ }
+
+ out << startIncludeGuard(grammar.merged_output) << 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);
+ out << "// This file was generated by qlalr - DO NOT EDIT!\n";
+
+ QString prot = declFileName.toUpper ().replace (QLatin1Char ('.'), QLatin1Char ('_'));
+
+ if (troll_copyright)
+ {
+ out << trollCopyrightHeader()
+ << trollPrivateCopyrightHeader()
+ << endl;
+ }
+
+ out << "#ifndef " << prot << endl
+ << "#define " << prot << endl
+ << endl;
+
+ generateDecl (out);
+
+ out << "#endif // " << prot << endl << endl;
+ } // end decls
+
+ { // bits...
+ QFile f (bitsFileName);
+ f.open (QFile::WriteOnly);
+ QTextStream out (&f);
+ out << "// This file was generated by qlalr - DO NOT EDIT!\n";
+
+ if (troll_copyright)
+ out << trollCopyrightHeader();
+
+ out << "#include \"" << declFileName << "\"" << endl << endl;
+ generateImpl(out);
+
+ } // end bits
+
+ if (! grammar.decl_file_name.isEmpty ())
+ {
+ QFile f (grammar.decl_file_name);
+ f.open (QFile::WriteOnly);
+ QTextStream out (&f);
+ out << "// This file was generated by qlalr - DO NOT EDIT!\n";
+ out << p.decls();
+ }
+
+ if (! grammar.impl_file_name.isEmpty ())
+ {
+ QFile f (grammar.impl_file_name);
+ f.open (QFile::WriteOnly);
+ QTextStream out (&f);
+ out << "// This file was generated by qlalr - DO NOT EDIT!\n";
+ 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 {" << 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 int lhs [];" << endl
+ << " static const int 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 int goto_default [];" << endl
+ << " static const int action_default [];" << endl
+ << " static const int action_index [];" << endl
+ << " static const int action_info [];" << endl
+ << " static const int action_check [];" << endl
+ << endl
+ << " static inline int nt_action (int state, int nt)" << endl
+ << " {" << endl
+ << " const int *const goto_index = &action_index [GOTO_INDEX_OFFSET];" << endl
+ << " const int *const goto_check = &action_check [GOTO_CHECK_OFFSET];" << endl
+ << endl
+ << " const int yyn = goto_index [state] + nt;" << endl
+ << endl
+ << " if (yyn < 0 || goto_check [yyn] != nt)" << endl
+ << " return goto_default [nt];" << endl
+ << endl
+ << " const int *const goto_info = &action_info [GOTO_INFO_OFFSET];" << endl
+ << " return goto_info [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 int " << 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 int " << 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 int " << 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 int " << 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 int " << 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 int " << 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 int " << 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/util/qlalr/cppgenerator.h b/util/qlalr/cppgenerator.h
new file mode 100644
index 0000000..dd32413
--- /dev/null
+++ b/util/qlalr/cppgenerator.h
@@ -0,0 +1,99 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the QLALR project on Trolltech 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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@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),
+ troll_copyright (false) {}
+
+ void operator () ();
+
+ bool debugInfo () const { return debug_info; }
+ void setDebugInfo (bool d) { debug_info = d; }
+
+ bool trollCopyright () const { return troll_copyright; }
+ void setTrollCopyright (bool t) { troll_copyright = t; }
+
+private:
+ void generateDecl (QTextStream &out);
+ void generateImpl (QTextStream &out);
+
+ QString debugInfoProt() const;
+ QString trollCopyrightHeader() const;
+ QString trollPrivateCopyrightHeader() 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 troll_copyright;
+ Compress compressed_action;
+ Compress compressed_goto;
+ QVector<int> count;
+ QVector<int> defgoto;
+};
+
+#endif // CPPGENERATOR_H
diff --git a/util/qlalr/doc/qlalr.qdocconf b/util/qlalr/doc/qlalr.qdocconf
new file mode 100644
index 0000000..d97ff7d
--- /dev/null
+++ b/util/qlalr/doc/qlalr.qdocconf
@@ -0,0 +1,65 @@
+# Run qdoc from the directory that contains this file.
+
+project = qlalr
+description = qlalr Reference Documentation
+url = http://doc.trolltech.com/
+
+language = Cpp
+
+# sourcedirs = $PWD/src
+sourcedirs = src
+sources.fileextensions = "*.qdoc"
+
+exampledirs = ../examples
+
+imagedirs = src/images
+outputdir = html
+codeindent = 1
+extraimages.HTML = qt-logo \
+ trolltech-logo
+
+macro.key = "\\bold"
+macro.menu = "\\bold"
+macro.gui = "\\bold"
+macro.reg.HTML = "<sup>&reg;</sup>"
+macro.raisedaster.HTML = "<sup>*</sup>"
+macro.BR.HTML = "<br />"
+macro.br.HTML = "<br />"
+macro.QD = "\\e{Qt Designer}"
+macro.QA = "\\e{Qt Assistant}"
+macro.eacute.HTML = "&eacute;"
+macro.aring.HTML = "&aring;"
+macro.oslash.HTML = "&oslash;"
+macro.ouml.HTML = "&ouml;"
+macro.Auml.HTML = "&Auml;"
+macro.uuml.HTML = "&uuml;"
+
+HTML.stylesheets = src/classic.css
+HTML.postheader = "<table border=\"0\" cellpadding=\"0\" cellspacing=\"0\" width=\"100%\">\n" \
+ "<tr>\n" \
+ "<td align=\"left\" valign=\"top\" width=\"32\">" \
+ "<a href=\"http://qtsoftware.com/products/qt\"><img src=\"images/qt-logo.png\" align=\"left\" width=\"32\" height=\"32\" border=\"0\" /></a>" \
+ "</td>\n" \
+ "<td width=\"1\">&nbsp;&nbsp;</td>" \
+ "<td class=\"postheader\" valign=\"center\">" \
+ "<a href=\"index.html\">" \
+ "<font color=\"#004faf\">Home</font></a>&nbsp;&middot;" \
+ " <a href=\"classes.html\">" \
+ "<font color=\"#004faf\">All&nbsp;Classes</font></a>&nbsp;&middot;" \
+ " <a href=\"mainclasses.html\">" \
+ "<font color=\"#004faf\">Main&nbsp;Classes</font></a>&nbsp;&middot;" \
+ " <a href=\"groups.html\">" \
+ "<font color=\"#004faf\">Grouped&nbsp;Classes</font></a>&nbsp;&middot;" \
+ " <a href=\"modules.html\">" \
+ "<font color=\"#004faf\">Modules</font></a>&nbsp;&middot;" \
+ " <a href=\"functions.html\">" \
+ "<font color=\"#004faf\">Functions</font></a>" \
+ "</td>\n" \
+ "<td align=\"right\" valign=\"top\" width=\"230\"><a href=\"http://qtsoftware.com\"><img src=\"images/trolltech-logo.png\" align=\"right\" width=\"203\" height=\"32\" border=\"0\" /></a></td></tr></table>"
+
+HTML.footer = "<p /><address><hr /><div align=\"center\">\n" \
+ "<table width=\"100%\" cellspacing=\"0\" border=\"0\"><tr class=\"address\">\n" \
+ "<td width=\"30%\">Copyright &copy; \$THISYEAR\$ <a href=\"trolltech.html\">Trolltech</a></td>\n" \
+ "<td width=\"40%\" align=\"center\"><a href=\"trademarks.html\">Trademarks</a></td>\n" \
+ "<td width=\"30%\" align=\"right\"><div align=\"right\">Qt \\version</div></td>\n" \
+ "</tr></table></div></address>"
diff --git a/util/qlalr/doc/src/classic.css b/util/qlalr/doc/src/classic.css
new file mode 100644
index 0000000..afc66d5
--- /dev/null
+++ b/util/qlalr/doc/src/classic.css
@@ -0,0 +1,97 @@
+h3.fn,span.fn
+{
+ margin-left: 1cm;
+ text-indent: -1cm;
+}
+
+a:link
+{
+ color: #004faf;
+ text-decoration: none
+}
+
+a:visited
+{
+ color: #672967;
+ text-decoration: none
+}
+
+td.postheader
+{
+ font-family: sans-serif
+}
+
+tr.address
+{
+ font-family: sans-serif
+}
+
+body
+{
+ background: #ffffff;
+ color: black
+}
+
+table tr.odd {
+ background: #f0f0f0;
+ color: black;
+}
+
+table tr.even {
+ background: #e4e4e4;
+ color: black;
+}
+
+table.annotated {
+ border-spacing: 0px;
+}
+
+table.annotated th {
+ font-weight: bold;
+ padding: 3px;
+ text-align: left
+}
+
+table.annotated td {
+ padding: 3px;
+}
+
+table tr pre
+{
+ padding-top: none;
+ padding-bottom: none;
+ padding-left: none;
+ padding-right: none;
+ border: none;
+ background: none
+}
+
+tr.qt-style
+{
+ background: #a2c511;
+ color: black
+}
+
+body pre
+{
+ padding: 0.2em;
+ border: #e7e7e7 1px solid;
+ background: #f1f1f1;
+ color: black
+}
+
+span.preprocessor, span.preprocessor a
+{
+ color: darkblue;
+}
+
+span.comment
+{
+ color: darkred;
+ font-style: italic
+}
+
+span.string,span.char
+{
+ color: darkgreen;
+}
diff --git a/util/qlalr/doc/src/images/qt-logo.png b/util/qlalr/doc/src/images/qt-logo.png
new file mode 100644
index 0000000..2dc6716
--- /dev/null
+++ b/util/qlalr/doc/src/images/qt-logo.png
Binary files differ
diff --git a/util/qlalr/doc/src/images/trolltech-logo.png b/util/qlalr/doc/src/images/trolltech-logo.png
new file mode 100644
index 0000000..19e3789
--- /dev/null
+++ b/util/qlalr/doc/src/images/trolltech-logo.png
Binary files differ
diff --git a/util/qlalr/doc/src/qlalr.qdoc b/util/qlalr/doc/src/qlalr.qdoc
new file mode 100644
index 0000000..313c7a4
--- /dev/null
+++ b/util/qlalr/doc/src/qlalr.qdoc
@@ -0,0 +1,79 @@
+/*!
+ \page qlalr.html
+ \title qlalr
+ \nextpage qlalr - Writing Grammars
+
+ \section1 Table of Contents
+
+ \list
+ \o \l{qlalr - Writing Grammars}
+ \tableofcontents{1 qlalr - Writing Grammars}
+ \o \l{qlalr - Generating Code from Grammar Specifications}
+ \tableofcontents{1 qlalr - Generating Code from Grammar Specifications}
+ \o \l{qlalr - qlalr Grammar Specification}
+ \tableofcontents{1 qlalr - qlalr Grammar Specification}
+ \o \l{qlalr - Handling Conflicts}
+ \tableofcontents{1 qlalr - Handling Conflicts}
+ \o \l{qlalr - Error Handling and Recovery}
+ \tableofcontents{1 qlalr - Error Handling and Recovery}
+ \o \l{qlalr - References to External Information}
+ \tableofcontents{1 qlalr - References to External Information}
+ \endlist
+
+*/
+
+/*!
+ \page qlalr-files.html
+ \title qlalr - Writing Grammars
+
+ \contentspage qlalr
+ \previouspage qlalr
+ \nextpage qlalr - Generating Code from Grammar Specifications
+
+*/
+
+/*!
+ \page qlalr-generating.html
+ \title qlalr - Generating Code from Grammar Specifications
+
+ \contentspage qlalr
+ \previouspage qlalr - Writing Grammars
+ \nextpage qlalr - qlalr Grammar Specification
+*/
+
+/*!
+ \page qlalr-grammar-specification.html
+ \title qlalr - qlalr Grammar Specification
+
+ \contentspage qlalr
+ \previouspage qlalr - Generating Code from Grammar Specifications
+ \nextpage qlalr - Handling Conflicts
+
+*/
+
+/*!
+ \page qlalr-handling-conflicts.html
+ \title qlalr - Handling Conflicts
+
+ \contentspage qlalr
+ \previouspage qlalr - qlalr Grammar Specification
+ \nextpage qlalr - Error Handling and Recovery
+*/
+
+/*!
+ \page qlalr-handling-errors.html
+ \title qlalr - Error Handling and Recovery
+
+ \contentspage qlalr
+ \previouspage qlalr - Handling Conflicts
+ \nextpage qlalr - References to External Information
+*/
+
+/*!
+ \page qlalr-external-references.html
+ \title qlalr - References to External Information
+
+ \contentspage qlalr
+ \previouspage qlalr - Error Handling and Recovery
+*/
+
diff --git a/util/qlalr/dotgraph.cpp b/util/qlalr/dotgraph.cpp
new file mode 100644
index 0000000..641ed01
--- /dev/null
+++ b/util/qlalr/dotgraph.cpp
@@ -0,0 +1,102 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the QLALR project on Trolltech 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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@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/util/qlalr/dotgraph.h b/util/qlalr/dotgraph.h
new file mode 100644
index 0000000..e308b74
--- /dev/null
+++ b/util/qlalr/dotgraph.h
@@ -0,0 +1,59 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the QLALR project on Trolltech 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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@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/util/qlalr/examples/dummy-xml/dummy-xml.pro b/util/qlalr/examples/dummy-xml/dummy-xml.pro
new file mode 100644
index 0000000..e54512d
--- /dev/null
+++ b/util/qlalr/examples/dummy-xml/dummy-xml.pro
@@ -0,0 +1,2 @@
+HEADERS += xmltable_p.h
+SOURCES += xmlreader.cpp xmltable.cpp
diff --git a/util/qlalr/examples/dummy-xml/ll/dummy-xml-ll.cpp b/util/qlalr/examples/dummy-xml/ll/dummy-xml-ll.cpp
new file mode 100644
index 0000000..54f5e0e
--- /dev/null
+++ b/util/qlalr/examples/dummy-xml/ll/dummy-xml-ll.cpp
@@ -0,0 +1,83 @@
+
+#include <cstdlib>
+#include <cstdio>
+
+enum Token {
+ EOF_SYMBOL,
+ LEFT_ANGLE,
+ RIGHT_ANGLE,
+ ANY,
+};
+
+static int current_char;
+static int yytoken;
+static bool in_tag = false;
+
+bool parseXmlStream();
+bool parseTagOrWord();
+bool parseTagName();
+
+inline int nextToken()
+{
+ current_char = fgetc(stdin);
+ if (current_char == EOF) {
+ return (yytoken = EOF_SYMBOL);
+ } else if (current_char == '<') {
+ in_tag = true;
+ return (yytoken = LEFT_ANGLE);
+ } else if (in_tag && current_char == '>') {
+ in_tag = false;
+ return (yytoken = RIGHT_ANGLE);
+ }
+ return (yytoken = ANY);
+}
+
+bool parse()
+{
+ nextToken();
+ return parseXmlStream();
+}
+
+bool parseXmlStream()
+{
+ while (parseTagOrWord())
+ ;
+
+ return true;
+}
+
+bool parseTagOrWord()
+{
+ if (yytoken == LEFT_ANGLE) {
+ nextToken();
+ if (! parseTagName())
+ return false;
+ if (yytoken != RIGHT_ANGLE)
+ return false;
+ nextToken();
+
+ fprintf (stderr, "*** found a tag\n");
+
+ } else if (yytoken == ANY) {
+ nextToken();
+ } else {
+ return false;
+ }
+ return true;
+}
+
+bool parseTagName()
+{
+ while (yytoken == ANY)
+ nextToken();
+
+ return true;
+}
+
+int main()
+{
+ if (parse())
+ printf("OK\n");
+ else
+ printf("KO\n");
+}
diff --git a/util/qlalr/examples/dummy-xml/xml.g b/util/qlalr/examples/dummy-xml/xml.g
new file mode 100644
index 0000000..212c829
--- /dev/null
+++ b/util/qlalr/examples/dummy-xml/xml.g
@@ -0,0 +1,202 @@
+
+%parser XMLTable
+
+%impl xmlreader.cpp
+
+%token LEFT_ANGLE
+%token RIGHT_ANGLE
+%token ANY
+
+%start XmlStream
+
+/.
+#ifndef XMLREADER_H
+#define XMLREADER_H
+
+#include <QtCore>
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+#include "$header"
+
+class XMLReader: protected $table
+{
+public:
+ XMLReader(const QByteArray &bytes);
+ ~XMLReader();
+
+ bool parse();
+
+ inline int nextToken()
+ {
+ switch (*bufptr++) {
+ case '\0':
+ return EOF_SYMBOL;
+
+ case '<':
+ in_tag = true;
+ return LEFT_ANGLE;
+
+ case '>':
+ if (! in_tag)
+ break;
+ in_tag = false;
+ return RIGHT_ANGLE;
+ break;
+
+ } // switch
+
+ return ANY;
+ }
+
+protected:
+ inline void reallocateStack();
+
+ inline int &sym(int index)
+ { return stack [tos + index - 1].ival; }
+
+protected:
+ int tos;
+ int stack_size;
+
+ struct StackItem {
+ int state;
+ int ival;
+ };
+
+ QVarLengthArray<StackItem> stack;
+ unsigned in_tag: 1;
+ QByteArray bytes;
+ const char *bufptr;
+};
+
+inline void XMLReader::reallocateStack()
+{
+ if (! stack_size)
+ stack_size = 128;
+ else
+ stack_size <<= 1;
+
+ stack.resize (stack_size);
+}
+
+#endif // XMLREADER_H
+
+XMLReader::XMLReader(const QByteArray &bytes):
+ tos(0),
+ stack_size(0),
+ bytes(bytes)
+{
+ bufptr = bytes.constData();
+}
+
+XMLReader::~XMLReader()
+{
+}
+
+bool XMLReader::parse()
+{
+ const int INITIAL_STATE = 0;
+
+ in_tag = 0;
+ bufptr = bytes.constData();
+
+ int yytoken = -1;
+ reallocateStack();
+
+ tos = 0;
+ stack [++tos].state = INITIAL_STATE;
+
+ while (true)
+ {
+ const int state = stack [tos].state;
+
+ if (yytoken == -1 && - TERMINAL_COUNT != action_index [state])
+ yytoken = nextToken();
+
+ int act = t_action (state, yytoken);
+
+ if (act == ACCEPT_STATE)
+ return true;
+
+ else if (act > 0)
+ {
+ if (++tos == stack_size)
+ reallocateStack();
+
+ stack [tos].ival = *bufptr; // ### save the token value here
+ stack [tos].state = act;
+ yytoken = -1;
+ }
+
+ else if (act < 0)
+ {
+ int r = - act - 1;
+
+ tos -= rhs [r];
+ act = stack [tos++].state;
+
+ switch (r) {
+./
+
+
+
+
+XmlStream: TagOrWord ;
+XmlStream: XmlStream TagOrWord ;
+
+TagOrWord: Tag ;
+TagOrWord: ANY ;
+
+Tag: LEFT_ANGLE TagName RIGHT_ANGLE ;
+/.
+ case $rule_number: {
+ fprintf (stderr, "*** found a tag\n");
+ } break;
+./
+
+TagName: ANY ;
+TagName: TagName ANY ;
+
+
+/.
+ } // switch
+
+ stack [tos].state = nt_action (act, lhs [r] - TERMINAL_COUNT);
+ }
+
+ else
+ {
+ // ### ERROR RECOVERY HERE
+ break;
+ }
+ }
+
+ return false;
+}
+
+
+
+/////////////////////////////
+// entry point
+/////////////////////////////
+int main(int, char *argv[])
+{
+ QFile f (argv[1]);
+
+ if (f.open(QFile::ReadOnly)) {
+ QByteArray contents = f.readAll();
+ XMLReader parser (contents);
+
+ if (parser.parse())
+ printf ("OK\n");
+ else
+ printf ("KO\n");
+ }
+}
+
+
+
+
+./
+
diff --git a/util/qlalr/examples/glsl/build.sh b/util/qlalr/examples/glsl/build.sh
new file mode 100644
index 0000000..0316911
--- /dev/null
+++ b/util/qlalr/examples/glsl/build.sh
@@ -0,0 +1,7 @@
+#!/bin/sh
+
+${FLEX-flex} -oglsl-lex.incl glsl-lex.l
+${QLALR-qlalr} glsl.g
+
+qmake
+make
diff --git a/util/qlalr/examples/glsl/glsl b/util/qlalr/examples/glsl/glsl
new file mode 100755
index 0000000..c19018f
--- /dev/null
+++ b/util/qlalr/examples/glsl/glsl
@@ -0,0 +1,4 @@
+#!/bin/sh
+
+me=$(dirname $0)
+${CPP-cpp} -nostdinc $* | $me/glsl.bin
diff --git a/util/qlalr/examples/glsl/glsl-lex.l b/util/qlalr/examples/glsl/glsl-lex.l
new file mode 100644
index 0000000..1e07c3b
--- /dev/null
+++ b/util/qlalr/examples/glsl/glsl-lex.l
@@ -0,0 +1,201 @@
+
+%{
+#include <cassert>
+#define YY_DECL int GLSLParser::nextToken()
+%}
+
+%option noyywrap
+
+hex [0-9a-fA-F]
+dec [1-9][0-9]*
+oct [0-7]
+digit [0-9]
+
+fract {digit}*\.{digit}+|{digit}+\.
+exp [eE][+-]?{digit}+
+
+hexfract {hex}*\.{hex}+|{hex}+\.
+binexp [pP][+-]?{digit}+
+
+icst ({dec}|0{oct}*|0[xX]{hex}+)
+
+%%
+
+[\n] { ++context.line; }
+[ \t\r]+ { /* skip */ }
+
+"+=" { return ADD_ASSIGN; }
+"&" { return AMPERSAND; }
+"&=" { return AND_ASSIGN; }
+"&&" { return AND_OP; }
+"attribute" { return ATTRIBUTE; }
+"!" { return BANG; }
+"bool" { return BOOL; }
+"true" { return BOOLCONSTANT; }
+"false" { return BOOLCONSTANT; }
+"break" { return BREAK; }
+"bvec2" { return BVEC2; }
+"bvec3" { return BVEC3; }
+"bvec4" { return BVEC4; }
+":" { return COLON; }
+"," { return COMMA; }
+"const" { return CONST; }
+"continue" { return CONTINUE; }
+"-" { return DASH; }
+"--" { return DEC_OP; }
+"discard" { return DISCARD; }
+"/=" { return DIV_ASSIGN; }
+"do" { return DO; }
+"." { return DOT; }
+"else" { return ELSE; }
+"=" { return EQUAL; }
+"==" { return EQ_OP; }
+"float" { return FLOAT; }
+"for" { return FOR; }
+">=" { return GE_OP; }
+"if" { return IF; }
+"in" { return IN; }
+"++" { return INC_OP; }
+"inout" { return INOUT; }
+"int" { return INT; }
+"ivec2" { return IVEC2; }
+"ivec3" { return IVEC3; }
+"ivec4" { return IVEC4; }
+"<" { return LEFT_ANGLE; }
+"<<=" { return LEFT_ASSIGN; }
+"{" { return LEFT_BRACE; }
+"[" { return LEFT_BRACKET; }
+"<<" { return LEFT_OP; }
+"(" { return LEFT_PAREN; }
+"<=" { return LE_OP; }
+"mat2" { return MAT2; }
+"mat3" { return MAT3; }
+"mat4" { return MAT4; }
+"%=" { return MOD_ASSIGN; }
+"*=" { return MUL_ASSIGN; }
+"!=" { return NE_OP; }
+"|=" { return OR_ASSIGN; }
+"||" { return OR_OP; }
+"out" { return OUT; }
+"%" { return PERCENT; }
+"+" { return PLUS; }
+"?" { return QUESTION; }
+"return" { return RETURN; }
+">" { return RIGHT_ANGLE; }
+">>=" { return RIGHT_ASSIGN; }
+"}" { return RIGHT_BRACE; }
+"]" { return RIGHT_BRACKET; }
+">>" { return RIGHT_OP; }
+")" { return RIGHT_PAREN; }
+"sampler1D" { return SAMPLER1D; }
+"sampler1DShadow" { return SAMPLER1DSHADOW; }
+"sampler2D" { return SAMPLER2D; }
+"sampler2DShadow" { return SAMPLER2DSHADOW; }
+"sampler3D" { return SAMPLER3D; }
+"samplerCube" { return SAMPLERCUBE; }
+";" { return SEMICOLON; }
+"/" { return SLASH; }
+"*" { return STAR; }
+"struct" { return STRUCT; }
+"-=" { return SUB_ASSIGN; }
+"~" { return TILDE; }
+"uniform" { return UNIFORM; }
+"varying" { return VARYING; }
+"vec2" { return VEC2; }
+"vec3" { return VEC3; }
+"vec4" { return VEC4; }
+"|" { return VERTICAL_BAR; }
+"void" { return VOID; }
+"while" { return WHILE; }
+"^=" { return XOR_ASSIGN; }
+"^" { return XOR_OP; }
+
+#[ \t]+[0-9]+.* {
+ char *eptr = 0;
+ context.line = (int) strtod(&yytext[1], &eptr);
+ QString fn = QString::fromUtf8(eptr).trimmed();
+ if (fn.length() > 2)
+ context.fileName = fn.mid(1, fn.length()-2);
+}
+
+#.* {
+ /* skip */
+}
+
+[_a-zA-Z][_a-zA-Z0-9]* {
+ yylval.s = intern (yytext);
+
+ if (isTypename (yylval.s))
+ return TYPE_NAME;
+
+ return IDENTIFIER;
+}
+
+{icst} {
+ yylval.i = (int) strtol (yytext, 0, 0);
+ return INTCONSTANT;
+}
+
+{icst}[uU] {
+ yylval.u = (unsigned) strtoul (yytext, 0, 0);
+ return INTCONSTANT;
+}
+
+{icst}[uU][lL] {
+ yylval.ul = strtoul (yytext, 0, 0);
+ return INTCONSTANT;
+}
+
+{icst}[lL][uU] {
+ yylval.ul = strtoul (yytext, 0, 0);
+ return INTCONSTANT;
+}
+
+{icst}[lL] {
+ yylval.l = strtol (yytext, 0, 0);
+ return INTCONSTANT;
+}
+
+{icst}[uU](ll|LL) {
+ yylval.l = strtoull (yytext, 0, 0);
+ return INTCONSTANT;
+}
+
+{icst}(ll|LL) {
+ yylval.l = strtoll (yytext, 0, 0);
+ return INTCONSTANT;
+}
+
+{icst}(ll|LL)[uU] {
+ yylval.l = strtoull (yytext, 0, 0);
+ return INTCONSTANT;
+}
+
+{fract}{exp}?[flFL]? {
+ yylval.f = strtof (yytext, 0);
+ return FLOATCONSTANT;
+}
+
+{digit}+{exp}[flFL]? {
+ yylval.f = strtof (yytext, 0);
+ return FLOATCONSTANT;
+}
+
+0[xX]{hexfract}{binexp}[flFL]? {
+ yylval.f = strtof (yytext, 0);
+ return FLOATCONSTANT;
+}
+
+0[xX]{hex}+{binexp}[flFL]? {
+ yylval.f = strtof (yytext, 0);
+ return FLOATCONSTANT;
+}
+
+. {
+ fprintf (stderr, "invalid char: %d\n", yytext [0]);
+ return ERROR;
+}
+
+
+%%
+
diff --git a/util/qlalr/examples/glsl/glsl.g b/util/qlalr/examples/glsl/glsl.g
new file mode 100644
index 0000000..3f3a3ad
--- /dev/null
+++ b/util/qlalr/examples/glsl/glsl.g
@@ -0,0 +1,621 @@
+
+%parser GLSLParserTable
+%merged_output glsl.cpp
+
+%token ADD_ASSIGN
+%token AMPERSAND
+%token AND_ASSIGN
+%token AND_OP
+%token ATTRIBUTE
+%token BANG
+%token BOOL
+%token BOOLCONSTANT
+%token BREAK
+%token BVEC2
+%token BVEC3
+%token BVEC4
+%token CARET
+%token COLON
+%token COMMA
+%token CONST
+%token CONTINUE
+%token DASH
+%token DEC_OP
+%token DISCARD
+%token DIV_ASSIGN
+%token DO
+%token DOT
+%token ELSE
+%token EQUAL
+%token EQ_OP
+%token FLOAT
+%token FLOATCONSTANT
+%token FOR
+%token GE_OP
+%token IDENTIFIER
+%token IF
+%token IN
+%token INC_OP
+%token INOUT
+%token INT
+%token INTCONSTANT
+%token IVEC2
+%token IVEC3
+%token IVEC4
+%token LEFT_ANGLE
+%token LEFT_ASSIGN
+%token LEFT_BRACE
+%token LEFT_BRACKET
+%token LEFT_OP
+%token LEFT_PAREN
+%token LE_OP
+%token MAT2
+%token MAT3
+%token MAT4
+%token MOD_ASSIGN
+%token MUL_ASSIGN
+%token NE_OP
+%token OR_ASSIGN
+%token OR_OP
+%token OUT
+%token PERCENT
+%token PLUS
+%token QUESTION
+%token RETURN
+%token RIGHT_ANGLE
+%token RIGHT_ASSIGN
+%token RIGHT_BRACE
+%token RIGHT_BRACKET
+%token RIGHT_OP
+%token RIGHT_PAREN
+%token SAMPLER1D
+%token SAMPLER1DSHADOW
+%token SAMPLER2D
+%token SAMPLER2DSHADOW
+%token SAMPLER3D
+%token SAMPLERCUBE
+%token SEMICOLON
+%token SLASH
+%token STAR
+%token STRUCT
+%token SUB_ASSIGN
+%token TILDE
+%token TYPE_NAME
+%token UNIFORM
+%token VARYING
+%token VEC2
+%token VEC3
+%token VEC4
+%token VERTICAL_BAR
+%token VOID
+%token WHILE
+%token XOR_ASSIGN
+%token XOR_OP
+%token ERROR
+%start translation_unit
+
+
+/:
+
+#include <QtCore>
+
+class GLSLParser: protected $table
+{
+public:
+ union Value {
+ int i;
+ unsigned u;
+ unsigned long ul;
+ unsigned long long ull;
+ long l;
+ double d;
+ float f;
+ const QString *s;
+ // ### more...
+ };
+
+public:
+ GLSLParser();
+ ~GLSLParser();
+
+ bool parse();
+
+protected:
+ inline void reallocateStack();
+
+ inline Value &sym(int index)
+ { return sym_stack [tos + index - 1]; }
+
+ int nextToken();
+
+ bool isTypename(const QString *s) const
+ {
+ return types.contains(s);
+ }
+
+ inline const QString *intern(const QString &s)
+ { return &*string_repository.insert(s); }
+
+protected:
+ int tos;
+ int stack_size;
+ Value *sym_stack;
+ int *state_stack;
+ Value yylval;
+ QSet<QString> string_repository;
+ QSet<const QString*> types;
+
+ struct /*Context*/ {
+ int line;
+ const QString *function_name;
+ QString fileName;
+
+ void init()
+ {
+ line = 1;
+ function_name = 0;
+ fileName.clear();
+ }
+ } context;
+};
+
+inline void GLSLParser::reallocateStack()
+{
+ if (! stack_size)
+ stack_size = 128;
+ else
+ stack_size <<= 1;
+
+ sym_stack = reinterpret_cast<Value*> (qRealloc(sym_stack, stack_size * sizeof(Value)));
+ state_stack = reinterpret_cast<int*> (qRealloc(state_stack, stack_size * sizeof(int)));
+}
+
+:/
+
+
+/.
+
+GLSLParser::GLSLParser():
+ tos(0),
+ stack_size(0),
+ sym_stack(0),
+ state_stack(0)
+{
+}
+
+GLSLParser::~GLSLParser()
+{
+ if (stack_size) {
+ qFree(sym_stack);
+ qFree(state_stack);
+ }
+}
+
+bool GLSLParser::parse()
+{
+ const int INITIAL_STATE = 0;
+
+ int yytoken = -1;
+
+ reallocateStack();
+
+ context.init();
+ tos = 0;
+ state_stack[++tos] = INITIAL_STATE;
+
+ 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] = yylval;
+ state_stack [tos] = act;
+ yytoken = -1;
+ }
+
+ else if (act < 0)
+ {
+ int r = - act - 1;
+
+ int ridx = rule_index [r];
+ printf ("*** reduce using rule %d %s ::=", r + 1, spell[rule_info [ridx]]);
+ ++ridx;
+ for (int i = ridx; i < ridx + rhs [r]; ++i)
+ {
+ int symbol = rule_info [i];
+ if (const char *name = spell [symbol])
+ printf (" %s", name);
+ else
+ printf (" #%d", symbol);
+ }
+ printf ("\n");
+
+ tos -= rhs [r];
+ act = state_stack [tos++];
+
+ switch (r) {
+./
+
+
+translation_unit ::= external_declaration ;
+translation_unit ::= translation_unit external_declaration ;
+
+variable_identifier ::= IDENTIFIER ;
+
+primary_expression ::= variable_identifier ;
+primary_expression ::= INTCONSTANT ;
+primary_expression ::= FLOATCONSTANT ;
+primary_expression ::= BOOLCONSTANT ;
+primary_expression ::= LEFT_PAREN expression RIGHT_PAREN ;
+
+
+postfix_expression ::= primary_expression ;
+postfix_expression ::= postfix_expression LEFT_BRACKET integer_expression RIGHT_BRACKET ;
+postfix_expression ::= function_call ;
+postfix_expression ::= postfix_expression DOT IDENTIFIER ;
+postfix_expression ::= postfix_expression DOT TYPE_NAME ;
+postfix_expression ::= postfix_expression INC_OP ;
+postfix_expression ::= postfix_expression DEC_OP ;
+
+
+integer_expression ::= expression ;
+
+function_call ::= function_call_generic ;
+
+function_call_generic ::= function_call_header_with_parameters RIGHT_PAREN ;
+function_call_generic ::= function_call_header_no_parameters RIGHT_PAREN ;
+
+function_call_header_no_parameters ::= function_call_header VOID ;
+function_call_header_no_parameters ::= function_call_header ;
+
+
+function_call_header_with_parameters ::= function_call_header assignment_expression ;
+function_call_header_with_parameters ::= function_call_header_with_parameters COMMA assignment_expression ;
+
+function_call_header ::= function_identifier LEFT_PAREN ;
+
+function_identifier ::= constructor_identifier ;
+function_identifier ::= IDENTIFIER ;
+
+
+constructor_identifier ::= FLOAT ;
+constructor_identifier ::= INT ;
+constructor_identifier ::= BOOL ;
+constructor_identifier ::= VEC2 ;
+constructor_identifier ::= VEC3 ;
+constructor_identifier ::= VEC4 ;
+constructor_identifier ::= BVEC2 ;
+constructor_identifier ::= BVEC3 ;
+constructor_identifier ::= BVEC4 ;
+constructor_identifier ::= IVEC2 ;
+constructor_identifier ::= IVEC3 ;
+constructor_identifier ::= IVEC4 ;
+constructor_identifier ::= MAT2 ;
+constructor_identifier ::= MAT3 ;
+constructor_identifier ::= MAT4 ;
+constructor_identifier ::= TYPE_NAME ;
+
+unary_expression ::= postfix_expression ;
+unary_expression ::= INC_OP unary_expression ;
+unary_expression ::= DEC_OP unary_expression ;
+unary_expression ::= unary_operator unary_expression ;
+
+-- Grammar Note: No traditional style type casts.
+
+unary_operator ::= PLUS ;
+unary_operator ::= DASH ;
+unary_operator ::= BANG ;
+unary_operator ::= TILDE ; -- reserved
+
+-- Grammar Note: No '*' or '&' unary ops. Pointers are not supported.
+
+multiplicative_expression ::= unary_expression ;
+multiplicative_expression ::= multiplicative_expression STAR unary_expression ;
+multiplicative_expression ::= multiplicative_expression SLASH unary_expression ;
+multiplicative_expression ::= multiplicative_expression PERCENT unary_expression ; -- reserved
+
+
+additive_expression ::= multiplicative_expression ;
+additive_expression ::= additive_expression PLUS multiplicative_expression ;
+additive_expression ::= additive_expression DASH multiplicative_expression ;
+
+shift_expression ::= additive_expression ;
+shift_expression ::= shift_expression LEFT_OP additive_expression ; -- reserved
+shift_expression ::= shift_expression RIGHT_OP additive_expression ; -- reserved
+
+relational_expression ::= shift_expression ;
+relational_expression ::= relational_expression LEFT_ANGLE shift_expression ;
+relational_expression ::= relational_expression RIGHT_ANGLE shift_expression ;
+relational_expression ::= relational_expression LE_OP shift_expression ;
+relational_expression ::= relational_expression GE_OP shift_expression ;
+
+equality_expression ::= relational_expression ;
+equality_expression ::= equality_expression EQ_OP relational_expression ;
+equality_expression ::= equality_expression NE_OP relational_expression ;
+
+and_expression ::= equality_expression ;
+and_expression ::= and_expression AMPERSAND equality_expression ; -- reserved
+
+exclusive_or_expression ::= and_expression ;
+exclusive_or_expression ::= exclusive_or_expression CARET and_expression ; -- reserved
+
+inclusive_or_expression ::= exclusive_or_expression ;
+inclusive_or_expression ::= inclusive_or_expression VERTICAL_BAR exclusive_or_expression ; -- reserved
+
+logical_and_expression ::= inclusive_or_expression ;
+logical_and_expression ::= logical_and_expression AND_OP inclusive_or_expression ;
+
+logical_xor_expression ::= logical_and_expression ;
+logical_xor_expression ::= logical_xor_expression XOR_OP logical_and_expression ;
+
+logical_or_expression ::= logical_xor_expression ;
+logical_or_expression ::= logical_or_expression OR_OP logical_xor_expression ;
+
+conditional_expression ::= logical_or_expression ;
+conditional_expression ::= logical_or_expression QUESTION expression COLON conditional_expression ;
+
+assignment_expression ::= conditional_expression ;
+assignment_expression ::= unary_expression assignment_operator assignment_expression ;
+
+assignment_operator ::= EQUAL ;
+assignment_operator ::= MUL_ASSIGN ;
+assignment_operator ::= DIV_ASSIGN ;
+assignment_operator ::= MOD_ASSIGN ; -- reserved
+assignment_operator ::= ADD_ASSIGN ;
+assignment_operator ::= SUB_ASSIGN ;
+assignment_operator ::= LEFT_ASSIGN ; -- reserved
+assignment_operator ::= RIGHT_ASSIGN ; -- reserved
+assignment_operator ::= AND_ASSIGN ; -- reserved
+assignment_operator ::= XOR_ASSIGN ; -- reserved
+assignment_operator ::= OR_ASSIGN ; -- reserved
+
+expression ::= assignment_expression ;
+expression ::= expression COMMA assignment_expression ;
+
+constant_expression ::= conditional_expression ;
+
+declaration ::= function_prototype SEMICOLON ;
+declaration ::= init_declarator_list SEMICOLON ;
+
+function_prototype ::= function_declarator RIGHT_PAREN ;
+
+function_declarator ::= function_header ;
+function_declarator ::= function_header_with_parameters ;
+
+function_header_with_parameters ::= function_header parameter_declaration ;
+function_header_with_parameters ::= function_header_with_parameters COMMA parameter_declaration ;
+
+function_header ::= fully_specified_type IDENTIFIER LEFT_PAREN ;
+/.
+case $rule_number: {
+ context.function_name = sym(2).s;
+} break;
+./
+
+parameter_declarator ::= type_specifier IDENTIFIER ;
+parameter_declarator ::= type_specifier IDENTIFIER LEFT_BRACKET constant_expression RIGHT_BRACKET ;
+
+parameter_declaration ::= type_qualifier parameter_qualifier parameter_declarator ;
+parameter_declaration ::= parameter_qualifier parameter_declarator ;
+parameter_declaration ::= type_qualifier parameter_qualifier parameter_type_specifier ;
+parameter_declaration ::= parameter_qualifier parameter_type_specifier ;
+
+parameter_qualifier ::= ;
+parameter_qualifier ::= IN ;
+parameter_qualifier ::= OUT ;
+parameter_qualifier ::= INOUT ;
+
+parameter_type_specifier ::= type_specifier ;
+parameter_type_specifier ::= type_specifier LEFT_BRACKET constant_expression RIGHT_BRACKET ;
+
+init_declarator_list ::= single_declaration ;
+init_declarator_list ::= init_declarator_list COMMA IDENTIFIER ;
+init_declarator_list ::= init_declarator_list COMMA IDENTIFIER LEFT_BRACKET RIGHT_BRACKET ;
+init_declarator_list ::= init_declarator_list COMMA IDENTIFIER LEFT_BRACKET constant_expression ;
+init_declarator_list ::= RIGHT_BRACKET ;
+init_declarator_list ::= init_declarator_list COMMA IDENTIFIER EQUAL initializer ;
+
+single_declaration ::= fully_specified_type ;
+single_declaration ::= fully_specified_type IDENTIFIER ;
+single_declaration ::= fully_specified_type IDENTIFIER LEFT_BRACKET RIGHT_BRACKET ;
+single_declaration ::= fully_specified_type IDENTIFIER LEFT_BRACKET constant_expression RIGHT_BRACKET ;
+single_declaration ::= fully_specified_type IDENTIFIER EQUAL initializer ;
+
+-- Grammar Note: No 'enum', or 'typedef'.
+
+--fully_specified_type ::= type_specifier ;
+--fully_specified_type ::= type_qualifier type_specifier ;
+
+fully_specified_type ::= type_specifier ;
+fully_specified_type ::= type_qualifier ;
+fully_specified_type ::= fully_specified_type type_specifier ;
+fully_specified_type ::= fully_specified_type type_qualifier ;
+
+type_qualifier ::= CONST ;
+type_qualifier ::= ATTRIBUTE ; -- Vertex only.
+type_qualifier ::= VARYING ;
+type_qualifier ::= UNIFORM ;
+
+type_specifier ::= VOID ;
+type_specifier ::= FLOAT ;
+type_specifier ::= INT ;
+type_specifier ::= BOOL ;
+type_specifier ::= VEC2 ;
+type_specifier ::= VEC3 ;
+type_specifier ::= VEC4 ;
+type_specifier ::= BVEC2 ;
+type_specifier ::= BVEC3 ;
+type_specifier ::= BVEC4 ;
+type_specifier ::= IVEC2 ;
+type_specifier ::= IVEC3 ;
+type_specifier ::= IVEC4 ;
+type_specifier ::= MAT2 ;
+type_specifier ::= MAT3 ;
+type_specifier ::= MAT4 ;
+type_specifier ::= SAMPLER1D ;
+type_specifier ::= SAMPLER2D ;
+type_specifier ::= SAMPLER3D ;
+type_specifier ::= SAMPLERCUBE ;
+type_specifier ::= SAMPLER1DSHADOW ;
+type_specifier ::= SAMPLER2DSHADOW ;
+type_specifier ::= struct_specifier ;
+type_specifier ::= TYPE_NAME ;
+
+struct_specifier ::= STRUCT IDENTIFIER LEFT_BRACE struct_declaration_list RIGHT_BRACE ;
+/.
+case $rule_number: {
+ types.insert(sym(2).s);
+} break;
+./
+
+struct_specifier ::= STRUCT LEFT_BRACE struct_declaration_list RIGHT_BRACE ;
+
+struct_declaration_list ::= struct_declaration ;
+struct_declaration_list ::= struct_declaration_list struct_declaration ;
+
+struct_declaration ::= type_specifier struct_declarator_list SEMICOLON ;
+
+struct_declarator_list ::= struct_declarator ;
+struct_declarator_list ::= struct_declarator_list COMMA struct_declarator ;
+
+struct_declarator ::= IDENTIFIER ;
+struct_declarator ::= IDENTIFIER LEFT_BRACKET constant_expression RIGHT_BRACKET ;
+
+initializer ::= assignment_expression ;
+
+declaration_statement ::= declaration ;
+
+statement ::= compound_statement ;
+statement ::= simple_statement ;
+
+-- Grammar Note: No labeled statements; 'goto' is not supported.
+
+simple_statement ::= declaration_statement ;
+simple_statement ::= expression_statement ;
+simple_statement ::= selection_statement ;
+simple_statement ::= iteration_statement ;
+simple_statement ::= jump_statement ;
+
+compound_statement ::= LEFT_BRACE RIGHT_BRACE ;
+compound_statement ::= LEFT_BRACE statement_list RIGHT_BRACE ;
+
+statement_no_new_scope ::= compound_statement_no_new_scope ;
+statement_no_new_scope ::= simple_statement ;
+
+compound_statement_no_new_scope ::= LEFT_BRACE RIGHT_BRACE ;
+compound_statement_no_new_scope ::= LEFT_BRACE statement_list RIGHT_BRACE ;
+
+statement_list ::= statement ;
+statement_list ::= statement_list statement ;
+
+expression_statement ::= SEMICOLON ;
+expression_statement ::= expression SEMICOLON ;
+
+selection_statement ::= IF LEFT_PAREN expression RIGHT_PAREN statement ELSE statement ;
+selection_statement ::= IF LEFT_PAREN expression RIGHT_PAREN statement ;
+
+-- Grammar Note: No 'switch'. Switch statements not supported.
+
+condition ::= expression ;
+condition ::= fully_specified_type IDENTIFIER EQUAL initializer ;
+
+iteration_statement ::= WHILE LEFT_PAREN condition RIGHT_PAREN statement_no_new_scope ;
+iteration_statement ::= DO statement WHILE LEFT_PAREN expression RIGHT_PAREN SEMICOLON ;
+iteration_statement ::= FOR LEFT_PAREN for_init_statement for_rest_statement RIGHT_PAREN statement_no_new_scope ;
+
+for_init_statement ::= expression_statement ;
+for_init_statement ::= declaration_statement ;
+
+conditionopt ::= ;
+conditionopt ::= condition ;
+
+for_rest_statement ::= conditionopt SEMICOLON ;
+for_rest_statement ::= conditionopt SEMICOLON expression ;
+
+jump_statement ::= CONTINUE SEMICOLON ;
+jump_statement ::= BREAK SEMICOLON ;
+jump_statement ::= RETURN SEMICOLON ;
+jump_statement ::= RETURN expression SEMICOLON ;
+jump_statement ::= DISCARD SEMICOLON ; -- Fragment shader only.
+
+-- Grammar Note: No 'goto'. Gotos are not supported.
+
+external_declaration ::= function_definition ;
+external_declaration ::= declaration ;
+
+function_definition ::= function_prototype compound_statement_no_new_scope ;
+/.
+ case $rule_number: { // $rule_name
+ qDebug() << "--> function" << *context.function_name;
+ } break;
+./
+
+
+
+
+
+/.
+ } // switch
+
+ state_stack [tos] = nt_action (act, lhs [r] - TERMINAL_COUNT);
+ }
+
+ else
+ {
+ // ### ERROR RECOVERY HERE
+ break;
+ }
+ }
+
+ fprintf (stderr, "%s:%d: Syntax Error\n", qPrintable(context.fileName), context.line);
+
+ return false;
+}
+
+#include "glsl-lex.incl"
+
+
+/////////////////////////////
+// entry point
+/////////////////////////////
+int main()
+{
+#if 0 // dump the GLSL grammar
+ for (int r = 0; r < GLSLParserTable::RULE_COUNT; ++r)
+ {
+ int ridx = GLSLParserTable::rule_index [r];
+ int rhs = GLSLParserTable::rhs [r];
+ printf ("%3d) %s ::=", r + 1, GLSLParserTable::spell[GLSLParserTable::rule_info [ridx]]);
+ ++ridx;
+ for (int i = ridx; i < ridx + rhs; ++i)
+ {
+ int symbol = GLSLParserTable::rule_info [i];
+ if (const char *name = GLSLParserTable::spell [symbol])
+ printf (" %s", name);
+ else
+ printf (" #%d", symbol);
+ }
+ printf ("\n");
+ }
+#endif
+
+ GLSLParser parser;
+
+ if (parser.parse())
+ qDebug() << "OK";
+ else
+ qDebug() << "KO";
+}
+
+./
diff --git a/util/qlalr/examples/glsl/glsl.pro b/util/qlalr/examples/glsl/glsl.pro
new file mode 100644
index 0000000..8ac775f
--- /dev/null
+++ b/util/qlalr/examples/glsl/glsl.pro
@@ -0,0 +1,4 @@
+QT = core
+TARGET = glsl.bin
+SOURCES += glsl.cpp
+
diff --git a/util/qlalr/examples/lambda/COMPILE b/util/qlalr/examples/lambda/COMPILE
new file mode 100644
index 0000000..3226ec9
--- /dev/null
+++ b/util/qlalr/examples/lambda/COMPILE
@@ -0,0 +1,3 @@
+qlalr lambda.g
+qmake
+make
diff --git a/util/qlalr/examples/lambda/lambda.g b/util/qlalr/examples/lambda/lambda.g
new file mode 100644
index 0000000..2fb9594
--- /dev/null
+++ b/util/qlalr/examples/lambda/lambda.g
@@ -0,0 +1,41 @@
+
+-- lambda calculus
+
+%decl lambda.h
+
+%token LPAREN
+%token RPAREN
+%token ID
+%token FUN
+%token DOT
+
+%nonassoc SHIFT_THERE
+%nonassoc LPAREN RPAREN ID FUN DOT
+%nonassoc REDUCE_HERE
+
+%start Expr
+
+/:
+enum {
+:/
+
+
+Expr ::= ID %prec SHIFT_THERE ;
+/: Symbol = $rule_number,
+:/
+
+Expr ::= LPAREN Expr RPAREN %prec SHIFT_THERE ;
+/: SubExpression = $rule_number,
+:/
+
+Expr ::= Expr Expr %prec REDUCE_HERE ;
+/: Appl = $rule_number,
+:/
+
+Expr ::= FUN ID DOT Expr %prec SHIFT_THERE ;
+/: Abstr = $rule_number,
+:/
+
+/:};
+:/
+
diff --git a/util/qlalr/examples/lambda/lambda.pro b/util/qlalr/examples/lambda/lambda.pro
new file mode 100644
index 0000000..dfe4824
--- /dev/null
+++ b/util/qlalr/examples/lambda/lambda.pro
@@ -0,0 +1,3 @@
+HEADERS += lambda.h parser_table_p.h
+SOURCES += main.cpp parser_table.cpp
+QT = core
diff --git a/util/qlalr/examples/lambda/main.cpp b/util/qlalr/examples/lambda/main.cpp
new file mode 100644
index 0000000..c70f9a5
--- /dev/null
+++ b/util/qlalr/examples/lambda/main.cpp
@@ -0,0 +1,160 @@
+
+#include "lambda.h"
+
+
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+#include "parser_table_p.h"
+
+class Parser: protected parser_table
+{
+public:
+ union Value {
+ int ival;
+ // ### more...
+ };
+
+public:
+ Parser();
+ ~Parser();
+
+ bool parse();
+
+protected:
+ inline void reallocateStack();
+
+ inline Value &sym(int index)
+ { return sym_stack [tos + index - 1]; }
+
+ int nextToken();
+ void consumeRule(int ruleno);
+
+protected:
+ int tos;
+ int stack_size;
+ Value *sym_stack;
+ int *state_stack;
+ int current_char;
+ unsigned in_tag: 1;
+};
+
+inline void Parser::reallocateStack()
+{
+ if (! stack_size)
+ stack_size = 128;
+ else
+ stack_size <<= 1;
+
+ sym_stack = reinterpret_cast<Value*> (::realloc(sym_stack, stack_size * sizeof(Value)));
+ state_stack = reinterpret_cast<int*> (::realloc(state_stack, stack_size * sizeof(int)));
+}
+
+Parser::Parser():
+ tos(0),
+ stack_size(0),
+ sym_stack(0),
+ state_stack(0)
+{
+}
+
+Parser::~Parser()
+{
+ if (stack_size) {
+ ::free(sym_stack);
+ ::free(state_stack);
+ }
+}
+
+bool Parser::parse()
+{
+ const int INITIAL_STATE = 0;
+
+ current_char = 0;
+ in_tag = 0;
+
+ int yytoken = -1;
+ reallocateStack();
+
+ tos = 0;
+ state_stack[++tos] = INITIAL_STATE;
+
+ 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].ival = current_char; // ### save the token value here
+ state_stack [tos] = act;
+ yytoken = -1;
+ }
+
+ else if (act < 0)
+ {
+ int r = - act - 1;
+
+ tos -= rhs [r];
+ act = state_stack [tos++];
+ consumeRule (r);
+ state_stack [tos] = nt_action (act, lhs [r] - TERMINAL_COUNT);
+ }
+
+ else
+ break;
+ }
+
+ return false;
+}
+
+
+int Parser::nextToken()
+{
+ static int tokens[] = { ID, ID, ID, EOF_SYMBOL };
+ static int *tk = tokens;
+
+ return *tk++;
+}
+
+void Parser::consumeRule(int ruleno)
+{
+ switch (ruleno) {
+ case Symbol:
+ printf("symbol\n");
+ break;
+ case SubExpression:
+ printf("sub-expr\n");
+ break;
+ case Appl:
+ printf("appl\n");
+ break;
+ case Abstr:
+ printf("abstr\n");
+ break;
+ }
+}
+
+/////////////////////////////
+// entry point
+/////////////////////////////
+int main()
+{
+ Parser parser;
+
+ if (parser.parse())
+ printf ("OK\n");
+ else
+ printf ("KO\n");
+}
+
+
diff --git a/util/qlalr/examples/qparser/COMPILE b/util/qlalr/examples/qparser/COMPILE
new file mode 100644
index 0000000..4aad300
--- /dev/null
+++ b/util/qlalr/examples/qparser/COMPILE
@@ -0,0 +1,3 @@
+qlalr calc.g
+qmake
+make
diff --git a/util/qlalr/examples/qparser/calc.g b/util/qlalr/examples/qparser/calc.g
new file mode 100644
index 0000000..24371d4
--- /dev/null
+++ b/util/qlalr/examples/qparser/calc.g
@@ -0,0 +1,93 @@
+
+%parser calc_grammar
+%decl calc_parser.h
+%impl calc_parser.cpp
+
+%token_prefix Token_
+%token number
+%token lparen
+%token rparen
+%token plus
+%token minus
+
+%start Goal
+
+/:
+#ifndef CALC_PARSER_H
+#define CALC_PARSER_H
+
+#include "qparser.h"
+#include "calc_grammar_p.h"
+
+class CalcParser: public QParser<CalcParser, $table>
+{
+public:
+ int nextToken();
+ void consumeRule(int ruleno);
+};
+
+#endif // CALC_PARSER_H
+:/
+
+
+
+
+
+/.
+#include "calc_parser.h"
+
+#include <QtDebug>
+#include <cstdlib>
+
+void CalcParser::consumeRule(int ruleno)
+ {
+ switch (ruleno) {
+./
+
+Goal: Expression ;
+/.
+case $rule_number:
+ qDebug() << "value:" << sym(1);
+ break;
+./
+
+PrimaryExpression: number ;
+PrimaryExpression: lparen Expression rparen ;
+/.
+case $rule_number:
+ sym(1) = sym (2);
+ break;
+./
+
+Expression: PrimaryExpression ;
+
+Expression: Expression plus PrimaryExpression;
+/.
+case $rule_number:
+ sym(1) += sym (3);
+ break;
+./
+
+Expression: Expression minus PrimaryExpression;
+/.
+case $rule_number:
+ sym(1) -= sym (3);
+ break;
+./
+
+
+
+/.
+ } // switch
+}
+
+#include <cstdio>
+
+int main()
+{
+ CalcParser p;
+
+ if (p.parse())
+ printf("ok\n");
+}
+./
diff --git a/util/qlalr/examples/qparser/calc.l b/util/qlalr/examples/qparser/calc.l
new file mode 100644
index 0000000..95181d5
--- /dev/null
+++ b/util/qlalr/examples/qparser/calc.l
@@ -0,0 +1,20 @@
+
+%option noyywrap
+
+%{
+#include "calc_parser.h"
+#include <cstdlib>
+
+#define YY_DECL int CalcParser::nextToken()
+%}
+
+%%
+
+[ \t\n] { /* eat me */ }
+[0-9]+ { sym(1) = atoi (yytext); return Token_number; }
+"(" { return Token_lparen; }
+")" { return Token_rparen; }
+"+" { return Token_plus; }
+"-" { return Token_minus; }
+
+%%
diff --git a/util/qlalr/examples/qparser/qparser.cpp b/util/qlalr/examples/qparser/qparser.cpp
new file mode 100644
index 0000000..5a18ee2
--- /dev/null
+++ b/util/qlalr/examples/qparser/qparser.cpp
@@ -0,0 +1,3 @@
+
+#include "qparser.h"
+
diff --git a/util/qlalr/examples/qparser/qparser.h b/util/qlalr/examples/qparser/qparser.h
new file mode 100644
index 0000000..e3ff61d
--- /dev/null
+++ b/util/qlalr/examples/qparser/qparser.h
@@ -0,0 +1,111 @@
+#ifndef QPARSER_H
+#define QPARSER_H
+
+#include <QtCore/QSharedDataPointer>
+#include <QtCore/QVarLengthArray>
+
+template <typename _Parser, typename _Table, typename _Value = int>
+class QParser: protected _Table
+{
+public:
+ QParser();
+ ~QParser();
+
+ bool parse();
+
+ inline _Value &sym(int index);
+
+private:
+ inline int nextToken()
+ {
+ return static_cast<_Parser*> (this)->nextToken();
+ }
+
+ inline void consumeRule(int rule)
+ {
+ static_cast<_Parser*> (this)->consumeRule(rule);
+ }
+
+ enum { DefaultStackSize = 128 };
+
+ struct Data: public QSharedData
+ {
+ Data(): stackSize (DefaultStackSize), tos (0) {}
+
+ QVarLengthArray<int, DefaultStackSize> stateStack;
+ QVarLengthArray<_Value, DefaultStackSize> parseStack;
+ int stackSize;
+ int tos;
+
+ void reallocateStack() {
+ stackSize <<= 1;
+ stateStack.resize(stackSize);
+ parseStack.resize(stackSize);
+ }
+ };
+
+ QSharedDataPointer<Data> d;
+};
+
+template <typename _Parser, typename _Table, typename _Value>
+inline _Value &QParser<_Parser, _Table, _Value>::sym(int n)
+{
+ return d->parseStack [d->tos + n - 1];
+}
+
+template <typename _Parser, typename _Table, typename _Value>
+QParser<_Parser, _Table, _Value>::QParser():
+ d(new Data())
+{
+}
+
+template <typename _Parser, typename _Table, typename _Value>
+QParser<_Parser, _Table, _Value>::~QParser()
+{
+}
+
+template <typename _Parser, typename _Table, typename _Value>
+bool QParser<_Parser, _Table, _Value>::parse()
+{
+ const int INITIAL_STATE = 0;
+
+ d->tos = 0;
+ d->reallocateStack();
+
+ int act = d->stateStack[++d->tos] = INITIAL_STATE;
+ int token = -1;
+
+ forever {
+ if (token == -1 && - _Table::TERMINAL_COUNT != _Table::action_index[act])
+ token = nextToken();
+
+ act = _Table::t_action(act, token);
+
+ if (d->stateStack[d->tos] == _Table::ACCEPT_STATE)
+ return true;
+
+ else if (act > 0) {
+ if (++d->tos == d->stackSize)
+ d->reallocateStack();
+
+ d->parseStack[d->tos] = d->parseStack[d->tos - 1];
+ d->stateStack[d->tos] = act;
+ token = -1;
+ }
+
+ else if (act < 0) {
+ int r = - act - 1;
+ d->tos -= _Table::rhs[r];
+ act = d->stateStack[d->tos++];
+ consumeRule(r);
+ act = d->stateStack[d->tos] = _Table::nt_action(act, _Table::lhs[r] - _Table::TERMINAL_COUNT);
+ }
+
+ else break;
+ }
+
+ return false;
+}
+
+
+#endif // QPARSER_H
diff --git a/util/qlalr/examples/qparser/qparser.pro b/util/qlalr/examples/qparser/qparser.pro
new file mode 100644
index 0000000..938e336
--- /dev/null
+++ b/util/qlalr/examples/qparser/qparser.pro
@@ -0,0 +1,4 @@
+QT = core
+HEADERS += calc_grammar_p.h calc_parser.h qparser.h
+SOURCES += calc_grammar.cpp calc_parser.cpp qparser.cpp
+LEXSOURCES += calc.l
diff --git a/util/qlalr/grammar.cpp b/util/qlalr/grammar.cpp
new file mode 100644
index 0000000..9e5dabf
--- /dev/null
+++ b/util/qlalr/grammar.cpp
@@ -0,0 +1,123 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the QLALR project on Trolltech 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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@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/util/qlalr/grammar_p.h b/util/qlalr/grammar_p.h
new file mode 100644
index 0000000..a9a4172
--- /dev/null
+++ b/util/qlalr/grammar_p.h
@@ -0,0 +1,119 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the QLALR project on Trolltech 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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@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/util/qlalr/lalr.cpp b/util/qlalr/lalr.cpp
new file mode 100644
index 0000000..51c2674
--- /dev/null
+++ b/util/qlalr/lalr.cpp
@@ -0,0 +1,783 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the QLALR project on Trolltech 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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@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/util/qlalr/lalr.g b/util/qlalr/lalr.g
new file mode 100644
index 0000000..ed2ef86
--- /dev/null
+++ b/util/qlalr/lalr.g
@@ -0,0 +1,803 @@
+-----------------------------------------------------------------------------
+--
+-- Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+-- Contact: Qt Software Information (qt-info@nokia.com)
+--
+-- This file is part of the QLALR project on Trolltech 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 either Technology Preview License Agreement or the
+-- Beta Release License Agreement.
+--
+-- 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.0, included in the file LGPL_EXCEPTION.txt in this
+-- package.
+--
+-- GNU General Public License Usage
+-- Alternatively, this file may be used under the terms of the GNU
+-- General Public License version 3.0 as published by the Free Software
+-- Foundation and appearing in the file LICENSE.GPL included in the
+-- packaging of this file. Please review the following information to
+-- ensure the GNU General Public License version 3.0 requirements will be
+-- met: http://www.gnu.org/copyleft/gpl.html.
+--
+-- If you are unsure which license is appropriate for your use, please
+-- contact the sales department at qt-sales@nokia.com.
+-- $QT_END_LICENSE$
+--
+-- This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+-- WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
+--
+-----------------------------------------------------------------------------
+
+
+%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) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the <your project> project on Trolltech 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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@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) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the <your project> project on Trolltech 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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@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/util/qlalr/lalr.h b/util/qlalr/lalr.h
new file mode 100644
index 0000000..29bb522
--- /dev/null
+++ b/util/qlalr/lalr.h
@@ -0,0 +1,502 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the QLALR project on Trolltech 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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@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/util/qlalr/main.cpp b/util/qlalr/main.cpp
new file mode 100644
index 0000000..91c72bb
--- /dev/null
+++ b/util/qlalr/main.cpp
@@ -0,0 +1,185 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the QLALR project on Trolltech 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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@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
+ << " --troll\t\tadd the Trolltech copyright header" << 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 ("--troll"))
+ 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.setTrollCopyright (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/util/qlalr/parsetable.cpp b/util/qlalr/parsetable.cpp
new file mode 100644
index 0000000..c117071
--- /dev/null
+++ b/util/qlalr/parsetable.cpp
@@ -0,0 +1,127 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the QLALR project on Trolltech 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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@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/util/qlalr/parsetable.h b/util/qlalr/parsetable.h
new file mode 100644
index 0000000..36f6926
--- /dev/null
+++ b/util/qlalr/parsetable.h
@@ -0,0 +1,59 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the QLALR project on Trolltech 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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@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/util/qlalr/qlalr.pro b/util/qlalr/qlalr.pro
new file mode 100644
index 0000000..881a36a
--- /dev/null
+++ b/util/qlalr/qlalr.pro
@@ -0,0 +1,21 @@
+
+TEMPLATE = app
+QT = core
+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
diff --git a/util/qlalr/recognizer.cpp b/util/qlalr/recognizer.cpp
new file mode 100644
index 0000000..5a7ad3b
--- /dev/null
+++ b/util/qlalr/recognizer.cpp
@@ -0,0 +1,489 @@
+
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the <your project> project on Trolltech 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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@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/util/qlalr/recognizer.h b/util/qlalr/recognizer.h
new file mode 100644
index 0000000..c9be98f
--- /dev/null
+++ b/util/qlalr/recognizer.h
@@ -0,0 +1,111 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the QLALR project on Trolltech 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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@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;
+};