|
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 |
Java API By Example, From Geeks To Geeks.