RBBINode


1   /********************************************************************
2    * COPYRIGHT:
3    * Copyright (c) 2001-2006, International Business Machines Corporation and
4    * others. All Rights Reserved.
5    ********************************************************************/
6   
7   package com.ibm.icu.text;
8   
9   import java.util.List  ;
10  import java.util.HashSet  ;
11  import java.util.Set  ;
12  
13  import com.ibm.icu.impl.Assert;
14  
15  /**
16   *   This class represents a node in the parse tree created by the RBBI Rule compiler.
17   * @internal
18   *
19   */
20  class RBBINode {
21  
22      
23   //   enum NodeType {
24       static final int    setRef = 0;
25       static final int    uset = 1;
26       static final int    varRef = 2;
27       static final int    leafChar = 3;
28       static final int    lookAhead = 4;
29       static final int    tag = 5;
30       static final int    endMark = 6;
31       static final int    opStart = 7;
32       static final int    opCat = 8;
33       static final int    opOr = 9;
34       static final int    opStar = 10;
35       static final int    opPlus = 11;
36       static final int    opQuestion = 12;
37       static final int    opBreak = 13;
38       static final int    opReverse = 14;
39       static final int    opLParen = 15;
40       static final int    nodeTypeLimit = 16;    //  For Assertion checking only.
41       
42       static String   []  nodeTypeNames = {
43           "setRef",
44           "uset",
45           "varRef",
46           "leafChar",
47           "lookAhead",
48           "tag",
49           "endMark",
50           "opStart",
51           "opCat",
52           "opOr",
53           "opStar",
54           "opPlus",
55           "opQuestion",
56           "opBreak",
57           "opReverse",
58           "opLParen"
59  };
60  
61  //    enum OpPrecedence {      
62      static final int    precZero   = 0;
63      static final int    precStart  = 1;
64      static final int    precLParen = 2;
65      static final int    precOpOr   = 3;
66      static final int    precOpCat  = 4;
67          
68      int          fType;   // enum NodeType
69      RBBINode      fParent;
70      RBBINode      fLeftChild;
71      RBBINode      fRightChild;
72      UnicodeSet    fInputSet;           // For uset nodes only.
73      int          fPrecedence = precZero;   // enum OpPrecedence, For binary ops only.
74      
75      String         fText;                 // Text corresponding to this node.
76                                          //   May be lazily evaluated when (if) needed
77                                          //   for some node types.
78      int           fFirstPos;            // Position in the rule source string of the
79                                          //   first text associated with the node.
80                                          //   If there's a left child, this will be the same
81                                          //   as that child's left pos.
82      int           fLastPos;             //  Last position in the rule source string
83                                          //    of any text associated with this node.
84                                          //    If there's a right child, this will be the same
85                                          //    as that child's last postion.
86  
87      boolean      fNullable;            //  See Aho DFA table generation algorithm
88      int           fVal;                 // For leafChar nodes, the value.
89                                          //   Values are the character category,
90                                          //   corresponds to columns in the final
91                                          //   state transition table.
92  
93      boolean      fLookAheadEnd;        // For endMark nodes, set TRUE if
94                                          //   marking the end of a look-ahead rule.
95  
96      Set             fFirstPosSet;         // See Aho DFA table generation algorithm
97      Set             fLastPosSet;          // See Aho.       
98      Set             fFollowPos;           // See Aho.
99      
100     int           fSerialNum;           //  Debugging aids.  Each node gets a unique serial number.
101     static int    gLastSerial;
102 
103     RBBINode(int t) {
104         Assert.assrt(t<nodeTypeLimit);
105         fSerialNum    = ++gLastSerial;
106         fType         = t;
107 
108         fFirstPosSet  = new HashSet  (); 
109         fLastPosSet   = new HashSet  ();
110         fFollowPos    = new HashSet  ();
111         if      (t==opCat)    {fPrecedence = precOpCat;}
112         else if (t==opOr)     {fPrecedence = precOpOr;}
113         else if (t==opStart)  {fPrecedence = precStart;}
114         else if (t==opLParen) {fPrecedence = precLParen;}
115         else fPrecedence   = precZero;
116     }
117 
118 
119     RBBINode(RBBINode other)  {
120         fSerialNum   = ++gLastSerial;
121         fType        = other.fType;
122         fInputSet    = other.fInputSet;
123         fPrecedence  = other.fPrecedence;
124         fText        = other.fText;
125         fFirstPos    = other.fFirstPos;
126         fLastPos     = other.fLastPos;
127         fNullable    = other.fNullable;
128         fVal         = other.fVal;
129         fFirstPosSet = new HashSet  (other.fFirstPosSet);
130         fLastPosSet  = new HashSet  (other.fLastPosSet);
131         fFollowPos   = new HashSet  (other.fFollowPos);
132     }
133 
134 
135 
136 
137 //-------------------------------------------------------------------------
138 //
139 //        cloneTree     Make a copy of the subtree rooted at this node.
140 //                      Discard any variable references encountered along the way,
141 //                      and replace with copies of the variable's definitions.
142 //                      Used to replicate the expression underneath variable
143 //                      references in preparation for generating the DFA tables.
144 //
145 //-------------------------------------------------------------------------
146     RBBINode cloneTree() {
147         RBBINode    n;
148 
149         if (fType == RBBINode.varRef) {
150             // If the current node is a variable reference, skip over it
151             //   and clone the definition of the variable instead.
152             n = fLeftChild.cloneTree();
153         } else if (fType == RBBINode.uset) {
154             n = this;
155         } else {
156             n = new RBBINode(this);
157             if (fLeftChild != null) {
158                 n.fLeftChild          = fLeftChild.cloneTree();
159                 n.fLeftChild.fParent = n;
160             }
161             if (fRightChild != null) {
162                 n.fRightChild          = fRightChild.cloneTree();
163                 n.fRightChild.fParent = n;
164             }
165         }
166         return n;
167     }
168 
169 
170 
171 //-------------------------------------------------------------------------
172 //
173 //       flattenVariables   Walk a parse tree, replacing any variable
174 //                          references with a copy of the variable's definition.
175 //                          Aside from variables, the tree is not changed.
176 //
177 //                          Return the root of the tree.  If the root was not a variable
178 //                          reference, it remains unchanged - the root we started with
179 //                          is the root we return.  If, however, the root was a variable
180 //                          reference, the root of the newly cloned replacement tree will
181 //                          be returned, and the original tree deleted.
182 //
183 //                          This function works by recursively walking the tree
184 //                          without doing anything until a variable reference is
185 //                          found, then calling cloneTree() at that point.  Any
186 //                          nested references are handled by cloneTree(), not here.
187 //
188 //-------------------------------------------------------------------------
189     RBBINode flattenVariables() {
190         if (fType == varRef) {
191             RBBINode retNode = fLeftChild.cloneTree();
192             // delete this;
193             return retNode;
194         }
195 
196         if (fLeftChild != null) {
197             fLeftChild = fLeftChild.flattenVariables();
198             fLeftChild.fParent  = this;
199         }
200         if (fRightChild != null) {
201             fRightChild = fRightChild.flattenVariables();
202             fRightChild.fParent = this;
203         }
204         return this;
205     }
206 
207 
208 //-------------------------------------------------------------------------
209 //
210 //      flattenSets    Walk the parse tree, replacing any nodes of type setRef
211 //                     with a copy of the expression tree for the set.  A set's
212 //                     equivalent expression tree is precomputed and saved as
213 //                     the left child of the uset node.
214 //
215 //-------------------------------------------------------------------------
216     void flattenSets() {
217         Assert.assrt(fType != setRef);
218 
219         if (fLeftChild != null) {
220             if (fLeftChild.fType==setRef) {
221                 RBBINode setRefNode = fLeftChild;
222                 RBBINode usetNode   = setRefNode.fLeftChild;
223                 RBBINode replTree   = usetNode.fLeftChild;
224                 fLeftChild          = replTree.cloneTree();
225                 fLeftChild.fParent  = this;
226              } else {
227                 fLeftChild.flattenSets();
228             }
229         }
230 
231         if (fRightChild != null) {
232             if (fRightChild.fType==setRef) {
233                 RBBINode setRefNode = fRightChild;
234                 RBBINode usetNode   = setRefNode.fLeftChild;
235                 RBBINode replTree   = usetNode.fLeftChild;
236                 fRightChild           = replTree.cloneTree();
237                 fRightChild.fParent  = this;
238                 // delete setRefNode;
239             } else {
240                 fRightChild.flattenSets();
241             }
242         }
243     }
244 
245 
246 
247 //-------------------------------------------------------------------------
248 //
249 //       findNodes()     Locate all the nodes of the specified type, starting
250 //                       at the specified root.
251 //
252 //-------------------------------------------------------------------------
253     void   findNodes(List   dest, int kind) {
254         if (fType == kind) {
255             dest.add(this);
256         }
257         if (fLeftChild != null) {
258             fLeftChild.findNodes(dest, kind);
259         }
260         if (fRightChild != null) {
261             fRightChild.findNodes(dest, kind);
262         }
263     }
264 
265     
266  
267     //-------------------------------------------------------------------------
268     //
269     //        print.         Print out a single node, for debugging.
270     //
271     //-------------------------------------------------------------------------
272     static void printNode(RBBINode n) {
273 
274         if (n==null) {
275             System.out.print (" -- null --\n");
276         } else {
277             RBBINode.printInt( n.fSerialNum, 10);
278             RBBINode.printString(nodeTypeNames[n.fType], 11);
279             RBBINode.printInt(n.fParent==null? 0     : n.fParent.fSerialNum, 11);
280             RBBINode.printInt(n.fLeftChild==null? 0  : n.fLeftChild.fSerialNum, 11);
281             RBBINode.printInt(n.fRightChild==null? 0 : n.fRightChild.fSerialNum, 12);
282             RBBINode.printInt(n.fFirstPos, 12);
283             RBBINode.printInt(n.fVal, 7);
284             
285             if (n.fType == varRef) {
286                 System.out.print(" " + n.fText);
287             }
288         }
289         System.out.println("");
290     }
291  
292 
293     // Print a String in a fixed field size.
294     // Debugging function.
295     static void printString(String   s, int minWidth)
296     {
297         for (int i=minWidth; i<0; i++) {
298             // negative width means pad leading spaces, not fixed width.
299             System.out.print(' ');
300         }
301         for (int i=s.length(); i<minWidth; i++) {
302             System.out.print(' ');
303         }
304         System.out.print(s);
305     }
306     
307      //
308      //  Print an int in a fixed size field.
309      //  Debugging function.
310      //
311      static void printInt(int i, int minWidth) {
312          String   s = Integer.toString(i);
313          printString(s, Math.max(minWidth, s.length()+1));
314      }
315      
316      static void printHex(int i, int minWidth) {
317          String   s = Integer.toString(i, 16);
318          String   leadingZeroes = "00000".substring(0, Math.max(0, 5-s.length()));
319          s = leadingZeroes+s;
320          printString(s, minWidth);
321      }
322  
323 
324      // -------------------------------------------------------------------------
325      //
326      //        print.         Print out the tree of nodes rooted at "this"
327      //
328      // -------------------------------------------------------------------------
329     void printTree(boolean printHeading) {
330         if (printHeading) {
331             System.out.println( "-------------------------------------------------------------------");
332             System.out.println("    Serial       type     Parent  LeftChild  RightChild    position  value");
333         }
334         printNode(this);
335             // Only dump the definition under a variable reference if asked to.
336             // Unconditinally dump children of all other node types.
337             if (fType != varRef) {
338                 if (fLeftChild != null) {
339                     fLeftChild.printTree(false);
340                 }
341                 
342                 if (fRightChild != null) {
343                     fRightChild.printTree(false);
344                 }
345             }
346     }
347 
348 }
349
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags