Source Code Cross Referenced for lalr_item_set.java in  » Parser » CUP-develop » java_cup » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » Parser » CUP develop » java_cup 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


001:        package java_cup;
002:
003:        import java.util.Hashtable;
004:        import java.util.Enumeration;
005:
006:        /** This class represents a set of LALR items.  For purposes of building
007:         *  these sets, items are considered unique only if they have unique cores
008:         *  (i.e., ignoring differences in their lookahead sets).<p>
009:         *
010:         *  This class provides fairly conventional set oriented operations (union,
011:         *  sub/super-set tests, etc.), as well as an LALR "closure" operation (see 
012:         *  compute_closure()).
013:         *
014:         * @see     java_cup.lalr_item
015:         * @see     java_cup.lalr_state
016:         * @version last updated: 3/6/96
017:         * @author  Scott Hudson
018:         */
019:
020:        public class lalr_item_set {
021:
022:            /*-----------------------------------------------------------*/
023:            /*--- Constructor(s) ----------------------------------------*/
024:            /*-----------------------------------------------------------*/
025:
026:            /** Constructor for an empty set. */
027:            public lalr_item_set() {
028:            }
029:
030:            /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
031:
032:            /** Constructor for cloning from another set. 
033:             * @param other indicates set we should copy from.
034:             */
035:            public lalr_item_set(lalr_item_set other) throws internal_error {
036:                not_null(other);
037:                _all = (Hashtable) other._all.clone();
038:            }
039:
040:            /*-----------------------------------------------------------*/
041:            /*--- (Access to) Instance Variables ------------------------*/
042:            /*-----------------------------------------------------------*/
043:
044:            /** A hash table to implement the set.  We store the items using themselves
045:             *  as keys. 
046:             */
047:            protected Hashtable _all = new Hashtable(11);
048:
049:            /** Access to all elements of the set. */
050:            public Enumeration all() {
051:                return _all.elements();
052:            }
053:
054:            /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
055:
056:            /** Cached hashcode for this set. */
057:            protected Integer hashcode_cache = null;
058:
059:            /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
060:
061:            /** Size of the set */
062:            public int size() {
063:                return _all.size();
064:            }
065:
066:            /*-----------------------------------------------------------*/
067:            /*--- Set Operation Methods ---------------------------------*/
068:            /*-----------------------------------------------------------*/
069:
070:            /** Does the set contain a particular item? 
071:             * @param itm the item in question.
072:             */
073:            public boolean contains(lalr_item itm) {
074:                return _all.containsKey(itm);
075:            }
076:
077:            /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
078:
079:            /** Return the item in the set matching a particular item (or null if not 
080:             *  found) 
081:             *  @param itm the item we are looking for.
082:             */
083:            public lalr_item find(lalr_item itm) {
084:                return (lalr_item) _all.get(itm);
085:            }
086:
087:            /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
088:
089:            /** Is this set an (improper) subset of another? 
090:             * @param other the other set in question.
091:             */
092:            public boolean is_subset_of(lalr_item_set other)
093:                    throws internal_error {
094:                not_null(other);
095:
096:                /* walk down our set and make sure every element is in the other */
097:                for (Enumeration e = all(); e.hasMoreElements();)
098:                    if (!other.contains((lalr_item) e.nextElement()))
099:                        return false;
100:
101:                /* they were all there */
102:                return true;
103:            }
104:
105:            /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
106:
107:            /** Is this set an (improper) superset of another? 
108:             * @param other the other set in question.
109:             */
110:            public boolean is_super set_of(lalr_item_set other)
111:                    throws internal_error {
112:                not_null(other);
113:                return other.is_subset_of(this );
114:            }
115:
116:            /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
117:
118:            /** Add a singleton item, merging lookahead sets if the item is already 
119:             *  part of the set.  returns the element of the set that was added or 
120:             *  merged into.
121:             * @param itm the item being added.
122:             */
123:            public lalr_item add(lalr_item itm) throws internal_error {
124:                lalr_item other;
125:
126:                not_null(itm);
127:
128:                /* see if an item with a matching core is already there */
129:                other = (lalr_item) _all.get(itm);
130:
131:                /* if so, merge this lookahead into the original and leave it */
132:                if (other != null) {
133:                    other.lookahead().add(itm.lookahead());
134:                    return other;
135:                }
136:                /* otherwise we just go in the set */
137:                else {
138:                    /* invalidate cached hashcode */
139:                    hashcode_cache = null;
140:
141:                    _all.put(itm, itm);
142:                    return itm;
143:                }
144:            }
145:
146:            /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
147:
148:            /** Remove a single item if it is in the set. 
149:             * @param itm the item to remove.
150:             */
151:            public void remove(lalr_item itm) throws internal_error {
152:                not_null(itm);
153:
154:                /* invalidate cached hashcode */
155:                hashcode_cache = null;
156:
157:                /* remove it from hash table implementing set */
158:                _all.remove(itm);
159:            }
160:
161:            /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
162:
163:            /** Add a complete set, merging lookaheads where items are already in 
164:             *  the set 
165:             * @param other the set to be added.
166:             */
167:            public void add(lalr_item_set other) throws internal_error {
168:                not_null(other);
169:
170:                /* walk down the other set and do the adds individually */
171:                for (Enumeration e = other.all(); e.hasMoreElements();)
172:                    add((lalr_item) e.nextElement());
173:            }
174:
175:            /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
176:
177:            /** Remove (set subtract) a complete set. 
178:             * @param other the set to remove.
179:             */
180:            public void remove(lalr_item_set other) throws internal_error {
181:                not_null(other);
182:
183:                /* walk down the other set and do the removes individually */
184:                for (Enumeration e = other.all(); e.hasMoreElements();)
185:                    remove((lalr_item) e.nextElement());
186:            }
187:
188:            /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
189:
190:            /** Remove and return one item from the set (done in hash order). */
191:            public lalr_item get_one() throws internal_error {
192:                Enumeration the_set;
193:                lalr_item result;
194:
195:                the_set = all();
196:                if (the_set.hasMoreElements()) {
197:                    result = (lalr_item) the_set.nextElement();
198:                    remove(result);
199:                    return result;
200:                } else
201:                    return null;
202:            }
203:
204:            /*-----------------------------------------------------------*/
205:            /*--- General Methods ---------------------------------------*/
206:            /*-----------------------------------------------------------*/
207:
208:            /** Helper function for null test.  Throws an interal_error exception if its
209:             *  parameter is null.
210:             *  @param obj the object we are testing.
211:             */
212:            protected void not_null(Object obj) throws internal_error {
213:                if (obj == null)
214:                    throw new internal_error(
215:                            "Null object used in set operation");
216:            }
217:
218:            /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
219:
220:            /** Compute the closure of the set using the LALR closure rules.  Basically
221:             *  for every item of the form: <pre>
222:             *    [L ::= a *N alpha, l] 
223:             *  </pre>
224:             *  (where N is a a non terminal and alpha is a string of symbols) make 
225:             *  sure there are also items of the form:  <pre>
226:             *    [N ::= *beta, first(alpha l)] 
227:             *  </pre>
228:             *  corresponding to each production of N.  Items with identical cores but 
229:             *  differing lookahead sets are merged by creating a new item with the same 
230:             *  core and the union of the lookahead sets (the LA in LALR stands for 
231:             *  "lookahead merged" and this is where the merger is).  This routine 
232:             *  assumes that nullability and first sets have been computed for all 
233:             *  productions before it is called.
234:             */
235:            public void compute_closure() throws internal_error {
236:                lalr_item_set consider;
237:                lalr_item itm, new_itm, add_itm;
238:                non_terminal nt;
239:                terminal_set new_lookaheads;
240:                Enumeration p;
241:                production prod;
242:                boolean need_prop;
243:
244:                /* invalidate cached hashcode */
245:                hashcode_cache = null;
246:
247:                /* each current element needs to be considered */
248:                consider = new lalr_item_set(this );
249:
250:                /* repeat this until there is nothing else to consider */
251:                while (consider.size() > 0) {
252:                    /* get one item to consider */
253:                    itm = consider.get_one();
254:
255:                    /* do we have a dot before a non terminal */
256:                    nt = itm.dot_before_nt();
257:                    if (nt != null) {
258:                        /* create the lookahead set based on first after dot */
259:                        new_lookaheads = itm.calc_lookahead(itm.lookahead());
260:
261:                        /* are we going to need to propagate our lookahead to new item */
262:                        need_prop = itm.lookahead_visible();
263:
264:                        /* create items for each production of that non term */
265:                        for (p = nt.productions(); p.hasMoreElements();) {
266:                            prod = (production) p.nextElement();
267:
268:                            /* create new item with dot at start and that lookahead */
269:                            new_itm = new lalr_item(prod, new terminal_set(
270:                                    new_lookaheads));
271:
272:                            /* add/merge item into the set */
273:                            add_itm = add(new_itm);
274:                            /* if propagation is needed link to that item */
275:                            if (need_prop)
276:                                itm.add_propagate(add_itm);
277:
278:                            /* was this was a new item*/
279:                            if (add_itm == new_itm) {
280:                                /* that may need further closure, consider it also */
281:                                consider.add(new_itm);
282:                            }
283:                        }
284:                    }
285:                }
286:            }
287:
288:            /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
289:
290:            /** Equality comparison. */
291:            public boolean equals(lalr_item_set other) {
292:                if (other == null || other.size() != size())
293:                    return false;
294:
295:                /* once we know they are the same size, then improper subset does test */
296:                try {
297:                    return is_subset_of(other);
298:                } catch (internal_error e) {
299:                    /* can't throw error from here (because superclass doesn't) so crash */
300:                    e.crash();
301:                    return false;
302:                }
303:
304:            }
305:
306:            /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
307:
308:            /** Generic equality comparison. */
309:            public boolean equals(Object other) {
310:                if (!(other instanceof  lalr_item_set))
311:                    return false;
312:                else
313:                    return equals((lalr_item_set) other);
314:            }
315:
316:            /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
317:
318:            /** Return hash code. */
319:            public int hashCode() {
320:                int result = 0;
321:                Enumeration e;
322:                int cnt;
323:
324:                /* only compute a new one if we don't have it cached */
325:                if (hashcode_cache == null) {
326:                    /* hash together codes from at most first 5 elements */
327:                    //   CSA fix! we'd *like* to hash just a few elements, but
328:                    //   that means equal sets will have inequal hashcodes, which
329:                    //   we're not allowed (by contract) to do.  So hash them all.
330:                    for (e = all(), cnt = 0; e.hasMoreElements() /*&& cnt<5*/; cnt++)
331:                        result ^= ((lalr_item) e.nextElement()).hashCode();
332:
333:                    hashcode_cache = new Integer(result);
334:                }
335:
336:                return hashcode_cache.intValue();
337:            }
338:
339:            /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
340:
341:            /** Convert to string. */
342:            public String toString() {
343:                StringBuffer result = new StringBuffer();
344:
345:                result.append("{\n");
346:                for (Enumeration e = all(); e.hasMoreElements();) {
347:                    result.append("  " + (lalr_item) e.nextElement() + "\n");
348:                }
349:                result.append("}");
350:
351:                return result.toString();
352:            }
353:            /*-----------------------------------------------------------*/
354:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.