|
1 package ro.infoiasi.donald.compiler.parser;
2
3 import ro.infoiasi.donald.compiler.cfg.*;
4 import ro.infoiasi.donald.compiler.simple.*;
5 import java.io.*;
6 import java.util.*;
7
8 public class SimplePrecedenceParser extends AbstractParser {
9 public SimplePrecedenceParser(ParserSpec spec) {
10 super(spec);
11 }
12
13 public SimplePrecedenceParser(String  parserSpecPath)
14 throws IOException, SpecParseException {
15 super(parserSpecPath);
16 }
17
18 private final int PARSE_ERROR = 0;
19 private final int EQUAL = 1;
20 private final int LESS = 1 << 1;
21 private final int GREATER = 1 << 2;
22 private final int LESS_OR_EQUAL = LESS | EQUAL;
23
24 private SymbolRelation eq;
25 private SymbolRelation lt;
26 private SymbolRelation gt;
27
28 private ParseTable parseTable;
29
30 class ParseTable {
31 private int n;
32 private int m;
33 private int[][] table;
34
35 public ParseTable(CFG g) {
36 n = g.getNonTerminals().count();
37 m = g.getTerminals().count();
38 int size = n+m;
39 table = new int[size][];
40 for (int i = 0; i<size; i++) {
41 table[i] = new int[size];
42 for (int j = 0; j<size; j++) {
43 table[i][j] = PARSE_ERROR;
44 }
45 }
46 }
47
48 public void add(SymbolRelation sr, int marker) {
49 Iterator it = sr.iteratorIP();
50 while (it.hasNext()) {
51 Relation.IntPair ip = (Relation.IntPair)it.next();
52 int i = ip.getFirst();
53 int j = ip.getSecond();
54 if (table[i][j] == PARSE_ERROR) {
55 table[i][j] = marker;
56 } else {
57 throw new RuntimeException ("Precedence conflict: "
58 +g.symbol(i)+" ? "+g.symbol(j));
59 }
60 }
61 }
62
63 public int get(Symbol x, Symbol y) {
64 return table[g.getSID(x)][g.getSID(y)];
65 }
66
67 public void print() {
68 if (table != null) {
69 for (int i = 0; i<g.symbolCount(); i++) {
70 for (int j = 0; j<g.symbolCount(); j++) {
71 int rel = table[i][j];
72 if (rel != PARSE_ERROR) {
73 System.out.print("("+g.symbol(i)+" "+rel+" "+g.symbol(j)+") ");
74 }
75 }
76 }
77 }
78 }
79 }
80
81 public void precompute() {
82 if (!g.isInvertible()) {
83 throw new RuntimeException ("Grammar is not invertible");
84 }
85
86 SymbolRelation begins = new SymbolRelation(g);
87 SymbolRelation ends = new SymbolRelation(g);
88 SymbolRelation adjoins = new SymbolRelation(g);
89 SymbolRelation terminal = new SymbolRelation(g);
90 Iterator itP = p.iterator();
91 while (itP.hasNext()) {
92 Production prod = (Production)itP.next();
93 NonTerminal a = prod.getLHS();
94 Word w = prod.getRHS();
95 if (w.isEmpty()) {
96 throw new RuntimeException ("Grammar in not erase-free");
97 }
98 begins.add(w.getFirst(), a);
99 ends.add(w.getLast(), a);
100
101 WordIterator itW = w.iterator();
102 Symbol x, y = itW.next();
103 while (itW.hasNext()) {
104 x = y;
105 y = itW.next();
106 adjoins.add(x, y);
107 }
108 }
109
110 Iterator itT = t.iterator();
111 while (itT.hasNext()) {
112 Terminal x = (Terminal)itT.next();
113 terminal.add(x, x);
114 }
115
116
120
121 SymbolRelation begins_plus = begins.plus();
122 SymbolRelation ends_plus = ends.plus();
123
124 eq = adjoins;
125 lt = adjoins.product(begins_plus.inverse());
126 gt = ends_plus.product(adjoins.product(
127 begins.star().inverse().product(terminal)));
128
129 Iterator it = begins_plus.iteratorSP();
130 while (it.hasNext()) {
131 SymbolRelation.SymbolPair sp = (SymbolRelation.SymbolPair)it.next();
132 if (sp.getSecond().equals(s)) {
133 lt.add(t.EOF, sp.getFirst());
134 }
135 }
136 it = ends_plus.iteratorSP();
137 while (it.hasNext()) {
138 SymbolRelation.SymbolPair sp = (SymbolRelation.SymbolPair)it.next();
139 if (sp.getSecond().equals(s)) {
140 gt.add(sp.getFirst(), t.EOF);
141 }
142 }
143
144
147
148 parseTable = new ParseTable(g);
149 parseTable.add(eq, EQUAL);
150 parseTable.add(lt, LESS);
151 parseTable.add(gt, GREATER);
152 }
153
154 public List parse() throws IOException, SyntaxError {
155 List pi = new LinkedList();
156 Word stack = new Word();
157 stack.addLast(t.EOF);
158 Word accept = new Word();
159 accept.addLast(t.EOF);
160 accept.addLast(s);
161 Terminal a = lexer.nextToken().getSymbol();
162
163 while (true) {
164 if (stack.equals(accept)) {
165 return pi; }
167 Symbol x = stack.getLast();
168 int rel = parseTable.get(x, a);
169 if (rel == EQUAL || rel == LESS) {
170 stack.addLast(a); a = lexer.nextToken().getSymbol();
172 } else {
173 Word w = new Word();
174 do {
175 stack.removeLast();
176 w.addFirst(x);
177 Symbol y = x;
178 x = stack.getLast();
179 rel = parseTable.get(x, y);
180 } while (rel == EQUAL);
181 List prodList = p.find(w);
182 if (prodList == null) {
183 throw new SyntaxError(a); } else {
185 Production prod = (Production)prodList.get(0);
186 stack.addLast(prod.getLHS()); pi.add(prod);
188 }
189 }
190
191 }
192 }
193
194 public static void main(String args[]) throws Exception {
195 if (args.length != 3) {
196 System.err.println("args: <grammar_file> <lexer_class> <input_file>");
197 System.exit(1);
198 }
199
200 Parser parser = new SimplePrecedenceParser(args[0]);
201 System.out.println(parser.getGrammar());
202 parser.precompute();
203 parser.setLexer(args[1], args[2]);
204 List pi = parser.parse();
205 Iterator it = pi.iterator();
206 while (it.hasNext()) {
207 System.out.println(it.next()+";");
208 }
209 }
210 }
211 |
Popular Tags |
Java API By Example, From Geeks To Geeks.