BaseAST


1   package antlr;
2   
3   /* ANTLR Translator Generator
4    * Project led by Terence Parr at http://www.jGuru.com
5    * Software rights: http://www.antlr.org/RIGHTS.html
6    *
7    * $Id: //depot/code/org.antlr/main/main/antlr/BaseAST.java#6 $
8    */
9   
10  import antlr.collections.AST;
11  import antlr.collections.ASTEnumeration;
12  import antlr.collections.impl.ASTEnumerator;
13  import antlr.collections.impl.Vector;
14  
15  import java.io.Serializable  ;
16  import java.io.IOException  ;
17  import java.io.Writer  ;
18  
19  /**
20   * A Child-Sibling Tree.
21   *
22   * A tree with PLUS at the root and with two children 3 and 4 is
23   * structured as:
24   *
25   *      PLUS
26   *        |
27   *        3 -- 4
28   *
29   * and can be specified easily in LISP notation as
30   *
31   * (PLUS 3 4)
32   *
33   * where every '(' starts a new subtree.
34   *
35   * These trees are particular useful for translators because of
36   * the flexibility of the children lists.  They are also very easy
37   * to walk automatically, whereas trees with specific children
38   * reference fields can't easily be walked automatically.
39   *
40   * This class contains the basic support for an AST.
41   * Most people will create ASTs that are subclasses of
42   * BaseAST or of CommonAST.
43   */
44  public abstract class BaseAST implements AST, Serializable   {
45      protected BaseAST down;
46      protected BaseAST right;
47  
48      private static boolean verboseStringConversion = false;
49      private static String  [] tokenNames = null;
50  
51      /**Add a node to the end of the child list for this node */
52      public void addChild(AST node) {
53          if (node == null) return;
54          BaseAST t = this.down;
55          if (t != null) {
56              while (t.right != null) {
57                  t = t.right;
58              }
59              t.right = (BaseAST)node;
60          }
61          else {
62              this.down = (BaseAST)node;
63          }
64      }
65  
66      private void doWorkForFindAll(Vector v, AST target, boolean partialMatch) {
67          AST sibling;
68  
69          // Start walking sibling lists, looking for matches.
70          siblingWalk:
71          for (sibling = this;
72               sibling != null;
73               sibling = sibling.getNextSibling()) {
74              if ((partialMatch && sibling.equalsTreePartial(target)) ||
75                  (!partialMatch && sibling.equalsTree(target))) {
76                  v.appendElement(sibling);
77              }
78              // regardless of match or not, check any children for matches
79              if (sibling.getFirstChild() != null) {
80                  ((BaseAST)sibling.getFirstChild()).doWorkForFindAll(v, target, partialMatch);
81              }
82          }
83      }
84  
85      /** Is node t equal to this in terms of token type and text? */
86      public boolean equals(AST t) {
87          if (t == null) return false;
88          return this.getText().equals(t.getText()) &&
89              this.getType() == t.getType();
90      }
91  
92      /** Is t an exact structural and equals() match of this tree.  The
93       *  'this' reference is considered the start of a sibling list.
94       */
95      public boolean equalsList(AST t) {
96          AST sibling;
97  
98          // the empty tree is not a match of any non-null tree.
99          if (t == null) {
100             return false;
101         }
102 
103         // Otherwise, start walking sibling lists.  First mismatch, return false.
104         for (sibling = this; sibling != null && t != null; sibling = sibling.getNextSibling(), t = t.getNextSibling()) {
105             // as a quick optimization, check roots first.
106             if (!sibling.equals(t)) {
107                 return false;
108             }
109             // if roots match, do full list match test on children.
110             if (sibling.getFirstChild() != null) {
111                 if (!sibling.getFirstChild().equalsList(t.getFirstChild())) {
112                     return false;
113                 }
114             }
115             // sibling has no kids, make sure t doesn't either
116             else if (t.getFirstChild() != null) {
117                 return false;
118             }
119         }
120         if (sibling == null && t == null) {
121             return true;
122         }
123         // one sibling list has more than the other
124         return false;
125     }
126 
127     /** Is 'sub' a subtree of this list?
128      *  The siblings of the root are NOT ignored.
129      */
130     public boolean equalsListPartial(AST sub) {
131         AST sibling;
132 
133         // the empty tree is always a subset of any tree.
134         if (sub == null) {
135             return true;
136         }
137 
138         // Otherwise, start walking sibling lists.  First mismatch, return false.
139         for (sibling = this;
140              sibling != null && sub != null;
141              sibling = sibling.getNextSibling(), sub = sub.getNextSibling()) {
142             // as a quick optimization, check roots first.
143             if (!sibling.equals(sub)) return false;
144             // if roots match, do partial list match test on children.
145             if (sibling.getFirstChild() != null) {
146                 if (!sibling.getFirstChild().equalsListPartial(sub.getFirstChild())) return false;
147             }
148         }
149         if (sibling == null && sub != null) {
150             // nothing left to match in this tree, but subtree has more
151             return false;
152         }
153         // either both are null or sibling has more, but subtree doesn't
154         return true;
155     }
156 
157     /** Is tree rooted at 'this' equal to 't'?  The siblings
158      *  of 'this' are ignored.
159      */
160     public boolean equalsTree(AST t) {
161         // check roots first.
162         if (!this.equals(t)) return false;
163         // if roots match, do full list match test on children.
164         if (this.getFirstChild() != null) {
165             if (!this.getFirstChild().equalsList(t.getFirstChild())) return false;
166         }
167         // sibling has no kids, make sure t doesn't either
168         else if (t.getFirstChild() != null) {
169             return false;
170         }
171         return true;
172     }
173 
174     /** Is 't' a subtree of the tree rooted at 'this'?  The siblings
175      *  of 'this' are ignored.
176      */
177     public boolean equalsTreePartial(AST sub) {
178         // the empty tree is always a subset of any tree.
179         if (sub == null) {
180             return true;
181         }
182 
183         // check roots first.
184         if (!this.equals(sub)) return false;
185         // if roots match, do full list partial match test on children.
186         if (this.getFirstChild() != null) {
187             if (!this.getFirstChild().equalsListPartial(sub.getFirstChild())) return false;
188         }
189         return true;
190     }
191 
192     /** Walk the tree looking for all exact subtree matches.  Return
193      *  an ASTEnumerator that lets the caller walk the list
194      *  of subtree roots found herein.
195      */
196     public ASTEnumeration findAll(AST target) {
197         Vector roots = new Vector(10);
198         AST sibling;
199 
200         // the empty tree cannot result in an enumeration
201         if (target == null) {
202             return null;
203         }
204 
205         doWorkForFindAll(roots, target, false);  // find all matches recursively
206 
207         return new ASTEnumerator(roots);
208     }
209 
210     /** Walk the tree looking for all subtrees.  Return
211      *  an ASTEnumerator that lets the caller walk the list
212      *  of subtree roots found herein.
213      */
214     public ASTEnumeration findAllPartial(AST sub) {
215         Vector roots = new Vector(10);
216         AST sibling;
217 
218         // the empty tree cannot result in an enumeration
219         if (sub == null) {
220             return null;
221         }
222 
223         doWorkForFindAll(roots, sub, true);  // find all matches recursively
224 
225         return new ASTEnumerator(roots);
226     }
227 
228     /** Get the first child of this node; null if not children */
229     public AST getFirstChild() {
230         return down;
231     }
232 
233     /** Get the next sibling in line after this one */
234     public AST getNextSibling() {
235         return right;
236     }
237 
238     /** Get the token text for this node */
239     public String   getText() {
240         return "";
241     }
242 
243     /** Get the token type for this node */
244     public int getType() {
245         return 0;
246     }
247 
248     public abstract void initialize(int t, String   txt);
249 
250     public abstract void initialize(AST t);
251 
252     public abstract void initialize(Token t);
253 
254     /** Remove all children */
255     public void removeChildren() {
256         down = null;
257     }
258 
259     public void setFirstChild(AST c) {
260         down = (BaseAST)c;
261     }
262 
263     public void setNextSibling(AST n) {
264         right = (BaseAST)n;
265     }
266 
267     /** Set the token text for this node */
268     public void setText(String   text) {
269     }
270 
271     /** Set the token type for this node */
272     public void setType(int ttype) {
273     }
274 
275     public static void setVerboseStringConversion(boolean verbose, String  [] names) {
276         verboseStringConversion = verbose;
277         tokenNames = names;
278     }
279 
280     public String   toString() {
281         StringBuffer   b = new StringBuffer  ();
282         // if verbose and type name not same as text (keyword probably)
283         if (verboseStringConversion &&
284             !getText().equalsIgnoreCase(tokenNames[getType()]) &&
285             !getText().equalsIgnoreCase(StringUtils.stripFrontBack(tokenNames[getType()], "\"", "\""))) {
286             b.append('[');
287             b.append(getText());
288             b.append(",<");
289             b.append(tokenNames[getType()]);
290             b.append(">]");
291             return b.toString();
292         }
293         return getText();
294     }
295 
296     /** Print out a child-sibling tree in LISP notation */
297     public String   toStringList() {
298         AST t = this;
299         String   ts = "";
300         if (t.getFirstChild() != null) ts += " (";
301         ts += " " + this.toString();
302         if (t.getFirstChild() != null) {
303             ts += ((BaseAST)t.getFirstChild()).toStringList();
304         }
305         if (t.getFirstChild() != null) ts += " )";
306         if (t.getNextSibling() != null) {
307             ts += ((BaseAST)t.getNextSibling()).toStringList();
308         }
309         return ts;
310     }
311 
312     public String   toStringTree() {
313         AST t = this;
314         String   ts = "";
315         if (t.getFirstChild() != null) ts += " (";
316         ts += " " + this.toString();
317         if (t.getFirstChild() != null) {
318             ts += ((BaseAST)t.getFirstChild()).toStringList();
319         }
320         if (t.getFirstChild() != null) ts += " )";
321         return ts;
322     }
323 
324     public static String   decode(String   text) {
325         char c, c1, c2, c3, c4, c5;
326         StringBuffer   n = new StringBuffer  ();
327         for (int i = 0; i < text.length(); i++) {
328             c = text.charAt(i);
329             if (c == '&') {
330                 c1 = text.charAt(i + 1);
331                 c2 = text.charAt(i + 2);
332                 c3 = text.charAt(i + 3);
333                 c4 = text.charAt(i + 4);
334                 c5 = text.charAt(i + 5);
335 
336                 if (c1 == 'a' && c2 == 'm' && c3 == 'p' && c4 == ';') {
337                     n.append("&");
338                     i += 5;
339                 }
340                 else if (c1 == 'l' && c2 == 't' && c3 == ';') {
341                     n.append("<");
342                     i += 4;
343                 }
344                 else if (c1 == 'g' && c2 == 't' && c3 == ';') {
345                     n.append(">");
346                     i += 4;
347                 }
348                 else if (c1 == 'q' && c2 == 'u' && c3 == 'o' &&
349                     c4 == 't' && c5 == ';') {
350                     n.append("\"");
351                     i += 6;
352                 }
353                 else if (c1 == 'a' && c2 == 'p' && c3 == 'o' &&
354                     c4 == 's' && c5 == ';') {
355                     n.append("'");
356                     i += 6;
357                 }
358                 else
359                     n.append("&");
360             }
361             else
362                 n.append(c);
363         }
364         return new String  (n);
365     }
366 
367     public static String   encode(String   text) {
368         char c;
369         StringBuffer   n = new StringBuffer  ();
370         for (int i = 0; i < text.length(); i++) {
371             c = text.charAt(i);
372             switch (c) {
373                 case '&':
374                     {
375                         n.append("&amp;");
376                         break;
377                     }
378                 case '<':
379                     {
380                         n.append("&lt;");
381                         break;
382                     }
383                 case '>':
384                     {
385                         n.append("&gt;");
386                         break;
387                     }
388                 case '"':
389                     {
390                         n.append("&quot;");
391                         break;
392                     }
393                 case '\'':
394                     {
395                         n.append("&apos;");
396                         break;
397                     }
398                 default :
399                     {
400                         n.append(c);
401                         break;
402                     }
403             }
404         }
405         return new String  (n);
406     }
407 
408     public void xmlSerializeNode(Writer   out)
409         throws IOException   {
410         StringBuffer   buf = new StringBuffer  (100);
411         buf.append("<");
412         buf.append(getClass().getName() + " ");
413         buf.append("text=\"" + encode(getText()) + "\" type=\"" +
414                    getType() + "\"/>");
415         out.write(buf.toString());
416     }
417 
418     public void xmlSerializeRootOpen(Writer   out)
419         throws IOException   {
420         StringBuffer   buf = new StringBuffer  (100);
421         buf.append("<");
422         buf.append(getClass().getName() + " ");
423         buf.append("text=\"" + encode(getText()) + "\" type=\"" +
424                    getType() + "\">\n");
425         out.write(buf.toString());
426     }
427 
428     public void xmlSerializeRootClose(Writer   out)
429         throws IOException   {
430         out.write("</" + getClass().getName() + ">\n");
431     }
432 
433     public void xmlSerialize(Writer   out) throws IOException   {
434         // print out this node and all siblings
435         for (AST node = this;
436              node != null;
437              node = node.getNextSibling()) {
438             if (node.getFirstChild() == null) {
439                 // print guts (class name, attributes)
440                 ((BaseAST)node).xmlSerializeNode(out);
441             }
442             else {
443                 ((BaseAST)node).xmlSerializeRootOpen(out);
444 
445                 // print children
446                 ((BaseAST)node.getFirstChild()).xmlSerialize(out);
447 
448                 // print end tag
449                 ((BaseAST)node).xmlSerializeRootClose(out);
450             }
451         }
452     }
453 
454 }
455
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags