001: /*
002: * xtc - The eXTensible Compiler
003: * Copyright (C) 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 xtc.tree.Visitor;
022:
023: import xtc.type.AST;
024:
025: import xtc.util.Runtime;
026:
027: /**
028: * Visitor to pear down a grammar to the structure of its abstract
029: * syntax tree. This visitor assumes that the entire grammar is
030: * contained in a single module. It also assumes that directly
031: * left-recursive generic productions have <em>not</em> been
032: * transformed by {@link DirectLeftRecurser}. Note that, after this
033: * visitor has processed the grammar, the grammar violates the code
034: * generator's requirements. Also note that this visitor internally
035: * uses {@link Simplifier} and {@link DeadProductionEliminator}.
036: *
037: * @author Robert Grimm
038: * @version $Revision: 1.11 $
039: */
040: public class TreeExtractor extends Visitor {
041:
042: /** The runtime. */
043: protected final Runtime runtime;
044:
045: /** The analyzer utility. */
046: protected final Analyzer analyzer;
047:
048: /** The common type operations. */
049: protected final AST ast;
050:
051: /** The flag for removing all elements from lexical productions. */
052: protected final boolean keepLexical;
053:
054: /** The flag for whether the current production is generic. */
055: protected boolean isGeneric;
056:
057: /** The flag for whether the current production is list-valued. */
058: protected boolean isList;
059:
060: /** The flag for whether the current production is text-only. */
061: protected boolean isTextOnly;
062:
063: /** The flag for whether the current production is token-level. */
064: protected boolean isToken;
065:
066: /**
067: * The flag for whether the current production defines the semantic
068: * value in an explicit action.
069: */
070: protected boolean setsValue;
071:
072: /**
073: * Create a new tree extractor.
074: *
075: * @param runtime The runtime.
076: * @param analyzer The analyzer utility.
077: * @param ast The type operations.
078: * @param keepLexical The flag for keeping elements of text-only
079: * or token-level productions.
080: */
081: public TreeExtractor(Runtime runtime, Analyzer analyzer, AST ast,
082: boolean keepLexical) {
083: this .runtime = runtime;
084: this .analyzer = analyzer;
085: this .ast = ast;
086: this .keepLexical = keepLexical;
087: }
088:
089: /** Visit the specified module. */
090: public void visit(Module m) {
091: // Initialize the per-grammar state.
092: analyzer.register(this );
093: analyzer.init(m);
094:
095: // Process the productions.
096: for (Production p : m.productions) {
097: analyzer.process(p);
098: }
099:
100: // Simplify the grammar and eliminate any dead productions.
101: new Simplifier(runtime, analyzer).dispatch(m);
102: new DeadProductionEliminator(runtime, analyzer).dispatch(m);
103:
104: // Eliminate any actions and attributes.
105: m.header = null;
106: m.body = null;
107: m.footer = null;
108: m.attributes = null;
109:
110: // Eliminate the production's attributes and internal types.
111: for (Production p : m.productions) {
112: p.attributes = null;
113: p.type = null;
114: }
115: }
116:
117: /** Visit the specified full production. */
118: public void visit(FullProduction p) {
119: // Initialize the per-production state.
120: isGeneric = Generifier.isGeneric(p);
121: isList = AST.isList(p.type);
122: isTextOnly = p.getBooleanProperty(Properties.TEXT_ONLY);
123: isToken = p.getBooleanProperty(Properties.TOKEN);
124: setsValue = false;
125:
126: // Preprocess directly left-recursive generic productions.
127: if (isGeneric && DirectLeftRecurser.isTransformable(p)) {
128: for (Sequence s : p.choice.alternatives) {
129: if (!DirectLeftRecurser.isRecursive(s, p)) {
130: Binding b = analyzer.bind(s.elements);
131: if (null != b)
132: b.name = CodeGenerator.VALUE;
133: }
134: }
135: }
136:
137: // Process the choice.
138: if ((isTextOnly || isToken) && (!keepLexical)) {
139: p.choice = new OrderedChoice(new Sequence());
140: p.setProperty(Properties.REDACTED, Boolean.TRUE);
141: } else {
142: dispatch(p.choice);
143: }
144:
145: // Patch the type.
146: final String s = ast.extern(p.type);
147: if (isGeneric) {
148: p.dType = "define<Node>";
149: } else if (isTextOnly) {
150: p.dType = "define<String>";
151: } else if (isToken) {
152: p.dType = "define<Token>";
153: } else if (isList) {
154: p.dType = "define<" + s + '>';
155: } else if (setsValue) {
156: p.dType = "define<" + s + '>';
157: } else {
158: p.dType = "expand<" + s + '>';
159: }
160: }
161:
162: /** Visit the specified ordered choice. */
163: public void visit(OrderedChoice c) {
164: for (Sequence alt : c.alternatives)
165: dispatch(alt);
166: }
167:
168: /** Visit the specified sequence. */
169: public void visit(Sequence s) {
170: // Eliminate the sequence name.
171: s.name = null;
172:
173: // Process the elements.
174: for (int i = 0; i < s.size(); i++) {
175: Element e = s.get(i);
176:
177: // If the element is a trailing choice, process its sequences.
178: if ((s.size() - 1 == i) && (e instanceof OrderedChoice)) {
179: dispatch(e);
180: continue;
181: }
182:
183: // If the element is a voided element, semantic predicate, or
184: // value element, remove the element and move on to the next
185: // element.
186: if ((e instanceof VoidedElement)
187: || (e instanceof SemanticPredicate)
188: || (e instanceof ValueElement)) {
189: s.elements.remove(i);
190: i--;
191: continue;
192: }
193:
194: // If the element is an action that sets the semantic value,
195: // simplify it. Otherwise, remove the action.
196: if (e instanceof Action) {
197: Action a = (Action) e;
198:
199: if (a.setsValue()) {
200: setsValue = true;
201:
202: a.code.clear();
203: a.indent.clear();
204:
205: a.code.add("yyValue = ...");
206: a.indent.add(0);
207:
208: } else {
209: s.elements.remove(i);
210: i--;
211: }
212: continue;
213: }
214:
215: // Process bindings. In generic productions, we get rid of
216: // bindings unless they bind yyValue (since they indicate a
217: // passed-through value). In productions that are neither
218: // generic, text-valued, or text-only, we get rid of elements if
219: // they are not bound (since they cannot contribute to a
220: // semantic value).
221: if (e instanceof Binding) {
222: Binding b = (Binding) e;
223:
224: if ((!isGeneric)
225: || (isGeneric && (!CodeGenerator.VALUE
226: .equals(b.name)))) {
227: e = b.element;
228: s.elements.set(i, e);
229: }
230: // Continue processing the element.
231:
232: } else if ((!isGeneric) && (!isList) && (!isTextOnly)
233: && (!isToken)) {
234: s.elements.remove(i);
235: i--;
236: continue;
237: }
238:
239: // Remove any void nonterminals.
240: if (e instanceof NonTerminal) {
241: FullProduction p = analyzer.lookup((NonTerminal) e);
242:
243: if (AST.isVoid(p.type)) {
244: s.elements.remove(i);
245: i--;
246: continue;
247: }
248: }
249:
250: // Process the element.
251: dispatch(e);
252: }
253: }
254:
255: /** Visit the specified character case. */
256: public void visit(CharCase c) {
257: dispatch(c.element);
258: }
259:
260: /** Visit the specified character switch. */
261: public void visit(CharSwitch s) {
262: for (CharCase c : s.cases) {
263: dispatch(c);
264: }
265: dispatch(s.base);
266: }
267:
268: /** Visit the specified unary operator. */
269: public void visit(UnaryOperator op) {
270: dispatch(op.element);
271:
272: // Strip any unnecessary choices and sequences.
273: op.element = Analyzer.strip(op.element);
274: }
275:
276: /** Visit the specified element. */
277: public void visit(Element e) {
278: // Nothing to do.
279: }
280:
281: }
|