include/AD/automata/ll1parse.h

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #ifndef LL1_parser_driver_h
  26 #define LL1_parser_driver_h
  27
  28 #include <AD/automata/ll1.h>
  29
  30 //
  31 //  The following template is used to instantiate a new version
  32 //  of a parser.
  33 //
  34
  35 template< class InputStream,     // Class for retrieving a character
  36           class SemanticType,    // The contents of the semantics stack
  37           int stackSize,         // The size of the semantics stack
  38           class ActionFunction,  // Action function class
  39           class ErrorHandler     // Error handler class
  40         >
  41    void LL1_parser
  42       ( LL1& parser, InputStream& stream, SemanticType stack[],
  43         ActionFunction& action, ErrorHandler& errorHandler
  44       )
  45    {  union ParseStack {
  46          Grammar::Symbol symbol;
  47          SemanticType * entry;
  48       };
  49       ParseStack parseStack[stackSize];
  50       register ParseStack * SP = parseStack;
  51       SemanticType * top, * current, * lhs, * rhs;
  52       register Grammar::Symbol lookahead;
  53
  54       lhs = rhs = stack; top = lhs + 1;
  55       lookahead = stream.get();
  56       for ( (SP++)->symbol = parser.grammar.start(); SP > parseStack; ) {
  57          Grammar::Symbol symbol = (--SP)->symbol;
  58          if (symbol == Grammar::END_PRODUCTION) {
  59             rhs     = SP[-1].entry;
  60             lhs     = SP[-2].entry;
  61             current = SP[-3].entry;
  62             top     = SP[-4].entry;
  63             SP     -= 4;
  64          } else if (parser.grammar.isTerminal(symbol)) {
  65             if (symbol == lookahead) {
  66                lookahead = stream.get();
  67             } else {
  68                errorHandler(lookahead);
  69             }
  70          } else if (parser.grammar.isAction(symbol)) {
  71             action(symbol);
  72          } else {
  73             register Grammar::Production production =
  74                parser.grammar.productions +
  75                    parser.next[parser.base[symbol] + lookahead];
  76             if (production[0] == symbol) {
  77                sp[0].entry  = top;
  78                sp[1].entry  = current;
  79                sp[2].entry  = lhs;
  80                sp[3].entry  = rhs;
  81                sp[4].symbol = Grammar::END_PRODUCTION;
  82                sp += 5;
  83                lhs = current; current = rhs = top;
  84                for (register Grammar::Production P =
  85                       production + production[-1]; production < P; )
  86                   if (! parser.grammar.isAction((sp++)->symbol = *P--))
  87                       top++;
  88             } else {
  89                errorHandler(lookahead);
  90             }
  91          }
  92       }
  93    }
  94
  95 #endif