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 LR1Parser extends AbstractLR1Parser {
008: public LR1Parser(ParserSpec spec) {
009: super (spec);
010: }
011:
012: public LR1Parser(String parserSpecPath) throws IOException,
013: SpecParseException {
014: super (parserSpecPath);
015: //DEBUG = true;
016: }
017:
018: public void precompute() {
019: g.computeFirst();
020:
021: LR1States states = new LR1States();
022: List actionList = new LinkedList();
023: List gotoList = new LinkedList();
024:
025: LR1State startState = new LR1State();
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: int i = 0;
039: while (i < states.size()) {
040: LR1State state = states.find(i);
041: for (int sid = 0; sid < g.symbolCount(); sid++) {
042: LR1State newState = new LR1State();
043: Symbol sym = g.symbol(sid);
044: //if (sym == s) continue;
045: Iterator it = state.iterator(sym);
046: while (it.hasNext()) {
047: LR1Item item = (LR1Item) it.next();
048: newState.addKernelItem(item.nextItem());
049: }
050: if (!newState.isEmpty()) {
051: LR1State oldState = states.find(newState
052: .getKernelItems());
053: if (oldState == null) {
054: newState.closure(g);
055: states.add(newState);
056:
057: actionLine = new ParseAction[t.count()];
058: gotoLine = new Integer[v.count()];
059:
060: // add the reduce actions to the action table
061: Iterator it2 = newState.iterator();
062: while (it2.hasNext()) {
063: LR1Item item = (LR1Item) it2.next();
064: if (item.isComplete()) {
065: Production prod = item.getProduction();
066: Terminal a = item.getLookahead();
067: if (actionLine[a.getIndex()] == null) {
068: actionLine[a.getIndex()] = new ReduceAction(
069: prod);
070: } else {
071: throw new RuntimeException(
072: "Grammar not LR(1). \nReduce-Reduce conflict: "
073: + state
074: + "\nState: "
075: + newState
076: + "\nLookahead: "
077: + a
078: + "\nProduction 1: "
079: + actionLine[a
080: .getIndex()]
081: + "\nProduction 2: "
082: + prod);
083: }
084: }
085: }
086:
087: actionList.add(actionLine);
088: gotoList.add(gotoLine);
089: } else {
090: newState = oldState;
091: }
092:
093: actionLine = (ParseAction[]) actionList.get(state
094: .getIndex());
095: gotoLine = (Integer[]) gotoList.get(state
096: .getIndex());
097:
098: if (sym.isTerminal()) {
099: Terminal a = (Terminal) sym;
100: if (actionLine[a.getIndex()] == null) {
101: actionLine[a.getIndex()] = new ShiftAction(
102: new Integer(newState.getIndex()));
103: } else {
104: throw new RuntimeException(
105: "Grammar not LR(1). \nShift-Reduce conflict: "
106: + state + "\nState: "
107: + state + "\nTerminal: "
108: + a + "\nProduction: "
109: + actionLine[a.getIndex()]
110: + "\nShift state: "
111: + newState);
112: }
113: } else {
114: NonTerminal x = (NonTerminal) sym;
115: gotoLine[x.getIndex()] = new Integer(newState
116: .getIndex());
117: }
118: }
119: }
120: i++;
121: }
122:
123: startStateIndex = new Integer(startState.getIndex());
124:
125: stateNo = states.size();
126: actionTable = new ParseAction[stateNo][];
127: gotoTable = new Integer[stateNo][];
128: for (int k = 0; k < stateNo; k++) {
129: actionTable[k] = (ParseAction[]) actionList.get(k);
130: gotoTable[k] = (Integer[]) gotoList.get(k);
131: }
132:
133: if (DEBUG) {
134: System.out.println(states.size() + " states");
135: System.out.println("start: " + startStateIndex);
136: }
137: }
138:
139: public static void main(String args[]) throws Exception {
140: if (args.length != 3) {
141: System.err
142: .println("args: <grammar_file> <lexer_class> <input_file>");
143: System.exit(1);
144: }
145: Parser parser = new LR1Parser(args[0]);
146: System.out.println(parser.getGrammar());
147: parser.precompute();
148: parser.setLexer(args[1], args[2]);
149: List pi = parser.parse();
150: Iterator it = pi.iterator();
151: while (it.hasNext()) {
152: System.out.println(it.next() + ";");
153: }
154: }
155: }
|