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 LALR1Parser extends AbstractLR1Parser {
008: public LALR1Parser(ParserSpec spec) {
009: super (spec);
010: }
011:
012: public LALR1Parser(String parserSpecPath) throws IOException,
013: SpecParseException {
014: super (parserSpecPath);
015: //DEBUG = true;
016: }
017:
018: public void precompute() {
019: g.computeFirst();
020:
021: LALR1States states = new LALR1States();
022: List actionList = new LinkedList();
023: List gotoList = new LinkedList();
024:
025: LALR1State startState = new LALR1State();
026: LR1Item startItem = new LR1Item(new LR0Item(sp), t.EOF);
027: startState.addKernelItem(startItem);
028: startState.closure(g);
029:
030: states.add(startState);
031:
032: ParseAction[] actionLine = new ParseAction[t.count()];
033: Integer[] gotoLine = new Integer[v.count()];
034:
035: actionList.add(actionLine);
036: gotoList.add(gotoLine);
037:
038: LinkedList queue = new LinkedList();
039: queue.add(startState);
040:
041: while (!queue.isEmpty()) {
042: LALR1State state = (LALR1State) queue.removeFirst();
043: for (int sid = 0; sid < g.symbolCount(); sid++) {
044: LALR1State newState = new LALR1State();
045: Symbol sym = g.symbol(sid);
046: //if (sym == s) continue;
047: Iterator it = state.iterator(sym);
048: while (it.hasNext()) {
049: LR1Item item = (LR1Item) it.next();
050: newState.addKernelItem(item.nextItem());
051: }
052: if (!newState.isEmpty()) {
053: LALR1State oldState = states.find(newState
054: .getLR0KernelItems());
055: if (oldState == null) {
056: newState.closure(g);
057: states.add(newState);
058:
059: actionLine = new ParseAction[t.count()];
060: gotoLine = new Integer[v.count()];
061:
062: // add the reduce actions to the action table
063: Iterator newIt = newState.iterator();
064: while (newIt.hasNext()) {
065: LR1Item newItem = (LR1Item) newIt.next();
066: if (newItem.isComplete()) {
067: Production prod = newItem
068: .getProduction();
069: Terminal a = newItem.getLookahead();
070: if (actionLine[a.getIndex()] == null) {
071: actionLine[a.getIndex()] = new ReduceAction(
072: prod);
073: } else {
074: throw new RuntimeException(
075: "Grammar not LR(1). \nReduce-Reduce conflict: "
076: + state
077: + "\nNew state: "
078: + newState
079: + "\nLookahead: "
080: + a
081: + "\nProduction 1: "
082: + actionLine[a
083: .getIndex()]
084: + "\nProduction 2: "
085: + prod);
086: }
087: }
088: }
089:
090: actionList.add(actionLine);
091: gotoList.add(gotoLine);
092: queue.add(newState);
093:
094: } else {
095: // newState and oldState have the same kernel, so merge the states.
096: // New items and reduce actions (and conflicts) may appear in oldState.
097: // If new items appear in oldState reintroduce it onto the stack.
098: actionLine = (ParseAction[]) actionList
099: .get(oldState.getIndex());
100:
101: boolean hasGrown = false;
102: Iterator newIt = newState.getKernelItems()
103: .iterator();
104: while (newIt.hasNext()) {
105: LR1Item item = (LR1Item) newIt.next();
106: if (!oldState.contains(item)) {
107: hasGrown = true;
108: Collection closure = oldState
109: .addKernelItemWithClosure(item,
110: g);
111: Iterator closureIt = closure.iterator();
112: while (closureIt.hasNext()) {
113: LR1Item newItem = (LR1Item) closureIt
114: .next();
115: if (newItem.isComplete()) {
116: Production prod = newItem
117: .getProduction();
118: Terminal a = newItem
119: .getLookahead();
120: if (actionLine[a.getIndex()] == null) {
121: actionLine[a.getIndex()] = new ReduceAction(
122: prod);
123: } else {
124: throw new RuntimeException(
125: "Grammar not LALR(1). \nReduce-Reduce conflict: "
126: + state
127: + "\nState (partial): "
128: + oldState
129: + "\nLookahead: "
130: + a
131: + "\nProduction 1: "
132: + actionLine[a
133: .getIndex()]
134: + "\nProduction 2: "
135: + prod);
136: }
137: }
138: }
139: }
140: }
141: if (hasGrown) {
142: queue.add(oldState);
143: }
144: newState = oldState;
145: }
146:
147: actionLine = (ParseAction[]) actionList.get(state
148: .getIndex());
149: gotoLine = (Integer[]) gotoList.get(state
150: .getIndex());
151:
152: if (sym.isTerminal()) {
153: Terminal a = (Terminal) sym;
154: if (actionLine[a.getIndex()] == null) {
155: actionLine[a.getIndex()] = new ShiftAction(
156: new Integer(newState.getIndex()));
157: } else if (actionLine[a.getIndex()]
158: .isReduceAction()) {
159: throw new RuntimeException(
160: "Grammar not LR(1). \nShift-Reduce conflict: "
161: + state + "\nState: "
162: + state + "\nTerminal: "
163: + a + "\nProduction: "
164: + actionLine[a.getIndex()]
165: + "\nShift state: "
166: + newState);
167: }
168: } else {
169: NonTerminal x = (NonTerminal) sym;
170: gotoLine[x.getIndex()] = new Integer(newState
171: .getIndex());
172: }
173: }
174: }
175: }
176:
177: startStateIndex = new Integer(startState.getIndex());
178:
179: stateNo = states.size();
180: actionTable = new ParseAction[stateNo][];
181: gotoTable = new Integer[stateNo][];
182: for (int k = 0; k < stateNo; k++) {
183: actionTable[k] = (ParseAction[]) actionList.get(k);
184: gotoTable[k] = (Integer[]) gotoList.get(k);
185: }
186:
187: if (DEBUG) {
188: System.out.println(states.size() + " states");
189: System.out.println("start: " + startStateIndex);
190: }
191: }
192:
193: public static void main(String args[]) throws Exception {
194: if (args.length != 3) {
195: System.err
196: .println("args: <grammar_file> <lexer_class> <input_file>");
197: System.exit(1);
198: }
199: Parser parser = new LALR1Parser(args[0]);
200: System.out.println(parser.getGrammar());
201: parser.precompute();
202: parser.setLexer(args[1], args[2]);
203: List pi = parser.parse();
204: Iterator it = pi.iterator();
205: while (it.hasNext()) {
206: System.out.println(it.next() + ";");
207: }
208: }
209: }
|