|
1 package ro.infoiasi.donald.compiler.parser;
2
3 import ro.infoiasi.donald.compiler.cfg.*;
4 import java.util.*;
5
6 public class LR1State {
7 private int index;
8 private Set kernel = new LinkedHashSet();
9 private Set closure = new LinkedHashSet();
10
11 private Map itemsByNext = new LinkedHashMap();
12
13 public boolean equals(Object  o) {
14 return (o instanceof LR1State &&
15 kernel.equals(((LR1State)o).kernel) &&
16 closure.equals(((LR1State)o).closure));
17 }
18
19 public int hashCode() {
20 return 17+kernel.hashCode()*37+closure.hashCode();
21 }
22
23 public boolean isEmpty() {
24 return kernel.isEmpty();
25 }
26
27 private void addToItemsByNext(LR1Item item) {
28 if (!item.isComplete()) {
29 Symbol sym = item.getNextSymbol();
30 LinkedList itemList;
31 if (itemsByNext.containsKey(sym)) {
32 itemList = (LinkedList)itemsByNext.get(sym);
33 } else {
34 itemList = new LinkedList();
35 }
36 itemList.add(item);
37 itemsByNext.put(sym, itemList);
38 }
39 }
40
41 public boolean addKernelItem(LR1Item item) {
42 if (kernel.add(item)) {
43 addToItemsByNext(item);
44 return true;
45 } else {
46 return false;
47 }
48 }
49
50 public Collection addKernelItemWithClosure(LR1Item item, CFG g) {
51 if (addKernelItem(item)) {
52 Collection closureKernel = new LinkedList();
53 closureKernel.add(item);
54 return closure(closureKernel, g);
55 } else {
56 return null;
57 }
58 }
59
60 public Iterator iterator() {
61 return new Iterator() {
62 Iterator it = kernel.iterator();
63 boolean inKernel = true;
64
65 public boolean hasNext() {
66 if (it.hasNext() || (inKernel && !closure.isEmpty())) {
67 return true;
68 } else {
69 return false;
70 }
71 }
72
73 public Object next() {
74 if (inKernel && !it.hasNext()) {
75 it = closure.iterator();
76 inKernel = false;
77 }
78 return it.next();
79 }
80
81 public void remove() {
82 throw new UnsupportedOperationException ();
83 }
84 };
85 }
86
87 public LinkedList find(Symbol x) {
88 return (LinkedList)itemsByNext.get(x);
89 }
90
91 public Iterator iterator(Symbol x) {
92 List itemList = find(x);
93 if (itemList == null) {
94 return new Iterator() {
96 public boolean hasNext() { return false; }
97 public Object next() { throw new NoSuchElementException(); }
98 public void remove() { throw new UnsupportedOperationException (); }
99 };
100 } else {
101 return Collections.unmodifiableList(itemList).iterator();
102 }
103 }
104
105 public boolean contains(LR1Item item) {
106 return kernel.contains(item) || closure.contains(item);
107 }
108
109 private Collection closure(Collection closureKernel, CFG g) {
110 Collection newClosureItems = new LinkedList(closureKernel);
111 LinkedList queue = new LinkedList(closureKernel);
112
113 while (!queue.isEmpty()) {
114 LR1Item item = (LR1Item)queue.removeFirst();
115
116 if (!item.isComplete()) {
117 Symbol sym = (Symbol)item.getNextSymbol();
118 if (!sym.isTerminal()) {
119 Iterator firstIt = g.first(item.getSufixAndLookahead()).iterator();
120 while (firstIt.hasNext()) {
121 Terminal newLookahead = (Terminal)firstIt.next();
122 List prodList = g.getProductions().find((NonTerminal)sym);
123 Iterator pIt = prodList.iterator();
124 while (pIt.hasNext()) {
125 Production prod = (Production)pIt.next();
126 LR1Item newItem = new LR1Item(new LR0Item(prod), newLookahead);
127 if (closure.add(newItem)) {
128 addToItemsByNext(newItem);
129 queue.addLast(newItem);
130 newClosureItems.add(newItem);
131 }
132 }
133 }
134 }
135 }
136 }
137 return newClosureItems;
138 }
139
140 public Collection closure(CFG g) {
141 return closure(kernel, g);
142 }
143
144 void setIndex(int index) {
145 this.index = index;
146 }
147
148 public int getIndex() {
149 return index;
150 }
151
152 public Collection getKernelItems() {
153 return Collections.unmodifiableSet(kernel);
154 }
155
156 public Collection getClosureItems() {
157 return Collections.unmodifiableSet(closure);
158 }
159
160 public String toString() {
161 StringBuffer sb = new StringBuffer ();
162 sb.append("{");
163 Iterator it = kernel.iterator();
164 while (it.hasNext()) {
165 sb.append(it.next());
166 if (it.hasNext()) {
167 sb.append(", ");
168 }
169 }
170 sb.append("; ");
171 it = closure.iterator();
172 while (it.hasNext()) {
173 sb.append(it.next());
174 if (it.hasNext()) {
175 sb.append(", ");
176 }
177 }
178 sb.append("}");
179 return new String (sb);
180 }
181 }
182 |
Popular Tags |
Java API By Example, From Geeks To Geeks.