• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 package org.antlr.tool;
2 
3 import org.antlr.codegen.CodeGenerator;
4 import org.antlr.grammar.v3.*;
5 import org.antlr.runtime.Token;
6 import org.antlr.runtime.tree.CommonTreeNodeStream;
7 import org.antlr.runtime.tree.TreeNodeStream;
8 import org.stringtemplate.v4.*;
9 
10 import java.util.*;
11 
12 /** */
13 public class LeftRecursiveRuleAnalyzer extends LeftRecursiveRuleWalker {
14 	public static enum ASSOC { left, right };
15 
16 	public Grammar g;
17 	public CodeGenerator generator;
18 	public String ruleName;
19 	Map<Integer, Integer> tokenToPrec = new HashMap<Integer, Integer>();
20 	public LinkedHashMap<Integer, String> binaryAlts = new LinkedHashMap<Integer, String>();
21 	public LinkedHashMap<Integer, String> ternaryAlts = new LinkedHashMap<Integer, String>();
22 	public LinkedHashMap<Integer, String> suffixAlts = new LinkedHashMap<Integer, String>();
23 	public List<String> prefixAlts = new ArrayList<String>();
24 	public List<String> otherAlts = new ArrayList<String>();
25 
26 	public GrammarAST retvals;
27 
28 	public STGroup recRuleTemplates;
29 	public String language;
30 
31 	public Map<Integer, ASSOC> altAssociativity = new HashMap<Integer, ASSOC>();
32 
LeftRecursiveRuleAnalyzer(TreeNodeStream input, Grammar g, String ruleName)33 	public LeftRecursiveRuleAnalyzer(TreeNodeStream input, Grammar g, String ruleName) {
34 		super(input);
35 		this.g = g;
36 		this.ruleName = ruleName;
37 		language = (String)g.getOption("language");
38 		generator = new CodeGenerator(g.tool, g, language);
39 		generator.loadTemplates(language);
40 		loadPrecRuleTemplates();
41 	}
42 
loadPrecRuleTemplates()43 	public void loadPrecRuleTemplates() {
44 		recRuleTemplates =
45 			new ToolSTGroupFile(CodeGenerator.classpathTemplateRootDirectoryName+
46 							"/LeftRecursiveRules.stg");
47 		if ( !recRuleTemplates.isDefined("recRuleName") ) {
48 			ErrorManager.error(ErrorManager.MSG_MISSING_CODE_GEN_TEMPLATES,
49 							   "PrecRules");
50 			return;
51 		}
52 	}
53 
54 	@Override
setReturnValues(GrammarAST t)55 	public void setReturnValues(GrammarAST t) {
56 		System.out.println(t);
57 		retvals = t;
58 	}
59 
60 	@Override
setTokenPrec(GrammarAST t, int alt)61 	public void setTokenPrec(GrammarAST t, int alt) {
62 		int ttype = g.getTokenType(t.getText());
63 		tokenToPrec.put(ttype, alt);
64 		ASSOC assoc = ASSOC.left;
65 		if ( t.terminalOptions!=null ) {
66 			String a = (String)t.terminalOptions.get("assoc");
67 			if ( a!=null ) {
68 				if ( a.equals(ASSOC.right.toString()) ) {
69 					assoc = ASSOC.right;
70 				}
71 				else {
72 					ErrorManager.error(ErrorManager.MSG_ILLEGAL_OPTION_VALUE, "assoc", assoc);
73 				}
74 			}
75 		}
76 
77 		if ( altAssociativity.get(alt)!=null && altAssociativity.get(alt)!=assoc ) {
78 			ErrorManager.error(ErrorManager.MSG_ALL_OPS_NEED_SAME_ASSOC, alt);
79 		}
80 		altAssociativity.put(alt, assoc);
81 
82 		//System.out.println("op " + alt + ": " + t.getText()+", assoc="+assoc);
83 	}
84 
85 	@Override
binaryAlt(GrammarAST altTree, GrammarAST rewriteTree, int alt)86 	public void binaryAlt(GrammarAST altTree, GrammarAST rewriteTree, int alt) {
87 		altTree = GrammarAST.dupTree(altTree);
88 		rewriteTree = GrammarAST.dupTree(rewriteTree);
89 
90 		stripSynPred(altTree);
91 		stripLeftRecursion(altTree);
92 
93 		// rewrite e to be e_[rec_arg]
94 		int nextPrec = nextPrecedence(alt);
95 		ST refST = recRuleTemplates.getInstanceOf("recRuleRef");
96 		refST.add("ruleName", ruleName);
97 		refST.add("arg", nextPrec);
98 		altTree = replaceRuleRefs(altTree, refST.render());
99 
100 		String altText = text(altTree);
101 		altText = altText.trim();
102 		altText += "{}"; // add empty alt to prevent pred hoisting
103 		ST nameST = recRuleTemplates.getInstanceOf("recRuleName");
104 		nameST.add("ruleName", ruleName);
105 		rewriteTree = replaceRuleRefs(rewriteTree, "$" + nameST.render());
106 		String rewriteText = text(rewriteTree);
107 		binaryAlts.put(alt, altText + (rewriteText != null ? " " + rewriteText : ""));
108 		//System.out.println("binaryAlt " + alt + ": " + altText + ", rewrite=" + rewriteText);
109 	}
110 
111 	/** Convert e ? e : e  &rarr;  ? e : e_[nextPrec] */
112 	@Override
ternaryAlt(GrammarAST altTree, GrammarAST rewriteTree, int alt)113 	public void ternaryAlt(GrammarAST altTree, GrammarAST rewriteTree, int alt) {
114 		altTree = GrammarAST.dupTree(altTree);
115 		rewriteTree = GrammarAST.dupTree(rewriteTree);
116 
117 		stripSynPred(altTree);
118 		stripLeftRecursion(altTree);
119 
120 		int nextPrec = nextPrecedence(alt);
121 		ST refST = recRuleTemplates.getInstanceOf("recRuleRef");
122 		refST.add("ruleName", ruleName);
123 		refST.add("arg", nextPrec);
124 		altTree = replaceLastRuleRef(altTree, refST.render());
125 
126 		String altText = text(altTree);
127 		altText = altText.trim();
128 		altText += "{}"; // add empty alt to prevent pred hoisting
129 		ST nameST = recRuleTemplates.getInstanceOf("recRuleName");
130 		nameST.add("ruleName", ruleName);
131 		rewriteTree = replaceRuleRefs(rewriteTree, "$" + nameST.render());
132 		String rewriteText = text(rewriteTree);
133 		ternaryAlts.put(alt, altText + (rewriteText != null ? " " + rewriteText : ""));
134 		//System.out.println("ternaryAlt " + alt + ": " + altText + ", rewrite=" + rewriteText);
135 	}
136 
137 	@Override
prefixAlt(GrammarAST altTree, GrammarAST rewriteTree, int alt)138 	public void prefixAlt(GrammarAST altTree, GrammarAST rewriteTree, int alt) {
139 		altTree = GrammarAST.dupTree(altTree);
140 		rewriteTree = GrammarAST.dupTree(rewriteTree);
141 
142 		stripSynPred(altTree);
143 
144 		int nextPrec = precedence(alt);
145 		// rewrite e to be e_[rec_arg]
146 		ST refST = recRuleTemplates.getInstanceOf("recRuleRef");
147 		refST.add("ruleName", ruleName);
148 		refST.add("arg", nextPrec);
149 		altTree = replaceRuleRefs(altTree, refST.render());
150 		String altText = text(altTree);
151 		altText = altText.trim();
152 		altText += "{}"; // add empty alt to prevent pred hoisting
153 
154 		ST nameST = recRuleTemplates.getInstanceOf("recRuleName");
155 		nameST.add("ruleName", ruleName);
156 		rewriteTree = replaceRuleRefs(rewriteTree, nameST.render());
157 		String rewriteText = text(rewriteTree);
158 
159 		prefixAlts.add(altText + (rewriteText != null ? " " + rewriteText : ""));
160 		//System.out.println("prefixAlt " + alt + ": " + altText + ", rewrite=" + rewriteText);
161 	}
162 
163 	@Override
suffixAlt(GrammarAST altTree, GrammarAST rewriteTree, int alt)164 	public void suffixAlt(GrammarAST altTree, GrammarAST rewriteTree, int alt) {
165 		altTree = GrammarAST.dupTree(altTree);
166 		rewriteTree = GrammarAST.dupTree(rewriteTree);
167 		stripSynPred(altTree);
168 		stripLeftRecursion(altTree);
169 		ST nameST = recRuleTemplates.getInstanceOf("recRuleName");
170 		nameST.add("ruleName", ruleName);
171 		rewriteTree = replaceRuleRefs(rewriteTree, "$" + nameST.render());
172 		String rewriteText = text(rewriteTree);
173 		String altText = text(altTree);
174 		altText = altText.trim();
175 		suffixAlts.put(alt, altText + (rewriteText != null ? " " + rewriteText : ""));
176 //		System.out.println("suffixAlt " + alt + ": " + altText + ", rewrite=" + rewriteText);
177 	}
178 
179 	@Override
otherAlt(GrammarAST altTree, GrammarAST rewriteTree, int alt)180 	public void otherAlt(GrammarAST altTree, GrammarAST rewriteTree, int alt) {
181 		altTree = GrammarAST.dupTree(altTree);
182 		rewriteTree = GrammarAST.dupTree(rewriteTree);
183 		stripSynPred(altTree);
184 		stripLeftRecursion(altTree);
185 		String altText = text(altTree);
186 
187 		String rewriteText = text(rewriteTree);
188 		otherAlts.add(altText + (rewriteText != null ? " " + rewriteText : ""));
189 		//System.out.println("otherAlt " + alt + ": " + altText + ", rewrite=" + rewriteText);
190 	}
191 
192 	// --------- get transformed rules ----------------
193 
getArtificialPrecStartRule()194 	public String getArtificialPrecStartRule() {
195 		ST ruleST = recRuleTemplates.getInstanceOf("recRuleStart");
196 		ruleST.add("ruleName", ruleName);
197 		ruleST.add("minPrec", 0);
198 		ruleST.add("userRetvals", retvals);
199 		fillRetValAssignments(ruleST, "recRuleName");
200 
201 		System.out.println("start: " + ruleST);
202 		return ruleST.render();
203 	}
204 
getArtificialOpPrecRule()205 	public String getArtificialOpPrecRule() {
206 		ST ruleST = recRuleTemplates.getInstanceOf("recRule");
207 		ruleST.add("ruleName", ruleName);
208 		ruleST.add("buildAST", grammar.buildAST());
209 		ST argDefST =
210 			generator.getTemplates().getInstanceOf("recRuleDefArg");
211 		ruleST.add("precArgDef", argDefST);
212 		ST ruleArgST =
213 			generator.getTemplates().getInstanceOf("recRuleArg");
214 		ruleST.add("argName", ruleArgST);
215 		ST setResultST =
216 			generator.getTemplates().getInstanceOf("recRuleSetResultAction");
217 		ruleST.add("setResultAction", setResultST);
218 		ruleST.add("userRetvals", retvals);
219 		fillRetValAssignments(ruleST, "recPrimaryName");
220 
221 		LinkedHashMap<Integer, String> opPrecRuleAlts = new LinkedHashMap<Integer, String>();
222 		opPrecRuleAlts.putAll(binaryAlts);
223 		opPrecRuleAlts.putAll(ternaryAlts);
224 		opPrecRuleAlts.putAll(suffixAlts);
225 		for (Map.Entry<Integer, String> entry : opPrecRuleAlts.entrySet()) {
226 			int alt = entry.getKey();
227 			String altText = entry.getValue();
228 			ST altST = recRuleTemplates.getInstanceOf("recRuleAlt");
229 			ST predST =
230 				generator.getTemplates().getInstanceOf("recRuleAltPredicate");
231 			predST.add("opPrec", precedence(alt));
232 			predST.add("ruleName", ruleName);
233 			altST.add("pred", predST);
234 			altST.add("alt", altText);
235 			ruleST.add("alts", altST);
236 		}
237 
238 		System.out.println(ruleST);
239 
240 		return ruleST.render();
241 	}
242 
getArtificialPrimaryRule()243 	public String getArtificialPrimaryRule() {
244 		ST ruleST = recRuleTemplates.getInstanceOf("recPrimaryRule");
245 		ruleST.add("ruleName", ruleName);
246 		ruleST.add("alts", prefixAlts);
247 		ruleST.add("alts", otherAlts);
248 		ruleST.add("userRetvals", retvals);
249 		System.out.println(ruleST);
250 		return ruleST.render();
251 	}
252 
replaceRuleRefs(GrammarAST t, String name)253 	public GrammarAST replaceRuleRefs(GrammarAST t, String name) {
254 		if ( t==null ) return null;
255 		for (GrammarAST rref : t.findAllType(RULE_REF)) {
256 			if ( rref.getText().equals(ruleName) ) rref.setText(name);
257 		}
258 		return t;
259 	}
260 
hasImmediateRecursiveRuleRefs(GrammarAST t, String ruleName)261 	public static boolean hasImmediateRecursiveRuleRefs(GrammarAST t, String ruleName) {
262 		if ( t==null ) return false;
263 		for (GrammarAST rref : t.findAllType(RULE_REF)) {
264 			if ( rref.getText().equals(ruleName) ) return true;
265 		}
266 		return false;
267 	}
268 
replaceLastRuleRef(GrammarAST t, String name)269 	public GrammarAST replaceLastRuleRef(GrammarAST t, String name) {
270 		if ( t==null ) return null;
271 		GrammarAST last = null;
272 		for (GrammarAST rref : t.findAllType(RULE_REF)) { last = rref; }
273 		if ( last !=null && last.getText().equals(ruleName) ) last.setText(name);
274 		return t;
275 	}
276 
stripSynPred(GrammarAST altAST)277 	public void stripSynPred(GrammarAST altAST) {
278 		GrammarAST t = (GrammarAST)altAST.getChild(0);
279 		if ( t.getType()==ANTLRParser.BACKTRACK_SEMPRED ||
280 			 t.getType()==ANTLRParser.SYNPRED ||
281 			 t.getType()==ANTLRParser.SYN_SEMPRED )
282 		{
283 			altAST.deleteChild(0); // kill it
284 		}
285 	}
286 
stripLeftRecursion(GrammarAST altAST)287 	public void stripLeftRecursion(GrammarAST altAST) {
288 		GrammarAST rref = (GrammarAST)altAST.getChild(0);
289 		if ( rref.getType()== ANTLRParser.RULE_REF &&
290 			 rref.getText().equals(ruleName))
291 		{
292 			// remove rule ref
293 			altAST.deleteChild(0);
294 			// reset index so it prints properly
295 			GrammarAST newFirstChild = (GrammarAST) altAST.getChild(0);
296 			altAST.setTokenStartIndex(newFirstChild.getTokenStartIndex());
297 		}
298 	}
299 
text(GrammarAST t)300 	public String text(GrammarAST t) {
301 		if ( t==null ) return null;
302 		try {
303 			return new ANTLRTreePrinter(new CommonTreeNodeStream(t)).toString(grammar, true);
304 		}
305 		catch (Exception e) {
306 			ErrorManager.error(ErrorManager.MSG_BAD_AST_STRUCTURE, e);
307 		}
308 		return null;
309 	}
310 
precedence(int alt)311 	public int precedence(int alt) {
312 		return numAlts-alt+1;
313 	}
314 
nextPrecedence(int alt)315 	public int nextPrecedence(int alt) {
316 		int p = precedence(alt);
317 		if ( altAssociativity.get(alt)==ASSOC.left ) p++;
318 		return p;
319 	}
320 
fillRetValAssignments(ST ruleST, String srcName)321 	public void fillRetValAssignments(ST ruleST, String srcName) {
322 		if ( retvals==null ) return;
323 
324 		// complicated since we must be target-independent
325 		for (String name : getNamesFromArgAction(retvals.token)) {
326 			ST setRetValST =
327 				generator.getTemplates().getInstanceOf("recRuleSetReturnAction");
328 			ST ruleNameST = recRuleTemplates.getInstanceOf(srcName);
329 			ruleNameST.add("ruleName", ruleName);
330 			setRetValST.add("src", ruleNameST);
331 			setRetValST.add("name", name);
332 			ruleST.add("userRetvalAssignments",setRetValST);
333 		}
334 	}
335 
getNamesFromArgAction(Token t)336 	public Collection<String> getNamesFromArgAction(Token t) {
337 		AttributeScope returnScope = grammar.createReturnScope("",t);
338 		returnScope.addAttributes(t.getText(), ',');
339 		return returnScope.attributes.keySet();
340 	}
341 
342 	@Override
toString()343 	public String toString() {
344 		return "PrecRuleOperatorCollector{" +
345 			   "binaryAlts=" + binaryAlts +
346 			   ", rec=" + tokenToPrec +
347 			   ", ternaryAlts=" + ternaryAlts +
348 			   ", suffixAlts=" + suffixAlts +
349 			   ", prefixAlts=" + prefixAlts +
350 			   ", otherAlts=" + otherAlts +
351 			   '}';
352 	}
353 }
354