prop-src/parsegen.pcc

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