|
1
8
9 package beaver.comp;
10
11 import java.io.ByteArrayOutputStream  ;
12 import java.io.DataOutputStream ;
13 import java.io.File ;
14 import java.io.FileOutputStream ;
15 import java.io.FileWriter ;
16 import java.io.IOException ;
17 import java.io.Writer ;
18 import java.util.Arrays ;
19 import java.util.Comparator ;
20 import java.util.zip.DeflaterOutputStream ;
21
22 import beaver.Parser;
23 import beaver.comp.io.SrcReader;
24 import beaver.comp.run.Options;
25 import beaver.comp.util.BitSet;
26 import beaver.comp.util.Log;
27 import beaver.spec.Grammar;
28 import beaver.spec.GrammarBuilder;
29 import beaver.spec.NonTerminal;
30 import beaver.spec.Production;
31 import beaver.spec.Terminal;
32 import beaver.spec.ast.GrammarTreeRoot;
33 import beaver.spec.parser.GrammarParser;
34 import beaver.spec.parser.GrammarScanner;
35
36
40 public class ParserGenerator
41 {
42 static public final String VERSION = "0.9.6.1";
43 static public final String SOURCE_FILE_EXT = ".java";
44 static public final String SERIALIZED_PARSER_TABLES_FILE_EXT = ".spec";
45 static public final String PARSER_ACTIONS_REPORT_FILE_EXT = ".stat";
46
47 static public class CompiledParser
48 {
49
61 static private int[] makeProductionDescriptors(Grammar grammar)
62 {
63 int[] rules = new int[grammar.rules.length];
64 for (int i = 0; i < grammar.rules.length; i++)
65 {
66 Production rule = grammar.rules[i];
67 rules[i] = rule.lhs.id << 16 | rule.rhs.items.length;
68 }
69 return rules;
70 }
71
72 static private final Comparator TERMINAL_NAME_CMP = new Comparator ()
73 {
74 public int compare(Object o1, Object o2)
75 {
76 Terminal term1 = (Terminal) o1;
77 Terminal term2 = (Terminal) o2;
78
79 return term1.id == 0 ? -1 : term1.name.compareTo(term2.name);
80 }
81 };
82
83 static private void writeTerminalsClass(Grammar grammar, Options opts, String indent, Writer out) throws IOException
84 {
85 out.write(indent);
86 if (indent.length() > 0)
87 out.write("static ");
88 out.write("public class Terminals {\n");
89
90 Terminal[] terms;
91 if (opts.sort_terminals)
92 {
93 terms = new Terminal[grammar.terminals.length];
94 System.arraycopy(grammar.terminals, 0, terms, 0, terms.length);
95 Arrays.sort(terms, TERMINAL_NAME_CMP);
96 }
97 else
98 {
99 terms = grammar.terminals;
100 }
101
102 for (int i = 0; i < terms.length; i++)
103 {
104 if (terms[i].name.charAt(0) == '$')
105 continue;
106 out.write(indent);
107 out.write("\tstatic public final short ");
108 out.write(terms[i].name);
109 out.write(" = ");
110 out.write(String.valueOf(terms[i].id));
111 out.write(";\n");
112 }
113 if (opts.terminal_names)
114 {
115 terms = grammar.terminals;
116 out.write('\n');
117 out.write(indent);
118 out.write("\tstatic public final String[] NAMES = {\n");
119 for (int i = 0; i < terms.length - 1; i++)
120 {
121 if (terms[i].name.charAt(0) == '$')
122 continue;
123 out.write(indent);
124 out.write("\t\t\"");
125 out.write(terms[i].name);
126 out.write("\",\n");
127 }
128 if (terms.length > 0 && terms[terms.length - 1].name.charAt(0) != '$')
129 {
130 out.write(indent);
131 out.write("\t\t\"");
132 out.write(terms[terms.length - 1].name);
133 out.write("\"\n");
134 }
135 out.write(indent);
136 out.write("\t};\n");
137 }
138 out.write(indent);
139 out.write("}\n");
140 }
141
142 static private boolean writeMarkersClass(Terminal[] terms, Writer out) throws IOException
143 {
144 boolean header_is_out = false;
145
146 for (int i = 0; i < terms.length; i++)
147 {
148 if (terms[i].name.charAt(0) == '$')
149 {
150 if (!header_is_out)
151 {
152 out.write("\tstatic public class AltGoals {\n");
153 header_is_out = true;
154 }
155 out.write("\t\tstatic public final short ");
156 out.write(terms[i].name.substring(1));
157 out.write(" = ");
158 out.write(String.valueOf(terms[i].id));
159 out.write(";\n");
160 }
161 }
162 if (header_is_out)
163 {
164 out.write("\t}\n");
165 }
166 return header_is_out;
167 }
168
169 static private void writeReduceActionClasses(Grammar grammar, Writer out) throws IOException
170 {
171 for (int i = 0; i < grammar.rules.length; i++)
172 {
173 Production rule = grammar.rules[i];
174 if (rule.code == null)
175 continue;
176
177 out.write("\n\t/**");
178 out.write("\n\t * ");
179 out.write(rule.toString());
180 out.write("\n\t */");
181 out.write("\n\tfinal class Action");
182 out.write(String.valueOf(rule.id));
183 out.write(" extends Action {\n");
184 out.write("\t\t\t\tpublic Symbol reduce(Symbol[] _symbols, int offset) {\n");
185 writeReduceActionCode(rule, out);
186 out.write("\t\t\t\t}");
187 out.write("\n\t}\n");
188 }
189 }
190
191 static private void writeStaticReturns(Grammar grammar, Writer out) throws IOException
192 {
193 BitSet ret_elems = new BitSet();
194 for (int i = 0; i < grammar.rules.length; i++)
195 {
196 Production rule = grammar.rules[i];
197 if (rule.code == null && rule.rhs.size() > 1)
198 {
199 int n = indexOfLastReferencedSymbol(rule.rhs);
200 if (n == 0)
201 continue;
202 if (n < 0)
203 n = rule.rhs.size() - 1;
204 if (ret_elems.add(n))
205 {
206 out.write("\n\tstatic final Action RETURN");
207 out.write(String.valueOf(n + 1));
208 out.write(" = new Action() {\n");
209 out.write("\t\tpublic Symbol reduce(Symbol[] _symbols, int offset) {\n");
210 out.write("\t\t\treturn _symbols[offset + ");
211 out.write(String.valueOf(n + 1));
212 out.write("];\n");
213 out.write("\t\t}\n");
214 out.write("\t};\n");
215 }
216 }
217 }
218 }
219
220 static private int countReferencedSymbols(Production.RHS rhs)
221 {
222 int c = 0;
223 for (int i = 0; i < rhs.items.length; i++)
224 {
225 if (rhs.items[i].alias != null) c++;
226 }
227 return c;
228 }
229
230 static private int indexOfLastReferencedSymbol(Production.RHS rhs)
231 {
232 int i = rhs.size();
233 while (--i >= 0 && rhs.items[i].alias == null)
234 ;
235 return i;
236 }
237
238 static private void writeParserActionsArray(Grammar grammar, Options opts, Writer out) throws IOException
239 {
240 for (int i = 0, last_i = grammar.rules.length - 1; i < grammar.rules.length; i++)
241 {
242 Production rule = grammar.rules[i];
243 out.write("\n\t\t\t");
244 if (rule.code == null)
245 {
246 if (rule.rhs.size() == 0)
247 {
248 out.write("Action.NONE");
249 if (i != last_i) out.write(", ");
250 out.write("\t// [");
251 out.write(String.valueOf(rule.id));
252 out.write("] ");
253 out.write(rule.toString());
254 }
255 else if (rule.rhs.size() == 1)
256 {
257 out.write("Action.RETURN");
258 if (i != last_i) out.write(',');
259 out.write("\t// [");
260 out.write(String.valueOf(rule.id));
261 out.write("] ");
262 out.write(rule.toString());
263 }
264 else
265 {
266 int n = indexOfLastReferencedSymbol(rule.rhs);
267 if (n == 0)
268 {
269 out.write("Action.RETURN");
270 }
271 else if (n > 0)
272 {
273 out.write("RETURN");
274 out.write(String.valueOf(n + 1));
275 }
276 else
277 {
278 out.write("RETURN");
279 out.write(String.valueOf(rule.rhs.size()));
280 }
281 if (i != last_i) out.write(',');
282 out.write("\t// [");
283 out.write(String.valueOf(rule.id));
284 out.write("] ");
285 out.write(rule.toString());
286
287 if (n < 0)
288 {
289 out.write("; returns '");
290 out.write(rule.rhs.items[rule.rhs.size() - 1].symbol.name);
291 out.write("' although none is marked");
292 }
293 else if (countReferencedSymbols(rule.rhs) > 1)
294 {
295 out.write("; returns '");
296 out.write(rule.rhs.items[n].alias);
297 out.write("' although more are marked");
298 }
299 }
300 }
301 else
302 {
303 out.write("new Action");
304 if (opts.name_action_classes)
305 {
306 out.write(String.valueOf(rule.id));
307 out.write("()");
308 if (i != last_i) out.write(',');
309 out.write("\t// [");
310 out.write(String.valueOf(rule.id));
311 out.write("] ");
312 out.write(rule.toString());
313 }
314 else
315 {
316 out.write("() {\t// [");
317 out.write(String.valueOf(rule.id));
318 out.write("] ");
319 out.write(rule.toString());
320 out.write('\n');
321 out.write("\t\t\t\tpublic Symbol reduce(Symbol[] _symbols, int offset) {\n");
322 writeReduceActionCode(rule, out);
323 out.write("\t\t\t\t}");
324 out.write("\n\t\t\t}");
325 if (i != last_i) out.write(',');
326 }
327 }
328 }
329 }
330
331 static private void writeParserActionsSwitch(Grammar grammar, Options opts, Writer out) throws IOException
332 {
333 out.write("\t\tswitch(rule_num) {\n");
334
335 int n = grammar.rules.length;
336 Production[] rules = new Production[n];
337 System.arraycopy(grammar.rules, 0, rules, 0, n);
338
339 for (int i = 0; i < rules.length; i++)
340 {
341 if (rules[i].code != null)
342 {
343 out.write("\t\t\tcase ");
344 out.write(String.valueOf(rules[i].id));
345 out.write(": // ");
346 out.write(rules[i].toString());
347 out.write("\n\t\t\t{\n");
348 writeReduceActionCode(rules[i], out);
349 out.write("\t\t\t}\n");
350
351 rules[i] = null;
352 n--;
353 }
354 }
355 for (int w = 0; n > 0; w++)
356 {
357 int cnt = 0;
358 for (int i = 0; i < rules.length; i++)
359 {
360 if (rules[i] != null)
361 {
362 int ref_off = indexOfLastReferencedSymbol(rules[i].rhs) + 1;
363 if (ref_off == 0)
364 {
365 ref_off = rules[i].rhs.size();
366 }
367
368 if (ref_off == w)
369 {
370 out.write("\t\t\tcase ");
371 out.write(String.valueOf(rules[i].id));
372 out.write(": // ");
373 out.write(rules[i].toString());
374 out.write("\n");
375
376 rules[i] = null;
377 n--;
378 cnt++;
379 }
380 }
381 }
382 if (cnt > 0)
383 {
384 out.write("\t\t\t{\n");
385 if (w == 0)
386 {
387 out.write("\t\t\t\treturn new Symbol(null);\n");
388 }
389 else
390 {
391 out.write("\t\t\t\treturn _symbols[offset + ");
392 out.write(String.valueOf(w));
393 out.write("];\n");
394 }
395 out.write("\t\t\t}\n");
396 }
397 }
398 out.write("\t\t\tdefault:\n");
399 out.write("\t\t\t\tthrow new IllegalArgumentException(\"unknown production #\" + rule_num);\n");
400 out.write("\t\t}\n");
401 }
402
403 private static void writeReduceActionCode(Production rule, Writer out) throws IOException
404 {
405 for (int i = 0; i < rule.rhs.items.length; i++)
406 {
407 Production.RHS.Item rhs_item = rule.rhs.items[i];
408 if (rhs_item.alias != null)
409 {
410 out.write("\t\t\t\t\t");
411 String type = rhs_item.symbol.type;
412 if (type == null)
413 {
414 out.write("final Symbol ");
415 out.write(rhs_item.alias);
416 out.write(" = _symbols[offset + ");
417 out.write(String.valueOf(i + 1));
418 out.write("];\n");
419 }
420 else
421 {
422 out.write("final Symbol _symbol_");
423 out.write(rhs_item.alias);
424 out.write(" = _symbols[offset + ");
425 out.write(String.valueOf(i + 1));
426 out.write("];\n");
427
428 if (type.charAt(0) == '+')
429 {
430 type = type.substring(1);
431 out.write("\t\t\t\t\tfinal ");
432 out.write(Grammar.EBNF_LIST_TYPE_NAME);
433 out.write(" _list_");
434 out.write(rhs_item.alias);
435 out.write(" = (");
436 out.write(Grammar.EBNF_LIST_TYPE_NAME);
437 out.write(") _symbol_");
438 out.write(rhs_item.alias);
439 out.write(".value;\n");
440
441 out.write("\t\t\t\t\tfinal ");
442 out.write(type);
443 out.write("[] ");
444 out.write(rhs_item.alias);
445 out.write(" = _list_");
446 out.write(rhs_item.alias);
447 out.write(" == null ? new ");
448 out.write(type);
449 out.write("[0] : (");
450 out.write(type);
451 out.write("[]) _list_");
452 out.write(rhs_item.alias);
453 out.write(".toArray(new ");
454 out.write(type);
455 out.write("[_list_");
456 out.write(rhs_item.alias);
457 out.write(".size()]);\n");
458 }
459 else
460 {
461 out.write("\t\t\t\t\tfinal ");
462 out.write(type);
463 out.write(' ');
464 out.write(rhs_item.alias);
465 out.write(" = (");
466 out.write(type);
467 out.write(") _symbol_");
468 out.write(rhs_item.alias);
469 out.write(".value;\n");
470 }
471 }
472 }
473 }
474 out.write("\t\t\t\t\t");
475 out.write(rule.code);
476 out.write('\n');
477 }
478
479 static private ByteArrayOutputStream serializeParsingTables(ParsingTables tables, int[] rule_descr, NonTerminal error) throws IOException
480 {
481 ByteArrayOutputStream bytes_stream = new ByteArrayOutputStream (16384);
482 DataOutputStream data_stream = new DataOutputStream (new DeflaterOutputStream (bytes_stream));
483
484 tables.writeTo(data_stream);
485
486 data_stream.writeInt(rule_descr.length);
487 for (int i = 0; i < rule_descr.length; i++)
488 {
489 data_stream.writeInt(rule_descr[i]);
490 }
491 data_stream.writeShort(error.id);
492 data_stream.close();
493 return bytes_stream;
494 }
495
496 static private String encode(byte[] bytes) throws IOException
497 {
498 final StringBuffer text = new StringBuffer ((bytes.length * 4 + 2) / 3);
499 int i = 0, end = bytes.length - bytes.length % 3;
500 while (i < end)
501 {
502 int b1 = bytes[i++] & 0xFF, b2 = bytes[i++] & 0xFF, b3 = bytes[i++] & 0xFF;
503 encode(b1 >> 2, text);
504 encode((b1 << 4 & 0x30) | b2 >> 4, text);
505 encode((b2 << 2 & 0x3C) | b3 >> 6, text);
506 encode(b3 & 0x3F, text);
507 }
508 if (i < bytes.length)
509 {
510 int b1 = bytes[i++] & 0xFF;
511 if (i < bytes.length)
512 {
513 int b2 = bytes[i] & 0xFF;
514 encode(b1 >> 2, text);
515 encode((b1 << 4 & 0x30) | b2 >> 4, text);
516 encode((b2 << 2 & 0x3C), text);
517 text.append('=');
518 }
519 else
520 {
521 encode(b1 >> 2, text);
522 encode(b1 << 4 & 0x30, text);
523 text.append('=');
524 text.append('=');
525 }
526 }
527 return text.toString();
528 }
529
530 static private final char[] _62_or_63 = { '#', '$' };
531
532 static private void encode(int c, StringBuffer text)
533 {
534 if (c < 10)
535 text.append((char)('0' + c));
536 else if (c < 36)
537 text.append((char)('A' - 10 + c));
538 else if (c < 62)
539 text.append((char)('a' - 36 + c));
540 else
541 text.append(_62_or_63[c - 62]);
542 }
543
544 private Grammar grammar;
545 private ParsingTables tables;
546 private int[] rule_descr;
547
548 CompiledParser(Grammar grammar, ParsingTables parsing_tables)
549 {
550 this.grammar = grammar;
551 this.tables = parsing_tables;
552 this.rule_descr = makeProductionDescriptors(grammar);
553 }
554
555 public void writeActionsReport(File dir, String output_file_name) throws IOException
556 {
557 FileWriter out = new FileWriter (new File (dir, output_file_name + PARSER_ACTIONS_REPORT_FILE_EXT));
558 try
559 {
560 out.write("// This file was generated by Beaver v");
561 out.write(VERSION);
562 out.write("\n\n");
563 for (State state = tables.first_state; state != null; state = state.next)
564 {
565 out.write(String.valueOf(state.id));
566 out.write(':');
567 for (Action act = state.terminal_lookahead_actions.first; act != null; act = act.next)
568 {
569 out.write('\t');
570 out.write(act.toString());
571 out.write('\n');
572 }
573 for (Action act = state.nonterminal_lookahead_actions.first; act != null; act = act.next)
574 {
575 out.write('\t');
576 out.write(act.toString());
577 out.write('\n');
578 }
579 if (state.default_action != null)
580 {
581 out.write('\t');
582 out.write(state.default_action.toString());
583 out.write('\n');
584 }
585 }
586 }
587 finally
588 {
589 out.close();
590 }
591 }
592
593
601 public void writeParserSource(File src_file, File dir, String class_name, Options opts) throws IOException
602 {
603 FileWriter out = new FileWriter (new File (dir, class_name + SOURCE_FILE_EXT));
604 try
605 {
606 if (grammar.prolog != null)
607 {
608 out.write(grammar.prolog);
609 out.write('\n');
610 }
611 if (grammar.package_name != null)
612 {
613 out.write("package ");
614 out.write(grammar.package_name);
615 out.write(";\n\n");
616 }
617 for (int i = 0; i < grammar.imports.length; i++)
618 {
619 out.write("import ");
620 out.write(grammar.imports[i]);
621 out.write(";\n");
622 }
623 out.write('\n');
624 out.write("/**\n");
625 out.write(" * This class is a LALR parser generated by\n");
626 out.write(" * <a HREF=\"http://beaver.sourceforge.net\">Beaver</a> v");
627 out.write(VERSION);
628 out.write('\n');
629 out.write(" * from the grammar specification \"");
630 out.write(src_file.getName());
631 out.write("\".\n");
632 out.write(" */\n");
633 writeClass(class_name, opts, out);
634 }
635 finally
636 {
637 out.close();
638 }
639 }
640
641 public void writeTerminalsSource(File src_file, File dir, String output_file_name, Options opts) throws IOException
642 {
643 FileWriter out = new FileWriter (new File (dir, output_file_name + SOURCE_FILE_EXT));
644 try
645 {
646 if (grammar.package_name != null)
647 {
648 out.write("package ");
649 out.write(grammar.package_name);
650 out.write(";\n\n");
651 }
652 out.write("/**\n");
653 out.write(" * This class lists terminals used by the\n");
654 out.write(" * grammar specified in \"");
655 out.write(src_file.getName());
656 out.write("\".\n");
657 out.write(" */\n");
658 writeTerminalsClass(grammar, opts, "", out);
659 }
660 finally
661 {
662 out.close();
663 }
664 }
665
666 public void writeParsingTables(File dir, String output_file_name) throws IOException
667 {
668 FileOutputStream out = new FileOutputStream (new File (dir, output_file_name + SERIALIZED_PARSER_TABLES_FILE_EXT));
669 try
670 {
671 serializeParsingTables(tables, rule_descr, grammar.error).writeTo(out);
672 }
673 finally
674 {
675 out.close();
676 }
677 }
678
679 private void writeClass(String class_name, Options opts, Writer out) throws IOException
680 {
681 out.write("public class ");
682 out.write(class_name);
683 out.write(" extends ");
684 if (class_name.equals("Parser"))
685 out.write("beaver.");
686 out.write("Parser {\n");
687
688 if (!opts.export_terminals)
689 {
690 writeTerminalsClass(grammar, opts, "\t", out);
691 }
692 writeMarkersClass(grammar.terminals, out);
693
694 out.write("\n\tstatic final ParsingTables PARSING_TABLES = new ParsingTables(");
695 if (opts.exp_parsing_tables)
696 {
697 out.write(class_name);
698 out.write(".class");
699 }
700 else
701 {
702 String enc = encodeParsingTables();
703
704 out.write('\n');
705 int from = 0;
706 int dlen = enc.length() != 71 ? 71 : 73;
707 for (int to = dlen; to < enc.length(); from = to, to += dlen)
708 {
709 out.write("\t\t\"");
710 out.write(enc.substring(from, to));
711 out.write("\" +\n");
712 }
713 out.write("\t\t\"");
714 out.write(enc.substring(from));
715 out.write('"');
716 }
717 out.write(");\n");
718
719 if (!opts.use_switch)
720 {
721 if (opts.name_action_classes)
722 writeReduceActionClasses(grammar, out);
723 writeStaticReturns(grammar, out);
724 }
725 if (grammar.class_code != null)
726 {
727 out.write(grammar.class_code);
728 out.write('\n');
729 }
730 if (!opts.use_switch)
731 {
732 out.write('\n');
733 out.write("\tprivate final Action[] actions;\n");
734 }
735 out.write('\n');
736
737 out.write("\tpublic ");
738 out.write(class_name);
739 out.write("() {\n");
740 out.write("\t\tsuper(PARSING_TABLES);\n");
741 if (!opts.use_switch)
742 {
743 out.write("\t\tactions = new Action[] {");
744 writeParserActionsArray(grammar, opts, out);
745 out.write("\n\t\t};\n");
746 }
747 if (grammar.init_code != null)
748 {
749 out.write('\n');
750 out.write(grammar.init_code);
751 out.write('\n');
752 }
753 out.write("\t}\n");
754 out.write('\n');
755 out.write("\tprotected Symbol invokeReduceAction(int rule_num, int offset) {\n");
756 if (opts.use_switch)
757 {
758 writeParserActionsSwitch(grammar, opts, out);
759 }
760 else
761 {
762 out.write("\t\treturn actions[rule_num].reduce(_symbols, offset);\n");
763 }
764 out.write("\t}\n");
765 out.write("}\n");
766 }
767
768 private String encodeParsingTables() throws IOException
769 {
770 return encode(serializeParsingTables(tables, rule_descr, grammar.error).toByteArray());
771 }
772 }
773
774 static public void compile(SrcReader src, Options opt, Log log) throws IOException , Parser.Exception, Grammar.Exception
775 {
776 Grammar grammar = ParserGenerator.parseGrammar(src, log);
777 if (!log.hasErrors())
778 {
779 ParserGenerator.CompiledParser parser = ParserGenerator.compile(grammar, opt, log);
780 if (!log.hasErrors())
781 {
782 File dir = src.file.getParentFile();
783 if (opt.dest_dir != null)
784 {
785 dir = opt.dest_dir;
786 if (grammar.package_name != null)
787 {
788 dir = new File (dir, grammar.package_name.replace('.', File.separatorChar));
789 if (!dir.exists())
790 {
791 dir.mkdirs();
792 }
793 }
794 }
795 String output_file_name = ParserGenerator.getOutputFileName(grammar, src.file);
796 if (opt.report_actions)
797 {
798 parser.writeActionsReport(dir, output_file_name);
799 log.message("Generated: " + output_file_name + PARSER_ACTIONS_REPORT_FILE_EXT);
800 }
801 if (!opt.no_output)
802 {
803 parser.writeParserSource(src.file, dir, output_file_name, opt);
804 log.message("Generated: " + output_file_name + SOURCE_FILE_EXT);
805 if (opt.export_terminals)
806 {
807 parser.writeTerminalsSource(src.file, dir, "Terminals", opt);
808 log.message("Generated: " + "Terminals" + SOURCE_FILE_EXT);
809 }
810 if (opt.exp_parsing_tables)
811 {
812 parser.writeParsingTables(dir, output_file_name);
813 log.message("Generated: " + output_file_name + SERIALIZED_PARSER_TABLES_FILE_EXT);
814 }
815 }
816 }
817 }
818 }
819
820 static public Grammar parseGrammar(SrcReader reader, Log log) throws IOException , Parser.Exception, Grammar.Exception
821 {
822 GrammarTreeRoot root = (GrammarTreeRoot) new GrammarParser(log).parse(new GrammarScanner(reader));
823 if (log.hasErrors())
824 throw new Grammar.Exception("cannot parse grammar");
825 GrammarBuilder maker = new GrammarBuilder(log);
826 root.accept(maker);
827 return maker.getGrammar();
828 }
829
830 static public ParserGenerator.CompiledParser compile(Grammar grammar, Options opts, Log log) throws Grammar.Exception
831 {
832 grammar.markNullableProductions();
833 grammar.buildFirstSets();
834 State first = makeStates(grammar);
835 findLookaheads(first);
836 buildActions(grammar, first);
837 checkAndResolveConflicts(first, log);
838 checkUnreducibleProductions(grammar, first, log);
839 if (!opts.no_compression)
840 compressActions(first);
841 splitActions(first);
842 return new CompiledParser(grammar, new ParsingTables(grammar, first));
843 }
844
845 static private State makeStates(Grammar grammar)
846 {
847 Configuration.Set.Factory conf_set_factory = new Configuration.Set.Factory(grammar);
848 for (Production rule = grammar.goal_symbol.definitions.start(); rule != null; rule = rule.next_definition)
849 {
850 Configuration conf = conf_set_factory.addConfiguration(rule, 0);
851 conf.addLookahead(grammar.eof);
852 }
853 State first = new State.Factory(conf_set_factory).getState(conf_set_factory.getCore());
854 for (State state = first; state != null; state = state.next)
855 {
856 state.conf_set.reverseReversePropagation();
857 state.conf_set.resetContributionFlags();
858 }
859 return first;
860 }
861
862 static private void findLookaheads(State first)
863 {
864 boolean more_found;
865 do
866 {
867 more_found = false;
868
869 for (State state = first; state != null; state = state.next)
870 {
871 if (state.findLookaheads())
872 {
873 more_found = true;
874 }
875 }
876 }
877 while (more_found);
878 }
879
880 static private void buildActions(Grammar grammar, State first)
881 {
882 new Action.Reduce.Maker(grammar.terminals, first).buildReduceActions();
883
884 first.actions.add(new Action.Accept(grammar));
887 }
888
889 static private void checkAndResolveConflicts(State first, Log log) throws Grammar.Exception
890 {
891 int num_conflicts = 0;
892 for (State state = first; state != null; state = state.next)
893 {
894 num_conflicts += state.actions.resolveConflicts(log);
895 }
896 if (num_conflicts > 0)
897 {
898 for (State state = first; state != null; state = state.next)
899 {
900 state.actions.reportConflicts(log);
901 }
902 throw new Grammar.Exception("grammar has conflicts");
903 }
904 }
905
906 static private void checkUnreducibleProductions(Grammar grammar, State first, Log log) throws Grammar.Exception
907 {
908 for (State state = first; state != null; state = state.next)
909 {
910 state.actions.markReducibleProductions();
911 }
912 boolean has_unreducible = false;
913 for (int i = 0; i < grammar.rules.length; i++)
914 {
915 Production rule = grammar.rules[i];
916 if (!rule.is_reducible)
917 {
918 log.error(rule.start_pos, rule.end_pos, "Production \"" + rule.toString() + "\" can not be reduced");
919 has_unreducible = true;
920 }
921 }
922 if (has_unreducible)
923 {
924 throw new Grammar.Exception("grammar has unreducible productions");
925 }
926 }
927
928 static private void compressActions(State first)
929 {
930 for (State state = first; state != null; state = state.next)
931 {
932 state.actions.compress();
933 }
934 }
935
936 static private void splitActions(State first)
937 {
938 for (State state = first; state != null; state = state.next)
939 {
940 state.splitActions();
941 }
942 }
943
944 static public String getOutputFileName(Grammar grammar, File src_file)
945 {
946 if (grammar.class_name != null)
947 return grammar.class_name;
948
949 String spec_file_name = src_file.getName();
950 int dot_index = spec_file_name.lastIndexOf('.');
951 if (dot_index > 0)
952 {
953 spec_file_name = spec_file_name.substring(0, dot_index);
954 }
955 return spec_file_name;
956 }
957 } |
Popular Tags |
Java API By Example, From Geeks To Geeks.