001: /*
002: * ProductionPatternAlternative.java
003: *
004: * This work is free software; you can redistribute it and/or modify
005: * it under the terms of the GNU General Public License as published
006: * by the Free Software Foundation; either version 2 of the License,
007: * or (at your option) any later version.
008: *
009: * This work is distributed in the hope that it will be useful, but
010: * WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * General Public License for more details.
013: *
014: * You should have received a copy of the GNU General Public License
015: * along with this program; if not, write to the Free Software
016: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
017: * USA
018: *
019: * As a special exception, the copyright holders of this library give
020: * you permission to link this library with independent modules to
021: * produce an executable, regardless of the license terms of these
022: * independent modules, and to copy and distribute the resulting
023: * executable under terms of your choice, provided that you also meet,
024: * for each linked independent module, the terms and conditions of the
025: * license of that module. An independent module is a module which is
026: * not derived from or based on this library. If you modify this
027: * library, you may extend this exception to your version of the
028: * library, but you are not obligated to do so. If you do not wish to
029: * do so, delete this exception statement from your version.
030: *
031: * Copyright (c) 2003 Per Cederberg. All rights reserved.
032: */
033:
034: package net.percederberg.grammatica.parser;
035:
036: import java.util.ArrayList;
037:
038: /**
039: * A production pattern alternative. This class represents a list of
040: * production pattern elements. In order to provide productions that
041: * cannot be represented with the element occurance counters, multiple
042: * alternatives must be created and added to the same production
043: * pattern. A production pattern alternative is always contained
044: * within a production pattern.
045: *
046: * @author Per Cederberg, <per at percederberg dot net>
047: * @version 1.0
048: */
049: public class ProductionPatternAlternative {
050:
051: /**
052: * The production pattern.
053: */
054: private ProductionPattern pattern;
055:
056: /**
057: * The element list.
058: */
059: private ArrayList elements = new ArrayList();
060:
061: /**
062: * The look-ahead set associated with this alternative.
063: */
064: private LookAheadSet lookAhead = null;
065:
066: /**
067: * Creates a new production pattern alternative.
068: */
069: public ProductionPatternAlternative() {
070: }
071:
072: /**
073: * Checks if this alternative is recursive on the left-hand side.
074: * This method checks all the possible left side elements and
075: * returns true if the pattern itself is among them.
076: *
077: * @return true if the alternative is left side recursive, or
078: * false otherwise
079: */
080: public boolean isLeftRecursive() {
081: ProductionPatternElement elem;
082:
083: for (int i = 0; i < elements.size(); i++) {
084: elem = (ProductionPatternElement) elements.get(i);
085: if (elem.getId() == pattern.getId()) {
086: return true;
087: } else if (elem.getMinCount() > 0) {
088: break;
089: }
090: }
091: return false;
092: }
093:
094: /**
095: * Checks if this alternative is recursive on the right-hand side.
096: * This method checks all the possible right side elements and
097: * returns true if the pattern itself is among them.
098: *
099: * @return true if the alternative is right side recursive, or
100: * false otherwise
101: */
102: public boolean isRightRecursive() {
103: ProductionPatternElement elem;
104:
105: for (int i = elements.size() - 1; i >= 0; i--) {
106: elem = (ProductionPatternElement) elements.get(i);
107: if (elem.getId() == pattern.getId()) {
108: return true;
109: } else if (elem.getMinCount() > 0) {
110: break;
111: }
112: }
113: return false;
114: }
115:
116: /**
117: * Checks if this alternative would match an empty stream of
118: * tokens. This check is equivalent of getMinElementCount()
119: * returning zero (0).
120: *
121: * @return true if the rule can match an empty token stream, or
122: * false otherwise
123: */
124: public boolean isMatchingEmpty() {
125: return getMinElementCount() == 0;
126: }
127:
128: /**
129: * Returns the production pattern containing this alternative.
130: *
131: * @return the production pattern for this alternative
132: */
133: public ProductionPattern getPattern() {
134: return pattern;
135: }
136:
137: /**
138: * Changes the production pattern containing this alternative.
139: * This method should only be called by the production pattern
140: * class.
141: *
142: * @param pattern the new production pattern
143: */
144: void setPattern(ProductionPattern pattern) {
145: this .pattern = pattern;
146: }
147:
148: /**
149: * Returns the number of elements in this alternative.
150: *
151: * @return the number of elements in this alternative
152: */
153: public int getElementCount() {
154: return elements.size();
155: }
156:
157: /**
158: * Returns the minimum number of elements needed to satisfy this
159: * alternative. The value returned is the sum of all the elements
160: * minimum count.
161: *
162: * @return the minimum number of elements
163: */
164: public int getMinElementCount() {
165: ProductionPatternElement elem;
166: int min = 0;
167:
168: for (int i = 0; i < elements.size(); i++) {
169: elem = (ProductionPatternElement) elements.get(i);
170: min += elem.getMinCount();
171: }
172: return min;
173: }
174:
175: /**
176: * Returns the maximum number of elements needed to satisfy this
177: * alternative. The value returned is the sum of all the elements
178: * maximum count.
179: *
180: * @return the maximum number of elements
181: */
182: public int getMaxElementCount() {
183: ProductionPatternElement elem;
184: int max = 0;
185:
186: for (int i = 0; i < elements.size(); i++) {
187: elem = (ProductionPatternElement) elements.get(i);
188: if (elem.getMaxCount() >= Integer.MAX_VALUE) {
189: return Integer.MAX_VALUE;
190: } else {
191: max += elem.getMaxCount();
192: }
193: }
194: return max;
195: }
196:
197: /**
198: * Returns an element in this alternative.
199: *
200: * @param pos the element position, 0 <= pos < count
201: *
202: * @return the element found
203: */
204: public ProductionPatternElement getElement(int pos) {
205: return (ProductionPatternElement) elements.get(pos);
206: }
207:
208: /**
209: * Adds a token to this alternative. The token is appended to the
210: * end of the element list. The multiplicity values specified
211: * define if the token is optional or required, and if it can be
212: * repeated.
213: *
214: * @param id the token (pattern) id
215: * @param min the minimum number of occurancies
216: * @param max the maximum number of occurancies, or
217: * -1 for infinite
218: */
219: public void addToken(int id, int min, int max) {
220: addElement(new ProductionPatternElement(true, id, min, max));
221: }
222:
223: /**
224: * Adds a production to this alternative. The production is
225: * appended to the end of the element list. The multiplicity
226: * values specified define if the production is optional or
227: * required, and if it can be repeated.
228: *
229: * @param id the production (pattern) id
230: * @param min the minimum number of occurancies
231: * @param max the maximum number of occurancies, or
232: * -1 for infinite
233: */
234: public void addProduction(int id, int min, int max) {
235: addElement(new ProductionPatternElement(false, id, min, max));
236: }
237:
238: /**
239: * Adds a production pattern element to this alternative. The
240: * element is appended to the end of the element list.
241: *
242: * @param elem the production pattern element
243: */
244: public void addElement(ProductionPatternElement elem) {
245: elements.add(elem);
246: }
247:
248: /**
249: * Adds a production pattern element to this alternative. The
250: * multiplicity values in the element will be overridden with the
251: * specified values. The element is appended to the end of the
252: * element list.
253: *
254: * @param elem the production pattern element
255: * @param min the minimum number of occurancies
256: * @param max the maximum number of occurancies, or
257: * -1 for infinite
258: */
259: public void addElement(ProductionPatternElement elem, int min,
260: int max) {
261:
262: if (elem.isToken()) {
263: addToken(elem.getId(), min, max);
264: } else {
265: addProduction(elem.getId(), min, max);
266: }
267: }
268:
269: /**
270: * Checks if this object is equal to another. This method only
271: * returns true for another production pattern alternative with
272: * identical elements in the same order.
273: *
274: * @param obj the object to compare with
275: *
276: * @return true if the object is identical to this one, or
277: * false otherwise
278: */
279: public boolean equals(Object obj) {
280: ProductionPatternAlternative alt;
281:
282: if (obj instanceof ProductionPatternAlternative) {
283: alt = (ProductionPatternAlternative) obj;
284: return elements.equals(alt.elements);
285: } else {
286: return false;
287: }
288: }
289:
290: /**
291: * Returns a string representation of this object.
292: *
293: * @return a token string representation
294: */
295: public String toString() {
296: StringBuffer buffer = new StringBuffer();
297:
298: for (int i = 0; i < elements.size(); i++) {
299: if (i > 0) {
300: buffer.append(" ");
301: }
302: buffer.append(elements.get(i));
303: }
304: return buffer.toString();
305: }
306:
307: /**
308: * Returns the look-ahead set associated with this alternative.
309: *
310: * @return the look-ahead set associated with this alternative
311: */
312: LookAheadSet getLookAhead() {
313: return lookAhead;
314: }
315:
316: /**
317: * Sets the look-ahead set for this alternative.
318: *
319: * @param lookAhead the new look-ahead set
320: */
321: void setLookAhead(LookAheadSet lookAhead) {
322: this.lookAhead = lookAhead;
323: }
324: }
|