001: /*
002: * xtc - The eXTensible Compiler
003: * Copyright (C) 2004 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: * as published by the Free Software Foundation; either version 2
008: * of the License, or (at your option) any later version.
009: *
010: * This program is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
013: * GNU General Public License for more details.
014: *
015: * You should have received a copy of the GNU General Public License
016: * along with this program; if not, write to the Free Software
017: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
018: */
019: package xtc.parser;
020:
021: import java.util.ArrayList;
022: import java.util.Iterator;
023: import java.util.List;
024:
025: import xtc.tree.Visitor;
026:
027: /**
028: * Visitor to transform productions. This visitor lifts repetitions,
029: * options, and nested choices into their own productions, desugars
030: * reptitions and options, and adds the appropriate semantic values to
031: * expressions that require them. It also ensures that all options
032: * and syntactic predicates are sequences, thus fullfilling the
033: * requirements for {@link CodeGenerator code generation}. Before
034: * applying this visitor on a grammar, the grammar must have been
035: * {@link Simplifier simplified} and all text-only productions should
036: * be marked as such by applying the {@link TextTester} visitor.
037: *
038: * @author Robert Grimm
039: * @version $Revision: 1.2 $
040: */
041: public class Transformer extends Visitor {
042:
043: /** The analyzer utility. */
044: protected final Analyzer analyzer;
045:
046: /** The flag for whether the current production is text-only. */
047: protected boolean isTextOnly;
048:
049: /** The flag for whether the current production is void. */
050: protected boolean isVoid;
051:
052: /** The flag for whether the current element is top-level. */
053: protected boolean isTopLevel;
054:
055: /**
056: * The flag for whether to transform ordered choices, repetition,
057: * and options in place, instead of creating a new production.
058: */
059: protected boolean transformInPlace;
060:
061: /**
062: * The flag for whether the current element is the last element in a
063: * sequence.
064: */
065: protected boolean isLastElement;
066:
067: /** The flag for whether we are currently processing a predicate. */
068: protected boolean isPredicate;
069:
070: /** The flag for whether the current element is bound. */
071: protected boolean isBound;
072:
073: /**
074: * Create a new transformer.
075: *
076: * @param analyzer The analyzer utility for the new transformer.
077: */
078: public Transformer(Analyzer analyzer) {
079: this .analyzer = analyzer;
080: }
081:
082: /**
083: * Determine whether the current production may contain repetitions.
084: * A production may contain repetitions if it is transient void or
085: * transient text-only and if the corresponding optimization option
086: * ("<code>-Orepeated</code>") is set.
087: */
088: protected boolean repeatable() {
089: return (Rats.optimizeRepeated && analyzer.current().isTransient && (isVoid || isTextOnly));
090: }
091:
092: /** Visit the specified grammar. */
093: public void visit(Grammar g) {
094: // Initialize the per-grammar state.
095: analyzer.register(this );
096: analyzer.init(g);
097:
098: // Now, process the productions.
099: for (int i = 0; i < g.productions.size(); i++) {
100: Production p = (Production) g.productions.get(i);
101:
102: // Initialize the per-production state.
103: isTextOnly = TextTester.isTextOnly(p);
104: isVoid = Type.isVoidT(p.type);
105: transformInPlace = false;
106: isTopLevel = true;
107: isLastElement = false;
108: isPredicate = false;
109: isBound = false;
110:
111: // Process the production.
112: analyzer.startAdding();
113: analyzer.process(p);
114:
115: // If there are new productions, add them to the grammar and
116: // make sure they are not processed again.
117: i += analyzer.addNewProductionsAt(i + 1);
118: }
119: }
120:
121: /** Visit the specified production. */
122: public void visit(Production p) {
123: // Note that we initialize all per-production state within the
124: // visit() method for the grammar.
125: p.element = (Element) p.element.accept(this );
126: }
127:
128: /** Visit the specified ordered choice. */
129: public Element visit(OrderedChoice c) {
130: boolean top = isTopLevel;
131: isTopLevel = false;
132: boolean last = isLastElement;
133: isLastElement = false;
134: boolean bound = isBound;
135: isBound = false;
136: boolean inPlace = transformInPlace;
137: transformInPlace = false;
138:
139: // If this choice is top-level, has only a single option, and that
140: // option consists of only a repetition or option (the '?' kind),
141: // replace this ordered choice with the desugared repetition or
142: // option, unless the repetition need not be desugared.
143: if (top && (1 == c.options.size())) {
144: Element e = (Element) c.options.get(0);
145:
146: if (((!repeatable()) && (e instanceof Repetition))
147: || (e instanceof Option)) {
148: if (Rats.optionVerbose) {
149: System.out.print("[Transforming top-level ");
150: if (e instanceof Repetition) {
151: System.out.print("repitition");
152: } else {
153: System.out.print("option");
154: }
155: System.out.println(" in production "
156: + analyzer.current().nonTerminal.name
157: + " in place]");
158: }
159:
160: transformInPlace = true;
161: return (Element) e.accept(this );
162: }
163: }
164:
165: // Process the options and ensure that every option has a semantic
166: // value.
167: String type = null;
168: final int length = c.options.size();
169: for (int i = 0; i < length; i++) {
170: Sequence s = Sequence.ensure((Element) ((Element) c.options
171: .get(i)).accept(this ));
172:
173: if (!inPlace) {
174: // Only add semantic values if the sequence does not end in
175: // another choice.
176: if (s.isEmpty()
177: || (!(s.get(s.length() - 1) instanceof OrderedChoice))) {
178: if (isTextOnly) {
179: if (top || bound || last) {
180: String text = analyzer.matchingText(s);
181: if ((null == text)
182: || (!Rats.optimizeTerminals)) {
183: s.elements.add(TextValue.VALUE);
184: } else {
185: s.elements.add(new StringValue(text));
186: }
187: type = Type.stringT();
188: } else {
189: s.elements.add(NullValue.VALUE);
190: type = Type.voidT();
191: }
192:
193: } else if (isVoid && (!bound)) {
194: s.elements.add(NullValue.VALUE);
195: type = Type.voidT();
196:
197: } else if (!last) {
198: // In general, we do not add semantic values for the last
199: // choice in a sequence.
200: Binding b = analyzer.bind(s);
201: if (null != b) {
202: // Patch the variable name to be the semantic value.
203: b.name = CodeGenerator.VALUE;
204: if (null == type) {
205: type = Type.type(b.element, analyzer);
206: } else {
207: type = Type.unify(type, Type.type(
208: b.element, analyzer));
209: }
210: } else {
211: type = Type.rootT();
212: }
213: }
214: }
215: }
216:
217: c.options.set(i, s);
218: }
219:
220: // If the ordered choice (1) is the top-level choice, (2) is being
221: // transformed in place, or (3) is the last element in a sequence
222: // (but not within a predicate), we are done.
223: if (top || inPlace || (last && (!isPredicate))) {
224: return c;
225: }
226:
227: // Otherwise, lift the choice.
228: NonTerminal nt = analyzer.choice();
229: Production p = new Production(analyzer.current().isTransient,
230: type, nt, c);
231: if (isTextOnly && Type.isStringT(type)) {
232: TextTester.markTextOnly(p);
233: }
234: analyzer.add(p);
235:
236: // Done.
237: return nt;
238: }
239:
240: /** Visit the specified repetition. */
241: public Element visit(Repetition r) {
242: isTopLevel = false;
243: isLastElement = false;
244: boolean bound = isBound;
245: isBound = false;
246: boolean inPlace = transformInPlace;
247: transformInPlace = isTextOnly || isVoid;
248:
249: // Process the repeated element first.
250: Element e = (Element) r.element.accept(this );
251:
252: // If the current production may contain repetitions and the
253: // repetition is not bound, then do not desugar it.
254: if (repeatable() && (!bound)) {
255: r.element = Sequence.ensure(e);
256: return r;
257: }
258:
259: // Now, desugar the repetition.
260: NonTerminal nt;
261: if (inPlace) {
262: nt = analyzer.current().nonTerminal;
263: } else {
264: nt = (r.once) ? analyzer.plus() : analyzer.star();
265: }
266:
267: List oldOptions;
268: if (e instanceof OrderedChoice) {
269: oldOptions = ((OrderedChoice) e).options;
270: } else {
271: oldOptions = new ArrayList(1);
272: oldOptions.add(e);
273: }
274:
275: List newOptions = new ArrayList(oldOptions.size()
276: + ((r.once) ? oldOptions.size() : 1));
277:
278: // The recursive options.
279: Iterator iter = oldOptions.iterator();
280: while (iter.hasNext()) {
281: Sequence s;
282: if (r.once) {
283: s = new Sequence((Element) iter.next());
284: } else {
285: s = Sequence.ensure((Element) iter.next());
286: }
287:
288: if (isTextOnly) {
289: s.elements.add(nt);
290: if (bound || inPlace) {
291: s.elements.add(TextValue.VALUE);
292: } else {
293: s.elements.add(NullValue.VALUE);
294: }
295:
296: } else if (isVoid && (!bound)) {
297: s.elements.add(nt);
298: s.elements.add(NullValue.VALUE);
299:
300: } else {
301: Binding b1 = analyzer.bind(s);
302: Binding b2 = new Binding(analyzer.variable(), nt);
303:
304: s.elements.add(b2);
305: s.elements.add(new ListValue(
306: (null == b1) ? CodeGenerator.VALUE : b1.name,
307: b2.name));
308: }
309:
310: newOptions.add(s);
311: }
312:
313: // The base option(s).
314: if (r.once) {
315: iter = oldOptions.iterator();
316: while (iter.hasNext()) {
317: Sequence s = new Sequence((Element) iter.next());
318:
319: if (isTextOnly) {
320: if (bound || inPlace) {
321: s.elements.add(TextValue.VALUE);
322: } else {
323: s.elements.add(NullValue.VALUE);
324: }
325:
326: } else if (isVoid && (!bound)) {
327: s.elements.add(NullValue.VALUE);
328:
329: } else {
330: Binding b = analyzer.bind(s);
331: s.elements
332: .add(new SingletonListValue(
333: (null == b) ? CodeGenerator.VALUE
334: : b.name));
335: }
336:
337: newOptions.add(s);
338: }
339:
340: } else {
341: Sequence s = new Sequence(new ArrayList());
342:
343: if (isTextOnly) {
344: if (bound || inPlace) {
345: s.elements.add(TextValue.VALUE);
346: } else {
347: s.elements.add(NullValue.VALUE);
348: }
349:
350: } else if (isVoid && (!bound)) {
351: s.elements.add(NullValue.VALUE);
352:
353: } else {
354: s.elements.add(EmptyListValue.VALUE);
355: }
356:
357: newOptions.add(s);
358: }
359:
360: // Create the new ordered choice.
361: OrderedChoice c = new OrderedChoice(newOptions);
362: if (inPlace) {
363: return c;
364: }
365:
366: // Create the new production.
367: String type;
368: if (isTextOnly) {
369: if (bound || inPlace) {
370: type = Type.stringT();
371: } else {
372: type = Type.voidT();
373: }
374:
375: } else if (isVoid && (!bound)) {
376: type = Type.voidT();
377:
378: } else {
379: type = Type.listT();
380: }
381:
382: Production p = new Production(analyzer.current().isTransient,
383: type, nt, c);
384: if (isTextOnly && Type.isStringT(type)) {
385: TextTester.markTextOnly(p);
386: }
387: analyzer.add(p);
388:
389: // Done.
390: return nt;
391: }
392:
393: /** Visit the specified option. */
394: public Element visit(Option o) {
395: isTopLevel = false;
396: isLastElement = false;
397: boolean bound = isBound;
398: isBound = false;
399: boolean inPlace = transformInPlace;
400: transformInPlace = true;
401:
402: // Process the optional element first.
403: Element e = (Element) o.element.accept(this );
404:
405: // Now, desugar the option.
406: NonTerminal nt = (inPlace) ? analyzer.current().nonTerminal
407: : analyzer.option();
408:
409: List oldOptions;
410: if (e instanceof OrderedChoice) {
411: oldOptions = ((OrderedChoice) e).options;
412: } else {
413: oldOptions = new ArrayList(1);
414: oldOptions.add(e);
415: }
416:
417: List newOptions = new ArrayList(oldOptions.size() + 1);
418: String type = null;
419:
420: // The matching options.
421: Iterator iter = oldOptions.iterator();
422: while (iter.hasNext()) {
423: Sequence s = Sequence.ensure((Element) iter.next());
424:
425: if (isTextOnly) {
426: if (bound || inPlace) {
427: s.elements.add(TextValue.VALUE);
428: type = Type.stringT();
429: } else {
430: s.elements.add(NullValue.VALUE);
431: type = Type.voidT();
432: }
433:
434: } else if (isVoid && (!bound)) {
435: s.elements.add(NullValue.VALUE);
436: type = Type.voidT();
437:
438: } else {
439: Binding b = analyzer.bind(s);
440: if (null != b) {
441: // Path the variable name to be the semantic value.
442: b.name = CodeGenerator.VALUE;
443: if (null == type) {
444: type = Type.type(b.element, analyzer);
445: } else {
446: type = Type.unify(type, Type.type(b.element,
447: analyzer));
448: }
449: } else {
450: type = Type.rootT();
451: }
452: }
453:
454: newOptions.add(s);
455: }
456:
457: // The (empty) alternative option.
458: Sequence alt = new Sequence(new ArrayList());
459:
460: if (isTextOnly && (bound || inPlace)) {
461: alt.elements.add(TextValue.VALUE);
462: } else {
463: alt.elements.add(NullValue.VALUE);
464: }
465:
466: newOptions.add(alt);
467:
468: // Create the new ordered choice.
469: OrderedChoice c = new OrderedChoice(newOptions);
470: if (inPlace) {
471: return c;
472: }
473:
474: // Create the new production.
475: Production p = new Production(analyzer.current().isTransient,
476: type, nt, c);
477: if (isTextOnly && Type.isStringT(type)) {
478: TextTester.markTextOnly(p);
479: }
480: analyzer.add(p);
481:
482: // Done.
483: return nt;
484: }
485:
486: /** Visit the specified sequence. */
487: public Element visit(Sequence s) {
488: isTopLevel = false;
489: isBound = false;
490: transformInPlace = false;
491: final int length = s.length();
492: for (int i = 0; i < length; i++) {
493: isLastElement = (i == length - 1);
494: s.elements.set(i, s.get(i).accept(this ));
495: }
496: isLastElement = false;
497: return s;
498: }
499:
500: /** Visit the specified predicate. */
501: public Element visit(Predicate p) {
502: boolean predicate = isPredicate;
503: isPredicate = true;
504: isTopLevel = false;
505: isLastElement = false;
506: isBound = false;
507: transformInPlace = false;
508: p.element = Sequence.ensure((Element) p.element.accept(this ));
509: isPredicate = predicate;
510: return p;
511: }
512:
513: /** Visit the specified semantic predicate. */
514: public Element visit(SemanticPredicate p) {
515: isTopLevel = false;
516: isLastElement = false;
517: isBound = false;
518: transformInPlace = false;
519: p.element = (Element) p.element.accept(this );
520: return p;
521: }
522:
523: /** Visit the specified character case. */
524: public CharCase visit(CharCase c) {
525: isTopLevel = false;
526: isLastElement = false;
527: isBound = false;
528: transformInPlace = false;
529: if (null != c.element) {
530: c.element = (Element) c.element.accept(this );
531: }
532: return c;
533: }
534:
535: /** Visit the specified character switch. */
536: public Element visit(CharSwitch s) {
537: isTopLevel = false;
538: isLastElement = false;
539: isBound = false;
540: transformInPlace = false;
541: final int length = s.cases.size();
542: for (int i = 0; i < length; i++) {
543: s.cases.set(i, ((CharCase) s.cases.get(i)).accept(this ));
544: }
545: if (null != s.base) {
546: s.base = (Element) s.base.accept(this );
547: }
548: return s;
549: }
550:
551: /**
552: * Visit the specified unary operator. This method provides the
553: * default implementation for bindings and string matches.
554: */
555: public Element visit(UnaryOperator op) {
556: isTopLevel = false;
557: isLastElement = false;
558: isBound = true;
559: transformInPlace = false;
560: op.element = (Element) op.element.accept(this );
561: return op;
562: }
563:
564: /**
565: * Visit the specified element. This method provides the default
566: * implementation for nonterminals, terminals, actions, and value
567: * elements.
568: */
569: public Element visit(Element e) {
570: isTopLevel = false;
571: isLastElement = false;
572: isBound = false;
573: transformInPlace = false;
574: return e;
575: }
576:
577: }
|