001: /*
002: [The "BSD licence"]
003: Copyright (c) 2005-2006 Terence Parr
004: All rights reserved.
005:
006: Redistribution and use in source and binary forms, with or without
007: modification, are permitted provided that the following conditions
008: are met:
009: 1. Redistributions of source code must retain the above copyright
010: notice, this list of conditions and the following disclaimer.
011: 2. Redistributions in binary form must reproduce the above copyright
012: notice, this list of conditions and the following disclaimer in the
013: documentation and/or other materials provided with the distribution.
014: 3. The name of the author may not be used to endorse or promote products
015: derived from this software without specific prior written permission.
016:
017: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
018: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
019: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
020: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
021: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
022: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
023: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
024: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
025: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
026: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
027: */
028: package org.antlr.analysis;
029:
030: import org.antlr.stringtemplate.StringTemplate;
031: import org.antlr.stringtemplate.StringTemplateGroup;
032: import org.antlr.codegen.CodeGenerator;
033: import org.antlr.tool.ANTLRParser;
034: import org.antlr.tool.GrammarAST;
035: import org.antlr.tool.Grammar;
036: import java.util.Set;
037: import java.util.HashSet;
038: import java.util.Iterator;
039:
040: /** A binary tree structure used to record the semantic context in which
041: * an NFA configuration is valid. It's either a single predicate or
042: * a tree representing an operation tree such as: p1&&p2 or p1||p2.
043: *
044: * For NFA o-p1->o-p2->o, create tree AND(p1,p2).
045: * For NFA (1)-p1->(2)
046: * | ^
047: * | |
048: * (3)-p2----
049: * we will have to combine p1 and p2 into DFA state as we will be
050: * adding NFA configurations for state 2 with two predicates p1,p2.
051: * So, set context for combined NFA config for state 2: OR(p1,p2).
052: *
053: * I have scoped the AND, NOT, OR, and Predicate subclasses of
054: * SemanticContext within the scope of this outer class.
055: *
056: * July 7, 2006: TJP altered OR to be set of operands. the Binary tree
057: * made it really hard to reduce complicated || sequences to their minimum.
058: * Got huge repeated || conditions.
059: */
060: public abstract class SemanticContext {
061: /** Create a default value for the semantic context shared among all
062: * NFAConfigurations that do not have an actual semantic context.
063: * This prevents lots of if!=null type checks all over; it represents
064: * just an empty set of predicates.
065: */
066: public static final SemanticContext EMPTY_SEMANTIC_CONTEXT = new Predicate();
067:
068: /** Given a semantic context expression tree, return a tree with all
069: * nongated predicates set to true and then reduced. So p&&(q||r) would
070: * return p&&r if q is nongated but p and r are gated.
071: */
072: public abstract SemanticContext getGatedPredicateContext();
073:
074: /** Generate an expression that will evaluate the semantic context,
075: * given a set of output templates.
076: */
077: public abstract StringTemplate genExpr(CodeGenerator generator,
078: StringTemplateGroup templates, DFA dfa);
079:
080: public abstract boolean isSyntacticPredicate();
081:
082: /** Notify the indicated grammar of any syn preds used within this context */
083: public void trackUseOfSyntacticPredicates(Grammar g) {
084: }
085:
086: public static class Predicate extends SemanticContext {
087: /** The AST node in tree created from the grammar holding the predicate */
088: protected GrammarAST predicate;
089:
090: /** Is this a {...}?=> gating predicate or a normal disambiguating {..}?
091: * If any predicate in expression is gated, then expression is considered
092: * gated.
093: *
094: * The simple Predicate object's predicate AST's type is used to set
095: * gated to true if type==GATED_SEMPRED.
096: */
097: protected boolean gated = false;
098:
099: /** syntactic predicates are converted to semantic predicates
100: * but synpreds are generated slightly differently.
101: */
102: protected boolean synpred = false;
103:
104: public static final int INVALID_PRED_VALUE = -1;
105: public static final int FALSE_PRED = 0;
106: public static final int TRUE_PRED = 1;
107:
108: /** sometimes predicates are known to be true or false; we need
109: * a way to represent this without resorting to a target language
110: * value like true or TRUE.
111: */
112: protected int constantValue = INVALID_PRED_VALUE;
113:
114: public Predicate() {
115: predicate = new GrammarAST();
116: this .gated = false;
117: }
118:
119: public Predicate(GrammarAST predicate) {
120: this .predicate = predicate;
121: this .gated = predicate.getType() == ANTLRParser.GATED_SEMPRED
122: || predicate.getType() == ANTLRParser.SYN_SEMPRED;
123: this .synpred = predicate.getType() == ANTLRParser.SYN_SEMPRED
124: || predicate.getType() == ANTLRParser.BACKTRACK_SEMPRED;
125: }
126:
127: public Predicate(Predicate p) {
128: this .predicate = p.predicate;
129: this .gated = p.gated;
130: this .synpred = p.synpred;
131: this .constantValue = p.constantValue;
132: }
133:
134: /** Two predicates are the same if they are literally the same
135: * text rather than same node in the grammar's AST.
136: * Or, if they have the same constant value, return equal.
137: * As of July 2006 I'm not sure these are needed.
138: */
139: public boolean equals(Object o) {
140: if (!(o instanceof Predicate)) {
141: return false;
142: }
143: return predicate.getText().equals(
144: ((Predicate) o).predicate.getText());
145: }
146:
147: public int hashCode() {
148: if (predicate == null) {
149: return 0;
150: }
151: return predicate.getText().hashCode();
152: }
153:
154: public StringTemplate genExpr(CodeGenerator generator,
155: StringTemplateGroup templates, DFA dfa) {
156: StringTemplate eST = null;
157: if (templates != null) {
158: if (synpred) {
159: eST = templates.getInstanceOf("evalSynPredicate");
160: } else {
161: eST = templates.getInstanceOf("evalPredicate");
162: generator.grammar.decisionsWhoseDFAsUsesSemPreds
163: .add(dfa);
164: }
165: String predEnclosingRuleName = predicate
166: .getEnclosingRule();
167: /*
168: String decisionEnclosingRuleName =
169: dfa.getNFADecisionStartState().getEnclosingRule();
170: // if these rulenames are diff, then pred was hoisted out of rule
171: // Currently I don't warn you about this as it could be annoying.
172: // I do the translation anyway.
173: */
174: //eST.setAttribute("pred", this.toString());
175: if (generator != null) {
176: eST.setAttribute("pred", generator.translateAction(
177: predEnclosingRuleName, predicate));
178: }
179: } else {
180: eST = new StringTemplate("$pred$");
181: eST.setAttribute("pred", this .toString());
182: return eST;
183: }
184: if (generator != null) {
185: String description = generator.target
186: .getTargetStringLiteralFromString(this
187: .toString());
188: eST.setAttribute("description", description);
189: }
190: return eST;
191: }
192:
193: public SemanticContext getGatedPredicateContext() {
194: if (gated) {
195: return this ;
196: }
197: return null;
198: }
199:
200: public boolean isSyntacticPredicate() {
201: return predicate != null
202: && (predicate.getType() == ANTLRParser.SYN_SEMPRED || predicate
203: .getType() == ANTLRParser.BACKTRACK_SEMPRED);
204: }
205:
206: public void trackUseOfSyntacticPredicates(Grammar g) {
207: if (synpred) {
208: g.synPredNamesUsedInDFA.add(predicate.getText());
209: }
210: }
211:
212: public String toString() {
213: if (predicate == null) {
214: return "<nopred>";
215: }
216: return predicate.getText();
217: }
218: }
219:
220: public static class TruePredicate extends Predicate {
221: public TruePredicate() {
222: super ();
223: this .constantValue = TRUE_PRED;
224: }
225:
226: public StringTemplate genExpr(CodeGenerator generator,
227: StringTemplateGroup templates, DFA dfa) {
228: if (templates != null) {
229: return templates.getInstanceOf("true");
230: }
231: return new StringTemplate("true");
232: }
233:
234: public String toString() {
235: return "true"; // not used for code gen, just DOT and print outs
236: }
237: }
238:
239: /*
240: public static class FalsePredicate extends Predicate {
241: public FalsePredicate() {
242: super();
243: this.constantValue = FALSE_PRED;
244: }
245: public StringTemplate genExpr(CodeGenerator generator,
246: StringTemplateGroup templates,
247: DFA dfa)
248: {
249: if ( templates!=null ) {
250: return templates.getInstanceOf("false");
251: }
252: return new StringTemplate("false");
253: }
254: public String toString() {
255: return "false"; // not used for code gen, just DOT and print outs
256: }
257: }
258: */
259:
260: public static class AND extends SemanticContext {
261: protected SemanticContext left, right;
262:
263: public AND(SemanticContext a, SemanticContext b) {
264: this .left = a;
265: this .right = b;
266: }
267:
268: public StringTemplate genExpr(CodeGenerator generator,
269: StringTemplateGroup templates, DFA dfa) {
270: StringTemplate eST = null;
271: if (templates != null) {
272: eST = templates.getInstanceOf("andPredicates");
273: } else {
274: eST = new StringTemplate("($left$&&$right$)");
275: }
276: eST.setAttribute("left", left.genExpr(generator, templates,
277: dfa));
278: eST.setAttribute("right", right.genExpr(generator,
279: templates, dfa));
280: return eST;
281: }
282:
283: public SemanticContext getGatedPredicateContext() {
284: SemanticContext gatedLeft = left.getGatedPredicateContext();
285: SemanticContext gatedRight = right
286: .getGatedPredicateContext();
287: if (gatedLeft == null) {
288: return gatedRight;
289: }
290: if (gatedRight == null) {
291: return gatedLeft;
292: }
293: return new AND(gatedLeft, gatedRight);
294: }
295:
296: public boolean isSyntacticPredicate() {
297: return left.isSyntacticPredicate()
298: || right.isSyntacticPredicate();
299: }
300:
301: public void trackUseOfSyntacticPredicates(Grammar g) {
302: left.trackUseOfSyntacticPredicates(g);
303: right.trackUseOfSyntacticPredicates(g);
304: }
305:
306: public String toString() {
307: return "(" + left + "&&" + right + ")";
308: }
309: }
310:
311: public static class OR extends SemanticContext {
312: protected Set operands;
313:
314: public OR(SemanticContext a, SemanticContext b) {
315: operands = new HashSet();
316: if (a instanceof OR) {
317: operands.addAll(((OR) a).operands);
318: } else if (a != null) {
319: operands.add(a);
320: }
321: if (b instanceof OR) {
322: operands.addAll(((OR) b).operands);
323: } else if (b != null) {
324: operands.add(b);
325: }
326: }
327:
328: public StringTemplate genExpr(CodeGenerator generator,
329: StringTemplateGroup templates, DFA dfa) {
330: StringTemplate eST = null;
331: if (templates != null) {
332: eST = templates.getInstanceOf("orPredicates");
333: } else {
334: eST = new StringTemplate(
335: "($first(operands)$$rest(operands):{o | ||$o$}$)");
336: }
337: for (Iterator it = operands.iterator(); it.hasNext();) {
338: SemanticContext semctx = (SemanticContext) it.next();
339: eST.setAttribute("operands", semctx.genExpr(generator,
340: templates, dfa));
341: }
342: return eST;
343: }
344:
345: public SemanticContext getGatedPredicateContext() {
346: SemanticContext result = null;
347: for (Iterator it = operands.iterator(); it.hasNext();) {
348: SemanticContext semctx = (SemanticContext) it.next();
349: SemanticContext gatedPred = semctx
350: .getGatedPredicateContext();
351: if (gatedPred != null) {
352: result = or(result, gatedPred);
353: // result = new OR(result, gatedPred);
354: }
355: }
356: return result;
357: }
358:
359: public boolean isSyntacticPredicate() {
360: for (Iterator it = operands.iterator(); it.hasNext();) {
361: SemanticContext semctx = (SemanticContext) it.next();
362: if (semctx.isSyntacticPredicate()) {
363: return true;
364: }
365: }
366: return false;
367: }
368:
369: public void trackUseOfSyntacticPredicates(Grammar g) {
370: for (Iterator it = operands.iterator(); it.hasNext();) {
371: SemanticContext semctx = (SemanticContext) it.next();
372: semctx.trackUseOfSyntacticPredicates(g);
373: }
374: }
375:
376: public String toString() {
377: StringBuffer buf = new StringBuffer();
378: buf.append("(");
379: int i = 0;
380: for (Iterator it = operands.iterator(); it.hasNext();) {
381: SemanticContext semctx = (SemanticContext) it.next();
382: if (i > 0) {
383: buf.append("||");
384: }
385: buf.append(semctx.toString());
386: i++;
387: }
388: buf.append(")");
389: return buf.toString();
390: }
391: }
392:
393: public static class NOT extends SemanticContext {
394: protected SemanticContext ctx;
395:
396: public NOT(SemanticContext ctx) {
397: this .ctx = ctx;
398: }
399:
400: public StringTemplate genExpr(CodeGenerator generator,
401: StringTemplateGroup templates, DFA dfa) {
402: StringTemplate eST = null;
403: if (templates != null) {
404: eST = templates.getInstanceOf("notPredicate");
405: } else {
406: eST = new StringTemplate("?!($pred$)");
407: }
408: eST.setAttribute("pred", ctx.genExpr(generator, templates,
409: dfa));
410: return eST;
411: }
412:
413: public SemanticContext getGatedPredicateContext() {
414: SemanticContext p = ctx.getGatedPredicateContext();
415: if (p == null) {
416: return null;
417: }
418: return new NOT(p);
419: }
420:
421: public boolean isSyntacticPredicate() {
422: return ctx.isSyntacticPredicate();
423: }
424:
425: public void trackUseOfSyntacticPredicates(Grammar g) {
426: ctx.trackUseOfSyntacticPredicates(g);
427: }
428:
429: public boolean equals(Object object) {
430: if (!(object instanceof NOT)) {
431: return false;
432: }
433: return this .ctx.equals(((NOT) object).ctx);
434: }
435:
436: public String toString() {
437: return "!(" + ctx + ")";
438: }
439: }
440:
441: public static SemanticContext and(SemanticContext a,
442: SemanticContext b) {
443: if (a == EMPTY_SEMANTIC_CONTEXT || a == null) {
444: return b;
445: }
446: if (b == EMPTY_SEMANTIC_CONTEXT || b == null) {
447: return a;
448: }
449: if (a.equals(b)) {
450: return a; // if same, just return left one
451: }
452: return new AND(a, b);
453: }
454:
455: public static SemanticContext or(SemanticContext a,
456: SemanticContext b) {
457: if (a == EMPTY_SEMANTIC_CONTEXT || a == null) {
458: return b;
459: }
460: if (b == EMPTY_SEMANTIC_CONTEXT || b == null) {
461: return a;
462: }
463: if (a instanceof TruePredicate) {
464: return a;
465: }
466: if (b instanceof TruePredicate) {
467: return b;
468: }
469: if (a instanceof NOT && b instanceof Predicate) {
470: NOT n = (NOT) a;
471: // check for !p||p
472: if (n.ctx.equals(b)) {
473: return new TruePredicate();
474: }
475: } else if (b instanceof NOT && a instanceof Predicate) {
476: NOT n = (NOT) b;
477: // check for p||!p
478: if (n.ctx.equals(a)) {
479: return new TruePredicate();
480: }
481: } else if (a.equals(b)) {
482: return a;
483: }
484: return new OR(a, b);
485: }
486:
487: public static SemanticContext not(SemanticContext a) {
488: return new NOT(a);
489: }
490:
491: }
|