KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > net > sourceforge > chaperon > build > FollowSetCollection


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.build;
10
11 import net.sourceforge.chaperon.model.grammar.Grammar;
12 import net.sourceforge.chaperon.model.symbol.Symbol;
13 import net.sourceforge.chaperon.model.symbol.SymbolList;
14 import net.sourceforge.chaperon.model.symbol.SymbolSet;
15
16 import org.apache.commons.logging.Log;
17
18 /**
19  * This class creates a collection of FOLLOW sets.
20  *
21  * @author <a HREF="mailto:stephan@apache.org">Stephan Michels</a>
22  * @version CVS $Id: FollowSetCollection.java,v 1.5 2003/12/09 19:55:53 benedikta Exp $
23  */
24 public class FollowSetCollection
25 {
26   private Grammar grammar;
27   private FirstSetCollection firstsets;
28   private Symbol[] symbols;
29   private SymbolSet[] followsets;
30   private Log log;
31   private static final EmptyList EMPTYLIST = new EmptyList();
32
33   /**
34    * Create a collection of FOLLOW sets.
35    *
36    * @param grammar Grammar.
37    */
38   public FollowSetCollection(Grammar grammar, FirstSetCollection firstsets)
39   {
40     this(grammar, firstsets, null);
41   }
42
43   /**
44    * Create a collection of FOLLOW sets
45    *
46    * @param grammar Grammar
47    * @param log Log, whch should be used.
48    */
49   public FollowSetCollection(Grammar grammar, FirstSetCollection firstsets, Log log)
50   {
51     this.grammar = grammar;
52     this.firstsets = firstsets;
53     this.log = log;
54
55     SymbolSet usedsymbols = grammar.getSymbols();
56
57     symbols = new Symbol[usedsymbols.getSymbolCount()];
58     followsets = new SymbolSet[usedsymbols.getSymbolCount()];
59     for (int i = 0; i<usedsymbols.getSymbolCount(); i++)
60     {
61       if (log!=null)
62         log.debug("Generating follow set for "+usedsymbols.getSymbol(i).getName());
63
64       symbols[i] = usedsymbols.getSymbol(i);
65       followsets[i] = follow(symbols[i]);
66     }
67   }
68
69   /**
70    * Returns the FOLLOW set for a symbol.
71    *
72    * @param symbol Symbol.
73    *
74    * @return Set of symbols.
75    */
76   public SymbolSet getFollowSet(Symbol symbol)
77   {
78     for (int i = 0; i<symbols.length; i++)
79       if (symbols[i].equals(symbol))
80         return followsets[i];
81
82     throw new IllegalArgumentException JavaDoc("No follow set found for symbol");
83   }
84
85   /**
86    * Calculates the FOLLOW set. The FOLLOW set is the set of terminal symbols, which come as next
87    * symbol
88    *
89    * @param symbol Symbol.
90    *
91    * @return Set of symbol.
92    */
93   private SymbolSet follow(Symbol symbol)
94   {
95     System.out.println();
96     System.out.println("Calculate FOLLOW set for "+symbol);
97
98     SymbolSet followset = new SymbolSet();
99
100     // if symbol is start symbol, then add symbol for end of file
101 if (symbol.equals(grammar.getStartSymbol()))
102       followset.addSymbol(new EndOfFile());
103
104     // if production A -> a B b exists, then add every symbol of
105 // FIRST(b) except the symbol for an empty list to FOLLOW(B)
106 SymbolList definition;
107     for (int production = 0; production<grammar.getProductionCount(); production++)
108     {
109       definition = grammar.getProduction(production).getDefinition();
110       for (int position = 0; position<definition.getSymbolCount(); position++)
111         if (definition.getSymbol(position).equals(symbol))
112         {
113           System.out.println("Found "+symbol+" at position "+position+" in production "+production);
114
115           SymbolSet firstset = null;
116           if ((position+1)<definition.getSymbolCount())
117           {
118             SymbolList rest = new SymbolList();
119             for (int restposition = position+1; restposition<definition.getSymbolCount();
120                  restposition++)
121               rest.addSymbol(definition.getSymbol(restposition));
122
123             firstset = firstsets.getFirstSet(rest);
124
125             System.out.println("first("+rest+")="+firstset);
126
127             followset.addSymbol(firstset);
128             followset.removeSymbol(EMPTYLIST);
129           }
130
131           if ((position+1)==definition.getSymbolCount())
132             System.out.println(symbol+" is last symbol of production "+production);
133
134           // if a production A -> a B or A -> a B b exist and FIRST(b)
135 // contains the symbol for an empty list, then every symbol
136 // of FOLLOW(A) belongs to FOLLOW(B)
137 if ((((position+1)==definition.getSymbolCount()) || (firstset.contains(EMPTYLIST))) &&
138               (!grammar.getProduction(production).getSymbol().equals(symbol)))
139             followset.addSymbol(follow(grammar.getProduction(production).getSymbol()));
140         }
141     }
142
143     return followset;
144   }
145
146   /**
147    * Return a string representation of the FOLLOW sets.
148    *
149    * @return String representation of the FOLLOW sets.
150    */
151   public String JavaDoc toString()
152   {
153     StringBuffer JavaDoc buffer = new StringBuffer JavaDoc();
154
155     SymbolSet symbols = grammar.getSymbols();
156
157     for (int symbol = 0; symbol<symbols.getSymbolCount(); symbol++)
158     {
159       buffer.append("follow(");
160       buffer.append(symbols.getSymbol(symbol).toString());
161       buffer.append(")=");
162       buffer.append(getFollowSet(symbols.getSymbol(symbol)).toString());
163       buffer.append("\n");
164     }
165
166     return buffer.toString();
167   }
168 }
169
Popular Tags