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 → ? 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