1 package fri.patterns.interpreter.parsergenerator.parsertables; 2 3 import java.util.*; 4 import java.io.PrintStream ; 5 import fri.patterns.interpreter.parsergenerator.Token; 6 import fri.patterns.interpreter.parsergenerator.syntax.*; 7 8 18 19 public class SLRParserTables extends AbstractParserTables 20 { 21 protected transient List syntaxNodes = new ArrayList(); 22 protected transient FirstSets firstSets; 23 protected transient FollowSets followSets; 24 25 26 30 public SLRParserTables(Syntax syntax) 31 throws ParserBuildException 32 { 33 this.syntax = addStartSymbol(syntax); getAllSymbols(); 35 init(); 36 } 37 38 39 40 protected void init() 41 throws ParserBuildException 42 { 43 syntaxNodes = new SLRSyntaxNode().build(syntax, syntaxNodes, new Hashtable()); 44 45 gotoTable = generateGoto(syntaxNodes); 46 47 Nullable nullAble = new Nullable(syntax, nonterminals); 48 firstSets = new FirstSets(syntax, nullAble, nonterminals); 49 followSets = new FollowSets(syntax, nullAble, firstSets); 50 51 parseTable = generateParseAction(syntaxNodes); 52 } 53 54 55 private Syntax addStartSymbol(Syntax syntax) 58 throws ParserBuildException 59 { 60 String startSym = null; 61 List startRules = syntax.findStartRules(); 62 63 if (startRules.size() <= 0) { Rule rule = syntax.getRule(0); 66 System.err.println("WARNING: Grammar has no top level rule, taking first rule >"+rule+"<"); 67 startSym = rule.getNonterminal(); 68 } 69 else 70 if (startRules.size() > 1) { for (int i = 0; i < startRules.size(); i++) { Rule r = (Rule) startRules.get(i); 73 String nt = r.getNonterminal(); 74 75 if (startSym == null) 76 startSym = nt; 77 else 78 if (startSym.equals(nt) == false) 79 throw new ParserBuildException("Grammar has more than one toplevel rules: "+startRules); 80 } 81 } 82 else { startSym = ((Rule) startRules.get(0)).getNonterminal(); 84 } 85 86 Rule start = new Rule("<START>", 1); 87 start.addRightSymbol(startSym); 88 syntax.insertRule(0, start); 89 90 return syntax; 91 } 92 93 94 95 protected List getAllSymbols() 96 throws ParserBuildException 97 { 98 for (int i = 0; i < syntax.size(); i++) { 100 Rule rule = syntax.getRule(i); 101 String nonterm = rule.getNonterminal(); 103 if (Nullable.isNull(nonterm)) 104 throw new ParserBuildException("ERROR: Empty nonterminal: >"+nonterm+"<"); 105 106 if (nonterminals.indexOf(nonterm) < 0) nonterminals.add(nonterm); 108 } 109 110 for (int j = 0; j < syntax.size(); j++) { 112 Rule rule = syntax.getRule(j); 113 114 for (int i = 0; i < rule.rightSize(); i++) { 115 String symbol = rule.getRightSymbol(i); 116 117 if (Nullable.isNull(symbol)) 118 throw new ParserBuildException("ERROR: Empty terminal: >"+symbol+"<"); 119 120 if (Token.isTerminal(symbol)) { 121 if (terminals.indexOf(symbol) < 0) { 122 terminals.add(symbol); 123 terminalsWithoutEpsilon.add(symbol); 124 } 125 } 126 else if (nonterminals.indexOf(symbol) < 0) 128 throw new ParserBuildException("ERROR: Every nonterminal must have a rule. symbol: >"+symbol+"<, rule: "+rule); 129 } 130 } 131 132 if (terminals.size() <= 0) 134 throw new ParserBuildException("ERROR: No terminal found: "+syntax); 135 136 if (nonterminals.size() <= 0) 137 throw new ParserBuildException("ERROR: No nonterminal found: "+syntax); 138 139 for (int i = 0; i < nonterminals.size(); i++) 141 symbols.add(nonterminals.get(i)); 142 143 for (int i = 0; i < terminals.size(); i++) 145 symbols.add(terminals.get(i)); 146 147 terminals.add(Token.EPSILON); 149 150 return symbols; 151 } 152 153 154 155 protected List generateGoto(List syntaxNodes) { 156 this.gotoTable = new ArrayList(syntaxNodes.size()); 158 159 Map hash = new Hashtable(syntaxNodes.size()); 160 161 for (int i = 0; i < syntaxNodes.size(); i++) { 162 SLRSyntaxNode node = (SLRSyntaxNode) syntaxNodes.get(i); 163 164 Map h = node.fillGotoLine(i); 165 166 if (h.size() <= 0) 167 gotoTable.add(null); 168 else 169 insertTableLine(i, h, gotoTable, hash); 170 } 171 172 return gotoTable; 173 } 174 175 176 179 protected List generateParseAction(List syntaxNodes) { 180 this.parseTable = new ArrayList(syntaxNodes.size()); 181 182 Map hash = new Hashtable(syntaxNodes.size()); 183 184 for (int i = 0; i < syntaxNodes.size(); i++) { 185 SLRSyntaxNode node = (SLRSyntaxNode) syntaxNodes.get(i); 186 187 Map h = node.fillParseActionLine(i, firstSets, followSets); 188 189 if (h.size() <= 0) 190 parseTable.add(null); 191 else 192 insertTableLine(i, h, parseTable, hash); 193 } 194 195 return parseTable; 196 } 197 198 199 203 protected void insertTableLine( 204 int i, 205 Map line, 206 List table, 207 Map hash) 208 { 209 Integer itg = (Integer ) hash.get(line); 210 if (itg == null) { 211 table.add(line); 212 hash.put(line, new Integer (i)); 213 } 214 else { 215 table.add(table.get(itg.intValue())); 216 } 217 } 218 219 220 221 222 public void freeSyntaxNodes() { 223 syntaxNodes = null; 224 symbols = null; 225 terminals = null; 226 } 227 228 229 230 232 233 public void report(PrintStream out) { 234 System.err.println("Parser Generator is "+getClass()); 235 super.report(out); 236 out.println("states: "+(syntaxNodes != null ? syntaxNodes.size() : -1)); 237 } 238 239 240 241 public void dump(PrintStream out) { 242 dumpSyntax(out); 243 dumpFirstSet(out); 244 dumpFollowSet(out); 245 dumpSyntaxNodes(out); 246 dumpGoto(out); 247 dumpParseAction(out); 248 } 249 250 public void dumpSyntaxNodes(PrintStream out) { 251 if (syntaxNodes != null) { 252 for (int i = 0; i < syntaxNodes.size(); i++) 253 dumpSyntaxNode(i, (SLRSyntaxNode) syntaxNodes.get(i), out); 254 out.println(); 255 } 256 } 257 258 public void dumpSyntaxNode(int i, SLRSyntaxNode node, PrintStream out) { 259 out.println("State "+i); 260 out.println(node.toString()); 261 } 262 263 public void dumpFirstSet(PrintStream out) { 264 if (firstSets != null) 265 dumpSet("FIRST", firstSets, out); 266 } 267 268 public void dumpFollowSet(PrintStream out) { 269 if (followSets != null) 270 dumpSet("FOLLOW", followSets, out); 271 } 272 273 public void dumpSet(String header, Map set, PrintStream out) { 274 for (Iterator it = set.keySet().iterator(); it.hasNext(); ) { 275 String nonterm = (String ) it.next(); 276 out.println(header+"("+nonterm+") = "+set.get(nonterm)); 277 } 278 out.println(); 279 } 280 281 282 283 284 public static void main(String [] args) { 285 String [][] syntax = { 286 { "EXPR", "TERM" }, 287 { "EXPR", "EXPR", "'+'", "TERM" }, 288 { "EXPR", "EXPR", "'-'", "TERM" }, 289 { "TERM", "FAKT", }, 290 { "TERM", "TERM", "'*'", "FAKT" }, 291 { "TERM", "TERM", "'/'", "FAKT" }, 292 { "FAKT", "`number`", }, 293 { "FAKT", "'('", "EXPR", "')'" }, 294 }; 295 296 try { 297 SLRParserTables p = new SLRParserTables(new Syntax(syntax)); 298 p.dump(System.err); 299 } 300 catch (Exception e) { 301 e.printStackTrace(); 302 } 303 } 304 305 } 306 307 | Popular Tags |