001: package ro.infoiasi.donald.compiler.parser;
002:
003: import ro.infoiasi.donald.compiler.cfg.*;
004: import ro.infoiasi.donald.compiler.simple.*;
005: import java.io.*;
006: import java.util.*;
007:
008: public class SimplePrecedenceParser extends AbstractParser {
009: public SimplePrecedenceParser(ParserSpec spec) {
010: super (spec);
011: }
012:
013: public SimplePrecedenceParser(String parserSpecPath)
014: throws IOException, SpecParseException {
015: super (parserSpecPath);
016: }
017:
018: private final int PARSE_ERROR = 0;
019: private final int EQUAL = 1;
020: private final int LESS = 1 << 1;
021: private final int GREATER = 1 << 2;
022: private final int LESS_OR_EQUAL = LESS | EQUAL;
023:
024: private SymbolRelation eq;
025: private SymbolRelation lt;
026: private SymbolRelation gt;
027:
028: private ParseTable parseTable;
029:
030: class ParseTable {
031: private int n;
032: private int m;
033: private int[][] table;
034:
035: public ParseTable(CFG g) {
036: n = g.getNonTerminals().count();
037: m = g.getTerminals().count();
038: int size = n + m;
039: table = new int[size][];
040: for (int i = 0; i < size; i++) {
041: table[i] = new int[size];
042: for (int j = 0; j < size; j++) {
043: table[i][j] = PARSE_ERROR;
044: }
045: }
046: }
047:
048: public void add(SymbolRelation sr, int marker) {
049: Iterator it = sr.iteratorIP();
050: while (it.hasNext()) {
051: Relation.IntPair ip = (Relation.IntPair) it.next();
052: int i = ip.getFirst();
053: int j = ip.getSecond();
054: if (table[i][j] == PARSE_ERROR) {
055: table[i][j] = marker;
056: } else {
057: throw new RuntimeException("Precedence conflict: "
058: + g.symbol(i) + " ? " + g.symbol(j));
059: }
060: }
061: }
062:
063: public int get(Symbol x, Symbol y) {
064: return table[g.getSID(x)][g.getSID(y)];
065: }
066:
067: public void print() {
068: if (table != null) {
069: for (int i = 0; i < g.symbolCount(); i++) {
070: for (int j = 0; j < g.symbolCount(); j++) {
071: int rel = table[i][j];
072: if (rel != PARSE_ERROR) {
073: System.out.print("(" + g.symbol(i) + " "
074: + rel + " " + g.symbol(j) + ") ");
075: }
076: }
077: }
078: }
079: }
080: }
081:
082: public void precompute() {
083: if (!g.isInvertible()) {
084: throw new RuntimeException("Grammar is not invertible");
085: }
086:
087: SymbolRelation begins = new SymbolRelation(g);
088: SymbolRelation ends = new SymbolRelation(g);
089: SymbolRelation adjoins = new SymbolRelation(g);
090: SymbolRelation terminal = new SymbolRelation(g);
091: Iterator itP = p.iterator();
092: while (itP.hasNext()) {
093: Production prod = (Production) itP.next();
094: NonTerminal a = prod.getLHS();
095: Word w = prod.getRHS();
096: if (w.isEmpty()) {
097: throw new RuntimeException("Grammar in not erase-free");
098: }
099: begins.add(w.getFirst(), a);
100: ends.add(w.getLast(), a);
101:
102: WordIterator itW = w.iterator();
103: Symbol x, y = itW.next();
104: while (itW.hasNext()) {
105: x = y;
106: y = itW.next();
107: adjoins.add(x, y);
108: }
109: }
110:
111: Iterator itT = t.iterator();
112: while (itT.hasNext()) {
113: Terminal x = (Terminal) itT.next();
114: terminal.add(x, x);
115: }
116:
117: /* System.out.println("begins:"+begins);
118: System.out.println("ends:"+ends);
119: System.out.println("adjoins:"+adjoins);
120: System.out.println("terminal:"+terminal);*/
121:
122: SymbolRelation begins_plus = begins.plus();
123: SymbolRelation ends_plus = ends.plus();
124:
125: eq = adjoins;
126: lt = adjoins.product(begins_plus.inverse());
127: gt = ends_plus.product(adjoins.product(begins.star().inverse()
128: .product(terminal)));
129:
130: Iterator it = begins_plus.iteratorSP();
131: while (it.hasNext()) {
132: SymbolRelation.SymbolPair sp = (SymbolRelation.SymbolPair) it
133: .next();
134: if (sp.getSecond().equals(s)) {
135: lt.add(t.EOF, sp.getFirst());
136: }
137: }
138: it = ends_plus.iteratorSP();
139: while (it.hasNext()) {
140: SymbolRelation.SymbolPair sp = (SymbolRelation.SymbolPair) it
141: .next();
142: if (sp.getSecond().equals(s)) {
143: gt.add(sp.getFirst(), t.EOF);
144: }
145: }
146:
147: /* System.out.println("eq:"+eq);
148: System.out.println("lt:"+lt);
149: System.out.println("gt:"+gt);*/
150:
151: parseTable = new ParseTable(g);
152: parseTable.add(eq, EQUAL);
153: parseTable.add(lt, LESS);
154: parseTable.add(gt, GREATER);
155: }
156:
157: public List parse() throws IOException, SyntaxError {
158: List pi = new LinkedList();
159: Word stack = new Word();
160: stack.addLast(t.EOF);
161: Word accept = new Word();
162: accept.addLast(t.EOF);
163: accept.addLast(s);
164: Terminal a = lexer.nextToken().getSymbol();
165:
166: while (true) {
167: if (stack.equals(accept)) {
168: return pi; // accept
169: }
170: Symbol x = stack.getLast();
171: int rel = parseTable.get(x, a);
172: if (rel == EQUAL || rel == LESS) {
173: stack.addLast(a); // shift
174: a = lexer.nextToken().getSymbol();
175: } else {
176: Word w = new Word();
177: do {
178: stack.removeLast();
179: w.addFirst(x);
180: Symbol y = x;
181: x = stack.getLast();
182: rel = parseTable.get(x, y);
183: } while (rel == EQUAL);
184: List prodList = p.find(w);
185: if (prodList == null) {
186: throw new SyntaxError(a); // cannot apply reduction
187: } else {
188: Production prod = (Production) prodList.get(0);
189: stack.addLast(prod.getLHS()); // reduce
190: pi.add(prod);
191: }
192: }
193:
194: }
195: }
196:
197: public static void main(String args[]) throws Exception {
198: if (args.length != 3) {
199: System.err
200: .println("args: <grammar_file> <lexer_class> <input_file>");
201: System.exit(1);
202: }
203:
204: Parser parser = new SimplePrecedenceParser(args[0]);
205: System.out.println(parser.getGrammar());
206: parser.precompute();
207: parser.setLexer(args[1], args[2]);
208: List pi = parser.parse();
209: Iterator it = pi.iterator();
210: while (it.hasNext()) {
211: System.out.println(it.next() + ";");
212: }
213: }
214: }
|