diff options
Diffstat (limited to 'util/qlalr')
42 files changed, 6439 insertions, 0 deletions
diff --git a/util/qlalr/.gitignore b/util/qlalr/.gitignore new file mode 100644 index 0000000..ce75745 --- /dev/null +++ b/util/qlalr/.gitignore @@ -0,0 +1 @@ +qlalr diff --git a/util/qlalr/README b/util/qlalr/README new file mode 100644 index 0000000..b186fa1 --- /dev/null +++ b/util/qlalr/README @@ -0,0 +1 @@ +qlalr is used to generate parsers for QXmlStream and QtScript. diff --git a/util/qlalr/compress.cpp b/util/qlalr/compress.cpp new file mode 100644 index 0000000..f1daac8 --- /dev/null +++ b/util/qlalr/compress.cpp @@ -0,0 +1,286 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QLALR project on Trolltech Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + + +#include <QtCore/QtDebug> +#include <QtCore/QList> + +#include <algorithm> +#include <iterator> +#include <iostream> +#include "compress.h" + +#define QLALR_NO_CHECK_SORTED_TABLE + +struct _Fit: public std::binary_function<int, int, bool> +{ + inline bool operator () (int a, int b) const + { + return a == 0 || b == 0 || a == b; + } +}; + +struct _PerfectMatch: public std::binary_function<int, int, bool> +{ + inline bool operator () (int a, int b) const + { return a == b; } +}; + +struct _GenerateCheck +{ + QVector<int>::const_iterator iterator; + int initial; + + _GenerateCheck (QVector<int>::const_iterator it, int i): + iterator (it), + initial (i) {} + + inline int operator () () + { + int check = initial++; + return *iterator++ ? check : -1; + } +}; + +class UncompressedRow +{ +public: + typedef const int *const_iterator; + typedef const int *iterator; + +public: + inline UncompressedRow (): + _M_index (0), + _M_begin (0), + _M_end (0), + _M_beginNonZeros (0), + _M_endNonZeros (0) {} + + inline UncompressedRow (int index, const_iterator begin, const_iterator end) + { assign (index, begin, end); } + + inline int index () const { return _M_index; } + inline const_iterator begin () const { return _M_begin; } + inline const_iterator end () const { return _M_end; } + + inline void assign (int index, const_iterator begin, const_iterator end) + { + _M_index = index; + _M_begin = begin; + _M_end = end; + + _M_beginNonZeros = _M_begin; + _M_endNonZeros = _M_end; + + for (_M_beginNonZeros = _M_begin; _M_beginNonZeros != _M_end && ! _M_beginNonZeros [0]; ++_M_beginNonZeros) + /*continue*/ ; + +#if 0 + for (_M_endNonZeros = _M_end; _M_endNonZeros != _M_beginNonZeros && ! _M_endNonZeros [-1]; --_M_endNonZeros) + /*continue*/ ; +#endif + } + + inline int at (int index) const + { return _M_begin [index]; } + + inline bool isEmpty () const + { return _M_begin == _M_end; } + + inline int size () const + { return _M_end - _M_begin; } + + inline int nonZeroElements () const + { return _M_endNonZeros - _M_beginNonZeros; } + + inline int count (int value) const + { return std::count (begin (), end (), value); } + + inline const_iterator beginNonZeros () const + { return _M_beginNonZeros; } + + inline const_iterator endNonZeros () const + { return _M_endNonZeros; } + +private: + int _M_index; + const_iterator _M_begin; + const_iterator _M_end; + const_iterator _M_beginNonZeros; + const_iterator _M_endNonZeros; +}; + +struct _SortUncompressedRow: public std::binary_function<UncompressedRow, UncompressedRow, bool> +{ + inline bool operator () (const UncompressedRow &a, const UncompressedRow &b) const + { return a.count (0) > b.count (0); } +}; + +Compress::Compress () +{ +} + +void Compress::operator () (int *table, int row_count, int column_count) +{ + index.clear (); + info.clear (); + check.clear (); + + QVector<UncompressedRow> sortedTable (row_count); + + for (int i = 0; i < row_count; ++i) + { + int *begin = &table [i * column_count]; + int *end = begin + column_count; + + sortedTable [i].assign (i, begin, end); + } + + qSort (sortedTable.begin (), sortedTable.end (), _SortUncompressedRow ()); + +#ifndef QLALR_NO_CHECK_SORTED_TABLE + int previous_zeros = INT_MAX; + + foreach (UncompressedRow row, sortedTable) + { + int zeros = row.count (0); + + Q_ASSERT (zeros <= previous_zeros); + zeros = previous_zeros; + qDebug () << "OK!"; + } +#endif + + index.fill (-999999, row_count); + + foreach (UncompressedRow row, sortedTable) + { + int first_token = std::distance (row.begin (), row.beginNonZeros ()); + QVector<int>::iterator pos = info.begin (); + + while (pos != info.end ()) + { + if (pos == info.begin ()) + { + // try to find a perfect match + QVector<int>::iterator pm = std::search (pos, info.end (), row.beginNonZeros (), row.endNonZeros (), _PerfectMatch ()); + + if (pm != info.end ()) + { + pos = pm; + break; + } + } + + pos = std::search (pos, info.end (), row.beginNonZeros (), row.endNonZeros (), _Fit ()); + + if (pos == info.end ()) + break; + + int idx = std::distance (info.begin (), pos) - first_token; + bool conflict = false; + + for (int j = 0; ! conflict && j < row.size (); ++j) + { + if (row.at (j) == 0) + conflict |= idx + j >= 0 && check [idx + j] == j; + + else + conflict |= check [idx + j] == j; + } + + if (! conflict) + break; + + ++pos; + } + + if (pos == info.end ()) + { + int size = info.size (); + + info.resize (info.size () + row.nonZeroElements ()); + check.resize (info.size ()); + + std::fill (check.begin () + size, check.end (), -1); + pos = info.begin () + size; + } + + int offset = std::distance (info.begin (), pos); + index [row.index ()] = offset - first_token; + + for (const int *it = row.beginNonZeros (); it != row.endNonZeros (); ++it, ++pos) + { + if (*it) + *pos = *it; + } + + int i = row.index (); + + for (int j = 0; j < row.size (); ++j) + { + if (row.at (j) == 0) + continue; + + check [index [i] + j] = j; + } + } + +#if 0 + foreach (UncompressedRow row, sortedTable) + { + int i = row.index (); + Q_ASSERT (i < sortedTable.size ()); + + for (int j = 0; j < row.size (); ++j) + { + if (row.at (j) == 0) + { + Q_ASSERT (index [i] + j < 0 || check [index [i] + j] != j); + continue; + } + + Q_ASSERT ( info [index [i] + j] == row.at (j)); + Q_ASSERT (check [index [i] + j] == j); + } + } +#endif +} diff --git a/util/qlalr/compress.h b/util/qlalr/compress.h new file mode 100644 index 0000000..8b7ac60 --- /dev/null +++ b/util/qlalr/compress.h @@ -0,0 +1,60 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QLALR project on Trolltech Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef COMPRESS_H +#define COMPRESS_H + +#include <QtCore/QVector> + +class Compress +{ +public: + Compress (); + + void operator () (int *table, int row_count, int column_count); + +public: + QVector<int> index; + QVector<int> info; + QVector<int> check; +}; + +#endif // COMPRESS_H diff --git a/util/qlalr/cppgenerator.cpp b/util/qlalr/cppgenerator.cpp new file mode 100644 index 0000000..9bfc1a9 --- /dev/null +++ b/util/qlalr/cppgenerator.cpp @@ -0,0 +1,703 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QLALR project on Trolltech Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + + +#include <QtCore/QtCore> + +#include "cppgenerator.h" +#include "lalr.h" +#include "recognizer.h" + +QString CppGenerator::trollCopyrightHeader() const +{ + return QLatin1String( + "/****************************************************************************\n" + "**\n" + "** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).\n" + "**\n" + "** This file is part of the $MODULE$ of the Qt Toolkit.\n" + "**\n" + "** $TROLLTECH_DUAL_LICENSE$\n" + "**\n" + "** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE\n" + "** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.\n" + "**\n" + "****************************************************************************/\n" + "\n"); +} + +QString CppGenerator::trollPrivateCopyrightHeader() const +{ + return QLatin1String( + "//\n" + "// W A R N I N G\n" + "// -------------\n" + "//\n" + "// This file is not part of the Qt API. It exists for the convenience\n" + "// of other Qt classes. This header file may change from version to\n" + "// version without notice, or even be removed.\n" + "//\n" + "// We mean it.\n" + "//\n"); +} + +QString CppGenerator::startIncludeGuard(const QString &fileName) +{ + const QString normalized(QString(fileName).replace(QLatin1Char('.'), QLatin1Char('_')).toUpper()); + + return QString::fromLatin1("#ifndef %1\n" + "#define %2\n").arg(normalized, normalized); +} + +QString CppGenerator::endIncludeGuard(const QString &fileName) +{ + const QString normalized(QString(fileName).replace(QLatin1Char('.'), QLatin1Char('_')).toUpper()); + + return QString::fromLatin1("#endif // %1\n").arg(normalized); +} + +void CppGenerator::operator () () +{ + // action table... + state_count = aut.states.size (); + terminal_count = grammar.terminals.size (); + non_terminal_count = grammar.non_terminals.size (); + +#define ACTION(i, j) table [(i) * terminal_count + (j)] +#define GOTO(i, j) pgoto [(i) * non_terminal_count + (j)] + + int *table = new int [state_count * terminal_count]; + ::memset (table, 0, state_count * terminal_count * sizeof (int)); + + int *pgoto = new int [state_count * non_terminal_count]; + ::memset (pgoto, 0, state_count * non_terminal_count * sizeof (int)); + + accept_state = -1; + int shift_reduce_conflict_count = 0; + int reduce_reduce_conflict_count = 0; + + for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state) + { + int q = aut.id (state); + + for (Bundle::iterator a = state->bundle.begin (); a != state->bundle.end (); ++a) + { + int symbol = aut.id (a.key ()); + int r = aut.id (a.value ()); + + Q_ASSERT (r < state_count); + + if (grammar.isNonTerminal (a.key ())) + { + Q_ASSERT (symbol >= terminal_count && symbol < grammar.names.size ()); + GOTO (q, symbol - terminal_count) = r; + } + + else + ACTION (q, symbol) = r; + } + + for (ItemPointer item = state->closure.begin (); item != state->closure.end (); ++item) + { + if (item->dot != item->end_rhs ()) + continue; + + int r = aut.id (item->rule); + + NameSet lookaheads = aut.lookaheads.value (item); + + if (item->rule == grammar.goal) + accept_state = q; + + foreach (Name s, lookaheads) + { + int &u = ACTION (q, aut.id (s)); + + if (u == 0) + u = - r; + + else if (u < 0) + { + if (verbose) + qout << "*** Warning. Found a reduce/reduce conflict in state " << q << " on token ``" << s << "'' between rule " + << r << " and " << -u << endl; + + ++reduce_reduce_conflict_count; + + u = qMax (u, -r); + + if (verbose) + qout << "\tresolved using rule " << -u << endl; + } + + else if (u > 0) + { + if (item->rule->prec != grammar.names.end() && grammar.token_info.contains (s)) + { + Grammar::TokenInfo info_r = grammar.token_info.value (item->rule->prec); + Grammar::TokenInfo info_s = grammar.token_info.value (s); + + if (info_r.prec > info_s.prec) + u = -r; + else if (info_r.prec == info_s.prec) + { + switch (info_r.assoc) { + case Grammar::Left: + u = -r; + break; + case Grammar::Right: + // shift... nothing to do + break; + case Grammar::NonAssoc: + u = 0; + break; + } // switch + } + } + + else + { + ++shift_reduce_conflict_count; + + if (verbose) + qout << "*** Warning. Found a shift/reduce conflict in state " << q << " on token ``" << s << "'' with rule " << r << endl; + } + } + } + } + } + + if (shift_reduce_conflict_count || reduce_reduce_conflict_count) + { + if (shift_reduce_conflict_count != grammar.expected_shift_reduce + || reduce_reduce_conflict_count != grammar.expected_reduce_reduce) + qerr << "*** Conflicts: " << shift_reduce_conflict_count << " shift/reduce, " << reduce_reduce_conflict_count << " reduce/reduce" << endl; + + if (verbose) + qout << endl << "*** Conflicts: " << shift_reduce_conflict_count << " shift/reduce, " << reduce_reduce_conflict_count << " reduce/reduce" << endl + << endl; + } + + QBitArray used_rules (grammar.rules.count ()); + + int q = 0; + for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state, ++q) + { + for (int j = 0; j < terminal_count; ++j) + { + int &u = ACTION (q, j); + + if (u < 0) + used_rules.setBit (-u - 1); + } + } + + for (int i = 0; i < used_rules.count (); ++i) + { + if (! used_rules.testBit (i)) + { + RulePointer rule = grammar.rules.begin () + i; + + if (rule != grammar.goal) + qerr << "*** Warning: Rule ``" << *rule << "'' is useless!" << endl; + } + } + + q = 0; + for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state, ++q) + { + for (int j = 0; j < terminal_count; ++j) + { + int &u = ACTION (q, j); + + if (u >= 0) + continue; + + RulePointer rule = grammar.rules.begin () + (- u - 1); + + if (state->defaultReduce == rule) + u = 0; + } + } + + // ... compress the goto table + defgoto.resize (non_terminal_count); + for (int j = 0; j < non_terminal_count; ++j) + { + count.fill (0, state_count); + + int &mx = defgoto [j]; + + for (int i = 0; i < state_count; ++i) + { + int r = GOTO (i, j); + + if (! r) + continue; + + ++count [r]; + + if (count [r] > count [mx]) + mx = r; + } + } + + for (int i = 0; i < state_count; ++i) + { + for (int j = 0; j < non_terminal_count; ++j) + { + int &r = GOTO (i, j); + + if (r == defgoto [j]) + r = 0; + } + } + + compressed_action (table, state_count, terminal_count); + compressed_goto (pgoto, state_count, non_terminal_count); + + delete[] table; + table = 0; + + delete[] pgoto; + pgoto = 0; + +#undef ACTION +#undef GOTO + + if (! grammar.merged_output.isEmpty()) + { + QFile f(grammar.merged_output); + if (! f.open (QFile::WriteOnly)) + { + fprintf (stderr, "*** cannot create %s\n", qPrintable(grammar.merged_output)); + return; + } + + QTextStream out (&f); + out << "// This file was generated by qlalr - DO NOT EDIT!\n"; + + if (troll_copyright) + { + out << trollCopyrightHeader() + << trollPrivateCopyrightHeader() + << endl; + } + + out << startIncludeGuard(grammar.merged_output) << endl; + + generateDecl (out); + generateImpl (out); + out << p.decls(); + out << p.impls(); + out << endl; + + out << endIncludeGuard(grammar.merged_output) << endl; + + return; + } + + // default behaviour + QString declFileName = grammar.table_name.toLower () + QLatin1String("_p.h"); + QString bitsFileName = grammar.table_name.toLower () + QLatin1String(".cpp"); + + { // decls... + QFile f (declFileName); + f.open (QFile::WriteOnly); + QTextStream out (&f); + out << "// This file was generated by qlalr - DO NOT EDIT!\n"; + + QString prot = declFileName.toUpper ().replace (QLatin1Char ('.'), QLatin1Char ('_')); + + if (troll_copyright) + { + out << trollCopyrightHeader() + << trollPrivateCopyrightHeader() + << endl; + } + + out << "#ifndef " << prot << endl + << "#define " << prot << endl + << endl; + + generateDecl (out); + + out << "#endif // " << prot << endl << endl; + } // end decls + + { // bits... + QFile f (bitsFileName); + f.open (QFile::WriteOnly); + QTextStream out (&f); + out << "// This file was generated by qlalr - DO NOT EDIT!\n"; + + if (troll_copyright) + out << trollCopyrightHeader(); + + out << "#include \"" << declFileName << "\"" << endl << endl; + generateImpl(out); + + } // end bits + + if (! grammar.decl_file_name.isEmpty ()) + { + QFile f (grammar.decl_file_name); + f.open (QFile::WriteOnly); + QTextStream out (&f); + out << "// This file was generated by qlalr - DO NOT EDIT!\n"; + out << p.decls(); + } + + if (! grammar.impl_file_name.isEmpty ()) + { + QFile f (grammar.impl_file_name); + f.open (QFile::WriteOnly); + QTextStream out (&f); + out << "// This file was generated by qlalr - DO NOT EDIT!\n"; + out << p.impls(); + } +} + +QString CppGenerator::debugInfoProt() const +{ + QString prot = QLatin1String("QLALR_NO_"); + prot += grammar.table_name.toUpper(); + prot += QLatin1String("_DEBUG_INFO"); + return prot; +} + +void CppGenerator::generateDecl (QTextStream &out) +{ + out << "class " << grammar.table_name << endl + << "{" << endl + << "public:" << endl + << " enum {" << endl; + + foreach (Name t, grammar.terminals) + { + QString name = *t; + int value = std::distance (grammar.names.begin (), t); + + if (name == QLatin1String ("$end")) + name = QLatin1String ("EOF_SYMBOL"); + + else if (name == QLatin1String ("$accept")) + name = QLatin1String ("ACCEPT_SYMBOL"); + + else + name.prepend (grammar.token_prefix); + + out << " " << name << " = " << value << "," << endl; + } + + out << endl + << " ACCEPT_STATE = " << accept_state << "," << endl + << " RULE_COUNT = " << grammar.rules.size () << "," << endl + << " STATE_COUNT = " << state_count << "," << endl + << " TERMINAL_COUNT = " << terminal_count << "," << endl + << " NON_TERMINAL_COUNT = " << non_terminal_count << "," << endl + << endl + << " GOTO_INDEX_OFFSET = " << compressed_action.index.size () << "," << endl + << " GOTO_INFO_OFFSET = " << compressed_action.info.size () << "," << endl + << " GOTO_CHECK_OFFSET = " << compressed_action.check.size () << endl + << " };" << endl + << endl + << " static const char *const spell [];" << endl + << " static const int lhs [];" << endl + << " static const int rhs [];" << endl; + + if (debug_info) + { + QString prot = debugInfoProt(); + + out << endl << "#ifndef " << prot << endl + << " static const int rule_index [];" << endl + << " static const int rule_info [];" << endl + << "#endif // " << prot << endl << endl; + } + + out << " static const int goto_default [];" << endl + << " static const int action_default [];" << endl + << " static const int action_index [];" << endl + << " static const int action_info [];" << endl + << " static const int action_check [];" << endl + << endl + << " static inline int nt_action (int state, int nt)" << endl + << " {" << endl + << " const int *const goto_index = &action_index [GOTO_INDEX_OFFSET];" << endl + << " const int *const goto_check = &action_check [GOTO_CHECK_OFFSET];" << endl + << endl + << " const int yyn = goto_index [state] + nt;" << endl + << endl + << " if (yyn < 0 || goto_check [yyn] != nt)" << endl + << " return goto_default [nt];" << endl + << endl + << " const int *const goto_info = &action_info [GOTO_INFO_OFFSET];" << endl + << " return goto_info [yyn];" << endl + << " }" << endl + << endl + << " static inline int t_action (int state, int token)" << endl + << " {" << endl + << " const int yyn = action_index [state] + token;" << endl + << endl + << " if (yyn < 0 || action_check [yyn] != token)" << endl + << " return - action_default [state];" << endl + << endl + << " return action_info [yyn];" << endl + << " }" << endl + << "};" << endl + << endl + << endl; +} + +void CppGenerator::generateImpl (QTextStream &out) +{ + int idx = 0; + + out << "const char *const " << grammar.table_name << "::spell [] = {"; + idx = 0; + + QMap<Name, int> name_ids; + bool first_nt = true; + + for (Name t = grammar.names.begin (); t != grammar.names.end (); ++t, ++idx) + { + bool terminal = grammar.isTerminal (t); + + if (! (debug_info || terminal)) + break; + + name_ids.insert (t, idx); + + if (idx) + out << ", "; + + if (! (idx % 10)) + out << endl << " "; + + if (terminal) + { + QString spell = grammar.spells.value (t); + + if (spell.isEmpty ()) + out << "0"; + else + out << "\"" << spell << "\""; + } + else + { + if (first_nt) + { + first_nt = false; + QString prot = debugInfoProt(); + out << endl << "#ifndef " << prot << endl; + } + out << "\"" << *t << "\""; + } + } + + if (debug_info) + out << endl << "#endif // " << debugInfoProt() << endl; + + out << "};" << endl << endl; + + out << "const int " << grammar.table_name << "::lhs [] = {"; + idx = 0; + for (RulePointer rule = grammar.rules.begin (); rule != grammar.rules.end (); ++rule, ++idx) + { + if (idx) + out << ", "; + + if (! (idx % 10)) + out << endl << " "; + + out << aut.id (rule->lhs); + } + out << "};" << endl << endl; + + out << "const int " << grammar.table_name << ":: rhs[] = {"; + idx = 0; + for (RulePointer rule = grammar.rules.begin (); rule != grammar.rules.end (); ++rule, ++idx) + { + if (idx) + out << ", "; + + if (! (idx % 10)) + out << endl << " "; + + out << rule->rhs.size (); + } + out << "};" << endl << endl; + + if (debug_info) + { + QString prot = debugInfoProt(); + + out << endl << "#ifndef " << prot << endl; + out << "const int " << grammar.table_name << "::rule_info [] = {"; + idx = 0; + for (RulePointer rule = grammar.rules.begin (); rule != grammar.rules.end (); ++rule, ++idx) + { + out << endl << " "; + + if (idx) + out << ", "; + else + out << " "; + + out << name_ids.value(rule->lhs); + + foreach (Name n, rule->rhs) + out << ", " << name_ids.value (n); + } + out << "};" << endl << endl; + + out << "const int " << grammar.table_name << "::rule_index [] = {"; + idx = 0; + int offset = 0; + for (RulePointer rule = grammar.rules.begin (); rule != grammar.rules.end (); ++rule, ++idx) + { + if (idx) + out << ", "; + + if (! (idx % 10)) + out << endl << " "; + + out << offset; + offset += rule->rhs.size () + 1; + } + out << "};" << endl + << "#endif // " << prot << endl << endl; + } + + out << "const int " << grammar.table_name << "::action_default [] = {"; + idx = 0; + for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state, ++idx) + { + if (state != aut.states.begin ()) + out << ", "; + + if (! (idx % 10)) + out << endl << " "; + + if (state->defaultReduce != grammar.rules.end ()) + out << aut.id (state->defaultReduce); + else + out << "0"; + } + out << "};" << endl << endl; + + out << "const int " << grammar.table_name << "::goto_default [] = {"; + for (int i = 0; i < defgoto.size (); ++i) + { + if (i) + out << ", "; + + if (! (i % 10)) + out << endl << " "; + + out << defgoto [i]; + } + out << "};" << endl << endl; + + out << "const int " << grammar.table_name << "::action_index [] = {"; + for (int i = 0; i < compressed_action.index.size (); ++i) + { + if (! (i % 10)) + out << endl << " "; + + out << compressed_action.index [i] << ", "; + } + out << endl; + for (int i = 0; i < compressed_goto.index.size (); ++i) + { + if (i) + out << ", "; + + if (! (i % 10)) + out << endl << " "; + + out << compressed_goto.index [i]; + } + out << "};" << endl << endl; + + out << "const int " << grammar.table_name << "::action_info [] = {"; + for (int i = 0; i < compressed_action.info.size (); ++i) + { + if (! (i % 10)) + out << endl << " "; + + out << compressed_action.info [i] << ", "; + } + out << endl; + for (int i = 0; i < compressed_goto.info.size (); ++i) + { + if (i) + out << ", "; + + if (! (i % 10)) + out << endl << " "; + + out << compressed_goto.info [i]; + } + out << "};" << endl << endl; + + out << "const int " << grammar.table_name << "::action_check [] = {"; + for (int i = 0; i < compressed_action.check.size (); ++i) + { + if (! (i % 10)) + out << endl << " "; + + out << compressed_action.check [i] << ", "; + } + out << endl; + for (int i = 0; i < compressed_goto.check.size (); ++i) + { + if (i) + out << ", "; + + if (! (i % 10)) + out << endl << " "; + + out << compressed_goto.check [i]; + } + out << "};" << endl << endl; +} diff --git a/util/qlalr/cppgenerator.h b/util/qlalr/cppgenerator.h new file mode 100644 index 0000000..dd32413 --- /dev/null +++ b/util/qlalr/cppgenerator.h @@ -0,0 +1,99 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QLALR project on Trolltech Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef CPPGENERATOR_H +#define CPPGENERATOR_H + +#include "lalr.h" +#include "compress.h" + +class Grammar; +class Automaton; +class Recognizer; + +class CppGenerator +{ +public: + CppGenerator(const Recognizer &p, Grammar &grammar, Automaton &aut, bool verbose): + p (p), + grammar (grammar), + aut (aut), + verbose (verbose), + debug_info (false), + troll_copyright (false) {} + + void operator () (); + + bool debugInfo () const { return debug_info; } + void setDebugInfo (bool d) { debug_info = d; } + + bool trollCopyright () const { return troll_copyright; } + void setTrollCopyright (bool t) { troll_copyright = t; } + +private: + void generateDecl (QTextStream &out); + void generateImpl (QTextStream &out); + + QString debugInfoProt() const; + QString trollCopyrightHeader() const; + QString trollPrivateCopyrightHeader() const; + +private: + static QString startIncludeGuard(const QString &fileName); + static QString endIncludeGuard(const QString &fileName); + + const Recognizer &p; + Grammar &grammar; + Automaton &aut; + bool verbose; + int accept_state; + int state_count; + int terminal_count; + int non_terminal_count; + bool debug_info; + bool troll_copyright; + Compress compressed_action; + Compress compressed_goto; + QVector<int> count; + QVector<int> defgoto; +}; + +#endif // CPPGENERATOR_H diff --git a/util/qlalr/doc/qlalr.qdocconf b/util/qlalr/doc/qlalr.qdocconf new file mode 100644 index 0000000..d97ff7d --- /dev/null +++ b/util/qlalr/doc/qlalr.qdocconf @@ -0,0 +1,65 @@ +# Run qdoc from the directory that contains this file. + +project = qlalr +description = qlalr Reference Documentation +url = http://doc.trolltech.com/ + +language = Cpp + +# sourcedirs = $PWD/src +sourcedirs = src +sources.fileextensions = "*.qdoc" + +exampledirs = ../examples + +imagedirs = src/images +outputdir = html +codeindent = 1 +extraimages.HTML = qt-logo \ + trolltech-logo + +macro.key = "\\bold" +macro.menu = "\\bold" +macro.gui = "\\bold" +macro.reg.HTML = "<sup>®</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://qtsoftware.com/products/qt\"><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://qtsoftware.com\"><img src=\"images/trolltech-logo.png\" align=\"right\" width=\"203\" height=\"32\" border=\"0\" /></a></td></tr></table>" + +HTML.footer = "<p /><address><hr /><div align=\"center\">\n" \ + "<table width=\"100%\" cellspacing=\"0\" border=\"0\"><tr class=\"address\">\n" \ + "<td width=\"30%\">Copyright © \$THISYEAR\$ <a href=\"trolltech.html\">Trolltech</a></td>\n" \ + "<td width=\"40%\" align=\"center\"><a href=\"trademarks.html\">Trademarks</a></td>\n" \ + "<td width=\"30%\" align=\"right\"><div align=\"right\">Qt \\version</div></td>\n" \ + "</tr></table></div></address>" diff --git a/util/qlalr/doc/src/classic.css b/util/qlalr/doc/src/classic.css new file mode 100644 index 0000000..afc66d5 --- /dev/null +++ b/util/qlalr/doc/src/classic.css @@ -0,0 +1,97 @@ +h3.fn,span.fn +{ + margin-left: 1cm; + text-indent: -1cm; +} + +a:link +{ + color: #004faf; + text-decoration: none +} + +a:visited +{ + color: #672967; + text-decoration: none +} + +td.postheader +{ + font-family: sans-serif +} + +tr.address +{ + font-family: sans-serif +} + +body +{ + background: #ffffff; + color: black +} + +table tr.odd { + background: #f0f0f0; + color: black; +} + +table tr.even { + background: #e4e4e4; + color: black; +} + +table.annotated { + border-spacing: 0px; +} + +table.annotated th { + font-weight: bold; + padding: 3px; + text-align: left +} + +table.annotated td { + padding: 3px; +} + +table tr pre +{ + padding-top: none; + padding-bottom: none; + padding-left: none; + padding-right: none; + border: none; + background: none +} + +tr.qt-style +{ + background: #a2c511; + color: black +} + +body pre +{ + padding: 0.2em; + border: #e7e7e7 1px solid; + background: #f1f1f1; + color: black +} + +span.preprocessor, span.preprocessor a +{ + color: darkblue; +} + +span.comment +{ + color: darkred; + font-style: italic +} + +span.string,span.char +{ + color: darkgreen; +} diff --git a/util/qlalr/doc/src/images/qt-logo.png b/util/qlalr/doc/src/images/qt-logo.png Binary files differnew file mode 100644 index 0000000..2dc6716 --- /dev/null +++ b/util/qlalr/doc/src/images/qt-logo.png diff --git a/util/qlalr/doc/src/images/trolltech-logo.png b/util/qlalr/doc/src/images/trolltech-logo.png Binary files differnew file mode 100644 index 0000000..19e3789 --- /dev/null +++ b/util/qlalr/doc/src/images/trolltech-logo.png diff --git a/util/qlalr/doc/src/qlalr.qdoc b/util/qlalr/doc/src/qlalr.qdoc new file mode 100644 index 0000000..313c7a4 --- /dev/null +++ b/util/qlalr/doc/src/qlalr.qdoc @@ -0,0 +1,79 @@ +/*! + \page qlalr.html + \title qlalr + \nextpage qlalr - Writing Grammars + + \section1 Table of Contents + + \list + \o \l{qlalr - Writing Grammars} + \tableofcontents{1 qlalr - Writing Grammars} + \o \l{qlalr - Generating Code from Grammar Specifications} + \tableofcontents{1 qlalr - Generating Code from Grammar Specifications} + \o \l{qlalr - qlalr Grammar Specification} + \tableofcontents{1 qlalr - qlalr Grammar Specification} + \o \l{qlalr - Handling Conflicts} + \tableofcontents{1 qlalr - Handling Conflicts} + \o \l{qlalr - Error Handling and Recovery} + \tableofcontents{1 qlalr - Error Handling and Recovery} + \o \l{qlalr - References to External Information} + \tableofcontents{1 qlalr - References to External Information} + \endlist + +*/ + +/*! + \page qlalr-files.html + \title qlalr - Writing Grammars + + \contentspage qlalr + \previouspage qlalr + \nextpage qlalr - Generating Code from Grammar Specifications + +*/ + +/*! + \page qlalr-generating.html + \title qlalr - Generating Code from Grammar Specifications + + \contentspage qlalr + \previouspage qlalr - Writing Grammars + \nextpage qlalr - qlalr Grammar Specification +*/ + +/*! + \page qlalr-grammar-specification.html + \title qlalr - qlalr Grammar Specification + + \contentspage qlalr + \previouspage qlalr - Generating Code from Grammar Specifications + \nextpage qlalr - Handling Conflicts + +*/ + +/*! + \page qlalr-handling-conflicts.html + \title qlalr - Handling Conflicts + + \contentspage qlalr + \previouspage qlalr - qlalr Grammar Specification + \nextpage qlalr - Error Handling and Recovery +*/ + +/*! + \page qlalr-handling-errors.html + \title qlalr - Error Handling and Recovery + + \contentspage qlalr + \previouspage qlalr - Handling Conflicts + \nextpage qlalr - References to External Information +*/ + +/*! + \page qlalr-external-references.html + \title qlalr - References to External Information + + \contentspage qlalr + \previouspage qlalr - Error Handling and Recovery +*/ + diff --git a/util/qlalr/dotgraph.cpp b/util/qlalr/dotgraph.cpp new file mode 100644 index 0000000..641ed01 --- /dev/null +++ b/util/qlalr/dotgraph.cpp @@ -0,0 +1,102 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QLALR project on Trolltech Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + + +#include <QtCore/QTextStream> + +#include "lalr.h" +#include "dotgraph.h" + +DotGraph::DotGraph(QTextStream &o): + out (o) +{ +} + +void DotGraph::operator () (Automaton *aut) +{ + Grammar *g = aut->_M_grammar; + + out << "digraph {" << endl << endl; + + out << "subgraph Includes {" << endl; + for (Automaton::IncludesGraph::iterator incl = Automaton::IncludesGraph::begin_nodes (); + incl != Automaton::IncludesGraph::end_nodes (); ++incl) + { + for (Automaton::IncludesGraph::edge_iterator edge = incl->begin (); edge != incl->end (); ++edge) + { + out << "\t\"(" << aut->id (incl->data.state) << ", " << incl->data.nt << ")\""; + out << "\t->\t"; + out << "\"(" << aut->id ((*edge)->data.state) << ", " << (*edge)->data.nt << ")\"\t"; + out << "[label=\"" << incl->data.state->follows [incl->data.nt] << "\"]"; + out << endl; + } + } + out << "}" << endl << endl; + + + out << "subgraph LRA {" << endl; + //out << "node [shape=record];" << endl << endl; + + for (StatePointer q = aut->states.begin (); q != aut->states.end (); ++q) + { + int state = aut->id (q); + + out << "\t" << state << "\t[shape=record,label=\"{"; + + out << "<0> State " << state; + + int index = 1; + for (ItemPointer item = q->kernel.begin (); item != q->kernel.end (); ++item) + out << "| <" << index++ << "> " << *item; + + out << "}\"]" << endl; + + for (Bundle::iterator a = q->bundle.begin (); a != q->bundle.end (); ++a) + { + const char *clr = g->isTerminal (a.key ()) ? "blue" : "red"; + out << "\t" << state << "\t->\t" << aut->id (*a) << "\t[color=\"" << clr << "\",label=\"" << a.key () << "\"]" << endl; + } + out << endl; + } + + out << "}" << endl; + out << endl << endl << "}" << endl; +} diff --git a/util/qlalr/dotgraph.h b/util/qlalr/dotgraph.h new file mode 100644 index 0000000..e308b74 --- /dev/null +++ b/util/qlalr/dotgraph.h @@ -0,0 +1,59 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QLALR project on Trolltech Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef DOTGRAPH_H +#define DOTGRAPH_H + +QT_FORWARD_DECLARE_CLASS(QTextStream); +class Automaton; + +class DotGraph +{ +public: + DotGraph (QTextStream &out); + + void operator () (Automaton *a); + +private: + QTextStream &out; +}; + +#endif // DOTGRAPH_H diff --git a/util/qlalr/examples/dummy-xml/dummy-xml.pro b/util/qlalr/examples/dummy-xml/dummy-xml.pro new file mode 100644 index 0000000..e54512d --- /dev/null +++ b/util/qlalr/examples/dummy-xml/dummy-xml.pro @@ -0,0 +1,2 @@ +HEADERS += xmltable_p.h +SOURCES += xmlreader.cpp xmltable.cpp diff --git a/util/qlalr/examples/dummy-xml/ll/dummy-xml-ll.cpp b/util/qlalr/examples/dummy-xml/ll/dummy-xml-ll.cpp new file mode 100644 index 0000000..54f5e0e --- /dev/null +++ b/util/qlalr/examples/dummy-xml/ll/dummy-xml-ll.cpp @@ -0,0 +1,83 @@ + +#include <cstdlib> +#include <cstdio> + +enum Token { + EOF_SYMBOL, + LEFT_ANGLE, + RIGHT_ANGLE, + ANY, +}; + +static int current_char; +static int yytoken; +static bool in_tag = false; + +bool parseXmlStream(); +bool parseTagOrWord(); +bool parseTagName(); + +inline int nextToken() +{ + current_char = fgetc(stdin); + if (current_char == EOF) { + return (yytoken = EOF_SYMBOL); + } else if (current_char == '<') { + in_tag = true; + return (yytoken = LEFT_ANGLE); + } else if (in_tag && current_char == '>') { + in_tag = false; + return (yytoken = RIGHT_ANGLE); + } + return (yytoken = ANY); +} + +bool parse() +{ + nextToken(); + return parseXmlStream(); +} + +bool parseXmlStream() +{ + while (parseTagOrWord()) + ; + + return true; +} + +bool parseTagOrWord() +{ + if (yytoken == LEFT_ANGLE) { + nextToken(); + if (! parseTagName()) + return false; + if (yytoken != RIGHT_ANGLE) + return false; + nextToken(); + + fprintf (stderr, "*** found a tag\n"); + + } else if (yytoken == ANY) { + nextToken(); + } else { + return false; + } + return true; +} + +bool parseTagName() +{ + while (yytoken == ANY) + nextToken(); + + return true; +} + +int main() +{ + if (parse()) + printf("OK\n"); + else + printf("KO\n"); +} diff --git a/util/qlalr/examples/dummy-xml/xml.g b/util/qlalr/examples/dummy-xml/xml.g new file mode 100644 index 0000000..212c829 --- /dev/null +++ b/util/qlalr/examples/dummy-xml/xml.g @@ -0,0 +1,202 @@ + +%parser XMLTable + +%impl xmlreader.cpp + +%token LEFT_ANGLE +%token RIGHT_ANGLE +%token ANY + +%start XmlStream + +/. +#ifndef XMLREADER_H +#define XMLREADER_H + +#include <QtCore> +#include <cstdio> +#include <cstdlib> +#include <cstring> +#include "$header" + +class XMLReader: protected $table +{ +public: + XMLReader(const QByteArray &bytes); + ~XMLReader(); + + bool parse(); + + inline int nextToken() + { + switch (*bufptr++) { + case '\0': + return EOF_SYMBOL; + + case '<': + in_tag = true; + return LEFT_ANGLE; + + case '>': + if (! in_tag) + break; + in_tag = false; + return RIGHT_ANGLE; + break; + + } // switch + + return ANY; + } + +protected: + inline void reallocateStack(); + + inline int &sym(int index) + { return stack [tos + index - 1].ival; } + +protected: + int tos; + int stack_size; + + struct StackItem { + int state; + int ival; + }; + + QVarLengthArray<StackItem> stack; + unsigned in_tag: 1; + QByteArray bytes; + const char *bufptr; +}; + +inline void XMLReader::reallocateStack() +{ + if (! stack_size) + stack_size = 128; + else + stack_size <<= 1; + + stack.resize (stack_size); +} + +#endif // XMLREADER_H + +XMLReader::XMLReader(const QByteArray &bytes): + tos(0), + stack_size(0), + bytes(bytes) +{ + bufptr = bytes.constData(); +} + +XMLReader::~XMLReader() +{ +} + +bool XMLReader::parse() +{ + const int INITIAL_STATE = 0; + + in_tag = 0; + bufptr = bytes.constData(); + + int yytoken = -1; + reallocateStack(); + + tos = 0; + stack [++tos].state = INITIAL_STATE; + + while (true) + { + const int state = stack [tos].state; + + if (yytoken == -1 && - TERMINAL_COUNT != action_index [state]) + yytoken = nextToken(); + + int act = t_action (state, yytoken); + + if (act == ACCEPT_STATE) + return true; + + else if (act > 0) + { + if (++tos == stack_size) + reallocateStack(); + + stack [tos].ival = *bufptr; // ### save the token value here + stack [tos].state = act; + yytoken = -1; + } + + else if (act < 0) + { + int r = - act - 1; + + tos -= rhs [r]; + act = stack [tos++].state; + + switch (r) { +./ + + + + +XmlStream: TagOrWord ; +XmlStream: XmlStream TagOrWord ; + +TagOrWord: Tag ; +TagOrWord: ANY ; + +Tag: LEFT_ANGLE TagName RIGHT_ANGLE ; +/. + case $rule_number: { + fprintf (stderr, "*** found a tag\n"); + } break; +./ + +TagName: ANY ; +TagName: TagName ANY ; + + +/. + } // switch + + stack [tos].state = nt_action (act, lhs [r] - TERMINAL_COUNT); + } + + else + { + // ### ERROR RECOVERY HERE + break; + } + } + + return false; +} + + + +///////////////////////////// +// entry point +///////////////////////////// +int main(int, char *argv[]) +{ + QFile f (argv[1]); + + if (f.open(QFile::ReadOnly)) { + QByteArray contents = f.readAll(); + XMLReader parser (contents); + + if (parser.parse()) + printf ("OK\n"); + else + printf ("KO\n"); + } +} + + + + +./ + diff --git a/util/qlalr/examples/glsl/build.sh b/util/qlalr/examples/glsl/build.sh new file mode 100644 index 0000000..0316911 --- /dev/null +++ b/util/qlalr/examples/glsl/build.sh @@ -0,0 +1,7 @@ +#!/bin/sh + +${FLEX-flex} -oglsl-lex.incl glsl-lex.l +${QLALR-qlalr} glsl.g + +qmake +make diff --git a/util/qlalr/examples/glsl/glsl b/util/qlalr/examples/glsl/glsl new file mode 100755 index 0000000..c19018f --- /dev/null +++ b/util/qlalr/examples/glsl/glsl @@ -0,0 +1,4 @@ +#!/bin/sh + +me=$(dirname $0) +${CPP-cpp} -nostdinc $* | $me/glsl.bin diff --git a/util/qlalr/examples/glsl/glsl-lex.l b/util/qlalr/examples/glsl/glsl-lex.l new file mode 100644 index 0000000..1e07c3b --- /dev/null +++ b/util/qlalr/examples/glsl/glsl-lex.l @@ -0,0 +1,201 @@ + +%{ +#include <cassert> +#define YY_DECL int GLSLParser::nextToken() +%} + +%option noyywrap + +hex [0-9a-fA-F] +dec [1-9][0-9]* +oct [0-7] +digit [0-9] + +fract {digit}*\.{digit}+|{digit}+\. +exp [eE][+-]?{digit}+ + +hexfract {hex}*\.{hex}+|{hex}+\. +binexp [pP][+-]?{digit}+ + +icst ({dec}|0{oct}*|0[xX]{hex}+) + +%% + +[\n] { ++context.line; } +[ \t\r]+ { /* skip */ } + +"+=" { return ADD_ASSIGN; } +"&" { return AMPERSAND; } +"&=" { return AND_ASSIGN; } +"&&" { return AND_OP; } +"attribute" { return ATTRIBUTE; } +"!" { return BANG; } +"bool" { return BOOL; } +"true" { return BOOLCONSTANT; } +"false" { return BOOLCONSTANT; } +"break" { return BREAK; } +"bvec2" { return BVEC2; } +"bvec3" { return BVEC3; } +"bvec4" { return BVEC4; } +":" { return COLON; } +"," { return COMMA; } +"const" { return CONST; } +"continue" { return CONTINUE; } +"-" { return DASH; } +"--" { return DEC_OP; } +"discard" { return DISCARD; } +"/=" { return DIV_ASSIGN; } +"do" { return DO; } +"." { return DOT; } +"else" { return ELSE; } +"=" { return EQUAL; } +"==" { return EQ_OP; } +"float" { return FLOAT; } +"for" { return FOR; } +">=" { return GE_OP; } +"if" { return IF; } +"in" { return IN; } +"++" { return INC_OP; } +"inout" { return INOUT; } +"int" { return INT; } +"ivec2" { return IVEC2; } +"ivec3" { return IVEC3; } +"ivec4" { return IVEC4; } +"<" { return LEFT_ANGLE; } +"<<=" { return LEFT_ASSIGN; } +"{" { return LEFT_BRACE; } +"[" { return LEFT_BRACKET; } +"<<" { return LEFT_OP; } +"(" { return LEFT_PAREN; } +"<=" { return LE_OP; } +"mat2" { return MAT2; } +"mat3" { return MAT3; } +"mat4" { return MAT4; } +"%=" { return MOD_ASSIGN; } +"*=" { return MUL_ASSIGN; } +"!=" { return NE_OP; } +"|=" { return OR_ASSIGN; } +"||" { return OR_OP; } +"out" { return OUT; } +"%" { return PERCENT; } +"+" { return PLUS; } +"?" { return QUESTION; } +"return" { return RETURN; } +">" { return RIGHT_ANGLE; } +">>=" { return RIGHT_ASSIGN; } +"}" { return RIGHT_BRACE; } +"]" { return RIGHT_BRACKET; } +">>" { return RIGHT_OP; } +")" { return RIGHT_PAREN; } +"sampler1D" { return SAMPLER1D; } +"sampler1DShadow" { return SAMPLER1DSHADOW; } +"sampler2D" { return SAMPLER2D; } +"sampler2DShadow" { return SAMPLER2DSHADOW; } +"sampler3D" { return SAMPLER3D; } +"samplerCube" { return SAMPLERCUBE; } +";" { return SEMICOLON; } +"/" { return SLASH; } +"*" { return STAR; } +"struct" { return STRUCT; } +"-=" { return SUB_ASSIGN; } +"~" { return TILDE; } +"uniform" { return UNIFORM; } +"varying" { return VARYING; } +"vec2" { return VEC2; } +"vec3" { return VEC3; } +"vec4" { return VEC4; } +"|" { return VERTICAL_BAR; } +"void" { return VOID; } +"while" { return WHILE; } +"^=" { return XOR_ASSIGN; } +"^" { return XOR_OP; } + +#[ \t]+[0-9]+.* { + char *eptr = 0; + context.line = (int) strtod(&yytext[1], &eptr); + QString fn = QString::fromUtf8(eptr).trimmed(); + if (fn.length() > 2) + context.fileName = fn.mid(1, fn.length()-2); +} + +#.* { + /* skip */ +} + +[_a-zA-Z][_a-zA-Z0-9]* { + yylval.s = intern (yytext); + + if (isTypename (yylval.s)) + return TYPE_NAME; + + return IDENTIFIER; +} + +{icst} { + yylval.i = (int) strtol (yytext, 0, 0); + return INTCONSTANT; +} + +{icst}[uU] { + yylval.u = (unsigned) strtoul (yytext, 0, 0); + return INTCONSTANT; +} + +{icst}[uU][lL] { + yylval.ul = strtoul (yytext, 0, 0); + return INTCONSTANT; +} + +{icst}[lL][uU] { + yylval.ul = strtoul (yytext, 0, 0); + return INTCONSTANT; +} + +{icst}[lL] { + yylval.l = strtol (yytext, 0, 0); + return INTCONSTANT; +} + +{icst}[uU](ll|LL) { + yylval.l = strtoull (yytext, 0, 0); + return INTCONSTANT; +} + +{icst}(ll|LL) { + yylval.l = strtoll (yytext, 0, 0); + return INTCONSTANT; +} + +{icst}(ll|LL)[uU] { + yylval.l = strtoull (yytext, 0, 0); + return INTCONSTANT; +} + +{fract}{exp}?[flFL]? { + yylval.f = strtof (yytext, 0); + return FLOATCONSTANT; +} + +{digit}+{exp}[flFL]? { + yylval.f = strtof (yytext, 0); + return FLOATCONSTANT; +} + +0[xX]{hexfract}{binexp}[flFL]? { + yylval.f = strtof (yytext, 0); + return FLOATCONSTANT; +} + +0[xX]{hex}+{binexp}[flFL]? { + yylval.f = strtof (yytext, 0); + return FLOATCONSTANT; +} + +. { + fprintf (stderr, "invalid char: %d\n", yytext [0]); + return ERROR; +} + + +%% + diff --git a/util/qlalr/examples/glsl/glsl.g b/util/qlalr/examples/glsl/glsl.g new file mode 100644 index 0000000..3f3a3ad --- /dev/null +++ b/util/qlalr/examples/glsl/glsl.g @@ -0,0 +1,621 @@ + +%parser GLSLParserTable +%merged_output glsl.cpp + +%token ADD_ASSIGN +%token AMPERSAND +%token AND_ASSIGN +%token AND_OP +%token ATTRIBUTE +%token BANG +%token BOOL +%token BOOLCONSTANT +%token BREAK +%token BVEC2 +%token BVEC3 +%token BVEC4 +%token CARET +%token COLON +%token COMMA +%token CONST +%token CONTINUE +%token DASH +%token DEC_OP +%token DISCARD +%token DIV_ASSIGN +%token DO +%token DOT +%token ELSE +%token EQUAL +%token EQ_OP +%token FLOAT +%token FLOATCONSTANT +%token FOR +%token GE_OP +%token IDENTIFIER +%token IF +%token IN +%token INC_OP +%token INOUT +%token INT +%token INTCONSTANT +%token IVEC2 +%token IVEC3 +%token IVEC4 +%token LEFT_ANGLE +%token LEFT_ASSIGN +%token LEFT_BRACE +%token LEFT_BRACKET +%token LEFT_OP +%token LEFT_PAREN +%token LE_OP +%token MAT2 +%token MAT3 +%token MAT4 +%token MOD_ASSIGN +%token MUL_ASSIGN +%token NE_OP +%token OR_ASSIGN +%token OR_OP +%token OUT +%token PERCENT +%token PLUS +%token QUESTION +%token RETURN +%token RIGHT_ANGLE +%token RIGHT_ASSIGN +%token RIGHT_BRACE +%token RIGHT_BRACKET +%token RIGHT_OP +%token RIGHT_PAREN +%token SAMPLER1D +%token SAMPLER1DSHADOW +%token SAMPLER2D +%token SAMPLER2DSHADOW +%token SAMPLER3D +%token SAMPLERCUBE +%token SEMICOLON +%token SLASH +%token STAR +%token STRUCT +%token SUB_ASSIGN +%token TILDE +%token TYPE_NAME +%token UNIFORM +%token VARYING +%token VEC2 +%token VEC3 +%token VEC4 +%token VERTICAL_BAR +%token VOID +%token WHILE +%token XOR_ASSIGN +%token XOR_OP +%token ERROR +%start translation_unit + + +/: + +#include <QtCore> + +class GLSLParser: protected $table +{ +public: + union Value { + int i; + unsigned u; + unsigned long ul; + unsigned long long ull; + long l; + double d; + float f; + const QString *s; + // ### more... + }; + +public: + GLSLParser(); + ~GLSLParser(); + + bool parse(); + +protected: + inline void reallocateStack(); + + inline Value &sym(int index) + { return sym_stack [tos + index - 1]; } + + int nextToken(); + + bool isTypename(const QString *s) const + { + return types.contains(s); + } + + inline const QString *intern(const QString &s) + { return &*string_repository.insert(s); } + +protected: + int tos; + int stack_size; + Value *sym_stack; + int *state_stack; + Value yylval; + QSet<QString> string_repository; + QSet<const QString*> types; + + struct /*Context*/ { + int line; + const QString *function_name; + QString fileName; + + void init() + { + line = 1; + function_name = 0; + fileName.clear(); + } + } context; +}; + +inline void GLSLParser::reallocateStack() +{ + if (! stack_size) + stack_size = 128; + else + stack_size <<= 1; + + sym_stack = reinterpret_cast<Value*> (qRealloc(sym_stack, stack_size * sizeof(Value))); + state_stack = reinterpret_cast<int*> (qRealloc(state_stack, stack_size * sizeof(int))); +} + +:/ + + +/. + +GLSLParser::GLSLParser(): + tos(0), + stack_size(0), + sym_stack(0), + state_stack(0) +{ +} + +GLSLParser::~GLSLParser() +{ + if (stack_size) { + qFree(sym_stack); + qFree(state_stack); + } +} + +bool GLSLParser::parse() +{ + const int INITIAL_STATE = 0; + + int yytoken = -1; + + reallocateStack(); + + context.init(); + tos = 0; + state_stack[++tos] = INITIAL_STATE; + + while (true) + { + if (yytoken == -1 && - TERMINAL_COUNT != action_index [state_stack [tos]]) + yytoken = nextToken(); + + int act = t_action (state_stack [tos], yytoken); + + if (act == ACCEPT_STATE) { + return true; + } + + else if (act > 0) + { + if (++tos == stack_size) + reallocateStack(); + + sym_stack [tos] = yylval; + state_stack [tos] = act; + yytoken = -1; + } + + else if (act < 0) + { + int r = - act - 1; + + int ridx = rule_index [r]; + printf ("*** reduce using rule %d %s ::=", r + 1, spell[rule_info [ridx]]); + ++ridx; + for (int i = ridx; i < ridx + rhs [r]; ++i) + { + int symbol = rule_info [i]; + if (const char *name = spell [symbol]) + printf (" %s", name); + else + printf (" #%d", symbol); + } + printf ("\n"); + + tos -= rhs [r]; + act = state_stack [tos++]; + + switch (r) { +./ + + +translation_unit ::= external_declaration ; +translation_unit ::= translation_unit external_declaration ; + +variable_identifier ::= IDENTIFIER ; + +primary_expression ::= variable_identifier ; +primary_expression ::= INTCONSTANT ; +primary_expression ::= FLOATCONSTANT ; +primary_expression ::= BOOLCONSTANT ; +primary_expression ::= LEFT_PAREN expression RIGHT_PAREN ; + + +postfix_expression ::= primary_expression ; +postfix_expression ::= postfix_expression LEFT_BRACKET integer_expression RIGHT_BRACKET ; +postfix_expression ::= function_call ; +postfix_expression ::= postfix_expression DOT IDENTIFIER ; +postfix_expression ::= postfix_expression DOT TYPE_NAME ; +postfix_expression ::= postfix_expression INC_OP ; +postfix_expression ::= postfix_expression DEC_OP ; + + +integer_expression ::= expression ; + +function_call ::= function_call_generic ; + +function_call_generic ::= function_call_header_with_parameters RIGHT_PAREN ; +function_call_generic ::= function_call_header_no_parameters RIGHT_PAREN ; + +function_call_header_no_parameters ::= function_call_header VOID ; +function_call_header_no_parameters ::= function_call_header ; + + +function_call_header_with_parameters ::= function_call_header assignment_expression ; +function_call_header_with_parameters ::= function_call_header_with_parameters COMMA assignment_expression ; + +function_call_header ::= function_identifier LEFT_PAREN ; + +function_identifier ::= constructor_identifier ; +function_identifier ::= IDENTIFIER ; + + +constructor_identifier ::= FLOAT ; +constructor_identifier ::= INT ; +constructor_identifier ::= BOOL ; +constructor_identifier ::= VEC2 ; +constructor_identifier ::= VEC3 ; +constructor_identifier ::= VEC4 ; +constructor_identifier ::= BVEC2 ; +constructor_identifier ::= BVEC3 ; +constructor_identifier ::= BVEC4 ; +constructor_identifier ::= IVEC2 ; +constructor_identifier ::= IVEC3 ; +constructor_identifier ::= IVEC4 ; +constructor_identifier ::= MAT2 ; +constructor_identifier ::= MAT3 ; +constructor_identifier ::= MAT4 ; +constructor_identifier ::= TYPE_NAME ; + +unary_expression ::= postfix_expression ; +unary_expression ::= INC_OP unary_expression ; +unary_expression ::= DEC_OP unary_expression ; +unary_expression ::= unary_operator unary_expression ; + +-- Grammar Note: No traditional style type casts. + +unary_operator ::= PLUS ; +unary_operator ::= DASH ; +unary_operator ::= BANG ; +unary_operator ::= TILDE ; -- reserved + +-- Grammar Note: No '*' or '&' unary ops. Pointers are not supported. + +multiplicative_expression ::= unary_expression ; +multiplicative_expression ::= multiplicative_expression STAR unary_expression ; +multiplicative_expression ::= multiplicative_expression SLASH unary_expression ; +multiplicative_expression ::= multiplicative_expression PERCENT unary_expression ; -- reserved + + +additive_expression ::= multiplicative_expression ; +additive_expression ::= additive_expression PLUS multiplicative_expression ; +additive_expression ::= additive_expression DASH multiplicative_expression ; + +shift_expression ::= additive_expression ; +shift_expression ::= shift_expression LEFT_OP additive_expression ; -- reserved +shift_expression ::= shift_expression RIGHT_OP additive_expression ; -- reserved + +relational_expression ::= shift_expression ; +relational_expression ::= relational_expression LEFT_ANGLE shift_expression ; +relational_expression ::= relational_expression RIGHT_ANGLE shift_expression ; +relational_expression ::= relational_expression LE_OP shift_expression ; +relational_expression ::= relational_expression GE_OP shift_expression ; + +equality_expression ::= relational_expression ; +equality_expression ::= equality_expression EQ_OP relational_expression ; +equality_expression ::= equality_expression NE_OP relational_expression ; + +and_expression ::= equality_expression ; +and_expression ::= and_expression AMPERSAND equality_expression ; -- reserved + +exclusive_or_expression ::= and_expression ; +exclusive_or_expression ::= exclusive_or_expression CARET and_expression ; -- reserved + +inclusive_or_expression ::= exclusive_or_expression ; +inclusive_or_expression ::= inclusive_or_expression VERTICAL_BAR exclusive_or_expression ; -- reserved + +logical_and_expression ::= inclusive_or_expression ; +logical_and_expression ::= logical_and_expression AND_OP inclusive_or_expression ; + +logical_xor_expression ::= logical_and_expression ; +logical_xor_expression ::= logical_xor_expression XOR_OP logical_and_expression ; + +logical_or_expression ::= logical_xor_expression ; +logical_or_expression ::= logical_or_expression OR_OP logical_xor_expression ; + +conditional_expression ::= logical_or_expression ; +conditional_expression ::= logical_or_expression QUESTION expression COLON conditional_expression ; + +assignment_expression ::= conditional_expression ; +assignment_expression ::= unary_expression assignment_operator assignment_expression ; + +assignment_operator ::= EQUAL ; +assignment_operator ::= MUL_ASSIGN ; +assignment_operator ::= DIV_ASSIGN ; +assignment_operator ::= MOD_ASSIGN ; -- reserved +assignment_operator ::= ADD_ASSIGN ; +assignment_operator ::= SUB_ASSIGN ; +assignment_operator ::= LEFT_ASSIGN ; -- reserved +assignment_operator ::= RIGHT_ASSIGN ; -- reserved +assignment_operator ::= AND_ASSIGN ; -- reserved +assignment_operator ::= XOR_ASSIGN ; -- reserved +assignment_operator ::= OR_ASSIGN ; -- reserved + +expression ::= assignment_expression ; +expression ::= expression COMMA assignment_expression ; + +constant_expression ::= conditional_expression ; + +declaration ::= function_prototype SEMICOLON ; +declaration ::= init_declarator_list SEMICOLON ; + +function_prototype ::= function_declarator RIGHT_PAREN ; + +function_declarator ::= function_header ; +function_declarator ::= function_header_with_parameters ; + +function_header_with_parameters ::= function_header parameter_declaration ; +function_header_with_parameters ::= function_header_with_parameters COMMA parameter_declaration ; + +function_header ::= fully_specified_type IDENTIFIER LEFT_PAREN ; +/. +case $rule_number: { + context.function_name = sym(2).s; +} break; +./ + +parameter_declarator ::= type_specifier IDENTIFIER ; +parameter_declarator ::= type_specifier IDENTIFIER LEFT_BRACKET constant_expression RIGHT_BRACKET ; + +parameter_declaration ::= type_qualifier parameter_qualifier parameter_declarator ; +parameter_declaration ::= parameter_qualifier parameter_declarator ; +parameter_declaration ::= type_qualifier parameter_qualifier parameter_type_specifier ; +parameter_declaration ::= parameter_qualifier parameter_type_specifier ; + +parameter_qualifier ::= ; +parameter_qualifier ::= IN ; +parameter_qualifier ::= OUT ; +parameter_qualifier ::= INOUT ; + +parameter_type_specifier ::= type_specifier ; +parameter_type_specifier ::= type_specifier LEFT_BRACKET constant_expression RIGHT_BRACKET ; + +init_declarator_list ::= single_declaration ; +init_declarator_list ::= init_declarator_list COMMA IDENTIFIER ; +init_declarator_list ::= init_declarator_list COMMA IDENTIFIER LEFT_BRACKET RIGHT_BRACKET ; +init_declarator_list ::= init_declarator_list COMMA IDENTIFIER LEFT_BRACKET constant_expression ; +init_declarator_list ::= RIGHT_BRACKET ; +init_declarator_list ::= init_declarator_list COMMA IDENTIFIER EQUAL initializer ; + +single_declaration ::= fully_specified_type ; +single_declaration ::= fully_specified_type IDENTIFIER ; +single_declaration ::= fully_specified_type IDENTIFIER LEFT_BRACKET RIGHT_BRACKET ; +single_declaration ::= fully_specified_type IDENTIFIER LEFT_BRACKET constant_expression RIGHT_BRACKET ; +single_declaration ::= fully_specified_type IDENTIFIER EQUAL initializer ; + +-- Grammar Note: No 'enum', or 'typedef'. + +--fully_specified_type ::= type_specifier ; +--fully_specified_type ::= type_qualifier type_specifier ; + +fully_specified_type ::= type_specifier ; +fully_specified_type ::= type_qualifier ; +fully_specified_type ::= fully_specified_type type_specifier ; +fully_specified_type ::= fully_specified_type type_qualifier ; + +type_qualifier ::= CONST ; +type_qualifier ::= ATTRIBUTE ; -- Vertex only. +type_qualifier ::= VARYING ; +type_qualifier ::= UNIFORM ; + +type_specifier ::= VOID ; +type_specifier ::= FLOAT ; +type_specifier ::= INT ; +type_specifier ::= BOOL ; +type_specifier ::= VEC2 ; +type_specifier ::= VEC3 ; +type_specifier ::= VEC4 ; +type_specifier ::= BVEC2 ; +type_specifier ::= BVEC3 ; +type_specifier ::= BVEC4 ; +type_specifier ::= IVEC2 ; +type_specifier ::= IVEC3 ; +type_specifier ::= IVEC4 ; +type_specifier ::= MAT2 ; +type_specifier ::= MAT3 ; +type_specifier ::= MAT4 ; +type_specifier ::= SAMPLER1D ; +type_specifier ::= SAMPLER2D ; +type_specifier ::= SAMPLER3D ; +type_specifier ::= SAMPLERCUBE ; +type_specifier ::= SAMPLER1DSHADOW ; +type_specifier ::= SAMPLER2DSHADOW ; +type_specifier ::= struct_specifier ; +type_specifier ::= TYPE_NAME ; + +struct_specifier ::= STRUCT IDENTIFIER LEFT_BRACE struct_declaration_list RIGHT_BRACE ; +/. +case $rule_number: { + types.insert(sym(2).s); +} break; +./ + +struct_specifier ::= STRUCT LEFT_BRACE struct_declaration_list RIGHT_BRACE ; + +struct_declaration_list ::= struct_declaration ; +struct_declaration_list ::= struct_declaration_list struct_declaration ; + +struct_declaration ::= type_specifier struct_declarator_list SEMICOLON ; + +struct_declarator_list ::= struct_declarator ; +struct_declarator_list ::= struct_declarator_list COMMA struct_declarator ; + +struct_declarator ::= IDENTIFIER ; +struct_declarator ::= IDENTIFIER LEFT_BRACKET constant_expression RIGHT_BRACKET ; + +initializer ::= assignment_expression ; + +declaration_statement ::= declaration ; + +statement ::= compound_statement ; +statement ::= simple_statement ; + +-- Grammar Note: No labeled statements; 'goto' is not supported. + +simple_statement ::= declaration_statement ; +simple_statement ::= expression_statement ; +simple_statement ::= selection_statement ; +simple_statement ::= iteration_statement ; +simple_statement ::= jump_statement ; + +compound_statement ::= LEFT_BRACE RIGHT_BRACE ; +compound_statement ::= LEFT_BRACE statement_list RIGHT_BRACE ; + +statement_no_new_scope ::= compound_statement_no_new_scope ; +statement_no_new_scope ::= simple_statement ; + +compound_statement_no_new_scope ::= LEFT_BRACE RIGHT_BRACE ; +compound_statement_no_new_scope ::= LEFT_BRACE statement_list RIGHT_BRACE ; + +statement_list ::= statement ; +statement_list ::= statement_list statement ; + +expression_statement ::= SEMICOLON ; +expression_statement ::= expression SEMICOLON ; + +selection_statement ::= IF LEFT_PAREN expression RIGHT_PAREN statement ELSE statement ; +selection_statement ::= IF LEFT_PAREN expression RIGHT_PAREN statement ; + +-- Grammar Note: No 'switch'. Switch statements not supported. + +condition ::= expression ; +condition ::= fully_specified_type IDENTIFIER EQUAL initializer ; + +iteration_statement ::= WHILE LEFT_PAREN condition RIGHT_PAREN statement_no_new_scope ; +iteration_statement ::= DO statement WHILE LEFT_PAREN expression RIGHT_PAREN SEMICOLON ; +iteration_statement ::= FOR LEFT_PAREN for_init_statement for_rest_statement RIGHT_PAREN statement_no_new_scope ; + +for_init_statement ::= expression_statement ; +for_init_statement ::= declaration_statement ; + +conditionopt ::= ; +conditionopt ::= condition ; + +for_rest_statement ::= conditionopt SEMICOLON ; +for_rest_statement ::= conditionopt SEMICOLON expression ; + +jump_statement ::= CONTINUE SEMICOLON ; +jump_statement ::= BREAK SEMICOLON ; +jump_statement ::= RETURN SEMICOLON ; +jump_statement ::= RETURN expression SEMICOLON ; +jump_statement ::= DISCARD SEMICOLON ; -- Fragment shader only. + +-- Grammar Note: No 'goto'. Gotos are not supported. + +external_declaration ::= function_definition ; +external_declaration ::= declaration ; + +function_definition ::= function_prototype compound_statement_no_new_scope ; +/. + case $rule_number: { // $rule_name + qDebug() << "--> function" << *context.function_name; + } break; +./ + + + + + +/. + } // switch + + state_stack [tos] = nt_action (act, lhs [r] - TERMINAL_COUNT); + } + + else + { + // ### ERROR RECOVERY HERE + break; + } + } + + fprintf (stderr, "%s:%d: Syntax Error\n", qPrintable(context.fileName), context.line); + + return false; +} + +#include "glsl-lex.incl" + + +///////////////////////////// +// entry point +///////////////////////////// +int main() +{ +#if 0 // dump the GLSL grammar + for (int r = 0; r < GLSLParserTable::RULE_COUNT; ++r) + { + int ridx = GLSLParserTable::rule_index [r]; + int rhs = GLSLParserTable::rhs [r]; + printf ("%3d) %s ::=", r + 1, GLSLParserTable::spell[GLSLParserTable::rule_info [ridx]]); + ++ridx; + for (int i = ridx; i < ridx + rhs; ++i) + { + int symbol = GLSLParserTable::rule_info [i]; + if (const char *name = GLSLParserTable::spell [symbol]) + printf (" %s", name); + else + printf (" #%d", symbol); + } + printf ("\n"); + } +#endif + + GLSLParser parser; + + if (parser.parse()) + qDebug() << "OK"; + else + qDebug() << "KO"; +} + +./ diff --git a/util/qlalr/examples/glsl/glsl.pro b/util/qlalr/examples/glsl/glsl.pro new file mode 100644 index 0000000..8ac775f --- /dev/null +++ b/util/qlalr/examples/glsl/glsl.pro @@ -0,0 +1,4 @@ +QT = core +TARGET = glsl.bin +SOURCES += glsl.cpp + diff --git a/util/qlalr/examples/lambda/COMPILE b/util/qlalr/examples/lambda/COMPILE new file mode 100644 index 0000000..3226ec9 --- /dev/null +++ b/util/qlalr/examples/lambda/COMPILE @@ -0,0 +1,3 @@ +qlalr lambda.g +qmake +make diff --git a/util/qlalr/examples/lambda/lambda.g b/util/qlalr/examples/lambda/lambda.g new file mode 100644 index 0000000..2fb9594 --- /dev/null +++ b/util/qlalr/examples/lambda/lambda.g @@ -0,0 +1,41 @@ + +-- lambda calculus + +%decl lambda.h + +%token LPAREN +%token RPAREN +%token ID +%token FUN +%token DOT + +%nonassoc SHIFT_THERE +%nonassoc LPAREN RPAREN ID FUN DOT +%nonassoc REDUCE_HERE + +%start Expr + +/: +enum { +:/ + + +Expr ::= ID %prec SHIFT_THERE ; +/: Symbol = $rule_number, +:/ + +Expr ::= LPAREN Expr RPAREN %prec SHIFT_THERE ; +/: SubExpression = $rule_number, +:/ + +Expr ::= Expr Expr %prec REDUCE_HERE ; +/: Appl = $rule_number, +:/ + +Expr ::= FUN ID DOT Expr %prec SHIFT_THERE ; +/: Abstr = $rule_number, +:/ + +/:}; +:/ + diff --git a/util/qlalr/examples/lambda/lambda.pro b/util/qlalr/examples/lambda/lambda.pro new file mode 100644 index 0000000..dfe4824 --- /dev/null +++ b/util/qlalr/examples/lambda/lambda.pro @@ -0,0 +1,3 @@ +HEADERS += lambda.h parser_table_p.h +SOURCES += main.cpp parser_table.cpp +QT = core diff --git a/util/qlalr/examples/lambda/main.cpp b/util/qlalr/examples/lambda/main.cpp new file mode 100644 index 0000000..c70f9a5 --- /dev/null +++ b/util/qlalr/examples/lambda/main.cpp @@ -0,0 +1,160 @@ + +#include "lambda.h" + + +#include <cstdio> +#include <cstdlib> +#include <cstring> +#include "parser_table_p.h" + +class Parser: protected parser_table +{ +public: + union Value { + int ival; + // ### more... + }; + +public: + Parser(); + ~Parser(); + + bool parse(); + +protected: + inline void reallocateStack(); + + inline Value &sym(int index) + { return sym_stack [tos + index - 1]; } + + int nextToken(); + void consumeRule(int ruleno); + +protected: + int tos; + int stack_size; + Value *sym_stack; + int *state_stack; + int current_char; + unsigned in_tag: 1; +}; + +inline void Parser::reallocateStack() +{ + if (! stack_size) + stack_size = 128; + else + stack_size <<= 1; + + sym_stack = reinterpret_cast<Value*> (::realloc(sym_stack, stack_size * sizeof(Value))); + state_stack = reinterpret_cast<int*> (::realloc(state_stack, stack_size * sizeof(int))); +} + +Parser::Parser(): + tos(0), + stack_size(0), + sym_stack(0), + state_stack(0) +{ +} + +Parser::~Parser() +{ + if (stack_size) { + ::free(sym_stack); + ::free(state_stack); + } +} + +bool Parser::parse() +{ + const int INITIAL_STATE = 0; + + current_char = 0; + in_tag = 0; + + int yytoken = -1; + reallocateStack(); + + tos = 0; + state_stack[++tos] = INITIAL_STATE; + + while (true) + { + if (yytoken == -1 && - TERMINAL_COUNT != action_index [state_stack [tos]]) + yytoken = nextToken(); + + int act = t_action (state_stack [tos], yytoken); + + if (act == ACCEPT_STATE) { + return true; + } + + else if (act > 0) + { + if (++tos == stack_size) + reallocateStack(); + + sym_stack [tos].ival = current_char; // ### save the token value here + state_stack [tos] = act; + yytoken = -1; + } + + else if (act < 0) + { + int r = - act - 1; + + tos -= rhs [r]; + act = state_stack [tos++]; + consumeRule (r); + state_stack [tos] = nt_action (act, lhs [r] - TERMINAL_COUNT); + } + + else + break; + } + + return false; +} + + +int Parser::nextToken() +{ + static int tokens[] = { ID, ID, ID, EOF_SYMBOL }; + static int *tk = tokens; + + return *tk++; +} + +void Parser::consumeRule(int ruleno) +{ + switch (ruleno) { + case Symbol: + printf("symbol\n"); + break; + case SubExpression: + printf("sub-expr\n"); + break; + case Appl: + printf("appl\n"); + break; + case Abstr: + printf("abstr\n"); + break; + } +} + +///////////////////////////// +// entry point +///////////////////////////// +int main() +{ + Parser parser; + + if (parser.parse()) + printf ("OK\n"); + else + printf ("KO\n"); +} + + diff --git a/util/qlalr/examples/qparser/COMPILE b/util/qlalr/examples/qparser/COMPILE new file mode 100644 index 0000000..4aad300 --- /dev/null +++ b/util/qlalr/examples/qparser/COMPILE @@ -0,0 +1,3 @@ +qlalr calc.g +qmake +make diff --git a/util/qlalr/examples/qparser/calc.g b/util/qlalr/examples/qparser/calc.g new file mode 100644 index 0000000..24371d4 --- /dev/null +++ b/util/qlalr/examples/qparser/calc.g @@ -0,0 +1,93 @@ + +%parser calc_grammar +%decl calc_parser.h +%impl calc_parser.cpp + +%token_prefix Token_ +%token number +%token lparen +%token rparen +%token plus +%token minus + +%start Goal + +/: +#ifndef CALC_PARSER_H +#define CALC_PARSER_H + +#include "qparser.h" +#include "calc_grammar_p.h" + +class CalcParser: public QParser<CalcParser, $table> +{ +public: + int nextToken(); + void consumeRule(int ruleno); +}; + +#endif // CALC_PARSER_H +:/ + + + + + +/. +#include "calc_parser.h" + +#include <QtDebug> +#include <cstdlib> + +void CalcParser::consumeRule(int ruleno) + { + switch (ruleno) { +./ + +Goal: Expression ; +/. +case $rule_number: + qDebug() << "value:" << sym(1); + break; +./ + +PrimaryExpression: number ; +PrimaryExpression: lparen Expression rparen ; +/. +case $rule_number: + sym(1) = sym (2); + break; +./ + +Expression: PrimaryExpression ; + +Expression: Expression plus PrimaryExpression; +/. +case $rule_number: + sym(1) += sym (3); + break; +./ + +Expression: Expression minus PrimaryExpression; +/. +case $rule_number: + sym(1) -= sym (3); + break; +./ + + + +/. + } // switch +} + +#include <cstdio> + +int main() +{ + CalcParser p; + + if (p.parse()) + printf("ok\n"); +} +./ diff --git a/util/qlalr/examples/qparser/calc.l b/util/qlalr/examples/qparser/calc.l new file mode 100644 index 0000000..95181d5 --- /dev/null +++ b/util/qlalr/examples/qparser/calc.l @@ -0,0 +1,20 @@ + +%option noyywrap + +%{ +#include "calc_parser.h" +#include <cstdlib> + +#define YY_DECL int CalcParser::nextToken() +%} + +%% + +[ \t\n] { /* eat me */ } +[0-9]+ { sym(1) = atoi (yytext); return Token_number; } +"(" { return Token_lparen; } +")" { return Token_rparen; } +"+" { return Token_plus; } +"-" { return Token_minus; } + +%% diff --git a/util/qlalr/examples/qparser/qparser.cpp b/util/qlalr/examples/qparser/qparser.cpp new file mode 100644 index 0000000..5a18ee2 --- /dev/null +++ b/util/qlalr/examples/qparser/qparser.cpp @@ -0,0 +1,3 @@ + +#include "qparser.h" + diff --git a/util/qlalr/examples/qparser/qparser.h b/util/qlalr/examples/qparser/qparser.h new file mode 100644 index 0000000..e3ff61d --- /dev/null +++ b/util/qlalr/examples/qparser/qparser.h @@ -0,0 +1,111 @@ +#ifndef QPARSER_H +#define QPARSER_H + +#include <QtCore/QSharedDataPointer> +#include <QtCore/QVarLengthArray> + +template <typename _Parser, typename _Table, typename _Value = int> +class QParser: protected _Table +{ +public: + QParser(); + ~QParser(); + + bool parse(); + + inline _Value &sym(int index); + +private: + inline int nextToken() + { + return static_cast<_Parser*> (this)->nextToken(); + } + + inline void consumeRule(int rule) + { + static_cast<_Parser*> (this)->consumeRule(rule); + } + + enum { DefaultStackSize = 128 }; + + struct Data: public QSharedData + { + Data(): stackSize (DefaultStackSize), tos (0) {} + + QVarLengthArray<int, DefaultStackSize> stateStack; + QVarLengthArray<_Value, DefaultStackSize> parseStack; + int stackSize; + int tos; + + void reallocateStack() { + stackSize <<= 1; + stateStack.resize(stackSize); + parseStack.resize(stackSize); + } + }; + + QSharedDataPointer<Data> d; +}; + +template <typename _Parser, typename _Table, typename _Value> +inline _Value &QParser<_Parser, _Table, _Value>::sym(int n) +{ + return d->parseStack [d->tos + n - 1]; +} + +template <typename _Parser, typename _Table, typename _Value> +QParser<_Parser, _Table, _Value>::QParser(): + d(new Data()) +{ +} + +template <typename _Parser, typename _Table, typename _Value> +QParser<_Parser, _Table, _Value>::~QParser() +{ +} + +template <typename _Parser, typename _Table, typename _Value> +bool QParser<_Parser, _Table, _Value>::parse() +{ + const int INITIAL_STATE = 0; + + d->tos = 0; + d->reallocateStack(); + + int act = d->stateStack[++d->tos] = INITIAL_STATE; + int token = -1; + + forever { + if (token == -1 && - _Table::TERMINAL_COUNT != _Table::action_index[act]) + token = nextToken(); + + act = _Table::t_action(act, token); + + if (d->stateStack[d->tos] == _Table::ACCEPT_STATE) + return true; + + else if (act > 0) { + if (++d->tos == d->stackSize) + d->reallocateStack(); + + d->parseStack[d->tos] = d->parseStack[d->tos - 1]; + d->stateStack[d->tos] = act; + token = -1; + } + + else if (act < 0) { + int r = - act - 1; + d->tos -= _Table::rhs[r]; + act = d->stateStack[d->tos++]; + consumeRule(r); + act = d->stateStack[d->tos] = _Table::nt_action(act, _Table::lhs[r] - _Table::TERMINAL_COUNT); + } + + else break; + } + + return false; +} + + +#endif // QPARSER_H diff --git a/util/qlalr/examples/qparser/qparser.pro b/util/qlalr/examples/qparser/qparser.pro new file mode 100644 index 0000000..938e336 --- /dev/null +++ b/util/qlalr/examples/qparser/qparser.pro @@ -0,0 +1,4 @@ +QT = core +HEADERS += calc_grammar_p.h calc_parser.h qparser.h +SOURCES += calc_grammar.cpp calc_parser.cpp qparser.cpp +LEXSOURCES += calc.l diff --git a/util/qlalr/grammar.cpp b/util/qlalr/grammar.cpp new file mode 100644 index 0000000..9e5dabf --- /dev/null +++ b/util/qlalr/grammar.cpp @@ -0,0 +1,123 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QLALR project on Trolltech Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "grammar_p.h" + +const char *const grammar::spell [] = { + "end of file", "identifier", "string literal", "%decl", "%expect", "%expect-lr", "%impl", "%left", "%merged_output", "%nonassoc", + "%parser", "%prec", "%right", "%start", "%token", "%token_prefix", ":", "|", ";", 0, + 0, 0}; + +const int grammar::lhs [] = { + 22, 23, 23, 29, 25, 28, 28, 28, 28, 28, + 28, 28, 24, 24, 31, 32, 32, 33, 33, 34, + 34, 34, 31, 35, 35, 36, 37, 37, 38, 38, + 30, 30, 26, 26, 40, 39, 41, 41, 44, 43, + 43, 42, 42, 27, 45}; + +const int grammar:: rhs[] = { + 4, 1, 2, 2, 2, 2, 2, 2, 2, 2, + 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, + 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, + 0, 1, 1, 2, 2, 4, 3, 6, 0, 0, + 2, 1, 2, 0, 2}; + +const int grammar::action_default [] = { + 44, 2, 44, 0, 0, 0, 0, 13, 0, 0, + 3, 0, 0, 0, 8, 10, 11, 9, 7, 6, + 12, 20, 22, 0, 21, 0, 44, 31, 0, 14, + 26, 24, 23, 25, 4, 33, 1, 0, 34, 44, + 35, 42, 39, 40, 0, 31, 44, 40, 43, 0, + 31, 41, 29, 27, 28, 32, 38, 30, 36, 31, + 37, 5, 44, 16, 15, 18, 19, 17, 45}; + +const int grammar::goto_default [] = { + 3, 2, 13, 26, 36, 41, 10, 27, 61, 29, + 64, 63, 23, 32, 31, 52, 55, 38, 39, 42, + 43, 59, 44, 0}; + +const int grammar::action_index [] = { + -22, -22, 54, 1, 5, 15, 20, -22, -1, 6, + -22, 3, 2, 35, -22, -22, -22, -22, -22, -22, + -22, -22, -22, 10, -22, 7, -22, 14, 9, -22, + -22, -22, 8, -22, -22, -22, 11, -2, -22, -22, + -22, -22, -3, 16, 13, 14, -22, 17, -22, 4, + 14, -22, -22, -22, -22, 14, -22, -22, -22, 14, + -22, -22, 0, -22, 12, -22, -22, -22, -22, + + 2, -24, -2, -24, -24, -24, -24, -24, -24, -24, + -24, -24, -24, -24, -24, -24, -24, -24, -24, -24, + -24, -24, -24, -24, -24, -24, -4, -24, -24, -24, + -24, -24, -14, -24, -24, -24, -24, -24, -24, -24, + -24, -24, -24, -24, -24, 0, -16, -15, -24, -24, + 15, -24, -24, -24, -24, -10, -24, -24, -24, 1, + -24, -24, -3, -24, -1, -24, -24, -24, -24}; + +const int grammar::action_info [] = { + 17, 68, 66, 20, 19, 51, 14, 18, 34, 30, + 62, 30, 37, 62, 40, 45, 15, 48, 48, 0, + 0, 16, 0, 0, 0, 0, 0, 49, 49, 0, + 46, 0, 0, 53, 54, 0, 0, 0, 0, 0, + 0, 0, 21, 0, 22, 0, 0, 24, 25, 28, + 0, 0, 0, 0, 0, 0, 0, 4, 5, 6, + 8, 0, 9, 0, 11, 0, 0, 0, 0, 12, + 0, 0, 0, 0, 0, 0, + + 33, 35, 65, 7, 47, 57, 50, 1, 58, 60, + 67, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 56, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0}; + +const int grammar::action_check [] = { + 1, 0, 2, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 16, 18, 1, 1, 1, -1, + -1, 1, -1, -1, -1, -1, -1, 11, 11, -1, + 17, -1, -1, 19, 20, -1, -1, -1, -1, -1, + -1, -1, 7, -1, 9, -1, -1, 12, 13, 14, + -1, -1, -1, -1, -1, -1, -1, 3, 4, 5, + 6, -1, 8, -1, 10, -1, -1, -1, -1, 15, + -1, -1, -1, -1, -1, -1, + + 14, 5, 5, 5, 20, 15, 21, 5, 8, 8, + 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, + -1, -1, -1, 8, -1, -1, -1, -1, -1, -1, + -1, -1, -1, -1, -1, -1, -1, -1, -1}; + diff --git a/util/qlalr/grammar_p.h b/util/qlalr/grammar_p.h new file mode 100644 index 0000000..a9a4172 --- /dev/null +++ b/util/qlalr/grammar_p.h @@ -0,0 +1,119 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QLALR project on Trolltech Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef GRAMMAR_P_H +#define GRAMMAR_P_H + +class grammar +{ +public: + enum { + EOF_SYMBOL = 0, + COLON = 16, + DECL = 19, + DECL_FILE = 3, + ERROR = 21, + EXPECT = 4, + EXPECT_RR = 5, + ID = 1, + IMPL = 20, + IMPL_FILE = 6, + LEFT = 7, + MERGED_OUTPUT = 8, + NONASSOC = 9, + OR = 17, + PARSER = 10, + PREC = 11, + RIGHT = 12, + SEMICOLON = 18, + START = 13, + STRING_LITERAL = 2, + TOKEN = 14, + TOKEN_PREFIX = 15, + + ACCEPT_STATE = 68, + RULE_COUNT = 45, + STATE_COUNT = 69, + TERMINAL_COUNT = 22, + NON_TERMINAL_COUNT = 24, + + GOTO_INDEX_OFFSET = 69, + GOTO_INFO_OFFSET = 76, + GOTO_CHECK_OFFSET = 76 + }; + + static const char *const spell []; + static const int lhs []; + static const int rhs []; + static const int goto_default []; + static const int action_default []; + static const int action_index []; + static const int action_info []; + static const int action_check []; + + inline int nt_action (int state, int nt) const + { + const int *const goto_index = &action_index [GOTO_INDEX_OFFSET]; + const int *const goto_check = &action_check [GOTO_CHECK_OFFSET]; + + const int yyn = goto_index [state] + nt; + + if (yyn < 0 || goto_check [yyn] != nt) + return goto_default [nt]; + + const int *const goto_info = &action_info [GOTO_INFO_OFFSET]; + return goto_info [yyn]; + } + + inline int t_action (int state, int token) const + { + const int yyn = action_index [state] + token; + + if (yyn < 0 || action_check [yyn] != token) + return - action_default [state]; + + return action_info [yyn]; + } +}; + + +#endif // GRAMMAR_P_H + diff --git a/util/qlalr/lalr.cpp b/util/qlalr/lalr.cpp new file mode 100644 index 0000000..51c2674 --- /dev/null +++ b/util/qlalr/lalr.cpp @@ -0,0 +1,783 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QLALR project on Trolltech Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + + +#include "lalr.h" +#include <limits.h> + +#include <algorithm> + +#define QLALR_NO_DEBUG_NULLABLES +#define QLALR_NO_DEBUG_LOOKBACKS +#define QLALR_NO_DEBUG_DIRECT_READS +#define QLALR_NO_DEBUG_READS +#define QLALR_NO_DEBUG_INCLUDES +#define QLALR_NO_DEBUG_LOOKAHEADS + +QT_BEGIN_NAMESPACE +QTextStream qerr (stderr, QIODevice::WriteOnly); +QTextStream qout (stdout, QIODevice::WriteOnly); + +bool operator < (Name a, Name b) +{ + return *a < *b; +} + +bool operator < (ItemPointer a, ItemPointer b) +{ + return &*a < &*b; +} + +bool operator < (StatePointer a, StatePointer b) +{ + return &*a < &*b; +} +QT_END_NAMESPACE + +bool Read::operator < (const Read &other) const +{ + if (state == other.state) + return nt < other.nt; + + return state < other.state; +} + +bool Include::operator < (const Include &other) const +{ + if (state == other.state) + return nt < other.nt; + + return state < other.state; +} + +bool Lookback::operator < (const Lookback &other) const +{ + if (state == other.state) + return nt < other.nt; + + return state < other.state; +} + +QTextStream &operator << (QTextStream &out, const Name &n) +{ + return out << *n; +} + +QTextStream &operator << (QTextStream &out, const Rule &r) +{ + out << *r.lhs << " ::="; + + for (NameList::const_iterator name = r.rhs.begin (); name != r.rhs.end (); ++name) + out << " " << **name; + + return out; +} + +QTextStream &operator << (QTextStream &out, const NameSet &ns) +{ + out << "{"; + + for (NameSet::const_iterator n = ns.begin (); n != ns.end (); ++n) + { + if (n != ns.begin ()) + out << ", "; + + out << *n; + } + + return out << "}"; +} + +Item Item::next () const +{ + Q_ASSERT (! isReduceItem ()); + + Item n; + n.rule = rule; + n.dot = dot; + ++n.dot; + + return n; +} + +QTextStream &operator << (QTextStream &out, const Item &item) +{ + RulePointer r = item.rule; + + out << *r->lhs << ":"; + for (NameList::iterator name = r->rhs.begin (); name != r->rhs.end (); ++name) + { + out << " "; + + if (item.dot == name) + out << ". "; + + out << **name; + } + + if (item.isReduceItem ()) + out << " ."; + + return out; +} + +State::State (Grammar *g): + defaultReduce (g->rules.end ()) +{ +} + +QPair<ItemPointer, bool> State::insert (const Item &item) +{ + ItemPointer it = qFind (kernel.begin (), kernel.end (), item); + + if (it != kernel.end ()) + return qMakePair (it, false); + + return qMakePair (kernel.insert (it, item), true); +} + +QPair<ItemPointer, bool> State::insertClosure (const Item &item) +{ + ItemPointer it = qFind (closure.begin (), closure.end (), item); + + if (it != closure.end ()) + return qMakePair (it, false); + + return qMakePair (closure.insert (it, item), true); +} + + +///////////////////////////////////////////////////////////// +// Grammar +///////////////////////////////////////////////////////////// +Grammar::Grammar (): + start (names.end ()) +{ + expected_shift_reduce = 0; + expected_reduce_reduce = 0; + current_prec = 0; + current_assoc = NonAssoc; + + table_name = QLatin1String ("parser_table"); + + tk_end = intern ("$end"); + terminals.insert (tk_end); + spells.insert (tk_end, "end of file"); + + /*tk_error= terminals.insert (intern ("error"))*/; +} + +Name Grammar::intern (const QString &id) +{ + Name name = qFind (names.begin (), names.end (), id); + + if (name == names.end ()) + name = names.insert (names.end (), id); + + return name; +} + +void Grammar::buildRuleMap () +{ + NameSet undefined; + for (RulePointer rule = rules.begin (); rule != rules.end (); ++rule) + { + for (NameList::iterator it = rule->rhs.begin (); it != rule->rhs.end (); ++it) + { + Name name = *it; + if (isTerminal (name) || declared_lhs.find (name) != declared_lhs.end () + || undefined.find (name) != undefined.end ()) + continue; + + undefined.insert(name); + fprintf (stderr, "*** Warning. Symbol `%s' is not defined\n", qPrintable (*name)); + } + + rule_map.insert (rule->lhs, rule); + } +} + +void Grammar::buildExtendedGrammar () +{ + accept_symbol = intern ("$accept"); + goal = rules.insert (rules.end (), Rule ()); + goal->lhs = accept_symbol; + goal->rhs.push_back (start); + goal->rhs.push_back (tk_end); + + non_terminals.insert (accept_symbol); +} + +struct _Nullable: public std::unary_function<Name, bool> +{ + Automaton *_M_automaton; + + _Nullable (Automaton *aut): + _M_automaton (aut) {} + + bool operator () (Name name) const + { return _M_automaton->nullables.find (name) != _M_automaton->nullables.end (); } +}; + +Automaton::Automaton (Grammar *g): + _M_grammar (g), + start (states.end ()) +{ +} + +int Automaton::id (RulePointer rule) +{ + return 1 + std::distance (_M_grammar->rules.begin (), rule); +} + +int Automaton::id (Name name) +{ + return std::distance (_M_grammar->names.begin (), name); +} + +int Automaton::id (StatePointer state) +{ + return std::distance (states.begin (), state); +} + +void Automaton::build () +{ + Item item; + item.rule = _M_grammar->goal; + item.dot = _M_grammar->goal->rhs.begin (); + + State tmp (_M_grammar); + tmp.insert (item); + start = internState (tmp).first; + + closure (start); + + buildNullables (); + buildLookbackSets (); + buildReads (); + buildIncludesAndFollows (); + buildLookaheads (); + buildDefaultReduceActions (); +} + +void Automaton::buildNullables () +{ + bool changed = true; + + while (changed) + { + changed = false; + + for (RulePointer rule = _M_grammar->rules.begin (); rule != _M_grammar->rules.end (); ++rule) + { + NameList::iterator nn = std::find_if (rule->rhs.begin (), rule->rhs.end (), std::not1 (_Nullable (this))); + + if (nn == rule->rhs.end ()) + changed |= nullables.insert (rule->lhs).second; + } + } + +#ifndef QLALR_NO_DEBUG_NULLABLES + qerr << "nullables = {" << nullables << endl; +#endif +} + +QPair<StatePointer, bool> Automaton::internState (const State &state) +{ + StatePointer it = qFind (states.begin (), states.end (), state); + + if (it != states.end ()) + return qMakePair (it, false); + + return qMakePair (states.insert (it, state), true); +} + +struct _Bucket +{ + QLinkedList<ItemPointer> items; + + void insert (ItemPointer item) + { items.push_back (item); } + + State toState (Automaton *aut) + { + State st (aut->_M_grammar); + + for (QLinkedList<ItemPointer>::iterator item = items.begin (); item != items.end (); ++item) + st.insert ((*item)->next ()); + + return st; + } +}; + +void Automaton::closure (StatePointer state) +{ + if (! state->closure.empty ()) // ### not true. + return; + + typedef QMap<Name, _Bucket> bucket_map_type; + + bucket_map_type buckets; + QStack<ItemPointer> working_list; + + for (ItemPointer item = state->kernel.begin (); item != state->kernel.end (); ++item) + working_list.push (item); + + state->closure = state->kernel; + + while (! working_list.empty ()) + { + ItemPointer item = working_list.top (); + working_list.pop (); + + if (item->isReduceItem ()) + continue; + + buckets [*item->dot].insert (item); + + if (_M_grammar->isNonTerminal (*item->dot)) + { + foreach (RulePointer rule, _M_grammar->rule_map.values (*item->dot)) + { + Item ii; + ii.rule = rule; + ii.dot = rule->rhs.begin (); + + QPair<ItemPointer, bool> r = state->insertClosure (ii); + + if (r.second) + working_list.push (r.first); + } + } + } + + QList<StatePointer> todo; + + for (bucket_map_type::iterator bucket = buckets.begin (); bucket != buckets.end (); ++bucket) + { + QPair<StatePointer, bool> r = internState (bucket->toState (this)); + + StatePointer target = r.first; + + if (r.second) + todo.push_back (target); + + state->bundle.insert (bucket.key(), target); + } + + while (! todo.empty ()) + { + closure (todo.front ()); + todo.pop_front (); + } +} + +void Automaton::buildLookbackSets () +{ + for (StatePointer p = states.begin (); p != states.end (); ++p) + { + for (Bundle::iterator a = p->bundle.begin (); a != p->bundle.end (); ++a) + { + Name A = a.key (); + + if (! _M_grammar->isNonTerminal (A)) + continue; + + foreach (RulePointer rule, _M_grammar->rule_map.values (A)) + { + StatePointer q = p; + + for (NameList::iterator dot = rule->rhs.begin (); dot != rule->rhs.end (); ++dot) + q = q->bundle.value (*dot, states.end ()); + + Q_ASSERT (q != states.end ()); + + ItemPointer item = q->closure.begin (); + + for (; item != q->closure.end (); ++item) + { + if (item->rule == rule && item->dot == item->end_rhs ()) + break; + } + + if (item == q->closure.end ()) + { + Q_ASSERT (q == p); + Q_ASSERT (rule->rhs.begin () == rule->rhs.end ()); + + for (item = q->closure.begin (); item != q->closure.end (); ++item) + { + if (item->rule == rule && item->dot == item->end_rhs ()) + break; + } + } + + Q_ASSERT (item != q->closure.end ()); + + lookbacks.insert (item, Lookback (p, A)); + +#ifndef QLALR_NO_DEBUG_LOOKBACKS + qerr << "*** (" << id (q) << ", " << *rule << ") lookback (" << id (p) << ", " << *A << ")" << endl; +#endif + } + } + } +} + +void Automaton::buildDirectReads () +{ + for (StatePointer q = states.begin (); q != states.end (); ++q) + { + for (Bundle::iterator a = q->bundle.begin (); a != q->bundle.end (); ++a) + { + if (! _M_grammar->isNonTerminal (a.key ())) + continue; + + StatePointer r = a.value (); + + for (Bundle::iterator z = r->bundle.begin (); z != r->bundle.end (); ++z) + { + Name sym = z.key (); + + if (! _M_grammar->isTerminal (sym)) + continue; + + q->reads [a.key ()].insert (sym); + } + } + +#ifndef QLALR_NO_DEBUG_DIRECT_READS + for (QMap<Name, NameSet>::iterator dr = q->reads.begin (); dr != q->reads.end (); ++dr) + qerr << "*** DR(" << id (q) << ", " << dr.key () << ") = " << dr.value () << endl; +#endif + } +} + +void Automaton::buildReadsDigraph () +{ + for (StatePointer q = states.begin (); q != states.end (); ++q) + { + for (Bundle::iterator a = q->bundle.begin (); a != q->bundle.end (); ++a) + { + if (! _M_grammar->isNonTerminal (a.key ())) + continue; + + StatePointer r = a.value (); + + for (Bundle::iterator z = r->bundle.begin (); z != r->bundle.end (); ++z) + { + Name sym = z.key (); + + if (! _M_grammar->isNonTerminal(sym) || nullables.find (sym) == nullables.end ()) + continue; + + ReadsGraph::iterator source = ReadsGraph::get (Read (q, a.key ())); + ReadsGraph::iterator target = ReadsGraph::get (Read (r, sym)); + + source->insertEdge (target); + +#ifndef QLALR_NO_DEBUG_READS + qerr << "*** "; + dump (qerr, source); + qerr << " reads "; + dump (qerr, target); + qerr << endl; +#endif + } + } + } +} + +void Automaton::buildReads () +{ + buildDirectReads (); + buildReadsDigraph (); + + _M_reads_dfn = 0; + + for (ReadsGraph::iterator node = ReadsGraph::begin_nodes (); node != ReadsGraph::end_nodes (); ++node) + { + if (! node->root) + continue; + + visitReadNode (node); + } + + for (ReadsGraph::iterator node = ReadsGraph::begin_nodes (); node != ReadsGraph::end_nodes (); ++node) + visitReadNode (node); +} + +void Automaton::visitReadNode (ReadNode node) +{ + if (node->dfn != 0) + return; // nothing to do + + int N = node->dfn = ++_M_reads_dfn; + _M_reads_stack.push (node); + +#ifndef QLALR_NO_DEBUG_INCLUDES + // qerr << "*** Debug. visit node (" << id (node->data.state) << ", " << node->data.nt << ") N = " << N << endl; +#endif + + for (ReadsGraph::edge_iterator edge = node->begin (); edge != node->end (); ++edge) + { + ReadsGraph::iterator r = *edge; + Name nt = r->data.nt; + + visitReadNode (r); + + node->dfn = qMin (N, r->dfn); + + NameSet &dst = node->data.state->reads [node->data.nt]; + NameSet &src = r->data.state->reads [r->data.nt]; + dst.insert (src.begin (), src.end ()); + } + + if (node->dfn == N) + { + ReadsGraph::iterator tos = _M_reads_stack.top (); + + do { + tos = _M_reads_stack.top (); + _M_reads_stack.pop (); + tos->dfn = INT_MAX; + } while (tos != node); + } +} + +void Automaton::buildIncludesAndFollows () +{ + for (StatePointer p = states.begin (); p != states.end (); ++p) + p->follows = p->reads; + + buildIncludesDigraph (); + + _M_includes_dfn = 0; + + for (IncludesGraph::iterator node = IncludesGraph::begin_nodes (); node != IncludesGraph::end_nodes (); ++node) + { + if (! node->root) + continue; + + visitIncludeNode (node); + } + + for (IncludesGraph::iterator node = IncludesGraph::begin_nodes (); node != IncludesGraph::end_nodes (); ++node) + visitIncludeNode (node); +} + +void Automaton::buildIncludesDigraph () +{ + for (StatePointer pp = states.begin (); pp != states.end (); ++pp) + { + for (Bundle::iterator a = pp->bundle.begin (); a != pp->bundle.end (); ++a) + { + Name name = a.key (); + + if (! _M_grammar->isNonTerminal (name)) + continue; + + foreach (RulePointer rule, _M_grammar->rule_map.values (name)) + { + StatePointer p = pp; + + for (NameList::iterator A = rule->rhs.begin (); A != rule->rhs.end (); ++A) + { + NameList::iterator dot = A; + ++dot; + + if (_M_grammar->isNonTerminal (*A) && dot == rule->rhs.end ()) + { + // found an include edge. + IncludesGraph::iterator target = IncludesGraph::get (Include (pp, name)); + IncludesGraph::iterator source = IncludesGraph::get (Include (p, *A)); + + source->insertEdge (target); + +#ifndef QLALR_NO_DEBUG_INCLUDES + qerr << "*** (" << id (p) << ", " << *A << ") includes (" << id (pp) << ", " << *name << ")" << endl; +#endif // QLALR_NO_DEBUG_INCLUDES + + continue; + } + + p = p->bundle.value (*A); + + if (! _M_grammar->isNonTerminal (*A)) + continue; + + NameList::iterator first_not_nullable = std::find_if (dot, rule->rhs.end (), std::not1 (_Nullable (this))); + if (first_not_nullable != rule->rhs.end ()) + continue; + + // found an include edge. + IncludesGraph::iterator target = IncludesGraph::get (Include (pp, name)); + IncludesGraph::iterator source = IncludesGraph::get (Include (p, *A)); + + source->insertEdge (target); + +#ifndef QLALR_NO_DEBUG_INCLUDES + qerr << "*** (" << id (p) << ", " << *A << ") includes (" << id (pp) << ", " << *name << ")" << endl; +#endif // QLALR_NO_DEBUG_INCLUDES + } + } + } + } +} + +void Automaton::visitIncludeNode (IncludeNode node) +{ + if (node->dfn != 0) + return; // nothing to do + + int N = node->dfn = ++_M_includes_dfn; + _M_includes_stack.push (node); + +#ifndef QLALR_NO_DEBUG_INCLUDES + // qerr << "*** Debug. visit node (" << id (node->data.state) << ", " << node->data.nt << ") N = " << N << endl; +#endif + + for (IncludesGraph::edge_iterator edge = node->begin (); edge != node->end (); ++edge) + { + IncludesGraph::iterator r = *edge; + Name nt = r->data.nt; + + visitIncludeNode (r); + + node->dfn = qMin (N, r->dfn); + +#ifndef QLALR_NO_DEBUG_INCLUDES + qerr << "*** Merge. follows"; + dump (qerr, node); + qerr << " += follows"; + dump (qerr, r); + qerr << endl; +#endif + + NameSet &dst = node->data.state->follows [node->data.nt]; + NameSet &src = r->data.state->follows [r->data.nt]; + + dst.insert (src.begin (), src.end ()); + } + + if (node->dfn == N) + { + IncludesGraph::iterator tos = _M_includes_stack.top (); + + do { + tos = _M_includes_stack.top (); + _M_includes_stack.pop (); + tos->dfn = INT_MAX; + } while (tos != node); + } +} + +void Automaton::buildLookaheads () +{ + for (StatePointer p = states.begin (); p != states.end (); ++p) + { + for (ItemPointer item = p->closure.begin (); item != p->closure.end (); ++item) + { + foreach (Lookback lookback, lookbacks.values (item)) + { + StatePointer q = lookback.state; + +#ifndef QLALR_NO_DEBUG_LOOKAHEADS + qerr << "(" << id (p) << ", " << *item->rule << ") lookbacks "; + dump (qerr, lookback); + qerr << " with follows (" << id (q) << ", " << lookback.nt << ") = " << q->follows [lookback.nt] << endl; +#endif + + lookaheads [item].insert (q->follows [lookback.nt].begin (), q->follows [lookback.nt].end ()); + } + } + + // propagate the lookahead in the kernel + ItemPointer k = p->kernel.begin (); + ItemPointer c = p->closure.begin (); + + for (; k != p->kernel.end (); ++k, ++c) + lookaheads [k] = lookaheads [c]; + } +} + +void Automaton::buildDefaultReduceActions () +{ + for (StatePointer state = states.begin (); state != states.end (); ++state) + { + ItemPointer def = state->closure.end (); + int size = -1; + + for (ItemPointer item = state->closure.begin (); item != state->closure.end (); ++item) + { + if (item->dot != item->end_rhs ()) + continue; + + int la = lookaheads.value (item).size (); + if (def == state->closure.end () || la > size) + { + def = item; + size = la; + } + } + + if (def != state->closure.end ()) + { + Q_ASSERT (size >= 0); + state->defaultReduce = def->rule; + } + } +} + +void Automaton::dump (QTextStream &out, IncludeNode incl) +{ + out << "(" << id (incl->data.state) << ", " << incl->data.nt << ")"; +} + +void Automaton::dump (QTextStream &out, ReadNode rd) +{ + out << "(" << id (rd->data.state) << ", " << rd->data.nt << ")"; +} + +void Automaton::dump (QTextStream &out, const Lookback &lp) +{ + out << "(" << id (lp.state) << ", " << lp.nt << ")"; +} diff --git a/util/qlalr/lalr.g b/util/qlalr/lalr.g new file mode 100644 index 0000000..ed2ef86 --- /dev/null +++ b/util/qlalr/lalr.g @@ -0,0 +1,803 @@ +----------------------------------------------------------------------------- +-- +-- Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +-- Contact: Qt Software Information (qt-info@nokia.com) +-- +-- This file is part of the QLALR project on Trolltech Labs. +-- +-- $QT_BEGIN_LICENSE:LGPL$ +-- No Commercial Usage +-- This file contains pre-release code and may not be distributed. +-- You may use this file in accordance with the terms and conditions +-- contained in the either Technology Preview License Agreement or the +-- Beta Release License Agreement. +-- +-- GNU Lesser General Public License Usage +-- Alternatively, this file may be used under the terms of the GNU Lesser +-- General Public License version 2.1 as published by the Free Software +-- Foundation and appearing in the file LICENSE.LGPL included in the +-- packaging of this file. Please review the following information to +-- ensure the GNU Lesser General Public License version 2.1 requirements +-- will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +-- +-- In addition, as a special exception, Nokia gives you certain +-- additional rights. These rights are described in the Nokia Qt LGPL +-- Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +-- package. +-- +-- GNU General Public License Usage +-- Alternatively, this file may be used under the terms of the GNU +-- General Public License version 3.0 as published by the Free Software +-- Foundation and appearing in the file LICENSE.GPL included in the +-- packaging of this file. Please review the following information to +-- ensure the GNU General Public License version 3.0 requirements will be +-- met: http://www.gnu.org/copyleft/gpl.html. +-- +-- If you are unsure which license is appropriate for your use, please +-- contact the sales department at qt-sales@nokia.com. +-- $QT_END_LICENSE$ +-- +-- This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +-- WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +-- +----------------------------------------------------------------------------- + + +%parser grammar + +%decl recognizer.h +%impl recognizer.cpp + +%token ID "identifier" +%token STRING_LITERAL "string literal" + +%token DECL_FILE "%decl" +%token EXPECT "%expect" +%token EXPECT_RR "%expect-lr" +%token IMPL_FILE "%impl" +%token LEFT "%left" +%token MERGED_OUTPUT "%merged_output" +%token NONASSOC "%nonassoc" +%token PARSER "%parser" +%token PREC "%prec" +%token RIGHT "%right" +%token START "%start" +%token TOKEN "%token" +%token TOKEN_PREFIX "%token_prefix" + +%token COLON ":" +%token OR "|" +%token SEMICOLON ";" + +%token DECL +%token IMPL + +%token ERROR + +%start Specification + + +/: +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the <your project> project on Trolltech Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include <QtCore/QtDebug> +#include <QtCore/QString> +#include <QtCore/QFile> +#include <QtCore/QTextStream> + +#include "$header" +#include "lalr.h" + +#include <cstdlib> + +class Recognizer: protected $table +{ +public: + Recognizer (Grammar *grammar, bool no_lines); + ~Recognizer(); + + bool parse (const QString &input_file = QString ()); + + inline QString decls () const { return _M_decls; } + inline QString impls () const { return _M_impls; } + +protected: + inline void reallocateStack (); + + inline QString &sym (int index) + { return sym_stack [tos + index - 1]; } + +protected: // scanner + int nextToken(); + + inline void inp () + { + if (_M_currentChar != _M_lastChar) + { + ch = *_M_currentChar++; + + if (ch == QLatin1Char('\n')) + ++_M_line; + } + else + ch = QChar(); + } + + QString expand (const QString &text) const; + +protected: + // recognizer + int tos; + int stack_size; + QVector<QString> sym_stack; + int *state_stack; + + QString _M_contents; + QString::const_iterator _M_firstChar; + QString::const_iterator _M_lastChar; + QString::const_iterator _M_currentChar; + + // scanner + QChar ch; + int _M_line; + int _M_action_line; + Grammar *_M_grammar; + RulePointer _M_current_rule; + QString _M_input_file; + + QString _M_decls; + QString _M_impls; + QString _M_current_value; + bool _M_no_lines; +}; +:/ + +/. +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the <your project> project on Trolltech Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "recognizer.h" +#include <cstdlib> +#include <cstring> +#include <cctype> + +Recognizer::Recognizer (Grammar *grammar, bool no_lines): + tos(0), + stack_size(0), + state_stack(0), + _M_line(1), + _M_action_line(0), + _M_grammar(grammar), + _M_no_lines(no_lines) +{ +} + +Recognizer::~Recognizer() +{ + if (stack_size) + ::qFree(state_stack); +} + +inline void Recognizer::reallocateStack() +{ + if (! stack_size) + stack_size = 128; + else + stack_size <<= 1; + + sym_stack.resize (stack_size); + + if (! state_stack) + state_stack = reinterpret_cast<int*> (::qMalloc(stack_size * sizeof(int))); + else + state_stack = reinterpret_cast<int*> (::qRealloc(state_stack, stack_size * sizeof(int))); +} + +int Recognizer::nextToken() +{ + QString text; + + Lagain: + while (ch.isSpace ()) + inp (); + + if (ch.isNull ()) + return EOF_SYMBOL; + + int token = ch.unicode (); + + if (token == '"') + { + inp(); // skip " + text.clear (); + while (! ch.isNull () && ch != QLatin1Char ('"')) + { + if (ch == QLatin1Char ('\\')) + { + text += ch; + inp(); + } + text += ch; + inp (); + } + + if (ch == QLatin1Char ('"')) + inp (); + else + qerr << _M_input_file << ":" << _M_line << ": Warning. Expected `\"'" << endl; + + _M_current_value = text; + return (token = STRING_LITERAL); + } + + else if (ch.isLetterOrNumber () || ch == QLatin1Char ('_')) + { + text.clear (); + do { text += ch; inp (); } + while (ch.isLetterOrNumber () || ch == QLatin1Char ('_') || ch == QLatin1Char ('.')); + _M_current_value = text; + return (token = ID); + } + + else if (token == '%') + { + text.clear (); + + do { inp (); } + while (ch.isSpace ()); + + do { text += ch; inp (); } + while (ch.isLetterOrNumber () || ch == QLatin1Char ('_') || ch == QLatin1Char ('-')); + + if (text == QLatin1String("token_prefix")) + return (token = TOKEN_PREFIX); + else if (text == QLatin1String("merged_output")) + return (token = MERGED_OUTPUT); + else if (text == QLatin1String("token")) + return (token = TOKEN); + else if (text == QLatin1String("start")) + return (token = START); + else if (text == QLatin1String("parser")) + return (token = PARSER); + else if (text == QLatin1String("decl")) + return (token = DECL_FILE); + else if (text == QLatin1String("impl")) + return (token = IMPL_FILE); + else if (text == QLatin1String("expect")) + return (token = EXPECT); + else if (text == QLatin1String("expect-rr")) + return (token = EXPECT_RR); + else if (text == QLatin1String("left")) + return (token = LEFT); + else if (text == QLatin1String("right")) + return (token = RIGHT); + else if (text == QLatin1String("nonassoc")) + return (token = NONASSOC); + else if (text == QLatin1String("prec")) + return (token = PREC); + else + { + qerr << _M_input_file << ":" << _M_line << ": Unknown keyword `" << text << "'" << endl; + exit (EXIT_FAILURE); + return (token = ERROR); + } + } + + inp (); + + if (token == '-' && ch == QLatin1Char ('-')) + { + do { inp (); } + while (! ch.isNull () && ch != QLatin1Char ('\n')); + goto Lagain; + } + + else if (token == ':' && ch == QLatin1Char (':')) + { + inp (); + if (ch != QLatin1Char ('=')) + return (token = ERROR); + inp (); + return (token = COLON); + } + + else if (token == '/' && ch == QLatin1Char (':')) + { + _M_action_line = _M_line; + + text.clear (); + if (! _M_no_lines) + text += QLatin1String ("\n#line ") + QString::number (_M_action_line) + " \"" + _M_input_file + "\"\n"; + inp (); // skip ':' + + forever + { + while (! ch.isNull ()) + { + token = ch.unicode (); + inp (); + + if (token == ':' && ch == QLatin1Char ('/')) + break; + + text += QLatin1Char (token); + } + + if (ch != QLatin1Char ('/')) + return (token = ERROR); + + inp (); + + if (ch.isNull () || ch.isSpace ()) + { + _M_current_value = text; + return (token = DECL); + } + else + text += QLatin1String (":/"); + } + } + + else if (token == '/' && ch == QLatin1Char ('.')) + { + _M_action_line = _M_line; + + text.clear (); + if (! _M_no_lines) + text += QLatin1String ("\n#line ") + QString::number (_M_action_line) + " \"" + _M_input_file + "\"\n"; + + inp (); // skip ':' + + forever + { + while (! ch.isNull ()) + { + token = ch.unicode (); + inp (); + + if (token == '.' && ch == QLatin1Char ('/')) + break; + + text += QLatin1Char (token); + } + + if (ch != QLatin1Char ('/')) + return (token = ERROR); + + inp (); + + if (ch.isNull () || ch.isSpace ()) + { + _M_current_value = text; + return (token = IMPL); + } + else + text += QLatin1String ("./"); + } + } + + switch (token) { + case ':': + return (token = COLON); + + case ';': + return (token = SEMICOLON); + + case '|': + return (token = OR); + + default: + break; + } + + return token; +} + +bool Recognizer::parse (const QString &input_file) +{ + _M_input_file = input_file; + + QFile file(_M_input_file); + if (! file.open(QFile::ReadOnly)) + { + qerr << "qlalr: no input file\n"; + return false; + } + + QString _M_contents = QTextStream(&file).readAll(); + _M_firstChar = _M_contents.constBegin(); + _M_lastChar = _M_contents.constEnd(); + _M_currentChar = _M_firstChar; + _M_line = 1; + + int yytoken = -1; + inp (); + + reallocateStack(); + + _M_current_rule = _M_grammar->rules.end (); + _M_decls.clear (); + _M_impls.clear (); + + tos = 0; + state_stack[++tos] = 0; + + while (true) + { + if (yytoken == -1 && - TERMINAL_COUNT != action_index [state_stack [tos]]) + yytoken = nextToken(); + + int act = t_action (state_stack [tos], yytoken); + + if (act == ACCEPT_STATE) + return true; + + else if (act > 0) + { + if (++tos == stack_size) + reallocateStack(); + + sym_stack [tos] = _M_current_value; + state_stack [tos] = act; + yytoken = -1; + } + + else if (act < 0) + { + int r = - act - 1; + + tos -= rhs [r]; + act = state_stack [tos++]; + + switch (r) { +./ + +----------------------------------------------------------- SPECS +Specification ::= Options Tokens Start Rules ; + +Options ::= Empty ; +Options ::= Options Option ; + +StartHeader ::= START ID ; +/. +case $rule_number: { + Name name = _M_grammar->intern (sym(2)); + _M_grammar->start = name; + _M_grammar->non_terminals.insert (name); +} break; +./ + +Start ::= StartHeader UserActionOpt ; + +----------------------------------------------------------- OPTIONS +Option ::= PARSER ID ; +/. +case $rule_number: { + _M_grammar->table_name = sym(2); +} break; +./ + +Option ::= MERGED_OUTPUT ID ; +/. +case $rule_number: { + _M_grammar->merged_output = sym(2); +} break; +./ + +Option ::= DECL_FILE ID ; +/. +case $rule_number: { + _M_grammar->decl_file_name = sym(2); +} break; +./ + + +Option ::= IMPL_FILE ID ; +/. +case $rule_number: { + _M_grammar->impl_file_name = sym(2); +} break; +./ + +Option ::= EXPECT ID ; +/. +case $rule_number: { + _M_grammar->expected_shift_reduce = sym(2).toInt(); +} break; +./ + +Option ::= EXPECT_RR ID ; +/. +case $rule_number: { + _M_grammar->expected_reduce_reduce = sym(2).toInt(); +} break; +./ + + +Option ::= TOKEN_PREFIX ID ; +/. +case $rule_number: { + _M_grammar->token_prefix = sym(2); +} break; +./ + + +----------------------------------------------------------- TOKENS +Tokens ::= Empty ; +Tokens ::= Tokens Token ; + +Token ::= TOKEN TerminalList ; + +TerminalList ::= Terminal ; + +TerminalList ::= TerminalList Terminal ; + +Terminal ::= ID Empty ; +/.case $rule_number:./ + +Terminal ::= ID STRING_LITERAL ; +/.case $rule_number: { + Name name = _M_grammar->intern (sym(1)); + _M_grammar->terminals.insert (name); + _M_grammar->spells.insert (name, sym(2)); +} break; +./ + +PrecHeader: LEFT ; +/. +case $rule_number: { + _M_grammar->current_assoc = Grammar::Left; + ++_M_grammar->current_prec; +} break; +./ + +PrecHeader: RIGHT ; +/. +case $rule_number: { + _M_grammar->current_assoc = Grammar::Right; + ++_M_grammar->current_prec; +} break; +./ + +PrecHeader: NONASSOC ; +/. +case $rule_number: { + _M_grammar->current_assoc = Grammar::NonAssoc; + ++_M_grammar->current_prec; +} break; +./ + +Token ::= PrecHeader TokenList ; + +TokenList ::= TokenId ; +TokenList ::= TokenList TokenId ; + +TokenId ::= ID ; +/. +case $rule_number: { + Name name = _M_grammar->intern (sym(1)); + _M_grammar->terminals.insert (name); + + Grammar::TokenInfo info; + info.prec = _M_grammar->current_prec; + info.assoc = _M_grammar->current_assoc; + _M_grammar->token_info.insert (name, info); +} break; +./ + +----------------------------------------------------------- Code +Code ::= DECL ; +/. +case $rule_number: { + _M_decls += expand (sym(1)); +} break; +./ + + +Code ::= IMPL ; +/. +case $rule_number: { + _M_impls += expand (sym(1)); +} break; +./ + +UserAction ::= Code ; +UserAction ::= UserAction Code ; + +UserActionOpt ::= ; +UserActionOpt ::= UserAction ; + +----------------------------------------------------------- RULES +Rules ::= Empty ; +Rules ::= Rules Rule ; + +RuleHeader ::= ID COLON ; +/. +case $rule_number: { + _M_current_rule = _M_grammar->rules.insert (_M_grammar->rules.end (), Rule ()); + _M_current_rule->lhs = _M_grammar->intern (sym(1)); + _M_grammar->declared_lhs.insert (_M_current_rule->lhs); + + if (_M_grammar->terminals.find (_M_current_rule->lhs) != _M_grammar->terminals.end ()) + { + qerr << _M_input_file << ":" << _M_line << ": Invalid non terminal `" << *_M_current_rule->lhs << "'" << endl; + return false; + } + + _M_grammar->non_terminals.insert (_M_current_rule->lhs); +} break; +./ + + +Rule ::= RuleHeader RuleDefinition SEMICOLON UserActionOpt ; + +RuleDefinition ::= Symbols PrecOpt UserActionOpt ; +RuleDefinition ::= RuleDefinition NewRule OR Symbols PrecOpt UserActionOpt ; + +NewRule ::= ; +/. +case $rule_number: { + Name lhs = _M_current_rule->lhs; + _M_current_rule = _M_grammar->rules.insert (_M_grammar->rules.end (), Rule ()); + _M_current_rule->lhs = lhs; + _M_grammar->declared_lhs.insert (_M_current_rule->lhs); + + if (_M_grammar->terminals.find (_M_current_rule->lhs) != _M_grammar->terminals.end ()) + { + qerr << _M_input_file << ":" << _M_line << ": Invalid non terminal `" << *_M_current_rule->lhs << "'" << endl; + return false; + } + + _M_grammar->non_terminals.insert (_M_current_rule->lhs); +} break; +./ + +PrecOpt ::= ; +/. +case $rule_number: { + _M_current_rule->prec = _M_grammar->names.end (); + + for (NameList::iterator it = _M_current_rule->rhs.begin (); it != _M_current_rule->rhs.end (); ++it) + { + if (! _M_grammar->isTerminal (*it)) + continue; + + _M_current_rule->prec = *it; + } +} break; +./ + +PrecOpt ::= PREC ID ; +/. +case $rule_number: { + Name tok = _M_grammar->intern (sym(2)); + if (! _M_grammar->isTerminal (tok)) + { + qerr << _M_input_file << ":" << _M_line << ": `" << *tok << " is not a terminal symbol" << endl; + _M_current_rule->prec = _M_grammar->names.end (); + } + else + _M_current_rule->prec = tok; +} break; +./ + +----------------------------------------------------------- SYMBOLS +Symbols ::= Empty ; +Symbols ::= Symbols ID ; +/. +case $rule_number: { + Name name = _M_grammar->intern (sym(2)); + + if (_M_grammar->terminals.find (name) == _M_grammar->terminals.end ()) + _M_grammar->non_terminals.insert (name); + + _M_current_rule->rhs.push_back (name); +} break; +./ + +----------------------------------------------------------- HELPERS +Empty ::= ; +/. +case $rule_number: { + sym(1) = QString(); +} break; +./ + + + + +----------------------------------------------------------- END +/. + } // switch + + state_stack [tos] = nt_action (act, lhs [r] - TERMINAL_COUNT); + } + + else + { + break; + } + } + + qerr << _M_input_file << ":" << _M_line << ": Syntax error" << endl; + return false; +} + +./ diff --git a/util/qlalr/lalr.h b/util/qlalr/lalr.h new file mode 100644 index 0000000..29bb522 --- /dev/null +++ b/util/qlalr/lalr.h @@ -0,0 +1,502 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QLALR project on Trolltech Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef LALR_H +#define LALR_H + +#include <functional> + +#include <QtCore/QSet> +#include <QtCore/QStack> +#include <QtCore/QMap> +#include <QtCore/QLinkedList> +#include <QtCore/QString> +#include <QtCore/QTextStream> +#include <QtCore/QPair> + +class Rule; +class State; +class Grammar; +class Item; +class State; +class Arrow; +class Automaton; + +template <typename _Tp > +class OrderedSet : protected QMap<_Tp, bool> +{ + typedef QMap<_Tp, bool> _Base; + +public: + class const_iterator + { + typename _Base::const_iterator _M_iterator; + + public: + const_iterator () {} + + const_iterator (const typename _Base::const_iterator &it): + _M_iterator (it) {} + + const _Tp &operator * () const + { return _M_iterator.key (); } + + const _Tp *operator -> () const + { return &_M_iterator.key (); } + + const_iterator &operator ++ () + { ++_M_iterator; return *this; } + + const_iterator operator ++ (int) const + { + const_iterator me (*this); + ++_M_iterator; + return me; + } + + bool operator == (const const_iterator &other) const + { return _M_iterator == other._M_iterator; } + + bool operator != (const const_iterator &other) const + { return _M_iterator != other._M_iterator; } + }; + + typedef const_iterator iterator; + +public: + OrderedSet () {} + + const_iterator begin () const + { return const_iterator (_Base::begin ()); } + + const_iterator end () const + { return const_iterator (_Base::end ()); } + + bool isEmpty () const + { return _Base::isEmpty (); } + + int size () const + { return _Base::size (); } + + const_iterator find (const _Tp &elt) const + { return const_iterator (_Base::find (elt)); } + + QPair<const_iterator, bool> insert (const _Tp &elt) + { + int elts = _Base::size (); + const_iterator it (_Base::insert (typename _Base::key_type (elt), true)); + return qMakePair (it, elts != _Base::size ()); + } + + QPair<const_iterator, bool> insert (const_iterator, const _Tp &elt) + { + int elts = _Base::size (); + const_iterator it (_Base::insert (typename _Base::key_type (elt), true)); + return qMakePair (it, elts != _Base::size ()); + } + + const _Tp &operator [] (const _Tp &elt) + { return *insert (elt)->first; } + + template <typename _InputIterator> + void insert (_InputIterator first, _InputIterator last) + { + for (; first != last; ++first) + insert (*first); + } +}; + +// names +typedef QLinkedList<QString>::iterator Name; +typedef QLinkedList<Name> NameList; +typedef OrderedSet<Name> NameSet; + +// items +typedef QLinkedList<Item> ItemList; +typedef ItemList::iterator ItemPointer; + +// rules +typedef QLinkedList<Rule> debug_infot; +typedef debug_infot::iterator RulePointer; +typedef QMultiMap<Name, RulePointer> RuleMap; + +// states +typedef QLinkedList<State> StateList; +typedef StateList::iterator StatePointer; + +// arrows +typedef QMap<Name, StatePointer> Bundle; + +class Rule +{ +public: + void clear () + { + lhs = Name (); + rhs.clear (); + prec = Name (); + } + +public: + Name lhs; + NameList rhs; + Name prec; +}; + +class Lookback +{ +public: + Lookback (StatePointer s, Name n): + state (s), nt (n) {} + + inline bool operator == (const Lookback &other) const + { return state == other.state && nt == other.nt; } + + inline bool operator != (const Lookback &other) const + { return state != other.state || nt != other.nt; } + + bool operator < (const Lookback &other) const; + +public: + StatePointer state; + Name nt; +}; + +class Item +{ +public: + inline NameList::iterator begin_rhs () const + { return rule->rhs.begin (); } + + inline NameList::iterator end_rhs () const + { return rule->rhs.end (); } + + inline bool operator == (const Item &other) const + { return rule == other.rule && dot == other.dot; } + + inline bool operator != (const Item &other) const + { return rule != other.rule || dot != other.dot; } + + inline bool isReduceItem () const + { return dot == rule->rhs.end (); } + + Item next () const; + +public: + RulePointer rule; + NameList::iterator dot; +}; + +class State +{ +public: + State (Grammar *grammar); + + inline bool operator == (const State &other) const + { return kernel == other.kernel; } + + inline bool operator != (const State &other) const + { return kernel != other.kernel; } + + QPair<ItemPointer, bool> insert (const Item &item); + QPair<ItemPointer, bool> insertClosure (const Item &item); + +public: // attributes + ItemList kernel; + ItemList closure; + Bundle bundle; + QMap<Name, NameSet> reads; + QMap<Name, NameSet> follows; + RulePointer defaultReduce; +}; + +///////////////////////////////////////////////////////////// +// digraph +///////////////////////////////////////////////////////////// +template <typename _Tp> +class Node +{ +public: + typedef OrderedSet<Node<_Tp> > Repository; + typedef typename Repository::iterator iterator; + typedef typename QLinkedList<iterator>::iterator edge_iterator; + +public: + static iterator get (_Tp data); + + QPair<edge_iterator, bool> insertEdge (iterator other) const; + + inline edge_iterator begin () const + { return outs.begin (); } + + inline edge_iterator end () const + { return outs.end (); } + + inline bool operator == (const Node<_Tp> &other) const + { return data == other.data; } + + inline bool operator != (const Node<_Tp> &other) const + { return data != other.data; } + + inline bool operator < (const Node<_Tp> &other) const + { return data < other.data; } + + static inline iterator begin_nodes () + { return repository ().begin (); } + + static inline iterator end_nodes () + { return repository ().end (); } + + static Repository &repository () + { + static Repository r; + return r; + } + +public: // attributes + mutable bool root; + mutable int dfn; + mutable _Tp data; + mutable QLinkedList<iterator> outs; + +protected: + inline Node () {} + + inline Node (_Tp d): + root (true), dfn (0), data (d) {} +}; + +template <typename _Tp> +typename Node<_Tp>::iterator Node<_Tp>::get (_Tp data) +{ + Node<_Tp> tmp (data); + iterator it = repository ().find (tmp); + + if (it != repository ().end ()) + return it; + + return repository ().insert (tmp).first; +} + +template <typename _Tp> +QPair<typename QLinkedList<typename Node<_Tp>::iterator>::iterator, bool> Node<_Tp>::insertEdge (typename Node<_Tp>::iterator other) const +{ + edge_iterator it = qFind (outs.begin (), outs.end (), other); + + if (it != outs.end ()) + return qMakePair (it, false); + + other->root = false; + return qMakePair (outs.insert (outs.end (), other), true); +} + +///////////////////////////////////////////////////////////// +// Grammar +///////////////////////////////////////////////////////////// +class Grammar +{ +public: + Grammar (); + + Name intern (const QString &id); + + inline bool isTerminal (Name name) const + { return terminals.find (name) != terminals.end (); } + + inline bool isNonTerminal (Name name) const + { return non_terminals.find (name) != non_terminals.end (); } + + void buildRuleMap (); + void buildExtendedGrammar (); + +public: + QString merged_output; + QString table_name; + QString decl_file_name; + QString impl_file_name; + QString token_prefix; + QLinkedList<QString> names; + Name start; + NameSet terminals; + NameSet non_terminals; + QMap<Name, QString> spells; + debug_infot rules; + RuleMap rule_map; + RulePointer goal; + Name tk_end; + Name accept_symbol; + NameSet declared_lhs; + int expected_shift_reduce; + int expected_reduce_reduce; + + enum Assoc { + NonAssoc, + Left, + Right + }; + + struct TokenInfo { + Assoc assoc; + int prec; + }; + + QMap<Name, TokenInfo> token_info; + Assoc current_assoc; + int current_prec; +}; + +class Read +{ +public: + inline Read () {} + + inline Read (StatePointer s, Name n): + state (s), nt (n) {} + + inline bool operator == (const Read &other) const + { return state == other.state && nt == other.nt; } + + inline bool operator != (const Read &other) const + { return state != other.state || nt != other.nt; } + + bool operator < (const Read &other) const; + +public: + StatePointer state; + Name nt; +}; + +class Include +{ +public: + inline Include () {} + + inline Include (StatePointer s, Name n): + state (s), nt (n) {} + + inline bool operator == (const Include &other) const + { return state == other.state && nt == other.nt; } + + inline bool operator != (const Include &other) const + { return state != other.state || nt != other.nt; } + + bool operator < (const Include &other) const; + +public: + StatePointer state; + Name nt; +}; + +class Automaton +{ +public: + Automaton (Grammar *g); + + QPair<StatePointer, bool> internState (const State &state); + + typedef Node<Read> ReadsGraph; + typedef ReadsGraph::iterator ReadNode; + + typedef Node<Include> IncludesGraph; + typedef IncludesGraph::iterator IncludeNode; + + void build (); + void buildNullables (); + + void buildLookbackSets (); + + void buildDirectReads (); + void buildReadsDigraph (); + void buildReads (); + void visitReadNode (ReadNode node); + + void buildIncludesAndFollows (); + void buildIncludesDigraph (); + void visitIncludeNode (IncludeNode node); + + void buildLookaheads (); + + void buildDefaultReduceActions (); + + void closure (StatePointer state); + + int id (RulePointer rule); + int id (StatePointer state); + int id (Name name); + + void dump (QTextStream &out, IncludeNode incl); + void dump (QTextStream &out, ReadNode rd); + void dump (QTextStream &out, const Lookback &lp); + +public: // ### private + Grammar *_M_grammar; + StateList states; + StatePointer start; + NameSet nullables; + QMultiMap<ItemPointer, Lookback> lookbacks; + QMap<ItemPointer, NameSet> lookaheads; + +private: + QStack<ReadsGraph::iterator> _M_reads_stack; + int _M_reads_dfn; + + QStack<IncludesGraph::iterator> _M_includes_stack; + int _M_includes_dfn; +}; + +QT_BEGIN_NAMESPACE +bool operator < (Name a, Name b); +bool operator < (StatePointer a, StatePointer b); +bool operator < (ItemPointer a, ItemPointer b); +QT_END_NAMESPACE + +QTextStream &operator << (QTextStream &out, const Name &n); +QTextStream &operator << (QTextStream &out, const Rule &r); +QTextStream &operator << (QTextStream &out, const Item &item); +QTextStream &operator << (QTextStream &out, const NameSet &ns); + +QT_BEGIN_NAMESPACE +// ... hmm +extern QTextStream qerr; +extern QTextStream qout; +QT_END_NAMESPACE + +#endif // LALR_H diff --git a/util/qlalr/main.cpp b/util/qlalr/main.cpp new file mode 100644 index 0000000..91c72bb --- /dev/null +++ b/util/qlalr/main.cpp @@ -0,0 +1,185 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QLALR project on Trolltech Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include <QtCore/QCoreApplication> +#include <QtCore/QFile> +#include <QtCore/QStringList> +#include <QtCore/QtDebug> + +#include <cstdlib> + +#include "lalr.h" +#include "dotgraph.h" +#include "parsetable.h" +#include "cppgenerator.h" +#include "recognizer.h" + +#define QLALR_NO_DEBUG_TABLE +#define QLALR_NO_DEBUG_DOT + +static void help_me () +{ + qerr << "Usage: qlalr [options] [input file name]" << endl + << endl + << " --help, -h\t\tdisplay this help and exit" << endl + << " --verbose, -v\t\tverbose output" << endl + << " --no-debug\t\tno debug information" << endl + << " --no-lines\t\tno #line directives" << endl + << " --dot\t\t\tgenerate a graph" << endl + << " --troll\t\tadd the Trolltech copyright header" << endl + << endl; + exit (0); +} + +int main (int argc, char *argv[]) +{ + QCoreApplication app (argc, argv); + + bool generate_dot = false; + bool generate_report = false; + bool no_lines = false; + bool debug_info = true; + bool troll_copyright = false; + QString file_name = 0; + + QStringList args = app.arguments (); + args.removeFirst (); + + foreach (QString arg, args) + { + if (arg == QLatin1String ("-h") || arg == QLatin1String ("--help")) + help_me (); + + else if (arg == QLatin1String ("-v") || arg == QLatin1String ("--verbose")) + generate_report = true; + + else if (arg == QLatin1String ("--dot")) + generate_dot = true; + + else if (arg == QLatin1String ("--no-lines")) + no_lines = true; + + else if (arg == QLatin1String ("--no-debug")) + debug_info = false; + + else if (arg == QLatin1String ("--troll")) + troll_copyright = true; + + else if (file_name.isEmpty ()) + file_name = arg; + + else + qerr << "*** Warning. Ignore argument `" << arg << "'" << endl; + } + + if (file_name.isEmpty ()) + { + help_me (); + exit (EXIT_SUCCESS); + } + + Grammar grammar; + Recognizer p (&grammar, no_lines); + + if (! p.parse (file_name)) + exit (EXIT_FAILURE); + + if (grammar.rules.isEmpty ()) + { + qerr << "*** Fatal. No rules!" << endl; + exit (EXIT_FAILURE); + } + + else if (grammar.start == grammar.names.end ()) + { + qerr << "*** Fatal. No start symbol!" << endl; + exit (EXIT_FAILURE); + } + + grammar.buildExtendedGrammar (); + grammar.buildRuleMap (); + + Automaton aut (&grammar); + aut.build (); + + CppGenerator gen (p, grammar, aut, generate_report); + gen.setDebugInfo (debug_info); + gen.setTrollCopyright (troll_copyright); + gen (); + + if (generate_dot) + { + DotGraph genDotFile (qout); + genDotFile (&aut); + } + + else if (generate_report) + { + ParseTable genParseTable (qout); + genParseTable(&aut); + } + + return EXIT_SUCCESS; +} + +QString Recognizer::expand (const QString &text) const +{ + QString code = text; + + if (_M_grammar->start != _M_grammar->names.end ()) + { + code = code.replace (QLatin1String("$start_id"), QString::number (std::distance (_M_grammar->names.begin (), _M_grammar->start))); + code = code.replace (QLatin1String("$start"), *_M_grammar->start); + } + + code = code.replace (QLatin1String("$header"), _M_grammar->table_name.toLower () + QLatin1String("_p.h")); + + code = code.replace (QLatin1String("$table"), _M_grammar->table_name); + code = code.replace (QLatin1String("$parser"), _M_grammar->table_name); + + if (_M_current_rule != _M_grammar->rules.end ()) + { + code = code.replace (QLatin1String("$rule_number"), QString::number (std::distance (_M_grammar->rules.begin (), _M_current_rule))); + code = code.replace (QLatin1String("$rule"), *_M_current_rule->lhs); + } + + return code; +} diff --git a/util/qlalr/parsetable.cpp b/util/qlalr/parsetable.cpp new file mode 100644 index 0000000..c117071 --- /dev/null +++ b/util/qlalr/parsetable.cpp @@ -0,0 +1,127 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QLALR project on Trolltech Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + + +#include <QtCore/QTextStream> +#include "lalr.h" +#include "parsetable.h" + +ParseTable::ParseTable (QTextStream &o): + out (o) +{ +} + +void ParseTable::operator () (Automaton *aut) +{ + Grammar *g = aut->_M_grammar; + + int rindex = 1; + for (RulePointer rule = g->rules.begin (); rule != g->rules.end (); ++rule) + out << rindex++ << ")\t" << *rule << endl; + out << endl << endl; + + int index = 0; + for (StatePointer state = aut->states.begin (); state != aut->states.end (); ++state) + { + out << "state " << index++ << endl << endl; + + for (ItemPointer item = state->kernel.begin (); item != state->kernel.end (); ++item) + { + out << " * " << *item; + + if (item->dot == item->end_rhs ()) + out << " " << aut->lookaheads [item]; + + out << endl; + } + + bool first = true; + for (Bundle::iterator arrow = state->bundle.begin (); arrow != state->bundle.end (); ++arrow) + { + if (! g->isTerminal (arrow.key ())) + continue; + + if (first) + out << endl; + + first = false; + + out << " " << *arrow.key () << " shift, and go to state " << std::distance (aut->states.begin (), *arrow) << endl; + } + + first = true; + for (ItemPointer item = state->closure.begin (); item != state->closure.end (); ++item) + { + if (item->dot != item->end_rhs () || item->rule == state->defaultReduce) + continue; + + if (first) + out << endl; + + first = false; + + foreach (Name la, aut->lookaheads.value (item)) + out << " " << *la << " reduce using rule " << aut->id (item->rule) << " (" << *item->rule->lhs << ")" << endl; + } + + first = true; + for (Bundle::iterator arrow = state->bundle.begin (); arrow != state->bundle.end (); ++arrow) + { + if (! g->isNonTerminal (arrow.key ())) + continue; + + if (first) + out << endl; + + first = false; + + out << " " << *arrow.key () << " go to state " << std::distance (aut->states.begin (), *arrow) << endl; + } + + if (state->defaultReduce != g->rules.end ()) + { + out << endl + << " $default reduce using rule " << aut->id (state->defaultReduce) << " (" << *state->defaultReduce->lhs << ")" << endl; + } + + out << endl; + } +} diff --git a/util/qlalr/parsetable.h b/util/qlalr/parsetable.h new file mode 100644 index 0000000..36f6926 --- /dev/null +++ b/util/qlalr/parsetable.h @@ -0,0 +1,59 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QLALR project on Trolltech Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef PARSETABLE_H +#define PARSETABLE_H + +QT_FORWARD_DECLARE_CLASS(QTextStream); +class Automaton; + +class ParseTable +{ +public: + ParseTable (QTextStream &out); + + void operator () (Automaton *a); + +private: + QTextStream &out; +}; + +#endif // PARSETABLE_H diff --git a/util/qlalr/qlalr.pro b/util/qlalr/qlalr.pro new file mode 100644 index 0000000..881a36a --- /dev/null +++ b/util/qlalr/qlalr.pro @@ -0,0 +1,21 @@ + +TEMPLATE = app +QT = core +TARGET = qlalr +mac:CONFIG -= app_bundle + +SOURCES += compress.cpp \ + cppgenerator.cpp \ + dotgraph.cpp \ + lalr.cpp \ + main.cpp \ + parsetable.cpp \ + recognizer.cpp \ + grammar.cpp + +HEADERS += compress.h \ + cppgenerator.h \ + dotgraph.h \ + lalr.h \ + parsetable.h \ + grammar_p.h diff --git a/util/qlalr/recognizer.cpp b/util/qlalr/recognizer.cpp new file mode 100644 index 0000000..5a7ad3b --- /dev/null +++ b/util/qlalr/recognizer.cpp @@ -0,0 +1,489 @@ + +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the <your project> project on Trolltech Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "recognizer.h" +#include <cstdlib> +#include <cstring> +#include <cctype> + +Recognizer::Recognizer (Grammar *grammar, bool no_lines): + tos(0), + stack_size(0), + state_stack(0), + _M_line(1), + _M_action_line(0), + _M_grammar(grammar), + _M_no_lines(no_lines) +{ +} + +Recognizer::~Recognizer() +{ + if (stack_size) + ::qFree(state_stack); +} + +inline void Recognizer::reallocateStack() +{ + if (! stack_size) + stack_size = 128; + else + stack_size <<= 1; + + sym_stack.resize (stack_size); + + if (! state_stack) + state_stack = reinterpret_cast<int*> (::qMalloc(stack_size * sizeof(int))); + else + state_stack = reinterpret_cast<int*> (::qRealloc(state_stack, stack_size * sizeof(int))); +} + +int Recognizer::nextToken() +{ + QString text; + + Lagain: + while (ch.isSpace ()) + inp (); + + if (ch.isNull ()) + return EOF_SYMBOL; + + int token = ch.unicode (); + + if (token == '"') + { + inp(); // skip " + text.clear (); + while (! ch.isNull () && ch != QLatin1Char ('"')) + { + if (ch == QLatin1Char ('\\')) + { + text += ch; + inp(); + } + text += ch; + inp (); + } + + if (ch == QLatin1Char ('"')) + inp (); + else + qerr << _M_input_file << ":" << _M_line << ": Warning. Expected `\"'" << endl; + + _M_current_value = text; + return (token = STRING_LITERAL); + } + + else if (ch.isLetterOrNumber () || ch == QLatin1Char ('_')) + { + text.clear (); + do { text += ch; inp (); } + while (ch.isLetterOrNumber () || ch == QLatin1Char ('_') || ch == QLatin1Char ('.')); + _M_current_value = text; + return (token = ID); + } + + else if (token == '%') + { + text.clear (); + + do { inp (); } + while (ch.isSpace ()); + + do { text += ch; inp (); } + while (ch.isLetterOrNumber () || ch == QLatin1Char ('_') || ch == QLatin1Char ('-')); + + if (text == QLatin1String("token_prefix")) + return (token = TOKEN_PREFIX); + else if (text == QLatin1String("merged_output")) + return (token = MERGED_OUTPUT); + else if (text == QLatin1String("token")) + return (token = TOKEN); + else if (text == QLatin1String("start")) + return (token = START); + else if (text == QLatin1String("parser")) + return (token = PARSER); + else if (text == QLatin1String("decl")) + return (token = DECL_FILE); + else if (text == QLatin1String("impl")) + return (token = IMPL_FILE); + else if (text == QLatin1String("expect")) + return (token = EXPECT); + else if (text == QLatin1String("expect-rr")) + return (token = EXPECT_RR); + else if (text == QLatin1String("left")) + return (token = LEFT); + else if (text == QLatin1String("right")) + return (token = RIGHT); + else if (text == QLatin1String("nonassoc")) + return (token = NONASSOC); + else if (text == QLatin1String("prec")) + return (token = PREC); + else + { + qerr << _M_input_file << ":" << _M_line << ": Unknown keyword `" << text << "'" << endl; + exit (EXIT_FAILURE); + return (token = ERROR); + } + } + + inp (); + + if (token == '-' && ch == QLatin1Char ('-')) + { + do { inp (); } + while (! ch.isNull () && ch != QLatin1Char ('\n')); + goto Lagain; + } + + else if (token == ':' && ch == QLatin1Char (':')) + { + inp (); + if (ch != QLatin1Char ('=')) + return (token = ERROR); + inp (); + return (token = COLON); + } + + else if (token == '/' && ch == QLatin1Char (':')) + { + _M_action_line = _M_line; + + text.clear (); + if (! _M_no_lines) + text += QLatin1String ("\n#line ") + QString::number (_M_action_line) + " \"" + _M_input_file + "\"\n"; + inp (); // skip ':' + + forever + { + while (! ch.isNull ()) + { + token = ch.unicode (); + inp (); + + if (token == ':' && ch == QLatin1Char ('/')) + break; + + text += QLatin1Char (token); + } + + if (ch != QLatin1Char ('/')) + return (token = ERROR); + + inp (); + + if (ch.isNull () || ch.isSpace ()) + { + _M_current_value = text; + return (token = DECL); + } + else + text += QLatin1String (":/"); + } + } + + else if (token == '/' && ch == QLatin1Char ('.')) + { + _M_action_line = _M_line; + + text.clear (); + if (! _M_no_lines) + text += QLatin1String ("\n#line ") + QString::number (_M_action_line) + " \"" + _M_input_file + "\"\n"; + + inp (); // skip ':' + + forever + { + while (! ch.isNull ()) + { + token = ch.unicode (); + inp (); + + if (token == '.' && ch == QLatin1Char ('/')) + break; + + text += QLatin1Char (token); + } + + if (ch != QLatin1Char ('/')) + return (token = ERROR); + + inp (); + + if (ch.isNull () || ch.isSpace ()) + { + _M_current_value = text; + return (token = IMPL); + } + else + text += QLatin1String (""); + } + } + + switch (token) { + case ':': + return (token = COLON); + + case ';': + return (token = SEMICOLON); + + case '|': + return (token = OR); + + default: + break; + } + + return token; +} + +bool Recognizer::parse (const QString &input_file) +{ + _M_input_file = input_file; + + QFile file(_M_input_file); + if (! file.open(QFile::ReadOnly)) + { + qerr << "qlalr: no input file\n"; + return false; + } + + QString _M_contents = QTextStream(&file).readAll(); + _M_firstChar = _M_contents.constBegin(); + _M_lastChar = _M_contents.constEnd(); + _M_currentChar = _M_firstChar; + _M_line = 1; + + int yytoken = -1; + inp (); + + reallocateStack(); + + _M_current_rule = _M_grammar->rules.end (); + _M_decls.clear (); + _M_impls.clear (); + + tos = 0; + state_stack[++tos] = 0; + + while (true) + { + if (yytoken == -1 && - TERMINAL_COUNT != action_index [state_stack [tos]]) + yytoken = nextToken(); + + int act = t_action (state_stack [tos], yytoken); + + if (act == ACCEPT_STATE) + return true; + + else if (act > 0) + { + if (++tos == stack_size) + reallocateStack(); + + sym_stack [tos] = _M_current_value; + state_stack [tos] = act; + yytoken = -1; + } + + else if (act < 0) + { + int r = - act - 1; + + tos -= rhs [r]; + act = state_stack [tos++]; + + switch (r) { + +case 3: { + Name name = _M_grammar->intern (sym(2)); + _M_grammar->start = name; + _M_grammar->non_terminals.insert (name); +} break; + +case 5: { + _M_grammar->table_name = sym(2); +} break; + +case 6: { + _M_grammar->merged_output = sym(2); +} break; + +case 7: { + _M_grammar->decl_file_name = sym(2); +} break; + +case 8: { + _M_grammar->impl_file_name = sym(2); +} break; + +case 9: { + _M_grammar->expected_shift_reduce = sym(2).toInt(); +} break; + +case 10: { + _M_grammar->expected_reduce_reduce = sym(2).toInt(); +} break; + +case 11: { + _M_grammar->token_prefix = sym(2); +} break; +case 17:case 18: { + Name name = _M_grammar->intern (sym(1)); + _M_grammar->terminals.insert (name); + _M_grammar->spells.insert (name, sym(2)); +} break; + +case 19: { + _M_grammar->current_assoc = Grammar::Left; + ++_M_grammar->current_prec; +} break; + +case 20: { + _M_grammar->current_assoc = Grammar::Right; + ++_M_grammar->current_prec; +} break; + +case 21: { + _M_grammar->current_assoc = Grammar::NonAssoc; + ++_M_grammar->current_prec; +} break; + +case 25: { + Name name = _M_grammar->intern (sym(1)); + _M_grammar->terminals.insert (name); + + Grammar::TokenInfo info; + info.prec = _M_grammar->current_prec; + info.assoc = _M_grammar->current_assoc; + _M_grammar->token_info.insert (name, info); +} break; + +case 26: { + _M_decls += expand (sym(1)); +} break; + +case 27: { + _M_impls += expand (sym(1)); +} break; + +case 34: { + _M_current_rule = _M_grammar->rules.insert (_M_grammar->rules.end (), Rule ()); + _M_current_rule->lhs = _M_grammar->intern (sym(1)); + _M_grammar->declared_lhs.insert (_M_current_rule->lhs); + + if (_M_grammar->terminals.find (_M_current_rule->lhs) != _M_grammar->terminals.end ()) + { + qerr << _M_input_file << ":" << _M_line << ": Invalid non terminal `" << *_M_current_rule->lhs << "'" << endl; + return false; + } + + _M_grammar->non_terminals.insert (_M_current_rule->lhs); +} break; + +case 38: { + Name lhs = _M_current_rule->lhs; + _M_current_rule = _M_grammar->rules.insert (_M_grammar->rules.end (), Rule ()); + _M_current_rule->lhs = lhs; + _M_grammar->declared_lhs.insert (_M_current_rule->lhs); + + if (_M_grammar->terminals.find (_M_current_rule->lhs) != _M_grammar->terminals.end ()) + { + qerr << _M_input_file << ":" << _M_line << ": Invalid non terminal `" << *_M_current_rule->lhs << "'" << endl; + return false; + } + + _M_grammar->non_terminals.insert (_M_current_rule->lhs); +} break; + +case 39: { + _M_current_rule->prec = _M_grammar->names.end (); + + for (NameList::iterator it = _M_current_rule->rhs.begin (); it != _M_current_rule->rhs.end (); ++it) + { + if (! _M_grammar->isTerminal (*it)) + continue; + + _M_current_rule->prec = *it; + } +} break; + +case 40: { + Name tok = _M_grammar->intern (sym(2)); + if (! _M_grammar->isTerminal (tok)) + { + qerr << _M_input_file << ":" << _M_line << ": `" << *tok << " is not a terminal symbol" << endl; + _M_current_rule->prec = _M_grammar->names.end (); + } + else + _M_current_rule->prec = tok; +} break; + +case 42: { + Name name = _M_grammar->intern (sym(2)); + + if (_M_grammar->terminals.find (name) == _M_grammar->terminals.end ()) + _M_grammar->non_terminals.insert (name); + + _M_current_rule->rhs.push_back (name); +} break; + +case 43: { + sym(1) = QString(); +} break; + + } // switch + + state_stack [tos] = nt_action (act, lhs [r] - TERMINAL_COUNT); + } + + else + { + break; + } + } + + qerr << _M_input_file << ":" << _M_line << ": Syntax error" << endl; + return false; +} + diff --git a/util/qlalr/recognizer.h b/util/qlalr/recognizer.h new file mode 100644 index 0000000..c9be98f --- /dev/null +++ b/util/qlalr/recognizer.h @@ -0,0 +1,111 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QLALR project on Trolltech Labs. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include <QtCore/QtDebug> +#include <QtCore/QString> +#include <QtCore/QFile> +#include <QtCore/QTextStream> + +#include "grammar_p.h" +#include "lalr.h" + +#include <cstdlib> + +class Recognizer: protected grammar +{ +public: + Recognizer (Grammar *grammar, bool no_lines); + ~Recognizer(); + + bool parse (const QString &input_file = QString ()); + + inline QString decls () const { return _M_decls; } + inline QString impls () const { return _M_impls; } + +protected: + inline void reallocateStack (); + + inline QString &sym (int index) + { return sym_stack [tos + index - 1]; } + +protected: // scanner + int nextToken(); + + inline void inp () + { + if (_M_currentChar != _M_lastChar) + { + ch = *_M_currentChar++; + + if (ch == QLatin1Char('\n')) + ++_M_line; + } + else + ch = QChar(); + } + + QString expand (const QString &text) const; + +protected: + // recognizer + int tos; + int stack_size; + QVector<QString> sym_stack; + int *state_stack; + + QString _M_contents; + QString::const_iterator _M_firstChar; + QString::const_iterator _M_lastChar; + QString::const_iterator _M_currentChar; + + // scanner + QChar ch; + int _M_line; + int _M_action_line; + Grammar *_M_grammar; + RulePointer _M_current_rule; + QString _M_input_file; + + QString _M_decls; + QString _M_impls; + QString _M_current_value; + bool _M_no_lines; +}; |
