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 24 25 class FirstSets extends UniqueAggregatingHashtable 26 { 27 35 public FirstSets(Syntax syntax, Nullable nullAble, List nonterminals) 36 throws ParserBuildException 37 { 38 Map done = new Hashtable(nonterminals.size()); for (int i = 0; i < nonterminals.size(); i++) { 42 String nonterm = (String ) nonterminals.get(i); 43 generateFirstSet(syntax, nullAble, nonterm, done); 44 } 45 } 46 47 private void generateFirstSet(Syntax syntax, Nullable nullAble, String nonterminal, Map done) 48 throws ParserBuildException 49 { 50 if (get(nonterminal) != null) 51 return; 53 if (done.get(nonterminal) != null) 54 return; 55 done.put(nonterminal, nonterminal); 58 for (int k = 0; k < syntax.size(); k++) { 62 Rule rule = syntax.getRule(k); 63 String nonterm = rule.getNonterminal(); 65 if (nonterminal.equals(nonterm)) { if (rule.rightSize() <= 0) { 68 put(nonterm, Nullable.NULL); 69 } 70 else { boolean nullable = true; 73 for (int i = 0; nullable && i < rule.rightSize(); i++) { 76 String symbol = rule.getRightSymbol(i); 77 78 nullable = false; 80 if (Token.isTerminal(symbol)) { 81 put(nonterm, symbol); 82 } 83 else { 84 try { 87 generateFirstSet(syntax, nullAble, symbol, done); 89 List list = (List) get(symbol); for (int j = 0; list != null && j < list.size(); j++) { 91 String s = (String ) list.get(j); 92 put(nonterm, s); 93 } 94 95 nullable = nullAble.isNullable(symbol); 96 } 97 catch (Exception ex) { 98 throw new ParserBuildException(ex.getMessage()+" <- "+nonterm); 99 } 100 } } 103 109 } } } 112 } 113 114 115 public Object put(Object key, Object value) { 116 if (key.equals(value)) 117 throw new IllegalArgumentException ("Can not be FIRST of its own: key="+key+", value="+value); 118 119 return super.put(key, value); 120 } 121 122 123 124 125 public static void main(String [] args) { 126 List nonterm = new ArrayList(); 128 nonterm.add("S"); nonterm.add("T"); nonterm.add("F"); nonterm.add("L"); 129 130 List sx = new ArrayList(); 132 133 List r = new ArrayList(); 134 r.add("S"); r.add("T"); r.add("'*'"); r.add("F"); 135 sx.add(r); 136 137 r = new ArrayList(); 138 r.add("S"); r.add("T"); 139 sx.add(r); 140 141 r = new ArrayList(); 142 r.add("T"); r.add("F"); 143 sx.add(r); 144 145 146 r = new ArrayList(); 147 r.add("F"); 148 sx.add(r); 149 150 r = new ArrayList(); 151 r.add("F"); 152 r.add("'1'"); 153 sx.add(r); 154 155 Syntax syntax = new Syntax(sx); 156 try { 157 FirstSets f = new FirstSets(syntax, new Nullable(syntax, nonterm), nonterm); 158 String s = "S"; 159 System.err.println("FIRST("+s+") = "+f.get(s)); 160 } 161 catch (Exception e) { 162 e.printStackTrace(); 163 } 164 } 165 166 } | Popular Tags |