Java > Open Source Codes > net > sourceforge > chaperon > process > ParserAutomaton


1 /*
2  * Copyright (C) Chaperon. All rights reserved.
3  * -------------------------------------------------------------------------
4  * This software is published under the terms of the Apache Software License
5  * version 1.1, a copy of which has been included with this distribution in
6  * the LICENSE file.
7  */
8
9 package net.sourceforge.chaperon.process;
10
11 import java.io.Serializable ;
12
13 import java.util.Arrays ;
14
15 /**
16  * This class represents a parser automaton, which holds all states and transition, which are used
17  * by the the parser processor.
18  *
19  * @author <a HREF="mailto:stephan@apache.org">Stephan Michels </a>
20  * @version CVS $Id: ParserAutomaton.java,v 1.9 2003/12/09 19:55:53 benedikta Exp $
21  */
22 public class ParserAutomaton implements Serializable
23 {
24   // List of all terminal symbols
25 private String [] tsymbols;
26
27   // List of all non terminal symbols
28 private String [] ntsymbols;
29
30   // Indices of the non terminal symbols for the productions
31 private int[] productionsymbols;
32
33   // Lengths from the productions
34 private int[] productionlengths;
35
36   // Error messages
37 private String [] errors;
38
39   // ---------- Action ------------------------
40 // Actions, contains the type of action and the action argument
41 private int[][] actions;
42   private int[] eofactions;
43
44   /** Error action */
45   private static final int ERROR = 0;
46
47   /** Shift action */
48   private static final int SHIFT = 1;
49
50   /** Reduce action */
51   private static final int REDUCE = 2;
52
53   /** Accept action */
54   private static final int ACCEPT = 3;
55
56   // ---------- Goto --------------------------
57 // Transitions for the productions
58 private int[][] transitions;
59   private static final long serialVersionUID = 8045275977315821215L;
60
61   /**
62    * Constructs a empty parser automaton
63    *
64    * @param tsymbolcount Count of terminal symbols.
65    * @param ntsymbolcount Count of nonterminal symbols.
66    * @param productioncount Count of productions.
67    * @param errorcount Count of error types.
68    * @param statecount Count of states.
69    */
70   public ParserAutomaton(int tsymbolcount, int ntsymbolcount, int productioncount, int errorcount,
71                          int statecount)
72   {
73     tsymbols = new String [tsymbolcount];
74     Arrays.fill(tsymbols, "noname");
75
76     ntsymbols = new String [ntsymbolcount];
77     Arrays.fill(ntsymbols, "noname");
78
79     productionsymbols = new int[productioncount];
80     Arrays.fill(productionsymbols, 0);
81     productionlengths = new int[productioncount];
82     Arrays.fill(productionlengths, 0);
83
84     errors = new String [errorcount];
85     Arrays.fill(errors, "Unexpected token.");
86
87     actions = new int[statecount][tsymbolcount];
88     for (int i = 0; i<statecount; i++)
89       Arrays.fill(actions[i], ERROR);
90
91     eofactions = new int[statecount];
92     Arrays.fill(eofactions, ERROR);
93
94     transitions = new int[statecount][ntsymbolcount];
95     for (int i = 0; i<statecount; i++)
96       Arrays.fill(transitions[i], 0);
97   }
98
99   /**
100    * Sets the name of a terminal symbol.
101    *
102    * @param index Index of the symbol.
103    * @param symbol Name of the symbol.
104    */
105   public void setTerminal(int index, String symbol)
106   {
107     if ((index<0) || (index>=tsymbols.length))
108       throw new IndexOutOfBoundsException ();
109
110     tsymbols[index] = symbol;
111   }
112
113   /**
114    * Returns the name of a terminal symbol.
115    *
116    * @param index Index of the symbol.
117    *
118    * @return Name of the symbol.
119    */
120   public String getTerminal(int index)
121   {
122     if ((index<0) || (index>=tsymbols.length))
123       throw new IndexOutOfBoundsException ();
124
125     return tsymbols[index];
126   }
127
128   /**
129    * Returns the count of terminal symbols.
130    *
131    * @return Count of terminal symbols.
132    */
133   public int getTerminalCount()
134   {
135     return tsymbols.length;
136   }
137
138   /**
139    * Sets the name of a nonterminal symbol.
140    *
141    * @param index Index of the symbol.
142    * @param symbol Name of the symbol.
143    */
144   public void setNonterminal(int index, String symbol)
145   {
146     if ((index<0) || (index>=ntsymbols.length))
147       throw new IndexOutOfBoundsException ();
148
149     ntsymbols[index] = symbol;
150   }
151
152   /**
153    * Returns the name of a nonterminal symbol.
154    *
155    * @param index Index of the symbol.
156    *
157    * @return Name of the symbol.
158    */
159   public String getNonterminal(int index)
160   {
161     if ((index<0) || (index>=ntsymbols.length))
162       throw new IndexOutOfBoundsException ();
163
164     return ntsymbols[index];
165   }
166
167   /**
168    * Returns the count of nonterminal symbols.
169    *
170    * @return Count of nonterminal symbols.
171    */
172   public int getNonterminalCount()
173   {
174     return ntsymbols.length;
175   }
176
177   /**
178    * Sets the symbol for a production
179    *
180    * @param index Index of the production
181    * @param symbolindex Index of the nonterminal symbol
182    */
183   public void setProductionSymbol(int index, int symbol)
184   {
185     if ((symbol<0) || (symbol>=ntsymbols.length))
186       throw new IndexOutOfBoundsException ();
187
188     productionsymbols[index] = symbol;
189   }
190
191   /**
192    * Return the symbol of a production.
193    *
194    * @param index Index of the production.
195    *
196    * @return Index of the nonterminal symbol
197    */
198   public int getProductionSymbol(int index)
199   {
200     return productionsymbols[index];
201   }
202
203   /**
204    * Set the length of a production.
205    *
206    * @param index Index of the production.
207    * @param length Length of the production.
208    */
209   public void setProductionLength(int index, int length)
210   {
211     if (length<0)
212       throw new IllegalArgumentException ();
213
214     productionlengths[index] = length;
215   }
216
217   /**
218    * Return the length of a production.
219    *
220    * @param index Index of a production.
221    *
222    * @return Length of the production.
223    */
224   public int getProductionLength(int index)
225   {
226     return productionlengths[index];
227   }
228
229   /**
230    * Return the count of productions.
231    *
232    * @return Count of productions.
233    */
234   public int getProductionCount()
235   {
236     return productionsymbols.length;
237   }
238
239   /**
240    * Sets the message for an error.
241    *
242    * @param index Index of the error.
243    * @param message Message of the error.
244    */
245   public void setErrorMessage(int index, String message)
246   {
247     if (index>0)
248       errors[index-1] = message;
249   }
250
251   /**
252    * Returns the message for an error.
253    *
254    * @param index Index of the error.
255    *
256    * @return Message of the error.
257    */
258   public String getErrorMessage(int index)
259   {
260     if (index==0)
261       return "Unexpected token.";
262
263     return errors[index-1];
264   }
265
266   /**
267    * Return the count of errors.
268    *
269    * @return Count of errors.
270    */
271   public int getErrorCount()
272   {
273     return errors.length;
274   }
275
276   /**
277    * Sets a error action for a given state and terminal symbol
278    *
279    * @param state Index of the state
280    * @param tsymbol Index of the terminal symbol
281    * @param nextstate Destination state
282    */
283   public void setErrorAction(int state, int tsymbol, int nextstate)
284   {
285     if ((nextstate<0) && (nextstate>=actions.length))
286       throw new IndexOutOfBoundsException ();
287
288     actions[state][tsymbol] = (ERROR|(nextstate<<2));
289   }
290
291   /**
292    * Sets a error action for a given state and terminal symbol
293    *
294    * @param state Index of the state
295    * @param nextstate Destination state
296    */
297   public void setErrorAction(int state, int nextstate)
298   {
299     if ((nextstate<0) && (nextstate>=actions.length))
300       throw new IndexOutOfBoundsException ();
301
302     eofactions[state] = (ERROR|(nextstate<<2));
303   }
304
305   /**
306    * Sets a shift action for a given state and terminal symbol
307    *
308    * @param state Index of the state
309    * @param tsymbol Index of the terminal symbol
310    * @param nextstate Destination state
311    */
312   public void setShiftAction(int state, int tsymbol, int nextstate)
313   {
314     if ((nextstate<0) && (nextstate>=actions.length))
315       throw new IndexOutOfBoundsException ();
316
317     actions[state][tsymbol] = (SHIFT|(nextstate<<2));
318   }
319
320   /**
321    * Sets a reduce action for a given state and terminal symbol
322    *
323    * @param state Index of the state
324    * @param tsymbol Index of the terminal symbol
325    * @param production Index of the production, which should be reduced
326    */
327   public void setReduceAction(int state, int tsymbol, int production)
328   {
329     if ((production<0) && (production>=productionsymbols.length))
330       throw new IndexOutOfBoundsException ();
331
332     actions[state][tsymbol] = (REDUCE|(production<<2));
333   }
334
335   /**
336    * Set a reduce action for a given state and for the end of the file.
337    *
338    * @param state Index of state.
339    * @param production Production, which shoudl be reduced.
340    */
341   public void setReduceAction(int state, int production)
342   {
343     if ((production<0) && (production>=productionsymbols.length))
344       throw new IndexOutOfBoundsException ();
345
346     eofactions[state] = (REDUCE|(production<<2));
347   }
348
349   /**
350    * Sets a accept action for a given state and terminal symbol
351    *
352    * @param state Index of the state
353    * @param production Index of the production, which should be reduced
354    */
355   public void setAcceptAction(int state, int production)
356   {
357     if ((production<0) && (production>=productionsymbols.length))
358       throw new IndexOutOfBoundsException ();
359
360     eofactions[state] = (ACCEPT|(production<<2));
361   }
362
363   /**
364    * If is an error action
365    *
366    * @param state Index of the state
367    * @param tsymbol Index of the terminal symbol
368    *
369    * @return True, if it is a error action
370    */
371   public boolean isErrorAction(int state, int tsymbol)
372   {
373     return (actions[state][tsymbol]&3)==ERROR;
374   }
375
376   /**
377    * If is a error action.
378    *
379    * @param state Index of the state
380    *
381    * @return True, if is an error action
382    */
383   public boolean isErrorAction(int state)
384   {
385     return (eofactions[state]&3)==ERROR;
386   }
387
388   /**
389    * If is a shift action
390    *
391    * @param state Index of the state
392    * @param tsymbol Index of the terminal symbol
393    *
394    * @return True, if is a shift action
395    */
396   public boolean isShiftAction(int state, int tsymbol)
397   {
398     return (actions[state][tsymbol]&3)==SHIFT;
399   }
400
401   /**
402    * If is a reduce action
403    *
404    * @param state Index of the state
405    * @param tsymbol Index of the terminal symbol
406    *
407    * @return True, if is a reduce action
408    */
409   public boolean isReduceAction(int state, int tsymbol)
410   {
411     return (actions[state][tsymbol]&3)==REDUCE;
412   }
413
414   /**
415    * If is a reduce action.
416    *
417    * @param state Index of the state.
418    *
419    * @return True, if is a reduce action.
420    */
421   public boolean isReduceAction(int state)
422   {
423     return (eofactions[state]&3)==REDUCE;
424   }
425
426   /**
427    * If is a accept action.
428    *
429    * @param state Index of the state
430    *
431    * @return True, if is a accept action
432    */
433   public boolean isAcceptAction(int state)
434   {
435     return (eofactions[state]&3)==ACCEPT;
436   }
437
438   /**
439    * Returns the transition for a given state and terminal symbol.
440    *
441    * @param state Index of the state
442    * @param tsymbol Index of the terminal symbol.
443    *
444    * @return Index of destination state
445    */
446   public int getShiftTransition(int state, int tsymbol)
447   {
448     if ((actions[state][tsymbol]&3)!=SHIFT)
449       throw new IllegalArgumentException ("Action is not a 'shift' action");
450
451     return actions[state][tsymbol]>>2;
452   }
453
454   /**
455    * Return for a given reduce action the production, which should be reduced.
456    *
457    * @param state Index of the state
458    * @param tsymbol Index of the terminal symbol
459    *
460    * @return Index of the production, which should be reduced
461    */
462   public int getReduceProduction(int state, int tsymbol)
463   {
464     if ((actions[state][tsymbol]&3)!=REDUCE)
465       throw new IllegalArgumentException ("Action is not a 'reduce' action");
466
467     return actions[state][tsymbol]>>2;
468   }
469
470   /**
471    * Return the production, which should be reduced.
472    *
473    * @param state Index of the state.
474    *
475    * @return Index of the production.
476    */
477   public int getReduceProduction(int state)
478   {
479     if (((eofactions[state]&3)!=REDUCE) && ((eofactions[state]&3)!=ACCEPT))
480       throw new IllegalArgumentException ("Action is not a 'reduce' action");
481
482     return eofactions[state]>>2;
483   }
484
485   /**
486    * Return for a given error action the error message
487    *
488    * @param state Index of the state
489    * @param tsymbol Index of the terminal symbol
490    *
491    * @return Index of the state, to continue processing
492    */
493   public int getErrorTransition(int state, int tsymbol)
494   {
495     if ((actions[state][tsymbol]&3)!=ERROR)
496       throw new IllegalArgumentException ("Action is not a 'error' action");
497
498     return actions[state][tsymbol]>>2;
499   }
500
501   /**
502    * Return index of the error.
503    *
504    * @param state Index of state.
505    *
506    * @return Index of error.
507    */
508   public int getErrorTransition(int state)
509   {
510     if ((eofactions[state]&3)!=ERROR)
511       throw new IllegalArgumentException ("Action is not a 'error' action");
512
513     return eofactions[state]>>2;
514   }
515
516   /**
517    * Sets transition for a given state and nonterminal symbol.
518    *
519    * @param state Index of the state.
520    * @param ntsymbol Index of the nonterminal symbol.
521    * @param nextstate Index of destination state.
522    */
523   public void setTransition(int state, int ntsymbol, int nextstate)
524   {
525     transitions[state][ntsymbol] = (nextstate);
526   }
527
528   /**
529    * Returns the transition for a given state and nonterminal symbol.
530    *
531    * @param state Index of the state.
532    * @param ntsymbol Index of the nonterminal symbol.
533    *
534    * @return Index of destination state.
535    */
536   public int getTransition(int state, int ntsymbol)
537   {
538     return transitions[state][ntsymbol];
539   }
540
541   /**
542    * Returns the count of states.
543    *
544    * @return Count of states.
545    */
546   public int getStateCount()
547   {
548     return actions.length;
549   }
550
551   /**
552    * Return a string representation of the automaton.
553    *
554    * @return String representation of the automaton.
555    */
556   public String toString()
557   {
558     int i;
559     int j;
560     java.text.DecimalFormat format = new java.text.DecimalFormat ("00");
561     StringBuffer buffer = new StringBuffer ();
562
563     buffer.append("Terminal symbols:");
564     for (i = 0; i<tsymbols.length; i++)
565     {
566       buffer.append(tsymbols[i]);
567       buffer.append("(");
568       buffer.append(String.valueOf(i));
569       buffer.append(") ");
570     }
571
572     buffer.append("\n");
573
574     buffer.append("Non terminal symbols:");
575     for (i = 0; i<ntsymbols.length; i++)
576     {
577       buffer.append(ntsymbols[i]);
578       buffer.append("(");
579       buffer.append(String.valueOf(i));
580       buffer.append(") ");
581     }
582
583     buffer.append("\n");
584
585     int max = 0;
586
587     for (i = 0; i<tsymbols.length; i++)
588       max = Math.max(max, tsymbols[i].length());
589
590     for (i = 0; i<ntsymbols.length; i++)
591       max = Math.max(max, ntsymbols[i].length());
592
593     max = Math.max(max, 3); // for EOF
594
595     for (i = 0; i<max; i++)
596     {
597       buffer.append(" ");
598       for (j = 0; j<tsymbols.length; j++)
599         if ((max-i-1)<tsymbols[j].length())
600         {
601           buffer.append(tsymbols[j].charAt(max-i-1));
602           buffer.append(" ");
603         }
604         else
605           buffer.append(" ");
606
607       if ((max-i-1)<"EOF".length())
608       {
609         buffer.append("EOF".charAt(max-i-1));
610         buffer.append(" ");
611       }
612       else
613         buffer.append(" ");
614
615       buffer.append(" ");
616
617       for (j = 0; j<ntsymbols.length; j++)
618         if ((max-i-1)<ntsymbols[j].length())
619         {
620           buffer.append(ntsymbols[j].charAt(max-i-1));
621           buffer.append(" ");
622         }
623         else
624           buffer.append(" ");
625
626       buffer.append("\n");
627     }
628
629     for (i = 0; i<actions.length; i++)
630     {
631       buffer.append(format.format(i)+" ");
632       for (j = 0; j<actions[i].length; j++)
633       {
634         if ((actions[i][j]&3)==SHIFT)
635         {
636           buffer.append("s");
637           buffer.append(format.format(actions[i][j]>>2));
638           buffer.append(" ");
639         }
640         else if ((actions[i][j]&3)==REDUCE)
641         {
642           buffer.append("r");
643           buffer.append(format.format(actions[i][j]>>2));
644           buffer.append(" ");
645         }
646         else if ((actions[i][j]&3)==ERROR)
647         {
648           if ((actions[i][j]>>2)!=0)
649           {
650             buffer.append("e");
651             buffer.append(format.format(actions[i][j]>>2));
652             buffer.append(" ");
653           }
654           else
655             buffer.append("--- ");
656         }
657         else if ((actions[i][j]&3)==ACCEPT)
658         {
659           buffer.append("a");
660           buffer.append(format.format(actions[i][j]>>2));
661           buffer.append(" ");
662         }
663       }
664
665       if ((eofactions[i]&3)==SHIFT)
666       {
667         buffer.append("s");
668         buffer.append(format.format(eofactions[i]>>2));
669         buffer.append(" ");
670       }
671       else if ((eofactions[i]&3)==REDUCE)
672       {
673         buffer.append("r");
674         buffer.append(format.format(eofactions[i]>>2));
675         buffer.append(" ");
676       }
677       else if ((eofactions[i]&3)==ERROR)
678       {
679         if ((eofactions[i]>>2)!=0)
680         {
681           buffer.append("e");
682           buffer.append(format.format(eofactions[i]>>2));
683           buffer.append(" ");
684         }
685         else
686           buffer.append("--- ");
687       }
688       else if ((eofactions[i]&3)==ACCEPT)
689       {
690         buffer.append("a");
691         buffer.append(format.format(eofactions[i]>>2));
692         buffer.append(" ");
693       }
694
695       buffer.append("| ");
696
697       for (j = 0; j<transitions[i].length; j++)
698         if (transitions[i][j]>0)
699         {
700           buffer.append(format.format(transitions[i][j]));
701           buffer.append(" ");
702         }
703         else
704           buffer.append("-- ");
705
706       buffer.append("\n");
707     }
708
709     return buffer.toString();
710   }
711 }
712

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags