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.tool;
029:
030: import antlr.CommonToken;
031: import org.antlr.analysis.NFAState;
032: import org.antlr.codegen.CodeGenerator;
033:
034: import java.util.*;
035:
036: /** Combine the info associated with a rule */
037: public class Rule {
038: public String name;
039: public int index;
040: public String modifier;
041: public NFAState startState;
042: public NFAState stopState;
043:
044: /** This rule's options */
045: protected Map options;
046:
047: public static final Set legalOptions = new HashSet() {
048: {
049: add("k");
050: add("greedy");
051: add("memoize");
052: add("backtrack");
053: }
054: };
055:
056: /** The AST representing the whole rule */
057: public GrammarAST tree;
058:
059: /** To which grammar does this belong? */
060: public Grammar grammar;
061:
062: /** For convenience, track the argument def AST action node if any */
063: public GrammarAST argActionAST;
064:
065: public GrammarAST EORNode;
066:
067: /** The return values of a rule and predefined rule attributes */
068: public AttributeScope returnScope;
069:
070: public AttributeScope parameterScope;
071:
072: /** the attributes defined with "scope {...}" inside a rule */
073: public AttributeScope ruleScope;
074:
075: /** A list of scope names (String) used by this rule */
076: public List useScopes;
077:
078: /** A list of all LabelElementPair attached to tokens like id=ID */
079: public LinkedHashMap tokenLabels;
080:
081: /** A list of all LabelElementPair attached to single char literals like x='a' */
082: public LinkedHashMap charLabels;
083:
084: /** A list of all LabelElementPair attached to rule references like f=field */
085: public LinkedHashMap ruleLabels;
086:
087: /** A list of all Token list LabelElementPair like ids+=ID */
088: public LinkedHashMap tokenListLabels;
089:
090: /** A list of all rule ref list LabelElementPair like ids+=expr */
091: public LinkedHashMap ruleListLabels;
092:
093: /** All labels go in here (plus being split per the above lists) to
094: * catch dup label and label type mismatches.
095: */
096: protected Map<String, Grammar.LabelElementPair> labelNameSpace = new HashMap<String, Grammar.LabelElementPair>();
097:
098: /** Map a name to an action for this rule. Currently init is only
099: * one we use, but we can add more in future.
100: * The code generator will use this to fill holes in the rule template.
101: * I track the AST node for the action in case I need the line number
102: * for errors. A better name is probably namedActions, but I don't
103: * want everyone to have to change their code gen templates now.
104: */
105: protected Map<String, GrammarAST> actions = new HashMap<String, GrammarAST>();
106:
107: /** Track all executable actions other than named actions like @init.
108: * Also tracks exception handlers, predicates, and rewrite rewrites.
109: * We need to examine these actions before code generation so
110: * that we can detect refs to $rule.attr etc...
111: */
112: protected List<GrammarAST> inlineActions = new ArrayList<GrammarAST>();
113:
114: public int numberOfAlts;
115:
116: /** Each alt has a Map<tokenRefName,List<tokenRefAST>>; range 1..numberOfAlts.
117: * So, if there are 3 ID refs in a rule's alt number 2, you'll have
118: * altToTokenRef[2].get("ID").size()==3. This is used to see if $ID is ok.
119: * There must be only one ID reference in the alt for $ID to be ok in
120: * an action--must be unique.
121: *
122: * This also tracks '+' and "int" literal token references
123: * (if not in LEXER).
124: *
125: * Rewrite rules force tracking of all tokens.
126: */
127: protected Map<String, List<GrammarAST>>[] altToTokenRefMap;
128:
129: /** Each alt has a Map<ruleRefName,List<ruleRefAST>>; range 1..numberOfAlts
130: * So, if there are 3 expr refs in a rule's alt number 2, you'll have
131: * altToRuleRef[2].get("expr").size()==3. This is used to see if $expr is ok.
132: * There must be only one expr reference in the alt for $expr to be ok in
133: * an action--must be unique.
134: *
135: * Rewrite rules force tracking of all rule result ASTs. 1..n
136: */
137: protected Map<String, List<GrammarAST>>[] altToRuleRefMap;
138:
139: /** Track which alts have rewrite rules associated with them. 1..n */
140: protected boolean[] altsWithRewrites;
141:
142: /** Do not generate start, stop etc... in a return value struct unless
143: * somebody references $r.start somewhere.
144: */
145: public boolean referencedPredefinedRuleAttributes = false;
146:
147: public boolean isSynPred = false;
148:
149: public Rule(Grammar grammar, String ruleName, int ruleIndex,
150: int numberOfAlts) {
151: this .name = ruleName;
152: this .index = ruleIndex;
153: this .numberOfAlts = numberOfAlts;
154: this .grammar = grammar;
155: altToTokenRefMap = new Map[numberOfAlts + 1];
156: altToRuleRefMap = new Map[numberOfAlts + 1];
157: altsWithRewrites = new boolean[numberOfAlts + 1];
158: for (int alt = 1; alt <= numberOfAlts; alt++) {
159: altToTokenRefMap[alt] = new HashMap<String, List<GrammarAST>>();
160: altToRuleRefMap[alt] = new HashMap<String, List<GrammarAST>>();
161: }
162: }
163:
164: public void defineLabel(antlr.Token label, GrammarAST elementRef,
165: int type) {
166: Grammar.LabelElementPair pair = grammar.new LabelElementPair(
167: label, elementRef);
168: pair.type = type;
169: labelNameSpace.put(label.getText(), pair);
170: switch (type) {
171: case Grammar.TOKEN_LABEL:
172: if (tokenLabels == null) {
173: tokenLabels = new LinkedHashMap();
174: }
175: tokenLabels.put(label.getText(), pair);
176: break;
177: case Grammar.RULE_LABEL:
178: if (ruleLabels == null) {
179: ruleLabels = new LinkedHashMap();
180: }
181: ruleLabels.put(label.getText(), pair);
182: break;
183: case Grammar.TOKEN_LIST_LABEL:
184: if (tokenListLabels == null) {
185: tokenListLabels = new LinkedHashMap();
186: }
187: tokenListLabels.put(label.getText(), pair);
188: break;
189: case Grammar.RULE_LIST_LABEL:
190: if (ruleListLabels == null) {
191: ruleListLabels = new LinkedHashMap();
192: }
193: ruleListLabels.put(label.getText(), pair);
194: break;
195: case Grammar.CHAR_LABEL:
196: if (charLabels == null) {
197: charLabels = new LinkedHashMap();
198: }
199: charLabels.put(label.getText(), pair);
200: break;
201: }
202: }
203:
204: public Grammar.LabelElementPair getLabel(String name) {
205: return (Grammar.LabelElementPair) labelNameSpace.get(name);
206: }
207:
208: public Grammar.LabelElementPair getTokenLabel(String name) {
209: Grammar.LabelElementPair pair = null;
210: if (tokenLabels != null) {
211: return (Grammar.LabelElementPair) tokenLabels.get(name);
212: }
213: return pair;
214: }
215:
216: public Map getRuleLabels() {
217: return ruleLabels;
218: }
219:
220: public Map getRuleListLabels() {
221: return ruleListLabels;
222: }
223:
224: public Grammar.LabelElementPair getRuleLabel(String name) {
225: Grammar.LabelElementPair pair = null;
226: if (ruleLabels != null) {
227: return (Grammar.LabelElementPair) ruleLabels.get(name);
228: }
229: return pair;
230: }
231:
232: public Grammar.LabelElementPair getTokenListLabel(String name) {
233: Grammar.LabelElementPair pair = null;
234: if (tokenListLabels != null) {
235: return (Grammar.LabelElementPair) tokenListLabels.get(name);
236: }
237: return pair;
238: }
239:
240: public Grammar.LabelElementPair getRuleListLabel(String name) {
241: Grammar.LabelElementPair pair = null;
242: if (ruleListLabels != null) {
243: return (Grammar.LabelElementPair) ruleListLabels.get(name);
244: }
245: return pair;
246: }
247:
248: /** Track a token ID or literal like '+' and "void" as having been referenced
249: * somewhere within the alts (not rewrite sections) of a rule.
250: *
251: * This differs from Grammar.altReferencesTokenID(), which tracks all
252: * token IDs to check for token IDs without corresponding lexer rules.
253: */
254: public void trackTokenReferenceInAlt(GrammarAST refAST,
255: int outerAltNum) {
256: List refs = (List) altToTokenRefMap[outerAltNum].get(refAST
257: .getText());
258: if (refs == null) {
259: refs = new ArrayList();
260: altToTokenRefMap[outerAltNum].put(refAST.getText(), refs);
261: }
262: refs.add(refAST);
263: }
264:
265: public List getTokenRefsInAlt(String ref, int outerAltNum) {
266: if (altToTokenRefMap[outerAltNum] != null) {
267: List tokenRefASTs = (List) altToTokenRefMap[outerAltNum]
268: .get(ref);
269: return tokenRefASTs;
270: }
271: return null;
272: }
273:
274: public void trackRuleReferenceInAlt(GrammarAST refAST,
275: int outerAltNum) {
276: List refs = (List) altToRuleRefMap[outerAltNum].get(refAST
277: .getText());
278: if (refs == null) {
279: refs = new ArrayList();
280: altToRuleRefMap[outerAltNum].put(refAST.getText(), refs);
281: }
282: refs.add(refAST);
283: }
284:
285: public List getRuleRefsInAlt(String ref, int outerAltNum) {
286: if (altToRuleRefMap[outerAltNum] != null) {
287: List ruleRefASTs = (List) altToRuleRefMap[outerAltNum]
288: .get(ref);
289: return ruleRefASTs;
290: }
291: return null;
292: }
293:
294: public Set getTokenRefsInAlt(int altNum) {
295: return altToTokenRefMap[altNum].keySet();
296: }
297:
298: /** For use with rewrite rules, we must track all tokens matched on the
299: * left-hand-side; so we need Lists. This is a unique list of all
300: * token types for which the rule needs a list of tokens. This
301: * is called from the rule template not directly by the code generator.
302: */
303: public Set getAllTokenRefsInAltsWithRewrites() {
304: String output = (String) grammar.getOption("output");
305: Set tokens = new HashSet();
306: if (output == null || !output.equals("AST")) {
307: // return nothing if not generating trees; i.e., don't do for templates
308: return tokens;
309: }
310: for (int i = 1; i <= numberOfAlts; i++) {
311: if (altsWithRewrites[i]) {
312: Map m = altToTokenRefMap[i];
313: Set s = m.keySet();
314: for (Iterator it = s.iterator(); it.hasNext();) {
315: // convert token name like ID to ID, "void" to 31
316: String tokenName = (String) it.next();
317: int ttype = grammar.getTokenType(tokenName);
318: String label = grammar.generator
319: .getTokenTypeAsTargetLabel(ttype);
320: tokens.add(label);
321: }
322: }
323: }
324: return tokens;
325: }
326:
327: public Set getRuleRefsInAlt(int outerAltNum) {
328: return altToRuleRefMap[outerAltNum].keySet();
329: }
330:
331: /** For use with rewrite rules, we must track all rule AST results on the
332: * left-hand-side; so we need Lists. This is a unique list of all
333: * rule results for which the rule needs a list of results.
334: */
335: public Set getAllRuleRefsInAltsWithRewrites() {
336: Set rules = new HashSet();
337: for (int i = 1; i <= numberOfAlts; i++) {
338: if (altsWithRewrites[i]) {
339: Map m = altToRuleRefMap[i];
340: rules.addAll(m.keySet());
341: }
342: }
343: return rules;
344: }
345:
346: public List<GrammarAST> getInlineActions() {
347: return inlineActions;
348: }
349:
350: public boolean hasRewrite(int i) {
351: return altsWithRewrites[i];
352: }
353:
354: /** Track which rules have rewrite rules. Pass in the ALT node
355: * for the alt so we can check for problems when output=template,
356: * rewrite=true, and grammar type is tree parser.
357: */
358: public void trackAltsWithRewrites(GrammarAST altAST, int outerAltNum) {
359: if (grammar.type == Grammar.TREE_PARSER
360: && grammar.buildTemplate()
361: && grammar.getOption("rewrite") != null
362: && grammar.getOption("rewrite").equals("true")) {
363: GrammarAST firstElementAST = (GrammarAST) altAST
364: .getFirstChild();
365: grammar.sanity.ensureAltIsSimpleNodeOrTree(altAST,
366: firstElementAST, outerAltNum);
367: }
368: altsWithRewrites[outerAltNum] = true;
369: }
370:
371: /** Return the scope containing name */
372: public AttributeScope getAttributeScope(String name) {
373: AttributeScope scope = getLocalAttributeScope(name);
374: if (scope != null) {
375: return scope;
376: }
377: if (ruleScope != null && ruleScope.getAttribute(name) != null) {
378: scope = ruleScope;
379: }
380: return scope;
381: }
382:
383: /** Get the arg, return value, or predefined property for this rule */
384: public AttributeScope getLocalAttributeScope(String name) {
385: AttributeScope scope = null;
386: if (returnScope != null
387: && returnScope.getAttribute(name) != null) {
388: scope = returnScope;
389: } else if (parameterScope != null
390: && parameterScope.getAttribute(name) != null) {
391: scope = parameterScope;
392: } else {
393: AttributeScope rulePropertiesScope = RuleLabelScope.grammarTypeToRulePropertiesScope[grammar.type];
394: if (rulePropertiesScope.getAttribute(name) != null) {
395: scope = rulePropertiesScope;
396: }
397: }
398: return scope;
399: }
400:
401: /** For references to tokens rather than by label such as $ID, we
402: * need to get the existing label for the ID ref or create a new
403: * one.
404: */
405: public String getElementLabel(String refdSymbol, int outerAltNum,
406: CodeGenerator generator) {
407: GrammarAST uniqueRefAST;
408: if (grammar.type != Grammar.LEXER
409: && Character.isUpperCase(refdSymbol.charAt(0))) {
410: // symbol is a token
411: List tokenRefs = getTokenRefsInAlt(refdSymbol, outerAltNum);
412: uniqueRefAST = (GrammarAST) tokenRefs.get(0);
413: } else {
414: // symbol is a rule
415: List ruleRefs = getRuleRefsInAlt(refdSymbol, outerAltNum);
416: uniqueRefAST = (GrammarAST) ruleRefs.get(0);
417: }
418: if (uniqueRefAST.code == null) {
419: // no code? must not have gen'd yet; forward ref
420: return null;
421: }
422: String labelName = null;
423: String existingLabelName = (String) uniqueRefAST.code
424: .getAttribute("label");
425: // reuse any label or list label if it exists
426: if (existingLabelName != null) {
427: labelName = existingLabelName;
428: } else {
429: // else create new label
430: labelName = generator.createUniqueLabel(refdSymbol);
431: CommonToken label = new CommonToken(ANTLRParser.ID,
432: labelName);
433: if (grammar.type != Grammar.LEXER
434: && Character.isUpperCase(refdSymbol.charAt(0))) {
435: grammar.defineTokenRefLabel(name, label, uniqueRefAST);
436: } else {
437: grammar.defineRuleRefLabel(name, label, uniqueRefAST);
438: }
439: uniqueRefAST.code.setAttribute("label", labelName);
440: }
441: return labelName;
442: }
443:
444: /** If a rule has no user-defined return values and nobody references
445: * it's start/stop (predefined attributes), then there is no need to
446: * define a struct; otherwise for now we assume a struct. A rule also
447: * has multiple return values if you are building trees or templates.
448: */
449: public boolean getHasMultipleReturnValues() {
450: return referencedPredefinedRuleAttributes
451: || grammar.buildAST()
452: || grammar.buildTemplate()
453: || (returnScope != null && returnScope.attributes
454: .size() > 1);
455: }
456:
457: public boolean getHasSingleReturnValue() {
458: return !(referencedPredefinedRuleAttributes
459: || grammar.buildAST() || grammar.buildTemplate())
460: && (returnScope != null && returnScope.attributes
461: .size() == 1);
462: }
463:
464: public boolean getHasReturnValue() {
465: return referencedPredefinedRuleAttributes
466: || grammar.buildAST()
467: || grammar.buildTemplate()
468: || (returnScope != null && returnScope.attributes
469: .size() > 0);
470: }
471:
472: public String getSingleValueReturnType() {
473: if (returnScope != null && returnScope.attributes.size() == 1) {
474: Collection retvalAttrs = returnScope.attributes.values();
475: Object[] javaSucks = retvalAttrs.toArray();
476: return ((Attribute) javaSucks[0]).type;
477: }
478: return null;
479: }
480:
481: public String getSingleValueReturnName() {
482: if (returnScope != null && returnScope.attributes.size() == 1) {
483: Collection retvalAttrs = returnScope.attributes.values();
484: Object[] javaSucks = retvalAttrs.toArray();
485: return ((Attribute) javaSucks[0]).name;
486: }
487: return null;
488: }
489:
490: /** Given @scope::name {action} define it for this grammar. Later,
491: * the code generator will ask for the actions table.
492: */
493: public void defineNamedAction(GrammarAST ampersandAST,
494: GrammarAST nameAST, GrammarAST actionAST) {
495: //System.out.println("rule @"+nameAST.getText()+"{"+actionAST.getText()+"}");
496: String actionName = nameAST.getText();
497: GrammarAST a = (GrammarAST) actions.get(actionName);
498: if (a != null) {
499: ErrorManager.grammarError(
500: ErrorManager.MSG_ACTION_REDEFINITION, grammar,
501: nameAST.getToken(), nameAST.getText());
502: } else {
503: actions.put(actionName, actionAST);
504: }
505: }
506:
507: public void trackInlineAction(GrammarAST actionAST) {
508: inlineActions.add(actionAST);
509: }
510:
511: public Map<String, GrammarAST> getActions() {
512: return actions;
513: }
514:
515: public void setActions(Map<String, GrammarAST> actions) {
516: this .actions = actions;
517: }
518:
519: /** Save the option key/value pair and process it; return the key
520: * or null if invalid option.
521: */
522: public String setOption(String key, Object value,
523: antlr.Token optionsStartToken) {
524: if (!legalOptions.contains(key)) {
525: ErrorManager.grammarError(ErrorManager.MSG_ILLEGAL_OPTION,
526: grammar, optionsStartToken, key);
527: return null;
528: }
529: if (options == null) {
530: options = new HashMap();
531: }
532: if (key.equals("k")) {
533: grammar.numberOfManualLookaheadOptions++;
534: }
535: options.put(key, value);
536: return key;
537: }
538:
539: public void setOptions(Map options, antlr.Token optionsStartToken) {
540: if (options == null) {
541: this .options = null;
542: return;
543: }
544: Set keys = options.keySet();
545: for (Iterator it = keys.iterator(); it.hasNext();) {
546: String optionName = (String) it.next();
547: Object optionValue = options.get(optionName);
548: String stored = setOption(optionName, optionValue,
549: optionsStartToken);
550: if (stored == null) {
551: it.remove();
552: }
553: }
554: }
555:
556: public String toString() { // used for testing
557: if (modifier != null) {
558: return modifier + " " + name;
559: }
560: return name;
561: }
562: }
|