001: /*
002: * xtc - The eXTensible Compiler
003: * Copyright (C) 2005-2006 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.HashSet;
022: import java.util.Set;
023:
024: import xtc.Constants;
025:
026: import xtc.util.Runtime;
027:
028: /**
029: * Visitor to identify a grammar's real root. A real root is a
030: * top-level nonterminal, whose production directly or indirectly
031: * depends on all other top-level nonterminals. If a grammar has such
032: * a root, this visitor annotates the grammar with the {@link
033: * Properties#ROOT root} property.
034: *
035: * <p />Note that this visitor assumes that the entire grammar is
036: * contained in a single module.
037: *
038: * @author Robert Grimm
039: * @version $Revision: 1.12 $
040: */
041: public class RootFinder extends GrammarVisitor {
042:
043: /** The set of qualified top-level nonterminals. */
044: protected Set<NonTerminal> topLevel;
045:
046: /**
047: * Create a new root finder.
048: *
049: * @param runtime The runtime.
050: * @param analyzer The analyzer utility.
051: */
052: public RootFinder(Runtime runtime, Analyzer analyzer) {
053: super (runtime, analyzer);
054: topLevel = new HashSet<NonTerminal>();
055: }
056:
057: /** Visit the specified grammar. */
058: public Object visit(Module m) {
059: // Make sure we don't do the work several times.
060: if (m.hasProperty(Properties.ROOT)) {
061: return null;
062: }
063:
064: // Initialize the per-grammar state.
065: analyzer.register(this );
066: analyzer.init(m);
067:
068: // Fill in the set of top-level nonterminals.
069: topLevel.clear();
070: for (Production p : m.productions) {
071: if (p.hasAttribute(Constants.ATT_PUBLIC)) {
072: topLevel.add(p.qName);
073: }
074: }
075:
076: // Get the trivial case out of the way.
077: if (1 == topLevel.size()) {
078: m.setProperty(Properties.ROOT, topLevel.toArray()[0]);
079: return null;
080: }
081:
082: // Traverse the grammar, starting with each top-level nonterminal.
083: for (NonTerminal nt : topLevel) {
084: // Mark the top-level nonterminals.
085: analyzer.unmarkAll();
086: analyzer.mark(topLevel);
087:
088: // Traverse the grammar.
089: analyzer.notWorkingOnAny();
090: dispatch(nt);
091:
092: // Is this nonterminal a real root?
093: if (!analyzer.hasMarked()) {
094: if (runtime.test("optionVerbose")) {
095: System.err.println("[Recognizing " + nt
096: + " as real root]");
097: }
098: m.setProperty(Properties.ROOT, nt);
099: break;
100: }
101: }
102:
103: // Done.
104: return null;
105: }
106:
107: /** Visit the specified nonterminal. */
108: public Element visit(NonTerminal nt) {
109: Production p = analyzer.lookup(nt);
110:
111: if (!analyzer.isBeingWorkedOn(p.qName)) {
112: analyzer.workingOn(p.qName);
113: analyzer.unmark(p.qName);
114: dispatch(p);
115: }
116: return nt;
117: }
118:
119: }
|