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.Collections;
023: import java.util.Iterator;
024: import java.util.Set;
025:
026: import xtc.Constants;
027:
028: import xtc.util.Utilities;
029:
030: import xtc.tree.Attribute;
031: import xtc.tree.Node;
032: import xtc.tree.Visitor;
033:
034: /**
035: * Visitor to check a grammar for consistency. This visitor should be
036: * applied on a grammar right after parsing, before any other
037: * visitors.
038: *
039: * @author Robert Grimm
040: * @version $Revision: 1.1 $
041: */
042: public class Checker extends Visitor {
043:
044: /** The analyzer utility. */
045: protected final Analyzer analyzer;
046:
047: /** The source file, one line per array entry. */
048: protected String[] source;
049:
050: /** Flag for whether we have seen an error. */
051: protected boolean error;
052:
053: /** Flag for whether we are currently processing a predicate. */
054: protected boolean predicate;
055:
056: /**
057: * Create a new checker.
058: *
059: * @param analyzer The analyzer utility for the new checker.
060: */
061: public Checker(Analyzer analyzer) {
062: this .analyzer = analyzer;
063: }
064:
065: /**
066: * Print the specified error message. Calling this method also sets
067: * the error flag.
068: *
069: * @param msg The error message.
070: * @param n The offending node.
071: */
072: protected void msg(String msg, Node n) {
073: String context = (null != analyzer.current()) ? analyzer
074: .current().nonTerminal.name : null;
075: System.err.println();
076: Utilities.msg(msg, n.location, context, source);
077: error = true;
078: }
079:
080: /**
081: * Analyze the specified grammar. This method returns a boolean flag
082: * indicating whether the grammar contains errors.
083: */
084: public Boolean visit(Grammar g) {
085: // (Re)initialize the per-grammar state.
086: LeftRecurser recurser = new LeftRecurser(analyzer);
087: g.accept(recurser);
088: Set recursive = recurser.recursive();
089:
090: source = (String[]) g.getProperty(Constants.SOURCE);
091: error = false;
092: predicate = false;
093:
094: // (Re)initialize the analyzer.
095: analyzer.register(this );
096: analyzer.init(g);
097:
098: // Check attributes (or, options).
099: if (null != g.attributes) {
100: int length = g.attributes.size();
101: for (int i = 0; i < length; i++) {
102: Attribute att = (Attribute) g.attributes.get(i);
103:
104: if ((!CodeGenerator.ATT_LOCATION.equals(att.name))
105: && (!CodeGenerator.ATT_CONSTANT_BINDING
106: .equals(att.name))
107: && (!CodeGenerator.ATT_DEBUG.equals(att.name))
108: && (!CodeGenerator.ATT_NO_MATCHING_ERRORS
109: .equals(att.name))) {
110: msg("unrecognized option " + att.name, att);
111:
112: } else {
113: for (int j = 0; j < i; j++) {
114: if (att.equals(g.attributes.get(j))) {
115: msg("duplicate option " + att.name, att);
116: break;
117: }
118: }
119: }
120: }
121: }
122:
123: // Check the top-level declarations.
124: int length = g.topLevel.size();
125: for (int i = 0; i < length; i++) {
126: NonTerminal nt = (NonTerminal) g.topLevel.get(i);
127:
128: if (!analyzer.isDefined(nt)) {
129: msg("undefined top-level nonterminal " + nt.name, nt);
130:
131: } else if (Type.isVoidT(analyzer.lookup(nt).type)) {
132: msg("void top-level nonterminal " + nt.name, nt);
133:
134: } else {
135: for (int j = 0; j < i; j++) {
136: if (nt.equals(g.topLevel.get(j))) {
137: msg("duplicate top-level nonterminal "
138: + nt.name, nt);
139: break;
140: }
141: }
142: }
143: }
144:
145: // Check the actual productions.
146: length = g.productions.size();
147: for (int i = 0; i < length; i++) {
148: Production p = (Production) g.productions.get(i);
149:
150: // Check the production's elements.
151: analyzer.process(p);
152:
153: // Check for left-recursive definitions.
154: if (recursive.contains(p.nonTerminal)) {
155: msg("left-recursive definition for nonterminal "
156: + p.nonTerminal.name, p);
157: }
158:
159: // Check for duplicate definitions.
160: for (int j = 0; j < i; j++) {
161: Production p2 = (Production) g.productions.get(j);
162:
163: if (p.nonTerminal.equals(p2.nonTerminal)) {
164: msg("duplicate definition for nonterminal "
165: + p.nonTerminal.name, p);
166: break;
167: }
168: }
169: }
170:
171: // Error check.
172: return (error) ? Boolean.TRUE : Boolean.FALSE;
173: }
174:
175: /** Analyze the specified production. */
176: public void visit(Production p) {
177: if (Type.isPrimitive(p.type)) {
178: msg("primitive type " + p.type + " for production "
179: + p.nonTerminal.name, p);
180: }
181: p.element.accept(this );
182: }
183:
184: /** Analyze the specified ordered choice. */
185: public void visit(OrderedChoice c) {
186: Iterator iter = c.options.iterator();
187: while (iter.hasNext()) {
188: ((Element) iter.next()).accept(this );
189: }
190: }
191:
192: /** Analyze the specified repetition. */
193: public void visit(Repetition r) {
194: if (analyzer.strip(r.element) instanceof Action) {
195: msg("repeated action", r);
196: }
197: r.element.accept(this );
198: }
199:
200: /** Analyze the specified option. */
201: public void visit(Option o) {
202: if (analyzer.strip(o.element) instanceof Action) {
203: msg("optional action", o);
204: }
205: o.element.accept(this );
206: }
207:
208: /** Analyze the specified sequence. */
209: public void visit(Sequence s) {
210: Iterator iter = s.elements.iterator();
211: while (iter.hasNext()) {
212: ((Element) iter.next()).accept(this );
213: }
214: }
215:
216: /** Analyze the specified predicate. */
217: public void visit(Predicate p) {
218: if (predicate) {
219: msg("syntactic predicate within syntactic predicate", p);
220: }
221:
222: boolean pred = predicate;
223: predicate = true;
224: p.element.accept(this );
225: predicate = pred;
226: }
227:
228: /** Analyze the specified semantic predicate. */
229: public void visit(SemanticPredicate p) {
230: if (!(p.element instanceof Action)) {
231: msg("malformed semantic predicate", p);
232: } else {
233: Action a = (Action) p.element;
234: if ((null == a.code) || (0 >= a.code.size())) {
235: msg("empty test for semantic predicate", p);
236: }
237: }
238:
239: p.element.accept(this );
240: }
241:
242: /** Analyze the specified binding. */
243: public void visit(Binding b) {
244: Element bound = analyzer.strip(b.element);
245:
246: if (bound instanceof Sequence) {
247: msg("binding for sequence", b);
248:
249: } else if (bound instanceof NonTerminal) {
250: NonTerminal nt = (NonTerminal) bound;
251: Production p = analyzer.lookup(nt);
252:
253: if ((null != p) && Type.isVoidT(p.type)) {
254: msg("binding for void nonterminal " + nt.name, b);
255: }
256:
257: } else if (bound instanceof Action) {
258: msg("binding for action", b);
259: }
260:
261: b.element.accept(this );
262: }
263:
264: /** Analyze the specified string match. */
265: public void visit(StringMatch m) {
266: Element matched = analyzer.strip(m.element);
267:
268: if (matched instanceof Sequence) {
269: msg("match for sequence", m);
270:
271: } else if (matched instanceof NonTerminal) {
272: NonTerminal nt = (NonTerminal) matched;
273: Production p = analyzer.lookup(nt);
274:
275: if ((null != p) && Type.isVoidT(p.type)) {
276: msg("match for void nonterminal " + nt.name, m);
277: }
278:
279: } else if (matched instanceof Terminal) {
280: msg("match for terminal", m);
281:
282: } else if (matched instanceof Action) {
283: msg("match for action", m);
284: }
285:
286: m.element.accept(this );
287: }
288:
289: /** Analyze the specified nonterminal. */
290: public void visit(NonTerminal nt) {
291: if (!analyzer.isDefined(nt)) {
292: msg("undefined nonterminal " + nt.name, nt);
293: }
294: }
295:
296: /** Analyze the specified terminal. */
297: public void visit(Terminal t) {
298: // Nothing to do.
299: }
300:
301: /** Analyze the specified string literal. */
302: public void visit(StringLiteral l) {
303: if (0 == l.text.length()) {
304: msg("empty string literal", l);
305: }
306: }
307:
308: /** Analyze the specified character class. */
309: public void visit(CharClass c) {
310: final int length = c.ranges.size();
311:
312: if (0 >= length) {
313: msg("empty character class", c);
314:
315: } else {
316: ArrayList list = new ArrayList(c.ranges);
317: Collections.sort(list);
318:
319: for (int i = 0; i < length - 1; i++) {
320: CharRange r1 = (CharRange) list.get(i);
321: CharRange r2 = (CharRange) list.get(i + 1);
322:
323: if (r1.last >= r2.first) {
324: boolean single1 = (r1.first == r1.last);
325: boolean single2 = (r2.first == r2.last);
326:
327: if (single1) {
328: if (single2) {
329: msg("duplicate character \'"
330: + Utilities.escape(r1.last,
331: Utilities.FULL_ESCAPES)
332: + "\' in character class", c);
333: } else {
334: msg("character \'"
335: + Utilities.escape(r1.last,
336: Utilities.FULL_ESCAPES)
337: + "\' already contained in range "
338: + Utilities.escape(r2.first,
339: Utilities.FULL_ESCAPES)
340: + "-"
341: + Utilities.escape(r2.last,
342: Utilities.FULL_ESCAPES), c);
343: }
344: } else {
345: if (single2) {
346: msg("character \'"
347: + Utilities.escape(r2.first,
348: Utilities.FULL_ESCAPES)
349: + "\' already contained in range "
350: + Utilities.escape(r1.first,
351: Utilities.FULL_ESCAPES)
352: + "-"
353: + Utilities.escape(r1.last,
354: Utilities.FULL_ESCAPES), c);
355: } else {
356: msg("ranges "
357: + Utilities.escape(r1.first,
358: Utilities.FULL_ESCAPES)
359: + "-"
360: + Utilities.escape(r1.last,
361: Utilities.FULL_ESCAPES)
362: + " and "
363: + Utilities.escape(r2.first,
364: Utilities.FULL_ESCAPES)
365: + "-"
366: + Utilities.escape(r2.last,
367: Utilities.FULL_ESCAPES)
368: + " overlap", c);
369: }
370: }
371: }
372: }
373: }
374: }
375:
376: /** Analyze the specified action. */
377: public void visit(Action a) {
378: // Nothing to do.
379: }
380:
381: /** Analyze the specified internal element. */
382: public void visit(InternalElement e) {
383: msg("internal element", (Element) e);
384: }
385:
386: }
|