001: package ro.infoiasi.donald.compiler.parser;
002:
003: import ro.infoiasi.donald.compiler.cfg.*;
004: import java.util.*;
005:
006: public class LR0State {
007: private int index;
008: private Set kernel = new LinkedHashSet();
009: private Set closure = new LinkedHashSet();
010: private Map itemsByNext = new LinkedHashMap();
011:
012: public boolean equals(Object o) {
013: return (o instanceof LR0State
014: && kernel.equals(((LR0State) o).kernel) && closure
015: .equals(((LR0State) o).closure));
016: }
017:
018: public int hashCode() {
019: return 17 + kernel.hashCode() * 37 + closure.hashCode();
020: }
021:
022: public boolean isEmpty() {
023: return kernel.isEmpty();
024: }
025:
026: private void addToItemsByNext(LR0Item item) {
027: if (!item.isComplete()) {
028: Symbol sym = item.getNextSymbol();
029: LinkedList itemList;
030: if (itemsByNext.containsKey(sym)) {
031: itemList = (LinkedList) itemsByNext.get(sym);
032: } else {
033: itemList = new LinkedList();
034: }
035: itemList.add(item);
036: itemsByNext.put(sym, itemList);
037: }
038: }
039:
040: public boolean addKernelItem(LR0Item item) {
041: if (kernel.add(item)) {
042: addToItemsByNext(item);
043: return true;
044: } else {
045: return false;
046: }
047: }
048:
049: public Iterator iterator() {
050: return new Iterator() {
051: Iterator it = kernel.iterator();
052: boolean inKernel = true;
053:
054: public boolean hasNext() {
055: if (it.hasNext() || (inKernel && !closure.isEmpty())) {
056: return true;
057: } else {
058: return false;
059: }
060: }
061:
062: public Object next() {
063: if (inKernel && !it.hasNext()) {
064: it = closure.iterator();
065: inKernel = false;
066: }
067: return it.next();
068: }
069:
070: public void remove() {
071: throw new UnsupportedOperationException();
072: }
073: };
074: }
075:
076: public LinkedList find(Symbol x) {
077: return (LinkedList) itemsByNext.get(x);
078: }
079:
080: public Iterator iterator(Symbol x) {
081: List itemList = find(x);
082: if (itemList == null) {
083: // iterator over the empty list
084: return new Iterator() {
085: public boolean hasNext() {
086: return false;
087: }
088:
089: public Object next() {
090: throw new NoSuchElementException();
091: }
092:
093: public void remove() {
094: throw new UnsupportedOperationException();
095: }
096: };
097: } else {
098: return Collections.unmodifiableList(itemList).iterator();
099: }
100: }
101:
102: public boolean contains(LR0Item item) {
103: return kernel.contains(item) || closure.contains(item);
104: }
105:
106: public void closure(Productions p) {
107: LinkedList queue = new LinkedList();
108: queue.addAll(kernel);
109:
110: while (!queue.isEmpty()) {
111: LR0Item item = (LR0Item) queue.removeFirst();
112: if (!item.isComplete()) {
113: Symbol sym = (Symbol) item.getNextSymbol();
114: if (!sym.isTerminal()) {
115: List prodList = p.find((NonTerminal) sym);
116: Iterator pIt = prodList.iterator();
117: while (pIt.hasNext()) {
118: Production prod = (Production) pIt.next();
119: LR0Item newItem = new LR0Item(prod);
120: if (closure.add(newItem)) {
121: addToItemsByNext(newItem);
122: queue.addLast(newItem);
123: }
124: }
125: }
126: }
127: }
128: }
129:
130: void setIndex(int index) {
131: this .index = index;
132: }
133:
134: public int getIndex() {
135: return index;
136: }
137:
138: public Collection getKernelItems() {
139: return kernel;
140: }
141:
142: public Collection getClosureItems() {
143: return closure;
144: }
145:
146: public String toString() {
147: StringBuffer sb = new StringBuffer();
148: sb.append("{");
149: Iterator it = kernel.iterator();
150: while (it.hasNext()) {
151: sb.append(it.next());
152: if (it.hasNext()) {
153: sb.append(", ");
154: }
155: }
156: sb.append("; ");
157: it = closure.iterator();
158: while (it.hasNext()) {
159: sb.append(it.next());
160: if (it.hasNext()) {
161: sb.append(", ");
162: }
163: }
164: sb.append("}");
165: return new String(sb);
166: }
167: }
|