|
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 LALR1Parser extends AbstractLR1Parser {
8 public LALR1Parser(ParserSpec spec) {
9 super(spec);
10 }
11
12 public LALR1Parser(String  parserSpecPath)
13 throws IOException, SpecParseException {
14 super(parserSpecPath);
15 }
17
18 public void precompute() {
19 g.computeFirst();
20
21 LALR1States states = new LALR1States();
22 List actionList = new LinkedList();
23 List gotoList = new LinkedList();
24
25 LALR1State startState = new LALR1State();
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 LinkedList queue = new LinkedList();
39 queue.add(startState);
40
41 while (!queue.isEmpty()) {
42 LALR1State state = (LALR1State)queue.removeFirst();
43 for (int sid = 0; sid<g.symbolCount(); sid++) {
44 LALR1State newState = new LALR1State();
45 Symbol sym = g.symbol(sid);
46 Iterator it = state.iterator(sym);
48 while (it.hasNext()) {
49 LR1Item item = (LR1Item)it.next();
50 newState.addKernelItem(item.nextItem());
51 }
52 if (!newState.isEmpty()) {
53 LALR1State oldState = states.find(newState.getLR0KernelItems());
54 if (oldState == null) {
55 newState.closure(g);
56 states.add(newState);
57
58 actionLine = new ParseAction[t.count()];
59 gotoLine = new Integer [v.count()];
60
61 Iterator newIt = newState.iterator();
63 while (newIt.hasNext()) {
64 LR1Item newItem = (LR1Item)newIt.next();
65 if (newItem.isComplete()) {
66 Production prod = newItem.getProduction();
67 Terminal a = newItem.getLookahead();
68 if (actionLine[a.getIndex()] == null) {
69 actionLine[a.getIndex()] = new ReduceAction(prod);
70 } else {
71 throw new RuntimeException (
72 "Grammar not LR(1). \nReduce-Reduce conflict: "+
73 state+"\nNew state: "+newState+"\nLookahead: "+a+
74 "\nProduction 1: "+actionLine[a.getIndex()]+
75 "\nProduction 2: "+prod);
76 }
77 }
78 }
79
80 actionList.add(actionLine);
81 gotoList.add(gotoLine);
82 queue.add(newState);
83
84 } else {
85 actionLine = (ParseAction[])actionList.get(oldState.getIndex());
89
90 boolean hasGrown = false;
91 Iterator newIt = newState.getKernelItems().iterator();
92 while (newIt.hasNext()) {
93 LR1Item item = (LR1Item)newIt.next();
94 if (!oldState.contains(item)) {
95 hasGrown = true;
96 Collection closure = oldState.addKernelItemWithClosure(item, g);
97 Iterator closureIt = closure.iterator();
98 while (closureIt.hasNext()) {
99 LR1Item newItem = (LR1Item)closureIt.next();
100 if (newItem.isComplete()) {
101 Production prod = newItem.getProduction();
102 Terminal a = newItem.getLookahead();
103 if (actionLine[a.getIndex()] == null) {
104 actionLine[a.getIndex()] = new ReduceAction(prod);
105 } else {
106 throw new RuntimeException (
107 "Grammar not LALR(1). \nReduce-Reduce conflict: "+
108 state+"\nState (partial): "+oldState+"\nLookahead: "+a+
109 "\nProduction 1: "+actionLine[a.getIndex()]+
110 "\nProduction 2: "+prod);
111 }
112 }
113 }
114 }
115 }
116 if (hasGrown) {
117 queue.add(oldState);
118 }
119 newState = oldState;
120 }
121
122
123 actionLine = (ParseAction[])actionList.get(state.getIndex());
124 gotoLine = (Integer [])gotoList.get(state.getIndex());
125
126 if (sym.isTerminal()) {
127 Terminal a = (Terminal)sym;
128 if (actionLine[a.getIndex()] == null) {
129 actionLine[a.getIndex()] = new ShiftAction(
130 new Integer (newState.getIndex()));
131 } else if (actionLine[a.getIndex()].isReduceAction()) {
132 throw new RuntimeException (
133 "Grammar not LR(1). \nShift-Reduce conflict: "+
134 state+"\nState: "+state+"\nTerminal: "+a+
135 "\nProduction: "+actionLine[a.getIndex()]+
136 "\nShift state: "+newState);
137 }
138 } else {
139 NonTerminal x = (NonTerminal)sym;
140 gotoLine[x.getIndex()] = new Integer (newState.getIndex());
141 }
142 }
143 }
144 }
145
146 startStateIndex = new Integer (startState.getIndex());
147
148 stateNo = states.size();
149 actionTable = new ParseAction[stateNo][];
150 gotoTable = new Integer [stateNo][];
151 for (int k = 0; k<stateNo; k++) {
152 actionTable[k] = (ParseAction[])actionList.get(k);
153 gotoTable[k] = (Integer [])gotoList.get(k);
154 }
155
156 if (DEBUG) {
157 System.out.println(states.size()+" states");
158 System.out.println("start: "+startStateIndex);
159 }
160 }
161
162 public static void main(String args[]) throws Exception {
163 if (args.length != 3) {
164 System.err.println("args: <grammar_file> <lexer_class> <input_file>");
165 System.exit(1);
166 }
167 Parser parser = new LALR1Parser(args[0]);
168 System.out.println(parser.getGrammar());
169 parser.precompute();
170 parser.setLexer(args[1], args[2]);
171 List pi = parser.parse();
172 Iterator it = pi.iterator();
173 while (it.hasNext()) {
174 System.out.println(it.next()+";");
175 }
176 }
177 }
178 |
Popular Tags |
Java API By Example, From Geeks To Geeks.