gcc config
[prop.git] / prop-src / parsegen.pcc.old
blob55d8394612e4ccbd04babe69f0167183c9d203d2
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"
21 ///////////////////////////////////////////////////////////////////////////////
23 //  Instantiate the parser/grammar related datatypes
25 ///////////////////////////////////////////////////////////////////////////////
26 instantiate datatype GramExp, List<GramExp>,
27                      BNF, List<BNF>, 
28                      ProductionSymbol, List<ProductionSymbol>,
29                      PrecRule, List<PrecRule>,
30                      List< List<ProductionSymbol> >;
32 ///////////////////////////////////////////////////////////////////////////////
34 //  Constructor and destructor
36 ///////////////////////////////////////////////////////////////////////////////
37 ParserCompiler:: ParserCompiler() {}
38 ParserCompiler::~ParserCompiler() {}
40 ///////////////////////////////////////////////////////////////////////////////
42 //  Pretty printing methods for grammar 
44 ///////////////////////////////////////////////////////////////////////////////
46 ///////////////////////////////////////////////////////////////////////////////
48 //  Pretty print a production symbol
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;
69 ///////////////////////////////////////////////////////////////////////////////
71 //  Pretty print a list of production symbols
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;
80 ///////////////////////////////////////////////////////////////////////////////
82 //  Pretty print a BNF
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;
98 ///////////////////////////////////////////////////////////////////////////////
100 //  Pretty print a list of alternatives
102 ///////////////////////////////////////////////////////////////////////////////
103 ostream& operator << (ostream& f, BNFs rules)
104 {  for_each(BNF, rule, rules) f << rule; 
105    return f;
108 ///////////////////////////////////////////////////////////////////////////////
110 //  Print a precedence rule
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;
127 ///////////////////////////////////////////////////////////////////////////////
129 //  Print a list of precedence rules
131 ///////////////////////////////////////////////////////////////////////////////
132 ostream& operator << (ostream& f, List<PrecRule> rules)
133 {  for_each (PrecRule, r, rules) f << r;
134    return f;
137 ///////////////////////////////////////////////////////////////////////////////
139 //  Pretty print a grammar expression
141 ///////////////////////////////////////////////////////////////////////////////
142 ostream& operator << (ostream& f, GramExp exp)
143 {  match (exp)
144    {  EXPgram (precs,_,rules):  { f << precs << rules; }
145    |  _:              
146    }
147    return f;
150 ///////////////////////////////////////////////////////////////////////////////
152 //  Method to crewate a syntax class
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() {}
160 ///////////////////////////////////////////////////////////////////////////////
162 //  Method to generate the interface of a parser class
164 ///////////////////////////////////////////////////////////////////////////////
165 void SyntaxClass::gen_class_interface (CodeGen& C)
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      );
203 ///////////////////////////////////////////////////////////////////////////////
205 //  Method to generate a parser given a grammar expression.
207 ///////////////////////////////////////////////////////////////////////////////
208 void ParserCompiler::gen_parser(Id id, GramExp e)
209 {  // if (debug) cerr << id << ":\n" << e;
211    SyntaxClass * C = (SyntaxClass*)
212        ClassDefinition::lookup_class(ClassDefinition::SYNTAX_CLASS, id);
213    if (C) C->gen_parser(*this,e);
215     
216 ///////////////////////////////////////////////////////////////////////////////
218 //  Method to generate a parser given a grammar expression.
220 ///////////////////////////////////////////////////////////////////////////////
221 void SyntaxClass::gen_parser(CodeGen& C, GramExp e)
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       );
238 ///////////////////////////////////////////////////////////////////////////////
240 //  Method to compile a grammar
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    }
252 ///////////////////////////////////////////////////////////////////////////////
254 //  Collect the names of the non-terminals
255 //  and count the number of productions.
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;
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    }  
301    ////////////////////////////////////////////////////////////////////////////
302    //  Set the error token
303    ////////////////////////////////////////////////////////////////////////////
304    error_term  = ++max_term;
305    max_nonterm = max_term + 1;
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    }
324 ///////////////////////////////////////////////////////////////////////////////
326 //  Translate rules into grammar form.
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    }
401 ///////////////////////////////////////////////////////////////////////////////
403 //  Function to enter the precedence information
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    }
438 ///////////////////////////////////////////////////////////////////////////////
440 // Add a new reference of a non-terminal
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    }
453 ///////////////////////////////////////////////////////////////////////////////
455 // Generate the semantic stack definition
457 ///////////////////////////////////////////////////////////////////////////////
458 static void generate_semantic_stack
459    ( Id        class_name, 
460      CodeGen&  C, 
461      BNFs      rules,
462      const Ty  ty_map[]
463    )
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);
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);
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    }
503    ////////////////////////////////////////////////////////////////////////////
504    //  
505    //  Now, we found out all references of all non-terminals.
506    //
507    ////////////////////////////////////////////////////////////////////////////
508    int item_number = 0;
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    }
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");
566 ///////////////////////////////////////////////////////////////////////////////
568 // Generate debugging tables 
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);
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");
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");
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");
644 ///////////////////////////////////////////////////////////////////////////////
646 // Generate parser tables and action code
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);
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         );
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        );
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         );
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         );
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         );
774 ///////////////////////////////////////////////////////////////////////////////
776 //  Method to compile a set of production rules
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;
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);
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);
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;
829    if (last_errors < errors) return;
830    if (number_of_productions > 0) start_symbol = productions[0][0];
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();
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);
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    }
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    }
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);
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 );