|
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 LR0Parser extends AbstractParser {
8 public LR0Parser(ParserSpec spec) {
9 super(spec, true);
10 }
11
12 public LR0Parser(String  parserSpecPath)
13 throws IOException, SpecParseException {
14 super(parserSpecPath, true);
15 }
16
17 private final int STATE_ERROR = -1;
18
19 private LR0States states = new LR0States();
20 private int[][] delta;
21 private LR0Item[] complete;
22
23 public void precompute() {
24 List deltaList = new ArrayList();
25 List completeList = new ArrayList();
26 LR0State first = new LR0State();
27 first.addKernelItem(new LR0Item(sp));
28 first.closure(p);
29 states.add(first);
30
31 int[] deltaLine = new int[g.symbolCount()];
32 for (int j = 0; j<g.symbolCount(); j++) {
33 deltaLine[j] = STATE_ERROR;
34 }
35 deltaList.add(deltaLine);
36 completeList.add(null);
37
38 int i = 0;
39 while (i<states.size()) {
40 LR0State state = states.find(i);
41 for (int sid = 0; sid<g.symbolCount(); sid++) {
42 LR0State newState = new LR0State();
43 Symbol sym = g.symbol(sid);
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
54 Iterator it2 = newState.getKernelItems().iterator();
56 LR0Item completeItem = null;
57 while (it2.hasNext()) {
58 LR0Item item = (LR0Item)it2.next();
59 if (item.isComplete()) {
60 if (completeItem == null) {
61 completeItem = item;
62 } else {
63 throw new RuntimeException (
64 "Grammar not LR(0). \nReduce-Reduce conflict: "+
65 state+"\nComplete item 1: "+completeItem+
66 "\nComplete item 2: "+item);
67 }
68 }
69 }
70
71 states.add(newState);
72 completeList.add(completeItem);
73 deltaLine = new int[g.symbolCount()];
74 for (int j = 0; j<g.symbolCount(); j++) {
75 deltaLine[j] = STATE_ERROR;
76 }
77 deltaList.add(deltaLine);
78 } else {
79 newState = oldState;
80 }
81 LR0Item completeItem = (LR0Item)completeList.get(state.getIndex());
82 if (sym.isTerminal() && completeItem != null) {
83 throw new RuntimeException (
84 "Grammar not LR(0). \nShift-Reduce conflict: "+
85 state+"\nComplete item: "+completeItem+
86 "\nShift symbol: "+sym);
87 }
88 deltaLine = (int[])deltaList.get(state.getIndex());
89 deltaLine[g.getSID(sym)] = newState.getIndex();
90 }
91 }
92 i++;
93 }
94 int n = states.size();
95 delta = new int[n][];
96 complete = new LR0Item[n];
97 for (int k = 0; k<n; k++) {
98 delta[k] = (int[])deltaList.get(k);
99 complete[k] = (LR0Item)completeList.get(k);
100 }
101
102
115 }
116
117 public List parse()
118 throws IOException, SyntaxError {
119 List pi = new LinkedList();
120 LinkedList stack = new LinkedList();
121 stack.add(states.find(0));
122 Terminal a = lexer.nextToken().getSymbol();
123
124 while (true) {
125
132
133 if (a == t.EOF && stack.size()<=2) {
134 if (stack.size() != 2) {
135 throw new SyntaxError("EOF read, stack doesn't contain two states");
136 }
137 LR0State state = (LR0State)stack.get(0);
138 if (state.getIndex() != 0) {
139 throw new SyntaxError("EOF read, first state on the stack is not state 0");
140 }
141 state = (LR0State)stack.get(1);
142 if (!state.contains(new LR0Item(sp, 1))) {
143 throw new SyntaxError("EOF read, second state on the stack is not the final state");
144 }
145 return pi; }
147
148 LR0State state = (LR0State)stack.getLast();
149 int next = STATE_ERROR;
150 if (a != null) {
151 next = delta[state.getIndex()][g.getSID(a)];
152 }
153 LR0Item completeItem = complete[state.getIndex()];
154
155 if (next == STATE_ERROR) {
156 if (completeItem == null) {
157 throw new SyntaxError(a); } else {
159 Production prod = completeItem.getProduction();
161 for (int i = 0; i<prod.getRHS().size(); i++) {
162 stack.removeLast();
163 }
164 state = (LR0State)stack.getLast();
165 next = delta[state.getIndex()][g.getSID(prod.getLHS())];
166 if (next == STATE_ERROR) {
167 throw new SyntaxError(a); } else {
169 stack.addLast(states.find(next));
170 pi.add(prod);
171 }
172 }
173 } else {
174 if (completeItem == null) {
175 stack.addLast(states.find(next));
177 a = lexer.nextToken().getSymbol();
178 } else {
179 throw new SyntaxError("Shift-reduce conflict", a);
180 }
181 }
182 }
183 }
184
185 public static void main(String args[]) throws Exception {
186 if (args.length != 3) {
187 System.err.println("args: <grammar_file> <lexer_class> <input_file>");
188 System.exit(1);
189 }
190
191 Parser parser = new LR0Parser(args[0]);
192 System.out.println(parser.getGrammar());
193 parser.precompute();
194 parser.setLexer(args[1], args[2]);
195 List pi = parser.parse();
196 Iterator it = pi.iterator();
197 while (it.hasNext()) {
198 System.out.println(it.next()+";");
199 }
200 }
201 }
202 |
Popular Tags |
Java API By Example, From Geeks To Geeks.