--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/util/qlalr/lalr.h Mon Jan 11 14:00:40 2010 +0000
@@ -0,0 +1,502 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the utils of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef LALR_H
+#define LALR_H
+
+#include <functional>
+
+#include <QtCore/QSet>
+#include <QtCore/QStack>
+#include <QtCore/QMap>
+#include <QtCore/QLinkedList>
+#include <QtCore/QString>
+#include <QtCore/QTextStream>
+#include <QtCore/QPair>
+
+class Rule;
+class State;
+class Grammar;
+class Item;
+class State;
+class Arrow;
+class Automaton;
+
+template <typename _Tp >
+class OrderedSet : protected QMap<_Tp, bool>
+{
+ typedef QMap<_Tp, bool> _Base;
+
+public:
+ class const_iterator
+ {
+ typename _Base::const_iterator _M_iterator;
+
+ public:
+ const_iterator () {}
+
+ const_iterator (const typename _Base::const_iterator &it):
+ _M_iterator (it) {}
+
+ const _Tp &operator * () const
+ { return _M_iterator.key (); }
+
+ const _Tp *operator -> () const
+ { return &_M_iterator.key (); }
+
+ const_iterator &operator ++ ()
+ { ++_M_iterator; return *this; }
+
+ const_iterator operator ++ (int) const
+ {
+ const_iterator me (*this);
+ ++_M_iterator;
+ return me;
+ }
+
+ bool operator == (const const_iterator &other) const
+ { return _M_iterator == other._M_iterator; }
+
+ bool operator != (const const_iterator &other) const
+ { return _M_iterator != other._M_iterator; }
+ };
+
+ typedef const_iterator iterator;
+
+public:
+ OrderedSet () {}
+
+ const_iterator begin () const
+ { return const_iterator (_Base::begin ()); }
+
+ const_iterator end () const
+ { return const_iterator (_Base::end ()); }
+
+ bool isEmpty () const
+ { return _Base::isEmpty (); }
+
+ int size () const
+ { return _Base::size (); }
+
+ const_iterator find (const _Tp &elt) const
+ { return const_iterator (_Base::find (elt)); }
+
+ QPair<const_iterator, bool> insert (const _Tp &elt)
+ {
+ int elts = _Base::size ();
+ const_iterator it (_Base::insert (typename _Base::key_type (elt), true));
+ return qMakePair (it, elts != _Base::size ());
+ }
+
+ QPair<const_iterator, bool> insert (const_iterator, const _Tp &elt)
+ {
+ int elts = _Base::size ();
+ const_iterator it (_Base::insert (typename _Base::key_type (elt), true));
+ return qMakePair (it, elts != _Base::size ());
+ }
+
+ const _Tp &operator [] (const _Tp &elt)
+ { return *insert (elt)->first; }
+
+ template <typename _InputIterator>
+ void insert (_InputIterator first, _InputIterator last)
+ {
+ for (; first != last; ++first)
+ insert (*first);
+ }
+};
+
+// names
+typedef QLinkedList<QString>::iterator Name;
+typedef QLinkedList<Name> NameList;
+typedef OrderedSet<Name> NameSet;
+
+// items
+typedef QLinkedList<Item> ItemList;
+typedef ItemList::iterator ItemPointer;
+
+// rules
+typedef QLinkedList<Rule> debug_infot;
+typedef debug_infot::iterator RulePointer;
+typedef QMultiMap<Name, RulePointer> RuleMap;
+
+// states
+typedef QLinkedList<State> StateList;
+typedef StateList::iterator StatePointer;
+
+// arrows
+typedef QMap<Name, StatePointer> Bundle;
+
+class Rule
+{
+public:
+ void clear ()
+ {
+ lhs = Name ();
+ rhs.clear ();
+ prec = Name ();
+ }
+
+public:
+ Name lhs;
+ NameList rhs;
+ Name prec;
+};
+
+class Lookback
+{
+public:
+ Lookback (StatePointer s, Name n):
+ state (s), nt (n) {}
+
+ inline bool operator == (const Lookback &other) const
+ { return state == other.state && nt == other.nt; }
+
+ inline bool operator != (const Lookback &other) const
+ { return state != other.state || nt != other.nt; }
+
+ bool operator < (const Lookback &other) const;
+
+public:
+ StatePointer state;
+ Name nt;
+};
+
+class Item
+{
+public:
+ inline NameList::iterator begin_rhs () const
+ { return rule->rhs.begin (); }
+
+ inline NameList::iterator end_rhs () const
+ { return rule->rhs.end (); }
+
+ inline bool operator == (const Item &other) const
+ { return rule == other.rule && dot == other.dot; }
+
+ inline bool operator != (const Item &other) const
+ { return rule != other.rule || dot != other.dot; }
+
+ inline bool isReduceItem () const
+ { return dot == rule->rhs.end (); }
+
+ Item next () const;
+
+public:
+ RulePointer rule;
+ NameList::iterator dot;
+};
+
+class State
+{
+public:
+ State (Grammar *grammar);
+
+ inline bool operator == (const State &other) const
+ { return kernel == other.kernel; }
+
+ inline bool operator != (const State &other) const
+ { return kernel != other.kernel; }
+
+ QPair<ItemPointer, bool> insert (const Item &item);
+ QPair<ItemPointer, bool> insertClosure (const Item &item);
+
+public: // attributes
+ ItemList kernel;
+ ItemList closure;
+ Bundle bundle;
+ QMap<Name, NameSet> reads;
+ QMap<Name, NameSet> follows;
+ RulePointer defaultReduce;
+};
+
+/////////////////////////////////////////////////////////////
+// digraph
+/////////////////////////////////////////////////////////////
+template <typename _Tp>
+class Node
+{
+public:
+ typedef OrderedSet<Node<_Tp> > Repository;
+ typedef typename Repository::iterator iterator;
+ typedef typename QLinkedList<iterator>::iterator edge_iterator;
+
+public:
+ static iterator get (_Tp data);
+
+ QPair<edge_iterator, bool> insertEdge (iterator other) const;
+
+ inline edge_iterator begin () const
+ { return outs.begin (); }
+
+ inline edge_iterator end () const
+ { return outs.end (); }
+
+ inline bool operator == (const Node<_Tp> &other) const
+ { return data == other.data; }
+
+ inline bool operator != (const Node<_Tp> &other) const
+ { return data != other.data; }
+
+ inline bool operator < (const Node<_Tp> &other) const
+ { return data < other.data; }
+
+ static inline iterator begin_nodes ()
+ { return repository ().begin (); }
+
+ static inline iterator end_nodes ()
+ { return repository ().end (); }
+
+ static Repository &repository ()
+ {
+ static Repository r;
+ return r;
+ }
+
+public: // attributes
+ mutable bool root;
+ mutable int dfn;
+ mutable _Tp data;
+ mutable QLinkedList<iterator> outs;
+
+protected:
+ inline Node () {}
+
+ inline Node (_Tp d):
+ root (true), dfn (0), data (d) {}
+};
+
+template <typename _Tp>
+typename Node<_Tp>::iterator Node<_Tp>::get (_Tp data)
+{
+ Node<_Tp> tmp (data);
+ iterator it = repository ().find (tmp);
+
+ if (it != repository ().end ())
+ return it;
+
+ return repository ().insert (tmp).first;
+}
+
+template <typename _Tp>
+QPair<typename QLinkedList<typename Node<_Tp>::iterator>::iterator, bool> Node<_Tp>::insertEdge (typename Node<_Tp>::iterator other) const
+{
+ edge_iterator it = qFind (outs.begin (), outs.end (), other);
+
+ if (it != outs.end ())
+ return qMakePair (it, false);
+
+ other->root = false;
+ return qMakePair (outs.insert (outs.end (), other), true);
+}
+
+/////////////////////////////////////////////////////////////
+// Grammar
+/////////////////////////////////////////////////////////////
+class Grammar
+{
+public:
+ Grammar ();
+
+ Name intern (const QString &id);
+
+ inline bool isTerminal (Name name) const
+ { return terminals.find (name) != terminals.end (); }
+
+ inline bool isNonTerminal (Name name) const
+ { return non_terminals.find (name) != non_terminals.end (); }
+
+ void buildRuleMap ();
+ void buildExtendedGrammar ();
+
+public:
+ QString merged_output;
+ QString table_name;
+ QString decl_file_name;
+ QString impl_file_name;
+ QString token_prefix;
+ QLinkedList<QString> names;
+ Name start;
+ NameSet terminals;
+ NameSet non_terminals;
+ QMap<Name, QString> spells;
+ debug_infot rules;
+ RuleMap rule_map;
+ RulePointer goal;
+ Name tk_end;
+ Name accept_symbol;
+ NameSet declared_lhs;
+ int expected_shift_reduce;
+ int expected_reduce_reduce;
+
+ enum Assoc {
+ NonAssoc,
+ Left,
+ Right
+ };
+
+ struct TokenInfo {
+ Assoc assoc;
+ int prec;
+ };
+
+ QMap<Name, TokenInfo> token_info;
+ Assoc current_assoc;
+ int current_prec;
+};
+
+class Read
+{
+public:
+ inline Read () {}
+
+ inline Read (StatePointer s, Name n):
+ state (s), nt (n) {}
+
+ inline bool operator == (const Read &other) const
+ { return state == other.state && nt == other.nt; }
+
+ inline bool operator != (const Read &other) const
+ { return state != other.state || nt != other.nt; }
+
+ bool operator < (const Read &other) const;
+
+public:
+ StatePointer state;
+ Name nt;
+};
+
+class Include
+{
+public:
+ inline Include () {}
+
+ inline Include (StatePointer s, Name n):
+ state (s), nt (n) {}
+
+ inline bool operator == (const Include &other) const
+ { return state == other.state && nt == other.nt; }
+
+ inline bool operator != (const Include &other) const
+ { return state != other.state || nt != other.nt; }
+
+ bool operator < (const Include &other) const;
+
+public:
+ StatePointer state;
+ Name nt;
+};
+
+class Automaton
+{
+public:
+ Automaton (Grammar *g);
+
+ QPair<StatePointer, bool> internState (const State &state);
+
+ typedef Node<Read> ReadsGraph;
+ typedef ReadsGraph::iterator ReadNode;
+
+ typedef Node<Include> IncludesGraph;
+ typedef IncludesGraph::iterator IncludeNode;
+
+ void build ();
+ void buildNullables ();
+
+ void buildLookbackSets ();
+
+ void buildDirectReads ();
+ void buildReadsDigraph ();
+ void buildReads ();
+ void visitReadNode (ReadNode node);
+
+ void buildIncludesAndFollows ();
+ void buildIncludesDigraph ();
+ void visitIncludeNode (IncludeNode node);
+
+ void buildLookaheads ();
+
+ void buildDefaultReduceActions ();
+
+ void closure (StatePointer state);
+
+ int id (RulePointer rule);
+ int id (StatePointer state);
+ int id (Name name);
+
+ void dump (QTextStream &out, IncludeNode incl);
+ void dump (QTextStream &out, ReadNode rd);
+ void dump (QTextStream &out, const Lookback &lp);
+
+public: // ### private
+ Grammar *_M_grammar;
+ StateList states;
+ StatePointer start;
+ NameSet nullables;
+ QMultiMap<ItemPointer, Lookback> lookbacks;
+ QMap<ItemPointer, NameSet> lookaheads;
+
+private:
+ QStack<ReadsGraph::iterator> _M_reads_stack;
+ int _M_reads_dfn;
+
+ QStack<IncludesGraph::iterator> _M_includes_stack;
+ int _M_includes_dfn;
+};
+
+QT_BEGIN_NAMESPACE
+bool operator < (Name a, Name b);
+bool operator < (StatePointer a, StatePointer b);
+bool operator < (ItemPointer a, ItemPointer b);
+QT_END_NAMESPACE
+
+QTextStream &operator << (QTextStream &out, const Name &n);
+QTextStream &operator << (QTextStream &out, const Rule &r);
+QTextStream &operator << (QTextStream &out, const Item &item);
+QTextStream &operator << (QTextStream &out, const NameSet &ns);
+
+QT_BEGIN_NAMESPACE
+// ... hmm
+extern QTextStream qerr;
+extern QTextStream qout;
+QT_END_NAMESPACE
+
+#endif // LALR_H