1 package ro.infoiasi.donald.compiler.parser; 2 3 import ro.infoiasi.donald.compiler.cfg.*; 4 import java.io.*; 5 import java.util.*; 6 7 public class SLR1Parser extends AbstractLR1Parser { 8 public SLR1Parser(ParserSpec spec) { 9 super(spec); 10 } 11 12 public SLR1Parser(String parserSpecPath) 13 throws IOException, SpecParseException { 14 super(parserSpecPath); 15 } 17 18 public void precompute() { 19 g.computeFollow(); 20 21 LR0States states = new LR0States(); 22 List actionList = new LinkedList(); 23 List gotoList = new LinkedList(); 24 25 LR0State startState = new LR0State(); 26 startState.addKernelItem(new LR0Item(sp)); 27 startState.closure(p); 28 29 states.add(startState); 30 31 ParseAction[] actionLine = new ParseAction[t.count()]; 32 Integer [] gotoLine = new Integer [v.count()]; 33 34 actionList.add(actionLine); 35 gotoList.add(gotoLine); 36 37 int i = 0; 38 while (i<states.size()) { 39 LR0State state = states.find(i); 40 for (int sid = 0; sid<g.symbolCount(); sid++) { 41 LR0State newState = new LR0State(); 42 Symbol sym = g.symbol(sid); 43 if (sym == s) continue; 44 Iterator it = state.iterator(sym); 45 while (it.hasNext()) { 46 LR0Item item = (LR0Item)it.next(); 47 newState.addKernelItem(item.nextItem()); 48 } 49 if (!newState.isEmpty()) { 50 LR0State oldState = states.find(newState.getKernelItems()); 51 if (oldState == null) { 52 newState.closure(p); 53 states.add(newState); 54 55 actionLine = new ParseAction[t.count()]; 56 gotoLine = new Integer [v.count()]; 57 58 Iterator it2 = newState.iterator(); 60 while (it2.hasNext()) { 61 LR0Item item = (LR0Item)it2.next(); 62 if (item.isComplete()) { 63 Production prod = item.getProduction(); 64 Set follow = g.follow(prod.getLHS()); 65 Iterator followIt = follow.iterator(); 66 while (followIt.hasNext()) { 67 Terminal a = (Terminal)followIt.next(); 68 if (actionLine[a.getIndex()] == null) { 69 actionLine[a.getIndex()] = new ReduceAction(prod); 70 } else { 71 throw new RuntimeException ( 72 "Grammar not SLR(1). \nReduce-Reduce conflict: "+ 73 state+"\nState: "+newState+"\nTerminal: "+a+ 74 "\nProduction 1: "+actionLine[a.getIndex()]+ 75 "\nProduction 2: "+prod); 76 } 77 } 78 } 79 } 80 81 actionList.add(actionLine); 82 gotoList.add(gotoLine); 83 } else { 84 newState = oldState; 85 } 86 87 actionLine = (ParseAction[])actionList.get(state.getIndex()); 88 gotoLine = (Integer [])gotoList.get(state.getIndex()); 89 90 if (sym.isTerminal()) { 91 Terminal a = (Terminal)sym; 92 if (actionLine[a.getIndex()] == null) { 93 actionLine[a.getIndex()] = new ShiftAction( 94 new Integer (newState.getIndex())); 95 } else { 96 throw new RuntimeException ( 97 "Grammar not SLR(1). \nShift-Reduce conflict: "+ 98 state+"\nState: "+state+"\nTerminal: "+a+ 99 "\nProduction: "+actionLine[a.getIndex()]+ 100 "\nShift state: "+newState); 101 } 102 } else { 103 NonTerminal x = (NonTerminal)sym; 104 gotoLine[x.getIndex()] = new Integer (newState.getIndex()); 105 } 106 } 107 } 108 i++; 109 } 110 111 startStateIndex = new Integer (startState.getIndex()); 112 113 stateNo = states.size(); 114 actionTable = new ParseAction[stateNo][]; 115 gotoTable = new Integer [stateNo][]; 116 for (int k = 0; k<stateNo; k++) { 117 actionTable[k] = (ParseAction[])actionList.get(k); 118 gotoTable[k] = (Integer [])gotoList.get(k); 119 } 120 121 if (DEBUG) { 122 System.out.println(states); 123 System.out.println("start: "+startStateIndex); 124 } 125 } 126 127 public static void main(String args[]) throws Exception { 128 if (args.length != 3) { 129 System.err.println("args: <grammar_file> <lexer_class> <input_file>"); 130 System.exit(1); 131 } 132 133 Parser parser = new SLR1Parser(args[0]); 134 System.out.println(parser.getGrammar()); 135 parser.precompute(); 136 parser.setLexer(args[1], args[2]); 137 List pi = parser.parse(); 138 Iterator it = pi.iterator(); 139 while (it.hasNext()) { 140 System.out.println(it.next()+";"); 141 } 142 } 143 } 144 | Popular Tags |