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

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