001: /*
002: * xtc - The eXTensible Compiler
003: * Copyright (C) 2004-2007 Robert Grimm
004: *
005: * This program is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU General Public License
007: * version 2 as published by the Free Software Foundation.
008: *
009: * This program is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
012: * GNU General Public License for more details.
013: *
014: * You should have received a copy of the GNU General Public License
015: * along with this program; if not, write to the Free Software
016: * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
017: * USA.
018: */
019: package xtc.parser;
020:
021: import java.io.File;
022: import java.io.IOException;
023: import java.io.PrintWriter;
024: import java.io.Reader;
025:
026: import java.util.ArrayList;
027:
028: import xtc.Constants;
029:
030: import xtc.util.Tool;
031: import xtc.util.Utilities;
032:
033: import xtc.tree.Attribute;
034: import xtc.tree.Node;
035: import xtc.tree.Printer;
036:
037: import xtc.type.AST;
038: import xtc.type.JavaAST;
039:
040: /**
041: * The command line interface to <i>Rats!</i>, the packrat parser
042: * generator for Java.
043: *
044: * @author Robert Grimm
045: * @version $Revision: 1.186 $
046: */
047: public class Rats extends Tool {
048:
049: /** Create a new instance of <i>Rats!</i>. */
050: public Rats() { /* Nothing to do. */
051: }
052:
053: public String getName() {
054: return "Rats! Parser Generator";
055: }
056:
057: public String getCopy() {
058: return Constants.COPY;
059: }
060:
061: public String getExplanation() {
062: return "By default, Rats! performs all optimizations besides the "
063: + "errors2 and left1 optimizations. If one or more "
064: + "individual optimizations are specified as command line flags, all "
065: + "other optimizations are automatically disabled. The choices2 "
066: + "optimization includes choices1, errors1 is complimentary to errors2, "
067: + "and left1 and left2 are mutually exclusive.";
068: }
069:
070: public void init() {
071: super .init();
072: runtime
073: .bool("loaded", "optionLoaded", false,
074: "Print every module after loading, then stop.")
075: .bool("instantiated", "optionInstantiated", false,
076: "Print all modules after loading and instantiating them, then stop.")
077: .bool(
078: "dependencies",
079: "optionDependencies",
080: false,
081: "Print module dependencies after loading and instantiating, "
082: + "then stop.")
083: .bool("applied", "optionApplied", false,
084: "Print all modules after applying modifications, then stop.")
085: .bool(
086: "valued",
087: "optionValued",
088: false,
089: "Print grammar after reducing it to expressions that directly "
090: + "contribute to AST, then stop.")
091: .bool("processed", "optionProcessed", false,
092: "Print full grammar before code generation, then stop.")
093: .bool(
094: "html",
095: "optionHtml",
096: false,
097: "Create HTML for instantiated, applied, valued, or processed "
098: + "options.")
099: .bool("variant", "optionVariant", false,
100: "Enforce variant types for productions having node values.")
101: .bool("ast", "optionASTDefinition", false,
102: "Print a formal definition of the grammar's AST, then stop.")
103: .bool("lgpl", "optionLGPL", false,
104: "Create an LGPL compliant parser.")
105: .att("option", "grammarOption", true,
106: "Add the specified attribute to the grammar's options.")
107: .bool("Onone", "doNotOptimize", false,
108: "Perform no optimizations.")
109: .bool("Ochunks", "optimizeChunks", true,
110: "Break memoization table into chunks.")
111: .bool("Ogrammar", "optimizeGrammar", true,
112: "Fold duplicate productions and eliminate dead productions.")
113: .bool("Oterminals", "optimizeTerminals", true,
114: "Optimize the recognition of terminals, incl. by using switches.")
115: .bool("Ocost", "optimizeCost", true,
116: "Perform cost-based inlining.")
117: .bool("Otransient", "optimizeTransient", true,
118: "Do not memoize transient productions.")
119: .bool("Onontransient", "optimizeNonTransient", true,
120: "Mark suitable productions as transient.")
121: .bool("Orepeated", "optimizeRepeated", true,
122: "Do not desugar transient repetitions.")
123: .bool("Oleft1", "optimizeLeftRecursions", false,
124: "Convert direct left-recursions into equivalent right-recursions.")
125: .bool("Oleft2", "optimizeLeftIterations", true,
126: "Convert direct left-recursions into equivalent iterations.")
127: .bool("Ooptional", "optimizeOptional", true,
128: "Do not desugar options.")
129: .bool("Ochoices1", "optimizeChoices1", true,
130: "Inline transient void or text-only productions into choices.")
131: .bool("Ochoices2", "optimizeChoices2", true,
132: "Inline productions with the inline attribute into choices.")
133: .bool("Oerrors1", "optimizeErrors1", true,
134: "Avoid creating parse errors for individual terms.")
135: .bool("Oerrors2", "optimizeErrors2", false,
136: "Avoid creating parse errors for transient productions.")
137: .bool("Oselect", "optimizeSelect", true,
138: "Optimize the selection of parse errors.")
139: .bool("Ovalues", "optimizeValues", true,
140: "Avoid creating duplicate semantic values.")
141: .bool("Omatches", "optimizeMatches", true,
142: "Optimize the performance of string matches.")
143: .bool("Oprefixes", "optimizePrefixes", true,
144: "Fold common prefixes in choices.")
145: .bool("Ognodes", "optimizeGenericNodes", true,
146: "Optimize the creation of generic nodes.")
147: .bool("Olocation", "optimizeLocation", true,
148: "Optimize the annotation of nodes with their source locations.");
149: }
150:
151: public void prepare() {
152: boolean explicitOptimizations = runtime
153: .hasPrefixValue("optimize");
154: boolean doNotOptimize = runtime.hasValue("doNotOptimize")
155: && runtime.test("doNotOptimize");
156:
157: // Check optimization options.
158: if (explicitOptimizations && doNotOptimize) {
159: runtime
160: .error("no optimizations incompatible with explicitly specified "
161: + "optimizations");
162: }
163:
164: if (runtime.hasValue("optimizeLeftRecursions")
165: && runtime.test("optimizeLeftRecursions")
166: && runtime.hasValue("optimizeLeftIterations")
167: && runtime.test("optimizeLeftIterations")) {
168: runtime
169: .error("left1 option mutually exclusive with left2 option");
170: }
171:
172: // Now, fill in the defaults.
173: if (explicitOptimizations || doNotOptimize) {
174: runtime.initFlags("optimize", false);
175: }
176: runtime.initDefaultValues();
177:
178: // Perform consistency checking of other options.
179: if (runtime.test("optionSilent")
180: && runtime.test("optionVerbose")) {
181: runtime
182: .error("can't run in silent and verbose mode at the same time");
183: }
184: if (runtime.test("optionLoaded")) {
185: if (runtime.test("optionInstantiated")) {
186: runtime
187: .error("loaded option incompatible with instantiated option");
188: }
189: if (runtime.test("optionApplied")) {
190: runtime
191: .error("loaded option incompatible with applied option");
192: }
193: if (runtime.test("optionValued")) {
194: runtime
195: .error("loaded option incompatiable with valued option");
196: }
197: if (runtime.test("optionProcessed")) {
198: runtime
199: .error("loaded option incompatible with processed option");
200: }
201: if (runtime.test("optionASTDefinition")) {
202: runtime
203: .error("loaded option incompatible with ast option");
204: }
205: }
206: if (runtime.test("optionInstantiated")) {
207: if (runtime.test("optionApplied")) {
208: runtime
209: .error("instantiated option incompatible with applied option");
210: }
211: if (runtime.test("optionValued")) {
212: runtime
213: .error("instantiated option incompatible with valued option");
214: }
215: if (runtime.test("optionProcessed")) {
216: runtime
217: .error("instantiated option incompatible with processed option");
218: }
219: if (runtime.test("optionASTDefinition")) {
220: runtime
221: .error("instantiated option incompatible with ast option");
222: }
223: }
224: if (runtime.test("optionApplied")) {
225: if (runtime.test("optionValued")) {
226: runtime
227: .error("applied option incompatible with valued option");
228: }
229: if (runtime.test("optionProcessed")) {
230: runtime
231: .error("applied option incompatible with processed option");
232: }
233: if (runtime.test("optionASTDefinition")) {
234: runtime
235: .error("applied option incompatible with ast option");
236: }
237: }
238: if (runtime.test("optionValued")) {
239: if (runtime.test("optionProcessed")) {
240: runtime
241: .error("valued option incompatible with processed option");
242: }
243: if (runtime.test("optionASTDefinition")) {
244: runtime
245: .error("valued option incompatible with ast option");
246: }
247: }
248: if (runtime.test("optionProcessed")
249: && runtime.test("optionASTDefinition")) {
250: runtime
251: .error("processed option incompatible with ast option");
252: }
253: if (runtime.test("optionHtml")) {
254: if (runtime.test("optionLoaded")) {
255: runtime
256: .error("loaded option incompatible with html option");
257: } else if ((!runtime.test("optionInstantiated"))
258: && (!runtime.test("optionApplied"))
259: && (!runtime.test("optionValued"))
260: && (!runtime.test("optionProcessed"))) {
261: runtime
262: .error("html option requires instantiated, applied, valued or "
263: + "processed option");
264: }
265: }
266: }
267:
268: public Node parse(Reader in, File file) throws IOException,
269: ParseException {
270: long length = file.length();
271: if (Integer.MAX_VALUE < length) {
272: throw new IllegalArgumentException(file
273: + ": file too large");
274: }
275: PParser parser = new PParser(in, file.toString(), (int) length);
276: Result result = parser.pModule(0);
277: Module mod = (Module) parser.value(result);
278: String name = file.getName();
279:
280: // Chop off extension.
281: int idx = name.lastIndexOf('.');
282: if (-1 != idx)
283: name = name.substring(0, idx);
284:
285: // Make sure the unqualified module name and the unqualified
286: // file name match.
287: if (!name.equals(Utilities.unqualify(mod.name.name))) {
288: runtime.error("module name '" + mod.name.name
289: + "' inconsistent with file name '" + file + "'",
290: mod.name);
291: }
292:
293: // Return the module.
294: return mod;
295: }
296:
297: public void process(Node node) {
298: Module module = (Module) node;
299:
300: // --------------------------------------------------------------------
301: // Analyze and transform module
302: // --------------------------------------------------------------------
303:
304: // Prepare for the work.
305: Analyzer ana = new Analyzer();
306: AST ast = new JavaAST();
307: Simplifier simple = new Simplifier(runtime, ana);
308: DeadProductionEliminator dead = new DeadProductionEliminator(
309: runtime, ana);
310: DuplicateProductionFolder dup = new DuplicateProductionFolder(
311: runtime, ana);
312: PrefixFolder prefix = new PrefixFolder(runtime, ana);
313: MetaDataCreator meta = new MetaDataCreator();
314: ReferenceCounter ref = new ReferenceCounter(runtime, ana);
315: TransientMarker trans = new TransientMarker(runtime, ana);
316: Inliner line = new Inliner(runtime, ana);
317:
318: // Add options from the command line.
319: if (null == module.attributes) {
320: module.attributes = new ArrayList<Attribute>();
321: }
322: module.attributes.addAll(runtime
323: .getAttributeList("grammarOption"));
324:
325: // Resolve all dependencies and check for well-formedness. Note
326: // that Resolver marks all text-only productions and recognizes
327: // direct left-recursions.
328: module = (Module) new Resolver(runtime, ana, ast)
329: .dispatch(module);
330: if (runtime.test("optionLoaded")
331: || runtime.test("optionApplied") || (null == module)) {
332: return;
333: }
334:
335: // If the grammar has the genericAsVoid attribute, void out
336: // generic productions.
337: if (module.hasAttribute(Constants.ATT_GENERIC_AS_VOID)) {
338: new GenericVoider(runtime, ana).dispatch(module);
339: }
340:
341: // Start simplifying the grammar: Find the real root, simplify
342: // expressions, void out repetitions, options, and nested choices
343: // without a value, and remove dead productions.
344: new RootFinder(runtime, ana).dispatch(module);
345: simple.dispatch(module);
346: if (runtime.test("optimizeGrammar"))
347: dead.dispatch(module);
348: new ElementVoider(runtime, ana).dispatch(module);
349:
350: // Determine a grammar's variants.
351: if (runtime.test("optionVariant")) {
352: new VariantSorter(runtime, ana, ast).dispatch(module);
353: if (0 < runtime.errorCount())
354: return;
355: }
356:
357: // Further simplify the grammar: Fold duplicate productions, fold
358: // common prefixes, inline productions, and mark productions as
359: // transient.
360: //
361: // Note that we need to fold duplicates before marking productions
362: // as transient, because a folded duplicate may be referenced more
363: // than once and thus should not be marked as transient, even
364: // though the non-folded productions could be marked as transient.
365: if (runtime.test("optimizeGrammar"))
366: dup.dispatch(module);
367: if (runtime.test("optimizePrefixes"))
368: prefix.dispatch(module);
369: boolean changed = false;
370: do {
371: changed = ((Boolean) line.dispatch(module)).booleanValue();
372: if (changed) {
373: simple.dispatch(module);
374: if (runtime.test("optimizeGrammar"))
375: dead.dispatch(module);
376: if (runtime.test("optimizePrefixes"))
377: prefix.dispatch(module);
378: }
379: if (runtime.test("optimizeNonTransient")) {
380: meta.dispatch(module);
381: ref.dispatch(module);
382: trans.dispatch(module);
383: }
384: } while (changed);
385:
386: // If requested, annotate the grammar to preserve all formatting.
387: if (module.hasAttribute(Constants.ATT_PARSE_TREE)) {
388: new Tokenizer(runtime, ana).dispatch(module);
389: new Annotator(runtime, ana).dispatch(module);
390: }
391:
392: // Determine each production's semantic value: make the values
393: // explicit; lift nested choices, repetitions, and options;
394: // transform repetitions, options, and direct left recursions;
395: // and, finally, check that every alternative has a semantic
396: // value.
397: new Transformer(runtime, ana, ast).dispatch(module);
398: if (!runtime.test("optionValued")) {
399: new ListMaker(runtime, ana, ast).dispatch(module);
400: new DirectLeftRecurser(runtime, ana, ast).dispatch(module);
401: new Generifier(runtime, ana).dispatch(module);
402: new ValueChecker(runtime, ana).dispatch(module);
403: }
404:
405: // If there were errors, we are done.
406: if (0 < runtime.errorCount())
407: return;
408:
409: // If requested, print the reduced grammar and then stop.
410: if (runtime.test("optionValued")) {
411: new TreeExtractor(runtime, ana, ast, false)
412: .dispatch(module);
413: if (runtime.test("optionHtml")) {
414: new HtmlPrinter(runtime, ana, ast, true)
415: .dispatch(module);
416: } else {
417: new PrettyPrinter(runtime.console(), ast, true)
418: .dispatch(module);
419: runtime.console().flush();
420: }
421: return;
422: }
423:
424: // Optimize the grammar.
425: if (runtime.test("optimizeChoices1")
426: || runtime.test("optimizeChoices2")) {
427: meta.dispatch(module);
428: ref.dispatch(module);
429: new ChoiceExpander(runtime, ana).dispatch(module);
430: }
431: if (runtime.test("optimizeTerminals")) {
432: new ProductionVoider(runtime, ana).dispatch(module);
433: new TerminalOptimizer(runtime, ana).dispatch(module);
434: }
435: if (runtime.test("optimizePrefixes")) {
436: // Perform prefix folding again, as the expanding of choices may
437: // lead to new common prefixes.
438: prefix.dispatch(module);
439:
440: // Check for unreachable alternatives (again since this was
441: // already done inside Resolver).
442: new ReachabilityChecker(runtime, ana).dispatch(module);
443: if (0 < runtime.errorCount())
444: return;
445: }
446: if (runtime.test("optimizeGrammar")) {
447: // Do duplicate production folding again, as the desugaring of
448: // options and repetitions can lead to new duplicates. Do
449: // dead production elimination again, as the expanding of
450: // choices can lead to new deaths.
451: dead.dispatch(module);
452: dup.dispatch(module);
453: }
454: meta.dispatch(module);
455: ref.dispatch(module);
456: if (runtime.test("optimizeNonTransient")) {
457: trans.dispatch(module);
458: }
459: new MetaDataSetter(runtime, ana, ast).dispatch(module);
460: if (0 < runtime.errorCount())
461: return;
462:
463: // --------------------------------------------------------------------
464: // Print AST definition and processed grammar
465: // --------------------------------------------------------------------
466:
467: if (runtime.test("optionASTDefinition")) {
468: new TreeTyper(runtime, ana, ast).dispatch(module);
469: return;
470:
471: } else if (runtime.test("optionProcessed")) {
472: if (runtime.test("optionHtml")) {
473: new HtmlPrinter(runtime, ana, ast, true)
474: .dispatch(module);
475: } else {
476: new PrettyPrinter(runtime.console(), ast, true)
477: .dispatch(module);
478: runtime.console().flush();
479: }
480: return;
481: }
482:
483: // --------------------------------------------------------------------
484: // Generate parser
485: // --------------------------------------------------------------------
486:
487: File file = new File(runtime.getOutputDirectory(), Utilities
488: .getName(module.getClassName())
489: + ".java");
490: Printer out;
491: try {
492: out = new Printer(new PrintWriter(runtime.getWriter(file)));
493: } catch (IOException x) {
494: if (null == x.getMessage()) {
495: runtime.error(file.toString() + ": I/O error");
496: } else {
497: runtime.error(file.toString() + ": " + x.getMessage());
498: }
499: return;
500: }
501: printHeader(out);
502: new CodeGenerator(runtime, ana, ast, out).dispatch(module);
503: out.flush().close();
504: }
505:
506: /**
507: * Run the packrat parser generator with the specified arguments.
508: * Invoking <i>Rats!</i> without arguments will print information
509: * about its usage.
510: *
511: * @param args The command line arguments.
512: */
513: public static void main(String[] args) {
514: new Rats().run(args);
515: }
516:
517: }
|