Long live Qt 4.5!

42 files changed, 6439 insertions, 0 deletions

diff --git a/util/qlalr/.gitignore b/util/qlalr/.gitignore
new file mode 100644
index 0000000000..ce75745f6a
--- /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 0000000000..b186fa1b51
--- /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 0000000000..f1daac8daf
--- /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 0000000000..8b7ac60bc1
--- /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 0000000000..9bfc1a9200
--- /dev/null
+++ b/util/qlalr/cppgenerator.cpp
@@ -0,0 +1,703 @@
+/****************************************************************************
+**
+** 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"
+    "**\n"
+    "** This file is part of the $MODULE$ of the Qt Toolkit.\n"
+    "**\n"
+    "** $TROLLTECH_DUAL_LICENSE$\n"
+    "**\n"
+    "** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE\n"
+    "** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.\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 0000000000..dd3241375d
--- /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 0000000000..d97ff7d217
--- /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 0000000000..afc66d548a
--- /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 0000000000..2dc67161c1
--- /dev/null
+++ b/util/qlalr/doc/src/images/qt-logo.png
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 0000000000..19e3789d50
--- /dev/null
+++ b/util/qlalr/doc/src/images/trolltech-logo.png
diff --git a/util/qlalr/doc/src/qlalr.qdoc b/util/qlalr/doc/src/qlalr.qdoc
new file mode 100644
index 0000000000..313c7a42aa
--- /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 0000000000..641ed01910
--- /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 0000000000..e308b74cc8
--- /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 0000000000..e54512d6c9
--- /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 0000000000..54f5e0e29f
--- /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 0000000000..212c8297c8
--- /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 0000000000..031691152e
--- /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 0000000000..c19018f985
--- /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 0000000000..1e07c3b71e
--- /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 0000000000..3f3a3ad573
--- /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 0000000000..8ac775f21d
--- /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 0000000000..3226ec95fa
--- /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 0000000000..2fb95940fd
--- /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 0000000000..dfe4824027
--- /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 0000000000..c70f9a5bdb
--- /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 0000000000..4aad300a9f
--- /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 0000000000..24371d48b7
--- /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 0000000000..95181d5213
--- /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 0000000000..5a18ee2cac
--- /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 0000000000..e3ff61d7c8
--- /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 0000000000..938e336939
--- /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 0000000000..9e5dabfdd5
--- /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 0000000000..a9a4172ce9
--- /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 0000000000..51c2674dad
--- /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 0000000000..ed2ef86dca
--- /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 0000000000..29bb522dd6
--- /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 0000000000..91c72bb3ff
--- /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 0000000000..c117071a64
--- /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 0000000000..36f6926818
--- /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 0000000000..881a36a734
--- /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 0000000000..5a7ad3b254
--- /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 0000000000..c9be98f7a8
--- /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;
+};