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 QLALR module 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 QPARSER_H

    43 #define QPARSER_H

    44 

    45 #include <QtCore/QSharedDataPointer>

    46 #include <QtCore/QVarLengthArray>

    47 

    48 template <typename _Parser, typename _Table, typename _Value = int>

    49 class QParser: protected _Table

    50 {

    51 public:

    52     QParser();

    53     ~QParser();

    54 

    55     bool parse();

    56 

    57     inline _Value &sym(int index);

    58 

    59 private:

    60     inline int nextToken()

    61     {

    62         return static_cast<_Parser*> (this)->nextToken();

    63     }

    64 

    65     inline void consumeRule(int rule)

    66     {

    67         static_cast<_Parser*> (this)->consumeRule(rule);

    68     }

    69 

    70     enum { DefaultStackSize = 128 };

    71 

    72     struct Data: public QSharedData

    73     {

    74         Data(): stackSize (DefaultStackSize), tos (0) {}

    75 

    76         QVarLengthArray<int, DefaultStackSize> stateStack;

    77         QVarLengthArray<_Value, DefaultStackSize> parseStack;

    78         int stackSize;

    79         int tos;

    80 

    81         void reallocateStack() {

    82             stackSize <<= 1;

    83             stateStack.resize(stackSize);

    84             parseStack.resize(stackSize);

    85         }

    86     };

    87 

    88     QSharedDataPointer<Data> d;

    89 };

    90 

    91 template <typename _Parser, typename _Table, typename _Value>

    92 inline _Value &QParser<_Parser, _Table, _Value>::sym(int n)

    93 {

    94     return d->parseStack [d->tos + n - 1];

    95 }

    96 

    97 template <typename _Parser, typename _Table, typename _Value>

    98 QParser<_Parser, _Table, _Value>::QParser():

    99     d(new Data())

   100 {

   101 }

   102 

   103 template <typename _Parser, typename _Table, typename _Value>

   104 QParser<_Parser, _Table, _Value>::~QParser()

   105 {

   106 }

   107 

   108 template <typename _Parser, typename _Table, typename _Value>

   109 bool QParser<_Parser, _Table, _Value>::parse()

   110 {

   111     const int INITIAL_STATE = 0;

   112 

   113     d->tos = 0;

   114     d->reallocateStack();

   115 

   116     int act = d->stateStack[++d->tos] = INITIAL_STATE;

   117     int token = -1;

   118 

   119     forever {

   120         if (token == -1 && - _Table::TERMINAL_COUNT != _Table::action_index[act])

   121             token = nextToken();

   122 

   123         act = _Table::t_action(act, token);

   124 

   125         if (d->stateStack[d->tos] == _Table::ACCEPT_STATE)

   126             return true;

   127 

   128         else if (act > 0) {

   129             if (++d->tos == d->stackSize)

   130                 d->reallocateStack();

   131 

   132             d->parseStack[d->tos] = d->parseStack[d->tos - 1];

   133             d->stateStack[d->tos] = act;

   134             token = -1;

   135         }

   136 

   137         else if (act < 0) {

   138             int r = - act - 1;

   139             d->tos -= _Table::rhs[r];

   140             act = d->stateStack[d->tos++];

   141             consumeRule(r);

   142             act = d->stateStack[d->tos] = _Table::nt_action(act, _Table::lhs[r] - _Table::TERMINAL_COUNT);

   143         }

   144 

   145         else break;

   146     }

   147 

   148     return false;

   149 }

   150 

   151 

   152 #endif // QPARSER_H