Java > Open Source Codes > ro > infoiasi > donald > compiler > cfg > CFG


1 package ro.infoiasi.donald.compiler.cfg;
2
3 import java.util.*;
4 import java.io.*;
5
6 /** Context Free Grammar */
7 public class CFG {
8     private NonTerminals v;
9     private Terminals t;
10     private NonTerminal s;
11     private Productions p;
12
13     /** The set of nullable non-terminals */
14     private Set vNullable;
15     /** The set of nullable productions */
16     private Set pNullable;
17
18     /** An array containing the FIRST set for each non-terminal */
19     private Set[] vFirst;
20     /** An array containing the FIRST set for each production */
21     private Set[] pFirst;
22
23     /** An array containing the FOLLOW set for each non-terminal */
24     private Set[] vFollow;
25
26     public CFG(NonTerminals v, Terminals t, NonTerminal s, Productions p) {
27         this.v = v;
28         this.t = t;
29         if (s == null) {
30             this.s = v.find(0);
31         } else {
32             this.s = s;
33         }
34         this.p = p;
35         removeUseless();
36     }
37
38     /** Removes the useless non-terminals and productions from the grammar.
39     A non-terminal is useless if it is not accessible or not productive.
40     A production is useless if it contains at least one useless non-terminal. */
41     private void removeUseless() {
42     /* When removing non-terminals and productions
43     their hash codes become unstable.*/
44         boolean haveUseless;
45         do {
46             Set vAccessible = new HashSet();
47             vAccessible.add(s);
48             LinkedList queue = new LinkedList();
49             queue.addLast(s);
50
51             while (!queue.isEmpty()) {
52                 NonTerminal a = (NonTerminal)queue.removeLast();
53                 Iterator itL = p.iterator(a);
54                 while (itL.hasNext()) {
55                     Word w = ((Production)itL.next()).getRHS();
56                     WordIterator itW = w.iterator();
57                     while (itW.hasNextNonTerminal()) {
58                         NonTerminal b = itW.nextNonTerminal();
59                         if (vAccessible.add(b)) {
60                             queue.addLast(b);
61                         }
62                     }
63                 }
64             }
65
66             Set vProductive = new HashSet();
67             boolean changed;
68             do {
69                 changed = false;
70                 Iterator itV = v.iterator();
71                 while (itV.hasNext()) {
72                     NonTerminal a = (NonTerminal)itV.next();
73                     if (!vProductive.contains(a)) {
74                         Iterator itP = p.iterator(a);
75                         while (itP.hasNext()) {
76                             Word w = ((Production)itP.next()).getRHS();
77                             WordIterator itW = w.iterator();
78                             boolean isProductive = true;
79                             while (itW.hasNextNonTerminal()) {
80                                 NonTerminal b =
81                                     (NonTerminal)itW.nextNonTerminal();
82                                 if (!vProductive.contains(b)) {
83                                     isProductive = false;
84                                     break;
85                                 }
86                             }
87                             if (isProductive) {
88                                 vProductive.add(a);
89                                 changed = true;
90                                 break;
91                             }
92                         }
93                     }
94                 }
95             } while (changed);
96
97             haveUseless = vAccessible.size()<v.count() ||
98                     vProductive.size()<v.count();
99             if (haveUseless) {
100                 // WARNING !!! it's imperative not to use hashing here
101 // and because TreeSet requires Comparable or Comparator
102 // we use a LinkedList
103 LinkedList vUseless = new LinkedList();
104                 for (int i = 0; i<v.count(); i++) {
105                     NonTerminal a = v.find(i);
106                     if (!vAccessible.contains(a) || !vProductive.contains(a)) {
107                         vUseless.add(a);
108                     }
109                 }
110                 v.removeUseless(vUseless);
111                 p.removeUseless(vUseless);
112             }
113         } while(haveUseless);
114     }
115
116     /** Adds a new start non-terminal $START to the grammar
117     and the production $START ::= oldStart EOF */
118     public Production addStartProduction() {
119         NonTerminal oldStart = s;
120         s = v.addNew("$START");
121         Word rhs = new Word();
122         rhs.addLast(oldStart);
123         rhs.addLast(t.EOF);
124         return p.addNew(s, rhs);
125     }
126
127     public NonTerminals getNonTerminals() {
128         return v;
129     }
130
131     public Terminals getTerminals() {
132         return t;
133     }
134
135     public NonTerminal getStartSymbol() {
136         return s;
137     }
138
139     public Productions getProductions() {
140         return p;
141     }
142
143     public int symbolCount() {
144         return v.count()+t.count();
145     }
146
147     public int getSID(Symbol x) {
148         int xSID = x.getIndex();
149         if (x.isTerminal()) {
150             xSID += v.count();
151         }
152         return xSID;
153     }
154
155     public Symbol symbol(int SID) {
156         if (0 <= SID && SID < v.count()) {
157             return v.find(SID);
158         } else if (SID < v.count()+t.count()) {
159             return t.find(SID-v.count());
160         } else {
161             throw new IllegalArgumentException ();
162         }
163     }
164
165     public void computeNullable() {
166         vNullable = new HashSet();
167         pNullable = new HashSet();
168         Set pVisited = new HashSet();
169         // a production is "visided" if it's (non)nullability in certain
170
171         boolean changed;
172         do {
173             changed = false;
174             Iterator itV = v.iterator();
175             while (itV.hasNext()) {
176                 NonTerminal a = (NonTerminal)itV.next();
177                 Iterator itP = p.iterator(a);
178                 while (itP.hasNext()) {
179                     Production prod = (Production)itP.next();
180                     if (!pVisited.contains(prod)) {
181                         Word w = prod.getRHS();
182                         WordIterator itW = w.iterator();
183                         if (itW.hasNextTerminal()) {
184                             pVisited.add(prod);
185                         } else {
186                             boolean nullable = true;
187                             while (itW.hasNext() && nullable) {
188                                 NonTerminal b = (NonTerminal)itW.next();
189                                 if (!vNullable.contains(b)) {
190                                     nullable = false; // cannot decide right now
191 }
192                             }
193                             if (nullable) {
194                                 vNullable.add(a);
195                                 pNullable.add(prod);
196                                 pVisited.add(prod);
197                                 changed = true;
198                             }
199                         }
200                     }
201                 }
202             }
203         } while (changed);
204     }
205
206     public boolean nullable(NonTerminal var) {
207         return vNullable.contains(var);
208     }
209
210     public boolean nullable(Production prod) {
211         return pNullable.contains(prod);
212     }
213
214     public boolean nullable(Word w) {
215         WordIterator itW = w.iterator();
216         if (itW.hasNextTerminal()) {
217             return false;
218         }
219         while (itW.hasNext()) {
220             NonTerminal var = (NonTerminal)itW.next();
221             if (!nullable(var)) {
222                 return false;
223             }
224         }
225         return true;
226     }
227     
228     
229     /** Epsilon rule elimination */
230     private void eliminateEpsilon() {
231         if (vNullable == null) {
232             computeNullable();
233         }
234 // System.out.println("vNullable:"+vNullable);
235
236         Productions pNew = new Productions();
237         Iterator itP = p.iterator();
238         while (itP.hasNext()) {
239             Production prod = (Production)itP.next();
240 // System.out.println("Production:"+prod);
241
242             Word w = prod.getRHS();
243             // ignore epsilon rules
244 if (!w.isEmpty()) {
245                 ArrayList words = new ArrayList();
246                 WordIterator itW = w.iterator();
247                 while (itW.hasNextNonTerminal()) {
248                     NonTerminal x = itW.nextNonTerminal();
249 // System.out.println("NonTerminal:"+x);
250 // System.out.println("words:"+words);
251 // System.out.println("w:"+w);
252
253                     if (vNullable.contains(x)) {
254                         Word prefW = itW.prefix();
255 // System.out.println("[NULABLE]");
256 // System.out.println("prefW:"+prefW);
257 if (words.isEmpty()) {
258                             Word w1 = new Word(prefW);
259                             Word w0 = new Word(prefW);
260                             w0.removeLast();
261                             words.add(w0);
262                             words.add(w1);
263
264                             w = new Word(itW.suffix());
265                         } else {
266                             int size = words.size();
267                             for (int i = 0; i<size; i++) {
268                                 Word w0 = (Word)words.get(i);
269                                 Word w1 = new Word(w0);
270                                 w1.addWordLast(new Word(prefW));
271                                 w0.addWordLast(new Word(prefW));
272                                 w0.removeLast();
273                                 words.add(w1);
274                             }
275                             w = itW.suffix();
276                         }
277                         itW = w.iterator();
278                     }
279                 }
280                 while (itW.hasNextTerminal()) {
281                     Terminal a = itW.nextTerminal();
282                     for (int i = 0; i<words.size(); i++) {
283                         Word wi = (Word)words.get(i);
284                         wi.addWordLast(new Word(itW.suffix()));
285                     }
286
287                 }
288                 if (words.isEmpty()) {
289                     // rule doesn't contain nullable symbols
290 pNew.addNew(prod.getLHS(), prod.getRHS()); //!!TODO: an exact copy might be better
291 } else {
292                     Iterator it = words.iterator();
293                     while (it.hasNext()) {
294                         Word w0 = (Word)it.next();
295                         w0.addWordLast(new Word(w)); // new optional?
296 // ignore epsilon rules
297 if (!w0.isEmpty()) {
298                             pNew.addNew(prod.getLHS(), w0);
299                         }
300                     }
301                 }
302             }
303         }
304         p = pNew;
305 // System.out.println("after epsilon rule elimination:\n"+p);
306 }
307     
308     /** Eliminate unit productions */
309     private void eliminateUnitProductions() {
310         Productions pNew = new Productions();
311         
312         // eliminate unit productions
313 Map map = new HashMap();
314         // foreach x in V, map.get(x) returns Set S, so that
315 // foreach y in S we have y ->* x
316 Iterator itV = v.iterator();
317         while (itV.hasNext()) {
318             NonTerminal x = (NonTerminal)itV.next();
319             Set set = new LinkedHashSet();
320             set.add(x);
321             map.put(x, set);
322         }
323         
324         boolean changed;
325         do {
326             changed = false;
327             Iterator itP = p.iterator();
328             while (itP.hasNext()) {
329                 Production prod = (Production)itP.next();
330                 Word w = prod.getRHS();
331                 if (w.size() == 1 && w.getFirst() instanceof NonTerminal) {
332                     // the rule is x2 ::= x
333 NonTerminal x = (NonTerminal)w.getFirst();
334                     NonTerminal x2 = prod.getLHS();
335                     Set s2 = (Set)map.get(x2);
336                     Iterator itS2 = s2.iterator();
337                     while (itS2.hasNext()) {
338                         // x1 =>* x2 then x1 =>* x
339 NonTerminal x1 = (NonTerminal)itS2.next();
340                         Set s2prime = (Set)map.get(x);
341                         if (s2prime.add(x1)) {
342                             changed = true;
343 // System.out.println("("+x1+","+x+")");
344 }
345                     }
346                 }
347             }
348         } while (changed);
349
350         // eliminate unit productions
351 Iterator itP = p.iterator();
352         while (itP.hasNext()) {
353             Production prod = (Production)itP.next();
354             Word w = prod.getRHS();
355             if (w.size() != 1 || w.getFirst() instanceof Terminal) {
356                 pNew.addNew(prod.getLHS(), prod.getRHS()); //!!TODO: an exact copy might be better
357 }
358         }
359
360         // add new rules to the grammar
361 itV = v.iterator();
362         while (itV.hasNext()) {
363             NonTerminal x2 = (NonTerminal)itV.next();
364             Set set = (Set)map.get(x2);
365             Iterator itS = set.iterator();
366             while (itS.hasNext()) {
367                 // x1 =>* x2
368 NonTerminal x1 = (NonTerminal)itS.next();
369                 if (x1 != x2) {
370                     LinkedList list = pNew.find(x2);
371                     if (list != null) { //!TODO: check the "find" function -> is it normal to return null or empty list?
372 Iterator itL = list.iterator();
373                         while (itL.hasNext()) {
374                             Production prod = (Production)itL.next();
375                             Word w = prod.getRHS();
376                             // x2 ::= w, than add the new rule x1 ::= w
377 pNew.addNew(x1, w);
378                         }
379                     }
380                 }
381             }
382         }
383         p = pNew;
384     }
385
386     // Arange that all bodies of length 2 or more consist only of variables
387 private void toChomskyNormalFormStep4() {
388         Productions pNew = new Productions();
389         Map map = new LinkedHashMap(); // (terminal -> nonterminal(new) or null)
390
391         int count = 0;
392         Iterator it = p.iterator();
393         while (it.hasNext()) {
394             Production prod = (Production)it.next();
395             Word w = prod.getRHS();
396             if (w.size() >= 2) {
397                 pNew.addNew(prod.getLHS(), w);
398                 WordIterator itW = w.iterator();
399                 while (itW.hasNext()) {
400                     Symbol sym = itW.next();
401                     if (sym instanceof Terminal) {
402                         NonTerminal y = (NonTerminal)map.get(sym);
403                         if (y == null) {
404                             y = v.addNew("$nt_cnf"+(count++));
405                             map.put(sym, y);
406                         }
407                         pNew.addNew(y, new Word(sym));
408                         itW.set(y);
409                     }
410                 }
411             } else {
412                 pNew.addNew(prod.getLHS(), w);
413             }
414         }
415         p = pNew;
416     }
417
418     private void toChomskyNormalFormStep5() {
419         // Break the bodies of lenght 3 or more into a cascade of productions
420 Productions pNew = new Productions();
421         int count = 0;
422         Iterator it = p.iterator();
423         while (it.hasNext()) {
424             Production prod = (Production)it.next();
425 // System.out.println("\nProduction:"+prod);
426 Word w = new Word(prod.getRHS());
427             if (w.size() > 2) {
428                 NonTerminal x = prod.getLHS();
429                 // x ::= x1 x2 ... xn
430 while (w.size() > 2) {
431                     Symbol sym = w.removeFirst();
432                     NonTerminal newX = v.addNew("$nt$cnf"+(count++));
433                     pNew.addNew(x, new Word(sym, newX));
434                     x = newX; // newX ::= w
435 }
436                 pNew.addNew(x, new Word(w));
437             } else {
438                 pNew.addNew(prod.getLHS(), w);
439             }
440         }
441         p = pNew;
442     }
443     
444     /** Transforms a grammar to the Chomsky normal form
445     all the precedences and semantic actions are discarded from the productions */
446     public void toChomskyNormalForm() {
447
448         // Step 1
449 eliminateEpsilon();
450 // System.out.println(this);
451
452         // Step 2
453 eliminateUnitProductions();
454 // System.out.println(this);
455
456         // Step 3
457 removeUseless();
458         
459         // Step 4
460 toChomskyNormalFormStep4();
461 // System.out.println(this);
462
463         // Step 5
464 toChomskyNormalFormStep5();
465 // System.out.println(this);
466
467         System.gc();
468     }
469
470     public void computeFirst() {
471         if (vNullable == null) {
472             computeNullable();
473         }
474
475         vFirst = new Set[v.count()];
476         for (int i = 0; i<v.count(); i++) {
477             vFirst[i] = new LinkedHashSet();
478         }
479
480         pFirst = new Set[p.count()];
481         for (int i = 0; i<p.count(); i++) {
482             pFirst[i] = new LinkedHashSet();
483         }
484
485         boolean changed;
486         do {
487             changed = false;
488             for (int i = 0; i<v.count(); i++) {
489                 Iterator itL = p.iterator(v.find(i));
490                 while (itL.hasNext()) {
491                     Production prod = (Production)itL.next();
492                     int j = prod.getIndex();
493
494                     Word w = prod.getRHS();
495                     if (!w.isEmpty()) {
496                         WordIterator itW = w.iterator();
497                         boolean over = false;
498                         while (itW.hasNext() && !over) {
499                             Symbol symbol = itW.next();
500                             if (symbol.isTerminal()) {
501                                 if (vFirst[i].add(symbol)) {
502                                     changed = true;
503                                 }
504                                 if (pFirst[j].add(symbol)) {
505                                     changed = true;
506                                 }
507                                 over = true;
508                             } else {
509                                 int k = symbol.getIndex();
510                                 if (vFirst[i].addAll(vFirst[k])) {
511                                     changed = true;
512                                 }
513                                 if (pFirst[j].addAll(vFirst[k])) {
514                                     changed = true;
515                                 }
516                                 if (!nullable((NonTerminal)symbol)) {
517                                     over = true;
518                                 }
519                             }
520                         }
521                     }
522                 }
523             }
524         } while (changed);
525     }
526
527     public Set first(NonTerminal var) {
528         return vFirst[var.getIndex()];
529     }
530
531     public Set first(Production prod) {
532         return pFirst[prod.getIndex()];
533     }
534     // Space efficient - don't use pFirst
535 // return first(prod.getRHS());
536 //
537
538     public Set first(Word w) {
539         Set first = new LinkedHashSet();
540         if (!w.isEmpty()) {
541             WordIterator itW = w.iterator();
542             Symbol symbol;
543             do {
544                 symbol = itW.next();
545                 if (symbol.isTerminal()) {
546                     first.add(symbol);
547                 } else {
548                     first.addAll(first((NonTerminal)symbol));
549                 }
550             } while (itW.hasNext() && !symbol.isTerminal() &&
551                     nullable((NonTerminal)symbol));
552         }
553         return first;
554     }
555
556     public void computeFollow() {
557         if (vFirst == null) {
558             computeFirst();
559         }
560         vFollow = new Set[v.count()];
561         for (int i = 0; i<v.count(); i++) {
562             vFollow[i] = new LinkedHashSet();
563         }
564
565         vFollow[s.getIndex()].add(t.EOF);
566
567         Iterator itV = v.iterator();
568         while (itV.hasNext()) {
569             NonTerminal a = (NonTerminal)itV.next();
570             Iterator itL = p.find(a).iterator();
571             while (itL.hasNext()) {
572                 Production prod = (Production)itL.next();
573                 Word w = prod.getRHS();
574                 WordIterator itW = w.iterator();
575                 while (itW.hasNextNonTerminal()) {
576                     int j = itW.nextNonTerminal().getIndex();
577                     vFollow[j].addAll(first(itW.suffix()));
578                 }
579             }
580         }
581
582         boolean changed;
583         do {
584             changed = false;
585             for (int i = 0; i<v.count(); i++) {
586                 List prodList = p.find(v.find(i));
587                 Iterator itL = prodList.iterator();
588                 while (itL.hasNext()) {
589                     Production prod = (Production)itL.next();
590                     Word w = prod.getRHS();
591                     WordIterator itW = w.iterator();
592                     while (itW.hasNextNonTerminal()) {
593                         int j = itW.nextNonTerminal().getIndex();
594                         if (nullable(itW.suffix())) {
595                             if (vFollow[j].addAll(vFollow[i])) {
596                                 changed = true;
597                             }
598                         }
599                     }
600                 }
601             }
602         } while (changed);
603     }
604
605     public Set follow(NonTerminal var) {
606         return vFollow[var.getIndex()];
607     }
608
609     public String toString() {
610         StringBuffer sb = new StringBuffer ();
611         sb.append("nonterminal "+v+";\n");
612         sb.append("terminal "+t+";\n");
613         sb.append("start with "+s+";\n");
614         sb.append(p);
615         return sb.toString();
616     }
617
618     public void printNullable() {
619         if (vNullable != null) {
620             System.out.println("nullable: ");
621             Iterator itV = v.iterator();
622             while (itV.hasNext()) {
623                 NonTerminal a = (NonTerminal)itV.next();
624                 if (vNullable.contains(a)) {
625                     System.out.println(a);
626                 }
627             }
628         } else {
629             System.out.println("nullability unknown");
630         }
631         if (pNullable != null) {
632             System.out.println("nullable productions: ");
633             Iterator itP = p.iterator();
634             while (itP.hasNext()) {
635                 Production prod = (Production)itP.next();
636                 if (pNullable.contains(prod)) {
637                     System.out.println(prod);
638                 }
639             }
640         } else {
641             System.out.println("nullability of productions unknown");
642         }
643     }
644
645     public void printFirst() {
646         if (vFirst != null) {
647             for (int i = 0; i<v.count(); i++) {
648                 System.out.print("first("+v.find(i).getName()+")={");
649                 Iterator it = t.iterator();
650                 while (it.hasNext()) {
651                     Terminal term = (Terminal)it.next();
652                     if (vFirst[i].contains(term)) {
653                         System.out.print(term+", ");
654                     }
655                 }
656                 System.out.println("}");
657             }
658         }
659         if (pFirst != null) {
660             for (int i = 0; i<p.count(); i++) {
661                 System.out.print("first("+p.find(i).getRHS()+")={");
662                 Iterator it = t.iterator();
663                 while (it.hasNext()) {
664                     Terminal term = (Terminal)it.next();
665                     if (pFirst[i].contains(term)) {
666                         System.out.print(term+", ");
667                     }
668                 }
669                 System.out.println("}");
670             }
671         }
672     }
673
674     public void printFollow() {
675         if (vFollow != null) {
676             for (int i = 0; i<v.count(); i++) {
677                 System.out.print("follow("+v.find(i).getName()+")={");
678                 Iterator it = t.iterator();
679                 while (it.hasNext()) {
680                     Terminal term = (Terminal)it.next();
681                     if (vFollow[i].contains(term)) {
682                         System.out.print(term+", ");
683                     }
684                 }
685                 System.out.println("}");
686             }
687         }
688     }
689
690     public boolean isInvertible() {
691         return p.isInvertible();
692     }
693 }
694
695

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags