001: package ro.infoiasi.donald.compiler.parser;
002:
003: import ro.infoiasi.donald.compiler.cfg.*;
004: import java.io.*;
005: import java.util.*;
006:
007: public class LR0Parser extends AbstractParser {
008: public LR0Parser(ParserSpec spec) {
009: super (spec, true);
010: }
011:
012: public LR0Parser(String parserSpecPath) throws IOException,
013: SpecParseException {
014: super (parserSpecPath, true);
015: }
016:
017: private final int STATE_ERROR = -1;
018:
019: private LR0States states = new LR0States();
020: private int[][] delta;
021: private LR0Item[] complete;
022:
023: public void precompute() {
024: List deltaList = new ArrayList();
025: List completeList = new ArrayList();
026: LR0State first = new LR0State();
027: first.addKernelItem(new LR0Item(sp));
028: first.closure(p);
029: states.add(first);
030:
031: int[] deltaLine = new int[g.symbolCount()];
032: for (int j = 0; j < g.symbolCount(); j++) {
033: deltaLine[j] = STATE_ERROR;
034: }
035: deltaList.add(deltaLine);
036: completeList.add(null);
037:
038: int i = 0;
039: while (i < states.size()) {
040: LR0State state = states.find(i);
041: for (int sid = 0; sid < g.symbolCount(); sid++) {
042: LR0State newState = new LR0State();
043: Symbol sym = g.symbol(sid);
044: Iterator it = state.iterator(sym);
045: while (it.hasNext()) {
046: LR0Item item = (LR0Item) it.next();
047: newState.addKernelItem(item.nextItem());
048: }
049: if (!newState.isEmpty()) {
050: LR0State oldState = states.find(newState
051: .getKernelItems());
052: if (oldState == null) {
053: newState.closure(p);
054:
055: // have more than one complete item?
056: Iterator it2 = newState.getKernelItems()
057: .iterator();
058: LR0Item completeItem = null;
059: while (it2.hasNext()) {
060: LR0Item item = (LR0Item) it2.next();
061: if (item.isComplete()) {
062: if (completeItem == null) {
063: completeItem = item;
064: } else {
065: throw new RuntimeException(
066: "Grammar not LR(0). \nReduce-Reduce conflict: "
067: + state
068: + "\nComplete item 1: "
069: + completeItem
070: + "\nComplete item 2: "
071: + item);
072: }
073: }
074: }
075:
076: states.add(newState);
077: completeList.add(completeItem);
078: deltaLine = new int[g.symbolCount()];
079: for (int j = 0; j < g.symbolCount(); j++) {
080: deltaLine[j] = STATE_ERROR;
081: }
082: deltaList.add(deltaLine);
083: } else {
084: newState = oldState;
085: }
086: LR0Item completeItem = (LR0Item) completeList
087: .get(state.getIndex());
088: if (sym.isTerminal() && completeItem != null) {
089: throw new RuntimeException(
090: "Grammar not LR(0). \nShift-Reduce conflict: "
091: + state + "\nComplete item: "
092: + completeItem
093: + "\nShift symbol: " + sym);
094: }
095: deltaLine = (int[]) deltaList.get(state.getIndex());
096: deltaLine[g.getSID(sym)] = newState.getIndex();
097: }
098: }
099: i++;
100: }
101: int n = states.size();
102: delta = new int[n][];
103: complete = new LR0Item[n];
104: for (int k = 0; k < n; k++) {
105: delta[k] = (int[]) deltaList.get(k);
106: complete[k] = (LR0Item) completeList.get(k);
107: }
108:
109: /* System.out.println(states);
110: // print delta
111: for (int k = 0; k<n; k++) {
112: for (int sid = 0; sid<g.symbolCount(); sid++) {
113: if (delta[k][sid] != STATE_ERROR) {
114: System.out.println("delta("+k+","+g.symbol(sid)+")="+delta[k][sid]);
115: }
116: }
117: }
118: // print complete items
119: for (int k = 0; k<n; k++) {
120: System.out.println(k+": "+complete[k]);
121: }*/
122: }
123:
124: public List parse() throws IOException, SyntaxError {
125: List pi = new LinkedList();
126: LinkedList stack = new LinkedList();
127: stack.add(states.find(0));
128: Terminal a = lexer.nextToken().getSymbol();
129:
130: while (true) {
131: /* // print stack
132: System.out.println("Stack dump:");
133: Iterator stackIt = stack.iterator();
134: while (stackIt.hasNext()) {
135: LR0State state = (LR0State)stackIt.next();
136: System.out.println(state.getIndex()+": "+state);
137: }*/
138:
139: if (a == t.EOF && stack.size() <= 2) {
140: if (stack.size() != 2) {
141: throw new SyntaxError(
142: "EOF read, stack doesn't contain two states");
143: }
144: LR0State state = (LR0State) stack.get(0);
145: if (state.getIndex() != 0) {
146: throw new SyntaxError(
147: "EOF read, first state on the stack is not state 0");
148: }
149: state = (LR0State) stack.get(1);
150: if (!state.contains(new LR0Item(sp, 1))) {
151: throw new SyntaxError(
152: "EOF read, second state on the stack is not the final state");
153: }
154: return pi; // accept
155: }
156:
157: LR0State state = (LR0State) stack.getLast();
158: int next = STATE_ERROR;
159: if (a != null) {
160: next = delta[state.getIndex()][g.getSID(a)];
161: }
162: LR0Item completeItem = complete[state.getIndex()];
163:
164: if (next == STATE_ERROR) {
165: if (completeItem == null) {
166: throw new SyntaxError(a); // reject
167: } else {
168: // reduce
169: Production prod = completeItem.getProduction();
170: for (int i = 0; i < prod.getRHS().size(); i++) {
171: stack.removeLast();
172: }
173: state = (LR0State) stack.getLast();
174: next = delta[state.getIndex()][g.getSID(prod
175: .getLHS())];
176: if (next == STATE_ERROR) {
177: throw new SyntaxError(a);// RuntimeError ???
178: } else {
179: stack.addLast(states.find(next));
180: pi.add(prod);
181: }
182: }
183: } else {
184: if (completeItem == null) {
185: // shift
186: stack.addLast(states.find(next));
187: a = lexer.nextToken().getSymbol();
188: } else {
189: throw new SyntaxError("Shift-reduce conflict", a);
190: }
191: }
192: }
193: }
194:
195: public static void main(String args[]) throws Exception {
196: if (args.length != 3) {
197: System.err
198: .println("args: <grammar_file> <lexer_class> <input_file>");
199: System.exit(1);
200: }
201:
202: Parser parser = new LR0Parser(args[0]);
203: System.out.println(parser.getGrammar());
204: parser.precompute();
205: parser.setLexer(args[1], args[2]);
206: List pi = parser.parse();
207: Iterator it = pi.iterator();
208: while (it.hasNext()) {
209: System.out.println(it.next() + ";");
210: }
211: }
212: }
|