infobase/examples/cpp_grammar_code/CxxParsing.cxx

   1 #include <iostream.h>
   2 #include <memory.h>
   3 #include <CxxToken.hxx>
   4
   5 extern CxxToken *yylex_token();
   6
   7 #ifdef BISON_PP_CLASS
   8 BISON_PP_CLASS theParser;
   9 #define PARSE_DOT theParser .
  10 #define PARSE_SCOPE BISON_PP_CLASS ::
  11 #else
  12 #define PARSE_DOT
  13 #define PARSE_SCOPE
  14 extern int yydebug;
  15 #ifndef YYEMPTY
  16 #define YYEMPTY -1
  17 #endif
  18 #endif
  19
  20 class CxxSearchContext
  21 {
  22     friend class ios;                   // Suppress GNU error message for no public constructors.
  23         CxxSearchContext *_next;
  24         size_t _index;
  25         size_t _depth;
  26         size_t _size;
  27         size_t _mark;
  28         bool _enable_type1;
  29         size_t _line;
  30         size_t _advances;
  31         bool _status[32];
  32 private:
  33         CxxSearchContext(CxxSearchContext *nextSearch)
  34                 : _next(nextSearch), _index(0), _depth(0), _size(sizeof(_status)/sizeof(_status[0])),
  35                 _mark(0), _enable_type1(false), _line(0), _advances(0) {}
  36         CxxSearchContext(const CxxSearchContext&);
  37         CxxSearchContext& operator=(const CxxSearchContext&);
  38         bool did_search() const { return _depth > 0 ? true : false; }
  39         void initialise(size_t markIndex, bool enableType1);
  40         CxxSearchContext *queue(CxxSearchContext *& listHead);
  41         void reset();
  42 public:
  43         bool advance();
  44         bool enable_type1() const { return _enable_type1; }
  45         bool is_template();
  46         size_t mark() const { return _mark; }
  47 private:
  48         static CxxSearchContext *_current;
  49         static CxxSearchContext *_free;
  50 public:
  51         static size_t actual_searches;
  52         static size_t advances[16];
  53         static size_t max_search_depth;
  54         static size_t nested_searches;
  55         static size_t releases;
  56         static size_t search_advances;
  57         static size_t unnested_searches;
  58 public:
  59         static CxxSearchContext *current() { return _current; }
  60         static void release();
  61         static void start(YACC_MARK_TYPE anIndex, bool enableType1);
  62 };
  63
  64 size_t bang_depth = 0;
  65 size_t error_count = 0;
  66 size_t marked_error_count = 0;
  67 bool in_type1 = false;
  68 bool show_marked = false;
  69
  70 int main(int argc, char *argv[])
  71 {
  72         for (--argc, ++argv; argc-- > 0; ++argv)
  73         {
  74                 char *p = *argv;
  75                 if (*p == '-')
  76                 {
  77                         switch (*(p+1))
  78                         {
  79                                 case 'c':
  80                                         c_keywords = true;
  81                                         break;
  82                                 case 't':
  83                                         echo_line_text = true;
  84                                         break;
  85                                 case 'm':
  86                                         show_marked = true;
  87                                         break;
  88                                 case 'n':
  89                                         echo_line_numbers = true;
  90                                         break;
  91                                 case 'y':
  92                                         PARSE_DOT yydebug = true;
  93                                         break;
  94                         }
  95                 }
  96         }
  97         if (PARSE_DOT yyparse() != 0)
  98                 ERRMSG("Failed to parse to end of file,");
  99         cout << "error_count = " << error_count
 100                  << ", marked_error_count = " << marked_error_count
 101                  << ", lines = " << line_number
 102                  << ", unnested_searches = " << CxxSearchContext::unnested_searches
 103                  << ", nested_searches = " << CxxSearchContext::nested_searches
 104                  << ", releases = " << CxxSearchContext::releases
 105                  << ", actual_searches = " << CxxSearchContext::actual_searches
 106                  << ", max_search_depth = " << CxxSearchContext::max_search_depth
 107                  << ", search_advances = " << CxxSearchContext::search_advances << endl;
 108         cout << "number of occurences of each advance";
 109         for (size_t i = 0; i < sizeof(CxxSearchContext::advances)/sizeof(CxxSearchContext::advances[0]); i++)
 110                 cout << ' ' << CxxSearchContext::advances[i];
 111         cout << endl;
 112         return 0;
 113 }
 114
 115 static CxxToken **tokenBuffer = 0;                              // Allocated buffer
 116 static YACC_MARK_TYPE tokenReadIndex = 0;               // Read index
 117 static size_t tokenSize = 0;                                    // Allocate buffer size
 118 static YACC_MARK_TYPE tokenWriteIndex = 0;              // Write index
 119 int tokenMarkDepth = 0;                                         // Write index
 120 static CxxToken *primed_tokens[3] = {0, 0};             // Restarting sequence
 121 static void token_put(CxxToken *aToken);
 122
 123 CxxSearchContext *CxxSearchContext::_current = 0;
 124 CxxSearchContext *CxxSearchContext::_free = 0;
 125 size_t CxxSearchContext::actual_searches = 0;
 126 size_t CxxSearchContext::advances[16] = { 0 };
 127 size_t CxxSearchContext::max_search_depth = 0;
 128 size_t CxxSearchContext::nested_searches = 0;
 129 size_t CxxSearchContext::releases = 0;
 130 size_t CxxSearchContext::search_advances;
 131 size_t CxxSearchContext::unnested_searches;
 132
 133 //
 134 //      Implements a binary search counter, performing the increment at the
 135 //      _index of othe failed search.
 136 //
 137 bool CxxSearchContext::advance()
 138 {
 139         _advances++;
 140         size_t i = _depth;
 141         if (i <= 0)
 142                 return false;
 143         while (--i > _index)
 144                 _status[i] = false;
 145         while (true)
 146         {
 147                 if (!_status[i])
 148                 {
 149                         _status[i] = true;
 150                         _index = 0;
 151                         return true;
 152                 }
 153                 if (i <= 0)
 154                         return false;
 155                 _status[i--] = false;
 156         }
 157 }
 158
 159 void CxxSearchContext::initialise(size_t markIndex, bool enableType1)
 160 {
 161         _index = 0;
 162         _depth = 0;
 163         _mark = markIndex;
 164     _enable_type1 = enableType1;
 165         _line = line_number;
 166         _advances = 0;
 167 }
 168
 169 bool CxxSearchContext::is_template()
 170 {
 171         if (_index >= _depth)
 172         {
 173                 if (_depth >= _size)
 174                 {
 175                         ERRMSG("Binary search depth exceeded.");
 176                         return false;
 177                 }
 178                 _status[_depth++] = false;
 179                 if (_depth > max_search_depth)
 180                         max_search_depth = _depth;
 181         }
 182         return _status[_index++] ? false : true;
 183 }
 184
 185 //
 186 //      Put this element onto listHead, returning element under this one.
 187 //
 188 CxxSearchContext *CxxSearchContext::queue(CxxSearchContext *& listHead)
 189 {
 190         CxxSearchContext *oldNext = _next;
 191         _next = listHead;
 192         listHead = this;
 193         return oldNext;
 194 }
 195
 196 //
 197 //      Release the current search buffer.
 198 //
 199 void CxxSearchContext::release()
 200 {
 201         if (_current)
 202         {
 203                 releases++;
 204                 _current->reset();
 205                 _current = _current->queue(_free);
 206         }
 207 }
 208
 209 void CxxSearchContext::reset()
 210 {
 211         if (did_search())
 212         {
 213                 _advances++;
 214                 actual_searches++;
 215         }
 216         if (_advances >= sizeof(advances)/sizeof(advances[0]))
 217                 advances[sizeof(advances)/sizeof(advances[0])-1]++;
 218         else
 219                 advances[_advances]++;
 220 }
 221
 222 void CxxSearchContext::start(YACC_MARK_TYPE anIndex, bool enableType1)
 223 {
 224         if (!_current)
 225                 unnested_searches++;
 226         else
 227                 nested_searches++;
 228         if (!_free)
 229                 _current = new CxxSearchContext(_current);
 230         else
 231                 _free = _free->queue(_current);
 232         _current->initialise(anIndex, enableType1);
 233 }
 234
 235 static CxxToken angleToken('<');
 236 static CxxToken colonToken(':');
 237 static CxxToken hashToken('#');
 238 static CxxToken plusToken('+');
 239 static CxxToken minusToken('-');
 240
 241 void PARSE_SCOPE yyerror(const char *s)
 242 {
 243         if (!bang_depth && (tokenMarkDepth == 0))
 244         {
 245                 cout << s << endl;
 246                 increment_error_count();
 247         }
 248         else
 249         {
 250                 if (show_marked)
 251                         cout << "Marked " << s << endl;
 252                 marked_error_count++;
 253         }
 254 }
 255
 256 //
 257 //      Get the next token for the parser, invoking yylex_token to get the next token from the lexer.
 258 //      This routine gets renamed to buffered_yylex by a #define when using yacc so that the two purposes
 259 //      above are split allowing lookahead buffering and primimimg to occur.
 260 //
 261 int PARSE_SCOPE yylex()
 262 {
 263         CxxToken *aToken = primed_tokens[0];
 264         if (aToken)
 265         {
 266                 primed_tokens[0] = primed_tokens[1];
 267                 primed_tokens[1] = primed_tokens[2];
 268                 primed_tokens[2] = 0;
 269         }
 270         else if (tokenReadIndex < tokenWriteIndex)
 271                 aToken = tokenBuffer[tokenReadIndex++];
 272         else
 273         {
 274                 aToken = yylex_token();
 275                 if (!aToken)
 276                         return 0;
 277                 if (tokenMarkDepth > 0)
 278                         token_put(aToken);
 279                 else
 280                 {
 281                         tokenWriteIndex = 0;
 282                         tokenReadIndex = 0;
 283                 }
 284         }
 285         yylval.token = aToken;
 286         return aToken->value();
 287 }
 288
 289 //
 290 //      Advance the binary search of template attempts. Rewinds and forces true into the input sequence
 291 //      to proceed with the search. Rewinds and forces false to terminate it. Also forces a # that may then
 292 //      be used to initiate error propagation.
 293 //
 294 void advance_search()
 295 {
 296         CxxSearchContext::search_advances++;
 297         remark(CxxSearchContext::current()->mark());
 298         if (CxxSearchContext::current() && CxxSearchContext::current()->advance())
 299         {
 300                 primed_tokens[0] = &plusToken;
 301                 primed_tokens[1] = 0;
 302         }
 303         else
 304         {
 305                 primed_tokens[0] = &minusToken;
 306                 primed_tokens[1] = &hashToken;
 307         }
 308 }
 309
 310 //
 311 //      Complete a search, releasing the search context object and popping a mark off the stack.
 312 //
 313 void end_search(CxxToken *aToken)
 314 {
 315         CxxSearchContext::release();
 316         unmark(aToken);
 317 }
 318
 319 //
 320 //      Notch up an error and establish a good break point.
 321 //
 322 void increment_error_count()
 323 {
 324         error_count++;
 325 }
 326
 327 //
 328 //      Push a new marked context onto the stack, returning its identity for use by remark().
 329 //      Any parser readahead is incorporated within the marked region.
 330 //
 331 YACC_MARK_TYPE mark()
 332 {
 333         if (primed_tokens[0])
 334                 ERRMSG("Unexpected primed_tokens[0] in mark.");
 335         YACC_MARK_TYPE markIndex = tokenReadIndex;
 336         if (PARSE_DOT yychar != YYEMPTY)
 337         {
 338 //              if (primed_tokens[2])
 339 //                      token_put(primed_tokens[2]);
 340 //              if (primed_tokens[1])
 341 //                      token_put(primed_tokens[1]);
 342 //              if (primed_tokens[0])
 343 //                      token_put(primed_tokens[0]);
 344 //              if (!tokenMarkDepth)
 345                 if (!tokenReadIndex && !tokenWriteIndex)
 346                 {
 347                         token_put(PARSE_DOT yylval.token);
 348                         tokenReadIndex = 0;
 349                 }
 350                 else if (!tokenReadIndex)
 351                         ERRMSG("Unexpected 0 read index in mark.");
 352                 else if (tokenBuffer[--tokenReadIndex] != PARSE_DOT yylval.token)
 353                         ERRMSG("Unexpected unget in mark.");
 354                 markIndex = tokenReadIndex;
 355                 yyclearin;
 356                 primed_tokens[0] = 0;
 357                 primed_tokens[1] = 0;
 358         }
 359         tokenMarkDepth++;
 360         bang_depth++;
 361         return markIndex;
 362 }
 363
 364 //
 365 //      If it is appropriate to do type I function parameter parsing perform a mark and force a rrue token
 366 //      into the input stream. Otherwise just force a false token in.
 367 //
 368 YACC_MARK_TYPE mark_type1()
 369 {
 370         if (!in_type1 && CxxSearchContext::current() && CxxSearchContext::current()->enable_type1())
 371         {
 372                 YACC_MARK_TYPE markIndex = mark();
 373                 primed_tokens[0] = &plusToken;
 374                 primed_tokens[1] = 0;
 375                 in_type1 = true;
 376         yyclearin;
 377                 return markIndex;
 378         }
 379         else
 380         {
 381                 primed_tokens[0] = &minusToken;
 382                 primed_tokens[1] = PARSE_DOT yychar != YYEMPTY ? PARSE_DOT yylval.token : 0;
 383         yyclearin;
 384                 return 0;                       // Never used.
 385         }
 386 }
 387
 388 //
 389 //      Push a bang context onto the error suppression stack, returning the context for restoration by pop_bang.
 390 //
 391 void pop_bang(YACC_BANG_TYPE bangValue)
 392 {
 393         bang_depth = bangValue;
 394 }
 395
 396 //
 397 //      Push a bang context onto the error suppression stack, returning the context for restoration by pop_bang.
 398 //
 399 YACC_BANG_TYPE push_bang()
 400 {
 401         return bang_depth++;
 402 }
 403
 404 //
 405 //      Reposition the input to restart at the position returned by a mark().
 406 //
 407 void remark(YACC_MARK_TYPE anIndex)
 408 {
 409         tokenReadIndex = anIndex;
 410     yyclearin;
 411 }
 412
 413 //
 414 //      Reposition the input to restart at the position returned by a mark().
 415 //
 416 void remark_type1(YACC_MARK_TYPE anIndex)
 417 {
 418         remark(anIndex);
 419         in_type1 = false;
 420 }
 421
 422 //
 423 //      Rewind the input stream back to anIndex and force a : prior to resuming input.
 424 //
 425 void rewind_colon(YACC_MARK_TYPE anIndex, const CxxToken *aToken)
 426 {
 427         remark(anIndex);
 428         unmark();
 429         primed_tokens[0] = &colonToken;
 430         primed_tokens[1] = PARSE_DOT yylval.token;
 431 }
 432
 433 //
 434 //      Start a new binary search over the template/arithmetic alternative parses of a statement.
 435 //      Marks the current position and saves it in a binary search context maintained on a private stack.
 436 //
 437 void start_search(bool enableType1)
 438 {
 439         bool type1Enabled = !CxxSearchContext::current() || CxxSearchContext::current()->enable_type1() ? true : false;
 440         CxxSearchContext::start(mark(), enableType1 && type1Enabled ? true : false);
 441 }
 442
 443 //
 444 //      Determine whether the just parsed < should be interpreted as a template or arithmetic operator.
 445 //      The implementation here intersacts with a binary search to traverse all possibilities in
 446 //      multiple passes. The search proceeds by branch and bound presuming the template interpretation.
 447 //      A true token is forced into the input stream to take the template interpretaion. A false token
 448 //      otherwise.
 449 //
 450 //      An alternate implementation that keeps track of scopes may interact with semantic knowledge to make
 451 //      the correct decision directly.
 452 //
 453 void template_test()
 454 {
 455         if (!CxxSearchContext::current() || CxxSearchContext::current()->is_template())
 456         {
 457                 primed_tokens[0] = &plusToken;
 458                 primed_tokens[1] = 0;
 459         }
 460         else
 461         {
 462                 primed_tokens[0] = &minusToken;
 463                 primed_tokens[1] = &angleToken;
 464         }
 465 }
 466
 467 void token_put(CxxToken *aToken)
 468 {
 469         if (!tokenBuffer || !tokenSize)
 470                 tokenBuffer = new CxxToken *[tokenSize = 256];
 471         else if (tokenWriteIndex >= tokenSize)
 472         {
 473                 CxxToken **oldTokenBuffer = tokenBuffer;
 474                 size_t oldTokenSize = tokenSize;
 475                 tokenBuffer = new CxxToken *[tokenSize *= 2];
 476                 memcpy(tokenBuffer, oldTokenBuffer, oldTokenSize * sizeof(*oldTokenBuffer));
 477                 delete[] oldTokenBuffer;
 478         }
 479         tokenBuffer[tokenWriteIndex++] = aToken;
 480         tokenReadIndex = tokenWriteIndex;
 481 }
 482
 483 //
 484 //      Pop a marked context off the stack.
 485 //
 486 void unmark(const CxxToken *aToken)
 487 {
 488     if (bang_depth)
 489         bang_depth--;
 490     else
 491         ERRMSG("BUG - should not unmark with 0 bang.");
 492         if (tokenMarkDepth <= 0)
 493                 ERRMSG("Unexpected unmark.");
 494         else
 495                 tokenMarkDepth--;
 496 }