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 #include "recognizer.h"

    43 #include <cstdlib>

    44 #include <cstring>

    45 #include <cctype>

    46 

    47 Recognizer::Recognizer (Grammar *grammar, bool no_lines):

    48   tos(0),

    49   stack_size(0),

    50   state_stack(0),

    51   _M_line(1),

    52   _M_action_line(0),

    53   _M_grammar(grammar),

    54   _M_no_lines(no_lines)

    55 {

    56 }

    57 

    58 Recognizer::~Recognizer()

    59 {

    60   if (stack_size)

    61     ::qFree(state_stack);

    62 }

    63 

    64 inline void Recognizer::reallocateStack()

    65 {

    66   if (! stack_size)

    67     stack_size = 128;

    68   else

    69     stack_size <<= 1;

    70 

    71   sym_stack.resize (stack_size);

    72 

    73   if (! state_stack)

    74     state_stack = reinterpret_cast<int*> (::qMalloc(stack_size * sizeof(int)));

    75   else

    76     state_stack = reinterpret_cast<int*> (::qRealloc(state_stack, stack_size * sizeof(int)));

    77 }

    78 

    79 int Recognizer::nextToken()

    80 {

    81   QString text;

    82 

    83  Lagain:

    84   while (ch.isSpace ())

    85     inp ();

    86   

    87   if (ch.isNull ())

    88     return EOF_SYMBOL;

    89 

    90   int token = ch.unicode ();

    91 

    92   if (token == '"')

    93     {

    94       inp(); // skip "

    95       text.clear ();

    96       while (! ch.isNull () && ch != QLatin1Char ('"'))

    97         {

    98           if (ch == QLatin1Char ('\\'))

    99             {

   100               text += ch;

   101               inp();

   102             }

   103           text += ch;

   104           inp ();

   105         }

   106 

   107       if (ch == QLatin1Char ('"'))

   108         inp ();

   109       else

   110         qerr << _M_input_file << ":" << _M_line << ": Warning. Expected `\"'" << endl;

   111 

   112       _M_current_value = text;

   113       return (token = STRING_LITERAL);

   114     }

   115 

   116   else if (ch.isLetterOrNumber () || ch == QLatin1Char ('_'))

   117     {

   118       text.clear ();

   119       do { text += ch; inp (); }

   120       while (ch.isLetterOrNumber () || ch == QLatin1Char ('_') || ch == QLatin1Char ('.'));

   121       _M_current_value = text;

   122       return (token = ID);

   123     }

   124 

   125   else if (token == '%')

   126     {

   127       text.clear ();

   128 

   129       do { inp (); }

   130       while (ch.isSpace ());

   131 

   132       do { text += ch; inp (); }

   133       while (ch.isLetterOrNumber () || ch == QLatin1Char ('_') || ch == QLatin1Char ('-'));

   134 

   135       if (text == QLatin1String("token_prefix"))

   136         return (token = TOKEN_PREFIX);

   137       else if (text == QLatin1String("merged_output"))

   138         return (token = MERGED_OUTPUT);

   139       else if (text == QLatin1String("token"))

   140         return (token = TOKEN);

   141       else if (text == QLatin1String("start"))

   142         return (token = START);

   143       else if (text == QLatin1String("parser"))

   144         return (token = PARSER);

   145       else if (text == QLatin1String("decl"))

   146         return (token = DECL_FILE);

   147       else if (text == QLatin1String("impl"))

   148         return (token = IMPL_FILE);

   149       else if (text == QLatin1String("expect"))

   150         return (token = EXPECT);

   151       else if (text == QLatin1String("expect-rr"))

   152         return (token = EXPECT_RR);

   153       else if (text == QLatin1String("left"))

   154         return (token = LEFT);

   155       else if (text == QLatin1String("right"))

   156         return (token = RIGHT);

   157       else if (text == QLatin1String("nonassoc"))

   158         return (token = NONASSOC);

   159       else if (text == QLatin1String("prec"))

   160         return (token = PREC);

   161       else

   162         {

   163           qerr << _M_input_file << ":" << _M_line << ": Unknown keyword `" << text << "'" << endl;

   164           exit (EXIT_FAILURE);

   165           return (token = ERROR);

   166         }

   167     }

   168 

   169   inp ();

   170 

   171   if (token == '-' && ch == QLatin1Char ('-'))

   172     {

   173       do { inp (); }

   174       while (! ch.isNull () && ch != QLatin1Char ('\n'));

   175       goto Lagain;

   176     }

   177 

   178   else if (token == ':' && ch == QLatin1Char (':'))

   179     {

   180       inp ();

   181       if (ch != QLatin1Char ('='))

   182         return (token = ERROR);

   183       inp ();

   184       return (token = COLON);

   185     }

   186 

   187   else if (token == '/' && ch == QLatin1Char (':'))

   188     {

   189       _M_action_line = _M_line;

   190 

   191       text.clear ();

   192       if (! _M_no_lines)

   193         text += QLatin1String ("\n#line ") + QString::number (_M_action_line) + " \"" + _M_input_file + "\"\n";

   194       inp (); // skip ':'

   195 

   196       forever

   197         {

   198           while (! ch.isNull ())

   199             {

   200               token = ch.unicode ();

   201               inp ();

   202 

   203               if (token == ':' && ch == QLatin1Char ('/'))

   204                 break;

   205 

   206               text += QLatin1Char (token);

   207             }

   208 

   209           if (ch != QLatin1Char ('/'))

   210             return (token = ERROR);

   211 

   212           inp ();

   213 

   214           if (ch.isNull () || ch.isSpace ())

   215             {

   216               _M_current_value = text;

   217               return (token = DECL);

   218             }

   219 	  else

   220 	    text += QLatin1String (":/");

   221         }

   222     }

   223 

   224   else if (token == '/' && ch == QLatin1Char ('.'))

   225     {

   226       _M_action_line = _M_line;

   227 

   228       text.clear ();

   229       if (! _M_no_lines)

   230         text += QLatin1String ("\n#line ") + QString::number (_M_action_line) + " \"" + _M_input_file + "\"\n";

   231 

   232       inp (); // skip ':'

   233 

   234       forever

   235         {

   236           while (! ch.isNull ())

   237             {

   238               token = ch.unicode ();

   239               inp ();

   240 

   241               if (token == '.' && ch == QLatin1Char ('/'))

   242                 break;

   243 

   244               text += QLatin1Char (token);

   245             }

   246 

   247           if (ch != QLatin1Char ('/'))

   248             return (token = ERROR);

   249 

   250           inp ();

   251 

   252           if (ch.isNull () || ch.isSpace ())

   253             {

   254               _M_current_value = text;

   255               return (token = IMPL);

   256             }

   257 	  else

   258 	    text += QLatin1String ("");

   259         }

   260     }

   261 

   262   switch (token) {

   263   case ':':

   264     return (token = COLON);

   265 

   266   case ';':

   267     return (token = SEMICOLON);

   268 

   269   case '|':

   270     return (token = OR);

   271 

   272   default:

   273     break;

   274   }

   275 

   276   return token;

   277 }

   278 

   279 bool Recognizer::parse (const QString &input_file)

   280 {

   281   _M_input_file = input_file;

   282 

   283   QFile file(_M_input_file);

   284   if (! file.open(QFile::ReadOnly))

   285     {

   286       qerr << "qlalr: no input file\n";

   287       return false;

   288     }

   289 

   290   QString _M_contents = QTextStream(&file).readAll();

   291   _M_firstChar = _M_contents.constBegin();

   292   _M_lastChar = _M_contents.constEnd();

   293   _M_currentChar = _M_firstChar;

   294   _M_line = 1;

   295 

   296   int yytoken = -1;

   297   inp ();

   298 

   299   reallocateStack();

   300 

   301   _M_current_rule = _M_grammar->rules.end ();

   302   _M_decls.clear ();

   303   _M_impls.clear ();

   304 

   305   tos = 0;

   306   state_stack[++tos] = 0;

   307 

   308   while (true)

   309     {

   310       if (yytoken == -1 && - TERMINAL_COUNT != action_index [state_stack [tos]])

   311         yytoken = nextToken();

   312 

   313       int act = t_action (state_stack [tos], yytoken);

   314 

   315       if (act == ACCEPT_STATE)

   316         return true;

   317 

   318       else if (act > 0)

   319         {

   320           if (++tos == stack_size)

   321             reallocateStack();

   322 

   323           sym_stack [tos] = _M_current_value;

   324           state_stack [tos] = act;

   325           yytoken = -1;

   326         }

   327 

   328       else if (act < 0)

   329         {

   330           int r = - act - 1;

   331 

   332           tos -= rhs [r];

   333           act = state_stack [tos++];

   334 

   335           switch (r) {

   336 

   337 case 3: {

   338   Name name = _M_grammar->intern (sym(2));

   339   _M_grammar->start = name;

   340   _M_grammar->non_terminals.insert (name);

   341 } break;

   342 

   343 case 5: {

   344   _M_grammar->table_name = sym(2);

   345 } break;

   346 

   347 case 6: {

   348   _M_grammar->merged_output = sym(2);

   349 } break;

   350 

   351 case 7: {

   352    _M_grammar->decl_file_name = sym(2);

   353 } break;

   354 

   355 case 8: {

   356    _M_grammar->impl_file_name = sym(2);

   357 } break;

   358 

   359 case 9: {

   360    _M_grammar->expected_shift_reduce = sym(2).toInt();

   361 } break;

   362 

   363 case 10: {

   364    _M_grammar->expected_reduce_reduce = sym(2).toInt();

   365 } break;

   366 

   367 case 11: {

   368   _M_grammar->token_prefix = sym(2);

   369 } break;

   370 case 17:case 18: {

   371   Name name = _M_grammar->intern (sym(1));

   372   _M_grammar->terminals.insert (name);

   373   _M_grammar->spells.insert (name, sym(2));

   374 } break;

   375 

   376 case 19: {

   377   _M_grammar->current_assoc = Grammar::Left;

   378   ++_M_grammar->current_prec;

   379 } break;

   380 

   381 case 20: {

   382   _M_grammar->current_assoc = Grammar::Right;

   383   ++_M_grammar->current_prec;

   384 } break;

   385 

   386 case 21: {

   387   _M_grammar->current_assoc = Grammar::NonAssoc;

   388   ++_M_grammar->current_prec;

   389 } break;

   390 

   391 case 25: {

   392   Name name = _M_grammar->intern (sym(1));

   393   _M_grammar->terminals.insert (name);

   394 

   395   Grammar::TokenInfo info;

   396   info.prec = _M_grammar->current_prec;

   397   info.assoc = _M_grammar->current_assoc;

   398   _M_grammar->token_info.insert (name, info);

   399 } break;

   400 

   401 case 26: {

   402   _M_decls += expand (sym(1));

   403 } break;

   404 

   405 case 27: {

   406   _M_impls += expand (sym(1));

   407 } break;

   408 

   409 case 34: {

   410   _M_current_rule = _M_grammar->rules.insert (_M_grammar->rules.end (), Rule ());

   411   _M_current_rule->lhs = _M_grammar->intern (sym(1));

   412   _M_grammar->declared_lhs.insert (_M_current_rule->lhs);

   413 

   414   if (_M_grammar->terminals.find (_M_current_rule->lhs) != _M_grammar->terminals.end ())

   415     {

   416       qerr << _M_input_file << ":" << _M_line << ": Invalid non terminal `" << *_M_current_rule->lhs << "'" << endl;

   417       return false;

   418     }

   419 

   420   _M_grammar->non_terminals.insert (_M_current_rule->lhs);

   421 } break;

   422 

   423 case 38: {

   424   Name lhs = _M_current_rule->lhs;

   425   _M_current_rule = _M_grammar->rules.insert (_M_grammar->rules.end (), Rule ());

   426   _M_current_rule->lhs = lhs;

   427   _M_grammar->declared_lhs.insert (_M_current_rule->lhs);

   428 

   429   if (_M_grammar->terminals.find (_M_current_rule->lhs) != _M_grammar->terminals.end ())

   430     {

   431       qerr << _M_input_file << ":" << _M_line << ": Invalid non terminal `" << *_M_current_rule->lhs << "'" << endl;

   432       return false;

   433     }

   434 

   435   _M_grammar->non_terminals.insert (_M_current_rule->lhs);

   436 } break;

   437 

   438 case 39: {

   439   _M_current_rule->prec = _M_grammar->names.end ();

   440 

   441   for (NameList::iterator it = _M_current_rule->rhs.begin (); it != _M_current_rule->rhs.end (); ++it)

   442     {

   443       if (! _M_grammar->isTerminal (*it))

   444         continue;

   445 

   446       _M_current_rule->prec = *it;

   447     }

   448 } break;

   449 

   450 case 40: {

   451   Name tok = _M_grammar->intern (sym(2));

   452   if (! _M_grammar->isTerminal (tok))

   453     {

   454       qerr << _M_input_file << ":" << _M_line << ": `" << *tok << " is not a terminal symbol" << endl;

   455       _M_current_rule->prec = _M_grammar->names.end ();

   456     }

   457   else

   458     _M_current_rule->prec = tok;

   459 } break;

   460 

   461 case 42: {

   462   Name name = _M_grammar->intern (sym(2));

   463 

   464   if (_M_grammar->terminals.find (name) == _M_grammar->terminals.end ())

   465     _M_grammar->non_terminals.insert (name);

   466 

   467   _M_current_rule->rhs.push_back (name);

   468 } break;

   469 

   470 case 43: {

   471   sym(1) = QString();

   472 } break;

   473 

   474           } // switch

   475 

   476           state_stack [tos] = nt_action (act, lhs [r] - TERMINAL_COUNT);

   477         }

   478       

   479       else

   480         {

   481           break;

   482         }

   483     }

   484 

   485   qerr << _M_input_file << ":" << _M_line << ": Syntax error" << endl;

   486   return false;

   487 }

   488