001    /*
002    // $Id: Grammar.java 3 2009-05-11 08:11:57Z jhyde $
003    // Clapham generates railroad diagrams to represent computer language grammars.
004    // Copyright (C) 2008-2009 Julian Hyde
005    // Copyright (c) 2005 Stefan Schoergenhumer, Markus Dopler
006    //
007    // This program is free software; you can redistribute it and/or modify it
008    // under the terms of the GNU General Public License as published by the Free
009    // Software Foundation; either version 2 of the License, or (at your option)
010    // any later version approved by The Eigenbase Project.
011    //
012    // This program is distributed in the hope that it will be useful,
013    // but WITHOUT ANY WARRANTY; without even the implied warranty of
014    // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
015    // GNU General Public License for more details.
016    //
017    // You should have received a copy of the GNU General Public License
018    // along with this program; if not, write to the Free Software
019    // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
020    */
021    package net.hydromatic.clapham.graph;
022    
023    import java.util.*;
024    import java.util.List;
025    import java.io.PrintStream;
026    
027    /**
028     * TODO:
029    *
030    * @author jhyde
031    * @version $Id: Grammar.java 3 2009-05-11 08:11:57Z jhyde $
032    * @since Aug 26, 2008
033    */
034    public class Grammar {
035        public final Map<String,Symbol> symbolMap = new HashMap<String, Symbol>();
036        public final Map<Symbol, Graph> ruleMap = new HashMap<Symbol, Graph>();
037        final List<Node> nodes = new ArrayList<Node>();
038    
039        public static boolean TRACE = false;
040    
041        // enable optimizations?
042        private boolean optimizeGraph = true;
043    
044        public final List<Symbol> terminals = new ArrayList<Symbol>();
045        public final List<Symbol> nonterminals = new ArrayList<Symbol>();
046    
047        private static int ptr(Node p, boolean up) {
048            if (p == null) {
049                return 0;
050            } else if (up) {
051                return -p.n;
052            } else {
053                return p.n;
054            }
055        }
056    
057        public void setOptimizeGraph(boolean value) {
058            this.optimizeGraph = value;
059        }
060    
061        public boolean setOptimizeGraph() {
062            return optimizeGraph;
063        }
064    
065        boolean compare(Node n1, Node n2) {
066            if (n1.typ == n2.typ) {
067                if (n1.typ == NodeType.NONTERM || n1.typ == NodeType.TERM) {
068                    if (!n1.sym.name.equals(n2.sym.name)) {
069                        return false;
070                    }
071                }
072                return true;
073            }
074            return false;
075        }
076    
077        boolean deepCompare(Node n1, Node n2, boolean untilIter) {
078            boolean samelevel = true;
079            Node identifier = n2; // helps to identify the relevant iter node
080            while (n1 != null && samelevel) {
081                //just compare nodes until the iter node
082                if (untilIter) {
083                    if (n1.typ == NodeType.ITER && n1.sub == identifier) {
084                        if (n1 == n2) { //last iter node's next points to the iter
085                            if (TRACE) {
086                                System.out.println(
087                                        "true: iter node reached, graphs match");
088                            }
089                            return true;
090                        } else {
091                            if (TRACE) {
092                                System.out.println(
093                                    "false: iter node reached, graphs do not match");
094                            }
095                            return false;
096                        }
097                    }
098                }
099                if (n2 == null) {
100                    if (TRACE) {
101                        System.out.println(
102                            "false: second enclosing substructure ended before first");
103                    }
104                    return false;
105                }
106                if (!compare(n1, n2)) {
107                    if (TRACE) {
108                        System.out.println("false: node not same type/content");
109                    }
110                    return false;
111                }
112                //--> t,nt,eps is ok, go to next
113    
114                if (n1.typ == NodeType.OPT
115                    || n1.typ == NodeType.ITER
116                    || n1.typ == NodeType.RERUN) {
117                    if (!deepCompare(n1.sub, n2.sub, false)) {
118                        if (TRACE) {
119                            System.out
120                                .println(
121                                    "false: false in subelem of iter,opt or rerun");
122                        }
123                        return false;
124                    }
125                    if (n1.typ == NodeType.RERUN
126                        && !deepCompare(n1.itergraph, n2.itergraph, false)) {
127                        if (TRACE) {
128                            System.out.println(
129                                "false: itergraph of rerun doesn't match");
130                        }
131                        return false;
132                    }
133                } else if (n1.typ == NodeType.ALT) {
134                    Node a1 = n1;
135                    Node a2 = n2;
136                    while (a1 != null) {
137                        if (a2 == null) {
138                            if (TRACE) {
139                                System.out
140                                    .println(
141                                        "false: false in subalt, second node null");
142                            }
143                            return false;
144                        }
145    
146                        if (!deepCompare(a1.sub, a2.sub, false)) {
147                            if (TRACE) {
148                                System.out
149                                    .println("false: false in subelem of subalt");
150                            }
151                            return false;
152                        }
153                        a1 = a1.down;
154                        a2 = a2.down;
155                    }
156                    if (a2 != null) {
157                        if (TRACE) {
158                            System.out
159                                .println("false: second alt has more alternatives");
160                        }
161                        return false;
162                    }
163                }
164                if (n1.up) {
165                    if (!n2.up) {
166                        if (TRACE) {
167                            System.out.println(
168                                "false: second has not finished enclosing structure");
169                        }
170                        return false;
171                    }
172                    samelevel = false;
173                }
174                n1 = n1.next;
175                n2 = n2.next;
176            }
177            if (n1 == null && n2 != null) {
178                if (TRACE) {
179                    System.out.println(
180                        "false: first enclosing substructure ended before second");
181                }
182                return false;
183            }
184            return true;
185        }
186    
187        /** calls all methods which optimize the graphs */
188        public void optimize() {
189            for (Symbol s : nonterminals) {
190                removeWrongLinebreaks(s.graph.l, null, s);
191                if (optimizeGraph) {
192                    //remove redundant iter/opts
193                    removeRedundancy(s.graph.l, null, s);
194                }
195                if (optimizeGraph) {
196                    //remove eps nodes and redundant eps nodes in alternatives
197                    removeEps(s.graph.l, null, s);
198                }
199                if (optimizeGraph) {
200                    optimizeIter(s.graph.l, null, s);
201                }
202            }
203        }
204    
205        /**
206         * Removes all unnecessary and wrong linebreaks (wrap-nodes) from the
207         * graph.
208         */
209        void removeWrongLinebreaks(Node n, Node parent, Symbol s) {
210            boolean samelevel = true;
211            Node i = n;
212            while (i != null && samelevel) {
213                if (i.typ == NodeType.WRAP) {
214                    //if in outer structure, just remove multiple wraps
215                    if (parent == null) {
216                        while (i.next != null && i.next.typ == NodeType.WRAP) {
217                            i.next = i.next.next;
218                        }
219                    } //if in inner structure remove it
220                    else {
221                        //if \n is first element of substructure
222                        if (n == i) {
223                            //parent==null doesn't occur
224    
225                            //if \n is the only subelement
226                            if (i.up || i.next == null) {
227                                Node eps = new Node(this, NodeType.EPS, null);
228                                parent.sub = eps;
229                                eps.up = i.up;
230                                eps.next = i.next;
231                                n = eps;
232                            } else {
233                                parent.sub = i.next;
234                                n = parent.sub;
235                            }
236                        } else { //if within substructure
237                            Node j = n;
238                            while (j.next != i) {
239                                j = j.next;
240                            }
241                            j.next = i.next;
242                            j.up = i.up;
243                        }
244                    }
245                } else if (i.typ == NodeType.OPT
246                    || i.typ == NodeType.ITER
247                    || i.typ == NodeType
248                    .RERUN) {
249                    removeWrongLinebreaks(i.sub, i, s);
250                } else if (i.typ == NodeType.ALT) {
251                    Node a = i;
252                    while (a != null) {
253                        removeWrongLinebreaks(a.sub, a, s);
254                        a = a.down;
255                    }
256                }
257    
258                if (i.up) {
259                    samelevel = false;
260                }
261                i = i.next;
262            }
263        }
264    
265        void removeRedundancy(Node n, Node parent, Symbol s) {
266            boolean samelevel = true;        //next node in same level?
267            Node begin = n;
268            while (n != null && samelevel) {
269                if (n.typ == NodeType.ALT) {
270                    Node a = n;
271                    while (a != null) {
272                        removeRedundancy(a.sub, a, s);
273                        a = a.down;
274                    }
275                } else if (n.typ == NodeType.ITER) {
276                    while ((n.sub.typ == NodeType.ITER
277                        || n.sub.typ == NodeType.OPT) && n.sub.up) {
278                        //EbnfForm.WriteLine("Rendundant "+Node.nTyp[n.sub.typ]+" Node removed (iter).");
279                        n.sub = n.sub.sub;
280                        Node i = n.sub;
281                        while (!i.up) {
282                            i = i.next;
283                        }
284                        i.next = n;
285                    }
286                    removeRedundancy(n.sub, n, s);
287                } else if (n.typ == NodeType.OPT) {
288                    boolean containsIter = false;
289                    while ((n.sub.typ == NodeType.OPT
290                        && (n.sub.up || n.sub.next == null))
291                        || (n.sub.typ == NodeType.ITER
292                        && (n.sub.up || n.sub.next == null))) {
293                        //if(n.sub.typ==Node.opt || containsIter) EbnfForm.WriteLine("Rendundant "+Node.nTyp[n.sub.typ]+" Node removed (opt).");
294                        if (n.sub.typ == NodeType.ITER) {
295                            containsIter = true;
296                        }
297                        n.sub = n.sub.sub;
298                    }
299                    if (containsIter) {
300                        Node iter = new Node(this, NodeType.ITER, n.sub);
301                        iter.next = n.next;
302                        if (n == begin) {
303                            if (parent == null) {
304                                s.graph.l = iter;
305                            } else {
306                                parent.sub = iter;
307                            }
308                        } else {
309                            Node j = begin;
310                            while (j.next != n) {
311                                j = j.next;
312                            }
313                            j.next = iter;
314                        }
315                        n = iter;
316    
317                        //set correct next pointer of last subelement of new iter
318                        Node i = iter.sub;
319                        while (i.next != null && !i.up) {
320                            i = i.next;
321                        }
322                        i.next = iter;
323                    }
324                    removeRedundancy(n.sub, n, s);
325                }
326                if (n.up) {
327                    samelevel = false;
328                }
329                n = n.next;
330            }
331        }
332    
333        /**
334         * Removes all empty ('epsilon') iter/opt nodes in alternatives, as well as
335         * multiple epsilon nodes at the beginning.
336         */
337        void removeEps(Node n, Node parent, Symbol s) {
338            boolean samelevel = true;        //next node in same level?
339            Node begin = n;
340            while (n != null && samelevel) {
341    
342                if (n.typ == NodeType.EPS) {
343                    if (n == begin) {
344                        if (parent == null) {
345                            //if the graph only consists of an eps, let it live
346                            if (n.next != null) {
347                                s.graph.l = n.next;
348                                begin = n.next;
349                            }
350                        } //else: at beginning of substructure not required (iter/opt/alt subnodes were already handled)
351                    } else {
352                        Node i = begin;
353                        while (i.next != n) {
354                            i = i.next;
355                        }
356                        i.next = n.next;
357                        i.up = n.up;
358                    }
359                } else if (n.typ == NodeType.ITER || n.typ == NodeType.OPT) {
360                    if (n.sub.typ == NodeType.EPS
361                        && (n.sub.next == null
362                        || n.sub.up)) {
363                        if (n == begin) {
364                            if (parent == null) { //beginning of graph
365                                //if graph only consists of this iter/opt, then replace it with an eps node
366                                if (n.next == null) {
367                                    Node eps = new Node(this, NodeType.EPS, null);
368                                    s.graph.l = eps;
369                                    s.graph.r = eps;
370                                } else { //remove that node
371                                    s.graph.l = n.next;
372                                    begin = n.next;
373                                }
374                            } //else: at beginning of substructure not required (iter/opt/alt subnodes were already handled)
375                        } else { //within substructure
376                            Node i = begin;
377                            while (i.next != n) {
378                                i = i.next;
379                            }
380                            if (n.up) {
381                                i.up = true;
382                            }
383                            i.next = n.next;
384                        }
385                    } else {
386                        removeEps(n.sub, n, s);
387                    }
388                } else if (n.typ == NodeType.ALT) {
389                    Node a = n;
390                    //count number of eps
391                    int numOfEps = 0;
392                    while (a != null) {
393                        //checkSubAlts(a);
394                        if (a.sub.typ == NodeType.EPS
395                            && (a.sub.next == null
396                            || a.sub.up)) {
397                            numOfEps++;
398                        }
399                        a = a.down;
400                    }
401                    a = n;
402                    while (numOfEps > 1) {
403                        if (n != a && a.sub.typ == NodeType.EPS && (a.sub
404                            .next
405                            == null || a.sub.up)) {
406                            Node i = n;
407                            while (i.down != a) {
408                                i = i.down;
409                            }
410                            i.down = a.down;
411                            numOfEps--;
412                        }
413                        a = a.down;
414                    }
415                    removeSameAlts(n);
416                    putEpsAtBeginningOfAlt(begin, n, parent, s);
417                    //optimize subcomponents
418                    a = n;
419                    while (a != null) {
420                        //if not the left eps node
421                        if (!(a.sub.typ == NodeType.EPS
422                            && (a.sub.next == null
423                            || a.sub.up))) {
424                            removeEps(a.sub, a, s);
425                        }
426                        a = a.down;
427                    }
428                }
429                if (n.up) {
430                    samelevel = false;
431                }
432                n = n.next;
433            }
434        }
435    
436        //they would bug a condition in removeEps
437        public void checkSubAlts(Node alt)  {
438    
439            //remove all empty iter/opts
440            //make sure, that at least one eps Node will exist
441            Node eps = new Node(this, NodeType.EPS, null);
442            eps.next = alt.sub;
443            alt.sub = eps;
444            Node i = alt.sub;
445            boolean samelevel = true;
446            while (i != null && samelevel) {
447                //if empty iter/opt
448                if ((i.typ == NodeType.ITER
449                    || i.typ == NodeType.OPT)
450                    && i.sub.typ == NodeType.EPS
451                    && (i.sub.next == null
452                    || i.sub.up)) {
453                    //case i==alt.sub not possible
454                    Node a = alt.sub;
455                    while (a.next != i) {
456                        a = a.next;
457                    }
458                    a.next = i.next;
459                }
460                if (i.up) {
461                    samelevel = false;
462                }
463                i = i.next;
464            }
465    
466            i = alt.sub;
467            //remove multiple eps nodes at the beginning
468            if (i.typ == NodeType.EPS) {
469                while (i.next != null
470                    && !i.next.up
471                    && i.next.typ == NodeType.EPS) {
472                    i.next = i.next.next;
473                }
474            }
475        }
476    
477        void removeSameAlts(Node alt)       {
478            Node a = alt;
479            while (a != null) {
480                Node i = a.down;
481                while (i != null) {
482                    if (deepCompare(a.sub, i.sub, false)) {
483                        Node n = a;
484                        while (n.down != i) {
485                            n = n.down;
486                        }
487                        n.down = i.down;
488                    }
489                    i = i.down;
490                }
491                a = a.down;
492            }
493        }
494    
495        void putEpsAtBeginningOfAlt(Node n, Node alt, Node parent, Symbol s) {
496            Node a = alt;
497            boolean containsEps = false;
498    
499            //determine if eps is contained
500            while (a != null) {
501                //if eps node
502                if (a.sub.typ == NodeType.EPS &&
503                    (a.sub.next == null
504                    || a.sub.up)) {
505                    containsEps = true;
506                }
507                a = a.down;
508            }
509            if (containsEps) {
510                //remove eps node
511                a = alt;
512                while (a != null) {
513                    //if eps node
514                    if (a.sub.typ == NodeType.EPS && (a.sub.next == null
515                        || a.sub
516                        .up)) {
517                        //remove eps only if within alternatives
518                        if (a != alt) {
519                            Node i = alt;
520                            while (i.down != a) {
521                                i = i.down;
522                            }
523                            i.down = a.down;
524                        }
525                        break; //there can be only one eps in the alts because same nodes have already been removed
526                    }
527                    a = a.down;
528                }
529                //insert eps, if first alt isn't eps
530    
531                if (!(alt.sub.typ == NodeType.EPS
532                    && (alt.sub.next == null || alt.sub.up))) {
533                    Node eps = new Node(this, NodeType.EPS, null);
534                    eps.next = alt.next;
535                    eps.up = true;
536                    AltNode a1 = new AltNode(this, eps);
537                    a1.down = alt;
538                    if (alt == n) {
539                        if (parent == null) {
540                            s.graph.l = a1;
541                        } else {
542                            parent.sub = a1;
543                        }
544                    } else {
545                        Node i = n;
546                        while (i.next != alt) {
547                            i = i.next;
548                        }
549                        i.next = a1;
550                    }
551                    a1.next = alt.next;
552                    a1.up = alt.up;
553                    alt.next = null;
554                }
555            }
556        }
557    
558        //optimizes enclosing structures and recursively its substructures
559        void optimizeIter(Node n, Node parent, Symbol s) {
560            boolean samelevel = true;        //next node in same level?
561            Node i = n;
562    
563            while (i != null && samelevel) {
564                if (i.typ == NodeType.OPT) {
565                    optimizeIter(i.sub, i, s);
566                } else if (i.typ == NodeType.ALT) {
567                    Node a = i;
568                    while (a != null) {
569                        optimizeIter(a.sub, a, s);
570                        a = a.down;
571                    }
572                } else if (i.typ == NodeType.ITER) {
573                    //first optimize the iter substructure
574                    optimizeIter(i.sub, i, s);
575    
576                    //while loop to deepCompare from every node until the iter node
577                    Node j = n;
578                    boolean matchFound = false;
579                    while (j != i && !matchFound) {
580                        Node k = i.sub;
581                        boolean samelevel2 = true;
582                        while (k != null && samelevel2 && !matchFound) {
583                            if (deepCompare(j, k, true)) {
584                                //EbnfForm.WriteLine("Iter node optimized.");
585                                matchFound = true;
586                                //replace the iter node and the nodes before by the rerun node
587                                Node re = new Node(this, NodeType.RERUN, k);
588                                if (j == n) {
589    
590                                    if (parent == null) {
591                                        s.graph.l = re;
592                                        n = re;
593                                    } else {
594                                        parent.sub = re;
595                                        n = re;
596                                    }
597                                } else {
598                                    Node l = n;
599                                    while (l.next != j) {
600                                        l = l.next;
601                                    }
602                                    l.next = re;
603                                }
604    
605                                //if a {b a} isolate b
606                                if (k != i.sub) {
607                                    re.itergraph = i.sub;
608                                    Node temp = re.itergraph;
609                                    while (temp.next != k) {
610                                        temp = temp.next;
611                                    }
612                                    temp.next = null;
613                                }
614    
615                                re.next = i.next;
616                                re.up = i.up;
617                                i = re;
618                            }
619                            if (k.up) {
620                                samelevel2 = false;
621                            }
622                            k = k.next;
623                        }
624    
625                        j = j.next;
626                    }
627                }
628                if (i.up) {
629                    samelevel = false;
630                }
631                i = i.next;
632            }
633        }
634    
635        public void makeEpsilon(Graph g) {
636            g.l = new Node(this, NodeType.EPS, null);
637            g.r = g.l;
638        }
639    
640        public void makeFirstAlt(Graph g) {
641            g.l = new AltNode(this, g.l);
642    //        g.l.next = g.r;
643            g.r = g.l;
644        }
645    
646        public void makeAlternative(Graph g1, Graph g2) {
647            g2.l = new AltNode(this, g2.l);
648            Node p = g1.l;
649            while (p.down != null) {
650                p = p.down;
651            }
652            p.down = g2.l;
653            p = g1.r;
654            while (p.next != null) {
655                p = p.next;
656            }
657    //        p.next = g2.r;
658        }
659    
660        public void makeSequence(Graph g1, Graph g2) {
661            if (g1.l == null && g1.r == null) {/*case: g1 is empty */
662                g1.l = g2.l;
663                g1.r = g2.r;
664            } else {
665                Node p = g1.r.next;
666                g1.r.next = g2.l; // link head node
667                while (p != null) {  // link substructure
668                    Node q = p.next;
669                    p.next = g2.l;
670                    p.up = true;
671                    p = q;
672                }
673                g1.r = g2.r;
674            }
675        }
676    
677        public void makeIteration(Graph g) {
678            g.l = new Node(this, NodeType.ITER, g.l);
679            Node p = g.r;
680            g.r = g.l;
681            while (p != null) {
682                Node q = p.next;
683                p.next = g.l;
684                p.up = true;
685                p = q;
686            }
687        }
688    
689        public void makeOption(Graph g) {
690            g.l = new Node(this, NodeType.OPT, g.l);
691            g.l.next = g.r;
692            g.r = g.l;
693        }
694    
695        public enum Direction {
696            LEFT,
697            RIGHT,
698            UP,
699            DOWN
700        }
701    
702        /**
703         * Finds a terminal or non-terminal with a given name.
704         *
705         * @param name Name of symbol
706         * @return terminal or non-terminal
707         */
708        public Node find(String name) {
709            for (Node n : nodes) {
710                if (n.sym != null && n.sym.name.equals(name)) {
711                    return n;
712                }
713            }
714            return null;
715        }
716    
717        /**
718         * Converts the terminal with a given name to a non-terminal.
719         *
720         * @param name Name of non-terminal.
721         */
722        public void terminalToNt(String name) {
723            for (Node n : nodes) {
724                if (n.sym != null && n.sym.name.equals(name)) {
725                    n.typ = NodeType.NONTERM;
726                }
727            }
728            for (Symbol s : terminals) {
729                if (s.name.equals(name)) {
730                    nonterminals.add(s);
731                    terminals.remove(s);
732                    break;
733                }
734            }
735        }
736    
737        public void printNodes(PrintStream out) {
738            out.println("Graph nodes:");
739            out.println("(S...Starting nodes)");
740            out.println("--------------------------------------------");
741            out.println("S   n type name          next  down   sub   ");
742            out.println("--------------------------------------------");
743    
744            for (Node p : nodes) {
745                boolean nt = false;
746                for (Symbol s : nonterminals) {
747                    if (s.graph.l.n == p.n) {
748                        out.print("*");
749                        nt = true;
750                    }
751                }
752                if (!nt) {
753                    out.print(" ");
754                }
755    
756                out.format("%1$-4s %2$-4s ", p.n, p.typ.name());
757    
758                if (p.sym != null) {
759                    out.format("%1$-12s ", p.sym.name);
760                } else {
761                    out.print("             ");
762                }
763    
764                out.format("%1$5s ", Grammar.ptr(p.next, p.up));
765    
766                switch (p.typ) {
767                case ALT:
768                case ITER:
769                case OPT:
770                case RERUN:
771                    out.format(
772                        "%1$5d %2$5d",
773                        Grammar.ptr(p.down, false),
774                        Grammar.ptr(p.sub, false));
775                    break;
776                case EPS:
777                    out.print("           ");
778                    break;
779                }
780                out.println();
781            }
782            out.println();
783    
784            for (Symbol symbol : symbolMap.values()) {
785                final StringBuffer buf = new StringBuffer();
786                out.println(symbol.name + " ::=");
787                symbol.graph.l.unparse(buf);
788                out.println("  " + buf);
789            }
790            out.println();
791        }
792    
793        // starts to draw the rule at the given symbol s
794    
795        /*
796             * compare two graphs on the basis of structure and value
797         * if untilIter is set, n1 and n2 are treated in a different way:
798         * the graph n1 to the iter node is compared to the iter subnode
799         * params: n1 must be the node before iter if untilIter==true
800         * params: n2 must be the first subnode of iter if untilIter==true
801         */
802    }
803    
804    // End Grammar.java