| blob | 55d8394612e4ccbd04babe69f0167183c9d203d2 |
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 ///////////////////////////////////////////////////////////////////////////////
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> >;
32 ///////////////////////////////////////////////////////////////////////////////
33 //
34 // Constructor and destructor
35 //
36 ///////////////////////////////////////////////////////////////////////////////
37 ParserCompiler:: ParserCompiler() {}
38 ParserCompiler::~ParserCompiler() {}
40 ///////////////////////////////////////////////////////////////////////////////
41 //
42 // Pretty printing methods for grammar
43 //
44 ///////////////////////////////////////////////////////////////////////////////
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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() {}
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 }
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;
211 SyntaxClass * C = (SyntaxClass*)
212 ClassDefinition::lookup_class(ClassDefinition::SYNTAX_CLASS, id);
213 if (C) C->gen_parser(*this,e);
214 }
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 }
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 }
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;
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 }
322 }
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 }
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 }
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 }
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);
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");
564 }
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);
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");
642 }
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);
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 );
772 }
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;
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);
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 );
907 }