diff options
| author | Oswald Buddenhagen <oswald.buddenhagen@digia.com> | 2013-06-12 12:08:32 +0200 |
|---|---|---|
| committer | The Qt Project <gerrit-noreply@qt-project.org> | 2014-01-20 09:26:37 +0100 |
| commit | e06557b596e7bc37aad70e4083bf59ff240681a1 (patch) | |
| tree | 38681727b52cbafe240acf289ef69b2f1878d404 /util | |
| parent | 08841c1c2f436fb304b3766114c4525ba21c63ba (diff) | |
re-import qlalr into qtbase
we have a bunch of qlalr-generated sources all over the place. it would
be much nicer to actually generate them at build time, rather than
checking them in. this obviously requires building qlalr early on ...
this commit restores the sources at their pre-modularization location
and makes no attempt at integrating them into the build process yet.
this is a measure to overcome git stupidity.
this imports qt/qlalr at commit 4071d86e82b299f26e335a7faf662b5a676e2279
with some style fixes on top.
Change-Id: I83472bc492440ecb96a8a0d5bf74cf968a1e17d2
Reviewed-by: Lars Knoll <lars.knoll@digia.com>
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
Diffstat (limited to 'util')
39 files changed, 6979 insertions, 0 deletions
diff --git a/util/qlalr/compress.cpp b/util/qlalr/compress.cpp new file mode 100644 index 0000000000..bd35b171cf --- /dev/null +++ b/util/qlalr/compress.cpp @@ -0,0 +1,286 @@ +/**************************************************************************** +** +** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the test suite module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $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..64c2bba14c --- /dev/null +++ b/util/qlalr/compress.h @@ -0,0 +1,60 @@ +/**************************************************************************** +** +** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the utils of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $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..c62ee78917 --- /dev/null +++ b/util/qlalr/cppgenerator.cpp @@ -0,0 +1,749 @@ +/**************************************************************************** +** +** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the QLALR module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + + +#include <QtCore/qbitarray.h> +#include <QtCore/qtextstream.h> +#include <QtCore/qfile.h> +#include <QtCore/qmap.h> + +#include "cppgenerator.h" +#include "lalr.h" +#include "recognizer.h" + +QString CppGenerator::copyrightHeader() const +{ + return QLatin1String( + "/****************************************************************************\n" + "**\n" + "** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies).\n" + "** Contact: http://www.qt-project.org/legal\n" + "**\n" + "** This file is part of the Qt Toolkit.\n" + "**\n" + "** $QT_BEGIN_LICENSE:LGPL$\n" + "** Commercial License Usage\n" + "** Licensees holding valid commercial Qt licenses may use this file in\n" + "** accordance with the commercial license agreement provided with the\n" + "** Software or, alternatively, in accordance with the terms contained in\n" + "** a written agreement between you and Digia. For licensing terms and\n" + "** conditions see http://qt.digia.com/licensing. For further information\n" + "** use the contact form at http://qt.digia.com/contact-us.\n" + "**\n" + "** GNU Lesser General Public License Usage\n" + "** Alternatively, this file may be used under the terms of the GNU Lesser\n" + "** General Public License version 2.1 as published by the Free Software\n" + "** Foundation and appearing in the file LICENSE.LGPL included in the\n" + "** packaging of this file. Please review the following information to\n" + "** ensure the GNU Lesser General Public License version 2.1 requirements\n" + "** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.\n" + "**\n" + "** In addition, as a special exception, Digia gives you certain additional\n" + "** rights. These rights are described in the Digia Qt LGPL Exception\n" + "** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.\n" + "**\n" + "** GNU General Public License Usage\n" + "** Alternatively, this file may be used under the terms of the GNU\n" + "** General Public License version 3.0 as published by the Free Software\n" + "** Foundation and appearing in the file LICENSE.GPL included in the\n" + "** packaging of this file. Please review the following information to\n" + "** ensure the GNU General Public License version 3.0 requirements will be\n" + "** met: http://www.gnu.org/copyleft/gpl.html.\n" + "**\n" + "**\n" + "** $QT_END_LICENSE$\n" + "**\n" + "****************************************************************************/\n" + "\n"); +} + +QString CppGenerator::privateCopyrightHeader() const +{ + return QLatin1String( + "//\n" + "// W A R N I N G\n" + "// -------------\n" + "//\n" + "// This file is not part of the Qt API. It exists for the convenience\n" + "// of other Qt classes. This header file may change from version to\n" + "// version without notice, or even be removed.\n" + "//\n" + "// We mean it.\n" + "//\n"); +} + +QString CppGenerator::startIncludeGuard(const QString &fileName) +{ + const QString normalized(QString(fileName).replace(QLatin1Char('.'), QLatin1Char('_')).toUpper()); + + return QString::fromLatin1("#ifndef %1\n" + "#define %2\n").arg(normalized, normalized); +} + +QString CppGenerator::endIncludeGuard(const QString &fileName) +{ + const QString normalized(QString(fileName).replace(QLatin1Char('.'), QLatin1Char('_')).toUpper()); + + return QString::fromLatin1("#endif // %1\n").arg(normalized); +} + +void CppGenerator::operator () () +{ + // action table... + state_count = aut.states.size (); + terminal_count = grammar.terminals.size (); + non_terminal_count = grammar.non_terminals.size (); + +#define ACTION(i, j) table [(i) * terminal_count + (j)] +#define GOTO(i, j) pgoto [(i) * non_terminal_count + (j)] + + int *table = new int [state_count * terminal_count]; + ::memset (table, 0, state_count * terminal_count * sizeof (int)); + + int *pgoto = new int [state_count * non_terminal_count]; + ::memset (pgoto, 0, state_count * non_terminal_count * sizeof (int)); + + accept_state = -1; + int shift_reduce_conflict_count = 0; + int reduce_reduce_conflict_count = 0; + + for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state) + { + int q = aut.id (state); + + for (Bundle::iterator a = state->bundle.begin (); a != state->bundle.end (); ++a) + { + int symbol = aut.id (a.key ()); + int r = aut.id (a.value ()); + + Q_ASSERT (r < state_count); + + if (grammar.isNonTerminal (a.key ())) + { + Q_ASSERT (symbol >= terminal_count && symbol < grammar.names.size ()); + GOTO (q, symbol - terminal_count) = r; + } + + else + ACTION (q, symbol) = r; + } + + for (ItemPointer item = state->closure.begin (); item != state->closure.end (); ++item) + { + if (item->dot != item->end_rhs ()) + continue; + + int r = aut.id (item->rule); + + NameSet lookaheads = aut.lookaheads.value (item); + + if (item->rule == grammar.goal) + accept_state = q; + + foreach (Name s, lookaheads) + { + int &u = ACTION (q, aut.id (s)); + + if (u == 0) + u = - r; + + else if (u < 0) + { + if (verbose) + qout << "*** Warning. Found a reduce/reduce conflict in state " << q << " on token ``" << s << "'' between rule " + << r << " and " << -u << endl; + + ++reduce_reduce_conflict_count; + + u = qMax (u, -r); + + if (verbose) + qout << "\tresolved using rule " << -u << endl; + } + + else if (u > 0) + { + if (item->rule->prec != grammar.names.end() && grammar.token_info.contains (s)) + { + Grammar::TokenInfo info_r = grammar.token_info.value (item->rule->prec); + Grammar::TokenInfo info_s = grammar.token_info.value (s); + + if (info_r.prec > info_s.prec) + u = -r; + else if (info_r.prec == info_s.prec) + { + switch (info_r.assoc) { + case Grammar::Left: + u = -r; + break; + case Grammar::Right: + // shift... nothing to do + break; + case Grammar::NonAssoc: + u = 0; + break; + } // switch + } + } + + else + { + ++shift_reduce_conflict_count; + + if (verbose) + qout << "*** Warning. Found a shift/reduce conflict in state " << q << " on token ``" << s << "'' with rule " << r << endl; + } + } + } + } + } + + if (shift_reduce_conflict_count || reduce_reduce_conflict_count) + { + if (shift_reduce_conflict_count != grammar.expected_shift_reduce + || reduce_reduce_conflict_count != grammar.expected_reduce_reduce) + qerr << "*** Conflicts: " << shift_reduce_conflict_count << " shift/reduce, " << reduce_reduce_conflict_count << " reduce/reduce" << endl; + + if (verbose) + qout << endl << "*** Conflicts: " << shift_reduce_conflict_count << " shift/reduce, " << reduce_reduce_conflict_count << " reduce/reduce" << endl + << endl; + } + + QBitArray used_rules (grammar.rules.count ()); + + int q = 0; + for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state, ++q) + { + for (int j = 0; j < terminal_count; ++j) + { + int &u = ACTION (q, j); + + if (u < 0) + used_rules.setBit (-u - 1); + } + } + + for (int i = 0; i < used_rules.count (); ++i) + { + if (! used_rules.testBit (i)) + { + RulePointer rule = grammar.rules.begin () + i; + + if (rule != grammar.goal) + qerr << "*** Warning: Rule ``" << *rule << "'' is useless!" << endl; + } + } + + q = 0; + for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state, ++q) + { + for (int j = 0; j < terminal_count; ++j) + { + int &u = ACTION (q, j); + + if (u >= 0) + continue; + + RulePointer rule = grammar.rules.begin () + (- u - 1); + + if (state->defaultReduce == rule) + u = 0; + } + } + + // ... compress the goto table + defgoto.resize (non_terminal_count); + for (int j = 0; j < non_terminal_count; ++j) + { + count.fill (0, state_count); + + int &mx = defgoto [j]; + + for (int i = 0; i < state_count; ++i) + { + int r = GOTO (i, j); + + if (! r) + continue; + + ++count [r]; + + if (count [r] > count [mx]) + mx = r; + } + } + + for (int i = 0; i < state_count; ++i) + { + for (int j = 0; j < non_terminal_count; ++j) + { + int &r = GOTO (i, j); + + if (r == defgoto [j]) + r = 0; + } + } + + compressed_action (table, state_count, terminal_count); + compressed_goto (pgoto, state_count, non_terminal_count); + + delete[] table; + table = 0; + + delete[] pgoto; + pgoto = 0; + +#undef ACTION +#undef GOTO + + if (! grammar.merged_output.isEmpty()) + { + QFile f(grammar.merged_output); + if (! f.open (QFile::WriteOnly)) + { + fprintf (stderr, "*** cannot create %s\n", qPrintable(grammar.merged_output)); + return; + } + + QTextStream out (&f); + + // copyright headers must come first, otherwise the headers tests will fail + if (copyright) + { + out << copyrightHeader() + << privateCopyrightHeader() + << endl; + } + + out << "// This file was generated by qlalr - DO NOT EDIT!\n"; + + out << startIncludeGuard(grammar.merged_output) << endl; + + if (copyright) { + out << "#if defined(ERROR)" << endl + << "# undef ERROR" << endl + << "#endif" << endl << endl; + } + + generateDecl (out); + generateImpl (out); + out << p.decls(); + out << p.impls(); + out << endl; + + out << endIncludeGuard(grammar.merged_output) << endl; + + return; + } + + // default behaviour + QString declFileName = grammar.table_name.toLower () + QLatin1String("_p.h"); + QString bitsFileName = grammar.table_name.toLower () + QLatin1String(".cpp"); + + { // decls... + QFile f (declFileName); + f.open (QFile::WriteOnly); + QTextStream out (&f); + + QString prot = declFileName.toUpper ().replace (QLatin1Char ('.'), QLatin1Char ('_')); + + // copyright headers must come first, otherwise the headers tests will fail + if (copyright) + { + out << copyrightHeader() + << privateCopyrightHeader() + << endl; + } + + out << "// This file was generated by qlalr - DO NOT EDIT!\n"; + + out << "#ifndef " << prot << endl + << "#define " << prot << endl + << endl; + + if (copyright) { + out << "#include <QtCore/qglobal.h>" << endl << endl; + out << "QT_BEGIN_NAMESPACE" << endl << endl; + } + generateDecl (out); + if (copyright) + out << "QT_END_NAMESPACE" << endl; + + out << "#endif // " << prot << endl << endl; + } // end decls + + { // bits... + QFile f (bitsFileName); + f.open (QFile::WriteOnly); + QTextStream out (&f); + + // copyright headers must come first, otherwise the headers tests will fail + if (copyright) + out << copyrightHeader(); + + out << "// This file was generated by qlalr - DO NOT EDIT!\n"; + + out << "#include \"" << declFileName << "\"" << endl << endl; + if (copyright) + out << "QT_BEGIN_NAMESPACE" << endl << endl; + generateImpl(out); + if (copyright) + out << "QT_END_NAMESPACE" << endl; + + } // end bits + + if (! grammar.decl_file_name.isEmpty ()) + { + QFile f (grammar.decl_file_name); + f.open (QFile::WriteOnly); + QTextStream out (&f); + out << p.decls(); + } + + if (! grammar.impl_file_name.isEmpty ()) + { + QFile f (grammar.impl_file_name); + f.open (QFile::WriteOnly); + QTextStream out (&f); + out << p.impls(); + } +} + +QString CppGenerator::debugInfoProt() const +{ + QString prot = QLatin1String("QLALR_NO_"); + prot += grammar.table_name.toUpper(); + prot += QLatin1String("_DEBUG_INFO"); + return prot; +} + +void CppGenerator::generateDecl (QTextStream &out) +{ + out << "class " << grammar.table_name << endl + << "{" << endl + << "public:" << endl + << " enum VariousConstants {" << endl; + + foreach (Name t, grammar.terminals) + { + QString name = *t; + int value = std::distance (grammar.names.begin (), t); + + if (name == QLatin1String ("$end")) + name = QLatin1String ("EOF_SYMBOL"); + + else if (name == QLatin1String ("$accept")) + name = QLatin1String ("ACCEPT_SYMBOL"); + + else + name.prepend (grammar.token_prefix); + + out << " " << name << " = " << value << "," << endl; + } + + out << endl + << " ACCEPT_STATE = " << accept_state << "," << endl + << " RULE_COUNT = " << grammar.rules.size () << "," << endl + << " STATE_COUNT = " << state_count << "," << endl + << " TERMINAL_COUNT = " << terminal_count << "," << endl + << " NON_TERMINAL_COUNT = " << non_terminal_count << "," << endl + << endl + << " GOTO_INDEX_OFFSET = " << compressed_action.index.size () << "," << endl + << " GOTO_INFO_OFFSET = " << compressed_action.info.size () << "," << endl + << " GOTO_CHECK_OFFSET = " << compressed_action.check.size () << endl + << " };" << endl + << endl + << " static const char *const spell [];" << endl + << " static const short lhs [];" << endl + << " static const short rhs [];" << endl; + + if (debug_info) + { + QString prot = debugInfoProt(); + + out << endl << "#ifndef " << prot << endl + << " static const int rule_index [];" << endl + << " static const int rule_info [];" << endl + << "#endif // " << prot << endl << endl; + } + + out << " static const short goto_default [];" << endl + << " static const short action_default [];" << endl + << " static const short action_index [];" << endl + << " static const short action_info [];" << endl + << " static const short action_check [];" << endl + << endl + << " static inline int nt_action (int state, int nt)" << endl + << " {" << endl + << " const int yyn = action_index [GOTO_INDEX_OFFSET + state] + nt;" << endl + << " if (yyn < 0 || action_check [GOTO_CHECK_OFFSET + yyn] != nt)" << endl + << " return goto_default [nt];" << endl + << endl + << " return action_info [GOTO_INFO_OFFSET + yyn];" << endl + << " }" << endl + << endl + << " static inline int t_action (int state, int token)" << endl + << " {" << endl + << " const int yyn = action_index [state] + token;" << endl + << endl + << " if (yyn < 0 || action_check [yyn] != token)" << endl + << " return - action_default [state];" << endl + << endl + << " return action_info [yyn];" << endl + << " }" << endl + << "};" << endl + << endl + << endl; +} + +void CppGenerator::generateImpl (QTextStream &out) +{ + int idx = 0; + + out << "const char *const " << grammar.table_name << "::spell [] = {"; + idx = 0; + + QMap<Name, int> name_ids; + bool first_nt = true; + + for (Name t = grammar.names.begin (); t != grammar.names.end (); ++t, ++idx) + { + bool terminal = grammar.isTerminal (t); + + if (! (debug_info || terminal)) + break; + + name_ids.insert (t, idx); + + if (idx) + out << ", "; + + if (! (idx % 10)) + out << endl << " "; + + if (terminal) + { + QString spell = grammar.spells.value (t); + + if (spell.isEmpty ()) + out << "0"; + else + out << "\"" << spell << "\""; + } + else + { + if (first_nt) + { + first_nt = false; + QString prot = debugInfoProt(); + out << endl << "#ifndef " << prot << endl; + } + out << "\"" << *t << "\""; + } + } + + if (debug_info) + out << endl << "#endif // " << debugInfoProt() << endl; + + out << "};" << endl << endl; + + out << "const short " << grammar.table_name << "::lhs [] = {"; + idx = 0; + for (RulePointer rule = grammar.rules.begin (); rule != grammar.rules.end (); ++rule, ++idx) + { + if (idx) + out << ", "; + + if (! (idx % 10)) + out << endl << " "; + + out << aut.id (rule->lhs); + } + out << "};" << endl << endl; + + out << "const short " << grammar.table_name << "::rhs [] = {"; + idx = 0; + for (RulePointer rule = grammar.rules.begin (); rule != grammar.rules.end (); ++rule, ++idx) + { + if (idx) + out << ", "; + + if (! (idx % 10)) + out << endl << " "; + + out << rule->rhs.size (); + } + out << "};" << endl << endl; + + if (debug_info) + { + QString prot = debugInfoProt(); + + out << endl << "#ifndef " << prot << endl; + out << "const int " << grammar.table_name << "::rule_info [] = {"; + idx = 0; + for (RulePointer rule = grammar.rules.begin (); rule != grammar.rules.end (); ++rule, ++idx) + { + out << endl << " "; + + if (idx) + out << ", "; + else + out << " "; + + out << name_ids.value(rule->lhs); + + foreach (Name n, rule->rhs) + out << ", " << name_ids.value (n); + } + out << "};" << endl << endl; + + out << "const int " << grammar.table_name << "::rule_index [] = {"; + idx = 0; + int offset = 0; + for (RulePointer rule = grammar.rules.begin (); rule != grammar.rules.end (); ++rule, ++idx) + { + if (idx) + out << ", "; + + if (! (idx % 10)) + out << endl << " "; + + out << offset; + offset += rule->rhs.size () + 1; + } + out << "};" << endl + << "#endif // " << prot << endl << endl; + } + + out << "const short " << grammar.table_name << "::action_default [] = {"; + idx = 0; + for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state, ++idx) + { + if (state != aut.states.begin ()) + out << ", "; + + if (! (idx % 10)) + out << endl << " "; + + if (state->defaultReduce != grammar.rules.end ()) + out << aut.id (state->defaultReduce); + else + out << "0"; + } + out << "};" << endl << endl; + + out << "const short " << grammar.table_name << "::goto_default [] = {"; + for (int i = 0; i < defgoto.size (); ++i) + { + if (i) + out << ", "; + + if (! (i % 10)) + out << endl << " "; + + out << defgoto [i]; + } + out << "};" << endl << endl; + + out << "const short " << grammar.table_name << "::action_index [] = {"; + for (int i = 0; i < compressed_action.index.size (); ++i) + { + if (! (i % 10)) + out << endl << " "; + + out << compressed_action.index [i] << ", "; + } + out << endl; + for (int i = 0; i < compressed_goto.index.size (); ++i) + { + if (i) + out << ", "; + + if (! (i % 10)) + out << endl << " "; + + out << compressed_goto.index [i]; + } + out << "};" << endl << endl; + + out << "const short " << grammar.table_name << "::action_info [] = {"; + for (int i = 0; i < compressed_action.info.size (); ++i) + { + if (! (i % 10)) + out << endl << " "; + + out << compressed_action.info [i] << ", "; + } + out << endl; + for (int i = 0; i < compressed_goto.info.size (); ++i) + { + if (i) + out << ", "; + + if (! (i % 10)) + out << endl << " "; + + out << compressed_goto.info [i]; + } + out << "};" << endl << endl; + + out << "const short " << grammar.table_name << "::action_check [] = {"; + for (int i = 0; i < compressed_action.check.size (); ++i) + { + if (! (i % 10)) + out << endl << " "; + + out << compressed_action.check [i] << ", "; + } + out << endl; + for (int i = 0; i < compressed_goto.check.size (); ++i) + { + if (i) + out << ", "; + + if (! (i % 10)) + out << endl << " "; + + out << compressed_goto.check [i]; + } + out << "};" << endl << endl; +} diff --git a/util/qlalr/cppgenerator.h b/util/qlalr/cppgenerator.h new file mode 100644 index 0000000000..3ee5dc91e3 --- /dev/null +++ b/util/qlalr/cppgenerator.h @@ -0,0 +1,98 @@ +/**************************************************************************** +** +** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the QLALR module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef CPPGENERATOR_H +#define CPPGENERATOR_H + +#include "lalr.h" +#include "compress.h" + +class Grammar; +class Automaton; +class Recognizer; + +class CppGenerator +{ +public: + CppGenerator(const Recognizer &p, Grammar &grammar, Automaton &aut, bool verbose): + p (p), + grammar (grammar), + aut (aut), + verbose (verbose), + debug_info (false), + copyright (false) {} + + void operator () (); + + bool debugInfo () const { return debug_info; } + void setDebugInfo (bool d) { debug_info = d; } + + void setCopyright (bool t) { copyright = t; } + +private: + void generateDecl (QTextStream &out); + void generateImpl (QTextStream &out); + + QString debugInfoProt() const; + QString copyrightHeader() const; + QString privateCopyrightHeader() const; + +private: + static QString startIncludeGuard(const QString &fileName); + static QString endIncludeGuard(const QString &fileName); + + const Recognizer &p; + Grammar &grammar; + Automaton &aut; + bool verbose; + int accept_state; + int state_count; + int terminal_count; + int non_terminal_count; + bool debug_info; + bool copyright; + Compress compressed_action; + Compress compressed_goto; + QVector<int> count; + QVector<int> defgoto; +}; + +#endif // CPPGENERATOR_H diff --git a/util/qlalr/doc/qlalr.qdocconf b/util/qlalr/doc/qlalr.qdocconf new file mode 100644 index 0000000000..434393a727 --- /dev/null +++ b/util/qlalr/doc/qlalr.qdocconf @@ -0,0 +1,64 @@ +# Run qdoc from the directory that contains this file. + +project = qlalr +description = qlalr Reference Documentation +url = http://qt.nokia.com/doc/ + +language = Cpp + +# sourcedirs = $PWD/src +sourcedirs = src +sources.fileextensions = "*.qdoc" + +exampledirs = ../examples + +imagedirs = src/images +outputdir = html +codeindent = 1 +extraimages.HTML = qt-logo + +macro.key = "\\b" +macro.menu = "\\b" +macro.gui = "\\b" +macro.reg.HTML = "<sup>®</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 = "é" +macro.aring.HTML = "å" +macro.oslash.HTML = "ø" +macro.ouml.HTML = "ö" +macro.Auml.HTML = "Ä" +macro.uuml.HTML = "ü" + +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://qt.nokia.com/\"><img src=\"images/qt-logo.png\" align=\"left\" width=\"32\" height=\"32\" border=\"0\" /></a>" \ + "</td>\n" \ + "<td width=\"1\"> </td>" \ + "<td class=\"postheader\" valign=\"center\">" \ + "<a href=\"index.html\">" \ + "<font color=\"#004faf\">Home</font></a> ·" \ + " <a href=\"classes.html\">" \ + "<font color=\"#004faf\">All Classes</font></a> ·" \ + " <a href=\"mainclasses.html\">" \ + "<font color=\"#004faf\">Main Classes</font></a> ·" \ + " <a href=\"groups.html\">" \ + "<font color=\"#004faf\">Grouped Classes</font></a> ·" \ + " <a href=\"modules.html\">" \ + "<font color=\"#004faf\">Modules</font></a> ·" \ + " <a href=\"functions.html\">" \ + "<font color=\"#004faf\">Functions</font></a>" \ + "</td>\n" \ + "<td align=\"right\" valign=\"top\" width=\"230\"><a href=\"http://qt.nokia.com\"><img src=\"images/qt-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%\" align=\"left\">Copyright © 2012 Digia Plc and/or its subsidiary(-ies)</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 Binary files differnew file mode 100644 index 0000000000..2dc67161c1 --- /dev/null +++ b/util/qlalr/doc/src/images/qt-logo.png diff --git a/util/qlalr/doc/src/qlalr.qdoc b/util/qlalr/doc/src/qlalr.qdoc new file mode 100644 index 0000000000..36cf27b3d9 --- /dev/null +++ b/util/qlalr/doc/src/qlalr.qdoc @@ -0,0 +1,106 @@ +/**************************************************************************** +** +** Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the documentation of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:FDL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** GNU Free Documentation License Usage +** Alternatively, this file may be used under the terms of the GNU Free +** Documentation License version 1.3 as published by the Free Software +** Foundation and appearing in the file included in the packaging of +** this file. Please review the following information to ensure +** the GNU Free Documentation License version 1.3 requirements +** will be met: http://www.gnu.org/copyleft/fdl.html. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +/*! + \page qlalr.html + \title qlalr + \nextpage qlalr - Writing Grammars + + \section1 Table of Contents + + \list + \li \l{qlalr - Writing Grammars} + \tableofcontents{1 qlalr - Writing Grammars} + \li \l{qlalr - Generating Code from Grammar Specifications} + \tableofcontents{1 qlalr - Generating Code from Grammar Specifications} + \li \l{qlalr - qlalr Grammar Specification} + \tableofcontents{1 qlalr - qlalr Grammar Specification} + \li \l{qlalr - Handling Conflicts} + \tableofcontents{1 qlalr - Handling Conflicts} + \li \l{qlalr - Error Handling and Recovery} + \tableofcontents{1 qlalr - Error Handling and Recovery} + \li \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..de3ff83112 --- /dev/null +++ b/util/qlalr/dotgraph.cpp @@ -0,0 +1,102 @@ +/**************************************************************************** +** +** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the utils of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $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..587817d4d2 --- /dev/null +++ b/util/qlalr/dotgraph.h @@ -0,0 +1,59 @@ +/**************************************************************************** +** +** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the utils of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $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..3d2a09c845 --- /dev/null +++ b/util/qlalr/examples/dummy-xml/ll/dummy-xml-ll.cpp @@ -0,0 +1,123 @@ +/**************************************************************************** +** +** Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the QLALR module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#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..a5d6b6e978 --- /dev/null +++ b/util/qlalr/examples/dummy-xml/xml.g @@ -0,0 +1,242 @@ +---------------------------------------------------------------------------- +-- +-- Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies). +-- Contact: http://www.qt-project.org/legal +-- +-- This file is part of the QtCore module of the Qt Toolkit. +-- +-- $QT_BEGIN_LICENSE:LGPL$ +-- Commercial License Usage +-- Licensees holding valid commercial Qt licenses may use this file in +-- accordance with the commercial license agreement provided with the +-- Software or, alternatively, in accordance with the terms contained in +-- a written agreement between you and Digia. For licensing terms and +-- conditions see http://qt.digia.com/licensing. For further information +-- use the contact form at http://qt.digia.com/contact-us. +-- +-- 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, Digia gives you certain additional +-- rights. These rights are described in the Digia Qt LGPL Exception +-- version 1.1, 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. +-- +-- +-- $QT_END_LICENSE$ +-- +---------------------------------------------------------------------------- + +%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..122431ba4e --- /dev/null +++ b/util/qlalr/examples/glsl/build.sh @@ -0,0 +1,47 @@ +#!/bin/sh +############################################################################# +## +## Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies). +## Contact: http://www.qt-project.org/legal +## +## This file is the build configuration utility of the Qt Toolkit. +## +## $QT_BEGIN_LICENSE:LGPL$ +## Commercial License Usage +## Licensees holding valid commercial Qt licenses may use this file in +## accordance with the commercial license agreement provided with the +## Software or, alternatively, in accordance with the terms contained in +## a written agreement between you and Digia. For licensing terms and +## conditions see http://qt.digia.com/licensing. For further information +## use the contact form at http://qt.digia.com/contact-us. +## +## 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, Digia gives you certain additional +## rights. These rights are described in the Digia Qt LGPL Exception +## version 1.1, 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. +## +## +## $QT_END_LICENSE$ +## +############################################################################# + +${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..16ff333b79 --- /dev/null +++ b/util/qlalr/examples/glsl/glsl-lex.l @@ -0,0 +1,245 @@ + +%{ +/**************************************************************************** +** +** Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the QLALR tool of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#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; } +"highp" { return HIGH_PRECISION; } +"mediump" { return MEDIUM_PRECISION; } +"lowp" { return LOW_PRECISION; } + +#[ \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..64b1b0b1e5 --- /dev/null +++ b/util/qlalr/examples/glsl/glsl.g @@ -0,0 +1,671 @@ +---------------------------------------------------------------------------- +-- +-- Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies). +-- Contact: http://www.qt-project.org/legal +-- +-- This file is part of the QtCore module of the Qt Toolkit. +-- +-- $QT_BEGIN_LICENSE:LGPL$ +-- Commercial License Usage +-- Licensees holding valid commercial Qt licenses may use this file in +-- accordance with the commercial license agreement provided with the +-- Software or, alternatively, in accordance with the terms contained in +-- a written agreement between you and Digia. For licensing terms and +-- conditions see http://qt.digia.com/licensing. For further information +-- use the contact form at http://qt.digia.com/contact-us. +-- +-- 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, Digia gives you certain additional +-- rights. These rights are described in the Digia Qt LGPL Exception +-- version 1.1, 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. +-- +-- +-- $QT_END_LICENSE$ +-- +---------------------------------------------------------------------------- + +%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 +%token HIGH_PRECISION +%token MEDIUM_PRECISION +%token LOW_PRECISION +%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*> (realloc(sym_stack, stack_size * sizeof(Value))); + state_stack = reinterpret_cast<int*> (realloc(state_stack, stack_size * sizeof(int))); +} + +:/ + + +/. + +GLSLParser::GLSLParser(): + tos(0), + stack_size(0), + sym_stack(0), + state_stack(0) +{ +} + +GLSLParser::~GLSLParser() +{ + if (stack_size) { + free(sym_stack); + free(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 ::= type_specifier_no_prec ; +type_specifier ::= precision_qualifier type_specifier_no_prec ; + +type_specifier_no_prec ::= VOID ; +type_specifier_no_prec ::= FLOAT ; +type_specifier_no_prec ::= INT ; +type_specifier_no_prec ::= BOOL ; +type_specifier_no_prec ::= VEC2 ; +type_specifier_no_prec ::= VEC3 ; +type_specifier_no_prec ::= VEC4 ; +type_specifier_no_prec ::= BVEC2 ; +type_specifier_no_prec ::= BVEC3 ; +type_specifier_no_prec ::= BVEC4 ; +type_specifier_no_prec ::= IVEC2 ; +type_specifier_no_prec ::= IVEC3 ; +type_specifier_no_prec ::= IVEC4 ; +type_specifier_no_prec ::= MAT2 ; +type_specifier_no_prec ::= MAT3 ; +type_specifier_no_prec ::= MAT4 ; +type_specifier_no_prec ::= SAMPLER1D ; +type_specifier_no_prec ::= SAMPLER2D ; +type_specifier_no_prec ::= SAMPLER3D ; +type_specifier_no_prec ::= SAMPLERCUBE ; +type_specifier_no_prec ::= SAMPLER1DSHADOW ; +type_specifier_no_prec ::= SAMPLER2DSHADOW ; +type_specifier_no_prec ::= struct_specifier ; +type_specifier_no_prec ::= TYPE_NAME ; + +precision_qualifier ::= HIGH_PRECISION ; +precision_qualifier ::= MEDIUM_PRECISION ; +precision_qualifier ::= LOW_PRECISION ; + +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..2d9ddd8ed4 --- /dev/null +++ b/util/qlalr/examples/lambda/lambda.g @@ -0,0 +1,81 @@ +---------------------------------------------------------------------------- +-- +-- Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies). +-- Contact: http://www.qt-project.org/legal +-- +-- This file is part of the QtCore module of the Qt Toolkit. +-- +-- $QT_BEGIN_LICENSE:LGPL$ +-- Commercial License Usage +-- Licensees holding valid commercial Qt licenses may use this file in +-- accordance with the commercial license agreement provided with the +-- Software or, alternatively, in accordance with the terms contained in +-- a written agreement between you and Digia. For licensing terms and +-- conditions see http://qt.digia.com/licensing. For further information +-- use the contact form at http://qt.digia.com/contact-us. +-- +-- 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, Digia gives you certain additional +-- rights. These rights are described in the Digia Qt LGPL Exception +-- version 1.1, 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. +-- +-- +-- $QT_END_LICENSE$ +-- +---------------------------------------------------------------------------- + +-- 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..6c45d48e69 --- /dev/null +++ b/util/qlalr/examples/lambda/main.cpp @@ -0,0 +1,199 @@ +/**************************************************************************** +** +** Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the QLALR module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#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..394b89c964 --- /dev/null +++ b/util/qlalr/examples/qparser/calc.g @@ -0,0 +1,133 @@ +---------------------------------------------------------------------------- +-- +-- Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies). +-- Contact: http://www.qt-project.org/legal +-- +-- This file is part of the QtCore module of the Qt Toolkit. +-- +-- $QT_BEGIN_LICENSE:LGPL$ +-- Commercial License Usage +-- Licensees holding valid commercial Qt licenses may use this file in +-- accordance with the commercial license agreement provided with the +-- Software or, alternatively, in accordance with the terms contained in +-- a written agreement between you and Digia. For licensing terms and +-- conditions see http://qt.digia.com/licensing. For further information +-- use the contact form at http://qt.digia.com/contact-us. +-- +-- 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, Digia gives you certain additional +-- rights. These rights are described in the Digia Qt LGPL Exception +-- version 1.1, 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. +-- +-- +-- $QT_END_LICENSE$ +-- +---------------------------------------------------------------------------- + +%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..eb666f1f7e --- /dev/null +++ b/util/qlalr/examples/qparser/calc.l @@ -0,0 +1,61 @@ + +%option noyywrap + +%{ +/**************************************************************************** +** +** Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the QLALR tool of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#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..d749467fe8 --- /dev/null +++ b/util/qlalr/examples/qparser/qparser.cpp @@ -0,0 +1,43 @@ +/**************************************************************************** +** +** Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the QLALR module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#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..a5678d0c33 --- /dev/null +++ b/util/qlalr/examples/qparser/qparser.h @@ -0,0 +1,152 @@ +/**************************************************************************** +** +** Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the QLALR module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#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..f1c32adb2d --- /dev/null +++ b/util/qlalr/grammar.cpp @@ -0,0 +1,127 @@ +/**************************************************************************** +** +** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +// This file was generated by qlalr - DO NOT EDIT! +#include "grammar_p.h" + +QT_BEGIN_NAMESPACE + +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 short 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 short 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 short 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 short 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 short 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 short 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 short 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}; + +QT_END_NAMESPACE diff --git a/util/qlalr/grammar_p.h b/util/qlalr/grammar_p.h new file mode 100644 index 0000000000..e2f294ea00 --- /dev/null +++ b/util/qlalr/grammar_p.h @@ -0,0 +1,131 @@ +/**************************************************************************** +** +** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of other Qt classes. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +// This file was generated by qlalr - DO NOT EDIT! +#ifndef GRAMMAR_P_H +#define GRAMMAR_P_H + +#include <QtCore/qglobal.h> + +QT_BEGIN_NAMESPACE + +class grammar +{ +public: + enum VariousConstants { + 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 short lhs []; + static const short rhs []; + static const short goto_default []; + static const short action_default []; + static const short action_index []; + static const short action_info []; + static const short action_check []; + + static inline int nt_action (int state, int nt) + { + const int yyn = action_index [GOTO_INDEX_OFFSET + state] + nt; + if (yyn < 0 || action_check [GOTO_CHECK_OFFSET + yyn] != nt) + return goto_default [nt]; + + return action_info [GOTO_INFO_OFFSET + yyn]; + } + + static inline int t_action (int state, int token) + { + const int yyn = action_index [state] + token; + + if (yyn < 0 || action_check [yyn] != token) + return - action_default [state]; + + return action_info [yyn]; + } +}; + + +QT_END_NAMESPACE +#endif // GRAMMAR_P_H + diff --git a/util/qlalr/lalr.cpp b/util/qlalr/lalr.cpp new file mode 100644 index 0000000000..6a14c0d701 --- /dev/null +++ b/util/qlalr/lalr.cpp @@ -0,0 +1,781 @@ +/**************************************************************************** +** +** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the utils of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $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; + + 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; + + 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..b744d7ea65 --- /dev/null +++ b/util/qlalr/lalr.g @@ -0,0 +1,800 @@ +----------------------------------------------------------------------------- +-- +-- Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). +-- Contact: http://www.qt-project.org/legal +-- +-- This file is part of the QLALR project on Qt Labs. +-- +-- $QT_BEGIN_LICENSE:LGPL$ +-- Commercial License Usage +-- Licensees holding valid commercial Qt licenses may use this file in +-- accordance with the commercial license agreement provided with the +-- Software or, alternatively, in accordance with the terms contained in +-- a written agreement between you and Digia. For licensing terms and +-- conditions see http://qt.digia.com/licensing. For further information +-- use the contact form at http://qt.digia.com/contact-us. +-- +-- 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, Digia gives you certain additional +-- rights. These rights are described in the Digia Qt LGPL Exception +-- version 1.1, 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. +-- +-- +-- $QT_END_LICENSE$ +-- +----------------------------------------------------------------------------- + + +%parser grammar + +%decl recognizer.h +%impl recognizer.cpp + +%token ID "identifier" +%token STRING_LITERAL "string literal" + +%token DECL_FILE "%decl" +%token EXPECT "%expect" +%token EXPECT_RR "%expect-lr" +%token IMPL_FILE "%impl" +%token LEFT "%left" +%token MERGED_OUTPUT "%merged_output" +%token NONASSOC "%nonassoc" +%token PARSER "%parser" +%token PREC "%prec" +%token RIGHT "%right" +%token START "%start" +%token TOKEN "%token" +%token TOKEN_PREFIX "%token_prefix" + +%token COLON ":" +%token OR "|" +%token SEMICOLON ";" + +%token DECL +%token IMPL + +%token ERROR + +%start Specification + + +/: +/**************************************************************************** +** +** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the QLALR project on Qt Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $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) 2013 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the QLALR project on Qt Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $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) + ::free(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*> (::malloc(stack_size * sizeof(int))); + else + state_stack = reinterpret_cast<int*> (::realloc(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..a4649d09b5 --- /dev/null +++ b/util/qlalr/lalr.h @@ -0,0 +1,502 @@ +/**************************************************************************** +** +** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the utils of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $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..203e4dec66 --- /dev/null +++ b/util/qlalr/main.cpp @@ -0,0 +1,185 @@ +/**************************************************************************** +** +** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the utils of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include <QtCore/QCoreApplication> +#include <QtCore/QFile> +#include <QtCore/QStringList> +#include <QtCore/QtDebug> + +#include <cstdlib> + +#include "lalr.h" +#include "dotgraph.h" +#include "parsetable.h" +#include "cppgenerator.h" +#include "recognizer.h" + +#define QLALR_NO_DEBUG_TABLE +#define QLALR_NO_DEBUG_DOT + +static void help_me () +{ + qerr << "Usage: qlalr [options] [input file name]" << endl + << endl + << " --help, -h\t\tdisplay this help and exit" << endl + << " --verbose, -v\t\tverbose output" << endl + << " --no-debug\t\tno debug information" << endl + << " --no-lines\t\tno #line directives" << endl + << " --dot\t\t\tgenerate a graph" << endl + << " --qt\t\tadd the Qt copyright header and Qt-specific types and macros" << endl + << endl; + exit (0); +} + +int main (int argc, char *argv[]) +{ + QCoreApplication app (argc, argv); + + bool generate_dot = false; + bool generate_report = false; + bool no_lines = false; + bool debug_info = true; + bool qt_copyright = false; + QString file_name = 0; + + QStringList args = app.arguments (); + args.removeFirst (); + + foreach (QString arg, args) + { + if (arg == QLatin1String ("-h") || arg == QLatin1String ("--help")) + help_me (); + + else if (arg == QLatin1String ("-v") || arg == QLatin1String ("--verbose")) + generate_report = true; + + else if (arg == QLatin1String ("--dot")) + generate_dot = true; + + else if (arg == QLatin1String ("--no-lines")) + no_lines = true; + + else if (arg == QLatin1String ("--no-debug")) + debug_info = false; + + else if (arg == QLatin1String ("--qt")) + qt_copyright = true; + + else if (file_name.isEmpty ()) + file_name = arg; + + else + qerr << "*** Warning. Ignore argument `" << arg << "'" << endl; + } + + if (file_name.isEmpty ()) + { + help_me (); + exit (EXIT_SUCCESS); + } + + Grammar grammar; + Recognizer p (&grammar, no_lines); + + if (! p.parse (file_name)) + exit (EXIT_FAILURE); + + if (grammar.rules.isEmpty ()) + { + qerr << "*** Fatal. No rules!" << endl; + exit (EXIT_FAILURE); + } + + else if (grammar.start == grammar.names.end ()) + { + qerr << "*** Fatal. No start symbol!" << endl; + exit (EXIT_FAILURE); + } + + grammar.buildExtendedGrammar (); + grammar.buildRuleMap (); + + Automaton aut (&grammar); + aut.build (); + + CppGenerator gen (p, grammar, aut, generate_report); + gen.setDebugInfo (debug_info); + gen.setCopyright (qt_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..25c7f8f8d6 --- /dev/null +++ b/util/qlalr/parsetable.cpp @@ -0,0 +1,127 @@ +/**************************************************************************** +** +** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the utils of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $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..75922ab16b --- /dev/null +++ b/util/qlalr/parsetable.h @@ -0,0 +1,59 @@ +/**************************************************************************** +** +** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the utils of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $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..4ebeb91e64 --- /dev/null +++ b/util/qlalr/qlalr.pro @@ -0,0 +1,25 @@ + +TEMPLATE = app +QT = core +CONFIG += console +TARGET = qlalr +mac:CONFIG -= app_bundle + +SOURCES += \ + compress.cpp \ + cppgenerator.cpp \ + dotgraph.cpp \ + lalr.cpp \ + main.cpp \ + parsetable.cpp \ + recognizer.cpp \ + grammar.cpp + +HEADERS += \ + compress.h \ + cppgenerator.h \ + dotgraph.h \ + lalr.h \ + parsetable.h \ + recognizer.h \ + grammar_p.h diff --git a/util/qlalr/recognizer.cpp b/util/qlalr/recognizer.cpp new file mode 100644 index 0000000000..d68d6fb78b --- /dev/null +++ b/util/qlalr/recognizer.cpp @@ -0,0 +1,489 @@ + +/**************************************************************************** +** +** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the QLALR project on Qt Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $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) + ::free(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*> (::malloc(stack_size * sizeof(int))); + else + state_stack = reinterpret_cast<int*> (::realloc(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..9c64fac043 --- /dev/null +++ b/util/qlalr/recognizer.h @@ -0,0 +1,112 @@ + +/**************************************************************************** +** +** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the QLALR project on Qt Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** 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, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, 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. +** +** +** $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; +}; |
