libstdc++-v3/include/bits/regex_compiler.h

   1 // class template regex -*- C++ -*-
   2
   3 // Copyright (C) 2010 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /**
  26  * @file bits/regex_compiler.h
  27  * This is an internal header file, included by other library headers.
  28  * You should not attempt to use it directly.
  29  */
  30
  31 _GLIBCXX_BEGIN_NAMESPACE(std)
  32
  33 namespace __regex
  34 {
  35   struct _Scanner_base
  36   {
  37     // FIXME: replace these constanst with constexpr
  38     typedef unsigned int _StateT;
  39
  40     static const _StateT _S_state_at_start    = 1 << 0;
  41     static const _StateT _S_state_in_brace    = 1 << 2;
  42     static const _StateT _S_state_in_bracket  = 1 << 3;
  43   };
  44
  45   //
  46   // @brief Scans an input range for regex tokens.
  47   //
  48   // The %_Scanner class interprets the regular expression pattern in the input
  49   // range passed to its constructor as a sequence of parse tokens passed to
  50   // the regular expression compiler.  The sequence of tokens provided depends
  51   // on the flag settings passed to the constructor:  different regular
  52   // expression gramars will interpret the same input pattern in syntactically
  53   // different ways.
  54   //
  55   template<typename _InputIterator>
  56     class _Scanner: public _Scanner_base
  57     {
  58     public:
  59       typedef _InputIterator                                        _IteratorT;
  60       typedef typename std::iterator_traits<_IteratorT>::value_type _CharT;
  61       typedef std::basic_string<_CharT>                             _StringT;
  62       typedef regex_constants::syntax_option_type                   _FlagT;
  63       typedef const std::ctype<_CharT>                              _CtypeT;
  64
  65       // Token types returned from the scanner.
  66       enum _TokenT
  67       {
  68         _S_token_anychar,
  69         _S_token_backref,
  70         _S_token_bracket_begin,
  71         _S_token_bracket_end,
  72         _S_token_inverse_class,
  73         _S_token_char_class_name,
  74         _S_token_closure0,
  75         _S_token_closure1,
  76         _S_token_collelem_multi,
  77         _S_token_collelem_single,
  78         _S_token_collsymbol,
  79         _S_token_comma,
  80         _S_token_dash,
  81         _S_token_dup_count,
  82         _S_token_eof,
  83         _S_token_equiv_class_name,
  84         _S_token_interval_begin,
  85         _S_token_interval_end,
  86         _S_token_line_begin,
  87         _S_token_line_end,
  88         _S_token_opt,
  89         _S_token_or,
  90         _S_token_ord_char,
  91         _S_token_quoted_char,
  92         _S_token_subexpr_begin,
  93         _S_token_subexpr_end,
  94         _S_token_word_begin,
  95         _S_token_word_end,
  96         _S_token_unknown
  97       };
  98
  99     public:
 100       _Scanner(_IteratorT __begin, _IteratorT __end, _FlagT __flags,
 101                std::locale __loc)
 102       : _M_current(__begin) , _M_end(__end) , _M_flags(__flags),
 103         _M_ctype(std::use_facet<_CtypeT>(__loc)), _M_state(_S_state_at_start)
 104       { _M_advance(); }
 105
 106       void
 107       _M_advance();
 108
 109       _TokenT
 110       _M_token() const
 111       { return _M_curToken; }
 112
 113       const _StringT&
 114       _M_value() const
 115       { return _M_curValue; }
 116
 117 #ifdef _GLIBCXX_DEBUG
 118       std::ostream&
 119       _M_print(std::ostream&);
 120 #endif
 121
 122     private:
 123       void
 124       _M_eat_escape();
 125
 126       void
 127       _M_scan_in_brace();
 128
 129       void
 130       _M_scan_in_bracket();
 131
 132       void
 133       _M_eat_charclass();
 134
 135       void
 136       _M_eat_equivclass();
 137
 138       void
 139       _M_eat_collsymbol();
 140
 141     private:
 142       _IteratorT  _M_current;
 143       _IteratorT  _M_end;
 144       _FlagT      _M_flags;
 145       _CtypeT&    _M_ctype;
 146       _TokenT     _M_curToken;
 147       _StringT    _M_curValue;
 148       _StateT     _M_state;
 149     };
 150
 151   template<typename _InputIterator>
 152     void
 153     _Scanner<_InputIterator>::
 154     _M_advance()
 155     {
 156       if (_M_current == _M_end)
 157         {
 158           _M_curToken = _S_token_eof;
 159           return;
 160         }
 161
 162       _CharT __c = *_M_current;
 163       if (_M_state & _S_state_in_bracket)
 164         {
 165           _M_scan_in_bracket();
 166           return;
 167         }
 168       if (_M_state & _S_state_in_brace)
 169         {
 170           _M_scan_in_brace();
 171           return;
 172         }
 173       else if (_M_state & _S_state_at_start && __c == _M_ctype.widen('^'))
 174         {
 175           _M_curToken = _S_token_line_begin;
 176           ++_M_current;
 177           return;
 178         }
 179       else if (__c == _M_ctype.widen('$'))
 180         {
 181           _M_curToken = _S_token_line_end;
 182           ++_M_current;
 183           return;
 184         }
 185       else if (__c == _M_ctype.widen('.'))
 186         {
 187           _M_curToken = _S_token_anychar;
 188           ++_M_current;
 189           return;
 190         }
 191       else if (__c == _M_ctype.widen('*'))
 192         {
 193           _M_curToken = _S_token_closure0;
 194           ++_M_current;
 195           return;
 196         }
 197       else if (__c == _M_ctype.widen('+'))
 198         {
 199           _M_curToken = _S_token_closure1;
 200           ++_M_current;
 201           return;
 202         }
 203       else if (__c == _M_ctype.widen('|'))
 204         {
 205           _M_curToken = _S_token_or;
 206           ++_M_current;
 207           return;
 208         }
 209       else if (__c == _M_ctype.widen('['))
 210         {
 211           _M_curToken = _S_token_bracket_begin;
 212           _M_state |= (_S_state_in_bracket | _S_state_at_start);
 213           ++_M_current;
 214           return;
 215         }
 216       else if (__c == _M_ctype.widen('\\'))
 217         {
 218           _M_eat_escape();
 219           return;
 220         }
 221       else if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))
 222         {
 223           if (__c == _M_ctype.widen('('))
 224             {
 225               _M_curToken = _S_token_subexpr_begin;
 226               ++_M_current;
 227               return;
 228             }
 229           else if (__c == _M_ctype.widen(')'))
 230             {
 231               _M_curToken = _S_token_subexpr_end;
 232               ++_M_current;
 233               return;
 234             }
 235           else if (__c == _M_ctype.widen('{'))
 236             {
 237               _M_curToken = _S_token_interval_begin;
 238               _M_state |= _S_state_in_brace;
 239               ++_M_current;
 240               return;
 241             }
 242         }
 243
 244       _M_curToken = _S_token_ord_char;
 245       _M_curValue.assign(1, __c);
 246       ++_M_current;
 247     }
 248
 249
 250   template<typename _InputIterator>
 251     void
 252     _Scanner<_InputIterator>::
 253     _M_scan_in_brace()
 254     {
 255       if (_M_ctype.is(_CtypeT::digit, *_M_current))
 256         {
 257           _M_curToken = _S_token_dup_count;
 258           _M_curValue.assign(1, *_M_current);
 259           ++_M_current;
 260           while (_M_current != _M_end
 261                  && _M_ctype.is(_CtypeT::digit, *_M_current))
 262             {
 263               _M_curValue += *_M_current;
 264               ++_M_current;
 265             }
 266           return;
 267         }
 268       else if (*_M_current == _M_ctype.widen(','))
 269         {
 270           _M_curToken = _S_token_comma;
 271           ++_M_current;
 272           return;
 273         }
 274       if (_M_flags & (regex_constants::basic | regex_constants::grep))
 275         {
 276           if (*_M_current == _M_ctype.widen('\\'))
 277             _M_eat_escape();
 278         }
 279       else
 280         {
 281           if (*_M_current == _M_ctype.widen('}'))
 282             {
 283               _M_curToken = _S_token_interval_end;
 284               _M_state &= ~_S_state_in_brace;
 285               ++_M_current;
 286               return;
 287             }
 288         }
 289     }
 290
 291   template<typename _InputIterator>
 292     void
 293     _Scanner<_InputIterator>::
 294     _M_scan_in_bracket()
 295     {
 296       if (_M_state & _S_state_at_start && *_M_current == _M_ctype.widen('^'))
 297         {
 298           _M_curToken = _S_token_inverse_class;
 299           _M_state &= ~_S_state_at_start;
 300           ++_M_current;
 301           return;
 302         }
 303       else if (*_M_current == _M_ctype.widen('['))
 304         {
 305           ++_M_current;
 306           if (_M_current == _M_end)
 307             {
 308               _M_curToken = _S_token_eof;
 309               return;
 310             }
 311
 312           if (*_M_current == _M_ctype.widen('.'))
 313             {
 314               _M_curToken = _S_token_collsymbol;
 315               _M_eat_collsymbol();
 316               return;
 317             }
 318           else if (*_M_current == _M_ctype.widen(':'))
 319             {
 320               _M_curToken = _S_token_char_class_name;
 321               _M_eat_charclass();
 322               return;
 323             }
 324           else if (*_M_current == _M_ctype.widen('='))
 325             {
 326               _M_curToken = _S_token_equiv_class_name;
 327               _M_eat_equivclass();
 328               return;
 329             }
 330         }
 331       else if (*_M_current == _M_ctype.widen('-'))
 332         {
 333           _M_curToken = _S_token_dash;
 334           ++_M_current;
 335           return;
 336         }
 337       else if (*_M_current == _M_ctype.widen(']'))
 338         {
 339           if (!(_M_flags & regex_constants::ECMAScript)
 340               || !(_M_state & _S_state_at_start))
 341             {
 342               // special case: only if  _not_ chr first after
 343               // '[' or '[^' and if not ECMAscript
 344               _M_curToken = _S_token_bracket_end;
 345               ++_M_current;
 346               return;
 347             }
 348         }
 349       _M_curToken = _S_token_collelem_single;
 350       _M_curValue.assign(1, *_M_current);
 351       ++_M_current;
 352     }
 353
 354   template<typename _InputIterator>
 355     void
 356     _Scanner<_InputIterator>::
 357     _M_eat_escape()
 358     {
 359       ++_M_current;
 360       if (_M_current == _M_end)
 361         {
 362           _M_curToken = _S_token_eof;
 363           return;
 364         }
 365       _CharT __c = *_M_current;
 366       ++_M_current;
 367
 368       if (__c == _M_ctype.widen('('))
 369         {
 370           if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))
 371             {
 372               _M_curToken = _S_token_ord_char;
 373               _M_curValue.assign(1, __c);
 374             }
 375           else
 376             _M_curToken = _S_token_subexpr_begin;
 377         }
 378       else if (__c == _M_ctype.widen(')'))
 379         {
 380           if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))
 381             {
 382               _M_curToken = _S_token_ord_char;
 383               _M_curValue.assign(1, __c);
 384             }
 385           else
 386             _M_curToken = _S_token_subexpr_end;
 387         }
 388       else if (__c == _M_ctype.widen('{'))
 389         {
 390           if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))
 391             {
 392               _M_curToken = _S_token_ord_char;
 393               _M_curValue.assign(1, __c);
 394             }
 395           else
 396             {
 397               _M_curToken = _S_token_interval_begin;
 398               _M_state |= _S_state_in_brace;
 399             }
 400         }
 401       else if (__c == _M_ctype.widen('}'))
 402         {
 403           if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))
 404             {
 405               _M_curToken = _S_token_ord_char;
 406               _M_curValue.assign(1, __c);
 407             }
 408           else
 409             {
 410               if (!(_M_state && _S_state_in_brace))
 411                 __throw_regex_error(regex_constants::error_badbrace);
 412               _M_state &= ~_S_state_in_brace;
 413               _M_curToken = _S_token_interval_end;
 414             }
 415         }
 416       else if (__c == _M_ctype.widen('x'))
 417         {
 418           ++_M_current;
 419           if (_M_current == _M_end)
 420             {
 421               _M_curToken = _S_token_eof;
 422               return;
 423             }
 424           if (_M_ctype.is(_CtypeT::digit, *_M_current))
 425             {
 426               _M_curValue.assign(1, *_M_current);
 427               ++_M_current;
 428               if (_M_current == _M_end)
 429                 {
 430                   _M_curToken = _S_token_eof;
 431                   return;
 432                 }
 433               if (_M_ctype.is(_CtypeT::digit, *_M_current))
 434                 {
 435                   _M_curValue += *_M_current;
 436                   ++_M_current;
 437                   return;
 438                 }
 439             }
 440         }
 441       else if (__c == _M_ctype.widen('^')
 442                || __c == _M_ctype.widen('.')
 443                || __c == _M_ctype.widen('*')
 444                || __c == _M_ctype.widen('$')
 445                || __c == _M_ctype.widen('\\'))
 446         {
 447           _M_curToken = _S_token_ord_char;
 448           _M_curValue.assign(1, __c);
 449         }
 450       else if (_M_ctype.is(_CtypeT::digit, __c))
 451         {
 452           _M_curToken = _S_token_backref;
 453           _M_curValue.assign(1, __c);
 454         }
 455       else
 456         __throw_regex_error(regex_constants::error_escape);
 457     }
 458
 459
 460   // Eats a character class or throwns an exception.
 461   // current point to ':' delimiter on entry, char after ']' on return
 462   template<typename _InputIterator>
 463     void
 464     _Scanner<_InputIterator>::
 465     _M_eat_charclass()
 466     {
 467       ++_M_current; // skip ':'
 468       if (_M_current == _M_end)
 469         __throw_regex_error(regex_constants::error_ctype);
 470       for (_M_curValue.clear();
 471            _M_current != _M_end && *_M_current != _M_ctype.widen(':');
 472            ++_M_current)
 473         _M_curValue += *_M_current;
 474       if (_M_current == _M_end)
 475         __throw_regex_error(regex_constants::error_ctype);
 476       ++_M_current; // skip ':'
 477       if (*_M_current != _M_ctype.widen(']'))
 478         __throw_regex_error(regex_constants::error_ctype);
 479       ++_M_current; // skip ']'
 480     }
 481
 482
 483   template<typename _InputIterator>
 484     void
 485     _Scanner<_InputIterator>::
 486     _M_eat_equivclass()
 487     {
 488       ++_M_current; // skip '='
 489       if (_M_current == _M_end)
 490         __throw_regex_error(regex_constants::error_collate);
 491       for (_M_curValue.clear();
 492            _M_current != _M_end && *_M_current != _M_ctype.widen('=');
 493            ++_M_current)
 494         _M_curValue += *_M_current;
 495       if (_M_current == _M_end)
 496         __throw_regex_error(regex_constants::error_collate);
 497       ++_M_current; // skip '='
 498       if (*_M_current != _M_ctype.widen(']'))
 499         __throw_regex_error(regex_constants::error_collate);
 500       ++_M_current; // skip ']'
 501     }
 502
 503
 504   template<typename _InputIterator>
 505     void
 506     _Scanner<_InputIterator>::
 507     _M_eat_collsymbol()
 508     {
 509       ++_M_current; // skip '.'
 510       if (_M_current == _M_end)
 511         __throw_regex_error(regex_constants::error_collate);
 512       for (_M_curValue.clear();
 513            _M_current != _M_end && *_M_current != _M_ctype.widen('.');
 514            ++_M_current)
 515         _M_curValue += *_M_current;
 516       if (_M_current == _M_end)
 517         __throw_regex_error(regex_constants::error_collate);
 518       ++_M_current; // skip '.'
 519       if (*_M_current != _M_ctype.widen(']'))
 520         __throw_regex_error(regex_constants::error_collate);
 521       ++_M_current; // skip ']'
 522     }
 523
 524 #ifdef _GLIBCXX_DEBUG
 525   template<typename _InputIterator>
 526     std::ostream&
 527     _Scanner<_InputIterator>::
 528     _M_print(std::ostream& ostr)
 529     {
 530       switch (_M_curToken)
 531       {
 532         case _S_token_anychar:
 533           ostr << "any-character\n";
 534           break;
 535         case _S_token_backref:
 536           ostr << "backref\n";
 537           break;
 538         case _S_token_bracket_begin:
 539           ostr << "bracket-begin\n";
 540           break;
 541         case _S_token_bracket_end:
 542           ostr << "bracket-end\n";
 543           break;
 544         case _S_token_char_class_name:
 545           ostr << "char-class-name \"" << _M_curValue << "\"\n";
 546           break;
 547         case _S_token_closure0:
 548           ostr << "closure0\n";
 549           break;
 550         case _S_token_closure1:
 551           ostr << "closure1\n";
 552           break;
 553         case _S_token_collelem_multi:
 554           ostr << "coll-elem-multi \"" << _M_curValue << "\"\n";
 555           break;
 556         case _S_token_collelem_single:
 557           ostr << "coll-elem-single \"" << _M_curValue << "\"\n";
 558           break;
 559         case _S_token_collsymbol:
 560           ostr << "collsymbol \"" << _M_curValue << "\"\n";
 561           break;
 562         case _S_token_comma:
 563           ostr << "comma\n";
 564           break;
 565         case _S_token_dash:
 566           ostr << "dash\n";
 567           break;
 568         case _S_token_dup_count:
 569           ostr << "dup count: " << _M_curValue << "\n";
 570           break;
 571         case _S_token_eof:
 572           ostr << "EOF\n";
 573           break;
 574         case _S_token_equiv_class_name:
 575           ostr << "equiv-class-name \"" << _M_curValue << "\"\n";
 576           break;
 577         case _S_token_interval_begin:
 578           ostr << "interval begin\n";
 579           break;
 580         case _S_token_interval_end:
 581           ostr << "interval end\n";
 582           break;
 583         case _S_token_line_begin:
 584           ostr << "line begin\n";
 585           break;
 586         case _S_token_line_end:
 587           ostr << "line end\n";
 588           break;
 589         case _S_token_opt:
 590           ostr << "opt\n";
 591           break;
 592         case _S_token_or:
 593           ostr << "or\n";
 594           break;
 595         case _S_token_ord_char:
 596           ostr << "ordinary character: \"" << _M_value() << "\"\n";
 597           break;
 598         case _S_token_quoted_char:
 599           ostr << "quoted char\n";
 600           break;
 601         case _S_token_subexpr_begin:
 602           ostr << "subexpr begin\n";
 603           break;
 604         case _S_token_subexpr_end:
 605           ostr << "subexpr end\n";
 606           break;
 607         case _S_token_word_begin:
 608           ostr << "word begin\n";
 609           break;
 610         case _S_token_word_end:
 611           ostr << "word end\n";
 612           break;
 613         case _S_token_unknown:
 614           ostr << "-- unknown token --\n";
 615           break;
 616       }
 617       return ostr;
 618     }
 619 #endif
 620
 621   // Builds an NFA from an input iterator interval.
 622   template<typename _InIter, typename _TraitsT>
 623     class _Compiler
 624     {
 625     public:
 626       typedef _InIter                                            _IterT;
 627       typedef typename std::iterator_traits<_InIter>::value_type _CharT;
 628       typedef std::basic_string<_CharT>                          _StringT;
 629       typedef regex_constants::syntax_option_type                _FlagT;
 630
 631     public:
 632       _Compiler(const _InIter& __b, const _InIter& __e,
 633                 _TraitsT& __traits, _FlagT __flags);
 634
 635       const _Nfa&
 636       _M_nfa() const
 637       { return _M_state_store; }
 638
 639     private:
 640       typedef _Scanner<_InIter>                              _ScannerT;
 641       typedef typename _ScannerT::_TokenT                    _TokenT;
 642       typedef std::stack<_StateSeq, std::vector<_StateSeq> > _StackT;
 643       typedef _RangeMatcher<_InIter, _TraitsT>               _RMatcherT;
 644
 645       // accepts a specific token or returns false.
 646       bool
 647       _M_match_token(_TokenT __token);
 648
 649       void
 650       _M_disjunction();
 651
 652       bool
 653       _M_alternative();
 654
 655       bool
 656       _M_term();
 657
 658       bool
 659       _M_assertion();
 660
 661       bool
 662       _M_quantifier();
 663
 664       bool
 665       _M_atom();
 666
 667       bool
 668       _M_bracket_expression();
 669
 670       bool
 671       _M_bracket_list(_RMatcherT& __matcher);
 672
 673       bool
 674       _M_follow_list(_RMatcherT& __matcher);
 675
 676       bool
 677       _M_follow_list2(_RMatcherT& __matcher);
 678
 679       bool
 680       _M_expression_term(_RMatcherT& __matcher);
 681
 682       bool
 683       _M_range_expression(_RMatcherT& __matcher);
 684
 685       bool
 686       _M_start_range(_RMatcherT& __matcher);
 687
 688       bool
 689       _M_collating_symbol(_RMatcherT& __matcher);
 690
 691       bool
 692       _M_equivalence_class(_RMatcherT& __matcher);
 693
 694       bool
 695       _M_character_class(_RMatcherT& __matcher);
 696
 697       int
 698       _M_cur_int_value(int __radix);
 699
 700     private:
 701       _TraitsT&      _M_traits;
 702       _ScannerT      _M_scanner;
 703       _StringT       _M_cur_value;
 704       _Nfa           _M_state_store;
 705       _StackT        _M_stack;
 706     };
 707
 708   template<typename _InIter, typename _TraitsT>
 709     _Compiler<_InIter, _TraitsT>::
 710     _Compiler(const _InIter& __b, const _InIter& __e, _TraitsT& __traits,
 711               _Compiler<_InIter, _TraitsT>::_FlagT __flags)
 712     : _M_traits(__traits), _M_scanner(__b, __e, __flags, _M_traits.getloc()),
 713       _M_state_store(__flags)
 714     {
 715       using std::bind;
 716       using std::placeholders::_1;
 717       using std::placeholders::_2;
 718       typedef _StartTagger<_InIter, _TraitsT> _Start;
 719       typedef _EndTagger<_InIter, _TraitsT> _End;
 720
 721       _StateSeq __r(_M_state_store,
 722                     _M_state_store._M_insert_subexpr_begin(
 723                         bind(_Start(0), _1, _2)));
 724       _M_disjunction();
 725       if (!_M_stack.empty())
 726         {
 727           __r._M_append(_M_stack.top());
 728           _M_stack.pop();
 729         }
 730       __r._M_append(_M_state_store.
 731                     _M_insert_subexpr_end(0, bind(_End(0), _1, _2)));
 732       __r._M_append(_M_state_store._M_insert_accept());
 733     }
 734
 735   template<typename _InIter, typename _TraitsT>
 736     bool
 737     _Compiler<_InIter, _TraitsT>::
 738     _M_match_token(_Compiler<_InIter, _TraitsT>::_TokenT token)
 739     {
 740       if (token == _M_scanner._M_token())
 741         {
 742           _M_cur_value = _M_scanner._M_value();
 743           _M_scanner._M_advance();
 744           return true;
 745         }
 746       return false;
 747     }
 748
 749   template<typename _InIter, typename _TraitsT>
 750     void
 751     _Compiler<_InIter, _TraitsT>::
 752     _M_disjunction()
 753     {
 754       this->_M_alternative();
 755       if (_M_match_token(_ScannerT::_S_token_or))
 756         {
 757           _StateSeq __alt1 = _M_stack.top(); _M_stack.pop();
 758           this->_M_disjunction();
 759           _StateSeq __alt2 = _M_stack.top(); _M_stack.pop();
 760           _M_stack.push(_StateSeq(__alt1, __alt2));
 761         }
 762     }
 763
 764   template<typename _InIter, typename _TraitsT>
 765     bool
 766     _Compiler<_InIter, _TraitsT>::
 767     _M_alternative()
 768     {
 769       if (this->_M_term())
 770         {
 771           _StateSeq __re = _M_stack.top(); _M_stack.pop();
 772           this->_M_alternative();
 773           if (!_M_stack.empty())
 774             {
 775               __re._M_append(_M_stack.top());
 776               _M_stack.pop();
 777             }
 778           _M_stack.push(__re);
 779           return true;
 780         }
 781       return false;
 782     }
 783
 784   template<typename _InIter, typename _TraitsT>
 785     bool
 786     _Compiler<_InIter, _TraitsT>::
 787     _M_term()
 788     {
 789       if (this->_M_assertion())
 790         return true;
 791       if (this->_M_atom())
 792         {
 793           this->_M_quantifier();
 794           return true;
 795         }
 796       return false;
 797     }
 798
 799   template<typename _InIter, typename _TraitsT>
 800     bool
 801     _Compiler<_InIter, _TraitsT>::
 802     _M_assertion()
 803     {
 804       if (_M_match_token(_ScannerT::_S_token_line_begin))
 805         {
 806           // __m.push(_Matcher::_S_opcode_line_begin);
 807           return true;
 808         }
 809       if (_M_match_token(_ScannerT::_S_token_line_end))
 810         {
 811           // __m.push(_Matcher::_S_opcode_line_end);
 812           return true;
 813         }
 814       if (_M_match_token(_ScannerT::_S_token_word_begin))
 815         {
 816           // __m.push(_Matcher::_S_opcode_word_begin);
 817           return true;
 818         }
 819       if (_M_match_token(_ScannerT::_S_token_word_end))
 820         {
 821           // __m.push(_Matcher::_S_opcode_word_end);
 822           return true;
 823         }
 824       return false;
 825     }
 826
 827   template<typename _InIter, typename _TraitsT>
 828     bool
 829     _Compiler<_InIter, _TraitsT>::
 830     _M_quantifier()
 831     {
 832       if (_M_match_token(_ScannerT::_S_token_closure0))
 833         {
 834           if (_M_stack.empty())
 835             __throw_regex_error(regex_constants::error_badrepeat);
 836           _StateSeq __r(_M_stack.top(), -1);
 837           __r._M_append(__r._M_front());
 838           _M_stack.pop();
 839           _M_stack.push(__r);
 840           return true;
 841         }
 842       if (_M_match_token(_ScannerT::_S_token_closure1))
 843         {
 844           if (_M_stack.empty())
 845             __throw_regex_error(regex_constants::error_badrepeat);
 846           _StateSeq __r(_M_state_store,
 847                         _M_state_store.
 848                         _M_insert_alt(_S_invalid_state_id,
 849                                       _M_stack.top()._M_front()));
 850           _M_stack.top()._M_append(__r);
 851           return true;
 852         }
 853       if (_M_match_token(_ScannerT::_S_token_opt))
 854         {
 855           if (_M_stack.empty())
 856           __throw_regex_error(regex_constants::error_badrepeat);
 857           _StateSeq __r(_M_stack.top(), -1);
 858           _M_stack.pop();
 859           _M_stack.push(__r);
 860           return true;
 861         }
 862       if (_M_match_token(_ScannerT::_S_token_interval_begin))
 863         {
 864           if (_M_stack.empty())
 865             __throw_regex_error(regex_constants::error_badrepeat);
 866           if (!_M_match_token(_ScannerT::_S_token_dup_count))
 867             __throw_regex_error(regex_constants::error_badbrace);
 868           _StateSeq __r(_M_stack.top());
 869           int __min_rep = _M_cur_int_value(10);
 870           for (int __i = 1; __i < __min_rep; ++__i)
 871             _M_stack.top()._M_append(__r._M_clone());
 872           if (_M_match_token(_ScannerT::_S_token_comma))
 873             if (_M_match_token(_ScannerT::_S_token_dup_count))
 874               {
 875                 int __n = _M_cur_int_value(10) - __min_rep;
 876                 if (__n < 0)
 877                   __throw_regex_error(regex_constants::error_badbrace);
 878                 for (int __i = 0; __i < __n; ++__i)
 879                   {
 880                     _StateSeq __r(_M_state_store,
 881                                   _M_state_store.
 882                                   _M_insert_alt(_S_invalid_state_id,
 883                                                 _M_stack.top()._M_front()));
 884                     _M_stack.top()._M_append(__r);
 885                   }
 886               }
 887             else
 888               {
 889                 _StateSeq __r(_M_stack.top(), -1);
 890                 __r._M_push_back(__r._M_front());
 891                 _M_stack.pop();
 892                 _M_stack.push(__r);
 893               }
 894           if (!_M_match_token(_ScannerT::_S_token_interval_end))
 895             __throw_regex_error(regex_constants::error_brace);
 896           return true;
 897         }
 898       return false;
 899     }
 900
 901   template<typename _InIter, typename _TraitsT>
 902     bool
 903     _Compiler<_InIter, _TraitsT>::
 904     _M_atom()
 905     {
 906       using std::bind;
 907       using std::placeholders::_1;
 908       using std::placeholders::_2;
 909       typedef _CharMatcher<_InIter, _TraitsT> _CMatcher;
 910       typedef _StartTagger<_InIter, _TraitsT> _Start;
 911       typedef _EndTagger<_InIter, _TraitsT> _End;
 912
 913       if (_M_match_token(_ScannerT::_S_token_anychar))
 914         {
 915           _M_stack.push(_StateSeq(_M_state_store,
 916                                   _M_state_store.
 917                                   _M_insert_matcher(bind(_AnyMatcher, _1))));
 918           return true;
 919         }
 920       if (_M_match_token(_ScannerT::_S_token_ord_char))
 921         {
 922           _M_stack.push(_StateSeq
 923                         (_M_state_store, _M_state_store.
 924                          _M_insert_matcher
 925                          (bind(_CMatcher(_M_cur_value[0], _M_traits), _1))));
 926           return true;
 927         }
 928       if (_M_match_token(_ScannerT::_S_token_quoted_char))
 929         {
 930           // note that in the ECMA grammar, this case covers backrefs.
 931           _M_stack.push(_StateSeq(_M_state_store,
 932                                   _M_state_store.
 933                                   _M_insert_matcher
 934                                   (bind(_CMatcher(_M_cur_value[0], _M_traits),
 935                                         _1))));
 936           return true;
 937         }
 938       if (_M_match_token(_ScannerT::_S_token_backref))
 939         {
 940           // __m.push(_Matcher::_S_opcode_ordchar, _M_cur_value);
 941           return true;
 942         }
 943       if (_M_match_token(_ScannerT::_S_token_subexpr_begin))
 944         {
 945           int __mark = _M_state_store._M_sub_count();
 946           _StateSeq __r(_M_state_store,
 947                         _M_state_store.
 948                         _M_insert_subexpr_begin(bind(_Start(__mark), _1, _2)));
 949           this->_M_disjunction();
 950           if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
 951             __throw_regex_error(regex_constants::error_paren);
 952           if (!_M_stack.empty())
 953             {
 954               __r._M_append(_M_stack.top());
 955               _M_stack.pop();
 956             }
 957           __r._M_append(_M_state_store._M_insert_subexpr_end
 958                         (__mark, bind(_End(__mark), _1, _2)));
 959           _M_stack.push(__r);
 960           return true;
 961         }
 962       return _M_bracket_expression();
 963     }
 964
 965   template<typename _InIter, typename _TraitsT>
 966     bool
 967     _Compiler<_InIter, _TraitsT>::
 968     _M_bracket_expression()
 969     {
 970       using std::bind;
 971       using std::placeholders::_1;
 972       if (_M_match_token(_ScannerT::_S_token_bracket_begin))
 973         {
 974           _RMatcherT __matcher(_M_match_token(_ScannerT::_S_token_line_begin),
 975                                _M_traits);
 976           if (!_M_bracket_list(__matcher)
 977               || !_M_match_token(_ScannerT::_S_token_bracket_end))
 978             __throw_regex_error(regex_constants::error_brack);
 979           _M_stack.push(_StateSeq(_M_state_store,
 980                                   _M_state_store._M_insert_matcher
 981                                   (bind(__matcher, _1))));
 982           return true;
 983         }
 984       return false;
 985     }
 986
 987   // If the dash is the last character in the bracket expression, it is not
 988   // special.
 989   template<typename _InIter, typename _TraitsT>
 990     bool
 991     _Compiler<_InIter, _TraitsT>::
 992     _M_bracket_list(_RMatcherT& __matcher)
 993     {
 994       if (_M_follow_list(__matcher))
 995         {
 996           if (_M_match_token(_ScannerT::_S_token_dash))
 997             __matcher._M_add_char(_M_cur_value[0]);
 998           return true;
 999         }
1000       return false;
1001     }
1002
1003   template<typename _InIter, typename _TraitsT>
1004     bool
1005     _Compiler<_InIter, _TraitsT>::
1006     _M_follow_list(_RMatcherT& __matcher)
1007     { return _M_expression_term(__matcher) && _M_follow_list2(__matcher); }
1008
1009   template<typename _InIter, typename _TraitsT>
1010     bool
1011     _Compiler<_InIter, _TraitsT>::
1012     _M_follow_list2(_RMatcherT& __matcher)
1013     {
1014       if (_M_expression_term(__matcher))
1015         return _M_follow_list2(__matcher);
1016       return true;
1017     }
1018
1019   template<typename _InIter, typename _TraitsT>
1020     bool
1021     _Compiler<_InIter, _TraitsT>::
1022     _M_expression_term(_RMatcherT& __matcher)
1023     {
1024       return (_M_collating_symbol(__matcher)
1025               || _M_character_class(__matcher)
1026               || _M_equivalence_class(__matcher)
1027               || (_M_start_range(__matcher)
1028                   && _M_range_expression(__matcher)));
1029     }
1030
1031   template<typename _InIter, typename _TraitsT>
1032     bool
1033     _Compiler<_InIter, _TraitsT>::
1034     _M_range_expression(_RMatcherT& __matcher)
1035     {
1036       if (!_M_collating_symbol(__matcher))
1037         if (!_M_match_token(_ScannerT::_S_token_dash))
1038           __throw_regex_error(regex_constants::error_range);
1039       __matcher._M_make_range();
1040       return true;
1041     }
1042
1043   template<typename _InIter, typename _TraitsT>
1044     bool
1045     _Compiler<_InIter, _TraitsT>::
1046     _M_start_range(_RMatcherT& __matcher)
1047     { return _M_match_token(_ScannerT::_S_token_dash); }
1048
1049   template<typename _InIter, typename _TraitsT>
1050     bool
1051     _Compiler<_InIter, _TraitsT>::
1052     _M_collating_symbol(_RMatcherT& __matcher)
1053     {
1054       if (_M_match_token(_ScannerT::_S_token_collelem_single))
1055         {
1056           __matcher._M_add_char(_M_cur_value[0]);
1057           return true;
1058         }
1059       if (_M_match_token(_ScannerT::_S_token_collsymbol))
1060         {
1061           __matcher._M_add_collating_element(_M_cur_value);
1062           return true;
1063         }
1064       return false;
1065     }
1066
1067   template<typename _InIter, typename _TraitsT>
1068     bool
1069     _Compiler<_InIter, _TraitsT>::
1070     _M_equivalence_class(_RMatcherT& __matcher)
1071     {
1072       if (_M_match_token(_ScannerT::_S_token_equiv_class_name))
1073         {
1074           __matcher._M_add_equivalence_class(_M_cur_value);
1075           return true;
1076         }
1077       return false;
1078     }
1079
1080   template<typename _InIter, typename _TraitsT>
1081     bool
1082     _Compiler<_InIter, _TraitsT>::
1083     _M_character_class(_RMatcherT& __matcher)
1084     {
1085       if (_M_match_token(_ScannerT::_S_token_char_class_name))
1086         {
1087           __matcher._M_add_character_class(_M_cur_value);
1088           return true;
1089         }
1090       return false;
1091     }
1092
1093   template<typename _InIter, typename _TraitsT>
1094     int
1095     _Compiler<_InIter, _TraitsT>::
1096     _M_cur_int_value(int __radix)
1097     {
1098       int __v = 0;
1099       for (typename _StringT::size_type __i = 0;
1100            __i < _M_cur_value.length(); ++__i)
1101         __v =__v * __radix + _M_traits.value(_M_cur_value[__i], __radix);
1102       return __v;
1103     }
1104
1105   template<typename _InIter, typename _TraitsT>
1106     _AutomatonPtr
1107     __compile(const _InIter& __b, const _InIter& __e, _TraitsT& __t,
1108               regex_constants::syntax_option_type __f)
1109     { return _AutomatonPtr(new _Nfa(_Compiler<_InIter, _TraitsT>(__b, __e, __t,
1110                                         __f)._M_nfa())); }
1111
1112 } // namespace __regex
1113
1114 _GLIBCXX_END_NAMESPACE
1115
1116 /* vim: set ts=8 sw=2 sts=2: */