1 package fri.patterns.interpreter.parsergenerator.parsertables; 2 3 import java.util.*; 4 import fri.util.collections.UniqueAggregatingHashtable; 5 import fri.patterns.interpreter.parsergenerator.Token; 6 import fri.patterns.interpreter.parsergenerator.syntax.*; 7 8 25 26 class FollowSets extends UniqueAggregatingHashtable 27 { 28 36 public FollowSets(Syntax syntax, Nullable nullAble, FirstSets firstSets) 37 throws ParserBuildException 38 { 39 generateFollow(syntax, nullAble, firstSets); 41 42 resolveSets(); 44 } 45 46 private void generateFollow(Syntax syntax, Nullable nullAble, FirstSets firstSets) { 47 51 for (int rulePos = 0; rulePos < syntax.size(); rulePos++) { 53 Rule rule = syntax.getRule(rulePos); 54 String nonterm = rule.getNonterminal(); 56 if (rulePos == 0) { put(nonterm, Token.EPSILON); 58 put(rule.getRightSymbol(0), Token.EPSILON); 60 } 61 else { 62 List nonterms = new ArrayList(); 64 for (int i = 0; i < rule.rightSize(); i++) { 65 String symbol = rule.getRightSymbol(i); 66 boolean isTerminal = Token.isTerminal(symbol); 67 68 if (nonterms.size() > 0) { List l; 71 if (isTerminal) { 72 l = new ArrayList(); 73 l.add(symbol); } 75 else { 76 l = (List) firstSets.get(symbol); } 78 addToAllFollowSets(nonterms, l); 80 } 81 82 if (isTerminal || nullAble.isNullable(symbol) == false) { nonterms.clear(); } 85 86 if (isTerminal == false) { nonterms.add(symbol); 88 89 if (i == rule.rightSize() - 1) { List l = new ArrayList(); 92 l.add(nonterm); 93 addToAllFollowSets(nonterms, l); 94 } 95 } 96 } } } } 100 101 private void addToAllFollowSets(List nonterms, List symbols) { 102 for (int i = 0; i < nonterms.size(); i++) { 103 String nt = (String ) nonterms.get(i); 104 105 for (int j = 0; j < symbols.size(); j++) { 106 String s = (String ) symbols.get(j); 107 108 if (Nullable.isNull(s) == false) put(nt, s); 110 } 111 } 112 } 113 114 115 private void resolveSets() 116 throws ParserBuildException 117 { 118 for (Enumeration e = keys(); e.hasMoreElements(); ) { 120 String key = (String ) e.nextElement(); 121 List newList = resolveSetSymbol(key, new Hashtable()); 123 replace(key, newList); 124 } 125 } 126 127 private List resolveSetSymbol(String nonterm, Map done) 128 throws ParserBuildException 129 { 130 if (done.get(nonterm) != null) 131 return null; 132 done.put(nonterm, nonterm); 134 List values = (List) get(nonterm); 135 List newList = new ArrayList(values.size() * 2); 136 137 for (int j = 0; j < values.size(); j++) { 138 String symbol = (String ) values.get(j); 139 140 if (Token.isTerminal(symbol) == false) { try { 142 List l = resolveSetSymbol(symbol, done); 143 for (int i = 0; l != null && i < l.size(); i++) { 144 String s = (String ) l.get(i); 145 if (newList.indexOf(s) < 0) 146 newList.add(s); 147 } 148 } 149 catch (Exception ex) { 150 throw new ParserBuildException("FOLLOW set error: "+ex.getMessage()+" <- "+symbol); 151 } 152 } 153 else { if (newList.indexOf(symbol) < 0) 155 newList.add(symbol); 156 } 157 } 158 return newList; 159 } 160 161 162 163 public Object put(Object key, Object value) { 164 if (key.equals(value)) 165 throw new IllegalArgumentException ("Can not be FOLLOW of its own: key="+key+", value="+value); 166 167 return super.put(key, value); 168 } 169 170 171 172 173 public static void main(String [] args) { 174 List nt = new ArrayList(); 175 nt.add("S"); nt.add("T"); nt.add("F"); nt.add("L"); 176 177 List sx = new ArrayList(); 178 179 List r = new ArrayList(); 180 r.add("S"); r.add("E"); 181 sx.add(r); 182 183 r = new ArrayList(); 184 r.add("E"); r.add("T"); r.add("'*'"); r.add("F"); 185 sx.add(r); 186 187 r = new ArrayList(); 188 r.add("E"); r.add("T"); 189 sx.add(r); 190 191 r = new ArrayList(); 192 r.add("T"); r.add("F"); 193 sx.add(r); 194 195 r = new ArrayList(); 196 r.add("F"); r.add("'1'"); 197 sx.add(r); 198 199 Syntax syntax = new Syntax(sx); 200 try { 201 Nullable nullAble = new Nullable(syntax, nt); 202 FollowSets f = new FollowSets(syntax, nullAble, new FirstSets(syntax, nullAble, nt)); 203 String s = "T"; 204 System.err.println("FOLLOW("+s+") = "+f.get(s)); 205 } 206 catch (Exception e) { 207 e.printStackTrace(); 208 } 209 } 210 211 } | Popular Tags |