1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the utils of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #ifndef LALR_H

    43 #define LALR_H

    44 

    45 #include <functional>

    46 

    47 #include <QtCore/QSet>

    48 #include <QtCore/QStack>

    49 #include <QtCore/QMap>

    50 #include <QtCore/QLinkedList>

    51 #include <QtCore/QString>

    52 #include <QtCore/QTextStream>

    53 #include <QtCore/QPair>

    54 

    55 class Rule;

    56 class State;

    57 class Grammar;

    58 class Item;

    59 class State;

    60 class Arrow;

    61 class Automaton;

    62 

    63 template <typename _Tp >

    64 class OrderedSet : protected QMap<_Tp, bool>

    65 {

    66   typedef QMap<_Tp, bool> _Base;

    67 

    68 public:

    69   class const_iterator

    70   {

    71     typename _Base::const_iterator _M_iterator;

    72 

    73   public:

    74     const_iterator () {}

    75 

    76     const_iterator (const typename _Base::const_iterator &it):

    77       _M_iterator (it) {}

    78 

    79     const _Tp &operator * () const

    80     { return _M_iterator.key (); }

    81 

    82     const _Tp *operator -> () const

    83     { return &_M_iterator.key (); }

    84 

    85     const_iterator &operator ++ ()

    86     { ++_M_iterator; return *this; }

    87 

    88     const_iterator operator ++ (int) const

    89     {

    90       const_iterator me (*this);

    91       ++_M_iterator;

    92       return me;

    93     }

    94 

    95     bool operator == (const const_iterator &other) const

    96     { return _M_iterator == other._M_iterator; }

    97 

    98     bool operator != (const const_iterator &other) const

    99     { return _M_iterator != other._M_iterator; }

   100   };

   101 

   102   typedef const_iterator iterator;

   103 

   104 public:

   105   OrderedSet () {}

   106 

   107   const_iterator begin () const

   108   { return const_iterator (_Base::begin ()); }

   109 

   110   const_iterator end () const

   111   { return const_iterator (_Base::end ()); }

   112 

   113   bool isEmpty () const

   114   { return _Base::isEmpty (); }

   115 

   116   int size () const

   117   { return _Base::size (); }

   118 

   119   const_iterator find (const _Tp &elt) const

   120   { return const_iterator (_Base::find (elt)); }

   121 

   122   QPair<const_iterator, bool> insert (const _Tp &elt)

   123   {

   124     int elts = _Base::size ();

   125     const_iterator it (_Base::insert (typename _Base::key_type (elt), true));

   126     return qMakePair (it, elts != _Base::size ());

   127   }

   128 

   129   QPair<const_iterator, bool> insert (const_iterator, const _Tp &elt)

   130   {

   131     int elts = _Base::size ();

   132     const_iterator it (_Base::insert (typename _Base::key_type (elt), true));

   133     return qMakePair (it, elts != _Base::size ());

   134   }

   135 

   136   const _Tp &operator [] (const _Tp &elt)

   137   { return *insert (elt)->first; }

   138 

   139   template <typename _InputIterator>

   140   void insert (_InputIterator first, _InputIterator last)

   141   {

   142     for (; first != last; ++first)

   143       insert (*first);

   144   }

   145 };

   146 

   147 // names

   148 typedef QLinkedList<QString>::iterator Name;

   149 typedef QLinkedList<Name> NameList;

   150 typedef OrderedSet<Name> NameSet;

   151 

   152 // items

   153 typedef QLinkedList<Item> ItemList;

   154 typedef ItemList::iterator ItemPointer;

   155 

   156 // rules

   157 typedef QLinkedList<Rule> debug_infot;

   158 typedef debug_infot::iterator RulePointer;

   159 typedef QMultiMap<Name, RulePointer> RuleMap;

   160 

   161 // states

   162 typedef QLinkedList<State> StateList;

   163 typedef StateList::iterator StatePointer;

   164 

   165 // arrows

   166 typedef QMap<Name, StatePointer> Bundle;

   167 

   168 class Rule

   169 {

   170 public:

   171   void clear ()

   172   {

   173     lhs = Name ();

   174     rhs.clear ();

   175     prec = Name ();

   176   }

   177 

   178 public:

   179   Name lhs;

   180   NameList rhs;

   181   Name prec;

   182 };

   183 

   184 class Lookback

   185 {

   186 public:

   187   Lookback (StatePointer s, Name n):

   188     state (s), nt (n) {}

   189 

   190   inline bool operator == (const Lookback &other) const

   191   { return state == other.state && nt == other.nt; }

   192 

   193   inline bool operator != (const Lookback &other) const

   194   { return state != other.state || nt != other.nt; }

   195 

   196   bool operator < (const Lookback &other) const;

   197 

   198 public:

   199   StatePointer state;

   200   Name nt;

   201 };

   202 

   203 class Item

   204 {

   205 public:

   206   inline NameList::iterator begin_rhs () const

   207   { return rule->rhs.begin (); }

   208 

   209   inline NameList::iterator end_rhs () const

   210   { return rule->rhs.end (); }

   211 

   212   inline bool operator == (const Item &other) const

   213   { return rule == other.rule && dot == other.dot; }

   214 

   215   inline bool operator != (const Item &other) const

   216   { return rule != other.rule || dot != other.dot; }

   217 

   218   inline bool isReduceItem () const

   219   { return dot == rule->rhs.end (); }

   220 

   221   Item next () const;

   222 

   223 public:

   224   RulePointer rule;

   225   NameList::iterator dot;

   226 };

   227 

   228 class State

   229 {

   230 public:

   231   State (Grammar *grammar);

   232 

   233   inline bool operator == (const State &other) const

   234   { return kernel == other.kernel; }

   235 

   236   inline bool operator != (const State &other) const

   237   { return kernel != other.kernel; }

   238 

   239   QPair<ItemPointer, bool> insert (const Item &item);

   240   QPair<ItemPointer, bool> insertClosure (const Item &item);

   241 

   242 public: // attributes

   243   ItemList kernel;

   244   ItemList closure;

   245   Bundle bundle;

   246   QMap<Name, NameSet> reads;

   247   QMap<Name, NameSet> follows;

   248   RulePointer defaultReduce;

   249 };

   250 

   251 /////////////////////////////////////////////////////////////

   252 // digraph

   253 /////////////////////////////////////////////////////////////

   254 template <typename _Tp>

   255 class Node

   256 {

   257 public:

   258   typedef OrderedSet<Node<_Tp> > Repository;

   259   typedef typename Repository::iterator iterator;

   260   typedef typename QLinkedList<iterator>::iterator edge_iterator;

   261 

   262 public:

   263   static iterator get (_Tp data);

   264 

   265   QPair<edge_iterator, bool> insertEdge (iterator other) const;

   266 

   267   inline edge_iterator begin () const

   268   { return outs.begin (); }

   269 

   270   inline edge_iterator end () const

   271   { return outs.end (); }

   272 

   273   inline bool operator == (const Node<_Tp> &other) const

   274   { return data == other.data; }

   275 

   276   inline bool operator != (const Node<_Tp> &other) const

   277   { return data != other.data; }

   278 

   279   inline bool operator < (const Node<_Tp> &other) const

   280   { return data < other.data; }

   281 

   282   static inline iterator begin_nodes ()

   283   { return repository ().begin (); }

   284 

   285   static inline iterator end_nodes ()

   286   { return repository ().end (); }

   287 

   288   static Repository &repository ()

   289   {

   290     static Repository r;

   291     return r;

   292   }

   293 

   294 public: // attributes

   295   mutable bool root;

   296   mutable int dfn;

   297   mutable _Tp data;

   298   mutable QLinkedList<iterator> outs;

   299 

   300 protected:

   301   inline Node () {}

   302 

   303   inline Node (_Tp d):

   304     root (true), dfn (0), data (d) {}

   305 };

   306 

   307 template <typename _Tp>

   308 typename Node<_Tp>::iterator Node<_Tp>::get (_Tp data)

   309 {

   310   Node<_Tp> tmp (data);

   311   iterator it = repository ().find (tmp);

   312 

   313   if (it != repository ().end ())

   314     return it;

   315 

   316   return repository ().insert (tmp).first;

   317 }

   318 

   319 template <typename _Tp>

   320 QPair<typename QLinkedList<typename Node<_Tp>::iterator>::iterator, bool> Node<_Tp>::insertEdge (typename Node<_Tp>::iterator other) const

   321 {

   322   edge_iterator it = qFind (outs.begin (), outs.end (), other);

   323 

   324   if (it != outs.end ())

   325     return qMakePair (it, false);

   326 

   327   other->root = false;

   328   return qMakePair (outs.insert (outs.end (), other), true);

   329 }

   330 

   331 /////////////////////////////////////////////////////////////

   332 // Grammar

   333 /////////////////////////////////////////////////////////////

   334 class Grammar

   335 {

   336 public:

   337   Grammar ();

   338 

   339   Name intern (const QString &id);

   340 

   341   inline bool isTerminal (Name name) const

   342   { return terminals.find (name) != terminals.end (); }

   343 

   344   inline bool isNonTerminal (Name name) const

   345   { return non_terminals.find (name) != non_terminals.end (); }

   346 

   347   void buildRuleMap ();

   348   void buildExtendedGrammar ();

   349 

   350 public:

   351   QString merged_output;

   352   QString table_name;

   353   QString decl_file_name;

   354   QString impl_file_name;

   355   QString token_prefix;

   356   QLinkedList<QString> names;

   357   Name start;

   358   NameSet terminals;

   359   NameSet non_terminals;

   360   QMap<Name, QString> spells;

   361   debug_infot rules;

   362   RuleMap rule_map;

   363   RulePointer goal;

   364   Name tk_end;

   365   Name accept_symbol;

   366   NameSet declared_lhs;

   367   int expected_shift_reduce;

   368   int expected_reduce_reduce;

   369 

   370   enum Assoc {

   371     NonAssoc,

   372     Left,

   373     Right

   374   };

   375 

   376   struct TokenInfo {

   377     Assoc assoc;

   378     int prec;

   379   };

   380 

   381   QMap<Name, TokenInfo> token_info;

   382   Assoc current_assoc;

   383   int current_prec;

   384 };

   385 

   386 class Read

   387 {

   388 public:

   389   inline Read () {}

   390 

   391   inline Read (StatePointer s, Name n):

   392     state (s), nt (n) {}

   393 

   394   inline bool operator == (const Read &other) const

   395   { return state == other.state && nt == other.nt; }

   396 

   397   inline bool operator != (const Read &other) const

   398   { return state != other.state || nt != other.nt; }

   399 

   400   bool operator < (const Read &other) const;

   401 

   402 public:

   403   StatePointer state;

   404   Name nt;

   405 };

   406 

   407 class Include

   408 {

   409 public:

   410   inline Include () {}

   411 

   412   inline Include (StatePointer s, Name n):

   413     state (s), nt (n) {}

   414 

   415   inline bool operator == (const Include &other) const

   416   { return state == other.state && nt == other.nt; }

   417 

   418   inline bool operator != (const Include &other) const

   419   { return state != other.state || nt != other.nt; }

   420 

   421   bool operator < (const Include &other) const;

   422 

   423 public:

   424   StatePointer state;

   425   Name nt;

   426 };

   427 

   428 class Automaton

   429 {

   430 public:

   431   Automaton (Grammar *g);

   432 

   433   QPair<StatePointer, bool> internState (const State &state);

   434 

   435   typedef Node<Read> ReadsGraph;

   436   typedef ReadsGraph::iterator ReadNode;

   437 

   438   typedef Node<Include> IncludesGraph;

   439   typedef IncludesGraph::iterator IncludeNode;

   440 

   441   void build ();

   442   void buildNullables ();

   443 

   444   void buildLookbackSets ();

   445 

   446   void buildDirectReads ();

   447   void buildReadsDigraph ();

   448   void buildReads ();

   449   void visitReadNode (ReadNode node);

   450 

   451   void buildIncludesAndFollows ();

   452   void buildIncludesDigraph ();

   453   void visitIncludeNode (IncludeNode node);

   454 

   455   void buildLookaheads ();

   456 

   457   void buildDefaultReduceActions ();

   458 

   459   void closure (StatePointer state);

   460 

   461   int id (RulePointer rule);

   462   int id (StatePointer state);

   463   int id (Name name);

   464 

   465   void dump (QTextStream &out, IncludeNode incl);

   466   void dump (QTextStream &out, ReadNode rd);

   467   void dump (QTextStream &out, const Lookback &lp);

   468 

   469 public: // ### private

   470   Grammar *_M_grammar;

   471   StateList states;

   472   StatePointer start;

   473   NameSet nullables;

   474   QMultiMap<ItemPointer, Lookback> lookbacks;

   475   QMap<ItemPointer, NameSet> lookaheads;

   476 

   477 private:

   478   QStack<ReadsGraph::iterator> _M_reads_stack;

   479   int _M_reads_dfn;

   480 

   481   QStack<IncludesGraph::iterator> _M_includes_stack;

   482   int _M_includes_dfn;

   483 };

   484 

   485 QT_BEGIN_NAMESPACE

   486 bool operator < (Name a, Name b);

   487 bool operator < (StatePointer a, StatePointer b);

   488 bool operator < (ItemPointer a, ItemPointer b);

   489 QT_END_NAMESPACE

   490 

   491 QTextStream &operator << (QTextStream &out, const Name &n);

   492 QTextStream &operator << (QTextStream &out, const Rule &r);

   493 QTextStream &operator << (QTextStream &out, const Item &item);

   494 QTextStream &operator << (QTextStream &out, const NameSet &ns);

   495 

   496 QT_BEGIN_NAMESPACE

   497 // ... hmm

   498 extern QTextStream qerr;

   499 extern QTextStream qout;

   500 QT_END_NAMESPACE

   501 

   502 #endif // LALR_H