|
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 LR1Parser extends AbstractLR1Parser {
8 public LR1Parser(ParserSpec spec) {
9 super(spec);
10 }
11
12 public LR1Parser(String  parserSpecPath)
13 throws IOException, SpecParseException {
14 super(parserSpecPath);
15 }
17
18 public void precompute() {
19 g.computeFirst();
20
21 LR1States states = new LR1States();
22 List actionList = new LinkedList();
23 List gotoList = new LinkedList();
24
25 LR1State startState = new LR1State();
26 LR1Item startItem = new LR1Item(new LR0Item(sp), t.EOF);
27 startState.addKernelItem(startItem);
28 startState.closure(g);
29
30 states.add(startState);
31
32 ParseAction[] actionLine = new ParseAction[t.count()];
33 Integer [] gotoLine = new Integer [v.count()];
34
35 actionList.add(actionLine);
36 gotoList.add(gotoLine);
37
38 int i = 0;
39 while (i<states.size()) {
40 LR1State state = states.find(i);
41 for (int sid = 0; sid<g.symbolCount(); sid++) {
42 LR1State newState = new LR1State();
43 Symbol sym = g.symbol(sid);
44 Iterator it = state.iterator(sym);
46 while (it.hasNext()) {
47 LR1Item item = (LR1Item)it.next();
48 newState.addKernelItem(item.nextItem());
49 }
50 if (!newState.isEmpty()) {
51 LR1State oldState = states.find(newState.getKernelItems());
52 if (oldState == null) {
53 newState.closure(g);
54 states.add(newState);
55
56 actionLine = new ParseAction[t.count()];
57 gotoLine = new Integer [v.count()];
58
59 Iterator it2 = newState.iterator();
61 while (it2.hasNext()) {
62 LR1Item item = (LR1Item)it2.next();
63 if (item.isComplete()) {
64 Production prod = item.getProduction();
65 Terminal a = item.getLookahead();
66 if (actionLine[a.getIndex()] == null) {
67 actionLine[a.getIndex()] = new ReduceAction(prod);
68 } else {
69 throw new RuntimeException (
70 "Grammar not LR(1). \nReduce-Reduce conflict: "+
71 state+"\nState: "+newState+"\nLookahead: "+a+
72 "\nProduction 1: "+actionLine[a.getIndex()]+
73 "\nProduction 2: "+prod);
74 }
75 }
76 }
77
78 actionList.add(actionLine);
79 gotoList.add(gotoLine);
80 } else {
81 newState = oldState;
82 }
83
84 actionLine = (ParseAction[])actionList.get(state.getIndex());
85 gotoLine = (Integer [])gotoList.get(state.getIndex());
86
87 if (sym.isTerminal()) {
88 Terminal a = (Terminal)sym;
89 if (actionLine[a.getIndex()] == null) {
90 actionLine[a.getIndex()] = new ShiftAction(
91 new Integer (newState.getIndex()));
92 } else {
93 throw new RuntimeException (
94 "Grammar not LR(1). \nShift-Reduce conflict: "+
95 state+"\nState: "+state+"\nTerminal: "+a+
96 "\nProduction: "+actionLine[a.getIndex()]+
97 "\nShift state: "+newState);
98 }
99 } else {
100 NonTerminal x = (NonTerminal)sym;
101 gotoLine[x.getIndex()] = new Integer (newState.getIndex());
102 }
103 }
104 }
105 i++;
106 }
107
108 startStateIndex = new Integer (startState.getIndex());
109
110 stateNo = states.size();
111 actionTable = new ParseAction[stateNo][];
112 gotoTable = new Integer [stateNo][];
113 for (int k = 0; k<stateNo; k++) {
114 actionTable[k] = (ParseAction[])actionList.get(k);
115 gotoTable[k] = (Integer [])gotoList.get(k);
116 }
117
118 if (DEBUG) {
119 System.out.println(states.size()+" states");
120 System.out.println("start: "+startStateIndex);
121 }
122 }
123
124 public static void main(String args[]) throws Exception {
125 if (args.length != 3) {
126 System.err.println("args: <grammar_file> <lexer_class> <input_file>");
127 System.exit(1);
128 }
129 Parser parser = new LR1Parser(args[0]);
130 System.out.println(parser.getGrammar());
131 parser.precompute();
132 parser.setLexer(args[1], args[2]);
133 List pi = parser.parse();
134 Iterator it = pi.iterator();
135 while (it.hasNext()) {
136 System.out.println(it.next()+";");
137 }
138 }
139 }
140 |
Popular Tags |
Java API By Example, From Geeks To Geeks.