jars/icu4j-4_2_1-src/src/com/ibm/icu/dev/test/util/BNF.java

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