1/* GENERATED SOURCE. DO NOT MODIFY. */ 2/* 3 ******************************************************************************* 4 * Copyright (C) 2002-2012, International Business Machines Corporation and * 5 * others. All Rights Reserved. * 6 ******************************************************************************* 7 */ 8package android.icu.dev.util; 9 10import java.util.ArrayList; 11import java.util.HashMap; 12import java.util.HashSet; 13import java.util.Iterator; 14import java.util.Map; 15import java.util.Random; 16import java.util.Set; 17 18import android.icu.text.UnicodeSet; 19 20public class BNF { 21 private Map map = new HashMap(); 22 private Set variables = new HashSet(); 23 private Pick pick = null; 24 private Pick.Target target = null; 25 private Tokenizer t; 26 private Quoter quoter; 27 private Random random; 28 29 public String next() { 30 return target.next(); 31 } 32 33 public String getInternal() { 34 return pick.getInternal(0, new HashSet()); 35 } 36 37 /* 38 + "weight = integer '%';" 39 + "range = '{' integer (',' integer?)? '}' weight*;" 40 + "quote = '@';" 41 + "star = '*' weight*;" 42 + "plus = '+' weight*;" 43 + "maybe = '?' weight?;" 44 + "quantifier = range | star | maybe | plus;" 45 + "core = string | unicodeSet | '(' alternation ')';" 46 + "sequence = (core quantifier*)+;" 47 + "alternation = sequence (weight? ('|' sequence weight?)+)?;" 48 + "rule = string '=' alternation;"; 49 50 51 * Match 0 or more times 52 + Match 1 or more times 53 ? Match 1 or 0 times 54 {n} Match exactly n times 55 {n,} Match at least n times 56 {n,m} Match at least n but not more than m times 57 58 59 60 */ 61 62 public BNF(Random random, Quoter quoter) { 63 this.random = random; 64 this.quoter = quoter; 65 t = new Tokenizer(); 66 } 67 68 public BNF addRules(String rules) { 69 t.setSource(rules); 70 while (addRule()) { 71 } 72 return this; // for chaining 73 } 74 75 public BNF complete() { 76 // check that the rules match the variables, except for $root in rules 77 Set ruleSet = map.keySet(); 78 // add also 79 variables.add("$root"); 80 variables.addAll(t.getLookedUpItems()); 81 if (!ruleSet.equals(variables)) { 82 String msg = showDiff(variables, ruleSet); 83 if (msg.length() != 0) msg = "Error: Missing definitions for: " + msg; 84 String temp = showDiff(ruleSet, variables); 85 if (temp.length() != 0) temp = "Warning: Defined but not used: " + temp; 86 if (msg.length() == 0) msg = temp; 87 else if (temp.length() != 0) { 88 msg = msg + "; " + temp; 89 } 90 error(msg); 91 } 92 93 if (!ruleSet.equals(variables)) { 94 String msg = showDiff(variables, ruleSet); 95 if (msg.length() != 0) msg = "Missing definitions for: " + msg; 96 String temp = showDiff(ruleSet, variables); 97 if (temp.length() != 0) temp = "Defined but not used: " + temp; 98 if (msg.length() == 0) msg = temp; 99 else if (temp.length() != 0) { 100 msg = msg + "; " + temp; 101 } 102 error(msg); 103 } 104 105 // replace variables by definitions 106 Iterator it = ruleSet.iterator(); 107 while (it.hasNext()) { 108 String key = (String) it.next(); 109 Pick expression = (Pick) map.get(key); 110 Iterator it2 = ruleSet.iterator(); 111 if (false && key.equals("$crlf")) { 112 System.out.println("debug") ; 113 } 114 while (it2.hasNext()) { 115 Object key2 = it2.next(); 116 if (key.equals(key2)) continue; 117 Pick expression2 = (Pick) map.get(key2); 118 expression2.replace(key, expression); 119 } 120 } 121 pick = (Pick) map.get("$root"); 122 target = Pick.Target.make(pick, random, quoter); 123 // TODO remove temp collections 124 return this; 125 } 126 127 String showDiff(Set a, Set b) { 128 Set temp = new HashSet(); 129 temp.addAll(a); 130 temp.removeAll(b); 131 if (temp.size() == 0) return ""; 132 StringBuffer buffer = new StringBuffer(); 133 Iterator it = temp.iterator(); 134 while (it.hasNext()) { 135 if (buffer.length() != 0) buffer.append(", "); 136 buffer.append(it.next().toString()); 137 } 138 return buffer.toString(); 139 } 140 141 void error(String msg) { 142 throw new IllegalArgumentException(msg 143 + "\r\n" + t.toString()); 144 } 145 146 private boolean addRule() { 147 int type = t.next(); 148 if (type == Tokenizer.DONE) return false; 149 if (type != Tokenizer.STRING) error("missing weight"); 150 String s = t.getString(); 151 if (s.length() == 0 || s.charAt(0) != '$') error("missing $ in variable"); 152 if (t.next() != '=') error("missing ="); 153 int startBody = t.index; 154 Pick rule = getAlternation(); 155 if (rule == null) error("missing expression"); 156 t.addSymbol(s, t.getSource(), startBody, t.index); 157 if (t.next() != ';') error("missing ;"); 158 return addPick(s, rule); 159 } 160 161 protected boolean addPick(String s, Pick rule) { 162 Object temp = map.get(s); 163 if (temp != null) error("duplicate variable"); 164 if (rule.name == null) rule.name(s); 165 map.put(s, rule); 166 return true; 167 } 168 169 public BNF addSet(String variable, UnicodeSet set) { 170 if (set != null) { 171 String body = set.toString(); 172 t.addSymbol(variable, body, 0, body.length()); 173 addPick(variable, Pick.codePoint(set)); 174 } 175 return this; 176 } 177 178 int maxRepeat = 99; 179 180 Pick qualify(Pick item) { 181 int[] weights; 182 int type = t.next(); 183 switch(type) { 184 case '@': 185 return new Pick.Quote(item); 186 case '~': 187 return new Pick.Morph(item); 188 case '?': 189 int weight = getWeight(); 190 if (weight == NO_WEIGHT) weight = 50; 191 weights = new int[] {100-weight, weight}; 192 return Pick.repeat(0, 1, weights, item); 193 case '*': 194 weights = getWeights(); 195 return Pick.repeat(1, maxRepeat, weights, item); 196 case '+': 197 weights = getWeights(); 198 return Pick.repeat(1, maxRepeat, weights, item); 199 case '{': 200 if (t.next() != Tokenizer.NUMBER) error("missing number"); 201 int start = (int) t.getNumber(); 202 int end = start; 203 type = t.next(); 204 if (type == ',') { 205 end = maxRepeat; 206 type = t.next(); 207 if (type == Tokenizer.NUMBER) { 208 end = (int)t.getNumber(); 209 type = t.next(); 210 } 211 } 212 if (type != '}') error("missing }"); 213 weights = getWeights(); 214 return Pick.repeat(start, end, weights, item); 215 } 216 t.backup(); 217 return item; 218 } 219 220 Pick getCore() { 221 int token = t.next(); 222 if (token == Tokenizer.STRING) { 223 String s = t.getString(); 224 if (s.charAt(0) == '$') variables.add(s); 225 return Pick.string(s); 226 } 227 if (token == Tokenizer.UNICODESET) { 228 return Pick.codePoint(t.getUnicodeSet()); 229 } 230 if (token != '(') { 231 t.backup(); 232 return null; 233 } 234 Pick temp = getAlternation(); 235 token = t.next(); 236 if (token != ')') error("missing )"); 237 return temp; 238 } 239 240 Pick getSequence() { 241 Pick.Sequence result = null; 242 Pick last = null; 243 while (true) { 244 Pick item = getCore(); 245 if (item == null) { 246 if (result != null) return result; 247 if (last != null) return last; 248 error("missing item"); 249 } 250 // qualify it as many times as possible 251 Pick oldItem; 252 do { 253 oldItem = item; 254 item = qualify(item); 255 } while (item != oldItem); 256 // add it in 257 if (last == null) { 258 last = item; 259 } else { 260 if (result == null) result = Pick.makeSequence().and2(last); 261 result = result.and2(item); 262 } 263 } 264 } 265 266 // for simplicity, we just use recursive descent 267 Pick getAlternation() { 268 Pick.Alternation result = null; 269 Pick last = null; 270 int lastWeight = NO_WEIGHT; 271 while (true) { 272 Pick temp = getSequence(); 273 if (temp == null) error("empty alternation"); 274 int weight = getWeight(); 275 if (weight == NO_WEIGHT) weight = 1; 276 if (last == null) { 277 last = temp; 278 lastWeight = weight; 279 } else { 280 if (result == null) result = Pick.makeAlternation().or2(lastWeight, last); 281 result = result.or2(weight, temp); 282 } 283 int token = t.next(); 284 if (token != '|') { 285 t.backup(); 286 if (result != null) return result; 287 if (last != null) return last; 288 } 289 } 290 } 291 292 private static final int NO_WEIGHT = Integer.MIN_VALUE; 293 294 int getWeight() { 295 int weight; 296 int token = t.next(); 297 if (token != Tokenizer.NUMBER) { 298 t.backup(); 299 return NO_WEIGHT; 300 } 301 weight = (int)t.getNumber(); 302 token = t.next(); 303 if (token != '%') error("missing %"); 304 return weight; 305 } 306 307 int[] getWeights() { 308 ArrayList list = new ArrayList(); 309 while (true) { 310 int weight = getWeight(); 311 if (weight == NO_WEIGHT) break; 312 list.add(new Integer(weight)); 313 } 314 if (list.size() == 0) return null; 315 int[] result = new int[list.size()]; 316 for (int i = 0; i < list.size(); ++i) { 317 result[i] = ((Integer)list.get(i)).intValue(); 318 } 319 return result; 320 } 321 322 public int getMaxRepeat() { 323 return maxRepeat; 324 } 325 326 public BNF setMaxRepeat(int maxRepeat) { 327 this.maxRepeat = maxRepeat; 328 return this; 329 } 330} 331