001: // !!! Productiile se pot repeta?
002:
003: package ro.infoiasi.donald.compiler.cfg;
004:
005: import java.util.*;
006:
007: public class Productions {
008: private List prodByIndex = new ArrayList();
009: /** Contains a LinkedList of productions for each LHS Non-Terminal */
010: private Map prodByLHS = new LinkedHashMap();
011: private Map prodByRHS = new HashMap();
012:
013: private Production addToMaps(Production prod) {
014: NonTerminal lhs = prod.getLHS();
015: Word rhs = prod.getRHS();
016:
017: LinkedList right;
018: if (prodByLHS.containsKey(lhs)) {
019: right = (LinkedList) prodByLHS.get(lhs);
020: } else {
021: right = new LinkedList();
022: }
023: // search for duplicates
024: Iterator it = right.iterator();
025: while (it.hasNext()) {
026: Production oldProd = (Production) it.next();
027: if (lhs.equals(oldProd.getLHS())
028: && rhs.equals(oldProd.getRHS())) {
029: return oldProd;
030: }
031: }
032: right.add(prod);
033: prodByLHS.put(lhs, right);
034:
035: LinkedList left;
036: if (prodByRHS.containsKey(rhs)) {
037: left = (LinkedList) prodByRHS.get(rhs);
038: } else {
039: left = new LinkedList();
040: }
041: left.add(prod);
042: prodByRHS.put(rhs, left);
043: return prod;
044: }
045:
046: private void clearMaps() {
047: prodByLHS.clear();
048: prodByRHS.clear();
049: }
050:
051: public Production addNew(NonTerminal lhs, Word rhs, int precedence,
052: SemanticAction action) {
053: Production prod = new Production(lhs, rhs, precedence, action,
054: count());
055: prod = addToMaps(prod);
056: prodByIndex.add(prod);
057: return prod;
058: }
059:
060: public Production addNew(NonTerminal lhs, Word rhs, int precedence) {
061: return addNew(lhs, rhs, precedence, null);
062:
063: }
064:
065: public Production addNew(NonTerminal lhs, Word rhs,
066: SemanticAction action) {
067: return addNew(lhs, rhs, Production.LAST_TERMINAL_PRECEDENCE,
068: action);
069: }
070:
071: public Production addNew(NonTerminal lhs, Word rhs) {
072: return addNew(lhs, rhs, Production.LAST_TERMINAL_PRECEDENCE,
073: null);
074: }
075:
076: public void addNew(NonTerminal lhs, List rhsList, int precedence,
077: SemanticAction action) {
078: Iterator it = rhsList.iterator();
079: while (it.hasNext()) {
080: Word rhs = (Word) it.next();
081: addNew(lhs, rhs, precedence, action);
082: }
083: }
084:
085: public void addNew(NonTerminal lhs, List rhsList, int precedence) {
086: addNew(lhs, rhsList, precedence, null);
087: }
088:
089: public void addNew(NonTerminal lhs, List rhsList,
090: SemanticAction action) {
091: addNew(lhs, rhsList, Production.LAST_TERMINAL_PRECEDENCE,
092: action);
093: }
094:
095: public void addNew(NonTerminal lhs, List rhsList) {
096: addNew(lhs, rhsList, Production.LAST_TERMINAL_PRECEDENCE, null);
097: }
098:
099: public int count() {
100: return prodByIndex.size();
101: }
102:
103: public Iterator iterator() {
104: return Collections.unmodifiableList(prodByIndex).iterator();
105: }
106:
107: public Iterator iterator(NonTerminal a) {
108: List prodList = find(a);
109: if (prodList == null) {
110: // iterator over the empty list
111: return new Iterator() {
112: public boolean hasNext() {
113: return false;
114: }
115:
116: public Object next() {
117: throw new NoSuchElementException();
118: }
119:
120: public void remove() {
121: throw new UnsupportedOperationException();
122: }
123: };
124: } else {
125: return Collections.unmodifiableList(prodList).iterator();
126: }
127: }
128:
129: public Production find(int index) {
130: if (index < 0 || index >= count()) {
131: return null;
132: } else {
133: return (Production) prodByIndex.get(index);
134: }
135: }
136:
137: public LinkedList find(NonTerminal a) {
138: // return (LinkedList)Collections.unmodifiableList((LinkedList)prodByLHS.get(a));
139: return (LinkedList) prodByLHS.get(a);
140: }
141:
142: public LinkedList find(Word w) {
143: // return (LinkedList)Collections.unmodifiableList((LinkedList)prodByRHS.get(w));
144: return (LinkedList) prodByRHS.get(w);
145: }
146:
147: public void clear() {
148: prodByIndex.clear();
149: clearMaps();
150: }
151:
152: /** Used to remove useless nonterminals and productions (package access) */
153: void removeUseless(List s) {
154: clearMaps();
155: List tmp = new ArrayList();
156: for (int i = 0; i < prodByIndex.size(); i++) {
157: Production p = find(i);
158: boolean useful = true;
159: if (s.contains(p.getLHS())) {
160: useful = false;
161: } else {
162: Word w = p.getRHS();
163: WordIterator itW = w.iterator();
164: while (itW.hasNextNonTerminal()) {
165: NonTerminal a = itW.nextNonTerminal();
166: if (s.contains(a)) {
167: useful = false;
168: break;
169: }
170: }
171: }
172: if (useful) {
173: p.setIndex(tmp.size());
174: tmp.add(p);
175: addToMaps(p);
176: }
177: }
178: prodByIndex = tmp;
179: }
180:
181: public boolean isInvertible() {
182: Iterator it = prodByRHS.keySet().iterator();
183: while (it.hasNext()) {
184: List rhsList = find((Word) it.next());
185: switch (rhsList.size()) {
186: case 0:
187: throw new RuntimeException("Null value in prodByRHS");
188: case 1:
189: break;
190: default:
191: return false;
192: }
193: }
194: return true;
195: }
196:
197: public String toString() {
198: StringBuffer sb = new StringBuffer();
199: Set keySet = prodByLHS.keySet();
200: Iterator it = keySet.iterator();
201: while (it.hasNext()) {
202: NonTerminal var = (NonTerminal) it.next();
203: sb.append(var + " ::= ");
204: List rhsList = (List) prodByLHS.get(var);
205: Iterator itL = rhsList.iterator();
206: while (itL.hasNext()) {
207: sb.append(((Production) itL.next()).getRHS());
208: if (itL.hasNext()) {
209: sb.append(" | ");
210: }
211: }
212: sb.append(";\n");
213: }
214: return sb.toString();
215: }
216: }
|