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