001: /*
002: * Copyright (C) Chaperon. All rights reserved.
003: * -------------------------------------------------------------------------
004: * This software is published under the terms of the Apache Software License
005: * version 1.1, a copy of which has been included with this distribution in
006: * the LICENSE file.
007: */
008:
009: package net.sourceforge.chaperon.process;
010:
011: import java.io.Serializable;
012:
013: import java.util.Arrays;
014:
015: /**
016: * This class represents a parser automaton, which holds all states and transition, which are used
017: * by the the parser processor.
018: *
019: * @author <a href="mailto:stephan@apache.org">Stephan Michels </a>
020: * @version CVS $Id: ParserAutomaton.java,v 1.9 2003/12/09 19:55:53 benedikta Exp $
021: */
022: public class ParserAutomaton implements Serializable {
023: // List of all terminal symbols
024: private String[] tsymbols;
025:
026: // List of all non terminal symbols
027: private String[] ntsymbols;
028:
029: // Indices of the non terminal symbols for the productions
030: private int[] productionsymbols;
031:
032: // Lengths from the productions
033: private int[] productionlengths;
034:
035: // Error messages
036: private String[] errors;
037:
038: // ---------- Action ------------------------
039: // Actions, contains the type of action and the action argument
040: private int[][] actions;
041: private int[] eofactions;
042:
043: /** Error action */
044: private static final int ERROR = 0;
045:
046: /** Shift action */
047: private static final int SHIFT = 1;
048:
049: /** Reduce action */
050: private static final int REDUCE = 2;
051:
052: /** Accept action */
053: private static final int ACCEPT = 3;
054:
055: // ---------- Goto --------------------------
056: // Transitions for the productions
057: private int[][] transitions;
058: private static final long serialVersionUID = 8045275977315821215L;
059:
060: /**
061: * Constructs a empty parser automaton
062: *
063: * @param tsymbolcount Count of terminal symbols.
064: * @param ntsymbolcount Count of nonterminal symbols.
065: * @param productioncount Count of productions.
066: * @param errorcount Count of error types.
067: * @param statecount Count of states.
068: */
069: public ParserAutomaton(int tsymbolcount, int ntsymbolcount,
070: int productioncount, int errorcount, int statecount) {
071: tsymbols = new String[tsymbolcount];
072: Arrays.fill(tsymbols, "noname");
073:
074: ntsymbols = new String[ntsymbolcount];
075: Arrays.fill(ntsymbols, "noname");
076:
077: productionsymbols = new int[productioncount];
078: Arrays.fill(productionsymbols, 0);
079: productionlengths = new int[productioncount];
080: Arrays.fill(productionlengths, 0);
081:
082: errors = new String[errorcount];
083: Arrays.fill(errors, "Unexpected token.");
084:
085: actions = new int[statecount][tsymbolcount];
086: for (int i = 0; i < statecount; i++)
087: Arrays.fill(actions[i], ERROR);
088:
089: eofactions = new int[statecount];
090: Arrays.fill(eofactions, ERROR);
091:
092: transitions = new int[statecount][ntsymbolcount];
093: for (int i = 0; i < statecount; i++)
094: Arrays.fill(transitions[i], 0);
095: }
096:
097: /**
098: * Sets the name of a terminal symbol.
099: *
100: * @param index Index of the symbol.
101: * @param symbol Name of the symbol.
102: */
103: public void setTerminal(int index, String symbol) {
104: if ((index < 0) || (index >= tsymbols.length))
105: throw new IndexOutOfBoundsException();
106:
107: tsymbols[index] = symbol;
108: }
109:
110: /**
111: * Returns the name of a terminal symbol.
112: *
113: * @param index Index of the symbol.
114: *
115: * @return Name of the symbol.
116: */
117: public String getTerminal(int index) {
118: if ((index < 0) || (index >= tsymbols.length))
119: throw new IndexOutOfBoundsException();
120:
121: return tsymbols[index];
122: }
123:
124: /**
125: * Returns the count of terminal symbols.
126: *
127: * @return Count of terminal symbols.
128: */
129: public int getTerminalCount() {
130: return tsymbols.length;
131: }
132:
133: /**
134: * Sets the name of a nonterminal symbol.
135: *
136: * @param index Index of the symbol.
137: * @param symbol Name of the symbol.
138: */
139: public void setNonterminal(int index, String symbol) {
140: if ((index < 0) || (index >= ntsymbols.length))
141: throw new IndexOutOfBoundsException();
142:
143: ntsymbols[index] = symbol;
144: }
145:
146: /**
147: * Returns the name of a nonterminal symbol.
148: *
149: * @param index Index of the symbol.
150: *
151: * @return Name of the symbol.
152: */
153: public String getNonterminal(int index) {
154: if ((index < 0) || (index >= ntsymbols.length))
155: throw new IndexOutOfBoundsException();
156:
157: return ntsymbols[index];
158: }
159:
160: /**
161: * Returns the count of nonterminal symbols.
162: *
163: * @return Count of nonterminal symbols.
164: */
165: public int getNonterminalCount() {
166: return ntsymbols.length;
167: }
168:
169: /**
170: * Sets the symbol for a production
171: *
172: * @param index Index of the production
173: * @param symbolindex Index of the nonterminal symbol
174: */
175: public void setProductionSymbol(int index, int symbol) {
176: if ((symbol < 0) || (symbol >= ntsymbols.length))
177: throw new IndexOutOfBoundsException();
178:
179: productionsymbols[index] = symbol;
180: }
181:
182: /**
183: * Return the symbol of a production.
184: *
185: * @param index Index of the production.
186: *
187: * @return Index of the nonterminal symbol
188: */
189: public int getProductionSymbol(int index) {
190: return productionsymbols[index];
191: }
192:
193: /**
194: * Set the length of a production.
195: *
196: * @param index Index of the production.
197: * @param length Length of the production.
198: */
199: public void setProductionLength(int index, int length) {
200: if (length < 0)
201: throw new IllegalArgumentException();
202:
203: productionlengths[index] = length;
204: }
205:
206: /**
207: * Return the length of a production.
208: *
209: * @param index Index of a production.
210: *
211: * @return Length of the production.
212: */
213: public int getProductionLength(int index) {
214: return productionlengths[index];
215: }
216:
217: /**
218: * Return the count of productions.
219: *
220: * @return Count of productions.
221: */
222: public int getProductionCount() {
223: return productionsymbols.length;
224: }
225:
226: /**
227: * Sets the message for an error.
228: *
229: * @param index Index of the error.
230: * @param message Message of the error.
231: */
232: public void setErrorMessage(int index, String message) {
233: if (index > 0)
234: errors[index - 1] = message;
235: }
236:
237: /**
238: * Returns the message for an error.
239: *
240: * @param index Index of the error.
241: *
242: * @return Message of the error.
243: */
244: public String getErrorMessage(int index) {
245: if (index == 0)
246: return "Unexpected token.";
247:
248: return errors[index - 1];
249: }
250:
251: /**
252: * Return the count of errors.
253: *
254: * @return Count of errors.
255: */
256: public int getErrorCount() {
257: return errors.length;
258: }
259:
260: /**
261: * Sets a error action for a given state and terminal symbol
262: *
263: * @param state Index of the state
264: * @param tsymbol Index of the terminal symbol
265: * @param nextstate Destination state
266: */
267: public void setErrorAction(int state, int tsymbol, int nextstate) {
268: if ((nextstate < 0) && (nextstate >= actions.length))
269: throw new IndexOutOfBoundsException();
270:
271: actions[state][tsymbol] = (ERROR | (nextstate << 2));
272: }
273:
274: /**
275: * Sets a error action for a given state and terminal symbol
276: *
277: * @param state Index of the state
278: * @param nextstate Destination state
279: */
280: public void setErrorAction(int state, int nextstate) {
281: if ((nextstate < 0) && (nextstate >= actions.length))
282: throw new IndexOutOfBoundsException();
283:
284: eofactions[state] = (ERROR | (nextstate << 2));
285: }
286:
287: /**
288: * Sets a shift action for a given state and terminal symbol
289: *
290: * @param state Index of the state
291: * @param tsymbol Index of the terminal symbol
292: * @param nextstate Destination state
293: */
294: public void setShiftAction(int state, int tsymbol, int nextstate) {
295: if ((nextstate < 0) && (nextstate >= actions.length))
296: throw new IndexOutOfBoundsException();
297:
298: actions[state][tsymbol] = (SHIFT | (nextstate << 2));
299: }
300:
301: /**
302: * Sets a reduce action for a given state and terminal symbol
303: *
304: * @param state Index of the state
305: * @param tsymbol Index of the terminal symbol
306: * @param production Index of the production, which should be reduced
307: */
308: public void setReduceAction(int state, int tsymbol, int production) {
309: if ((production < 0)
310: && (production >= productionsymbols.length))
311: throw new IndexOutOfBoundsException();
312:
313: actions[state][tsymbol] = (REDUCE | (production << 2));
314: }
315:
316: /**
317: * Set a reduce action for a given state and for the end of the file.
318: *
319: * @param state Index of state.
320: * @param production Production, which shoudl be reduced.
321: */
322: public void setReduceAction(int state, int production) {
323: if ((production < 0)
324: && (production >= productionsymbols.length))
325: throw new IndexOutOfBoundsException();
326:
327: eofactions[state] = (REDUCE | (production << 2));
328: }
329:
330: /**
331: * Sets a accept action for a given state and terminal symbol
332: *
333: * @param state Index of the state
334: * @param production Index of the production, which should be reduced
335: */
336: public void setAcceptAction(int state, int production) {
337: if ((production < 0)
338: && (production >= productionsymbols.length))
339: throw new IndexOutOfBoundsException();
340:
341: eofactions[state] = (ACCEPT | (production << 2));
342: }
343:
344: /**
345: * If is an error action
346: *
347: * @param state Index of the state
348: * @param tsymbol Index of the terminal symbol
349: *
350: * @return True, if it is a error action
351: */
352: public boolean isErrorAction(int state, int tsymbol) {
353: return (actions[state][tsymbol] & 3) == ERROR;
354: }
355:
356: /**
357: * If is a error action.
358: *
359: * @param state Index of the state
360: *
361: * @return True, if is an error action
362: */
363: public boolean isErrorAction(int state) {
364: return (eofactions[state] & 3) == ERROR;
365: }
366:
367: /**
368: * If is a shift action
369: *
370: * @param state Index of the state
371: * @param tsymbol Index of the terminal symbol
372: *
373: * @return True, if is a shift action
374: */
375: public boolean isShiftAction(int state, int tsymbol) {
376: return (actions[state][tsymbol] & 3) == SHIFT;
377: }
378:
379: /**
380: * If is a reduce action
381: *
382: * @param state Index of the state
383: * @param tsymbol Index of the terminal symbol
384: *
385: * @return True, if is a reduce action
386: */
387: public boolean isReduceAction(int state, int tsymbol) {
388: return (actions[state][tsymbol] & 3) == REDUCE;
389: }
390:
391: /**
392: * If is a reduce action.
393: *
394: * @param state Index of the state.
395: *
396: * @return True, if is a reduce action.
397: */
398: public boolean isReduceAction(int state) {
399: return (eofactions[state] & 3) == REDUCE;
400: }
401:
402: /**
403: * If is a accept action.
404: *
405: * @param state Index of the state
406: *
407: * @return True, if is a accept action
408: */
409: public boolean isAcceptAction(int state) {
410: return (eofactions[state] & 3) == ACCEPT;
411: }
412:
413: /**
414: * Returns the transition for a given state and terminal symbol.
415: *
416: * @param state Index of the state
417: * @param tsymbol Index of the terminal symbol.
418: *
419: * @return Index of destination state
420: */
421: public int getShiftTransition(int state, int tsymbol) {
422: if ((actions[state][tsymbol] & 3) != SHIFT)
423: throw new IllegalArgumentException(
424: "Action is not a 'shift' action");
425:
426: return actions[state][tsymbol] >> 2;
427: }
428:
429: /**
430: * Return for a given reduce action the production, which should be reduced.
431: *
432: * @param state Index of the state
433: * @param tsymbol Index of the terminal symbol
434: *
435: * @return Index of the production, which should be reduced
436: */
437: public int getReduceProduction(int state, int tsymbol) {
438: if ((actions[state][tsymbol] & 3) != REDUCE)
439: throw new IllegalArgumentException(
440: "Action is not a 'reduce' action");
441:
442: return actions[state][tsymbol] >> 2;
443: }
444:
445: /**
446: * Return the production, which should be reduced.
447: *
448: * @param state Index of the state.
449: *
450: * @return Index of the production.
451: */
452: public int getReduceProduction(int state) {
453: if (((eofactions[state] & 3) != REDUCE)
454: && ((eofactions[state] & 3) != ACCEPT))
455: throw new IllegalArgumentException(
456: "Action is not a 'reduce' action");
457:
458: return eofactions[state] >> 2;
459: }
460:
461: /**
462: * Return for a given error action the error message
463: *
464: * @param state Index of the state
465: * @param tsymbol Index of the terminal symbol
466: *
467: * @return Index of the state, to continue processing
468: */
469: public int getErrorTransition(int state, int tsymbol) {
470: if ((actions[state][tsymbol] & 3) != ERROR)
471: throw new IllegalArgumentException(
472: "Action is not a 'error' action");
473:
474: return actions[state][tsymbol] >> 2;
475: }
476:
477: /**
478: * Return index of the error.
479: *
480: * @param state Index of state.
481: *
482: * @return Index of error.
483: */
484: public int getErrorTransition(int state) {
485: if ((eofactions[state] & 3) != ERROR)
486: throw new IllegalArgumentException(
487: "Action is not a 'error' action");
488:
489: return eofactions[state] >> 2;
490: }
491:
492: /**
493: * Sets transition for a given state and nonterminal symbol.
494: *
495: * @param state Index of the state.
496: * @param ntsymbol Index of the nonterminal symbol.
497: * @param nextstate Index of destination state.
498: */
499: public void setTransition(int state, int ntsymbol, int nextstate) {
500: transitions[state][ntsymbol] = (nextstate);
501: }
502:
503: /**
504: * Returns the transition for a given state and nonterminal symbol.
505: *
506: * @param state Index of the state.
507: * @param ntsymbol Index of the nonterminal symbol.
508: *
509: * @return Index of destination state.
510: */
511: public int getTransition(int state, int ntsymbol) {
512: return transitions[state][ntsymbol];
513: }
514:
515: /**
516: * Returns the count of states.
517: *
518: * @return Count of states.
519: */
520: public int getStateCount() {
521: return actions.length;
522: }
523:
524: /**
525: * Return a string representation of the automaton.
526: *
527: * @return String representation of the automaton.
528: */
529: public String toString() {
530: int i;
531: int j;
532: java.text.DecimalFormat format = new java.text.DecimalFormat(
533: "00");
534: StringBuffer buffer = new StringBuffer();
535:
536: buffer.append("Terminal symbols:");
537: for (i = 0; i < tsymbols.length; i++) {
538: buffer.append(tsymbols[i]);
539: buffer.append("(");
540: buffer.append(String.valueOf(i));
541: buffer.append(") ");
542: }
543:
544: buffer.append("\n");
545:
546: buffer.append("Non terminal symbols:");
547: for (i = 0; i < ntsymbols.length; i++) {
548: buffer.append(ntsymbols[i]);
549: buffer.append("(");
550: buffer.append(String.valueOf(i));
551: buffer.append(") ");
552: }
553:
554: buffer.append("\n");
555:
556: int max = 0;
557:
558: for (i = 0; i < tsymbols.length; i++)
559: max = Math.max(max, tsymbols[i].length());
560:
561: for (i = 0; i < ntsymbols.length; i++)
562: max = Math.max(max, ntsymbols[i].length());
563:
564: max = Math.max(max, 3); // for EOF
565:
566: for (i = 0; i < max; i++) {
567: buffer.append(" ");
568: for (j = 0; j < tsymbols.length; j++)
569: if ((max - i - 1) < tsymbols[j].length()) {
570: buffer.append(tsymbols[j].charAt(max - i - 1));
571: buffer.append(" ");
572: } else
573: buffer.append(" ");
574:
575: if ((max - i - 1) < "EOF".length()) {
576: buffer.append("EOF".charAt(max - i - 1));
577: buffer.append(" ");
578: } else
579: buffer.append(" ");
580:
581: buffer.append(" ");
582:
583: for (j = 0; j < ntsymbols.length; j++)
584: if ((max - i - 1) < ntsymbols[j].length()) {
585: buffer.append(ntsymbols[j].charAt(max - i - 1));
586: buffer.append(" ");
587: } else
588: buffer.append(" ");
589:
590: buffer.append("\n");
591: }
592:
593: for (i = 0; i < actions.length; i++) {
594: buffer.append(format.format(i) + " ");
595: for (j = 0; j < actions[i].length; j++) {
596: if ((actions[i][j] & 3) == SHIFT) {
597: buffer.append("s");
598: buffer.append(format.format(actions[i][j] >> 2));
599: buffer.append(" ");
600: } else if ((actions[i][j] & 3) == REDUCE) {
601: buffer.append("r");
602: buffer.append(format.format(actions[i][j] >> 2));
603: buffer.append(" ");
604: } else if ((actions[i][j] & 3) == ERROR) {
605: if ((actions[i][j] >> 2) != 0) {
606: buffer.append("e");
607: buffer
608: .append(format
609: .format(actions[i][j] >> 2));
610: buffer.append(" ");
611: } else
612: buffer.append("--- ");
613: } else if ((actions[i][j] & 3) == ACCEPT) {
614: buffer.append("a");
615: buffer.append(format.format(actions[i][j] >> 2));
616: buffer.append(" ");
617: }
618: }
619:
620: if ((eofactions[i] & 3) == SHIFT) {
621: buffer.append("s");
622: buffer.append(format.format(eofactions[i] >> 2));
623: buffer.append(" ");
624: } else if ((eofactions[i] & 3) == REDUCE) {
625: buffer.append("r");
626: buffer.append(format.format(eofactions[i] >> 2));
627: buffer.append(" ");
628: } else if ((eofactions[i] & 3) == ERROR) {
629: if ((eofactions[i] >> 2) != 0) {
630: buffer.append("e");
631: buffer.append(format.format(eofactions[i] >> 2));
632: buffer.append(" ");
633: } else
634: buffer.append("--- ");
635: } else if ((eofactions[i] & 3) == ACCEPT) {
636: buffer.append("a");
637: buffer.append(format.format(eofactions[i] >> 2));
638: buffer.append(" ");
639: }
640:
641: buffer.append("| ");
642:
643: for (j = 0; j < transitions[i].length; j++)
644: if (transitions[i][j] > 0) {
645: buffer.append(format.format(transitions[i][j]));
646: buffer.append(" ");
647: } else
648: buffer.append("-- ");
649:
650: buffer.append("\n");
651: }
652:
653: return buffer.toString();
654: }
655: }
|