prop-src/parsegen.pcc.old

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 //  This file implements the syntax/syntax class constructs of Prop.
   4 //
   5 ///////////////////////////////////////////////////////////////////////////////
   6 #include <iostream.h>
   7 #include <AD/strings/charesc.h>
   8 #include <AD/strings/quark.h>
   9 #include <AD/automata/grammar.h>
  10 #include <AD/automata/operprec.h>
  11 #include <AD/automata/lalr1gen.h>
  12 #include "ir.ph"
  13 #include "ast.ph"
  14 #include "parsegen.ph"
  15 #include "datagen.h"
  16 #include "hashtab.h"
  17 #include "type.h"
  18 #include "list.h"
  19 #include "options.h"
  20
  21 ///////////////////////////////////////////////////////////////////////////////
  22 //
  23 //  Instantiate the parser/grammar related datatypes
  24 //
  25 ///////////////////////////////////////////////////////////////////////////////
  26 instantiate datatype GramExp, List<GramExp>,
  27                      BNF, List<BNF>,
  28                      ProductionSymbol, List<ProductionSymbol>,
  29                      PrecRule, List<PrecRule>,
  30                      List< List<ProductionSymbol> >;
  31
  32 ///////////////////////////////////////////////////////////////////////////////
  33 //
  34 //  Constructor and destructor
  35 //
  36 ///////////////////////////////////////////////////////////////////////////////
  37 ParserCompiler:: ParserCompiler() {}
  38 ParserCompiler::~ParserCompiler() {}
  39
  40 ///////////////////////////////////////////////////////////////////////////////
  41 //
  42 //  Pretty printing methods for grammar
  43 //
  44 ///////////////////////////////////////////////////////////////////////////////
  45
  46 ///////////////////////////////////////////////////////////////////////////////
  47 //
  48 //  Pretty print a production symbol
  49 //
  50 ///////////////////////////////////////////////////////////////////////////////
  51 ostream& operator << (ostream& f, ProductionSymbol sym)
  52 {  match (sym)
  53    {  TERMsym c:                    {  f << '\'' << print_char(c) << '\''; }
  54    |  TOKENsym NOcons:              {  f << "<?>"; }
  55    |  TOKENsym ONEcons{ name ... }: {  f << name; }
  56    |  NONTERMsym id:                {  f << id; }
  57    |  ACTIONsym a:                  {  f << "{ ... }"; }
  58    |  TERMSTRINGsym s:              {  f << s; }
  59    |  TERMREGEXPsym re:             {  f << re; }
  60    |  PREDICATEsym e:               {  f << '(' << e << ')'; }
  61    |  INDsym _:                     {  f << "???"; }
  62    |  PRECsym(ONEcons{name ...}):   {  f << "prec: " << name; }
  63    |  PRECsym NOcons:               {  f << "prec: ???"; }
  64    |  ERRORsym():                   {  f << '?'; }
  65    }
  66    return f;
  67 }
  68
  69 ///////////////////////////////////////////////////////////////////////////////
  70 //
  71 //  Pretty print a list of production symbols
  72 //
  73 ///////////////////////////////////////////////////////////////////////////////
  74 ostream& operator << (ostream& f, ProductionSymbols P)
  75 {  for (ProductionSymbols l = P; l; l = l->#2)
  76    {  f << l->#1; if (l->#2) f << " "; }
  77    return f;
  78 }
  79
  80 ///////////////////////////////////////////////////////////////////////////////
  81 //
  82 //  Pretty print a BNF
  83 //
  84 ///////////////////////////////////////////////////////////////////////////////
  85 ostream& operator << (ostream& f, BNF bnf)
  86 {  match (bnf)
  87    {  BNFrule(id,ty,alts):
  88       {  f << id;
  89          if (ty != NOty) f << ' ' << ty << ' ';
  90          f << ':';
  91          for_each (ProductionSymbols, p, alts)
  92          {  f << '\t' << p << '\n'; }
  93       }
  94   }
  95    return f;
  96 }
  97
  98 ///////////////////////////////////////////////////////////////////////////////
  99 //
 100 //  Pretty print a list of alternatives
 101 //
 102 ///////////////////////////////////////////////////////////////////////////////
 103 ostream& operator << (ostream& f, BNFs rules)
 104 {  for_each(BNF, rule, rules) f << rule;
 105    return f;
 106 }
 107
 108 ///////////////////////////////////////////////////////////////////////////////
 109 //
 110 //  Print a precedence rule
 111 //
 112 ///////////////////////////////////////////////////////////////////////////////
 113 ostream& operator << (ostream& f, PrecRule r)
 114 {  match (r)
 115    {  PRECrule(assoc,pri,symbols):
 116       {  match (assoc)
 117          {  LEFTassoc:  { f << "left: "; }
 118          |  RIGHTassoc: { f << "right: "; }
 119          |  NONassoc:   { f << "nonfix: "; }
 120          }
 121          f << pri << ' ' << symbols << '\n';
 122       }
 123    }
 124    return f;
 125 }
 126
 127 ///////////////////////////////////////////////////////////////////////////////
 128 //
 129 //  Print a list of precedence rules
 130 //
 131 ///////////////////////////////////////////////////////////////////////////////
 132 ostream& operator << (ostream& f, List<PrecRule> rules)
 133 {  for_each (PrecRule, r, rules) f << r;
 134    return f;
 135 }
 136
 137 ///////////////////////////////////////////////////////////////////////////////
 138 //
 139 //  Pretty print a grammar expression
 140 //
 141 ///////////////////////////////////////////////////////////////////////////////
 142 ostream& operator << (ostream& f, GramExp exp)
 143 {  match (exp)
 144    {  EXPgram (precs,_,rules):  { f << precs << rules; }
 145    |  _:
 146    }
 147    return f;
 148 }
 149
 150 ///////////////////////////////////////////////////////////////////////////////
 151 //
 152 //  Method to crewate a syntax class
 153 //
 154 ///////////////////////////////////////////////////////////////////////////////
 155 SyntaxClass::SyntaxClass(Id id, Inherits i, TyQual q, Decls body)
 156    : ClassDefinition(SYNTAX_CLASS,id,#[],add_inherit("LR1Parser",#[],i),q,body)
 157    {}
 158 SyntaxClass::~SyntaxClass() {}
 159
 160 ///////////////////////////////////////////////////////////////////////////////
 161 //
 162 //  Method to generate the interface of a parser class
 163 //
 164 ///////////////////////////////////////////////////////////////////////////////
 165 void SyntaxClass::gen_class_interface (CodeGen& C)
 166 {
 167  C.pr ("%-%^public:%+"
 168        "%^%/"
 169        "%^// Parser table type definitions"
 170        "%^%/"
 171        "%^typedef LR1Parser               Super;"
 172        "%^typedef Super::Offset           Offset;"
 173        "%^typedef Super::State            State;"
 174        "%^typedef Super::Rule             Rule;"
 175        "%^typedef Super::Symbol           Symbol;"
 176        "%^typedef Super::ProductionLength ProductionLength;"
 177        "%^typedef Super::ShortSymbol      ShortSymbol;"
 178        "%^typedef Super::EquivMap         EquivMap;"
 179        "%^enum { INITIAL_STACK_SIZE_ = 256,"
 180        "%^       MAX_STACK_SIZE_     = 8192"
 181        "%^     };"
 182        "%-%^protected:%+"
 183        "%^%/"
 184        "%^// Semantic value stack"
 185        "%^%/"
 186        "%^union %s_semantic_stack_type * t__, * bot__;"
 187        "%^int stack_size__;"
 188        "%^int heap_allocated__;"
 189        "%-%^public:%+"
 190        "%^%/"
 191        "%^// Constructor and parsing method"
 192        "%^%/"
 193        "%^%s();"
 194        "%^virtual void parse();"
 195        "%^void action_driver(const Rule);"
 196        "%-%^private:%+"
 197        "%^void adjust_stack(int);\n"
 198        "%^void grow_semantic_stack();",
 199        class_name, class_name
 200      );
 201 }
 202
 203 ///////////////////////////////////////////////////////////////////////////////
 204 //
 205 //  Method to generate a parser given a grammar expression.
 206 //
 207 ///////////////////////////////////////////////////////////////////////////////
 208 void ParserCompiler::gen_parser(Id id, GramExp e)
 209 {  // if (debug) cerr << id << ":\n" << e;
 210
 211    SyntaxClass * C = (SyntaxClass*)
 212        ClassDefinition::lookup_class(ClassDefinition::SYNTAX_CLASS, id);
 213    if (C) C->gen_parser(*this,e);
 214 }
 215
 216 ///////////////////////////////////////////////////////////////////////////////
 217 //
 218 //  Method to generate a parser given a grammar expression.
 219 //
 220 ///////////////////////////////////////////////////////////////////////////////
 221 void SyntaxClass::gen_parser(CodeGen& C, GramExp e)
 222 {
 223    compile_grammar(C, e);
 224    Id id = class_name;
 225    C.pr
 226       ("%^%/"
 227        "%^// Constructor for parser class %s"
 228        "%^%/"
 229        "%^%s::%s()"
 230        "%^  : Super(%s_base,%s_check,%s_def,%s_defact,%s_next,"
 231        "%^          %s_len,%s_ncount,%s_lhs,%s_equiv,%i,%i,%i) {}\n\n",
 232        id, id, id, id, id, id, id, id, id, id, id, id,
 233        (int)error_symbol, (int)max_terminal_symbol,
 234        (int)max_nonterminal_symbol
 235       );
 236 }
 237
 238 ///////////////////////////////////////////////////////////////////////////////
 239 //
 240 //  Method to compile a grammar
 241 //
 242 ///////////////////////////////////////////////////////////////////////////////
 243 void SyntaxClass::compile_grammar(CodeGen& C, GramExp e)
 244 {  match (e)
 245    {  EXPgram (precs,err,rules):
 246       { compile_rules(C, precs, err, rules); }
 247    |  _:
 248       { bug("SyntaxClass::compile_grammar"); }
 249    }
 250 }
 251
 252 ///////////////////////////////////////////////////////////////////////////////
 253 //
 254 //  Collect the names of the non-terminals
 255 //  and count the number of productions.
 256 //
 257 ///////////////////////////////////////////////////////////////////////////////
 258 static void preprocess_grammar
 259    (BNFs                  rules,
 260     HashTable&            nonterms_map,
 261     int&                  number_of_productions,
 262     Grammar::Terminal&    max_term,
 263     Grammar::NonTerminal& max_nonterm,
 264     Grammar::Terminal&    error_term
 265    )
 266 {  number_of_productions = 0;
 267
 268    ////////////////////////////////////////////////////////////////////////////
 269    //  Compute the terminal and action encoding
 270    ////////////////////////////////////////////////////////////////////////////
 271    {  for_each(BNF, r, rules)
 272       {  match (r)
 273          {  BNFrule(id,ty,alts):
 274             {  for_each (ProductionSymbols, p, alts)
 275                {  Bool no_action = true;
 276                   for_each (ProductionSymbol, s, p)
 277                   {  s->set_loc();
 278                      match (s)
 279                      {  TOKENsym (cons as ONEcons {
 280                            tag, name,
 281                            alg_ty = DATATYPEty({ qualifiers ...},_) ... }
 282                         ):
 283                         {  if ((qualifiers & QUALlexeme) == 0)
 284                               error("%Lconstructor %s is not a lexeme\n",name);
 285                            if (tag_of(cons) > max_term)
 286                                max_term = tag_of(cons);
 287                         }
 288                      |  ACTIONsym _: { no_action = false; }
 289                      |  _: // skip
 290                      }
 291                   }
 292                   if (ty != NOty && no_action)
 293                     msg("%!%wsynthesized value missing in production: ",
 294                         r->loc()) << p << '\n';
 295                }
 296             }
 297          }
 298       }
 299    }
 300
 301    ////////////////////////////////////////////////////////////////////////////
 302    //  Set the error token
 303    ////////////////////////////////////////////////////////////////////////////
 304    error_term  = ++max_term;
 305    max_nonterm = max_term + 1;
 306
 307    ////////////////////////////////////////////////////////////////////////////
 308    //  Compute the non-terminals encoding.
 309    ////////////////////////////////////////////////////////////////////////////
 310    {  for_each(BNF, r, rules)
 311       {  match (r)
 312          {  BNFrule(id,_,alts):
 313             {  if (! nonterms_map.contains(id))
 314                {  max_nonterm++;
 315                   nonterms_map.insert(id,(HashTable::Value)max_nonterm);
 316                }
 317                number_of_productions += length(alts);
 318             }
 319          }
 320       }
 321    }
 322 }
 323
 324 ///////////////////////////////////////////////////////////////////////////////
 325 //
 326 //  Translate rules into grammar form.
 327 //
 328 ///////////////////////////////////////////////////////////////////////////////
 329 static void translate_into_grammar
 330    ( BNFs                rules,
 331      Grammar::Production productions[],
 332      const HashTable&    nonterm_map,
 333      HashTable&          action_map,
 334      HashTable&          inner_action_map,
 335      HashTable&          line_map,
 336      Grammar::Action&    action,
 337      Grammar::Terminal   error_term,
 338      Ty                  ty_map[],
 339      Id                  symbol_names[]
 340    )
 341 {  int i = 0; // production number
 342    action = Grammar::First_action;
 343    for_each(BNF, r, rules)
 344    {  match (r)
 345       {  BNFrule(id,ty,alts):
 346          {  Grammar::NonTerminal A = (Grammar::NonTerminal)nonterm_map[id];
 347             symbol_names[A] = id;
 348             for_each (ProductionSymbols, p, alts)
 349             {  int j = 1;
 350                int non_terms_or_actions = 0;
 351                ty_map[i] = ty;
 352                Grammar::Production P =
 353                   (Grammar::Production)mem_pool.c_alloc
 354                      (sizeof(Grammar::Symbol) * (length(p) + 2));
 355                P[0] = A;
 356                for (List<ProductionSymbol> L = p; L; L = L->#2)
 357                {  ProductionSymbol X = L->#1;
 358                   X->set_loc();
 359                   match (X)
 360                   {  TERMsym c:
 361                      {  P[j] = c;
 362                         if (symbol_names[c] == 0)
 363                            symbol_names[c] = #"'" + print_char(c) + #"'";
 364                      }
 365                   |  NONTERMsym id:
 366                      {  if (! nonterm_map.contains(id))
 367                         {  error("%Lundefined non-terminal %s\n",id); }
 368                         else
 369                         {  P[j] = (Grammar::NonTerminal)nonterm_map[id]; }
 370                         ++non_terms_or_actions;
 371                      }
 372                   |  TOKENsym (cons as ONEcons { tag, name ... }):
 373                      {  P[j] = tag_of(cons);
 374                         symbol_names[P[j]] = name;
 375                      }
 376                   |  TOKENsym _: { P[j] = ' '; }
 377                   |  ACTIONsym decls:
 378                      {  P[j] = action;
 379                         action_map.insert(HashTable::Key(action), decls);
 380                         line_map.insert(HashTable::Key(action),
 381                                         HashTable::Value(X->begin_line));
 382                         if (L->#2 != #[])
 383                            inner_action_map.insert(HashTable::Key(action),
 384                               HashTable::Value(non_terms_or_actions));
 385                         action--;
 386                         ++non_terms_or_actions;
 387                      }
 388                   |  ERRORsym(): { P[j] = error_term; }
 389                   |  _:  { bug("translate_into_grammar()"); }
 390                   }
 391                   j++;
 392                }
 393                P[j] = Grammar::END_PRODUCTION;
 394                productions[i++] = P;
 395             }
 396          }
 397       }
 398    }
 399 }
 400
 401 ///////////////////////////////////////////////////////////////////////////////
 402 //
 403 //  Function to enter the precedence information
 404 //
 405 ///////////////////////////////////////////////////////////////////////////////
 406 static void define_operator_precedence
 407    (PrecRules rules, OpPrecedence& prec, const Grammar& G)
 408 {  for_each (PrecRule, r, rules)
 409    {  match (r)
 410       {  PRECrule(assoc,pri,symbols):
 411          {  OpPrecedence::Associativity a;
 412             match (assoc)
 413             {  LEFTassoc:  { a = OpPrecedence::Left; }
 414             |  RIGHTassoc: { a = OpPrecedence::Right; }
 415             |  NONEassoc:  { a = OpPrecedence::None; }
 416             }
 417             for_each(ProductionSymbol, s, symbols)
 418             {  match (s)
 419                {  TERMsym c:
 420                   {  prec.precedence(G.map(c),pri);
 421                      prec.associativity(G.map(c),a);
 422                   }
 423                |  TOKENsym cons:
 424                   {  prec.precedence(G.map(tag_of(cons)),pri);
 425                      prec.associativity(G.map(tag_of(cons)),a);
 426                   }
 427                |  s:
 428                   { s->set_loc();
 429                     error("%Lprecedence symbol must be terminal: ") << s << '\n';
 430                   }
 431                }
 432             }
 433          }
 434       }
 435    }
 436 }
 437
 438 ///////////////////////////////////////////////////////////////////////////////
 439 //
 440 // Add a new reference of a non-terminal
 441 //
 442 ///////////////////////////////////////////////////////////////////////////////
 443 static void add_use (HashTable& table, Id nonterm, int item_number)
 444 {  HashTable::Entry * e = table.lookup(nonterm);
 445    if (e)
 446    {  List<int> old_uses = (List<int>) table.value(e);
 447       table.insert(nonterm,#[item_number ... old_uses]);
 448    } else
 449    {  table.insert(nonterm,#[item_number]);
 450    }
 451 }
 452
 453 ///////////////////////////////////////////////////////////////////////////////
 454 //
 455 // Generate the semantic stack definition
 456 //
 457 ///////////////////////////////////////////////////////////////////////////////
 458 static void generate_semantic_stack
 459    ( Id        class_name,
 460      CodeGen&  C,
 461      BNFs      rules,
 462      const Ty  ty_map[]
 463    )
 464 {
 465    ////////////////////////////////////////////////////////////////////////////
 466    //  Mapping from nonterminal to type
 467    ////////////////////////////////////////////////////////////////////////////
 468    HashTable nonterm_to_ty(string_hash,string_equal);
 469    HashTable nonterm_to_uses(string_hash,string_equal);
 470
 471    ////////////////////////////////////////////////////////////////////////////
 472    //  Generate the semantic stack definition.
 473    ////////////////////////////////////////////////////////////////////////////
 474    C.pr ("%^%/"
 475          "%^// Semantic value stack for syntax class %s"
 476          "%^%/"
 477          "%^union %s_semantic_stack_type {%+"
 478          "%^int dummy;",
 479          class_name, class_name);
 480
 481    ////////////////////////////////////////////////////////////////////////////
 482    //
 483    //  First, we'll make sure that all productions with the same non-terminal
 484    //  have the same synthesized attribute type.
 485    //
 486    ////////////////////////////////////////////////////////////////////////////
 487    for_each (BNF, rl, rules)
 488    {  match (rl)
 489       {  BNFrule(id,ty,_):
 490          {  HashTable::Entry * e = nonterm_to_ty.lookup(id);
 491             if (e)
 492             {  Ty last_ty = (Ty)nonterm_to_ty.value(e);
 493                if (! ty_equal(ty,last_ty))
 494                {  rl->set_loc();
 495                   error("%Lexpecting type '%T' but found '%T'\n", last_ty, ty);
 496                }
 497             }
 498             nonterm_to_ty.insert(id,ty);
 499          }
 500       }
 501    }
 502
 503    ////////////////////////////////////////////////////////////////////////////
 504    //
 505    //  Now, we found out all references of all non-terminals.
 506    //
 507    ////////////////////////////////////////////////////////////////////////////
 508    int item_number = 0;
 509
 510    for_each (BNF, r, rules)
 511    {  match (r)
 512       {  BNFrule(id,ty,alts):
 513          {  for_each (ProductionSymbols, p, alts)
 514             {  ++item_number;
 515                if (ty != NOty)
 516                   add_use(nonterm_to_uses,id,item_number);
 517                for_each (ProductionSymbol, X, p)
 518                {  ++item_number;
 519                   match (X)
 520                   {  NONTERMsym id:
 521                      {  HashTable::Entry * e = nonterm_to_ty.lookup(id);
 522                         if (e)
 523                         {  Ty this_ty = (Ty)nonterm_to_ty.value(e);
 524                            if (this_ty != NOty)
 525                               add_use(nonterm_to_uses,id,item_number);
 526                         }
 527                      }
 528                   |  _: // skip
 529                   }
 530                }
 531             }
 532          }
 533       }
 534    }
 535
 536    ////////////////////////////////////////////////////////////////////////////
 537    //
 538    //  Then we print out the type definitions for all the synthesized
 539    //  attributes.
 540    //
 541    ////////////////////////////////////////////////////////////////////////////
 542    {  int i = 0;
 543       for_each (BNF, r, rules)
 544       {  match (r)
 545          {  BNFrule(id,ty,_):
 546             {  if (ty != NOty)
 547                {  List<int> uses = (List<int>)nonterm_to_uses[id];
 548                   if (uses != #[])
 549                   {  C.pr ("%#"
 550                            "%^typedef %tATTRIBUTE_%i;"
 551                            "%^ATTRIBUTE_%i ",
 552                            r->begin_line, r->file_name, ty, "", i, i);
 553                      for (List<int> l = uses; l; l = l->#2)
 554                      {  C.pr ("_%i", l->#1); if (l->#2) C.pr(", "); }
 555                      C.pr (";\n");
 556                      i++;
 557                   }
 558                }
 559             }
 560          }
 561       }
 562    }
 563    C.pr ("%-%^};\n\n");
 564 }
 565
 566 ///////////////////////////////////////////////////////////////////////////////
 567 //
 568 // Generate debugging tables
 569 //
 570 ///////////////////////////////////////////////////////////////////////////////
 571 static void generate_debugging_tables
 572    ( Id                    class_name,
 573      CodeGen&              C,
 574      const LALR1Gen&       parserGen,
 575      const Grammar&        G,
 576      Id                    symbol_names[],
 577      const HashTable&      line_map,
 578      const Grammar::Action min_action,
 579      Grammar::NonTerminal  max_nonterm
 580    )
 581 {  C.pr ("%^%/"
 582          "%^// Debugging tables for syntax class %s"
 583          "%^%/"
 584          "\n#ifdef DEBUG_%s",
 585          class_name, class_name);
 586
 587    ////////////////////////////////////////////////////////////////////////////
 588    //  Generate the mapping from rule number to source code line number.
 589    ////////////////////////////////////////////////////////////////////////////
 590    C.pr ("%^static const int %s_line[] =%^{%+%^", class_name);
 591    {  int * line_table = (int *)mem_pool.c_alloc(G.size() * sizeof(int));
 592       for (Grammar::Action a = Grammar::First_action; a > min_action; a--)
 593       {  int r = G.rule_of(a);
 594          if (r >= 0)
 595          {  line_table[r] = (int)line_map[HashTable::Key(a)]; }
 596       }
 597       for (int r = 0; r < G.size(); r++)
 598       {  C.pr ("%i", line_table[r]);
 599          if (r < G.size() - 1) C.pr(", ");
 600          if (r % 8 == 7) C.pr ("%^");
 601       }
 602    }
 603    C.pr ("%-%^};\n\n");
 604
 605    ////////////////////////////////////////////////////////////////////////////
 606    //  Generate the mapping from equivalence class number to name.
 607    ////////////////////////////////////////////////////////////////////////////
 608    C.pr ("%^static const char * const %s_symbolname[] =%^{%+%^", class_name);
 609    {  Id * sym_map = (Id *)
 610          mem_pool.c_alloc((G.max_non_terminal() + 1) * sizeof(Id));
 611       for (int c = 0; c <= max_nonterm; c++)
 612          if (symbol_names[c]) sym_map[G.map(c)] = symbol_names[c];
 613       for (int i = 0; i <= G.max_non_terminal(); i++)
 614       {   C.pr ("%s", sym_map[i] ? make_quoted_string(sym_map[i]) : "\"???\"");
 615           if (i < G.max_non_terminal()) C.pr (", ");
 616           if (i % 8 == 7) C.pr ("%^");
 617       }
 618    }
 619    C.pr ("%-%^};\n\n");
 620
 621    ////////////////////////////////////////////////////////////////////////////
 622    //  Generate the mapping from rule number to production.
 623    ////////////////////////////////////////////////////////////////////////////
 624    {  for (int r = 0; r < G.size(); r++)
 625       {  C.pr("%^static const DFATables::ShortSymbol %s_rhs_%i[] = { ",
 626               class_name, r);
 627          int len = G.length(G.rhs(r));
 628          for (int i = 0; i < len; i++)
 629          {  C.pr ("%i, ", (int)G.rhs(r)[i]); }
 630          C.pr(" -1 };");
 631       }
 632    }
 633    {  C.pr ("%^static const DFATables::ShortSymbol * %s_rhs[] =%^{%+",
 634             class_name);
 635       for (int r = 0; r < G.size(); r++)
 636       {  C.pr ("%^%s_rhs_%i", class_name, r);
 637          if (r < G.size() - 1) C.pr(", ");
 638       }
 639       C.pr ("%-%^};\n\n");
 640    }
 641    C.pr ("\n#endif\n\n");
 642 }
 643
 644 ///////////////////////////////////////////////////////////////////////////////
 645 //
 646 // Generate parser tables and action code
 647 //
 648 ///////////////////////////////////////////////////////////////////////////////
 649 static void generate_parser_driver
 650    ( Id                    class_name,
 651      CodeGen&              C,
 652      const LALR1Gen&       parserGen,
 653      const Grammar&        G,
 654      Id                    symbol_names[],
 655      int                   number_of_productions,
 656      BNFs                  rules,
 657      const Ty              ty_map[],
 658      const HashTable&      action_map,
 659      const HashTable&      inner_action_map,
 660      const HashTable&      line_map,
 661      const Grammar::Action min_action,
 662      Grammar::NonTerminal  max_nonterm
 663    )
 664 {
 665    ////////////////////////////////////////////////////////////////////////////
 666    //  Generate the parser tables.
 667    ////////////////////////////////////////////////////////////////////////////
 668    C.pr ( "%^%/"
 669           "%^// Encoded parser tables for syntax class %s"
 670           "%^%/",
 671           class_name);
 672    parserGen.gen_code(C.pr(""),class_name);
 673    ::generate_debugging_tables(class_name, C, parserGen, G, symbol_names,
 674                                line_map, min_action, max_nonterm);
 675    ::generate_semantic_stack(class_name, C, rules, ty_map);
 676
 677    ////////////////////////////////////////////////////////////////////////////
 678    //  Generate the parser driver header.
 679    ////////////////////////////////////////////////////////////////////////////
 680    C.pr ( "\n"
 681           "%^%/"
 682           "%^// Parser driver for syntax class %s"
 683           "%^%/"
 684           "%^inline void %s::action_driver(const Rule _r_)"
 685           "%^{\n%+"
 686           "%^%s_semantic_stack_type syn_;",
 687           class_name, class_name, class_name
 688         );
 689
 690    ////////////////////////////////////////////////////////////////////////////
 691    //  Generate the debugging function
 692    ////////////////////////////////////////////////////////////////////////////
 693    C.pr ("\n%^%/"
 694          "%^// Tracing code for syntax class %s"
 695          "%^%/"
 696          "#ifdef DEBUG_%s"
 697          "%^{  cerr << \"Reducing via rule \" << _r_ << \" at line \""
 698          "%^        << %s_line[_r_] << \", \""
 699          "%^        << %s_symbolname[%s_lhs[_r_]] << \" <- \";"
 700          "%^   for (const DFATables::ShortSymbol * _p_ = %s_rhs[_r_]; *_p_ >= 0; _p_++)"
 701          "%^      cerr << %s_symbolname[*_p_] << ' ';"
 702          "%^   cerr << '\\n';"
 703          "%^}"
 704          "\n#endif\n\n",
 705          class_name, class_name, class_name, class_name,
 706          class_name, class_name, class_name, class_name, class_name
 707        );
 708
 709    ////////////////////////////////////////////////////////////////////////////
 710    //  Generate the switch on the reduction rules.
 711    ////////////////////////////////////////////////////////////////////////////
 712    C.pr ( "%^%/"
 713           "%^// Actions for syntax class %s"
 714           "%^%/"
 715           "%^t__ -= %s_ncount[_r_];"
 716           "%^switch (_r_) {\n%+",
 717           class_name, class_name, class_name, class_name
 718         );
 719
 720    ////////////////////////////////////////////////////////////////////////////
 721    //  Generate the parsing actions
 722    ////////////////////////////////////////////////////////////////////////////
 723    C.pr("\n"
 724         "#undef to__\n"
 725         "#define to__ 0\n"
 726        );
 727    for (Grammar::Action a = Grammar::First_action; a > min_action; a--)
 728    {  HashTable::Entry * e = inner_action_map.lookup(HashTable::Key(a));
 729       if (e)
 730       {  C.pr("\n"
 731               "#undef to__\n"
 732               "#define to__ -%i",
 733               (int)(e->v)
 734              );
 735       }
 736       C.pr ("%^case %i: {%+%&%-} break;",
 737             (int)G.rule_of(a), action_map[HashTable::Key(a)]);
 738       if (e)
 739       {  C.pr("\n"
 740               "#undef to__\n"
 741               "#define to__ 0\n"
 742              );
 743       }
 744    }
 745    C.pr ("%-%^}"
 746          "%^if (t__ >= bot__ + stack_size__) grow_semantic_stack();"
 747          "%^*++t__ = syn_;"
 748          "%-%^}\n\n"
 749         );
 750
 751    ////////////////////////////////////////////////////////////////////////////
 752    //  Generate the parser method
 753    ////////////////////////////////////////////////////////////////////////////
 754    C.pr ("%^%/"
 755          "%^// Parsing method for parser class %s"
 756          "%^%/"
 757          "%^void %s::parse()"
 758          "%^{"
 759          "%^   %s_semantic_stack_type stack__[INITIAL_STACK_SIZE_];"
 760          "%^   t__ = bot__ = stack__;"
 761          "%^   stack_size__ = sizeof(stack__)/sizeof(stack__[0]) - 1;"
 762          "%^   heap_allocated__ = 0;"
 763          "%^   parser_prefix();"
 764          "%^   LR1ParserDriver<%s,(LR1Parser::State)%i> drv;"
 765          "%^   drv.driver(*this);"
 766          "%^   parser_suffix();"
 767          "%^   if (bot__ != stack__) delete [] bot__;"
 768          "%^}\n\n",
 769          class_name, class_name, class_name,
 770          class_name, parserGen.final_state()
 771         );
 772 }
 773
 774 ///////////////////////////////////////////////////////////////////////////////
 775 //
 776 //  Method to compile a set of production rules
 777 //
 778 ///////////////////////////////////////////////////////////////////////////////
 779 void SyntaxClass::compile_rules
 780    ( CodeGen&          C,
 781      PrecRules         precedence_rules,
 782      ShiftReduceErrors expected_errors,
 783      BNFs              rules
 784    )
 785 {  int last_errors = errors;
 786    ////////////////////////////////////////////////////////////////////////////
 787    //  Data structures used
 788    ////////////////////////////////////////////////////////////////////////////
 789    HashTable nonterm_map(string_hash, string_equal);
 790    HashTable action_map(integer_hash, integer_equal);
 791    HashTable inner_action_map(integer_hash, integer_equal);
 792    HashTable line_map  (integer_hash, integer_equal);
 793    HashTable predicate_map(integer_hash, integer_equal);
 794    int                  number_of_productions = 0;
 795    Grammar::Terminal    min_term              = 0;
 796    Grammar::Terminal    max_term              = 255;
 797    Grammar::Terminal    error_term            = 255;
 798    Grammar::NonTerminal max_nonterm           = 255;
 799    Grammar::NonTerminal start_symbol          = 0;
 800    Grammar::Action      action                = Grammar::First_action;
 801    Id *                 symbol_names          = 0;
 802    Grammar::Production * productions          = 0;
 803    Ty *                 ty_map                = 0;
 804
 805    ////////////////////////////////////////////////////////////////////////////
 806    // Collect the names of the non-terminals in this grammar
 807    ////////////////////////////////////////////////////////////////////////////
 808    ::preprocess_grammar
 809       (rules, nonterm_map, number_of_productions,
 810        max_term, max_nonterm, error_term);
 811
 812    ////////////////////////////////////////////////////////////////////////////
 813    // Translate into grammar form.
 814    ////////////////////////////////////////////////////////////////////////////
 815    productions  = (Grammar::Production *)mem_pool.c_alloc
 816         (sizeof(Grammar::Production) * number_of_productions);
 817    symbol_names = (Id *)mem_pool.c_alloc(sizeof(Id) * (max_nonterm + 1));
 818    ty_map       = (Ty *)mem_pool.c_alloc(sizeof(Ty) * number_of_productions);
 819
 820    ::translate_into_grammar
 821        (rules, productions, nonterm_map,
 822         action_map, inner_action_map, line_map, action,
 823         error_term, ty_map, symbol_names);
 824    symbol_names[error_term] = "?";
 825    error_symbol = error_term;
 826    max_terminal_symbol = max_term;
 827    max_nonterminal_symbol = max_nonterm;
 828
 829    if (last_errors < errors) return;
 830    if (number_of_productions > 0) start_symbol = productions[0][0];
 831
 832    ////////////////////////////////////////////////////////////////////////////
 833    // Create the grammar and put it into canonical form
 834    ////////////////////////////////////////////////////////////////////////////
 835    Grammar G0(productions, number_of_productions, min_term, max_term,
 836               start_symbol, symbol_names);
 837    Grammar G = G0.makeCanonical();
 838
 839    ////////////////////////////////////////////////////////////////////////////
 840    // Compile the grammar into tables.
 841    ////////////////////////////////////////////////////////////////////////////
 842    LALR1Gen     parserGen;
 843    OpPrecedence prec(G);
 844    ::define_operator_precedence(precedence_rules,prec,G);
 845    parserGen.compile(G,prec);
 846
 847    ////////////////////////////////////////////////////////////////////////////
 848    // Print error messages
 849    ////////////////////////////////////////////////////////////////////////////
 850    int sr_conflicts = parserGen.shift_reduce_conflicts();
 851    int rr_conflicts = parserGen.reduce_reduce_conflicts();
 852    if (sr_conflicts > 0 && expected_errors < 0)
 853    {  msg(expected_errors == -1 ? "%L%w: %i%s%s\n" : "%L%w%i%s%s\n",
 854           sr_conflicts, " shift/reduce conflicts in syntax class ",
 855           class_name);
 856    }
 857    if (expected_errors >= 0 && sr_conflicts != expected_errors)
 858    {  msg("%L%wexpecting %i shift/reduce conflicts but found %i in syntax class %s\n",
 859           expected_errors, sr_conflicts, class_name);
 860    }
 861    if (rr_conflicts > 0)
 862    {  msg("%L%w%i reduce/reduce conflicts in syntax class %s\n",
 863           rr_conflicts, class_name);
 864    }
 865
 866    ////////////////////////////////////////////////////////////////////////////
 867    // Generate a report
 868    ////////////////////////////////////////////////////////////////////////////
 869    if (options.generate_report)
 870    {  ostream& log = open_logfile();
 871       log << "[Syntax class " << class_name << "]\n";
 872       parserGen.print_report(log, options.verbosity) << '\n';
 873    }
 874
 875    ////////////////////////////////////////////////////////////////////////////
 876    // Generate driver code
 877    ////////////////////////////////////////////////////////////////////////////
 878    ::generate_parser_driver
 879       (class_name, C, parserGen, G, symbol_names, number_of_productions,
 880        rules, ty_map, action_map, inner_action_map,
 881        line_map, action, max_nonterm);
 882
 883    ////////////////////////////////////////////////////////////////////////////
 884    // Generate the stack adjustment method
 885    ////////////////////////////////////////////////////////////////////////////
 886    C.pr("%^void %s::adjust_stack(int offset) { t__ += offset; }\n\n",
 887         class_name);
 888
 889    ////////////////////////////////////////////////////////////////////////////
 890    // Generate the semantic stack growing method
 891    ////////////////////////////////////////////////////////////////////////////
 892    C.pr(
 893       "%^void %s::grow_semantic_stack()\n"
 894       "%^{%+"
 895       "%^int N = (stack_size__ + 1) * 2;"
 896       "%^%s_semantic_stack_type * S = new %s_semantic_stack_type [N];"
 897       "%^if (N >= LR1Parser::SEMANTIC_STACK_SIZE) "
 898       "%^   error_report(\"Warning: semantic stack overflow\");"
 899       "%^memcpy(S, bot__, sizeof(%s_semantic_stack_type) * (stack_size__ + 1));"
 900       "%^if (heap_allocated__) delete [] bot__;"
 901       "%^t__ = S + (t__ - bot__);"
 902       "%^bot__ = S;"
 903       "%^stack_size__ = N - 1;"
 904       "%^heap_allocated__ = 1;"
 905       "%-%^}\n\n",
 906       class_name, class_name, class_name, class_name );
 907 }