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