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.util.ArrayList;
022: import java.util.List;
023:
024: import xtc.tree.Visitor;
025:
026: import xtc.type.AST;
027:
028: import xtc.util.Runtime;
029:
030: /**
031: * Visitor to add generic nodes as semantic values.
032: *
033: * <p />For any production with pseudotype "<code>generic</code>" that
034: * does not contain any direct left-recursions (which is also called a
035: * generic node production), this visitor adds the appropriate {@link
036: * GenericNodeValue generic node value} elements, which create a
037: * {@link xtc.tree.GNode generic node} as the productions' semantic
038: * value. The children of such a generic node are the matched
039: * component values of the production, though voided elements, void
040: * nonterminals, and character terminals are not included. If an
041: * alternative assigns {@link CodeGenerator#VALUE} either through a
042: * binding or a semantic action, that alternative's semantic value is
043: * the specified semantic value and not a newly generated generic
044: * node. This visitor requires that all nested choices that do not
045: * appear as the last element in a sequence have been lifted. It also
046: * assumes that the entire grammar is contained in a single module.
047: *
048: * <p />Note that this visitor does not process generic productions
049: * that contain direct left-recursions; they are processed by {@link
050: * DirectLeftRecurser}.
051: *
052: * @author Robert Grimm
053: * @version $Revision: 1.55 $
054: */
055: public class Generifier extends Visitor {
056:
057: /** The marker for synthetic variables. */
058: public static final String MARKER = "g";
059:
060: /** The runtime. */
061: protected final Runtime runtime;
062:
063: /** The analyzer utility. */
064: protected final Analyzer analyzer;
065:
066: /**
067: * The list of variables representing the children of the generic
068: * node to be created.
069: */
070: protected List<Binding> children;
071:
072: /** The list of node markers. */
073: protected List<NodeMarker> markers;
074:
075: /**
076: * Create a new generifier.
077: *
078: * @param runtime The runtime.
079: * @param analyzer The analyzer utility.
080: */
081: public Generifier(Runtime runtime, Analyzer analyzer) {
082: this .runtime = runtime;
083: this .analyzer = analyzer;
084: this .children = new ArrayList<Binding>();
085: this .markers = new ArrayList<NodeMarker>();
086: }
087:
088: /**
089: * Create a binding for the specified element. This method also
090: * adds the name of the bound variable to the end of the list of
091: * children.
092: *
093: * @param e The element to bind.
094: * @return The corresponding binding.
095: */
096: protected Binding bind(Element e) {
097: Binding b = new Binding(analyzer.variable(MARKER), e);
098: children.add(b);
099: return b;
100: }
101:
102: /** Visit the specified grammar. */
103: public void visit(Module m) {
104: // Initialize the analyzer.
105: analyzer.register(this );
106: analyzer.init(m);
107:
108: // Process the productions.
109: for (Production p : m.productions) {
110: if (isGenericNode((FullProduction) p)) {
111: analyzer.process(p);
112: }
113: }
114: }
115:
116: /** Visit the specified production. */
117: public void visit(FullProduction p) {
118: // Process the production's element.
119: p.choice = (OrderedChoice) dispatch(p.choice);
120:
121: // Patch the type (but only for dynamically typed productions).
122: if (AST.isDynamicNode(p.type))
123: p.type = AST.NODE;
124:
125: // Mark the production as a generic node production.
126: markGenericNode(p, runtime.test("optionVerbose"));
127: }
128:
129: /** Visit the specified ordered choice. */
130: public Element visit(OrderedChoice c) {
131: // Process the alternatives.
132: final int size = c.alternatives.size();
133: for (int i = 0; i < size; i++) {
134: Sequence alternative = c.alternatives.get(i);
135:
136: // We only add generic node values to the current alternative if
137: // that alternative does not contain any simple values, i.e.,
138: // either bindings to CodeGenerator.VALUE or value elements.
139: if (!Analyzer.setsValue(alternative, true)) {
140: c.alternatives.set(i, (Sequence) dispatch(alternative));
141: }
142: }
143:
144: // Done.
145: return c;
146: }
147:
148: /** Visit the specified repetition. */
149: public Element visit(Repetition r) {
150: return bind(r);
151: }
152:
153: /** Visit the specified option. */
154: public Element visit(Option o) {
155: return bind(o);
156: }
157:
158: /** Visit the specified sequence. */
159: public Element visit(Sequence s) {
160: // Remember the current number of children and markers.
161: final int base = children.size();
162: final int base2 = markers.size();
163:
164: // Process the elements of the sequence.
165: final int size = s.size();
166: for (int i = 0; i < size; i++) {
167: s.elements.set(i, (Element) dispatch(s.get(i)));
168: }
169:
170: // If this sequence has not ended with a choice, add the
171: // appropriate semantic value.
172: if (!s.hasTrailingChoice()) {
173: final String name;
174: if (0 == markers.size()) {
175: name = analyzer.current().name.unqualify().name;
176: } else {
177: name = markers.get(markers.size() - 1).name;
178: }
179:
180: final List<Binding> formatting;
181: if (s.hasProperty(Properties.FORMATTING)) {
182: formatting = Properties.getFormatting(s);
183: } else {
184: formatting = new ArrayList<Binding>(0);
185: }
186:
187: s.add(new GenericNodeValue(name, new ArrayList<Binding>(
188: children), formatting));
189: }
190:
191: // Remove any children and markers added by processing the sequence.
192: if (0 == base) {
193: children.clear();
194: } else {
195: children.subList(base, children.size()).clear();
196: }
197:
198: if (0 == base2) {
199: markers.clear();
200: } else {
201: markers.subList(base2, markers.size()).clear();
202: }
203:
204: // Done.
205: return s;
206: }
207:
208: /** Visit the specified binding. */
209: public Element visit(Binding b) {
210: // Record the binding.
211: children.add(b);
212:
213: // We assume that the bound expression does not require any
214: // further processing. I.e., if it is a repetition, option, or
215: // choice, it already has been lifted and replaced by a
216: // nonterminal.
217:
218: // Done.
219: return b;
220: }
221:
222: /** Visit the specified string match. */
223: public Element visit(StringMatch m) {
224: return bind(m);
225: }
226:
227: /** Visit the specified nonterminal. */
228: public Element visit(NonTerminal nt) {
229: FullProduction p = analyzer.lookup(nt);
230: if (AST.isVoid(p.type)) {
231: return nt;
232: } else {
233: return bind(nt);
234: }
235: }
236:
237: /** Visit the specified string literal. */
238: public Element visit(StringLiteral l) {
239: return bind(l);
240: }
241:
242: /** Visit the specified parse tree node. */
243: public Element visit(ParseTreeNode n) {
244: return bind(n);
245: }
246:
247: /** Visit the specified null literal. */
248: public Element visit(NullLiteral l) {
249: return bind(l);
250: }
251:
252: /** Visit the specified node marker. */
253: public Element visit(NodeMarker m) {
254: markers.add(m);
255: return m;
256: }
257:
258: /**
259: * Visit the specified element. This method provides the default
260: * implementation for predicates, voided elements, character
261: * terminals, (parser) actions, and value elements.
262: */
263: public Element visit(Element e) {
264: return e;
265: }
266:
267: /**
268: * Mark the specified production as a generic node production.
269: *
270: * @param p The production.
271: * @param verbose The flag for whether to be verbose.
272: */
273: public static void markGenericNode(FullProduction p, boolean verbose) {
274: if (verbose) {
275: System.err.println("[Recognizing " + p.qName
276: + " as generic node]");
277: }
278: p.setProperty(Properties.GENERIC, Properties.GENERIC_NODE);
279: }
280:
281: /**
282: * Mark the specified production as a generic recursion production.
283: *
284: * @param p The production.
285: * @param verbose The flag for whether to be verbose.
286: */
287: public static void markGenericRecursion(FullProduction p,
288: boolean verbose) {
289: if (verbose) {
290: System.err.println("[Recognizing " + p.qName
291: + " as generic recursion]");
292: }
293: p.setProperty(Properties.GENERIC, Properties.GENERIC_RECURSION);
294: }
295:
296: /**
297: * Determine whether the specified production is a generic node or a
298: * generic recursion production.
299: *
300: * @param p The production.
301: * @return <code>true</code> if the specified production is a generic
302: * node or generic recursion production.
303: */
304: public static boolean isGeneric(FullProduction p) {
305: if (p.hasProperty(Properties.GENERIC)) {
306: Object value = p.getProperty(Properties.GENERIC);
307:
308: return (Properties.GENERIC_NODE.equals(value) || Properties.GENERIC_RECURSION
309: .equals(value));
310: } else {
311: return AST.isGenericNode(p.type);
312: }
313: }
314:
315: /**
316: * Determine whether the specified production is a generic node
317: * production. A production is a generic node production if its
318: * semantic value is an automatically generated generic node with
319: * the component values as its children.
320: *
321: * @param p The production.
322: * @return <code>true</code> if the specified production is
323: * a generic node production.
324: */
325: public static boolean isGenericNode(FullProduction p) {
326: if (p.hasProperty(Properties.GENERIC)) {
327: return Properties.GENERIC_NODE.equals(p
328: .getProperty(Properties.GENERIC));
329: } else {
330: return (AST.isGenericNode(p.type) && (!DirectLeftRecurser
331: .isTransformable(p)));
332: }
333: }
334:
335: /**
336: * Determine whether the specified production is a generic recursion
337: * production. A production is a generic recursion production if
338: * its semantic value is an automatically generated generic node and
339: * the production, as specified, contains one or more direct
340: * left-recursions that can automatically be transformed into the
341: * corresponding right-recursions.
342: *
343: * @see DirectLeftRecurser
344: *
345: * @param p The production.
346: * @return <code>true</code> if the specified production is
347: * a generic recursion production.
348: */
349: public static boolean isGenericRecursion(FullProduction p) {
350: if (p.hasProperty(Properties.GENERIC)) {
351: return Properties.GENERIC_RECURSION.equals(p
352: .getProperty(Properties.GENERIC));
353: } else {
354: return (AST.isGenericNode(p.type) && DirectLeftRecurser
355: .isTransformable(p));
356: }
357: }
358:
359: }
|