1package org.antlr.tool;
2
3import org.antlr.codegen.CodeGenerator;
4import org.antlr.grammar.v3.*;
5import org.antlr.runtime.Token;
6import org.antlr.runtime.tree.CommonTreeNodeStream;
7import org.antlr.runtime.tree.TreeNodeStream;
8import org.stringtemplate.v4.*;
9
10import java.util.*;
11
12/** */
13public 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
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
43	public void loadPrecRuleTemplates() {
44		recRuleTemplates =
45			new STGroupFile(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
55	public void setReturnValues(GrammarAST t) {
56		System.out.println(t);
57		retvals = t;
58	}
59
60	@Override
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
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  ->  ? e : e_[nextPrec] */
112	@Override
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
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
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
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
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
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 (int alt : opPrecRuleAlts.keySet()) {
226			String altText = opPrecRuleAlts.get(alt);
227			ST altST = recRuleTemplates.getInstanceOf("recRuleAlt");
228			ST predST =
229				generator.getTemplates().getInstanceOf("recRuleAltPredicate");
230			predST.add("opPrec", precedence(alt));
231			predST.add("ruleName", ruleName);
232			altST.add("pred", predST);
233			altST.add("alt", altText);
234			ruleST.add("alts", altST);
235		}
236
237		System.out.println(ruleST);
238
239		return ruleST.render();
240	}
241
242	public String getArtificialPrimaryRule() {
243		ST ruleST = recRuleTemplates.getInstanceOf("recPrimaryRule");
244		ruleST.add("ruleName", ruleName);
245		ruleST.add("alts", prefixAlts);
246		ruleST.add("alts", otherAlts);
247		ruleST.add("userRetvals", retvals);
248		System.out.println(ruleST);
249		return ruleST.render();
250	}
251
252	public GrammarAST replaceRuleRefs(GrammarAST t, String name) {
253		if ( t==null ) return null;
254		for (GrammarAST rref : t.findAllType(RULE_REF)) {
255			if ( rref.getText().equals(ruleName) ) rref.setText(name);
256		}
257		return t;
258	}
259
260	public static boolean hasImmediateRecursiveRuleRefs(GrammarAST t, String ruleName) {
261		if ( t==null ) return false;
262		for (GrammarAST rref : t.findAllType(RULE_REF)) {
263			if ( rref.getText().equals(ruleName) ) return true;
264		}
265		return false;
266	}
267
268	public GrammarAST replaceLastRuleRef(GrammarAST t, String name) {
269		if ( t==null ) return null;
270		GrammarAST last = null;
271		for (GrammarAST rref : t.findAllType(RULE_REF)) { last = rref; }
272		if ( last !=null && last.getText().equals(ruleName) ) last.setText(name);
273		return t;
274	}
275
276	public void stripSynPred(GrammarAST altAST) {
277		GrammarAST t = (GrammarAST)altAST.getChild(0);
278		if ( t.getType()==ANTLRParser.BACKTRACK_SEMPRED ||
279			 t.getType()==ANTLRParser.SYNPRED ||
280			 t.getType()==ANTLRParser.SYN_SEMPRED )
281		{
282			altAST.deleteChild(0); // kill it
283		}
284	}
285
286	public void stripLeftRecursion(GrammarAST altAST) {
287		GrammarAST rref = (GrammarAST)altAST.getChild(0);
288		if ( rref.getType()== ANTLRParser.RULE_REF &&
289			 rref.getText().equals(ruleName))
290		{
291			// remove rule ref
292			altAST.deleteChild(0);
293			// reset index so it prints properly
294			GrammarAST newFirstChild = (GrammarAST) altAST.getChild(0);
295			altAST.setTokenStartIndex(newFirstChild.getTokenStartIndex());
296		}
297	}
298
299	public String text(GrammarAST t) {
300		if ( t==null ) return null;
301		try {
302			return new ANTLRTreePrinter(new CommonTreeNodeStream(t)).toString(grammar, true);
303		}
304		catch (Exception e) {
305			ErrorManager.error(ErrorManager.MSG_BAD_AST_STRUCTURE, e);
306		}
307		return null;
308	}
309
310	public int precedence(int alt) {
311		return numAlts-alt+1;
312	}
313
314	public int nextPrecedence(int alt) {
315		int p = precedence(alt);
316		if ( altAssociativity.get(alt)==ASSOC.left ) p++;
317		return p;
318	}
319
320	public void fillRetValAssignments(ST ruleST, String srcName) {
321		if ( retvals==null ) return;
322
323		// complicated since we must be target-independent
324		for (String name : getNamesFromArgAction(retvals.token)) {
325			ST setRetValST =
326				generator.getTemplates().getInstanceOf("recRuleSetReturnAction");
327			ST ruleNameST = recRuleTemplates.getInstanceOf(srcName);
328			ruleNameST.add("ruleName", ruleName);
329			setRetValST.add("src", ruleNameST);
330			setRetValST.add("name", name);
331			ruleST.add("userRetvalAssignments",setRetValST);
332		}
333	}
334
335	public Collection<String> getNamesFromArgAction(Token t) {
336		AttributeScope returnScope = grammar.createReturnScope("",t);
337		returnScope.addAttributes(t.getText(), ',');
338		return returnScope.attributes.keySet();
339	}
340
341	@Override
342	public String toString() {
343		return "PrecRuleOperatorCollector{" +
344			   "binaryAlts=" + binaryAlts +
345			   ", rec=" + tokenToPrec +
346			   ", ternaryAlts=" + ternaryAlts +
347			   ", suffixAlts=" + suffixAlts +
348			   ", prefixAlts=" + prefixAlts +
349			   ", otherAlts=" + otherAlts +
350			   '}';
351	}
352}
353