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 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 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 -> ? 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 (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 getArtificialPrimaryRule()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 replaceRuleRefs(GrammarAST t, String name)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 hasImmediateRecursiveRuleRefs(GrammarAST t, String ruleName)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 replaceLastRuleRef(GrammarAST t, String name)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 stripSynPred(GrammarAST altAST)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 stripLeftRecursion(GrammarAST altAST)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 text(GrammarAST t)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 precedence(int alt)310 public int precedence(int alt) { 311 return numAlts-alt+1; 312 } 313 nextPrecedence(int alt)314 public int nextPrecedence(int alt) { 315 int p = precedence(alt); 316 if ( altAssociativity.get(alt)==ASSOC.left ) p++; 317 return p; 318 } 319 fillRetValAssignments(ST ruleST, String srcName)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 getNamesFromArgAction(Token t)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 toString()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