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