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: class LL1Parser extends AbstractParser {
008: public LL1Parser(ParserSpec spec) {
009: super (spec);
010: }
011:
012: public LL1Parser(String parserSpecPath) throws IOException,
013: SpecParseException {
014: super (parserSpecPath);
015: }
016:
017: private int[][] parseTable;
018:
019: private final int PARSE_ERROR = -1;
020:
021: public void precompute() {
022: g.computeNullable();
023: g.computeFirst();
024: g.computeFollow();
025: // g.printNullable();
026: // g.printFirst();
027: // g.printFollow();
028:
029: parseTable = new int[v.count()][];
030: for (int i = 0; i < v.count(); i++) {
031: parseTable[i] = new int[t.count()];
032: for (int j = 0; j < t.count(); j++) {
033: parseTable[i][j] = PARSE_ERROR;
034: }
035: }
036:
037: for (int i = 0; i < v.count(); i++) {
038: NonTerminal var = v.find(i);
039: List prodList = p.find(var);
040: Iterator itL = prodList.iterator();
041: while (itL.hasNext()) {
042: Production prod = (Production) itL.next();
043: Set first = g.first(prod);
044: Iterator it = first.iterator();
045: if (g.nullable(prod)) {
046: Set set = new LinkedHashSet(first);
047: set.addAll(g.follow(var));
048: it = set.iterator();
049: }
050: while (it.hasNext()) {
051: Terminal a = (Terminal) it.next();
052: int j = a.getIndex();
053: if (parseTable[i][j] != PARSE_ERROR) {
054: throw new RuntimeException("Grammar not LL1.");
055: } else {
056: parseTable[i][j] = prod.getIndex();
057: }
058: }
059: }
060: }
061: }
062:
063: public Production parseTable(NonTerminal x, Terminal a) {
064: int val = parseTable[x.getIndex()][a.getIndex()];
065: if (val == PARSE_ERROR) {
066: return null;
067: } else {
068: return p.find(val);
069: }
070: }
071:
072: public List parse() throws IOException, SyntaxError {
073: List pi = new LinkedList();
074: Word stack = new Word();
075: stack.addLast(t.EOF);
076: stack.addLast(s);
077: Terminal a = lexer.nextToken().getSymbol();
078:
079: while (true) {
080: Symbol x = stack.removeLast();
081: //System.out.println("a:"+a+" x:"+x);
082: if (x.isTerminal()) {
083: if (x.equals(t.EOF) && a.equals(t.EOF)) {
084: return pi; // accept
085: } else if (x.equals(a)) {
086: a = lexer.nextToken().getSymbol(); // match
087: } else {
088: throw new SyntaxError(a); // reject
089: }
090: } else {
091: Production prod = parseTable((NonTerminal) x, a);
092: if (prod == null) {
093: throw new SyntaxError(a); // reject
094: } else {
095: pi.add(prod); // expand
096: //System.out.println(prod);
097: Word w = prod.getRHS().mirror();
098: WordIterator it = w.iterator();
099: while (it.hasNext()) {
100: stack.addLast(it.next());
101: }
102: }
103: }
104: }
105: }
106:
107: private void printParseTable() {
108: if (parseTable != null) {
109: for (int i = 0; i < v.count(); i++) {
110: for (int j = 0; j < t.count(); j++) {
111: if (parseTable[i][j] != PARSE_ERROR) {
112: System.out.print("(" + v.find(i) + ","
113: + t.find(j) + "): ");
114: System.out.println(p.find(parseTable[i][j]));
115: }
116: }
117: }
118: }
119: }
120:
121: public static void main(String args[]) throws Exception {
122: if (args.length != 3) {
123: System.err
124: .println("args: <grammar_file> <lexer_class> <input_file>");
125: System.exit(1);
126: }
127:
128: LL1Parser parser = new LL1Parser(args[0]);
129: System.out.println(parser.getGrammar());
130:
131: parser.precompute();
132:
133: CFG g = parser.getGrammar();
134: g.printNullable();
135: g.printFirst();
136: g.printFollow();
137: parser.printParseTable();
138:
139: parser.setLexer(args[1], args[2]);
140: List pi = parser.parse();
141: Iterator it = pi.iterator();
142: while (it.hasNext()) {
143: System.out.println(it.next() + ";");
144: }
145: }
146: }
|